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

数据结构---顺序表，链表_顺序链表

作者：盐析白兔 | 2024-05-02 04:58:53

赞

踩

顺序链表

目录

前言

线性表

线性表的概念

顺序表

顺序表的概念

顺序表的结构

接口实现

相关面试题分析

顺序表的问题及思考

链表

链表的概念及结构

链表的分类

单链表的实现 

接口实现 

链表面试题

双向链表

顺序表和链表的区别

前言

        这篇文章主要讲顺序表和链表，有几点需要大家注意一下：1.在学习的时候如果认为看着比较吃力的话，建议先去看看c语言--指针于结构体。2.当我们学习数据结构更多的是要练习，一遍一遍的把练习把基础打牢固。3.我们希望大家都能养成爱画图的习惯，很多时候图画出来了，思路就清晰了，代码就自然出来。4.遇到bug多调试，不熟不要怕慢慢就熟了。在这里与君共勉，互相加油，互相学习。

线性表

线性表的概念

        线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串...

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

 顺序表

顺序表的概念

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

顺序表的结构

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

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

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

接口实现

SeqList.h---头文件，声明

  1. #pragma once
  2. #include <stdio.h>
  3. #include <assert.h>
  4. #include <stdlib.h>
  5.  
  6. typedef int SLDateType;
  7.  
  8. typedef struct SeqList
  9. {
  10. 	SLDateType* a;
  11. 	size_t size;
  12. 	size_t capacity;
  13. }SeqList;
  14.  
  15. //初始化
  16. void SeqListInit(SeqList* ps);
  17.  
  18. //销毁
  19. void SeqListDestroy(SeqList* ps);
  20.  
  21. //打印
  22. void SeqListPrint(SeqList* ps);
  23.  
  24. //尾加
  25. void SeqListPushBack(SeqList* ps, SLDateType x);
  26.  
  27. //头加
  28. void SeqListPushFront(SeqList* ps, SLDateType x);
  29.  
  30. //头删
  31. void SeqListPopFront(SeqList* ps);
  32.  
  33. //尾删
  34. void SeqListPopBack(SeqList* ps);
  35.  
  36. //顺序表查找
  37. int SeqListFind(SeqList* ps, SLDateType x);
  38.  
  39. //顺序表在pos位置插入x
  40. void SeqListInsert(SeqList* ps, size_t pos, SLDateType x);
  41.  
  42. //顺序表删除pos位置的值
  43. void SeqListErase(SeqList* ps, size_t pos);

SeqList.c---函数实现

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include  "SeqList.h"
  3.  
  4.  
  5. void SeqListInit(SeqList* ps)//初始化
  6. {
  7. 	assert(ps);
  8.  
  9. 	ps->a = NULL;
  10. 	ps->size = ps->capacity = 0;
  11. }
  12.  
  13. void SeqListDestroy(SeqList* ps)//销毁
  14. {
  15. 	assert(ps);
  16. 	free(ps->a);
  17. 	ps->a = NULL;
  18. 	ps->size = ps->capacity = 0;
  19. }
  20.  
  21. void SeqListPrint(SeqList* ps)//打印
  22. {
  23. 	assert(ps);
  24.  
  25. 	for (size_t i = 0; i < ps->size; i++)
  26. 	{
  27. 		printf("%d ", ps->a[i]);
  28. 	}
  29. 	printf("\n");
  30. }
  31.  
  32. void SLCheckCapacity(SeqList* ps)//检查
  33. {
  34. 	if (ps->size==ps->capacity)
  35. 	{
  36. 		SLDateType newCapcity = ps->capacity==0 ? 4 : ps->capacity * 2;
  37. 		SLDateType* temp = (SLDateType*)realloc(ps->a, sizeof(ps->a)*newCapcity);
  38. 		if (temp == NULL)
  39. 		{
  40. 			perror("realloc fail");
  41. 			return;
  42. 		}
  43. 		ps->a = temp;
  44. 		ps->capacity = newCapcity;
  45. 	}
  46. }
  47.  
  48. void SeqListPushBack(SeqList* ps, SLDateType x)//尾加
  49. {
  50. 	assert(ps);
  51. 	SLCheckCapacity(ps);
  52.  
  53. 	ps->a[ps->size] = x;
  54. 	ps->size++;
  55. }
  56.  
  57. void SeqListPushFront(SeqList* ps, SLDateType x)//头加
  58. {
  59. 	assert(ps);
  60. 	SLCheckCapacity(ps);
  61.  
  62. 	int end = ps->size-1;
  63. 	while (end >= 0)
  64. 	{
  65. 		ps->a[end+1] = ps->a[end];
  66. 		end--;	
  67. 	}
  68. 	ps->a[0] = x;
  69. 	ps->size++;
  70. }
  71.  
  72. void SeqListPopFront(SeqList* ps)//头删
  73. {
  74. 	assert(ps);
  75.  
  76. 	if (ps->size == 0)
  77. 	{
  78. 		return;
  79. 	}
  80. 	SLDateType str = 0;
  81. 	SLDateType end = ps->size - 1;
  82. 	while (str <= end)
  83. 	{
  84. 		ps->a[str] = ps->a[str + 1];
  85. 		str++;
  86. 	}
  87. 	ps->size--;
  88. }
  89.  
  90. void SeqListPopBack(SeqList* ps)//尾删
  91. {
  92. 	assert(ps);
  93. 	if (ps->size == 0)
  94. 	{
  95. 		return;
  96. 	}
  97. 	ps->size--;
  98. }
  99.  
  100. int SeqListFind(SeqList* ps, SLDateType x)//顺序表插入
  101. {
  102. 	assert(ps);
  103.  
  104. 	int end = ps->size - 1;
  105. 	while (end>=0)
  106. 	{
  107. 		if (ps->a[end] == x)
  108. 			return end;
  109. 		end--;
  110. 	}
  111. 	return -1;
  112. }
  113.  
  114. void SeqListInsert(SeqList* ps, size_t pos, SLDateType x)//顺序表在pos位置插入x
  115. {
  116. 	assert(ps);
  117.  
  118. 	if (pos < 0 || pos >(ps->size - 1))
  119. 	{
  120. 		printf("输入错误\n");
  121. 		return;
  122. 	}
  123.  
  124. 	for (size_t i = ps->size; i > pos; i--)
  125. 	{
  126. 		ps->a[i] = ps->a[i - 1];
  127. 	}
  128. 		
  129. 	ps->a[pos] = x;
  130. 	ps->size++;
  131. }
  132.  
  133. void SeqListErase(SeqList* ps, size_t pos)//顺序表删除pos位置的值
  134. {
  135. 	assert(ps);
  136.  
  137. 	if (pos < 0 || pos >(ps->size - 1))
  138. 	{
  139. 		printf("输入错误\n");
  140. 		return;
  141. 	}
  142.  
  143. 	for (size_t i = pos; i < ps->size; i++)
  144. 	{
  145. 		ps->a[i] = ps->a[i+1];
  146. 	}
  147. 	ps->size--;
  148. }

 test.c---测试

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "SeqList.h" 
  3.  
  4. int main()
  5. {
  6. 	SeqList s;
  7. 	SeqListInit(&s);
  8.  
  9. 	SeqListPushBack(&s, 1);
  10. 	SeqListPrint(&s);
  11.  
  12. 	SeqListPushFront(&s, 2);
  13. 	SeqListPushFront(&s, 3);
  14. 	SeqListPrint(&s);
  15.  
  16. 	SeqListPopFront(&s);
  17. 	SeqListPrint(&s);
  18.  
  19. 	int ret = SeqListFind(&s, 2);
  20. 	if (ret == 1)
  21. 		printf("yes\n");
  22. 	else
  23. 		printf("no\n");
  24.  
  25. 	SeqListInsert(&s, 1, 5);
  26. 	SeqListPrint(&s);
  27.  
  28. 	SeqListErase(&s, 1);
  29. 	SeqListPrint(&s);
  30. }

这里建议实现一个函数了就先测试了来，后面过多了就容易看着眼花缭乱的。大神就另当别论！

相关面试题分析

例题1

原地移除数组中所有的元素val，要求时间复杂度为O(N)，空间复杂度为O(1)。链接

实现过程：

 实现代码：

  1. int removeElement(int* nums, int numsSize, int val){
  2.    
  3.    int src=0,dest=0;
  4.    while(src<numsSize)
  5.    {
  6.        if(nums[src]==val)
  7.        {
  8.            src++;
  9.        }
  10.        else
  11.        {
  12.            nums[dest++]=nums[src++];
  13.        }
  14.    }
  15.     return dest;
  16. }

例题2

删除排序数组中的重复项：链接

实现过程：

 实现代码：

  1. int removeDuplicates(int* nums, int numsSize){
  2.    if (numsSize == 0) {
  3. 		return 0;
  4. 	}
  5.     int src=1,dest=0;
  6.     while(src<numsSize)
  7.     {
  8.         if(nums[src]==nums[dest])
  9.         {
  10.             src++;
  11.         }
  12.         else
  13.         {
  14.             dest++;
  15.             nums[dest]=nums[src];
  16.             src++;
  17.         }
  18.     }
  19.     return dest+1;
  20. }

例题3

合并两个有序数组：链接

实现过程---2种情况:：

 实现代码：

  1. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
  2.    int src=m-1,dest=n-1;
  3.    int end=m+n-1;
  4.    while(src>=0&&dest>=0)
  5.    {
  6.        if(nums1[src]>nums2[dest])
  7.        {
  8.            nums1[end]=nums1[src];
  9.            src--;
  10.            end--;
  11.        }
  12.        else
  13.        {
  14.            nums1[end]=nums2[dest];
  15.            end--;
  16.            dest--;
  17.        }
  18.    }
  19.    while(dest>=0)
  20.    {
  21.        nums1[end]=nums2[dest];
  22.        end--;
  23.        dest--;
  24.    }
  25. }
  26.  
  27. //方法二--插入快排
  28. int cmp(void* dest,void* src)
  29. {
  30.     return *(int*)dest-*(int*)src;
  31. }
  32. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
  33.    
  34.     for (int i=0;i!=n;i++){
  35. 		nums1[m+i] = nums2[i];
  36. 	}
  37.     qsort(nums1,n+m,sizeof(int),cmp);
  38. }

 顺序表的问题及思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(N)

2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。

3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

如何解决这一问题呢？下面给出了链表的结构来看看。

链表

链表的概念及结构

概念：

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

 链表的分类

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

 单向或者双向

 带头或者不带头 

循环或者非循环 

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

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面代码实现了就知道了。

单链表的实现 

在学习单链表之前，我们需要弄明白我们是否需要改变我们传过去的参数？如果需要改变那我们传参的时候，实现功能的函数用什么接受参数？我们知道单链表是需要结构体来实现的，一个是存数据一个是存地址，那么结构体中的变量就应该是一个int类型的数据和一个指针。当我们明白结构体重的变量之后，我们会发现实现增删改查就是改变指针中的地址。数据有地址，指针也有地址。所需要改变指针地址时，我们就用二级指针来接受指针的地址。下面就是说明为什么需要用二级指针来接受。

接口实现 

SList.h--函数声明

  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <stdio.h>
  3. #include <assert.h>
  4. #include <stdlib.h> 
  5. typedef int SLTDateType;
  6.  
  7. //创建结构体
  8. typedef struct SListNode
  9. {
  10. 	SLTDateType data;
  11. 	struct SListNode* next;
  12. }SListNode;
  13.  
  14. // 动态申请一个节点
  15. SListNode* BuySListNode(SLTDateType x);
  16.  
  17. // 单链表打印
  18. void SListPrint(SListNode* phead);
  19.  
  20. // 单链表尾插
  21. void SListPushBack(SListNode** pphead, SLTDateType x);
  22.  
  23. // 单链表的头插
  24. void SListPushFront(SListNode** pphead, SLTDateType x);
  25.  
  26. // 单链表的尾删
  27. void SListPopBack(SListNode** pphead);
  28.  
  29. // 单链表头删
  30. void SListPopFront(SListNode** pphead);
  31.  
  32. // 单链表查找
  33. SListNode* SListFind(SListNode* plist, SLTDateType x);
  34.  
  35. // 单链表在pos位置之后插入x
  36. void SListInsertAfter(SListNode* pos, SLTDateType x);
  37.  
  38. // 单链表删除pos位置之后的值
  39. void SListEraseAfter(SListNode* pos);
  40.  
  41. // 单链表的销毁
  42. void SListDestroy(SListNode* phead);

SList.c--功能实现

  1. #include "SList.h"
  2.  
  3. // 动态申请一个节点
  4. SListNode* BuySListNode(SLTDateType x)
  5. {
  6. 	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)* 1);
  7. 	if (newnode == NULL)
  8. 	{
  9. 		perror("malloc fail");
  10. 		exit(-1);
  11. 	}
  12. 	newnode->data = x;
  13. 	newnode->next = NULL;
  14.  
  15. 	return newnode;
  16. }
  17.  
  18. // 单链表打印
  19. void SListPrint(SListNode* phead)
  20. {
  21. 	assert(phead);
  22. 	SListNode*cur = phead;
  23.  
  24. 	while (cur != NULL)
  25. 	{
  26. 		printf("%d->", cur->data);
  27. 		cur = cur->next;
  28. 	}
  29. 	printf("NULL\n");
  30. }
  31.  
  32. // 单链表尾插
  33. void SListPushBack(SListNode** pphead, SLTDateType x)
  34. {
  35. 	assert(pphead);
  36.  
  37. 	SListNode* newnode = BuySListNode(x);
  38. 	if (*pphead == NULL)//为空
  39. 	{
  40. 		*pphead = newnode;
  41. 	}
  42. 	else//不为空
  43. 	{
  44. 		SListNode* tail = *pphead;
  45. 		while (tail->next != NULL)
  46. 		{
  47. 			tail = tail->next;
  48. 		}
  49. 		tail->next = newnode;
  50. 	}
  51. }
  52.  
  53. // 单链表的头插
  54. void SListPushFront(SListNode** pphead, SLTDateType x)
  55. {
  56. 	assert(pphead);
  57. 	SListNode* newnode = BuySListNode(x);
  58. 	newnode->next = *pphead;
  59. 	*pphead = newnode;
  60. }
  61.  
  62. // 单链表的尾删
  63. void SListPopBack(SListNode** pphead)
  64. {
  65. 	assert(pphead);
  66. 	if (*pphead == NULL)
  67. 	{
  68. 		return;
  69. 	}
  70.  
  71. 	SListNode* tail = *pphead;
  72. 	while (tail->next->next != NULL)
  73. 	{
  74. 		tail = tail->next;
  75. 	}
  76. 	free(tail->next);
  77. 	tail->next = NULL;
  78.  
  79. }
  80.  
  81. // 单链表头删
  82. void SListPopFront(SListNode** pphead)
  83. {
  84. 	assert(pphead);
  85. 	
  86. 	if (*pphead == NULL)
  87. 	{
  88. 		return;
  89. 	}
  90. 	SListNode* del = *pphead;
  91. 	*pphead = del->next;
  92. 	free(del);
  93. 	del = NULL;
  94. }
  95.  
  96. // 单链表查找
  97. SListNode* SListFind(SListNode* plist, SLTDateType x)
  98. {
  99. 	assert(plist);
  100.  
  101. 	while (plist->data!= x)
  102. 	{
  103. 		plist = plist->next;
  104. 	}
  105. 	if (plist == NULL)
  106. 	{
  107. 		return NULL;
  108. 	}
  109. 	else
  110. 		return plist;
  111. }
  112.  
  113. // 单链表在pos位置之后插入x
  114. void SListInsertAfter( SListNode* pos, SLTDateType x)
  115. {
  116. 	assert(pos);
  117. 	SListNode*newnode= BuySListNode(x);
  118. 	newnode->next = pos->next;
  119. 	pos->next = newnode;
  120.  
  121. }
  122.  
  123. // 单链表删除pos位置之后的值
  124. void SListEraseAfter(SListNode* pos)
  125. {
  126. 	assert(pos);
  127. 	//SListNode*newnode = pos->next;	
  128. 	//
  129. 	//if (newnode != NULL)
  130. 	//{
  131. 	//	SListNode* nextnext = newnode->next;
  132. 	//	free(newnode);
  133. 	//	pos->next = nextnext;
  134. 	//}
  135. 	SListNode*newnode = pos;
  136. 	if (newnode->next != NULL)
  137. 	{
  138. 		SListNode*nextnext = newnode->next->next;
  139. 		free(newnode->next);
  140. 		pos->next = nextnext;
  141. 	}
  142. }
  143.  
  144. // 单链表的销毁
  145. void SListDestroy(SListNode* phead)
  146. {
  147. 	assert(phead);
  148.  
  149. 	free(phead->next);
  150. 	phead->data = 0;
  151. 	phead->next= NULL; 
  152. }

Test.c--测试

  1. #include "SList.h"
  2.  
  3. //尾插展示
  4. void TestSList1()
  5. {
  6. 	SListNode* plist=NULL;
  7. 	SListPushBack(&plist, 1);
  8. 	SListPushBack(&plist, 3);
  9. 	SListPushBack(&plist, 7);
  10. 	SListPrint(plist);
  11.  
  12. }
  13.  
  14. //头查展示
  15. void TestSList2()
  16. {
  17. 	SListNode* plist = NULL;
  18. 	SListPushFront(&plist, 1);
  19. 	SListPushFront(&plist, 7);
  20. 	SListPushFront(&plist, 11);
  21. 	SListPrint(plist);
  22. }
  23. // 单链表的尾删
  24. void TestSList3()
  25. {
  26. 	SListNode* plist = NULL;
  27. 	SListPushFront(&plist, 1);
  28. 	SListPushFront(&plist, 7);
  29. 	SListPushFront(&plist, 11);
  30. 	SListPopBack(&plist);
  31. 	SListPopBack(&plist);
  32. 	SListPrint(plist);
  33. }
  34. void TestSList4()
  35. {
  36. 	SListNode* plist = NULL;
  37. 	SListPushFront(&plist, 2);
  38. 	SListPushFront(&plist, 8);
  39. 	SListPushFront(&plist, 9);
  40. 	SListPopFront(&plist);
  41. 	SListPrint(plist);
  42. 	SListNode* pos = SListFind(plist, 8);
  43. 	if (pos)
  44. 	{
  45. 		// ޸
  46. 		pos->data *= 10;
  47. 		printf("\n");
  48. 	}
  49. 	else
  50. 	{
  51. 		printf("\n");
  52. 	}
  53. 	SListPrint(plist);
  54.  
  55. }
  56. void TestSList5()
  57. {
  58. 	SListNode* plist = NULL;
  59. 	SListPushFront(&plist, 2);
  60. 	SListPushFront(&plist, 2);
  61. 	SListPushFront(&plist, 3);
  62. 	SListPushFront(&plist, 4);
  63. 	SListNode* pos = SListFind(plist, 2);
  64. 	SListInsertAfter(pos, 4);
  65. 	SListPrint(plist);
  66. }
  67.  
  68. void TestSList6()
  69. {
  70. 	SListNode* plist = NULL;
  71. 	SListPushFront(&plist, 4);
  72. 	SListPushFront(&plist, 5);
  73. 	SListPushFront(&plist, 7);
  74. 	SListPushFront(&plist, 8);
  75. 	SListPushFront(&plist, 8);
  76. 	SListPushFront(&plist, 8);
  77. 	SListNode* pos = SListFind(plist,7);
  78. 	SListEraseAfter(pos);
  79. 	SListPrint(plist);
  80.  
  81. }
  82.  
  83. void TestSList7()
  84. {
  85. 	SListNode* plist = NULL;
  86. 	SListPushFront(&plist, 4);
  87. 	SListPushFront(&plist, 5);
  88. 	SListPushFront(&plist, 7);
  89. 	SListDestroy(plist);
  90. 	SListPrint(plist);
  91. }
  92.  
  93. int main()
  94. {
  95. 	TestSList1();
  96. 	TestSList2();
  97. 	TestSList3();
  98. 	TestSList4();
  99. 	TestSList5();
  100. 	TestSList6();
  101. 	TestSList7();
  102. }

链表面试题

例题1

删除链表中等于给定值 val 的所有结点 ：链接

图文解析：

实现代码：

  1. struct ListNode* removeElements(struct ListNode* head, int val){
  2.   struct ListNode* plist=NULL;
  3.   struct ListNode* newnod=head;
  4.     while(newnod)
  5.     {       
  6.         if(newnod->val!=val)
  7.         {
  8.             plist=newnod;
  9.             newnod=newnod->next;
  10.         }
  11.         else 
  12.         {
  13.             if(plist==NULL)
  14.             {
  15.                 head=newnod->next;
  16.                 free(newnod); 
  17.                 newnod=head;         
  18.             }
  19.             else
  20.             {
  21.                plist->next=newnod->next;
  22.                 free(newnod);
  23.                 newnod=plist->next;
  24.             }
  25.         }
  26.     }
  27.     return  head;
  28. }

例题2

反转一个单链表：链接

方法1：我们用plist来改变地址指向，最开始将首元素next地址置为空，再将首元素地址赋予plist，将第二个元素的next地址改成第一个元素地址，接下来依次循环。主要是用plist与next保存地址。

图文解析：

 实现代码：

  1. struct ListNode* reverseList(struct ListNode* head){
  2.     struct ListNode* plist=NULL;
  3.     struct ListNode* cur=head;
  4.  
  5.     while(cur)
  6.     {
  7.         struct ListNode* next=cur->next;
  8.         cur->next=plist;
  9.         plist=cur;
  10.  
  11.         cur=next;
  12.     }
  13.     return plist;
  14. }

方法2：我们用n1，n2，n3进行同时移动，将n1赋值为null，n2为首元素，n3为首元素next，我们改变了地址指向后，n1，n2，n3依次向右的移动，n1为n2，n2为n3，直到n2位空，用返回n1。

图文解析：

  实现代码：

  1. struct ListNode* reverseList(struct ListNode* head){
  2.     struct ListNode* n1=NULL;
  3.     struct ListNode* n2=head;
  4.     struct ListNode* n3=NULL;
  5.     while(n2)
  6.     {
  7.         n3=n2->next;
  8.         n2->next=n1;
  9.         n1=n2;
  10.         n2=n3; 
  11.                 
  12.     }
  13.     return n1;
  14. }

例题3：

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则 返回第二个中间结点：链接

图文解析：

实现代码：

  1. struct ListNode* middleNode(struct ListNode* head){
  2.     struct ListNode* slow=head;
  3.     struct ListNode* fsat=head;
  4.     while(fsat&&fsat->next)
  5.     {
  6.          fsat=fsat->next->next;
  7.          slow=slow->next;
  8.     }
  9.     return slow;
  10. }

例题4

输入一个链表，输出该链表中倒数第k个结点：链接

图文解析：

实现代码： 

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     struct ListNode* fast=pListHead;
  3.     struct ListNode* slow=pListHead;
  4.     struct ListNode* cur=pListHead;
  5.     int count=0;
  6.     while(cur)
  7.     {
  8.         cur=cur->next;
  9.         count++;
  10.     }
  11.     if(pListHead==NULL||k==0||k>count)
  12.     {
  13.         return NULL;
  14.     }
  15.     while(k--&&fast)
  16.     {
  17.         fast=fast->next;
  18.     }
  19.    
  20.     while(fast)
  21.     {
  22.         fast=fast->next;
  23.         slow=slow->next;
  24.     }
  25.     return slow;
  26. }

 注意：有两个特殊情况，当k（倒数第几个）=0时，链表为空是，k>count(链表长度)时，返回null

例题5

图文解析：

 实现代码：

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  2.     struct ListNode* cur=(struct ListNode*)malloc(sizeof(struct ListNode));
  3.     cur->next=NULL;
  4.     struct ListNode* prve=cur;
  5.  
  6.  
  7.     struct ListNode* plist1=list1;
  8.     struct ListNode* plist2=list2;
  9.  
  10.  
  11.     while(plist1&&plist2)
  12.     {
  13.         if((plist1->val) <=(plist2->val))
  14.         {
  15.             prve->next=plist1;
  16.             prve=prve->next;
  17.             plist1=plist1->next;
  18.         }
  19.         else
  20.         {
  21.             prve->next=plist2;
  22.             prve=prve->next;
  23.             plist2=plist2->next;
  24.         }
  25.     }
  26.     if(plist1)
  27.     {
  28.         prve->next=plist1;
  29.     }
  30.     else
  31.     {
  32.         prve->next=plist2;
  33.     }
  34.     return cur->next;
  35. }

建议：这里建议建立一个头指针，用了头指针避免了很多判断，如果不用头指针，需要判断两个list链表是否为空，头元素到底是从list1开始还是从list2开始

例题6：

图文解析：

 实现代码：

  1. class Partition {
  2. public:
  3.     ListNode* partition(ListNode* pHead, int x) {
  4.          struct ListNode* plist1, *plist2;
  5.        struct ListNode* head1,* head2;
  6.        head1 = plist1 = (struct ListNode*)malloc(sizeof(struct ListNode));
  7.        head2= plist2 = (struct ListNode*)malloc(sizeof(struct ListNode));
  8.         struct ListNode* cur = pHead;
  9.         while(cur)
  10.         {
  11.             if(cur->val<x)
  12.             {
  13.                 head1->next=cur;
  14.                  head1=head1->next;
  15.                 cur=cur->next;
  16.             }
  17.             else
  18.             {
  19.                 head2->next=cur;
  20.                 head2=head2->next;
  21.                 cur=cur->next;
  22.             }
  23.         }
  24.         head2->next=NULL;
  25.         head1->next=plist2->next;
  26.         pHead=plist1->next;
  27.         return pHead;
  28.     }
  29. };

例题7：

链表的回文结构：链接

图文解析：

 实现代码：

  1. //寻找中间点
  2. struct ListNode* middleNode(struct ListNode* head){
  3.     struct ListNode* slow=head;
  4.     struct ListNode* fsat=head;
  5.     while(fsat&&fsat->next)
  6.     {
  7.          fsat=fsat->next->next;
  8.          slow=slow->next;
  9.     }
  10.     return slow;
  11. }
  12. //逆置中间以后
  13. struct ListNode* reverseList(struct ListNode* head){
  14.     struct ListNode* plist=NULL;
  15.     struct ListNode* newnode=head;
  16.    while(newnode)
  17.    {
  18.        struct ListNode* next=newnode->next;
  19.        newnode->next=plist;
  20.        plist=newnode;
  21.  
  22.        newnode=next;
  23.    }
  24.    return plist;
  25. }
  26. //判断是否是回文
  27. class PalindromeList {
  28. public:
  29.     bool chkPalindrome(ListNode* A) {
  30.        ListNode* cur=A;
  31.        ListNode* mid= middleNode(cur);
  32.        ListNode*rmid =reverseList (mid);
  33.         while(rmid)
  34.         {
  35.             if(rmid->val!=A->val)
  36.                 return false;
  37.             A=A->next;
  38.             rmid=rmid->next;
  39.         }
  40.         return true;
  41.     }
  42. };

例题8

输入两个链表，找出它们的第一个公共结点：链接

图文解析：

 实现代码：

  1. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
  2.     int len1=0,len2=0;
  3.     struct ListNode* plist1=headA;
  4.     struct ListNode* plist2=headB;
  5.     while(plist1)
  6.     {
  7.         len1++;
  8.         plist1=plist1->next;
  9.     }
  10.     while(plist2)
  11.     {
  12.         len2++;
  13.         plist2=plist2->next;
  14.     }
  15.     if(plist1!=plist2)
  16.     {
  17.         return NULL;
  18.     }
  19.     int len=abs(len1-len2);
  20.     plist1=headA;
  21.     plist2=headB;
  22.     if(len1>len2)
  23.     {
  24.         while(len--)
  25.         {
  26.             plist1=plist1->next;
  27.         }
  28.     }
  29.     else
  30.     {
  31.         while(len--)
  32.         {
  33.             plist2=plist2->next;
  34.         }
  35.     }
  36.     while(plist1!=plist2)
  37.     {
  38.         plist1=plist1->next;
  39.         plist2=plist2->next;
  40.     }
  41.     return plist1;
  42. }

例题9：

给定一个链表，判断链表中是否有环：例题

【思路】 快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行， 如果链表 带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减 肥。 【扩展问题】

为什么快指针每次走两步，慢指针走一步可以？

假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚 进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。 此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情 况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

快指针一次走3步，走4步， ...n步行吗？

 实现代码：

  1. bool hasCycle(struct ListNode *head) {
  2.     struct ListNode *headA=head;
  3.     struct ListNode *headB=head;
  4.     while(headA&&headA->next)
  5.     {
  6.         headA=headA->next->next;
  7.         headB=headB->next;
  8.        if(headA==headB)
  9.        {
  10.            return true;
  11.        }
  12.       
  13.     }
  14.     return false;
  15.  
  16. }

例题10：

给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL：链接

方法1：

结论 ：让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环 运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。

证明 

 实现代码：

  1. struct ListNode *detectCycle(struct ListNode *head) {
  2.     struct ListNode *fastA=head;
  3.     struct ListNode *slow = head, *fast = head;
  4.     while (fast != NULL&&fast->next != NULL) {
  5.         slow = slow->next;
  6.         fast = fast->next->next;
  7.         if (fast == slow) {
  8.             struct ListNode* ptr = head;
  9.             while (ptr != slow) {
  10.                 ptr = ptr->next;
  11.                 slow = slow->next;
  12.             }
  13.             return ptr;
  14.         }
  15.     }
  16.     return NULL;
  17. }

方法2:

 图文解析：

 代码实现：--自己实现

例题11

给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点 或空结点：链接

图文解析：

 代码实现：

  1. struct Node* copyRandomList(struct Node* head) {
  2. 	struct Node* cur=head;
  3.     struct Node* next=NULL;
  4.     struct Node* copy=NULL;
  5.     //插入copy节点
  6.     while(cur)
  7.     {
  8.         next=cur->next;
  9.        copy=(struct Node*)malloc(sizeof(struct Node));
  10.        copy->val=cur->val;
  11.        cur->next=copy;
  12.        copy->next=next;
  13.  
  14.        cur=next;
  15.     }
  16.     //更新random
  17.     cur=head;
  18.     while(cur)
  19.     {
  20.         copy=cur->next;
  21.         if(cur->random==NULL)
  22.         {
  23.             copy->random=NULL;
  24.         }
  25.         else
  26.         {
  27.             copy->random=cur->random->next;
  28.         }
  29.         cur=cur->next->next;
  30.     }
  31.     //分解与恢复
  32.     struct Node* copyhead=NULL,*copytail=NULL;
  33.     cur=head;
  34.     while(cur)
  35.     {
  36.         copy=cur->next;
  37.         next=copy->next;
  38.         if(copytail==NULL)
  39.         {
  40.             copyhead=copytail=copy;
  41.         }
  42.         else
  43.         {
  44.             copytail->next=copy;
  45.             copytail=copytail->next;
  46.         }
  47.         cur->next=next;
  48.         cur=next;
  49.     }
  50.     return copyhead;
  51. }

 其他链接：力扣             牛客网

 双向链表

接口的实现

List.h

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

List.c

  1. #include "List.h"
  2.  
  3.  
  4. // 创建返回链表的头结点.
  5. ListNode* ListCreate()
  6. {
  7. 	ListNode* gurad = (ListNode*)malloc(sizeof(ListNode));
  8. 	if (gurad == NULL)
  9. 	{
  10. 		perror("malloc fail");
  11. 		exit(-1);
  12. 	}
  13. 	gurad->_next=gurad ;
  14. 	gurad->_prev=gurad;
  15.  
  16. 	return gurad;
  17. }
  18.  
  19. // 双向链表销毁
  20. void ListDestory(ListNode* pHead)
  21. {
  22. 	assert(pHead);
  23. 	ListNode* cur = pHead->_next;
  24. 	while (cur!=pHead)
  25. 	{
  26. 		ListNode* next = cur->_next;
  27. 	    
  28. 		free(cur);
  29. 		
  30. 		cur = next;
  31. 	}
  32. }
  33.  
  34. // 双向链表打印
  35. void ListPrint(ListNode* pHead)
  36. {
  37. 	assert(pHead);
  38. 	ListNode* cur = pHead->_next;
  39. 	while (cur != pHead)
  40. 	{
  41. 		ListNode* next = cur->_next;
  42. 		printf("%d<==>", cur->_data);
  43. 		cur = cur->_next;
  44. 	}
  45. 	printf("\n");
  46. }
  47.  
  48. //创造新节点
  49. ListNode* BuyListNode(LTDataType x)
  50. {
  51. 	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
  52. 	if (newnode == NULL)
  53. 	{
  54. 		perror("malloc fail");
  55. 		exit(-1);
  56. 	}
  57. 	newnode->_data = x;
  58. 	newnode->_next = NULL;
  59. 	newnode->_prev = NULL;
  60.  
  61. 	return newnode;
  62. }
  63.  
  64. // 双向链表尾插
  65. void ListPushBack(ListNode* pHead, LTDataType x)
  66. {
  67. 	assert(pHead);
  68. 	ListNode* cur = BuyListNode(x);
  69. 	ListNode* prve = pHead->_prev;
  70. 	prve->_next = cur;
  71. 	cur->_prev = prve;
  72. 	cur->_next = pHead;
  73. 	pHead->_prev = cur;
  74.  
  75. 	//ListInsert(pHead, x);
  76. 	
  77. }
  78.  
  79. // 双向链表尾删
  80. void ListPopBack(ListNode* pHead)
  81. {
  82. 	assert(pHead);
  83. 	ListNode* prve1 = pHead->_prev;
  84. 	ListNode* prve2 = prve1->_prev;
  85. 	prve2->_next = pHead;
  86. 	pHead->_prev = prve2;
  87. 	free(prve1);
  88. 	prve1 = NULL;
  89.  
  90. 	//ListErase(pHead->_prev);
  91. }
  92.  
  93. // 双向链表头插
  94. void ListPushFront(ListNode* pHead, LTDataType x)
  95. {
  96. 	assert(pHead);
  97. 	ListNode* cur = BuyListNode(x);
  98. 	ListNode* next = pHead->_next;
  99. 	
  100. 	pHead->_next = cur;
  101. 	cur->_prev = pHead;
  102. 	next->_prev = cur;
  103. 	cur->_next = next;
  104.  
  105. 	//ListInsert(pHead->_next, x);
  106. }
  107.  
  108. // 双向链表头删
  109. void ListPopFront(ListNode* pHead)
  110. {
  111. 	assert(pHead);
  112. 	ListNode* next1 = pHead->_next;
  113. 	ListNode* next2 = next1->_next;
  114. 	pHead->_next = next2;
  115. 	next2->_prev = pHead;
  116. 	free(next1);
  117. 	next1 = NULL;
  118.  
  119. 	//ListErase(pHead->_next);
  120. }
  121.  
  122. // 双向链表查找
  123. ListNode* ListFind(ListNode* pHead, LTDataType x)
  124. {
  125. 	assert(pHead);
  126. 	ListNode* cur = pHead->_next;
  127. 	while (cur != pHead)
  128. 	{
  129. 		if (cur->_data == x)
  130. 			return cur;
  131. 		cur = cur->_next;
  132. 	}
  133. 	return NULL;
  134. }
  135.  
  136. // 双向链表在pos的前面进行插入
  137. void ListInsert(ListNode* pos, LTDataType x)
  138. {
  139. 	assert(pos);
  140. 	ListNode* cur = BuyListNode(x);
  141. 	ListNode* prev = pos->_prev;
  142.  
  143. 	prev->_next = cur;
  144. 	cur->_prev = prev;
  145. 	pos->_prev = cur;
  146. 	cur->_next = pos;
  147. }
  148.  
  149. // 双向链表删除pos位置的节点
  150. void ListErase(ListNode* pos)
  151. {
  152. 	assert(pos);
  153. 	ListNode* prev = pos->_prev;
  154.     ListNode* next = pos->_next;
  155. 	next->_prev = prev;
  156. 	prev->_next = next;
  157. 	free(pos);
  158. }

Test.c

  1. #include "List.h"
  2.  
  3. //尾插-打印-尾删-打印
  4. void Test1()
  5. {
  6. 	ListNode* plist = ListCreate();
  7. 	ListPushBack(plist,4);
  8. 	ListPushBack(plist, 5);
  9. 	ListPushBack(plist, 8); 
  10. 	ListPushBack(plist, 9);
  11. 	ListPrint(plist);
  12. 	ListPopBack(plist);
  13. 	ListPrint(plist);
  14. }
  15. //头查-打印-头删-打印-查找
  16. void Test2()
  17. {
  18. 	ListNode* plist = ListCreate();
  19. 	ListPushFront(plist, 1);
  20. 	ListPushFront(plist, 2);
  21. 	ListPushFront(plist, 3);
  22. 	ListPushFront(plist, 4);
  23. 	ListPrint(plist);
  24. 	ListPopFront(plist);
  25. 	ListPrint(plist);
  26. 	ListNode*ret = ListFind(plist, 2);
  27. 	if (ret != NULL)
  28. 		printf("yes\n");
  29. 	else
  30. 		printf("no\n");
  31. }
  32. //pos的前面插入-打印-pos的前面删除-打印
  33. void Test3()
  34. {
  35. 	ListNode* plist = ListCreate();
  36. 	ListPushFront(plist, 1);
  37. 	ListPushFront(plist, 2);
  38. 	ListPushFront(plist, 3);
  39. 	ListPushFront(plist, 4);
  40. 	ListInsert(plist->_next, 5);
  41. 	ListPrint(plist);
  42. 	ListErase(plist->_next);
  43. 	ListPrint(plist);
  44. }
  45.  
  46. int main()
  47. {
  48. 	Test1();
  49. 	Test2();
  50. 	Test3();
  51.  
  52. 	return 0;
  53. }

顺序表和链表的区别

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

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

顺序表与链表相比：顺序表CPU高速缓存命中率更高

CPU高速缓存：在寄存器与主存之间的缓存，寄存器访问速度是非常快的，但主存访问速度较慢，更不上寄存器的访问速度，所以不可能让寄存器一直等主存，为了提高效率我们就需要高速缓存（三级缓存）来将主存的数据先加载到缓存中。

CPU指向指如何访问内存：先看数据在不在三级缓存，在（命中），直接访问。不在（不命中），先加载到缓存，在访问。加载进缓存时不会一次加载一个数据，是将数据周边的数据一起加载（一段数据）--加载多少取决于硬件，为了更高效的加载

如何理解   顺序表CPU高速缓存命中率更高：因为顺序表的结构关系，它的数据具有连续性的，当我们CPU访问的时候，主存加载到缓存时是直接将一段数据直接加载，正因为它是连续寄存器寻找有用数据时就更加容易命中（更加容易找到数据），带来的好处就是效率的提高。与之相反链表的数据不具有连续性，当寄存器访问的时候该数据周围的地址不连续，访问一些没有用的数据，缓存的内存也是有限，所以也就浪费了缓存的内存。

如何知道自己的电脑的三级缓存：打开任务管理器，选择性能

 与程序员相关的CPU缓存知识

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

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

  

闽ICP备14008679号