当前位置:   article > 正文

线性表:关于链表(主要以单链表为例)的相关理解和应用

线性表:关于链表(主要以单链表为例)的相关理解和应用

多清澈这天空 晴雨相拥 同心逐梦!

坚守我信心  一路出众!!

首先,按照惯例,欢迎大家边听歌边观看本博客

▶ 紫荆花盛开 (163.com)(建议复制链接,浏览器打开,csdn打开太慢了)

2022香港回归祖国25周年主题歌曲,好听!!!

一.单链表

首先 大家肯定知道链表的表达方式,如下

  1. typedef struct LNode
  2. {
  3. ElemType data;
  4. struct LNode *next;
  5. }LinkNode;

定义一个LNode,node节点,结点,L是link,表示链接,所以叫做LNode链接结点构成链表

第一个存放元素的信息,链表的特点就是多存了一个节点(指针域)指向后继节点。

0.1稍微浅浅的给大家补充一下结构体的知识点:

1.一个正常的结构体代码编写

  1. struct
  2. {
  3. int num;
  4. char name[20];
  5. char sex;
  6. float score;
  7. }boy1,boy2;

你可以直接在boy2后面打个{ }初始化,在使用boy的时候我们可以具体到一个成员如boy1.num 即为boy1结构体的num成员

然后接下来其实更加常见的定义是这样子的

  1. struct stu
  2. {
  3. int num;
  4. char name[20];
  5. char sex;
  6. float score;
  7. }*boy1,boy2; //boy1是结构体指针,boy2是结构体

这时候我们对指向结构体的指针标表示的成员方式有所不同,可表示为(*boy1).num或者boy1->num(熟悉吧,这里算是补充一下知识点)都可以。一般配合malloc(与free)或者c++中的new(delete)函数使用,主要是结构体指针自创立开始指向的空间就不存在,所以我们得开辟一个空间给他们. 

1.1理解一些易混概念

        本来吧,其实我真想按课本讲一遍,但是感觉有点浪费时间,而且课本那些加深不了我的理解,所以干脆我就直接把我的理解说了,如果有错,希望各位大佬指正!

温馨提示:接下来的话可能有点绕口令!!

第一:节(结)点

我们知道一个节点包括了他的数据域和他的指针域

数据域存放他的data,指针域存放下一个节点的地址,其中在第一个的叫做头结点,头结点链接的第一个节点叫做首节点,最后一个节点叫做尾结点。经常会出现R指针,我管他叫标记指针,用于记住我们要操作的节点的下一个地址,免得链表丢失,至少现在我知道的就是这点,其中^表示NULL。

ok,接下来,来解决几个知识,保证我们看得到接下来的代码,懂了应该就会写了吧

1.对指针赋值相当于就是让指针指向哪里

1.1:比如Lode *r=L;让r指向头结点L。

1.2:pre=p;(pre和p都是指针),让pre指向p(指向的地址)

1.3:p=p->next p指向下一位(详细一点:p->next在等号后面表示解引用,指的是p指向的结构体的指针域的地址(表示这个结构体的下一个地址))

1.4:r->next=p 这个指的是让r对应的结构体指向p(而非指针r指向p,此时的r相当于标记指针)

1.5:s->next=p->next;p->next=s;像这种我们就推荐画图理解

1.6:p=L->next->next表示p指向L的下下指针域而L->next->next=NULL则指的是L的下一个节点的指针域为空,如下图所示

 

 2.链表的基本功能

相信大家已经对链表有了初步的了解,现在我们来一个一个实现他们

2.1链表创建与初始化

  1. typedef char ch
  2. typedef struct LNode
  3. {
  4. ch data;
  5. struct LNode* next;
  6. }Linknode;
  7. 初始化
  8. void InitLnode(LinkNode *&L){
  9. L=new LinkNode;
  10. L->next=NULL;
  11. }

 2.2插入

这里就不得不讲讲插入的两种方法

2.2.1头插法

思路示意图如下:

  1. LinkList Headinster(LinkList &L,int n){
  2. LNode *s;
  3. int x=1;
  4. L= (LinkList)malloc(sizeof(LNode));
  5. L->data=x++;
  6. L->next=NULL;
  7. while(x!=n){
  8. s=(LNode*) malloc(sizeof(LNode));
  9. s->data=x;
  10. s->next=L;
  11. L=s;
  12. x++;
  13. }
  14. return L;
  15. }

 

核心代码

  1. s->next=L->next; ①
  2. L->next=s; ②

 作用效果就是从头结点和首节点插入新的元素,从而导致先插进来的反而在后面

这里借用一下大佬的动图(侵权删)

2.2.2尾插法

顾名思义就是从尾部开始插入由于新的节点插入后成为新的尾部,所以我们需要用一个指针R去更新尾部节点(始终指向尾部)

大概像这样子

  1. LinkList TailInster(LinkList &L,int n){
  2. int x=1;
  3. L= (LinkList)malloc(sizeof(LNode));
  4. LNode *s,*r=L;
  5. while(x!=n){
  6. s=(LNode*) malloc(sizeof(LNode));
  7. s->data=x;
  8. r->next=s;
  9. r=s;
  10. x++;
  11. }
  12. r->next=NULL;
  13. return L;
  14. }

核心代码

  1. r->next=s; //①r的指针域指向S(让新结点插入到链表)
  2. r=s; //②r指针指向s(保持r指针一直在链表尾端,方便插入新的结点)

 那么 现在我们继续写这个尾插法

  1. //插入(使用尾插法)
  2. void InsertLnode(LinkNode *&L,ch a[],int n)
  3. {
  4. LinkNode *s,*r;
  5. r=L;
  6. for(int i=0;i<n;i++)
  7. {
  8. s=new LinkNode;
  9. s->next=a[i];
  10. r->next=s;
  11. r=s;
  12. }
  13. r->next=NULL;
  14. }

2.3链表的展示

  1. void DisplayLinkNode(LinkNode *L)
  2. {
  3. LinkNode *p=L->next;
  4. while(p!=NULL)
  5. {
  6. cout<<p->data<<" ";
  7. p=p->next;
  8. }
  9. cout<<endl<<endl;
  10. }

 2.4链表的长度

  1. int LinkNodeLength(LinkNode *L)
  2. {
  3. LinkNode *p=L;
  4. int n=0;
  5. while(p->next!=NULL)//注意头结点不算我们的链表长度
  6. {
  7. n++;
  8. p=p->next;
  9. }
  10. return n;
  11. }

2.5链表中取值

  1. bool Getlink(LinkNode *L,int n,ch &e)
  2. {
  3. if(n<=0)
  4. return false;
  5. LinkNode *p=L;
  6. int j=0;
  7. while(j<n&&p!=NULL)
  8. {
  9. j++;
  10. p=p->next;
  11. }
  12. if(p==NULL)
  13. return false;
  14. else
  15. {
  16. e=p->data;
  17. return true;
  18. }
  19. }

记忆方法:创建指针,遍历一下,判断是否为空,否则为可取之值 

 2.6链表中删除

  1. bool DeleteNode(LinkNode *&L,int n,ch &e)
  2. {
  3. if(n<=0)
  4. return false;
  5. LinkNode *p=L,q;
  6. int j=0;
  7. while(j<n-1&&p!=NULL)//注意删除代码停在删除元素的前面
  8. {
  9. j++;
  10. p=p->next;
  11. }
  12. if(p==NULL)
  13. return false;
  14. q=p->next;
  15. if(q==NULL)
  16. return false
  17. e=q->data;
  18. p->next=q->next;
  19. delete q;
  20. return true;
  21. }

记忆方法 建立两个指针,遍历到删除元素的前一个,用p指向删除元素,然后进行交换

2.7新的插入

  1. bool insertnode(LinkNode *&L,int i,ch e)
  2. {
  3. if(i<=0)
  4. return false;
  5. LinkNode *p=L,*s;
  6. int j=0;
  7. while(j<n&&p!=NULL)
  8. {
  9. j++;
  10. p=p->next;
  11. }
  12. if(p==NULL||p->next==NULL)
  13. return false;
  14. s=new LinkNode;
  15. s->data=e;
  16. s->next=p->next;
  17. p->next=s;
  18. return true;
  19. }

记忆方法:创建一个新节点,类似头插法的方式插进去 

小作业 

  1. #include <iostream>
  2. using namespace std;
  3. typedef char ch;
  4. typedef struct LNode {
  5. ch data;
  6. struct LNode*next;//指针域:存放下一个节点的地址
  7. } LinkNode;
  8. //初始化
  9. void InitList(LinkNode *&L) {
  10. L = new LinkNode;
  11. L->next = NULL;
  12. }
  13. //插入(尾插法)
  14. void Insertlist(LinkNode *&L, ch a[], int n) { //传入想插入的数组(1,2,3,4),则此法插完后亦是(1,2,3,4)
  15. LinkNode *s, *r; //创建两个指针
  16. r = L; //r指向首节点L
  17. for (int i = 0; i < n; i++) {
  18. s = new LinkNode; //创建空间
  19. s->data = a[i]; //数据存储(值得注意的是s是指针)
  20. r->next = s; //r->next表示L的next指针域,其实就是赋值,将s的地址(s本身就是地址)赋给L的next域,相当于是L--s
  21. r = s; //然后将r指向s
  22. }
  23. r->next = NULL; //最后r指向末节,指针域为NULL
  24. }
  25. //输出
  26. void Displaylist(LinkNode *L) {
  27. LinkNode *p = L->next; //这里注意一下,其实首节点是没有数据的,直接指向下一个节点打印
  28. while (p != NULL) {
  29. cout << p->data << " ";
  30. p = p->next;
  31. }
  32. cout << endl << endl;
  33. }
  34. //输出长度
  35. int Listlength(LinkNode *L) {
  36. int n = 0;
  37. LinkNode *p = L;
  38. while (p->next != NULL) {
  39. n++;
  40. p = p->next;
  41. }
  42. return n;
  43. }
  44. //判断是否为空
  45. bool emptyelem(LinkNode *L) {
  46. if (L->next == NULL)
  47. return false;
  48. else
  49. return true;
  50. }
  51. //取值
  52. bool Getelem(LinkNode *L, int n, ch &e) {
  53. if (n <= 0)
  54. return false;
  55. LinkNode *p = L;
  56. int j = 0;
  57. while (j < n && p != NULL) {
  58. j++;
  59. p = p->next;
  60. }
  61. if (p == NULL)
  62. return false;
  63. e = p->data;
  64. return true;
  65. }
  66. //输出位置
  67. int Locelem(LinkNode *L, ch e) {
  68. LinkNode *p = L->next;
  69. int j = 1;
  70. while (p != NULL && p->data != e) {
  71. p = p->next;
  72. j++;
  73. }
  74. if (p == NULL) {
  75. return 0;
  76. }
  77. return j;
  78. }
  79. //指定位置插入元素
  80. bool insertlist(LinkNode *&L, int n, ch q) {
  81. if (n <= 0)
  82. return false;
  83. int j = 0;
  84. LinkNode *p = L, *s;
  85. while (j < n - 1 && p != NULL) {
  86. j++;
  87. p = p->next;
  88. }
  89. if (p==NULL||p->next == NULL)
  90. return false;
  91. else {
  92. s = new LinkNode;
  93. s->data = q;
  94. s->next = p->next;
  95. p->next = s;
  96. return true;
  97. }
  98. }
  99. //删除指定元素
  100. bool Delem(LinkNode *&L, int n, ch &e) {
  101. if (n <= 0)
  102. return false;
  103. int j = 0;
  104. LinkNode *p = L, *q;
  105. while (j < n - 1 && p != NULL) {
  106. j++;
  107. p = p->next;
  108. }
  109. if (p == NULL)
  110. return false;
  111. q = p->next;
  112. if (q == NULL)
  113. return false;
  114. e = q->data;
  115. p->next = q->next;
  116. delete q;
  117. return true;
  118. }
  119. //释放
  120. void Destroylist(LinkNode *&L) {
  121. delete L;
  122. }
  123. int main() {
  124. LinkNode *L1;
  125. InitList(L1);
  126. cout << "1.初始化单链表成功!!!" << endl << endl;
  127. //插入
  128. ch a[10] = {'a', 'b', 'c', 'd', 'e'};
  129. cout << "2.依次插入abcde." << "尾插法" << " ";
  130. Insertlist(L1, a, 5);
  131. cout << "插入成功!!!" << endl << endl;
  132. //打印
  133. cout << "3.当前的单链表为: ";
  134. Displaylist(L1);
  135. //输出长度
  136. int n = Listlength(L1);
  137. cout << "4.当前单链表的长度为:" << n << endl << endl;
  138. //判断链表是否为空
  139. cout << "5.当前链表";
  140. if (emptyelem(L1))
  141. cout << "不为空表" << endl << endl;
  142. else
  143. cout << "为空表" << endl << endl;
  144. //取值(输出元素)
  145. cout << "6.取值操作:"; int l;ch e;
  146. cout << "请输入您要取哪个位置的值:";cin >> l;
  147. if (Getelem(L1, l, e))
  148. cout << "取值成功! " << "单链表第" << l << "位的元素是:" << e << endl << endl;
  149. else
  150. cout << "取值失败,您输入的位置" << l << "越界!!!" << endl << endl;
  151. //查找
  152. cout << "7.查找操作:";ch find;
  153. cout << "请输入您要查找的元素: ";
  154. cin >> find;
  155. if (Locelem(L1, find) == 0)
  156. cout << "对不起,当前单链表中没有您查找的元素!!" ;
  157. else
  158. cout << "查找成功,您所查找的元素" << find << "在当前单链表的第" << Locelem(L1, find) << "位" ;
  159. cout<<endl<<endl;
  160. cout << "8.插入操作:";int k;ch q;
  161. cout << "请您输入一个数字和一个字符,代表在第几位插入一个字符:";cin >> k;cin >> q;
  162. if (!insertlist(L1, k, q))
  163. cout << "Warning:输入序号越界,插入失败!!!" << endl;
  164. else
  165. cout << "插入成功!!!" << endl << endl;
  166. cout << "9.当前单链表的元素有:";
  167. Displaylist(L1);
  168. cout << "10.删除操作:";int y;ch o;
  169. cout << "请您输入要删除的元素的序号:";cin >> y;
  170. if (!Delem(L1, y, o))
  171. cout << "对不起,您的输入的序号有误(越界),删除失败!" << endl << endl;
  172. else
  173. cout << "删除成功!成功删除第" << y << "个元素" << o << endl << endl;
  174. cout << "11.当前单链表的元素有:";Displaylist(L1);
  175. //释放
  176. cout << "12.销毁单链表:";Destroylist(L1);
  177. cout << "销毁成功!!!";
  178. return 0;
  179. }

 全部失败的样例:9,p,8p,7

全部成功的样例:4,c,2p,6

所以建议大家自己打吧,看完上面的写这个代码就很轻松 

感谢您今天的捧场,敬请期待下次演出。 See you next  illusion.

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/盐析白兔/article/detail/337671
推荐阅读
相关标签
  

闽ICP备14008679号