当前位置：首页 > news >正文

【数据结构入门】顺序表

news 2025/8/2 10:34:26

1.线性表

2.顺序表

2.1 动态顺序表的实现

思路：

代码：

2.2 顺序表的缺陷与优势

3.题目

3.1移除元素

分析：

代码：

1.线性表

线性表在逻辑上是线性结构，是连续的一条直线，但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式的形式存储。常见的线性表：顺序表、链表、栈、队列、字符串......

数据结构分为物理结构（内存中如何存）和逻辑结构（想象出来的），那么线性表的物理结构其实就是数组（内存连续存储）和链表（内存不一定连续存储）。所以线性表在逻辑上是连续的，物理上不一定连续。

2.顺序表

可以粗浅的理解为是一个数组，即在内存中是连续存储的。在这个数组上完成数据的增删改查。

顺序表一般可以分为：

1.静态顺序表：定长数组来存储数据；

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

2.1 动态顺序表的实现

动态顺序表和静态顺序表唯一的区别就是存储空间是否可变，前者在堆处开辟空间，可以使用malloc、relloc函数进行实现，后者只能在栈上预先开辟好空间，存储空间大小不能改变。

思路：

实现头插尾插、头删尾删、指定下标删除、插入、二分查找指定元素的下标、排序。

①实现插入操作的时候，需要判断是否要扩容。

②实现删除操作的时候，需要判断实际元素的个数是否为0。

③指定位置删除的下标范围是：0-size-1。

④指定位置插入的下标范围是：0-size。

⑤二分查找的前提是有序，需要先排序。

⑥排序使用qsort的时候需要注意，比较函数是升序还是降序。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include"SeqList.h"// 遍历顺序表
void printSeqList(SeqList* list)
{for (int i = 0; i < list->size; i++){printf("%d ", list->data[i]);}printf("\n");
}// 扩容
void expend_space(SeqList* list)
{list->capacity *= 2;dataType* tmp = (dataType*)realloc(list->data, list->capacity * sizeof(dataType));if (tmp == NULL){perror("申请内存失败");exit(-1); // 直接退出程序}list->data = tmp;
}// 初始化顺序表
void InitSeqList(SeqList* list)
{assert(list);list->data = (dataType*)malloc(sizeof(dataType) * 4);if (list->data == NULL){perror("申请内存失败");exit(-1); // 直接退出程序}list->capacity = 4;list->size = 0;
}// 尾插
void push_back(SeqList* list, dataType data)
{assert(list);// 扩容if (list->size == list->capacity){expend_space(list);}list->data[list->size] = data;list->size++;
}// 尾删
void pop_back(SeqList* list)
{assert(list);if (list->size == 0){printf("空表无法删除！");exit(-1);}list->size--;
}// 头插
void push_front(SeqList* list, dataType data)
{assert(list);// 容量够才能头插if (list->capacity == list->size){expend_space(list);}// 所有的数据后移一位// 从最后一个元素开始后移（逻辑更直观）for (int i = list->size; i > 0; i--) {list->data[i] = list->data[i - 1];}list->data[0] = data;list->size++;
}// 头删
void pop_front(SeqList* list)
{assert(list);if (list->size == 0){printf("空表无法删除！");exit(-1);}// 从第二个元素开始，每一个元素向前移动一位for (int i = 1; i < list->size; i++){list->data[i - 1] = list->data[i];}list->size--;
}// 指定插入
void insert_position(SeqList* list, int pos, dataType data)
{assert(list);assert(pos >= 0 && pos <= list->size);// 容量够才能插入if (list->capacity == list->size){expend_space(list);}// 从最后一个元素到pos位置后移for (int i = list->size; i > pos; i--) {list->data[i] = list->data[i - 1];}list->data[pos] = data;list->size++;
}// 指定删除
void erase_position(SeqList* list, int pos)
{assert(list);assert(pos >= 0 && pos < list->size);  // pos范围：0 ~ size-1if (list->size == 0){printf("空表无法删除！");exit(-1);}// 指定下标之后的元素向前覆盖// 指定下标之后的元素向前覆盖for (int i = pos; i < list->size - 1; i++){list->data[i] = list->data[i + 1];}list->size--;
}// 排序模版
size_t cmp(const void* e1, const void* e2)
{return *(dataType*)e1 - *(dataType*)e2;
}
// 排序
void sort_list(SeqList* list)
{qsort(list->data, list->size, sizeof(dataType), cmp);
}// 查找指定元素的下标
int binary_search(SeqList* list, dataType data)
{assert(list);sort_list(list);int left = 0;int right = list->size - 1;while (left <= right){int mid = left + (right - left) / 2;if (data > list->data[mid]){left = mid + 1;}else if(data < list->data[mid]){right = mid - 1;}else if(data == list->data[mid]){return mid;}}return -1;
}// 销毁数据
void destrory_list(SeqList* list) 
{assert(list);free(list->data);list->data = NULL;list->size = 0;list->capacity = 0;
}

2.2 顺序表的缺陷与优势

缺点：

①头插、头删操作的时候，需要将后面所有的元素进行前移一位，时间复杂度为O(N)；

②空间不够的时候，进行扩容（二倍扩），会造成一定的空间浪费。

优点：

①尾插、尾删，直接根据数组下标插入即可，时间复杂度是O(1)；

②可以随机访问，这就意味着可以对顺序表进行排序。

③由于数据是在内存中是连续存储的，数组存入缓存中，缓存会进行预加载，预加载由于会访问一段相邻的地址，那么缓存命中率就会很高（相较于链式结构），访问数组速度就会很快。

3.题目

3.1移除元素

原题

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回移除了val之后的元素数量。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

分析：

定义一个快指针和慢指针，快指针当遇到非val值的时候需要把值赋给慢指针所指向的位置，也就是说，慢指针每次移动的时候，是遇到了非val值的时候，而快指针每次循环移动一次，这样就时间复杂度和空间复杂度都是O（N）。

代码：

int removeElement(int* nums, int numsSize, int val) {// 快慢指针int fast = 0;int slow = 0;for(fast;fast < numsSize;fast++){if(nums[fast] != val){nums[slow] = nums[fast];slow++;}}return slow;
}

本期内容主要介绍了顺序表的实现，关于顺序表包括后面的链表，相关的OJ题会单独开一期内容进行讲解，如果本期内容对你有帮助，那么可以对博主后续内容进行关注。

查看全文

http://www.lryc.cn/news/607267.html