• [数据结构初阶]顺序表

    目录

    线性表

    顺序表

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

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

    接口实现 

    SeqList.h

    SeqList.c

     Test.c

     数组相关面试题

     顺序表的问题及思考

    线性表

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

    顺序表

             顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
            顺序表相较于链表有一个要求，数据必须从第一个位置连续存储的！
            顺序表一般可以分为：

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

    1. #pragma once
    2. #define N 100
    3. typedef int SLDataType;
    4. struct SeqList
    5. {
    6. 	SLDataType a[N];
    7. 	int size;
    8. };

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

    1. #pragma once
    2. typedef int SLDataType;
    3. struct SeqList
    4. {
    5. 	SLDataType* a;
    6. 	int size;
    7. 	int capacity;//容量
    8. };

    接口实现 

    SeqList.h

    1. #pragma once
    2. typedef int SLDataType;
    3. typedef struct SeqList
    4. {
    5. 	SLDataType* a;
    6. 	int size;
    7. 	int capacity;//容量
    8. }SL;
    9. void SLInit(SL* ps);
    10.  
    11. void SLDestory(SL* ps);
    12.  
    13. void SLCheckCapacity(SL* ps);
    14.  
    15.  
    16. void SLPushBack(SL* ps, SLDataType x);
    17. void SLpopBack(SL* ps);
    18. void SLPushFront(SL* ps, SLDataType x);
    19. void SLpopFront(SL* ps);
    20.  
    21.  
    22. void SLInsert(SL* ps, int pos, SLDataType x);
    23. void SLErase(SL* ps, int pos);
    24.  
    25. int SLFind(SL* ps, SLDataType x);
    26. void SLModify(SL* ps, int pos,int x);
    27.  
    28.  
    29. void SLPrint(SL* ps);

    SeqList.c

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

     Test.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3. #include
    4. #include
    5. void menu()
    6. {
    7. 	printf("*****************************************************************\n");
    8. 	printf("1、查找      2、修改\n");
    9. 	printf("3、尾插      4、头插\n");
    10. 	printf("5、任意删    6、任意插\n");
    11. 	printf("7、尾删      8、头删\n");
    12. 	printf("9、打印     -1、退出\n");
    13.  
    14. 	printf("*****************************************************************\n");
    15.  
    16. }
    17.  
    18.  
    19. int main()
    20. {
    21. 	SL s1;
    22. 	SLInit(&s1);
    23. 	int option ;
    24. 	do {
    25. 		menu();
    26. 		if (scanf("%d", &option) == EOF)
    27. 		{
    28. 			printf("scanf输入错误\n");
    29. 			break;
    30. 		}
    31. 		
    32. 		int val, pos;
    33. 		switch (option)
    34. 		{
    35. 		case -1:
    36. 			printf("退出\n");
    37. 			exit(0);
    38. 			break;
    39. 		case 1:
    40. 			printf("请输入你要查找的值\n");
    41. 			int x;
    42. 			scanf("%d", &x);
    43. 			int pos = SLFind(&s1, x);
    44. 			printf("在%d位置处\n",pos);
    45. 			break;
    46. 		case 2: {
    47. 			int y;
    48. 			int z;
    49. 			printf("请输入你要修改的值和修改后的值\n");
    50. 			scanf("%d%d", &y, &z);
    51. 			pos = SLFind(&s1, y);
    52. 			if (pos != -1)
    53. 			{
    54. 				SLModify(&s1, pos, z);
    55. 			}
    56. 			else
    57. 			{
    58. 				printf("没找到：%d\n", y);
    59. 			}
    60. 			break;
    61. 		}
    62. 		case 3:
    63. 			printf("请连续输入你要尾插的数据，以0结束：\n");
    64. 			scanf("%d", &val);
    65. 			while (val!=0)
    66. 			{
    67. 				SLPushBack(&s1, val);
    68. 				scanf("%d", &val);
    69. 			}
    70. 			break;
    71. 		case 4:
    72. 			printf("请连续输入你要头插的数据，以0结束：\n");
    73. 			scanf("%d", &val);
    74. 			while (val != 0)
    75. 			{
    76. 				
    77. 				SLPushFront(&s1, val);
    78. 				scanf("%d", &val);
    79. 			}
    80. 			break;
    81. 		case 5:
    82. 		{
    83. 			int y;
    84. 			printf("请输入你要删除的位置\n");
    85. 			scanf("%d", &y);
    86. 			SLErase(&s1, y);
    87. 			break;
    88. 		}
    89. 		case 6:
    90. 		{
    91. 			int y;
    92. 			int x;
    93. 			printf("请输入你要插入的位置,和插入的值\n");
    94. 			scanf("%d%d", &y, &x);
    95. 			SLInsert(&s1, y, x);
    96. 			break;
    97. 		}
    98. 		case 7:
    99. 			SLpopBack(&s1);
    100. 			break;
    101. 		case 8:
    102. 			SLpopFront(&s1);
    103. 			break;
    104.  
    105. 		case 9:
    106. 			SLPrint(&s1);
    107. 			break;
    108. 		default:
    109. 			exit(-1);
    110. 			break;
    111. 		}
    112. 	} while (option != -1);
    113. 	SLDestory(&s1);
    114. 		return 0;
    115. }

     

     数组相关面试题

    1、分析以下函数的空间复杂度（   ）

            A.O(n)

            B.O(n^2)

            C.O( 1 )

            D.O(nlogn)

    1. int** fun(int n) {
    2.     int ** s = (int **)malloc(n * sizeof(int *));
    3.     while(n--)
    4.       s[n] = (int *)malloc(n * sizeof(int));
    5.     return s;
    6.   }

      答案解析：

    此处开辟的是一个二维数组，数组有n行，每行分别有1,2,3,...n列，所以是n(n + 1)/2个元素空间，空间复杂度为n^2

    2、如果一个函数的内部中只定义了一个二维数组a[3][6]，请问这个函数的空间复杂度为（   ）

            A.O(n)

            B.O(n^2)

            C.O( 1 )

            D.O(m*n)

     答案解析：

    函数内部数组的大小是固定的，不论函数运行多少次，所需空间都是固定大小的，因此空间复杂度为O(1)

    27. 移除元素 - 力扣（LeetCode）

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

    26. 删除有序数组中的重复项 - 力扣（LeetCode）

    1. int removeDuplicates(int* nums, int numsSize){
    2.     int left = 0;
    3.     int right = 0;
    4.     while(right
    5.     {
    6.         if(nums[left] == nums[right])
    7.         {
    8.             right++;
    9.         }else{
    10.             nums[++left]=nums[right++];
    11.         }
    12.     }
    13.     return ++left;
    14. }

    88. 合并两个有序数组 - 力扣（LeetCode）

    1. void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    2.     int num1right = m - 1;
    3.     int num2right = n - 1;
    4.     int a = m + n - 1;
    5.     while(num1right >= 0 || num2right >= 0)
    6.     {
    7.         if(num2right < 0)
    8.         {
    9.             nums1[a--] = nums1[num1right--];
    10.         }
    11.         else if(num1right < 0)
    12.         {
    13.             nums1[a--] = nums2[num2right--];
    14.         }
    15.         else if(nums1[num1right] >= nums2[num2right])
    16.         {
    17.             nums1[a--] = nums1[num1right--];
    18.         }
    19.         else{
    20.             nums1[a--] = nums2[num2right--];
    21.         }
    22.     } 
    23. }

     顺序表的问题及思考

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

  • 相关阅读:
    STM32个人笔记-FatFs文件系统
    从底层结构开始学习FPGA（8）----Block RAM（BRAM，块RAM）
    【面试题】js实现将excel表格copy到页面
    Java覆盖与重载
    【Arduino+ESP32专题】Modbus RTU简介
    【吴恩达机器学习-笔记整理】异常检测与高斯分布
    【Java并发入门】01 并发编程Bug的源头
    芒格-“永远不要有受害者心态”
    吃透Redis（七）：网络框架篇-redis 6.0 IO多线程原子性保证
    radiantq：jQuery Gantt Package--好使的HTML5甘特图
  • 原文地址：https://blog.csdn.net/qq_51581716/article/details/127575887