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

数据结构（初阶）——顺序表、链表_sldatetype x

作者：小舞很执着 | 2024-08-04 05:42:44

赞

踩

sldatetype x

一、顺序表

SeqList.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<stdlib.h>
  5. #include<errno.h>
  6. #include<assert.h>
  7. typedef int SLDataType;
  8. // 顺序表的动态存储
  9. typedef struct SeqList
  10. {
  11. 	SLDataType* array; // 指向动态开辟的数组
  12. 	size_t size; // 有效数据个数
  13. 	size_t capicity; // 容量空间的大小
  14. }SeqList;
  15. SeqList SL;
  16. // 基本增删查改接口
  17. // 顺序表初始化
  18. void SeqListInit(SeqList* psl);
  19.  
  20. // 检查空间，如果满了，进行增容
  21. void CheckCapacity(SeqList* psl);
  22.  
  23. // 顺序表尾插
  24. void SeqListPushBack(SeqList* psl, SLDataType x);
  25.  
  26. // 顺序表尾删
  27. void SeqListPopBack(SeqList* psl);
  28.  
  29. // 顺序表头插
  30. void SeqListPushFront(SeqList* psl, SLDataType x);
  31.  
  32. // 顺序表头删
  33. void SeqListPopFront(SeqList* psl);
  34.  
  35. // 顺序表查找
  36. int SeqListFind(SeqList* psl, SLDataType x);
  37.  
  38. // 顺序表在pos位置插入x
  39. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
  40.  
  41. // 顺序表删除pos位置的值
  42. void SeqListErase(SeqList* psl, size_t pos);
  43.  
  44. // 顺序表销毁
  45. void SeqListDestory(SeqList* psl);
  46.  
  47. // 顺序表打印
  48. void SeqListPrint(SeqList* psl);
  49.  
  50. //顺序表修改
  51. void SLModify(SeqList* psl, size_t pos, SLDataType x);

SeqList.c

  1. #define _CRT_SECURE_NO_WARNINGS 
  2.  
  3. #include "SeqList.h"
  4.  
  5. // 顺序表初始化
  6. void SeqListInit(SeqList* psl) {
  7. 	assert(psl);
  8.  
  9. 	psl->capicity = 0;
  10. 	psl->size = 0;
  11. 	psl->array = NULL;
  12. 	
  13.  
  14. }
  15.  
  16.  //顺序表打印
  17. void SeqListPrint(SeqList* psl) {
  18. 	assert(psl);
  19. 	for (int i = 0; i < psl->size; i++) {
  20. 		printf("%d ", psl->array[i]);
  21. 	}
  22.  
  23. }
  24.  
  25. // 顺序表头插
  26. void SeqListPushFront(SeqList* psl, SLDataType x) {
  27. 	assert(psl);
  28.  
  29. 	//检查空间是否足够
  30. 	 CheckCapacity(&psl);
  31. 	 int temp_size = psl->size;
  32. 	 while (temp_size > 0) {
  33.  
  34. 		 psl->array[temp_size] = psl->array[temp_size-1];
  35. 		 temp_size--;
  36.  
  37. 	 }
  38. 	 psl->array[0] = x;
  39. 	 psl->size++;
  40.  
  41. }
  42.  
  43. // 顺序表尾插
  44. void SeqListPushBack(SeqList* psl, SLDataType x) {
  45. 	assert(psl);
  46.  
  47. 	//检查空间是否足够
  48. 	CheckCapacity(&psl);
  49.  
  50. 	psl->array[psl->size] = x;
  51. 	psl->size++;
  52.  
  53. }
  54.  
  55. // 顺序表销毁
  56. void SeqListDestory(SeqList* psl) {
  57.  
  58. 	assert(psl);
  59. 	free(psl->array);
  60. 	psl->array = NULL;
  61. 	psl->capicity = 0;
  62. 	psl->size = 0;
  63.  
  64. }
  65. // 检查空间，如果满了，进行增容
  66. void CheckCapacity(SeqList** psl) {
  67.  
  68. 	if ((*psl)->capicity == 0) {
  69. 		SLDataType* temp = NULL;
  70. 		(*psl)->capicity = 4 * sizeof(SLDataType);
  71. 		temp = (SLDataType)malloc((*psl)->capicity);
  72. 		if (temp == NULL) {
  73. 			perror(CheckCapacity);
  74. 			return 0;
  75. 		}
  76. 		(*psl)->array = temp;
  77.  
  78. 		return;
  79. 	}
  80.  
  81. 	if ((*psl)->capicity <= (*psl)->size*sizeof(SLDataType)) {
  82. 		(*psl)->capicity *= 2;
  83. 		SLDataType* temp = NULL;
  84. 		//检查开辟是否成功
  85. 		temp = (SLDataType)realloc((*psl)->array,(*psl)->capicity);
  86.  
  87. 		if (temp == NULL) {
  88. 			perror(CheckCapacity);
  89. 			return 0;
  90. 		}
  91. 		(*psl)->array = temp;
  92. 	}
  93.  
  94. }
  95.  
  96. // 顺序表尾删
  97. void SeqListPopBack(SeqList* psl) {
  98.  
  99. 	assert(psl);
  100.  
  101. 	psl->size--;
  102. }
  103.  
  104. // 顺序表头删
  105. void SeqListPopFront(SeqList* psl) {
  106. 	assert(psl);
  107.  
  108. 	int temp_size = 1;
  109. 	while (temp_size <= psl->size) {
  110.  
  111. 		psl->array[temp_size-1] = psl->array[temp_size];
  112. 		temp_size++;
  113.  
  114. 	}
  115. 	psl->size--;
  116.  
  117. }
  118. // 顺序表查找
  119. int SeqListFind(SeqList* psl, SLDataType x) {
  120. 	assert(psl);
  121. 	//找到返回下标
  122. 	for (int i = 0; i < psl->size; i++) {
  123. 		if (psl->array[i] == x) {
  124.  
  125. 			return i;
  126. 		}
  127. 	}
  128. 	//没找到返回-1；
  129. 	return -1;
  130. }
  131.  
  132.  
  133. // 顺序表删除pos位置的值
  134. void SeqListErase(SeqList* psl, size_t pos) {
  135.  
  136. 	assert(psl);
  137. 	assert(pos < psl->size);
  138. 	if (pos >= psl->size) {
  139. 		printf("删除超出范围限制");
  140. 		return ;
  141. 	}
  142.  
  143. 	while (pos < psl->size) {
  144. 		psl->array[pos] = psl->array[pos + 1];
  145. 		pos++;
  146. 	}
  147. 	psl->size--;
  148. }
  149.  
  150. // 顺序表在pos位置插入x
  151. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x) {
  152.  
  153. 	assert(psl);
  154. 	assert(pos <= psl->size);
  155.  
  156. 	CheckCapacity(&psl);
  157.  
  158. 	int temp = psl->size;
  159. 	while (temp > pos) {
  160. 		psl->array[temp] = psl->array[temp - 1];
  161. 		temp--;
  162. 	}
  163. 	psl->array[pos] = x;
  164. 	psl->size++;
  165. }
  166.  
  167. //修改
  168. void SLModify(SeqList* psl, size_t pos, SLDataType x) {
  169.  
  170. 	assert(psl);
  171. 	assert(pos < psl->size);
  172. 	
  173. 	psl->array[pos] = x;
  174.  
  175. }

二.单链表

单链表.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<stdlib.h>
  5.  
  6. typedef int SLTDateType;
  7. typedef struct SListNode
  8. {
  9. 	SLTDateType data;
  10. 	struct SListNode* next;
  11. }SListNode;
  12. // 动态申请一个结点
  13. SListNode* BuySListNode(SLTDateType x);
  14. // 单链表打印
  15. void SListPrint(SListNode* plist);
  16. // 单链表尾插
  17. void SListPushBack(SListNode** pplist, SLTDateType x);
  18. // 单链表的头插
  19. void SListPushFront(SListNode** pplist, SLTDateType x);
  20. // 单链表的尾删
  21. void SListPopBack(SListNode** pplist);
  22. // 单链表头删
  23. void SListPopFront(SListNode** pplist);
  24. // 单链表查找
  25. SListNode* SListFind(SListNode* plist, SLTDateType x);
  26. // 单链表在pos位置之后插入x
  27. // 分析思考为什么不在pos位置之前插入？
  28. void SListInsertAfter(SListNode* pos, SLTDateType x);
  29. // 单链表 之前插入（难）
  30. void SListInsertBefore(SListNode* pos, SLTDateType x);
  31. // 单链表删除pos位置之后的值
  32. // 分析思考为什么不删除pos位置？
  33. void SListEraseAfter(SListNode* pos);
  34. // 单链表销毁
  35. void SLlistDestory(SListNode* phead);
  36. //单链表删除当前位置
  37. void SListErase(SListNode* pos);

单链表.c

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include"单链表.h"
  3.  
  4. SListNode* BuySListNode(SLTDateType x) {
  5.  
  6. 	SListNode* temp = (SListNode*)malloc(sizeof(SListNode));
  7.  
  8. 	if (temp == NULL) {
  9. 		perror("malloc fail");
  10. 		exit(-1);
  11. 	}
  12. 	SListNode* newnode = temp;
  13. 	temp = NULL;
  14.  
  15. 	newnode->data = x;
  16. 	newnode->next = NULL;
  17.  
  18. 	return newnode;
  19. }
  20.  
  21. // 单链表打印
  22. void SListPrint(SListNode* phead) {
  23.  
  24. 	SListNode* cur = phead;
  25.  
  26. 	while (cur) {
  27. 		printf("%d->", cur->data);
  28. 		cur = cur->next;
  29. 	}
  30. 	printf("NULL\n");
  31.  
  32. }
  33.  
  34. // 单链表的头插
  35. void SListPushFront(SListNode** pphead, SLTDateType x) {   //改变一级指针就需要一级指针的地址，所以传入二级指针
  36. 	assert(pphead);
  37. 	SListNode* newnode = BuySListNode(x);
  38.  
  39. 	newnode->next = *pphead;
  40. 	*pphead = newnode;
  41.  
  42. }
  43.  
  44. // 单链表尾插
  45. void SListPushBack(SListNode** pphead, SLTDateType x) {
  46. 	assert(pphead);
  47. 	//单链表不为空
  48. 	if (* pphead == NULL ) {
  49. 		SListNode* next = BuySListNode(x);
  50. 		*pphead = next;
  51. 		
  52.  
  53. 	}//单链表为空
  54. 	else {
  55. 		SListNode* cur = *pphead;
  56. 		while (cur->next != NULL) {
  57. 			cur = cur->next;
  58. 		}
  59.  
  60. 		SListNode* next = BuySListNode(x);
  61. 		cur->next = next;
  62. 	}
  63.  
  64. }
  65. // 单链表头删
  66. void SListPopFront(SListNode** pphead) {
  67. 	
  68. 	assert(pphead);
  69. 	if (*pphead == NULL) {
  70. 		return;
  71. 	}
  72. 	SListNode* del = *pphead;
  73. 	*pphead = (*pphead)->next;
  74. 	free(del);
  75. 	del = NULL;
  76.  
  77. }
  78.  
  79. // 单链表的尾删
  80. void SListPopBack(SListNode** pphead) {
  81.  
  82. 	assert(pphead);
  83. 	if (*pphead == NULL) {
  84. 		return;
  85. 	}
  86. 	if ((*pphead)->next == NULL) {
  87. 		free(*pphead);
  88. 		*pphead = NULL;
  89. 		return;
  90. 	}
  91. 	SListNode* cur = *pphead;
  92.  
  93. 	while (cur->next->next != NULL) {
  94. 		cur = cur->next;
  95. 	}
  96. 	free(cur->next);
  97. 	cur->next = NULL;
  98.  
  99.  
  100. }
  101. // 单链表查找
  102. SListNode* SListFind(SListNode* pphead, SLTDateType x) {
  103.  
  104. 	assert(pphead);
  105. 	SListNode* cur = pphead;
  106.  
  107. 	while (cur) {
  108. 		if (x == cur->data) {
  109. 			printf("找到了\n");
  110. 			return cur;
  111. 		}
  112. 		else {
  113. 			cur = cur->next;
  114. 		}
  115.  
  116. 	}
  117. 	return NULL;
  118.  
  119. }
  120.  
  121.  
  122. //单链表在某位置之后插入
  123. void SListInsertAfter(SListNode** pphead,SListNode* pos, SLTDateType x) {
  124.  
  125. 	assert(pphead);
  126.  
  127. 	if (*pphead == NULL) {
  128. 		SListPushFront(pphead, x);
  129. 		return;
  130. 	}
  131. 	
  132. 	SListNode* newcode =  BuySListNode(x);
  133. 	newcode->next = pos->next;//注意这两行的顺序
  134. 	pos->next = newcode;
  135.  
  136. }
  137. // 单链表 之前插入（难）
  138. void SListInsertBefore(SListNode** pphead, SListNode* pos, SLTDateType x) {
  139.  
  140. 	assert(pos);
  141. 	assert(pphead);
  142.  
  143. 	if (*pphead == NULL) {
  144. 		SListPushFront(pphead, x);
  145. 		return;
  146. 	}
  147.  
  148. 	//方法一：找到前一项的next
  149. 	SListNode* cur = *pphead;
  150. 	if (pos == pphead) {
  151. 		SListPushFront(pphead, x);
  152. 		return;
  153. 	}
  154. 	while (cur->next != pos) {
  155.  
  156. 		cur = cur->next;
  157.  
  158. 		//找不到，说明pos传错了
  159. 		assert(cur);
  160. 	}
  161. 	SListNode* newcode = BuySListNode(x);
  162. 	newcode->next = pos;
  163. 	cur->next = newcode;
  164. 	//方法二 顺序法交换
  165.  
  166. 	//SListNode* newcode = BuySListNode(pos->data);
  167. 	//pos->data = x;
  168.  
  169.  
  170. }
  171. // 单链表删除pos位置之后的值
  172. // 分析思考为什么不删除pos位置？
  173. void SListEraseAfter(SListNode** pphead, SListNode* pos) {
  174.  
  175. 	assert(pphead);
  176. 	assert(pos);
  177. 	
  178. 	if (pos->next == NULL) {
  179. 		SListPopBack(pphead);
  180. 		return;
  181. 	}
  182. 	SListNode* cur = pos->next;
  183. 	pos->next = pos->next->next;
  184.  
  185. 	free(cur);
  186. }
  187.  
  188.  
  189. //单链表删除当前位置
  190. void SListErase(SListNode** pphead, SListNode* pos) {
  191. 	assert(pphead && pos);
  192.  
  193. 	if (pos == *pphead) {
  194. 		SListPopFront(pphead);
  195. 		return;
  196. 	}
  197.  
  198. 	SListNode* cur = pos->next->next;
  199. 	pos->data = pos->next->data;
  200. 	free(pos->next);
  201. 	pos->next = cur;
  202.  
  203. }
  204.  
  205.  
  206. // 单链表销毁
  207. void SLlistDestory(SListNode** pphead) {
  208.  
  209. 	assert(pphead);
  210. 	SListNode* cur = pphead;
  211. 	SListNode* next = pphead;
  212. 	while (cur) {
  213. 		next = cur->next;
  214. 		free(cur);
  215. 		cur = next;
  216. 	}
  217.  
  218. 	pphead = NULL;
  219.  
  220. }
  221.

三.带头双向循环链表

List.h

  1. #pragma once
  2. #include<stdio.h>
  3. #include<assert.h>
  4. #include<stdlib.h>
  5.  
  6. typedef int LTDataType;
  7. typedef struct ListNode
  8. {
  9. 	LTDataType _data;
  10. 	struct ListNode* next;
  11. 	struct ListNode* prev;
  12. }ListNode;
  13. // 创建返回链表的头结点.
  14. ListNode* ListCreate();
  15. //双向链表创造一个新节点
  16. ListNode* ListBuyNode(LTDataType x);
  17. // 双向链表打印
  18. void ListPrint(ListNode* plist);
  19. // 双向链表尾插
  20. void ListPushBack(ListNode* plist, LTDataType x);
  21. // 双向链表头插
  22. void ListPushFront(ListNode* plist, LTDataType x);
  23. // 双向链表尾删
  24. void ListPopBack(ListNode* plist);
  25. // 双向链表头删
  26. void ListPopFront(ListNode * plist);
  27. // 双向链表查找
  28. ListNode* ListFind(ListNode* plist, LTDataType x);
  29. // 双向链表在pos的前面进行插入
  30. void ListInsert(ListNode* pos, LTDataType x);
  31. // 双向链表删除pos位置的结点
  32. void ListErase(ListNode* pos);
  33. // 双向链表销毁
  34. void ListDestory(ListNode* plist);
  35.  
  36.  
  37.

List.c

  1. #define _CRT_SECURE_NO_WARNINGS 
  2. #include"List.h"
  3.  
  4. // 创建返回链表的头结点.
  5. ListNode* ListCreate() {
  6. 	ListNode* ListGuard = (ListNode*)malloc(sizeof(ListNode));
  7. 	if (ListGuard == NULL) {
  8. 		perror("ListGuard malloc fai");
  9. 		exit(-1);
  10. 	}
  11. 	ListGuard->next = ListGuard;
  12. 	ListGuard->prev = ListGuard;
  13. 	return ListGuard;
  14. }
  15.  
  16. // 双向链表打印
  17. void ListPrint(ListNode* plist) {
  18. 	assert(plist);
  19. 	ListNode* head = plist;
  20. 	ListNode* cur = head->next;
  21.  
  22. 	printf("head<=>");
  23. 	while (cur != head) {
  24. 		printf("%d<=>", cur->_data);
  25. 		cur = cur->next;
  26. 	}
  27. 	printf("\n");
  28. }
  29. //双向链表创造一个新节点
  30. ListNode* ListBuyNode(LTDataType x) {
  31. 	ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
  32. 	if (newNode == NULL) {
  33. 		perror("newNode malloc fail");
  34. 		exit(-1);
  35. 	}
  36. 	newNode->next = NULL;
  37. 	newNode->prev = NULL;
  38. 	newNode->_data = x;
  39. 	return newNode;
  40. }
  41. // 双向链表尾插
  42. void ListPushBack(ListNode* plist, LTDataType x) {
  43. 	assert(plist);
  44. 	ListNode* tail = plist->prev;
  45.  
  46. 	ListNode* newNode = ListBuyNode(x);
  47. 	//节点四步走 注意语句顺序！
  48. 	newNode->next = plist;
  49. 	plist->prev = newNode;
  50. 	tail->next = newNode;
  51. 	newNode->prev = tail;
  52.  
  53. }
  54. // 双向链表头插
  55. void ListPushFront(ListNode* plist, LTDataType x) {
  56. 	assert(plist);
  57. 	ListNode* first = plist->next;
  58.  
  59. 	ListNode* newNode = ListBuyNode(x);
  60. 	//节点四步走 注意语句顺序！
  61. 	first->prev = newNode;
  62. 	newNode->next = first;
  63. 	plist->next = newNode;
  64. 	newNode->prev = plist;
  65.  
  66. }
  67. //检查双向列表是否为空
  68. int CheckList(ListNode* plist) {
  69. 	assert(plist);
  70. 	//返回“真”为空 返回"假"为非空；
  71. 	return plist->next == plist->prev;
  72. }
  73. // 双向链表尾删
  74. void ListPopBack(ListNode* plist) {
  75. 	assert(plist);
  76. 	assert(!CheckList(plist));
  77. 	ListNode* tail = plist->prev;
  78.  
  79. 	//节点链接
  80. 	tail->prev->next = plist;
  81. 	plist->prev = tail->prev;
  82. 	//释放
  83. 	free(tail);
  84. }
  85. // 双向链表头删
  86. void ListPopFront(ListNode* plist) {
  87. 	assert(plist);
  88. 	assert(!CheckList(plist));
  89. 	ListNode* first = plist->next;
  90.  
  91. 	//节点链接
  92. 	plist->next = first->next;
  93. 	first->next->prev = plist;
  94.  
  95. 	//释放
  96. 	free(first);
  97. }
  98. // 双向链表查找
  99. ListNode* ListFind(ListNode* plist, LTDataType x) {
  100. 	assert(plist);
  101. 	if (CheckList(plist)) {
  102. 		printf("链表为NULL,无法查找有效数据\n");
  103. 		exit(-1);
  104. 	}
  105. 	ListNode* cur = plist->next;
  106. 	while (cur != plist) {
  107. 		if (cur->_data == x) {
  108. 			printf("找到啦\n");
  109. 			return cur;
  110. 		}
  111. 		cur = cur->next;
  112. 	}
  113. 	return NULL;
  114. }
  115. // 双向链表在pos的前面进行插入
  116. void ListInsert(ListNode* pos, LTDataType x) {
  117. 	assert(pos);
  118. 	ListNode* first = pos->prev;
  119. 	ListNode* second = pos;
  120. 	ListNode* newNode = ListBuyNode(x);
  121.  
  122. 	newNode->next = second;
  123. 	second->prev = newNode;
  124. 	first->next = newNode;
  125. 	newNode->prev = first;
  126.  
  127. }
  128. // 双向链表删除pos位置的结点
  129. void ListErase(ListNode* pos) {
  130. 	assert(pos);
  131. 	ListNode* first = pos->prev;
  132. 	ListNode* del = pos;
  133. 	ListNode* second = pos->next;
  134.  
  135. 	first->next = second;
  136. 	second->prev = first;
  137. 	free(del);
  138. }
  139. // 双向链表销毁
  140. void ListDestory(ListNode* plist) {
  141. 	assert(plist);
  142. 	ListNode* cur = plist->next;
  143. 	ListNode* next = NULL;
  144. 	plist->next = NULL;
  145. 	while (cur != NULL) {
  146. 		next = cur->next;
  147. 		free(cur);
  148. 		cur = next;
  149. 	}
  150. 	printf("销毁成功\n");
  151. }

四、顺序表、链表 oj

 顺序表

1. 原地移除数组中所有的元素 val ，要求时间复杂度为 O(N) ，空间复杂度为 O(1) 。
2. 删除排序数组中的重复项。
3. 合并两个有序数组。

力扣

链表

1. 删除链表中等于给定值 val 的所有结点  力扣
2. 反转一个单链表。
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则
返回第二个中间结点。
4. 输入一个链表，输出该链表中倒数第 k 个结点。
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有
结点组成的。
6. 编写代码，以给定值 x 为基准将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结
7. 链表的回文结构。 链表的回文结构_牛客题霸_牛客网
8. 输入两个链表，找出它们的第一个公共结点。 力扣
9. 给定一个链表，判断链表中是否有环。 力扣
【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，
如果链表
带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减
肥。
10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL 力扣
11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点
或空结点。
要求返回这个链表的深度拷贝。 力扣
12. 其他 。 ps ：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，以后大家自己
顺序表优点：
1.尾插、尾删效率高。
2.可以随机访问。.
（了解）3.cpu高速缓存命中率更高（相比链表）
顺序表缺点：
1.头部中部插入效率低——O(N)
2.扩容 ——性能消耗，空间浪费
链表优点：
1.任意插入删除都很方便
2.扩容——不存在空间浪费（按需申请空间）
链表缺点：
1.扩容——每次都要申请malloc浪费了时间
2.不能随机访问

 

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

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

  

闽ICP备14008679号