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

数据结构 - 顺序表基本操作_顺序表的基本操作

作者：知新_RL | 2024-04-26 03:41:22

赞

踩

顺序表的基本操作

目录

前言：

接口实现

顺序表基本操作

顺序表初始化（SeqListInit）

检查空间进行增容（SeqListCheckCapacity）

顺序表打印（SeqListPrint）

 销毁（SeqListDestroy）

1、尾插（SeqListPushBack）

2、尾删（SeqListPopBack）

3、头插（SeqListPushFront）

4、头删（SeqListPopFront）

5、查找位置（SeqListFind）

6、在指定的下标位置插入（SeqListInsert）

7、删除指定位置的数据（SeqListErase） 

 代码封装优化

   完整代码：

SeqList.h：头文件以及函数申明

SeqList.c：接口实现

OJ练习：

前言：

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

 顺序表

顺序表是用一段 物理地址连续 的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组
上完成数据的增删查改。
顺序表一般可以分为：
1. 静态顺序表：使用定长数组存储元素 。 
  1. ​#define N 7
  2. typedef int SLDataType
  3.  
  4. typedef struct SeqList {
  5.     SLDataType array[N];  //定长数组
  6.     size_t size;          //有效数据的个数
  7. } SeqList;

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

  1. typedef int SLDataType
  2.  
  3. typedef struct SeqList {
  4.     SLDataType* array;    //指向动态开辟的数组
  5.     size_t size;          //有效数据的个数
  6.     size_t capacity;      //容量空间的大小
  7. } SeqList;

接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致 N 定大了，空间开多了浪 费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实 现动态顺序表。
为了方便后续修改数据类型，我们可以使用 typedef 定义一个新的数据类型，这里我们把它取名为  SLDataType
为了让定义的结构体使用时更方便，我们同样可以使用 typedef 将其定义为  SeqList（此时 SeqList = struct SeqList，后续在使用时可以更加方便）。 
  1. typedef int SLDataType;
  2. // 顺序表的动态存储
  3. typedef struct SeqList
  4. {
  5.  SLDataType* array; // 指向动态开辟的数组
  6.  size_t size ; // 有效数据个数
  7.  size_t capicity ; // 容量空间的大小
  8. }SeqList;

 顺序表的所以基本操作：

  1. // 基本增删查改接口
  2. // 顺序表初始化
  3. void SeqListInit(SeqList* psl, size_t capacity);
  4. // 检查空间，如果满了，进行增容
  5. void SeqListCheckCapacity(SeqList* psl);
  6. // 顺序表尾插
  7. void SeqListPushBack(SeqList* psl, SLDataType x);
  8. // 顺序表尾删
  9. void SeqListPopBack(SeqList* psl);
  10. // 顺序表头插
  11. void SeqListPushFront(SeqList* psl, SLDataType x);
  12. // 顺序表头删
  13. void SeqListPopFront(SeqList* psl);
  14. // 顺序表查找
  15. int SeqListFind(SeqList* psl, SLDataType x); 
  16. // 顺序表在pos位置插入x
  17. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
  18. // 顺序表删除pos位置的值
  19. void SeqListErase(SeqList* psl, size_t pos);
  20. // 顺序表销毁
  21. void SeqListDestory(SeqList* psl);
  22. // 顺序表打印
  23. void SeqListPrint(SeqList* psl);

顺序表基本操作

前情提要：assert()函数

#include "assert.h" 
void assert( int expression );

assert 的作用是现计算表达式 expression ，如果其值为假（即为0）或者为NULL，那么将直接报错。（断言(assert)的用法 | 菜鸟教程 (runoob.com)）

下文中 assert(psl);用于防止错误并方便Debug，因为assert会精准的报出错误位置；

顺序表初始化（SeqListInit）

  1. void SeqListInit(SeqList* psl)
  2. {
  3. 	assert(psl);
  4.  
  5. 	psl->a = NULL;
  6. 	psl->size = 0;        //有效数据个数
  7. 	psl->capacity = 0;        //数组实际能存数据的空间容量是多大
  8. }

检查空间进行增容（SeqListCheckCapacity）

size_t等价于unsigned int

  1. void SeqListCheckCapacity(SeqList* psl)
  2. {
  3. 	assert(psl);
  4.  
  5. 	// 如果满了，我们要扩容
  6. 	if (psl->size == psl->capacity)
  7. 	{
  8. 		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  9. 		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
  10. 		if (tmp == NULL)
  11. 		{
  12. 			printf("realloc fail\n");//扩容失败，直接退出
  13. 			exit(-1);
  14. 		}
  15. 		else
  16. 		{
  17. 			psl->a = tmp;
  18. 			psl->capacity = newCapacity;
  19. 		}
  20. 	}
  21. }
  • 这里巧妙地使用三目操作符：int new_capacity = psl->capacity == 0 ? 4 : psl->capacity*2 ， 如果 capacity 为 0 （第一次使用大小是0），就把4赋值给它；如果不为0，就把 capacity 的值翻一倍（x2）。
  • 你想一次扩容多少就扩容多少，乘2只是一个比较折中的扩容容量方案。 

顺序表打印（SeqListPrint）

  1. void SeqListPrint(SeqList* psl)
  2. {
  3. 	assert(psl);
  4.  
  5. 	for (int i = 0; i < psl->size; ++i)
  6. 	{
  7. 		printf("%d ", psl->a[i]);
  8. 	}
  9. 	printf("\n");
  10. }
因为是单纯的打印，所以只需要把顺序表传过去就行。

 销毁（SeqListDestroy）

因为是动态开辟的，所以如果空间不用我们就需要销毁掉。如果不销毁会存在内存泄漏的风险，所以与之对应的我们写一个销毁的接口函数。

  1. void SeqListDestroy(SeqList* psl)
  2. {
  3. 	assert(psl);
  4. 	free(psl->a);
  5. 	psl->a = NULL;
  6. 	psl->capacity = psl->size = 0;
  7. }

1、尾插（SeqListPushBack）

  1. void SeqListPushBack(SeqList* psl, SLDataType x)
  2. {
  3. 	assert(psl);
  4.  
  5. 	SeqListCheckCapacity(psl);//查看是否要扩容
  6.  
  7. 	psl->a[psl->size] = x;
  8. 	psl->size++;
  9. }

2、尾删（SeqListPopBack）

  1. void SeqListPopBack(SeqList* psl)
  2. {
  3. 	assert(psl);
  4.  
  5. 	//psl->a[psl->size - 1] = 0;
  6. 	if (psl->size > 0)
  7. 	{
  8. 		psl->size--;
  9. 	}
  10. 	
  11. }

对于尾删，其实只要让最后一个元素访问不到就行，即size--即可。

3、头插（SeqListPushFront）

  1. void SeqListPushFront(SeqList* psl, SLDataType x)
  2. {
  3. 	assert(psl);
  4.  
  5. 	SeqListCheckCapacity(psl);
  6.  
  7. 	// 挪动数据，腾出头部空间
  8. 	int end = psl->size - 1;
  9. 	while (end >= 0)
  10. 	{
  11. 		psl->a[end + 1] = psl->a[end];
  12. 		--end;
  13. 	}
  14. 	psl->a[0] = x;
  15. 	psl->size++;
  16. }

4、头删（SeqListPopFront）

  1. void SeqListPopFront(SeqList* psl)
  2. {
  3. 	assert(psl);
  4.  
  5. 	// 挪动数据覆盖删除
  6. 	if (psl->size > 0)
  7. 	{
  8. 		int begin = 1;
  9. 		while (begin < psl->size)
  10. 		{
  11. 			psl->a[begin - 1] = psl->a[begin];
  12. 			++begin;
  13. 		}
  14. 		--psl->size;    //相当于让指针指向第二个元素
  15. 	}
  16. }

5、查找位置（SeqListFind）

  1. int SeqListFind(SeqList* psl, SLDataType x)
  2. {
  3. 	assert(psl);
  4.  
  5. 	for (int i = 0; i < psl->size; ++i)
  6. 	{
  7. 		if (psl->a[i] == x)
  8. 		{
  9. 			return i;
  10. 		}
  11. 	}
  12. 	return -1;
  13. }

 6、在指定的下标位置插入（SeqListInsert）

  1. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
  2. {
  3. 	// 暴力检查
  4. 	assert(psl);
  5.  
  6. 	// 温和检查
  7. 	if (pos > psl->size)
  8. 	{
  9. 		printf("pos 越界：%d\n", pos);
  10. 		return;
  11. 	}
  12. 	
  13. 	SeqListCheckCapacity(psl);
  14.  
  15. 	size_t end = psl->size;
  16. 	while (end > pos)
  17. 	{
  18. 		psl->a[end] = psl->a[end - 1];
  19. 		--end;
  20. 	}
  21.  
  22. 	psl->a[pos] = x;
  23. 	psl->size++;
  24. }

 7、删除指定位置的数据（SeqListErase） 

  1. void SeqListErase(SeqList* psl, size_t pos)
  2. {
  3. 	assert(psl);
  4. 	assert(pos < psl->size);
  5.  
  6. 	size_t begin = pos + 1;
  7. 	while (begin < psl->size)
  8. 	{
  9. 		psl->a[begin - 1] = psl->a[begin];
  10. 		++begin;
  11. 	}
  12. 	psl->size--;
  13. }

此时，我们发现代码有许多共同点；比如头插、尾插不就是SeqListInsert在下标为0和下标为size（）时插入吗？同理：头删、尾删也可以用SeqListErase代替

 代码封装优化

  1. void SeqListPushBack(SeqList* psl, SLDataType x)
  2. {
  3. 	assert(psl);
  4.  
  5. 	SeqListInsert(psl, psl->size, x);
  6. }
  7.  
  8. void SeqListPopBack(SeqList* psl)
  9. {
  10. 	assert(psl);
  11.  
  12. 	SeqListErase(psl, psl->size - 1);
  13. }
  14.  
  15. void SeqListPushFront(SeqList* psl, SLDataType x)
  16. {
  17. 	assert(psl);
  18.  
  19. 	SeqListInsert(psl, 0, x);
  20. }
  21.  
  22. void SeqListPopFront(SeqList* psl)
  23. {
  24. 	assert(psl);
  25.  
  26. 	SeqListErase(psl, 0);
  27. }

完整代码：

SeqList.h：头文件以及函数申明

  1. #pragma once//为了避免同一个头文件被包含多次我们可以使用 #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h>
  5.  
  6. // 要求：存储的数据从0开始，依次连续存储
  7. // 静态的顺序表
  8. // 问题：开小了，不够用。开大了，存在浪费。
  9. //#define N 10000
  10. //struct SeqList
  11. //{
  12. //	int a[N];
  13. //	int size; // 记录存储了多少个数据
  14. //};
  15.  
  16. typedef int SLDataType;
  17.  
  18. // 动态的顺序表
  19. typedef struct SeqList
  20. {
  21. 	SLDataType* a;
  22. 	int size;     // 存储数据个数
  23. 	int capacity; // 存储空间大小
  24. }SL, SeqList;
  25.  
  26. void SeqListPrint(SeqList* psl);
  27.  
  28. //void SLInit(SeqList* psl);
  29. void SeqListInit(SeqList* psl);
  30. void SeqListDestroy(SeqList* psl);
  31.  
  32. void SeqListCheckCapacity(SeqList* psl);
  33.  
  34. // 时间复杂度是O(1)
  35. void SeqListPushBack(SeqList* psl, SLDataType x);
  36. void SeqListPopBack(SeqList* psl);
  37.  
  38. // 时间复杂度是O(N)
  39. void SeqListPushFront(SeqList* psl, SLDataType x);
  40. void SeqListPopFront(SeqList* psl);
  41.  
  42. // 在pos位置插入x
  43. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
  44. // 删除pos位置的数据
  45. void SeqListErase(SeqList* psl, size_t pos);
  46.  
  47. // 顺序表查找
  48. int SeqListFind(SeqList* psl, SLDataType x);

SeqList.c：接口实现

  1. #include "SeqList.h"
  2.  
  3. void SeqListPrint(SeqList* psl)
  4. {
  5. 	assert(psl);
  6.  
  7. 	for (int i = 0; i < psl->size; ++i)
  8. 	{
  9. 		printf("%d ", psl->a[i]);
  10. 	}
  11. 	printf("\n");
  12. }
  13.  
  14. void SeqListInit(SeqList* psl)
  15. {
  16. 	assert(psl);
  17.  
  18. 	psl->a = NULL;
  19. 	psl->size = 0;
  20. 	psl->capacity = 0;
  21. }
  22.  
  23. void SeqListDestroy(SeqList* psl)
  24. {
  25. 	assert(psl);
  26. 	free(psl->a);
  27. 	psl->a = NULL;
  28. 	psl->capacity = psl->size = 0;
  29. }
  30.  
  31. void SeqListCheckCapacity(SeqList* psl)
  32. {
  33. 	assert(psl);
  34.  
  35. 	// 如果满了，我们要扩容
  36. 	if (psl->size == psl->capacity)
  37. 	{
  38. 		size_t newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
  39. 		SLDataType* tmp = realloc(psl->a, sizeof(SLDataType) * newCapacity);
  40. 		if (tmp == NULL)
  41. 		{
  42. 			printf("realloc fail\n");
  43. 			exit(-1);
  44. 		}
  45. 		else
  46. 		{
  47. 			psl->a = tmp;
  48. 			psl->capacity = newCapacity;
  49. 		}
  50. 	}
  51. }
  52.  
  53. void SeqListPushBack(SeqList* psl, SLDataType x)
  54. {
  55. 	assert(psl);
  56.  
  57. 	SeqListInsert(psl, psl->size, x);
  58. }
  59.  
  60. void SeqListPopBack(SeqList* psl)
  61. {
  62. 	assert(psl);
  63.  
  64. 	SeqListErase(psl, psl->size - 1);
  65. }
  66.  
  67. void SeqListPushFront(SeqList* psl, SLDataType x)
  68. {
  69. 	assert(psl);
  70.  
  71. 	SeqListInsert(psl, 0, x);
  72. }
  73.  
  74. void SeqListPopFront(SeqList* psl)
  75. {
  76. 	assert(psl);
  77.  
  78. 	SeqListErase(psl, 0);
  79. }
  80.  
  81. // 在pos位置插入x
  82. void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
  83. {
  84. 	// 暴力检查
  85. 	assert(psl);
  86.  
  87. 	// 温和检查
  88. 	if (pos > psl->size)
  89. 	{
  90. 		printf("pos 越界：%d\n", pos);
  91. 		return;
  92. 		//exit(-1);
  93. 	}
  94. 	// 暴力检查
  95. 	//assert(pos <= psl->size);
  96.  
  97. 	SeqListCheckCapacity(psl);
  98.  
  99. 	size_t end = psl->size;
  100. 	while (end > pos)
  101. 	{
  102. 		psl->a[end] = psl->a[end - 1];
  103. 		--end;
  104. 	}
  105.  
  106. 	psl->a[pos] = x;
  107. 	psl->size++;
  108. }
  109.  
  110. // 删除pos位置的数据
  111. void SeqListErase(SeqList* psl, size_t pos)
  112. {
  113. 	assert(psl);
  114. 	assert(pos < psl->size);
  115.  
  116. 	size_t begin = pos + 1;
  117. 	while (begin < psl->size)
  118. 	{
  119. 		psl->a[begin - 1] = psl->a[begin];
  120. 		++begin;
  121. 	}
  122.  
  123. 	psl->size--;
  124. }
  125.  
  126. int SeqListFind(SeqList* psl, SLDataType x)
  127. {
  128. 	assert(psl);
  129.  
  130. 	for (int i = 0; i < psl->size; ++i)
  131. 	{
  132. 		if (psl->a[i] == x)
  133. 		{
  134. 			return i;
  135. 		}
  136. 	}
  137.  
  138. 	return -1;
  139. }

笔记篇：参考资料->比特科技

OJ练习：

链表的结构图：

203. 移除链表元素

 

 思路：

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     struct ListNode *next;
  6.  * };
  7.  */
  8.  
  9. struct ListNode* removeElements(struct ListNode* head, int val){
  10.     struct ListNode*prve=NULL;
  11.     struct ListNode*cur=head;
  12.  
  13.     while(cur){    //遍历整个数组
  14.         if(cur->val!=val){    //如果不是，则共同前进一步
  15.             prve=cur;
  16.             cur=cur->next;
  17.         }
  18.         else{    //如果是，则如图所示
  19.             struct ListNode*next=cur->next;
  20.             if(prve==NULL){    //头删情况，因为头删时没有prve->next
  21.                 free(cur);    
  22.                 head=next;
  23.                 cur=head;
  24.             }
  25.             else{
  26.                 free(cur);
  27.                 prve->next=next;
  28.                 cur=next;
  29.             }
  30.         }
  31.     }
  32.     return head;
  33. }

206. 反转链表

思路：直接把链表的指向反转即可

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         struct ListNode*newHead=NULL;
  15.         struct ListNode*cur=head;
  16.  
  17.         while(cur){
  18.             struct ListNode*next=cur->next;
  19.  
  20.             cur->next=newHead;    //将“箭头”反转
  21.             newHead=cur;
  22.             cur=next;
  23.         }
  24.         return newHead;
  25.     }
  26. };
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* reverseList(ListNode* head) {
  14.         if(head==NULL)
  15.         return NULL;
  16.         struct ListNode*n1,*n2,*n3;
  17.         n1=NULL;
  18.         n2=head;
  19.         n3=n2->next;
  20.  
  21.         while(n2){
  22.             n2->next=n1;
  23.             n1=n2;
  24.             n2=n3;
  25.             if(n3)    //作图可知，最后一个n3=NULL，无n3->next
  26.                 n3=n3->next;
  27.         }
  28.         return n1;
  29.     }
  30. };

C++写法

方法一：迭代

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         ListNode* p=nullptr;
  5.         ListNode* curr=head;
  6.         while(curr)
  7.         {
  8.             ListNode* next=curr->next;
  9.             curr->next=p;
  10.             p=curr;
  11.             curr=next;
  12.         }
  13.         return p;
  14.     }
  15. };

方法二：递归

  • 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 retret .
  • 此后，每次函数在返回的过程中，让当前结点的下一个结点的 nextnext 指针指向当前节点。
  • 同时让当前结点的 nextnext 指针指向 NULLNULL ，从而实现从链表尾部开始的局部反转
  • 当递归函数全部出栈后，链表反转完成。

 

 

  1. class Solution {
  2. public:
  3.     ListNode* reverseList(ListNode* head) {
  4.         if(!head||!head->next)
  5.             return head;
  6.         ListNode* ret=reverseList(head->next);
  7.         head->next->next=head;
  8.         head->next=NULL;
  9.         return ret;
  10.     }
  11. };

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

经典快慢指针！！ 

  1. class Solution {
  2. public:
  3.     int removeDuplicates(vector<int>& nums) {
  4.         int n=nums.size();
  5.         int slow=1,fast=1;
  6.         while(fast<n)
  7.         {
  8.             if(nums[fast]!=nums[fast-1])
  9.             {
  10.                 nums[slow++]=nums[fast];
  11.             }
  12.             fast++;
  13.         }
  14.         return slow;
  15.     }
  16. };

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

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

  

闽ICP备14008679号