devbox
寸_铁
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

单、双向链表(c++)插入和删除的秘密_双向链表和单向链表的插入和删除

作者：寸_铁 | 2024-07-03 04:48:44

赞

踩

双向链表和单向链表的插入和删除

一、文章概述

        本人在学习线性表时，发现单链表与双向链表的插入、删除操作的算法实现有较大差别，并且自己用的课本并未详细给出双向链表的插入和删除的算法实现，于是自己就动手实现了这两个操作，下面我将分享自己在学习中总结的单链表与双链表插入删除算法的区别，并给出算法实现。但由于本人学识浅陋、见闻不广，文中难免会出现错误或不足之处，恳请读者批评指正。

二、区别

（一）操作时获取的指针不同

为了方便下面的讲解，先把两种链表的结构划出，如下图：

头结点：链表中的第一个节点

首元结点：链表中的第一个元素节点

（1）单链表获取的指针

        单链表无论是插入还是删除，我们都需要找到待插入位置或删除位置的前一个位置，比如我们如果要将一个元素插入到第i个元素位置，那么我们就要找到第i-1个元素的指针即可，要删除第i个结点，我们也需要找到第i-1个结点的指针。

举例：

        （1）如下图，我们要将数据域为10的S结点插入到第2个元素位置，那么我们要找第1个元素的指针P，然后执行图中的两步操作

        

（2）如下图，我们要删除第2个元素，我们也要先找到第1个元素的指针p，然后再进行下面的操作。

（2）双向链表获取的指针

        与单链表不同的是，我们如果要将元素插入到第i个位置，或删除第i个位置，我们都需要找到第i个元素的指针，而不是第i-1个元素的指针。

举例：

        （1）如下图，我们要将数据域为10的S结点插入到第2个元素位置，那么我们要找到第2个元素的指针P，然后执行图中的四步操作

        ​​​​​​​

        （2）如下图，我们要删除第2个元素，我们也要先找到第2个元素的指针p，然后再进行下面的操作。

（二）考虑的情况不同

（1）单链表所考虑的情况

        由下面的代码可知，单链表的插入和删除较为简单，我们没有特殊的需要情况考虑，而下面要讲的双向链表有特殊情况需要考虑。

  1. //双向链表的存储结构
  2. typedef struct LNode {
  3. 	int data;
  4. 	struct LNode* next;
  5. }LNode, *LinkList;
  6.  
  7. //在链表第i个位置插入结点
  8. void listInsert(LinkList L, int i, int data) {
  9. 	LinkList p = L;
  10. 	int j = 0; 
  11. 	//找到待插入位置的前一结点的指针
  12. 	while (p && j < i - 1) {
  13. 		p = p->next;
  14. 		j++;
  15. 	}
  16. 	if (!p || j > i - 1) {
  17. 		printf("i为不合法的插入位置");
  18. 		return;
  19. 	}
  20. 	//创建待插入节点s
  21. 	LNode* s = new LNode;
  22. 	s->data = data;
  23. 	s->next = NULL;
  24. 	//将结点插入
  25. 	s->next = p->next;
  26. 	p->next = s;
  27. }
  28.  
  29.  
  30. //删除链表L第i个位置的元素
  31. void listDelete(LinkList L, int i) {
  32. 	int j = 0;
  33. 	LNode* p = L;
  34.     //找到待删除结点的前一结点的指针
  35. 	while (p->next && j < i - 1) {
  36. 		p = p->next;
  37. 		j++;
  38. 	}
  39. 	if (!(p->next) || j > i - 1) {
  40. 		printf("i为不合法的删除位置");
  41. 		return;
  42. 	}
  43. 	LNode* s = p->next;
  44. 	p->next = p->next->next;
  45. 	delete s;
  46. }

 （2）双向链表所考虑的情况

插入时：

        （1）插入位置=0，的情况需要单独考虑，提示"i为不合法的插入位置"，仍然按照单链表中的逻辑：if(!p&&j>i){}，不可以检测出插入位置=0的不合法情况。

        （2）我们需要单独考虑 插入位置 = 元素个数+1的情况，否则的话根据下面的代码，可知会直接显示“i为不合法的插入位置”。

删除时：

        （1）同插入时的情况（1），删除时也需要单独考虑插入位置=0的情况，否则会出现同样的情况。

        （2）我们需要考虑删除尾结点的情况，如果不单独考虑的话，会出现“null->next-prior”的情况，就会报错。

  1. //双向链表的存储结构
  2. typedef struct DuLNode {
  3. 	int data;
  4. 	struct DuLNode* prior;
  5. 	struct DuLNode* next;
  6. }DuLNode, *DuLinkList;
  7.  
  8.  
  9. //在第i个元素位置插入结点，结点数据域为data
  10. void listInsert_Du(DuLinkList L, int i, int data) {
  11. 	DuLinkList p = L;
  12. 	if (i == getLength( L) + 1) {//插入的位置为链表的尾部（尾结点后）
  13. 		for (int i = 0; i < getLength(L); i++) {//获取链表尾结点的指针
  14. 			p = p->next;
  15. 		}
  16. 		DuLNode* s = new DuLNode;
  17. 		s->data = data;
  18. 		p->next = s;
  19. 		s->prior = p;
  20. 		s->next = NULL;
  21. 	}
  22. 	else {
  23. 		int j = 0;
  24. 		while (p && j < i) {//将指针p指向待插入位置的节点
  25. 			p = p->next;
  26. 			j++;
  27. 		}
  28. 		if (!p || j > i ||  i== 0) {
  29. 			cout << "i为不合法的插入位置"<<endl;
  30. 			return;
  31. 		}
  32. 		DuLNode* s = new DuLNode;
  33. 		s->data = data;
  34. 		p->prior->next = s;
  35. 		s->prior = p->prior;
  36. 		p->prior = s;
  37. 		s->next = p;
  38. 	}
  39. }
  40.  
  41. //删除链表中第i个元素
  42. void listDelete(DuLinkList L, int i) {
  43. 	DuLNode* p = L;
  44. 	int j = 0;
  45. 	while (p && j < i) {//获取待删除结点的指针
  46. 		p = p->next;
  47. 		j++;
  48. 	}
  49.  if (!p || j > i || i == 0) {
  50. 		cout << "i为不合法的位置"<<endl;
  51. 		return;
  52. 	}
  53.  if (j == getLength(L)) {//待删除的结点为尾结点
  54. 	 p->prior->next = NULL;
  55. 	 delete p;
  56. 	 return;
  57.  }
  58. 	p->prior->next = p->next;
  59. 	p->next->prior = p->prior;
  60. 	delete p;
  61. }

三、全部代码

下面是我在实验时写的整体代码，读者可以在本地查看执行效果：

双向链表：

  1. #include<iostream>
  2. using namespace std;
  3. //双向链表的存储结构
  4. typedef struct DuLNode {
  5. 	int data;
  6. 	struct DuLNode* prior;
  7. 	struct DuLNode* next;
  8. }DuLNode, *DuLinkList;
  9. void createList_Du(DuLinkList& L, int n);
  10. void printList(DuLinkList L);
  11. void listInsert_Du(DuLinkList L, int i, int data);
  12. void listDelete(DuLinkList L, int i);
  13. int getLength(DuLinkList L);
  14. int main() {
  15. 	DuLinkList L = NULL;
  16. 	int length = 0;
  17. 	cout << "请输入链表长度：";
  18. 	cin >> length;
  19. 	createList_Du(L, length);//创建一个长度为length的双向链表
  20. 	printList(L);//打印链表
  21. 	int i, data;
  22. 	cout << "请输入待插入位置、及数据:"<<endl;
  23. 	cin >> i>>data;
  24. 	listInsert_Du(L, i, data);//在链表第i个位置插入结点，结点数据为data
  25. 	printList(L);
  26. 	cout << "请输入待删除结点的位置:"<<endl;
  27. 	cin >> i;
  28. 	listDelete(L, i);//删除链表中第i个结点
  29. 	printList(L);
  30.  
  31. 	return 0;
  32. }
  33.  
  34. //创建含有n个元素的双向连表
  35. void createList_Du(DuLinkList &L, int n) {
  36. 	L = new DuLNode;//创建头结点
  37. 	L->next = NULL;
  38. 	L->prior = NULL;
  39. 	DuLNode* r = L;//指针r指向链表的尾结点
  40. 	cout << "请输入链表元素:";
  41. 	//尾插法创建长度为n的链表
  42. 	for (int i = 0; i < n; i++) {
  43. 		int data;
  44. 		cin >> data;
  45. 		DuLNode* p = new DuLNode;
  46. 		p->data = data;
  47. 		r->next = p;
  48. 		p->prior = r;
  49. 		p->next = NULL;
  50. 		r = p;
  51. 	}
  52. }
  53.  
  54. //在第i个元素位置插入结点，结点数据域为data
  55. void listInsert_Du(DuLinkList L, int i, int data) {
  56. 	DuLinkList p = L;
  57. 	if (i == getLength( L) + 1) {//插入的位置为链表的尾部（尾结点后）
  58. 		for (int i = 0; i < getLength(L); i++) {//获取链表尾结点的指针
  59. 			p = p->next;
  60. 		}
  61. 		DuLNode* s = new DuLNode;
  62. 		s->data = data;
  63. 		p->next = s;
  64. 		s->prior = p;
  65. 		s->next = NULL;
  66. 	}
  67. 	else {
  68. 		int j = 0;
  69. 		while (p && j < i) {//将指针p指向待插入位置的节点
  70. 			p = p->next;
  71. 			j++;
  72. 		}
  73. 		if (!p || j > i ||  i== 0) {
  74. 			cout << "i为不合法的插入位置"<<endl;
  75. 			return;
  76. 		}
  77. 		DuLNode* s = new DuLNode;
  78. 		s->data = data;
  79. 		p->prior->next = s;
  80. 		s->prior = p->prior;
  81. 		p->prior = s;
  82. 		s->next = p;
  83. 	}
  84. }
  85.  
  86. //删除链表中第i个元素
  87. void listDelete(DuLinkList L, int i) {
  88. 	DuLNode* p = L;
  89. 	int j = 0;
  90. 	while (p && j < i) {//获取待删除结点的指针
  91. 		p = p->next;
  92. 		j++;
  93. 	}
  94.  if (!p || j > i || i == 0) {
  95. 		cout << "i为不合法的位置"<<endl;
  96. 		return;
  97. 	}
  98.  if (j == getLength(L)) {//待删除的结点为尾结点
  99. 	 p->prior->next = NULL;
  100. 	 delete p;
  101. 	 return;
  102.  }
  103. 	p->prior->next = p->next;
  104. 	p->next->prior = p->prior;
  105. 	delete p;
  106. }
  107. //打印链表
  108. void printList(DuLinkList L) {
  109. 	DuLNode* p = L->next;
  110. 	cout << "形成的链表：";
  111. 	while (p) {
  112. 		cout << p->data << " ";
  113. 		p = p->next;
  114. 	}
  115. 	cout << endl;
  116. }
  117.  
  118. //得到链表长度
  119. int getLength(DuLinkList L) {
  120. 	DuLNode* p = L->next;
  121. 	int length = 0;
  122. 	while (p) {
  123. 		p = p->next;
  124. 		length++;
  125. 	}
  126. 	return length;
  127. }

单链表：

  1. #include <iostream>
  2. using namespace std;
  3. //单链表的存储结构
  4. typedef struct LNode {
  5. 	int data;
  6. 	struct LNode* next;
  7. }LNode, *LinkList;
  8. void createList(LinkList &L, int n);
  9. void listInsert(LinkList L, int i, int data);
  10. void printList(LinkList L);
  11. void listDelete(LinkList L, int i);
  12. int main() {
  13. 	LinkList L = NULL;
  14. 	int length = 0;
  15. 	cout << "请输入链表长度：";
  16. 	cin >> length;
  17. 	createList(L, length);//创建一个长度为length的双向链表
  18. 	printList(L);//打印链表
  19. 	int i, data;
  20. 	cout << "请输入待插入位置、及数据:" << endl;
  21. 	cin >> i >> data;
  22. 	listInsert(L, i, data);//在链表第i个位置插入节点，结点数据为data
  23. 	printList(L);
  24. 	cout << "请输入待删除结点的位置:" << endl;
  25. 	cin >> i;
  26. 	listDelete(L, i);//删除链表中第i个结点
  27. 	printList(L);
  28.  
  29. 	return 0;
  30. }
  31.  
  32. //尾插法创建一个长度为n的链表
  33. void createList(LinkList &L, int n) {
  34. 	L = new LNode;
  35. 	L->next = NULL;//创建头结点
  36. 	LNode* r = L;//指针r指向尾结点
  37. 	cout << "请输入链表元素:";
  38. 	for (int i = 0; i < n; i++) {
  39. 		int data;
  40. 		cin >> data;
  41. 		LNode* p = new LNode;
  42. 		p->data = data;
  43. 		r->next = p;
  44. 		p->next = NULL;
  45. 		r = p;
  46. 	}
  47. }
  48.  
  49. //在带头结点的链表第i个位置插入结点
  50. void listInsert(LinkList L, int i, int data) {
  51. 	LinkList p = L;
  52. 	int j = 0; 
  53. 	//找到待插入位置的前一结点的指针
  54. 	while (p && j < i - 1) {
  55. 		p = p->next;
  56. 		j++;
  57. 	}
  58. 	if (!p || j > i - 1) {
  59. 		printf("i为不合法的插入位置");
  60. 		return;
  61. 	}
  62. 	//创建待插入节点s
  63. 	LNode* s = new LNode;
  64. 	s->data = data;
  65. 	s->next = NULL;
  66. 	//将s结点插入
  67. 	s->next = p->next;
  68. 	p->next = s;
  69. }
  70.  
  71. //删除链表L第i个位置的元素
  72. void listDelete(LinkList L, int i) {
  73. 	int j = 0;
  74. 	LNode* p = L;
  75. 	//找到待删除位置的前一结点的指针
  76. 	while (p->next && j < i - 1) {
  77. 		p = p->next;
  78. 		j++;
  79. 	}
  80. 	if (!(p->next) || j > i - 1) {
  81. 		printf("i为不合法的删除位置");
  82. 		return;
  83. 	}
  84. 	LNode* s = p->next;
  85. 	p->next = p->next->next;
  86. 	delete s;
  87. }
  88.  
  89. //打印链表
  90. void printList(LinkList L) {
  91. 	LNode* p = L->next;
  92. 	cout << "形成的链表：";
  93. 	while (p) {
  94. 		cout << p->data << " ";
  95. 		p = p->next;
  96. 	}
  97. 	cout << endl;
  98. }

声明：本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号