• 【数据结构与算法-初阶】顺序表和链表

    目录

    1.线性表

    2.顺序表

    2.1概念及结构

    2.2 接口实现

    2.3 顺序表的问题及思考

    3.链表

    3.1 链表的概念及结构

     3.2 链表的分类

    3.3 链表的实现

    3.3.1 无头+单向+非循环链表增删查改实现

    3.3.2 带头+双向+循环链表增删查改实现

    4.顺序表和链表的区别

    1.线性表

    线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...
    线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以    数组和链式结构的形式存储。

    2.顺序表

    2.1概念及结构

    顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存
    储。在数组上完成数据的增删查改。
    顺序表一般可以分为：

    (1) 静态顺序表：使用定长数组存储元素。

    (2) 动态顺序表：使用动态开辟的数组存储。

    2.2 接口实现

    静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

    1. typedef int SLDataType;
    2.  
    3. //动态顺序表 
    4. typedef struct SeqList
    5. {
    6. 	SLDataType* a;//指向动态数组的指针
    7. 	int size;     //数据个数
    8. 	int capacity; //容量-空间大小
    9. }SL;
    10.  
    11. //顺序表初始化
    12. void SLInit(SL* ps);
    13.  
    14. // 顺序表尾插
    15. void SLPushBack(SL* ps, SLDataType x);
    16.  
    17. // 顺序表尾删
    18. void SLPopBack(SL* ps);
    19.  
    20. // 顺序表头插
    21. void SLPushFront(SL* ps, SLDataType x);
    22.  
    23. // 顺序表头删
    24. void SLPopFront(SL* ps);
    25.  
    26. // 检查空间，如果满了，进行增容
    27. void SLCheckCapacity(SL* ps);
    28.  
    29. // 顺序表查找
    30. int SLFind(SL* ps, SLDataType x);
    31.  
    32. //顺序表修改
    33. void SLModify(SL* ps, int pos, SLDataType x);
    34.  
    35. // 顺序表在pos位置插入x
    36. void SLInsert(SL* ps, int pos, SLDataType x);
    37.  
    38. // 顺序表删除pos位置的值
    39. void SLErase(SL* ps, int pos);
    40.  
    41. // 顺序表销毁
    42. void SLDestory(SL* ps);
    43.  
    44. // 顺序表打印
    45. void SLPrint(SL* ps);

    接口的实现:

    1. void SLPrint(SL* ps)
    2. {
    3. 	assert(ps);
    4. 	for (int i = 0; i < ps->size; i++)
    5. 	{
    6. 		printf("%d ", ps->a[i]);
    7. 	}
    8. 	printf("\n");
    9. }
    10.  
    11. void SLInit(SL* ps)
    12. {
    13. 	assert(ps);
    14. 	ps->a = NULL;
    15. 	ps->size = ps->capacity = 0;
    16. }
    17.  
    18. void SLCheckCapacity(SL* ps)
    19. {
    20. 	assert(ps);
    21. 	if (ps->capacity == ps->size)
    22. 	{
    23. 		int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    24. 		SLDataType* tmp = (SLDataType*)realloc(ps->a, newCapacity * sizeof(SLDataType));
    25. 		if (tmp == NULL)
    26. 		{
    27. 			printf("realloc fail\n");
    28. 			exit(-1);
    29. 		}
    30. 		ps->a = tmp;
    31. 		ps->capacity = newCapacity;
    32. 	}
    33. }
    34.  
    35. int SLFind(SL* ps, SLDataType x)
    36. {
    37. 	assert(ps);
    38. 	for (int i = 0; i < ps->size; i++)
    39. 	{
    40. 		if (ps->a[i] = x)
    41. 			return i;
    42. 	}
    43. 	return -1;
    44. }
    45.  
    46. void SLModify(SL* ps, int pos, SLDataType x)
    47. {
    48. 	assert(ps);
    49. 	assert(pos <= 0 && pos > ps->size);
    50. 	ps->a[pos] = x;
    51. }
    52.  
    53. void SLInsert(SL* ps, int pos, SLDataType x)
    54. {
    55. 	assert(ps);
    56. 	assert(pos >= 0 && pos < ps->size);
    57. 	SLCheckCapacity(ps);
    58.  
    59. 	int end = 0;
    60. 	while (end >= pos)
    61. 	{
    62. 		ps->a[end + 1] = ps->a[end];
    63. 		end--;
    64. 	}
    65. 	ps->a[pos] = x;
    66. 	ps->size++;
    67. }
    68.  
    69. void SLErase(SL* ps, int pos)
    70. {
    71. 	assert(pos);
    72. 	assert(pos >= 0 && pos < ps->size);
    73. 	int begin = pos;
    74. 	while (begin < ps->size - 1)
    75. 	{
    76. 		ps->a[begin] = ps->a[begin + 1];
    77. 		begin++;
    78. 	}
    79. 	ps->size--;
    80. }
    81.  
    82. void SLPushBack(SL* ps, SLDataType x)
    83. {
    84. 	assert(ps);
    85. 	SLCheckCapacity(ps);
    86. 	ps->a[ps->size] = x;
    87. 	ps->size++;
    88. }
    89.  
    90. void SLPopBack(SL* ps)
    91. {
    92. 	assert(ps);
    93. 	assert(ps->size > 0);
    94. 	ps->size--;
    95. }
    96.  
    97. void SLPushFront(SL* ps, SLDataType x)
    98. {
    99. 	assert(ps);
    100. 	SLCheckCapacity(ps);
    101. 	int end = ps->size - 1;
    102. 	while (end >= 0)
    103. 	{
    104. 		ps->a[end + 1] = ps->a[end];
    105. 		end--;
    106. 	}
    107.  
    108. 	ps->a[0] = x;
    109. 	ps->size++;
    110. }
    111.  
    112. void SLPopFront(SL* ps)
    113. {
    114. 	assert(ps);
    115. 	assert(ps->size > 0);
    116. 	int begin = 0;
    117.     while(begin < ps->size - 1)
    118. 	{
    119. 		ps->a[begin + 1] = ps->a[begin];
    120. 		begin++;
    121. 	}
    122. 	ps->size--;
    123. }
    124.  
    125.  
    126. void SLDestory(SL* ps)
    127. {
    128. 	assert(ps);
    129. 	if (ps->a)
    130. 	{
    131. 		free(ps->a);
    132. 		ps->a = NULL;
    133. 		ps->capacity = ps->size = 0;
    134. 	}
    135. }

    2.3 顺序表的问题及思考

    问题：
    1. 中间/头部的插入删除，时间复杂度为O(N)
    2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
    3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
    思考：如何解决以上问题呢？下面给出了链表的结构来看看。
     

    3.链表

    3.1 链表的概念及结构

    概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。

     3.2 链表的分类

    实际中链表的结构非常多样，以下情况组合起来就有8种链表结构：

    1. 单向或者双向

    2. 带头或者不带头

    3. 循环或者非循环

     

     虽然有这么多的链表的结构，但是我们实际中最常用还是两种结构：

    无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
    带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

    3.3 链表的实现

    3.3.1 无头+单向+非循环链表增删查改实现
     

    1. typedef int SLTDataType;
    2.  
    3. typedef struct SListNode
    4. {
    5. 	struct SListNode* next;
    6. 	SLTDataType data;
    7. }SLTNode;
    8.  
    9. //开辟空间
    10. SLTNode* BuySListNode(SLTDataType x);
    11.  
    12. //打印
    13. void SListPrint(SLTNode* phead);
    14.  
    15. //尾插
    16. void SListPushBack(SLTNode** pphead, SLTDataType x);
    17.  
    18. //头插
    19. void SListPushFront(SLTNode** pphead, SLTDataType x);
    20.  
    21. //尾删
    22. void SListPopBack(SLTNode** pphead);
    23.  
    24. //头删
    25. void SListPopFront(SLTNode** pphead);
    26.  
    27. //查找
    28. SLTNode* SListFind(SLTNode* phead, SLTDataType x);
    29.  
    30. // 在pos位置之前插入
    31. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
    32.  
    33. // 删除pos位置的值
    34. void SListErase(SLTNode** pphead, SLTNode* pos);
    35.  
    36. // 在pos位置后面插入
    37. void SListInsertAfter(SLTNode* pos, SLTDataType x);
    38.  
    39. // 删除pos位置后面的值
    40. void SListEraseAfter(SLTNode* pos);

    接口的实现:

    1. SLTNode* BuySListNode(SLTDataType x)
    2. {
    3. 	SLTNode* newNode = (SLTNode*)malloc(sizeof(SLTNode));
    4. 	assert(newNode);
    5. 	newNode->data = x;
    6. 	newNode->next = NULL;
    7.  
    8. 	return newNode;
    9. }
    10.  
    11. void SListPrint(SLTNode* phead)
    12. {
    13. 	assert(phead);
    14. 	SLTNode* cur = phead;
    15. 	while (cur != NULL)
    16. 	{
    17. 		printf("%d->", cur->data);
    18. 		cur = cur->next;
    19. 	}
    20. 	printf("NULL\n");
    21. }
    22.  
    23. void SListPushBack(SLTNode** pphead, SLTDataType x)
    24. {
    25. 	assert(pphead);
    26. 	SLTNode* newNode = BuySListNode(x);
    27.  
    28. 	if (*pphead == NULL)
    29. 	{
    30. 		*pphead = newNode;
    31. 	}
    32. 	else
    33. 	{
    34. 		// 找尾节点
    35. 		SLTNode* tail = *pphead;
    36. 		while (tail->next != NULL)
    37. 		{
    38. 			tail = tail->next;
    39. 		}
    40.  
    41. 		tail->next = newNode;
    42. 	}
    43. }
    44.  
    45. void SListPushFront(SLTNode** pphead, SLTDataType x)
    46. {
    47. 	assert(pphead);
    48. 	SLTNode* newNode = BuySListNode(x);
    49.  
    50. 	newNode->next = *pphead;
    51. 	*pphead = newNode;
    52. }
    53.  
    54.  
    55. void SListPopBack(SLTNode** pphead)
    56. {
    57. 	assert(pphead);
    58. 	assert(*pphead);
    59.  
    60. 	// 1、只有一个节点
    61. 	// 2、多个节点
    62. 	if ((*pphead)->next == NULL)
    63. 	{
    64. 		free(*pphead);
    65. 		*pphead = NULL;
    66. 	}
    67. 	else
    68. 	{
    69. 		
    70. 		SLTNode* tail = *pphead;
    71. 		while (tail->next->next != NULL)
    72. 		{
    73. 			tail = tail->next;
    74. 		}
    75. 		free(tail->next);
    76. 		tail->next = NULL;
    77. 	}
    78. }
    79.  
    80. void SListPopFront(SLTNode** pphead)
    81. {
    82. 	assert(pphead);
    83. 	assert(*pphead != NULL);
    84. 	//if (*pphead == NULL)
    85. 	//	return;
    86.  
    87. 	SLTNode* next = (*pphead)->next;
    88. 	free(*pphead);
    89. 	*pphead = next;
    90. }
    91.  
    92. SLTNode* SListFind(SLTNode* phead, SLTDataType x)
    93. {
    94. 	SLTNode* cur = phead;
    95. 	while (cur)
    96. 	{
    97. 		if (cur->data == x)
    98. 			return cur;
    99.  
    100. 		cur = cur->next;
    101. 	}
    102.  
    103. 	return NULL;
    104. }
    105.  
    106.  
    107. void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
    108. {
    109. 	assert(pos);
    110. 	assert(pphead);
    111.  
    112. 	// 头插
    113. 	if (pos == *pphead)
    114. 	{
    115. 		SListPushFront(pphead, x);
    116. 	}
    117. 	else
    118. 	{
    119. 		SLTNode* prev = *pphead;
    120. 		while (prev->next != pos)
    121. 		{
    122. 			prev = prev->next;
    123. 		}
    124.  
    125. 		SLTNode* newnode = BuySListNode(x);
    126. 		prev->next = newnode;
    127. 		newnode->next = pos;
    128. 	}
    129. }
    130.  
    131.  
    132. void SListErase(SLTNode** pphead, SLTNode* pos)
    133. {
    134. 	assert(pphead);
    135. 	assert(pos);
    136.  
    137. 	if (*pphead == pos)
    138. 	{
    139. 		SListPopFront(pphead);
    140. 	}
    141. 	else
    142. 	{
    143. 		SLTNode* prev = *pphead;
    144. 		while (prev->next != pos)
    145. 		{
    146. 			prev = prev->next;
    147. 		}
    148.  
    149. 		prev->next = pos->next;
    150.  
    151. 		free(pos);
    152. 		pos = NULL;
    153. 	}
    154. }
    155.  
    156.  
    157. void SListInsertAfter(SLTNode* pos, SLTDataType x)
    158. {
    159. 	assert(pos);
    160.  
    161. 	
    162. 	// 不在乎链接顺序
    163. 	SLTNode* newnode = BuySListNode(x);
    164. 	SLTNode* next = pos->next;
    165.  
    166. 	pos->next = newnode;
    167. 	newnode->next = next;
    168. }
    169.  
    170. void SListEraseAfter(SLTNode* pos)
    171. {
    172. 	assert(pos);
    173.  
    174. 	if (pos->next == NULL)
    175. 		return;
    176.  
    177. 	SLTNode* del = pos->next;
    178.  
    179. 	pos->next = del->next;
    180.  
    181. 	free(del);
    182. 	del = NULL;
    183. }

    3.3.2 带头+双向+循环链表增删查改实现

    1. typedef int LTDataType;
    2. typedef struct ListNode
    3. {
    4. 	struct ListNode* next;
    5. 	struct ListNode* prev;
    6. 	LTDataType data;
    7. }LTNode;
    8.  
    9. //初始化
    10. LTNode* ListInit();
    11.  
    12. //打印
    13. void ListPrint(LTNode* phead);
    14.  
    15. //尾插
    16. void ListPushBack(LTNode* phead, LTDataType x);
    17.  
    18. //头插
    19. void ListPushFront(LTNode* phead, LTDataType x);
    20.  
    21. //尾删
    22. void ListPopBack(LTNode* phead);
    23.  
    24. //头删
    25. void ListPopFront(LTNode* phead);
    26.  
    27. //判断是否为空
    28. bool ListEmpty(LTNode* phead);
    29.  
    30. // 在pos位置之前插入x
    31. void ListInsert(LTNode* pos, LTDataType x);
    32.  
    33. //  删除pos位置的节点
    34. void ListErase(LTNode* pos);

    接口的实现:

    1. LTNode* BuyListNode(LTDataType x)
    2. {
    3. 	LTNode* newNode = (LTNode*)malloc(sizeof(LTNode));
    4. 	if (newNode == NULL)
    5. 	{
    6. 		perror("malloc fail");
    7. 		exit(-1);
    8. 	}
    9. 	newNode->data = x;
    10. 	newNode->next = NULL;
    11. 	newNode->prev = NULL;
    12. 	return newNode;
    13. }
    14.  
    15. LTNode* ListInit()
    16. {
    17. 	LTNode* phead = BuyListNode(-1);
    18. 	phead->next = phead;
    19. 	phead->prev = phead;
    20.  
    21. 	return phead;
    22. }
    23.  
    24. void ListPrint(LTNode* phead)
    25. {
    26. 	assert(phead);
    27. 	LTNode* cur = phead->next;
    28. 	while (cur != phead)
    29. 	{
    30. 		printf("%d ", cur->data);
    31. 		cur = cur->next;
    32. 	}
    33. 	printf("\n");
    34. }
    35.  
    36. void ListPushBack(LTNode* phead, LTDataType x)
    37. {
    38. 	assert(phead);
    39.  
    40. 	LTNode* newNode = BuyListNode(x);
    41. 	LTNode* tail = phead->prev;
    42. 	tail->next = newNode;
    43. 	newNode->prev = tail;
    44. 	newNode->next = phead;
    45. 	phead->prev = newNode;
    46. }
    47.  
    48. void ListPushFront(LTNode* phead, LTDataType x)
    49. {
    50. 	assert(phead);
    51. 	LTNode* newNode = BuyListNode(x);
    52. 	LTNode* next = phead->next;
    53. 	newNode->next = next;
    54. 	next->prev = newNode;
    55. 	newNode->prev = phead;
    56. 	phead->next = newNode;
    57. }
    58.  
    59. void ListPopBack(LTNode* phead)
    60. {
    61. 	assert(phead);
    62.  
    63. 	assert(phead->next != phead);
    64. 	
    65. 	LTNode* tail = phead->prev;
    66. 	LTNode* tailPrev = tail->prev;
    67.  
    68. 	free(tail);
    69.  
    70. 	tailPrev->next = phead;
    71. 	phead->prev = tailPrev;
    72. }
    73.  
    74. void ListPopFront(LTNode* phead)
    75. {
    76. 	assert(phead);
    77. 	assert(phead->next != phead);
    78. 	LTNode* cur = phead->next;
    79. 	LTNode* next = phead->next->next;
    80.  
    81. 	phead->next = next;
    82. 	next->prev = phead;
    83. 	free(cur);
    84. }
    85.  
    86. bool ListEmpty(LTNode* phead)
    87. {
    88. 	assert(phead);
    89. 	return phead->next == phead;
    90. }
    91.  
    92. void ListInsert(LTNode* pos, LTDataType x)
    93. {
    94. 	assert(pos);
    95. 	LTNode* prev = pos->prev;
    96. 	LTNode* newnode = BuyListNode(x);
    97.  
    98. 	prev->next = newnode;
    99. 	newnode->prev = prev;
    100. 	newnode->next = pos;
    101. 	pos->prev = newnode;
    102. }
    103.  
    104. void ListErase(LTNode* pos)
    105. {
    106. 	assert(pos);
    107. 	LTNode* prev = pos->prev;
    108. 	LTNode* next = pos->next;
    109.  
    110. 	prev->next = next;
    111. 	next->prev = prev;
    112. 	free(pos);
    113. }

    4.顺序表和链表的区别
     

    不同点

    		顺序表链表
    存储空间上物理上一定连续逻辑上连续，但物理上不一定
    连续
    随机访问支持O(1)不支持：O(N)
    任意位置插入或者删除
    元素    		可能需要搬移元素，效率低
    O(N)    		只需修改指针指向
    插入动态顺序表，空间不够时需要
    扩容    		没有容量的概念
    应用场景元素高效存储+频繁访问任意位置插入和删除频繁
    缓存利用率高低

    备注：缓存利用率参考存储体系结构 以及 局部原理性。
     

  • 相关阅读:
    maven运行乱码，控制台运行乱码 idea,非法字符: ‘\ufeff‘需要class, interface或enum
    Go和Java实现命令模式
    Python爬虫详解：原理、常用库与实战案例
    Git 入门到精通
    51单片机BH1750智能补光灯台灯光强光照恒流源LED控制系统
    【密码学复习】第九讲 密钥管理（二）
    《中国垒球》：“五个融合”打开中国垒球发展新局面
    图解系列--理解L3交换机的性能与功能
    1、读写分离、分库分表
    Trello的替代方案有哪些？6种国内外选择！
  • 原文地址：https://blog.csdn.net/qq_54880517/article/details/125306153