数据结构之带头节点的单链表增删改查操作实现

 

单链表的定义

什么是单链表

      单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。

      单链表的各个数据元素在物理上可以是离散存放的,每个结点除了存放数据元素外,还要存储指向下一个节点的指针。而顺序表是连续存放的,每个结点中只存放数据元素。

      单链表的优点:不要求大片连续空间,改变容量方便,只需在内存单元中随便找个位置作为新节点的区域;缺点:不可随机存储,要耗费一定空间存放指针。

      顺序表的优点:可随机存储,存储密度高;缺点:要求大片连续空间,改变容量不方便,要在内存中再申请一片连续空间。

先理解并记住专业术语 :

        首节点:第一个有效节点。

      尾节点:最后一个有效节点。

      头节点:头节点的数据类型和首节点的类型一样,没有存放有效数据,最最前面的,是在首节点之前的,主要是为了方便对链表的操作(不理解的话,先记住)。

      头指针:指向头节点的指针变量。

      尾指针:指向尾节点的指针。

 确定一个链表需要几个参数:(或者说如果期望一个函数对链表进行操作,我们至少需要接收链表的那些信息???)

        只需要一个参数:头指针,因为通过它我们可以推出链表的所有信息。

用代码定义一个单链表 

          大概思路:由一个个节点组成一个单链表 ,所以从定义节点出发,来创建单链表。那节点里都有什么呢?每个节点里不光有存放的数据元素,还要有一个指向下一个节点的指针。这两个也称为数据域和指针域。为什么要有指针域呢?因为单链表的每个节点在物理上是离散存放的,有了一个节点后,那下一个节点就需要通过这个节点找到,这个节点的指针域可以理解为起着连接的作用。需要注意的是指针域的类型是我们此时定义的节点类型。之后为了方便写代码和区分,用typedef 起了节点和节点指针的别名。单链表的英文单词是LinkList,LNode是简写了单链表节点的英文单词 LinkNode。

1 typedef struct LNode{ //定义单链表结点类型    //这种方式代码可读性更强
2     int data;//每个节点存放一个数据元素
3     struct LNode *next;//指针指向下一个节点
4 }LNode, *LinkList; //LNode 是struct LNode 的别名,LinkList是struct LNode *的别名,指针指向整个结构体

 

           在后续代码中 ,使用LinkList,强调这是一个单链表; 使用LNode,强调这是一个节点。

 

1 void test()
2 {
3       LinkList L; // //声明一个指向单链表的指针,强调声明了一个单链表
4 }

 

 

 

 初始化单链表

        大概思路:在初始化的过程中,给单链表分配好一个头节点,让头节点的指向下一个节点的指针域指向空,因为在整个单链表中,此时还是空表,也就是没有有效节点,头节点虽然起着节点的名字,并且在写专业术语的时候说过,它只是为了便于操作,注意不要混淆了。

 

 1 bool InitList(LinkList &L) //初始化一个单链表(带头结点)
 2 {
 3     L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点,malloc函数强调返回是一个节点(LNode *),如果单链表有头节点,则头指针指向头节点,即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
 4     if(L == NULL) //内存不足,分配失败,就没有创建出单链表,因为已经分配了一个节点,所以只能内存不足的原因,空表是没有节点
 5         return false;
 6     L->next = NULL;//目前只有一个头节点,头节点之后暂时还没有节点
 7     return true;
 8 }
 9 void test()
10 {
11     LinkList L; //声明一个指向单链表的指针
12     InitList(L); //初始化一个空表
13     // .......后续代码......
14 }

 

 

 如果要判断带头节点的单链表是否为空,代码如下:

 

1 bool Empty(LinkList L) //判断单链表是否为空(带头节点) 头节点不存储数据,只有指针域,且表内没有有效节点
2 {
3     if(L->next == NULL)
4         return true;
5     else
6         return false;
7 }

 

 

带头结点的单链表的插入操作

     

InsertList(&L,i,e):插入操作。在表 L 中的第 i 个位置上插入指定元素 e,刚开始建议看b站的动画,再来理解代码 。

     利用while循环找到第 i - 1 个结点,将新结点插入其后,头结点可以看作 “ 第0个” 结点。

     

 1 bool InsertList(LinkList &L, int i, ElemType e) //在第 i 个位置插入元素 e (带头结点)
 2 {
 3     if(i < 1) //只能在头结点之后插入,头结点是第0个,之后是第1个
 4         return false;
 5     LNode *p; //LNode * 强调这是一个结点,声明一个结点,表示指针p指向当前找到的结点
 6     p = L; //L是指向头结点的头指针,再把刚开始的指针p指向L,表示目前的指针p指向头结点
 7     int j = 0;//记录当前p指向的是第几个结点,从头结点0开始
 8     while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点,j = i-1,不进入循环,内存满了,不进入循环
 9     {
10         p = p->next; //p指向下一个结点
11         j++;
12     }
13     if(p==NULL) //i值不合法,如果有4个结点,那i不能等于6,因为 p = p->next,在第5个位置之后满了,p指向NULL,下一步p->next出错了,根本找不到表的某个位置
14         return false;
15     LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点,这个节点的数据域就是e
16     s->data = e;
17     s->next = p->next;  //自己画图理解,一开始p后的节点不是s,这里让p的下一个节点变成了在s的下一个节点
18     p->next = s; //将结点s连到p之后
19     return true; //插入成功
20 }

 

 

带头结点的单链表的删除操作

     DeleteList(&L,i,&e):删除操作。删除表L中第 i 个位置的元素,并用e返回删除元素的值。

     利用while循环找到第 i - 1 个结点,将其指针指向 第 i + 1个结点,并释放第 i 个结点。

 1 bool DeleteList(LinkList &L, int i, ElemType &e)
 2 {
 3     if(i < 1)
 4         return false;
 5     LNode *p;
 6     p = L;
 7     int j = 0;
 8     while(p != NULL && j < i - 1) //循环找第 i-1 个节点
 9     {
10         p = p->next;
11         j++;
12     }
13     if(p == NULL) //i值不合法,导致第 i-1 个节点根本在表中找不到
14         return false;
15     if(p->next == NULL) //第 i-1 个节点能找到,但是刚好第 i-1 个节点之后已无其他节点(第i个结点和第i+1个节点没有了),那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
16         return false;
17     LNode *q = p->next; //p是第 i-1 个节点,p->next是之后的节点,也是第 i 个节点,令q指向被删除节点
18     e = q->data; //用e返回元素的值
19     p->next = q->next; //将*q 节点从链中断开,重新更改指针p的指向,指向第 i + 1个节点
20     free(q); //释放节s点的存储空间
21     return true;
22 }

 

 带头结点的单链表的修改操作

  UpdateList(&L, i, num):修改操作,把第i个位置的数修改为num

 1 int UpdateList(LinkList &L, int i, int num)//把第i个位置的数修改为num
 2 {
 3    if(i < 0)//有头节点,头节点是第0个节点,所以查找元素i不能小于0
 4         return 0;
 5     LNode *p;
 6     int j = 0;
 7     p = L;
 8     while(p != NULL && j < i) //找的是第i个节点,插入那里找的是第i-1 个节点
 9     {  //如果i大于表的长度,那循环找到的p会指向NULL,不会进入循环体,最后返回NULL
10         p = p->next;
11         j++;
12     }
13     p->data = num;
14     return p->data;    
15 }

 

带头结点的单链表的查找操作

     GetList(L,i):按位查找操作。获取表L中第 i 个位置的元素的值。

      

 1 int GetList(LinkList L, int i)//按位查找,返回第 i 个元素(带头节点)
 2 {
 3     if(i < 0)//有头节点,头节点是第0个节点,所以查找元素i不能小于0
 4         return NULL;
 5     LNode *p;
 6     int j = 0;
 7     p = L;
 8     while(p != NULL && j < i) //找的是第i个节点,插入那里找的是第i-1 个节点
 9     {  //如果i大于表的长度,那循环找到的p会指向NULL,不会进入循环体,最后返回NULL
10         p = p->next;
11         j++;
12     }
13     return p->data;
14 } //平均时间复杂度为O(n)

 

 

带头结点的单链表的销毁操作

        利用while循环把头节点之后的有效节点free掉。

 

 1 void Destroy(LinkList &L)
 2 {
 3     LNode *p;
 4     while(L != NULL)
 5     {
 6         p = L;
 7         L = L->next;
 8         free(p);
 9     }
10 }

 

 完整的增删改查操作的代码,我自己一开始全写在main函数里,只能调用成功一个函数,我也不知道为啥,所以就用了switch选择结构来分别实现这些功能。这些代码理解了,就不难,建议多敲几遍!

 

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 typedef struct LNode{ //定义单链表结点类型    //这种方式代码可读性更强
  4     int data;//每个节点存放一个数据元素
  5     struct LNode *next;//指针指向下一个节点
  6 }LNode, *LinkList; //LNode 是struct LNode 的别名,LinkList是struct LNode *的别名,指针指向整个结构体
  7 bool InitList(LinkList &L) //初始化一个单链表(带头结点)
  8 {
  9     L = (LNode *)malloc(sizeof(LNode)); //分配一个头节点,malloc函数强调返回是一个节点(LNode *),如果单链表有头节点,则头指针指向头节点,即 LinkList L = (LNode *)malloc(sizeof(LNode)); 等号有指向作用
 10     if(L == NULL) //内存不足,分配失败,就没有创建出单链表,因为已经分配了一个节点,所以只能内存不足的原因,空表是没有节点
 11         return false;
 12     L->next = NULL;//目前只有一个头节点,头节点之后暂时还没有节点
 13     return true;
 14 }
 15 bool InsertList(LinkList &L, int i, int e) //在第 i 个位置插入元素 e (带头结点)
 16 {
 17     if(i < 1) //只能在头结点之后插入,头结点是第0个,之后是第1个
 18         return false;
 19     LNode *p; //LNode * 强调这是一个结点,声明一个结点,表示指针p指向当前找到的结点
 20     p = L; //L是指向头结点的头指针,再把刚开始的指针p指向L,表示目前的指针p指向头结点
 21     int j = 0;//记录当前p指向的是第几个结点,从头结点0开始
 22     while(p!= NULL && j < i - 1) //循环找到第 i-1 个结点,j = i-1,不进入循环,内存满了,不进入循环
 23     {
 24         p = p->next; //p指向下一个结点
 25         j++;
 26     }
 27     if(p==NULL) //i值不合法,如果有4个结点,那i不能等于6,因为 p = p->next,在第5个位置之后满了,p指向NULL,下一步p->next出错了,根本找不到表的某个位置
 28         return false;
 29     LNode *s = (LNode *)malloc(sizeof(LNode));//创建一个节点,这个节点的数据域就是e
 30     s->data = e;
 31     s->next = p->next;  //自己画图理解,一开始p后的节点不是s,这里让p的下一个节点变成了在s的下一个节点
 32     p->next = s; //将结点s连到p之后
 33     return true; //插入成功
 34 }
 35 void ShowList(LinkList L) //显示
 36 {
 37     if(L->next == NULL)
 38        printf("这是一个空表\n"); 
 39     while(L != NULL)
 40     {
 41         L = L->next;
 42         printf("%d ",L->data);
 43     }
 44     
 45 }
 46 bool DeleteList(LinkList &L, int i, int &e)//删除表L中第 i 个位置的元素,并用e返回删除元素的值。
 47 {
 48     if(i < 1)
 49         return false;
 50     LNode *p;
 51     p = L;
 52     int j = 0;
 53     while(p != NULL && j < i - 1) //循环找第 i-1 个节点
 54     {
 55         p = p->next;
 56         j++;
 57     }
 58     if(p == NULL) //i值不合法,导致第 i-1 个节点根本在表中找不到
 59         return false;
 60     if(p->next == NULL) //第 i-1 个节点能找到,但是刚好第 i-1 个节点之后已无其他节点(第i个结点和第i+1个节点没有了),那就没有办法把第 i-1 个节点的指向下一个节点的指针指向第 i+1 个节点
 61         return false;
 62     LNode *q = p->next; //p是第 i-1 个节点,p->next是之后的节点,也是第 i 个节点,令q指向被删除节点
 63     e = q->data; //用e返回元素的值
 64     p->next = q->next; //将*q 节点从链中断开,重新更改指针p的指向,指向第 i + 1个节点
 65     free(q); //释放节s点的存储空间
 66     return true;
 67 }
 68 int GetList(LinkList &L, int i)//按位查找,返回第 i 个元素(带头节点)
 69 {
 70     if(i < 0)//有头节点,头节点是第0个节点,所以查找元素i不能小于0
 71         return 0;
 72     LNode *p;
 73     int j = 0;
 74     p = L;
 75     while(p != NULL && j < i) //找的是第i个节点,插入那里找的是第i-1 个节点
 76     {  //如果i大于表的长度,那循环找到的p会指向NULL,不会进入循环体,最后返回NULL
 77         p = p->next;
 78         j++;
 79     }
 80     return p->data;
 81 } //平均时间复杂度为O(n)
 82 int UpdateList(LinkList &L, int i, int num)
 83 {
 84    if(i < 0)//有头节点,头节点是第0个节点,所以查找元素i不能小于0
 85         return 0;
 86     LNode *p;
 87     int j = 0;
 88     p = L;
 89     while(p != NULL && j < i) //找的是第i个节点,插入那里找的是第i-1 个节点
 90     {  //如果i大于表的长度,那循环找到的p会指向NULL,不会进入循环体,最后返回NULL
 91         p = p->next;
 92         j++;
 93     }
 94     p->data = num;
 95     return p->data;    
 96 }
 97 void Destroy(LinkList &L) //销毁单链表 
 98 {
 99     LNode *p;
100     while(L != NULL)
101     {
102         p = L;
103         L = L->next;
104         free(p);
105     }
106 }
107 void ShowMenu()
108 {
109     printf("************************\n");
110     printf("*****  1,添加数据  *****\n");
111     printf("*****  2,删除数据  *****\n");
112     printf("*****  3,查找数据  *****\n");    
113     printf("*****  4,修改数据  *****\n");
114     printf("*****  5,显示数据  *****\n");
115     printf("*****  0,销毁并退出  ***\n");
116 }
117 int main()
118 {
119     LinkList L;//声明一个单链表 
120     InitList(L);//初始化函数调用 
121 
122     int select = 0; //创建选择输入的变量
123     while (true)
124     {
125         //菜单调用
126         ShowMenu();
127         printf("请输入你的选择\n");
128         scanf("%d", &select);
129         switch (select)
130         {
131         case 1: //1,添加数据
132             InsertList(L,1,1);
133             InsertList(L,2,2);  
134             InsertList(L,3,3);
135             InsertList(L,4,4);
136             InsertList(L,5,5);
137             printf("数据添加成功!\n");
138             getchar();
139             break;
140         case 2: //2,删除数据
141             int e;
142             if(DeleteList(L,4,e))
143             {
144                 printf("删除的数是:%d\n",e);
145             }
146             getchar();
147             break;
148         case 3: //3,查找数据
149             printf("查找的元素是:%d\n",GetList(L,1));
150             getchar();
151             break;
152         case 4: //4,修改数据
153             UpdateList(L,1,0);
154             printf("修改成功!\n"); 
155             getchar();
156             break;            
157         case 5: //4,显示数据
158             printf("单链表的数据有:"); 
159             ShowList(L);
160             getchar();
161             break;
162         case 0: //0,退出
163             Destroy(L);
164             printf("单链表已销毁!");
165             printf("欢迎下次使用");
166             return 0;
167             break;
168 
169         default:
170             break;
171         }
172     }
173     return 0;
174 }    

 

 

运行结果如下:

       在单链表中添加数据并显示数据成功:

     

     在单链表中删除数据并显示数据成功:

 

 在单链表中查找数据并显示数据成功:

 

 在单链表中修改数据并显示数据成功:

 

 

 

 

 

热门相关:恭喜你被逮捕了   闺范   裙上之臣   上神来了   锦庭娇