单链表的创建算法

浅浅的花香味﹌ 2022-07-28 00:26 176阅读 0赞

**单链表的创建算法**

**本文根据：清华大学出版社《数据结构与算法(C语言版)(第3版)》整理，详细请见书本。**

当一个序列中只含有指向它的后继结点的链接时，就称该链表为单链表。

单链表的示意图如下：

![Center][]  
Head指针为单链表的头指针，单链表L：L既是单链表的名字，也是其头指针。链表中的最后一个结点的指针域定义为空指针(NULL)。  
单链表的定义：

struct Node
     {
       ElemType data;
       struct Node *next;
     };
     typedef struct Node LNode;
     typedef struct Node *LinkedList;

单链表有带头结点和不带头结点之分。

上图为没有头结点的单链表，下图为带有头结点的单链表：

![Center 1][]

#  1.单链表的初始化，即建立一个空链表。 #

//不带头结点的单链表的初始化
      void LinkedListInit1(LinkedList L)
      {
        L=NULL;
      }
      //带头结点的单链表的初始化
      void LinkedListInit2(LinkedList L)
      {
        L=(LNode *)malloc(sizeof(LNode));
        if(L==NULL)
        {
          printf("申请空间失败！");
          exit(0);
        }
        L->next=NULL;
      }

#  2.单链表的求表长操作 #

单链表的求表长操作需要设定当前指针p和一个计数器j，初始时p指向链表中的第一个结点，p每向下移动一个结点时，j就加1，直到到达p链表的尾部。带头结点的链表，链表长度不包括头结点。

//带头结点的单链表求表长
      int LinkedListLength(LinkedList L)
      {
        LNode *p;            //p需要声明为LNode类型
        p=L->next;
        int j=0;
        while(p!=NULL)
        {
          j++;
          p=p->next;         //将p向下移动一个结点
        }
        return j;
      }

#  3.单链表获取第i个结点元素的操作 #

设定p为当前结点，初始时p指向链表的第一个结点，然后向下移动i，此时p所指向的元素就是需要查找的第i个结点元素。

//带头结点的单链表取元素操作
      LinkedList LinkedListGetINode(LinkedList L, int i)
      {
        LNode *p;
        p=L->next;
        int j=1;
        while((p!=NULL)&&(j<i))
        {
          p=p->next;
          j++;
        }
        return p;
      }

#  4.单链表的定位操作 #

查找元素e第一次出现的位置。从链表的第一个结点开始，判断当前结点的值是否等于e，等于则返回该结点的指针，否则继续向后查找，直至到达链表的最后。

//带头结点的单链表定位操作
      LNode LinkedListLocateE(LinkedList L, ElemType e)
      {
        LNode *p;
        p=L->next;
        while((p!=NULL)&&(p->data!=e))
        {
          p=p->next;
        }
        return p;
      }

#  5.单链表的插入操作 #

在结点p之前插入一个新的结点q:对于不带头结点的单链表，结点p的位置有所不同，插入操作有以下两种情况：  
1)在链表的表头插入：  
(1)创建一个新的结点q。  
(2)将此结点的数据域赋值为e，并将它的next指针指向第一个结点，即L。  
(3)将L修改为指向新的结点q。  
操作示意图如下：

![Center 2][]  
2)在链表的中间插入  
(1)创建一个新的结点q。  
(2)将此结点的数据域赋值为e，并将它的next指针指向p。  
(3)查找到p的前驱结点pre。  
(4)将pre的next指针指向新创建的结点q。  
操作示意图如下：  
![Center 3][]

//不带头结点的单链表的插入操作
        void LinkedListInertQE1(LinkedList L, LinkedList p, ElemType e)
        {
          q=(LNode *)malloc(sizeof(LNode));        //创建一个新的结点q
          if(q==NULL)
          {
            printf("申请空间失败！");
            exit(0);
          }
          q->data=e;
    
          if(p==L)   //在表头插入
          {
            q->next=L;
            L=q;
          }
          else      //在表的中间进行插入
          {
            pre=L;
            while((pre!=NULL)&&(pre->next!=p))           //寻找p的前驱
               pre=pre->next;
    
            q->next=pre->next;
            pre->next=q;
          }
        }
    
        //带头结点的单链表的插入操作
        void LinkedListInertQE2(LinkedList L, LinkedList p, ElemType e)
        {
          q=(LNode *)malloc(sizeof(LNode));        //创建一个新的结点q
          if(q==NULL)
          {
            printf("申请空间失败！");
            exit(0);
          }
          q->data=e;
    
          //插入新的结点
          pre=L;
          while((pre!=NULL)&&(pre->next!=p))           //寻找p的前驱
            pre=pre->next;
    
          q->next=pre->next;
          pre->next=q;
        }

#  6.单链表的删除操作 #

删除链表中的某个元素e，如果e在链表中出现不止一次，将删除第一次出现的e，否则什么也不做。  
用p找到元素e所在的结点：  
1)p是链表中的第一个结点  
(1)将L指向p->next。  
(2)释放p。  
示意图如下：

![Center 4][]

2)p是链表中的其他结点  
(1)找到p的前驱结点pre。  
(2)将pre->next指向p->next。  
(3)释放p。  
示意图如下：

![Center 5][]

//不带头结点的单链表的删除操作
         void LinkedListDeleteQE1(LinkedList L, LinkedList p, ElemType e)
         {
            pre=L;
            while((pre!=NULL)&&(pre->next->data!=e))      //查找元素e的前驱
                pre=pre->next;
            p=pre->next;
    
            if(p!=NULL)                //找到需要删除的结点
            {
              if(p==L)                 //删除的是第一个结点
                L=p->next;
              else                     //删除的是其他结点
                pre->next=p->next;
              free(p);
            }
         }
         //带头结点的单链表的删除操作
         void LinkedListDeleteQE2(LinkedList L, LinkedList p, ElemType e)
         {
            pre=L;
            while((pre!=NULL)&&(pre->next->data!=e))      //查找元素e的前驱
                pre=pre->next;
            p=pre->next;
    
            if(p!=NULL)                //找到需要删除的结点
            {
              pre->next=p->next;
              free(p);
            }
         }

#  7.单链表的创建操作 #

单链表的创建方法有两种：头插法和尾插法。  
头插法是将新增结点插入第一个结点之前，示意图如下：

![Center 6][]  
尾插法是将新增结点插入最后一个结点之后，示意图如下：

![Center 7][]

//用头插法创建带头结点的单链表
        void LinkedListCreateHeadL(LinkedList L, ElemType a[n])
        {
          L=(LNode *)malloc(sizeof(LNode));
          if(L==NULL)
          {
            printf("申请空间失败！");
            exit(0);
          }
          L->next=NULL;
    
          for(i=0; i<n; i++)
          {
            p=(LNode *)malloc(sizeof(LNode));
            if(p==NULL)
            {
              printf("申请空间失败！");
              exit(0);
            }
    
            p->data=a[i];
            p->next=L->next;
            L->next=p;
          }
        }
        //用尾插法创建带头结点的单链表
        void LinkedListCreateTailL(LinkedList L, ElemType a[n])
        {
          L=(LNode *)malloc(sizeof(LNode));
          if(L==NULL)
          {
            printf("申请空间失败！");
            exit(0);
          }
          L->next=NULL;
          tail=L;         //设置尾指针，方便插入
    
          for(j=0; j<n; j++)
          {
            p=(LNode *)malloc(sizeof(LNode));
            if(p==NULL)
            {
              printf("申请空间失败！");
              exit(0);
            }
    
            p->data=a[j];
            p->next=NULL;
            tail->next=p;
            tail=p;
          }
        }

#  8.单链表的合并操作 #

首先设置3个指针pa、pb、pc, pa和pb分别指向链表La与Lb的当前待比较插入结点，pc指向链表Lc的最后一个结点。当pa->data≤pb->data时，将pa所指的结点插入到pc后面，否则就将pb所指的结点插入到pc后面。最后，当有一个表合并完，将另一个表剩余的结点全插入到pc。

//带头结点的单链表合并操作
        void LinkedListMergeLaLb(LinkedList La, LinkedList Lb, LinkedList Lc)
        {
          pa=La->next;
          pb=Lb->next;
          Lc=La;          //借用表La的头结点作为表Lc的头结点
          pc=Lc;
    
          while((pa!=NULL)&&(pb!=NULL))
          {
            if(pa->data<=pb->data)
            {
              pc->next=pa;
              pc=pa;
              pa=pa->next;
            }
            else
            {
              pc->next=pb;
              pc=pb;
              pb=pb->next;
            }
          }
          if(pa!=NULL)
            pc=pa->next;
          else
            pc=pb->next;
    
          free(pb);    //将Lb的表头结点释放
        }

#  附录： #

程序实例：尾插法创建单链表

首先在VS2010中新建Win32 控制台应用程序的项目LinkedList，结果如下：

![Center 8][]

LinkedList.cpp : 定义控制台应用程序的入口点。

// LinkedList.cpp : 定义控制台应用程序的入口点。
    
        #include "stdafx.h"
    
        #include<stdio.h>
        #include<stdlib.h>
        typedef struct node
        {
          int data;
          struct node *next;
        }*LinkedList;
    
        LinkedList LinkedListCreateTailL(int a[8])
        {
          LinkedList p, L, tail;
          int i=0;
          L=(struct node*)malloc(sizeof(struct node));
          tail=L;
    
          for(i=0; i<8; i++)
          {
            p=(struct node*)malloc(sizeof(struct node));
            p->data=a[i];
            tail->next=p;
            tail=p;
          }
          tail->next=NULL;
          return L;
        }
    
        void LinkedListPrint(LinkedList L)
        {
          LinkedList p;
          p=L->next;
          while(p!=NULL)
          {
            printf("%d ",p->data);
            p=p->next;
          }
        }
    
        void main()
        {
          int a[8], i;
          LinkedList L;
          printf("请输入8个列表元素，以回车结束：\n");
    	  for(i=0; i<8; i++)
          {
            scanf("%d", &a[i]);
          }
    
          L=LinkedListCreateTailL(a);
          LinkedListPrint(L);
        }

Ctrl+F5执行以上cpp文件，程序运行截图：

![Center 9][]

[Center]: /images/20220727/5f521584e0914a198c13391fef04d676.png
[Center 1]: /images/20220727/06346cac0f5b439ba2504a16a052e02f.png
[Center 2]: /images/20220727/c51004391f8a49839990ec42e142aa77.png
[Center 3]: /images/20220727/56d8a536033442bca4ee44669355a4c5.png
[Center 4]: /images/20220727/5ecdf318109d4317b4324748c6f66dea.png
[Center 5]: /images/20220727/aa159d054bc54e82a14da15bb6c691e5.png
[Center 6]: /images/20220727/ff2d5cd094ce4258b149de5a18786fb9.png
[Center 7]: /images/20220727/466e057fdb084848bb7f9d8f02e9d56c.png
[Center 8]: /images/20220727/abb3ec1d02a04eeabe528174f43f439a.png
[Center 9]: /images/20220727/4b4dd0e1fad1431084fd73e4f4323540.png