程序的解释：链表基本操作

秒速五厘米 2022-05-25 04:16 40阅读 0赞

`本实验中，我没有满足于老师给定的方法，而是自己将程序从头到尾重写了一遍。`

`我在几乎每个子函数的第一句加了判断单链表是否存在的语句，这样是为了使程序更加严谨。`

/**************************************************************************************************
    *                                   链表基本操作实验   *
    *该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和 *
    *主函数。程序中的单链表（带头结点）结点为结构类型，结点值为整型。   *
    *                                                              9/5/2018  13:40        史博辉     *
    ***************************************************************************************************/
    #include<stdio.h>
    #include<stdlib.h>
    /* 定义ElemType为int型 */
    typedef int ElemType;  //给int另起一个名字。
    #define TRUE 1
    #define FALSE 0
    #define NULL 0
    #define flag -1      //宏定义
    
    
    /* 单链表的结点类型 */
    typedef struct LNode{
     ElemType data;
     struct LNode *next;
    }LNode,*LinkedList;
    /* 初始化单链表 */
    LinkedList LinkedListInit()     //初始化链表，建立头结点，返回值为头结点。
    {
     LinkedList L;    //声明一个头结点
     L = (LinkedList)malloc(sizeof(LNode)); /*调用malloc函数，在内存中动态开辟一个长度为
     *结构体LNode的长度的空间，函数返回值强转为
     *一个指向结构体的指针类型LinkedList。    */
     L->next = NULL;
     return L;
    }
    /* 清空单链表 */
    void LinkedListClear(LinkedList L)  //清空链表，传递一个指向结构体类型的指针变量，无返回值。
    {
     if(L != NULL)
     {
     if(L->next == NULL)
     printf("单链表已经为空，不用清空！\n");
     else
     {
     LinkedList p;
     while(L->next)
     {
     p = L->next;
     L->next = p->next;
     free(p);
     }
     printf("单链表清空！\n");
     }
     }
     else
     printf("单链表尚未初始化！\n");
    }
    /* 检查单链表是否为空 */
    bool LinkedListEmpty(LinkedList L)
    {
     if(L != NULL)
     {
     if(L->next==NULL)
     return true;
     else
     return false;
     }
     else
     return true;
    }
    /* 遍历单链表 */
    void LinkedListTraverse(LinkedList L)
    {
     if(L != NULL)
     {
     LinkedList p;
     p = L->next;
     if(p == NULL)
     printf("单链表为空！");
     else
     {
     printf("单链表元素为：");
     while(p)
     {
     printf("%d ",p->data);
     p = p->next;
     }
     }
     printf("\n");
     }
     else
     printf("单链表尚未初始化！\n");
    }
    /* 求单链表长度 */
    int LinkedListLength(LinkedList L)
    {
     int len = 0;
     if(L != NULL)
     {
     LinkedList p;
     p = L->next;
     while(p)
     {
     len++;
     p = p->next;
     }
     return len;
     }
     else
     return -1;
    }
    /* 从单链表中查找与给定元素值相同的元素在链表中的位置 */
    int LinkedListLocate(LinkedList L,ElemType e)
    {
     if(L != NULL)
     {
     LinkedList p;
     int locate = 1;
     p = L->next; 
     if(p == NULL)
     return 0;
     else
     {
     while(p && p->data != e)
     {
     p = p->next;
     locate++;
     }
     if(p == NULL)
     return 0;
     else
     return locate;
     }
     }
     else
     return 0;
    }
    /* 从单链表中查找元素 */
    LinkedList LinkedListGet(LinkedList L,int i)
    {
     if(L != NULL)
     {
     LinkedList p;
     int num = 0;
     p = L->next;
     if(p == NULL)
     return NULL;
     else
     {
     while(p && num != i)
     {
     p = p->next;
     num++;
     }
     if(p == NULL)
     return NULL;
     else
     return p;
     }
     }
     else
     return NULL;
    }
    /* 向单链表中插入元素 */
    void LinkedListInsert(LinkedList L,int i,ElemType e)
    {
     if(L != NULL)
     {
     LinkedList p,q,s;
     int num = 0;
     p = L->next;
     q = L;
     while(p && num != i)
     {
     q = p;
     p = p->next;
     num++;
     }
     if(p == NULL)
     printf("单链表为空或插入位置不正确！\n");
     else
     {
     s = (LinkedList)malloc(sizeof(LNode));
     s->data = e;
     s->next = p;
     q->next = s;
     printf("插入完毕！\n");
     }
     }
     else
     printf("单链表尚未初始化！\n");
    }
    /* 从单链表中删除元素 */
    void LinkedListDel(LinkedList L,ElemType e)
    {
     if(L != NULL)
     {
     if(L->next == NULL)
     printf("单链表已为空，不能再进行删除！\n");
     else
     {
     LinkedList p,q;
     p = L->next;
     q = L;
     while(p->data != e && p != NULL)
     {
     q = p;
     p = p->next;
     }
     if(p == NULL)
     printf("单链表中没有该元素，因此删除失败！");
     else
     {
     e = p->data;
     q->next = q->next->next;
     free (p);
     printf("删除成功！\n");
     }
     }
     }
     else
     printf("单链表尚未初始化！\n");
    }
    /* 用尾插法建立单链表 */
    LinkedList LinkedListCreat()
    {
     LinkedList L = LinkedListInit();
     LinkedList p,q;
     int m=0,n;
     ElemType k;
     printf("请输入单链表元素个数:");
     scanf("%d",&n);
     if(n <= 0)
     return NULL;
     else
     {
     printf("请输入单链表元素：");
     for(m = 0;m<n;m++)
     {
     scanf("%d",&k);
     if(L->next == NULL)
     {
     p = (LinkedList)malloc(sizeof(LNode));
     p->data = k;
     L->next = p;
     p->next = NULL;
     }
     else
     {
     q = (LinkedList)malloc(sizeof(LNode));
     q->data = k;
     p->next = q;
     q->next = NULL;
     p = q;
     }
     }
     return L;
     }
    }
    void show()
    {
     printf("0.初始化单链表\n");
     printf("1.清空单链表\n");
     printf("2.检查单链表是否为空\n");
     printf("3.遍历单链表\n");
     printf("4.求单链表长度\n");
     printf("5.从单链表中查找与给定元素值相同的元素在链表中的位置\n");
     printf("6.从单链表中查找元素\n");
     printf("7.向单链表中插入元素\n");
     printf("8.从单链表中删除元素\n");
     printf("9.用尾插法建立单链表\n");
     printf("其他键退出\n");
    }
    
    
    void main()
    {
     LinkedList L=NULL,p;
     ElemType e;
     int a,i,locate;
     show();
     while(1){
     scanf("%d",&a);
     switch(a)
     {
     case 0:
     L = LinkedListInit();
     printf("单链表初始化完毕！\n");
     break;
     case 1:
     LinkedListClear(L);
     break;
     case 2:
     if(LinkedListEmpty(L))
     printf("单链表为空或尚未初始化！\n");
     else
     printf("单链表不为空！\n");
     break;
     case 3:
     LinkedListTraverse(L);
     break;
     case 4:
     i = LinkedListLength(L);
     if(i == -1)
     printf("单链表尚未初始化！\n");
     else
     printf("单链表长度为：%d\n",i);
     break;
     case 5:
     printf("请输入要查找的元素：");
     scanf("%d",&e);
     locate = LinkedListLocate(L,e);
     if(locate == 0)
     printf("查找失败，请检查单链表是否尚未初始化或单链表是否为空或单链表中是否无此元素！\n");
     else
     printf("找到该元素，下标为：%d\n",locate-1);
     break;
     case 6:
     printf("请输入要查找元素的下标：");
     scanf("%d",&i);
     p = LinkedListGet(L,i);
     if(p == NULL)
     printf("查找失败，请检查单链表是否尚未初始化或单链表是否为空或输入的下标是否超出单链表下标范围！\n");
     else
     printf("找到该元素为：%d\n",p->data);
     break;
     case 7:
     printf("请输入要插入元素的位置：");
     scanf("%d",&locate);
     printf("请输入要插入的元素：");
     scanf("%d",&e);
     LinkedListInsert(L,locate,e);
     break;
     case 8:
     printf("请输入要删除的元素：");
     scanf("%d",&e);
     LinkedListDel(L,e);
     break;
     case 9:
     L = LinkedListCreat();
     if(L)
     printf("单链表建立完毕！\n");
     else
     printf("单链表建立失败，原因：输入的元素个数有误!\n");
     break;
     default:
     exit(-1);
     }
    }
    }

程序解释：

1.首先，初始化单链表，这里声明了一个头结点，然后，为结点开辟一个新的空间，令其指针域为空，这样一个头结点就创建好了。

2.清空单链表：老师用的是直接将头结点的指针域置空，我觉得这样可能不太严谨，因此我选择了将结点逐个清空释放，最后留下头结点。

3.检查单链表是否为空：这里定义一个函数，返回值为bool类型，若单链表为空，则头结点的指针域为空，因此根据头结点的指针域可以判断出单链表是否为空。

4.遍历单链表：首先判断头结点的指针域是否为空，然后再对单链表进行遍历即可。

5.求单链表长度：定义一个计数器，遍历一遍单链表，求出其长度。

6.从单链表中查找与给定元素值相同的元素在链表中的位置：定义一个下标计数器，遍历单链表，根据下标计数器的值找出该元素。

7.从单链表中查找元素：直接遍历单链表，找出要查找元素的值即可。

8.向单链表中插入元素：首先定义一个计数器，根据计数器找到插入位置，插入元素即可。

9.从单链表中删除元素：直接找到要删除的元素，然后对该元素进行删除。

10.用尾插法建立单链表：这样设计是为了使建立好的单链表在遍历时是顺序排列。因此我的思路是先建立第一个结点，然后对后面的结点依次建立。

运行结果如下：

首先，尚未初始化的情况：

![20180510141824231][]

其次，初始化成功的情况：

![20180510142108727][]

![20180510142323921][]

[20180510141824231]: /images/20220525/00bde8f70b124c51a0f07167c9283973.png
[20180510142108727]: /images/20220525/4452252dbef747d198c1f9db819742e6.png
[20180510142323921]: /images/20220525/4b1225405b16470c9c28958ef1afe5c8.png