熟练进行链表的基本操作，编程实现动态链表的建立 插入 删除和输出操作这个实验不怎么会

Question

熟练进行链表的基本操作，编程实现动态链表的建立 插入 删除和输出操作
这个实验不怎么会，想问问朋友们

Answer 1

供参考：

#include <malloc.h>
#include <stdio.h>
typedef int ElemType;
typedef struct node
{
    ElemType  data; //数据域
    struct node* next; //指针域
} SLinkNode; //单链表类型

void DestroyList(SLinkNode*& L) //销毁单链表L
{
    SLinkNode* pre = L, * p = pre->next;
    while (p != NULL)
    {
        free(pre);
        pre = p;
        p = p->next; 
    }
    free(pre);
}
int GetLength(SLinkNode* L) //求单链表L的长度
{
    int i = 0;
    SLinkNode* p = L->next;
    while (p != NULL)
    {
        i++;
        p = p->next;
    }
    return i;
}
int GetElem(SLinkNode* L, int i, ElemType& e) //求第i个结点值e
{
    int j = 0;
    SLinkNode* p = L; //p指向头结点，计数器j置为0
    if (i <= 0) return 0; //参数i错误返回0
    while (p != NULL && j < i)
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return 0; //未找到返回0
    else
    {
        e = p->data;
        return 1; //找到后返回1
    }
}
int Locate(SLinkNode* L, ElemType e) //求第一个值为e的结点的逻辑序号
{
    SLinkNode* p = L->next;
    int j = 1; //p指向第一个数据结点，j置为其序号1
    while (p != NULL && p->data != e)
    {
        p = p->next;
        j++;
    }
    if (p == NULL) return(0); //未找到返回0
    else return(j); //找到后返回其序号
}
int InsElem(SLinkNode*& L, ElemType x, int i) //插入结点值为x的结点
{
    int j = 0;
    SLinkNode* p = L, * s;
    if (i <= 0) return 0; //参数i错误返回0
    while (p != NULL && j < i - 1) //查找第i-1个结点*p
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return 0; //未找到第i-1个结点时返回0
    else //找到第i-1个结点p
    {
        s = (SLinkNode*)malloc(sizeof(SLinkNode));
        s->data = x; //创建存放元素x的新结点s
        s->next = p->next; //将s结点插入到p结点之后
        p->next = s;
        return 1; //插入运算成功,返回1
    }
}
int DelElem(SLinkNode*& L, int i) //删除第i个结点
{
    int j = 0;
    SLinkNode* p = L, * q;
    if (i <= 0) return 0; //参数i错误返回0
    while (p != NULL && j < i - 1) //查找第i-1个结点
    {
        j++;
        p = p->next;
    }
    if (p == NULL)
        return 0; //未找到第i-1个结点时返回0
    else //找到第i-1个结点p
    {
        q = p->next; //q指向被删结点
        if (q == NULL)
            return 0; //没有第i个结点时返回0
        else
        {
            p->next = q->next; //从单链表中删除q结点
            free(q); //释放其空间
            return 1;
        }
    }
}
void DispList(SLinkNode* L) //输出单链表
{
    SLinkNode* p = L->next;
    while (p != NULL)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}
//采用头插法建表的算法
void CreateListF(SLinkNode*& L, ElemType a[], int n)
{
    SLinkNode* s;
    int i;
    L = (SLinkNode*)malloc(sizeof(SLinkNode)); //创建头结点
    L->next = NULL; //头结点的next域置空，表示一个空单链表
    for (i = 0; i < n; i++) //遍历a数组所有元素
    {
        s = (SLinkNode*)malloc(sizeof(SLinkNode));
        s->data = a[i]; //创建存放a[i]元素的新结点s
        s->next = L->next; //将s插在头结点之后
        L->next = s;
    }
}
//采用尾插法建表的算法
void CreateListR(SLinkNode*& L, ElemType a[], int n)
{
    SLinkNode* s, * tc;
    int i;
    L = (SLinkNode*)malloc(sizeof(SLinkNode)); //创建头结点
    tc = L; //tc始终指向尾结点,开始时指向头结点
    for (i = 0; i < n; i++)
    {
        s = (SLinkNode*)malloc(sizeof(SLinkNode));
        s->data = a[i]; //创建存放a[i]元素的新结点s
        tc->next = s; //将s插入tc之后
        tc = s;
    }
    tc->next = NULL; //尾结点next域置为NULL
}
int main()
{
    SLinkNode* L = NULL, * L1 = NULL;
    ElemType n, a[20] = { 0 }, i, e;
    scanf("%d", &n);
    for (i = 0; i < n; i++)//（1）输入一组长度不超过20的整数元素
        scanf("%d", &a[i]);


    //***使用头插法建立一个带头结点的单链表***
    CreateListF(L, a, n);//（1）使用头插法建立一个带头结点的单向链表
    printf("L:");
    DispList(L);         //（2）显示单链表
    printf("L的长度:%d\n", GetLength(L)); //（2）显示单链表的长度
    i = 3;
    GetElem(L, i, e);
    printf("第%d个位置的值:%d\n", i, e); //（3）显示第3个位置的值
    e = 5;
    printf("元素%d的位置:%d\n", e, Locate(L, e));//（3）显示链表中某个元素是第几个位置
    i = 4; e = 10;
    DelElem(L, i);  //（4）删除第4个位置元素
    InsElem(L, e, i);//（4）往第4个位置插入元素10
    printf("L:");
    DispList(L);   //（4）显示单链表


    //***使用尾插法建立一个带头结点的单链表***
    printf("\n");
    CreateListR(L1, a, n);//（1）使用尾插法建立一个带头结点的单向链表
    printf("L1:");
    DispList(L1);         //（2）显示单链表
    printf("L1的长度:%d\n", GetLength(L1)); //（2）显示单链表的长度
    i = 3;
    GetElem(L1, i, e);
    printf("第%d个位置的值:%d\n", i, e); //（3）显示第3个位置的值
    e = 5;
    printf("元素%d的位置:%d\n", e, Locate(L1, e));//（3）显示链表中某个元素是第几个位置
    i = 4; e = 10;
    DelElem(L1, i);  //（4）删除第4个位置元素
    InsElem(L1, e, i);//（4）往第4个位置插入元素10
    printf("L1:");
    DispList(L1);   //（4）显示单链表
    return 0;
}