当前位置:   article > 正文

数据结构-链表基础详解(超详细代码)_链表代码

链表代码

目录

一、线性表

 1.线性表定义

2.线性表特点

二、线性表的顺序表示(顺序表)

1、顺序表的优缺点

2.插入操作

3.删除操作

4.顺序表完整代码

5.练习

三、线性表的链式表示(单链表)

1.单链表定义

2.单链表优缺点

3.插入操作

4.删除操作

 5.查找操作

5.1按序号查找结点

 5.2按值查找结点

6.链表完整代码

7.练习


一、线性表

 1.线性表定义

有n(n>=0)个相同类型的元素组成的有序集合。

L=(a1,a2,......,a(i-1),ai,a(i+1),......,an)

线性表中元素个数n,称为线性表的长度。当n=0时,为空表。
a1是唯一的“第一个"”数据元素, an是唯一的“最后一个”数据元素。
ai-1为ai的直接前驱, ai+1为ai的直接后继

2.线性表特点

2.1表中元素的个数是有限的。
2.2表中元素的数据类型都相同。意味着每一个元素占用相同大小的空间
2.3表中元素具有逻辑上的顺序性,在序列中各元素排序有其先后顺序

二、线性表的顺序表示(顺序表)

顺序表的定义 :

  1. #define MaxSize 50 //定义线性表的长度
  2. typedef struct{
  3. ElemType data[MaxSize]; //顺序表的元素
  4. int len; //顺序表的当前长度
  5. }SqList; //顺序表的类型定义

1、顺序表的优缺点

1.优点:

1.1可以随机存取(根据表头元素 地址和元素序号)表中任意一个元素。
1.2存储密度高,每个结点只存储 数据元素。
2.缺点
2.1插入和删除操作需要移动大量元素。
2.2线性表变化较大时,难以确定存储空间的容量。
2.3存储分配需要一整段连续的存储空间,不够灵活。

2.插入操作

最好情况:在表尾插入元素,不需要移动元素,时间复杂度为O(1)。

最坏情况:在表头插入元素,所有元素依次后移,时间复杂度为O(n)。
平均情况:在插入位置概率均等的情况下,平均移动元素的次数为n/2,时间

复杂度为O(n)。

代码片段:

  1. //判断插入位置i是否合法(满足1≤i≤len+1)
  2. //判断存储空间是否已满(即插入x后是否会超出数组长度)
  3. for(int j=L.len;j>=i;j--) //将最后一个元素到第i个元素依次后移一位
  4. L.data[j]=L.data[j-1];
  5. L.data[i-1]=x; //空出的位置i处放入x
  6. L.len++; //线性表长度加1

 注意:线性表第一个元素的数组下标是0;

3.删除操作

 最好情况:删除表尾元素,不需要移动元素,时间复杂度为O(1)。

最坏情况:删除表头元素,之后的所有元素依次前移,时间复杂度为O(n)。
平均情况:在删除位置概率均等的情况下,平均移动元素的次数为(n-1)/2,
时间复杂度为O(n)。
代码片段:
  1. //判断删除位置i是否合法(满足1≤i≤len)
  2. e=L.data[i-1]; //将被删除的元素赋值给e
  3. for(int j=i;j<L.len;j++) //将删除位置后的元素依次前移
  4. L.data[j-1]=L.data[j];
  5. L.len--;

4.顺序表完整代码

  1. #include <stdio.h>
  2. #define MaxSize 50
  3. typedef int ElemType;//让顺序表存储其他类型元素时,可以快速完成代码修改
  4. typedef struct{
  5. ElemType data[MaxSize];
  6. int length;//顺序表长度
  7. }SqList;
  8. //顺序表的插入,因为L会改变,因此我们这里要用引用,i是插入的位置
  9. bool ListInsert(SqList &L,int i,ElemType element)
  10. {
  11. //判断i是否合法
  12. if(i<1 || i>L.length+1)
  13. {
  14. return false;
  15. }
  16. //如果存储空间满了,不能插入
  17. if(L.length==MaxSize)
  18. {
  19. return false;//未插入返回false
  20. }
  21. //把后面的元素依次往后移动,空出位置,来放要插入的元素
  22. for(int j=L.length;j>=i;j--)
  23. {
  24. L.data[j]=L.data[j-1];
  25. }
  26. L.data[i-1]=element;//放入要插入的元素
  27. L.length++;//顺序表长度要加1
  28. return true;//插入成功返回true
  29. }
  30. //打印顺序表
  31. void PrintList(SqList L)
  32. {
  33. int i;
  34. for(i=0;i<L.length;i++)
  35. {
  36. printf("%3d",L.data[i]);//为了打印到同一行
  37. }
  38. printf("\n");
  39. }
  40. //删除顺序表中的元素,i是要删除的元素的位置,e是为了获取被删除的元素的值
  41. bool ListDelete(SqList &L,int i,ElemType &e)
  42. {
  43. //判断删除的元素的位置是否合法
  44. if(i<1 || i>L.length)
  45. {
  46. return false;//一旦走到return函数就结束了
  47. }
  48. e=L.data[i-1];//首先保存要删除元素的值
  49. int j;
  50. for(j=i;j<L.length;j++)//往前移动元素
  51. {
  52. L.data[j-1]=L.data[j];
  53. }
  54. L.length--;//顺序表长度减1
  55. return true;
  56. }
  57. //查找某个元素的位置,找到了就会对应位置,没找到就返回0
  58. int LocateElem(SqList L,ElemType element)
  59. {
  60. int i;
  61. for(i=0;i<L.length;i++)
  62. {
  63. if(element==L.data[i])
  64. {
  65. return i+1;//因为i是数组的下标,加1以后才是顺序表的下标
  66. }
  67. }
  68. return 0;//循环结束没找到
  69. }
  70. //顺序表的初始化及插入操作实战
  71. int main() {
  72. SqList L;//定义一个顺序表,变量L
  73. bool ret;//ret用来装函数的返回值
  74. L.data[0]=1;//放置元素
  75. L.data[1]=2;
  76. L.data[2]=3;
  77. L.length=3;//设置长度
  78. ret=ListInsert(L,2,60);
  79. if(ret)
  80. {
  81. printf("insert sqlist success\n");
  82. PrintList(L);
  83. }else{
  84. printf("insert sqlist failed\n");
  85. }
  86. printf("----------------------\n");
  87. ElemType del;//删除的元素存入del中
  88. ret=ListDelete(L,1,del);
  89. if(ret)
  90. {
  91. printf("delete sqlist success\n");
  92. printf("del element=%d\n",del);
  93. PrintList(L);//顺序表打印
  94. }else{
  95. printf("delete sqlist failed\n");
  96. }
  97. int pos;//存储元素位置
  98. pos=LocateElem(L,60);
  99. if(pos)
  100. {
  101. printf("find this element\n");
  102. printf("element pos=%d\n",pos);
  103. }else{
  104. printf("don't find this element\n");
  105. }
  106. return 0;
  107. }

5.练习

初始化顺序表(顺序表中元素为整型),里边的元素是1,2,3,然后通过scanf读取一个元素(假如插入的是6),插入到第2个位置,打印输出顺序表,每个元素占3个空格,格式为1  6  2  3,然后scanf读取一个整型数,是删除的位置(假如输入为1),然后输出顺序表  6  2  3,假如输入的位置不合法,输出false字符串。

Input

第一次输入插入的元素值,第二次输入删除的位置

Output

假如插入的元素为6,那么输出为
1  6  2  3

假如删除的位置为1,那么输出为


6  2  3

Sample Input 1 

6
1

Sample Output 1

  1  6  2  3
  6  2  3

Sample Input 2 

9
3

Sample Output 2

  1  9  2  3
  1  9  3

Sample Input 3 

9
6

Sample Output 3

  1  9  2  3
false

代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define MaxSize 50
  4. typedef int ElemType;
  5. typedef struct {
  6. ElemType data[MaxSize];
  7. int length;
  8. }SqList;
  9. //链表插入
  10. bool ListInsert(SqList &L,int i, ElemType ist)
  11. {
  12. if(i < 1 || i > L.length + 1)
  13. return false;
  14. if (L.length >= MaxSize)
  15. return false;
  16. for (int j = L.length; j >= i; --j) {
  17. L.data[j] = L.data[j - 1];
  18. }
  19. L.data[i - 1] = ist;
  20. L.length++;
  21. return true;
  22. }
  23. //链表删除
  24. bool ListDelete(SqList &L,int pos)
  25. {
  26. if(pos < 1 || pos > L.length)
  27. return false;
  28. if(L.length >= MaxSize)
  29. return false;
  30. for(int i = pos - 1; i <= L.length - 1; i++)
  31. {
  32. L.data[i] = L.data[i + 1];
  33. }
  34. L.length--;
  35. return true;
  36. }
  37. int main() {
  38. SqList L;
  39. L.data[0] = 1;
  40. L.data[1] = 2;
  41. L.data[2] = 3;
  42. L.length = 3;
  43. ElemType ist;
  44. scanf("%d",&ist);
  45. bool ret = ListInsert(L,2,ist);
  46. if(ret){
  47. for (int i = 0; i < L.length; i++)
  48. {
  49. printf("%3d",L.data[i]);
  50. }
  51. printf("\n");
  52. }
  53. else
  54. printf("false\n");
  55. ElemType pos;
  56. scanf("%d",&pos);
  57. ret = ListDelete(L,pos);
  58. if (ret){
  59. for (int i = 0; i < L.length; i++)
  60. {
  61. printf("%3d",L.data[i]);
  62. }
  63. printf("\n");
  64. }
  65. else
  66. printf("false\n");
  67. return 0;
  68. }

三、线性表的链式表示(单链表)

1.单链表定义

 单链表结点的定义:

  1. typedef struct LNode{ //单链表结点类型
  2. ElemType data; //数据域
  3. struct LNode *next; //指针域
  4. }LNode, *LinkList;

 头指针:链表中第一个结点的存储位置,用来标识单链表。 头结点:在单链表第一个结点之前附加的一个结点,为了操作上的方便。

        若链表有头结点,则头指针永远指向头结点,不论链表是否为空,头指针均不为 空,头指针是链表的必须元素,他标识一个链表。 头结点是为了操作的方便而设立的,其数据域一般为空,或者存放链表的长度。 有头结点后,对在第一结点前插入和删除第一结点的操作就统一了,不需要频繁 重置头指针。但头结点不是必须的。

2.单链表优缺点

1、优点:

1.1 插入和删除操作不需要移动元 素,只需要修改指针。 

1.2 不需要大量的连续存储空间。

2、缺点

2.1 单链表附加指针域,也存在浪 费存储空间的缺点。

2.2 查找操作时需要从表头开始遍历,依次查找,不能随机存取。

3.插入操作

创建新结点代码:

  1. q=(LNode*)malloc(sizeof(LNode))
  2. q->data=x;

(a) (b)操作的代码:

  1. q->next=p->next;
  2. p->next=q;

(c)操作的代码:

  1. p->next=q;
  2. q->next=NULL;

4.删除操作

(a)(b)(c)操作的代码:

  1. p=GetElem(L,i-1);//查找删除位置的前驱节点
  2. q=p->next;
  3. p->next=q->next;
  4. free(q);

 5.查找操作


5.1按序号查找结点

代码:

  1. LNode *p = L->next;
  2. int j = 1;
  3. while(p && j<i){
  4. p = p->next;
  5. j++;
  6. }
  7. retrun p;

 5.2按值查找结点

代码:

  1. LNode *p = L->next;
  2. while(p!=NULL && p->date!=e){
  3. p = p->next;
  4. }
  5. return p;

6.链表完整代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef int ElemType;
  4. typedef struct LNode{
  5. ElemType data;//数据域
  6. struct LNode *next;
  7. }LNode,*LinkList;
  8. //LNode*是结构体指针,和LinkList完全等价的
  9. //输入3,4,5,6,7,9999
  10. void list_head_insert(LNode* &L)
  11. {
  12. L= (LinkList)malloc(sizeof(LNode));//申请头结点空间,头指针指向头结点
  13. L->next=NULL;
  14. ElemType x;
  15. scanf("%d",&x);
  16. LNode *s;//用来指向申请的新结点
  17. while(x!=9999)
  18. {
  19. s=(LinkList)malloc(sizeof(LNode));
  20. s->data=x;
  21. s->next=L->next;//s的next指向原本链表的第一个结点
  22. L->next=s;//头结点的next,指向新结点
  23. scanf("%d",&x);
  24. }
  25. }
  26. //尾插法新建链表
  27. void list_tail_insert(LNode* &L)
  28. {
  29. L= (LinkList)malloc(sizeof(LNode));//申请头结点空间,头指针指向头结点
  30. L->next=NULL;
  31. ElemType x;
  32. scanf("%d",&x);
  33. LNode *s,*r=L;//s是用来指向申请的新结点,r始终指向链表尾部
  34. while(x!=9999)
  35. {
  36. s=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
  37. s->data=x;
  38. r->next=s;//新结点给尾结点的next指针
  39. r=s;//r要指向新的尾部
  40. scanf("%d",&x);
  41. }
  42. r->next=NULL;//让尾结点的next为NULL
  43. }
  44. void print_list(LinkList L)
  45. {
  46. L=L->next;
  47. while(L!=NULL)
  48. {
  49. printf("%3d",L->data);
  50. L=L->next;
  51. }
  52. printf("\n");
  53. }
  54. //按位置查找
  55. LinkList GetElem(LinkList L,int SearchPos)
  56. {
  57. int j=0;
  58. if(SearchPos<0)
  59. {
  60. return NULL;
  61. }
  62. while(L&&j<SearchPos)
  63. {
  64. L=L->next;
  65. j++;
  66. }
  67. return L;
  68. }
  69. //按值查找
  70. LinkList LocateElem(LinkList L,ElemType SearchVal)
  71. {
  72. while(L)
  73. {
  74. if(L->data==SearchVal)//如果找到对应的值,就返回那个结点的地址
  75. {
  76. return L;
  77. }
  78. L=L->next;
  79. }
  80. return NULL;
  81. }
  82. //i代表插入到第几个位置
  83. bool ListFrontInsert(LinkList L,int i,ElemType InsertVal)
  84. {
  85. LinkList p= GetElem(L,i-1);
  86. if(NULL==p)
  87. {
  88. return false;
  89. }
  90. LinkList q;
  91. q=(LinkList)malloc(sizeof(LNode));//为新结点申请空间
  92. q->data=InsertVal;
  93. q->next=p->next;
  94. p->next=q;
  95. return true;
  96. }
  97. //删除第i个位置的元素
  98. //删除时L是不会变的,所以不需要加引用
  99. bool ListDelete(LinkList L,int i)
  100. {
  101. LinkList p= GetElem(L,i-1);//拿到要删除结点的前一个结点
  102. if(NULL==p)
  103. {
  104. return false;
  105. }
  106. LinkList q=p->next;//拿到要删除的结点指针
  107. p->next=q->next;//断链
  108. free(q);//释放被删除结点的空间
  109. return true;
  110. }
  111. //头插法,尾插法来新建链表
  112. int main() {
  113. LinkList L,search;//L是链表头指针,是结构体指针类型
  114. // list_head_insert(L);//输入数据可以为3 4 5 6 7 9999,头插法新建链表
  115. list_tail_insert(L);
  116. print_list(L);//链表打印
  117. // //按位置查找
  118. // search=GetElem(L,2);
  119. // if(search!=NULL)
  120. // {
  121. // printf("Succeeded in searching by serial number\n");
  122. // printf("%d\n",search->data);
  123. // }
  124. // search=LocateElem(L,6);//按值查询
  125. // if(search!=NULL)
  126. // {
  127. // printf("Search by value succeeded\n");
  128. // printf("%d\n",search->data);
  129. // }
  130. // bool ret;
  131. // ret=ListFrontInsert(L,2,99);//新结点插入第i个位置
  132. // print_list(L);
  133. ListDelete(L,5);//删除第4个位置
  134. print_list(L);
  135. return 0;
  136. }

7.练习

输入3 4 5 6 7 9999一串整数,9999代表结束,通过头插法新建链表,并输出,通过尾插法新建链表并输出。

注意输出要采用如下代码

  1. //打印链表中每个结点的值
  2. void PrintList(LinkList L)
  3. {
  4. L=L->next;
  5. while(L!=NULL)
  6. {
  7. printf("%d",L->data);//打印当前结点数据
  8. L=L->next;//指向下一个结点
  9. if(L!=NULL)
  10. {
  11. printf(" ");
  12. }
  13. }
  14. printf("\n");
  15. }

Input

3 4 5 6 7 9999,第二行也是3 4 5 6 7 9999,数据需要输入两次

Output

如果输入是3 4 5 6 7 9999,那么输出是7 6 5 4 3,数之间空格隔开,尾插法的输出是3 4 5 6 7

Sample Input 1 

3 4 5 6 7 9999
3 4 5 6 7 9999

Sample Output 1

7 6 5 4 3
3 4 5 6 7

Sample Input 2 

1 3 5 7 9 9999
1 3 5 7 9 9999

Sample Output 2

9 7 5 3 1
1 3 5 7 9

答案:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. typedef int ElemType;
  4. typedef struct LNode{
  5. ElemType data;
  6. struct LNode *next;
  7. }LNode,*LinkList;
  8. //头插法
  9. void List_head_insert(LNode* &L)
  10. {
  11. L = (LinkList)malloc(sizeof(LNode));
  12. L->next = NULL;
  13. ElemType x;
  14. scanf("%d",&x);
  15. LinkList q;
  16. while (x != 9999)
  17. {
  18. q = (LinkList)malloc(sizeof(LNode));
  19. q->data = x;
  20. q->next = L->next;
  21. L->next = q;
  22. scanf("%d",&x);
  23. }
  24. }
  25. //尾插法
  26. void List_tail_insert(LinkList &L)
  27. {
  28. L = (LNode*)malloc(sizeof(LNode));
  29. //L->next = NULL;
  30. ElemType x;
  31. scanf("%d",&x);
  32. LinkList p = L,q;
  33. while (x != 9999)
  34. {
  35. q = (LinkList)malloc(sizeof(LNode));
  36. q->data = x;
  37. p->next = q;
  38. p = q;
  39. scanf("%d",&x);
  40. }
  41. q->next = NULL;
  42. }
  43. //链表打印
  44. void print_List(LNode* L)
  45. {
  46. L=L->next;
  47. while(L!=NULL)
  48. {
  49. printf("%d",L->data);//打印当前结点数据
  50. L=L->next;//指向下一个结点
  51. if(L!=NULL)
  52. {
  53. printf(" ");
  54. }
  55. }
  56. printf("\n");
  57. }
  58. //按值查询
  59. LinkList GetElem(LNode* L,int i)
  60. {
  61. if(i < 0)
  62. return NULL;
  63. while(i-- && L)
  64. {
  65. L = L->next;
  66. }
  67. return L;
  68. }
  69. //按位置查询
  70. LinkList LocateElem(LinkList L,int key)
  71. {
  72. L = L->next;
  73. while(L)
  74. {
  75. if(L->data == key)
  76. return L;
  77. L = L->next;
  78. }
  79. return NULL;
  80. }
  81. //中间插入
  82. bool ListFrontInsert(LinkList L,int pos,ElemType key) //中间插入不会改变头指针
  83. {
  84. LinkList p,q;
  85. p = GetElem(L,pos - 1);
  86. if(p)
  87. {
  88. q = (LinkList)malloc(sizeof(LNode));
  89. q->data = key;
  90. q->next = p->next;
  91. p->next = q;
  92. return true;
  93. }
  94. return false;
  95. }
  96. int main() {
  97. LinkList L1,L2,search; //链表头指针
  98. ElemType key;
  99. List_head_insert(L1);
  100. List_tail_insert(L2);
  101. print_List(L1);
  102. print_List(L2);
  103. return 0;
  104. }

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

闽ICP备14008679号