202 lines
5.5 KiB
Markdown
202 lines
5.5 KiB
Markdown
---
|
||
title: 数据结构-c语言-顺序表
|
||
tags: 数据结构,C语言
|
||
categories: 数据结构,C语言
|
||
date: 2022-08-13 17:50:56
|
||
---
|
||
|
||
# 什么是顺序表
|
||
+ 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
|
||
|
||
+ 顺序表：可动态增长的数组，要求数据是连续存储的
|
||
|
||
+ 与链表的区别：同样是存储想同类型数据的线性表，但是链表两个节点之间使用指针进行链接，相比来说占用更大的空间，但是对于增加和删除节点时相比比顺序表更快。
|
||
|
||
# 静态顺序表和动态顺序表
|
||
|
||
- 静态顺序表：静态顺序表通过一个提前分配好了的数组进行存储数据，优点是不能很好评估分配的大小
|
||
|
||
- 动态顺序表：动态顺序表是通过动态分配数组的大小进行存储数据，优点是可以动态分配大小，缺点是在扩容过程中可能比较复杂
|
||
|
||
# 动态顺序表
|
||
|
||
## 顺序表的数据结构定义
|
||
```c
|
||
typedef struct OrderLists {
|
||
int *datas;
|
||
int maxsize;
|
||
int size;
|
||
|
||
}OrderList;
|
||
```
|
||
|
||
size代表当前顺序表已经存储的数据量，maxsize表示当前顺序表所能存储的最大数据，当size=maxsize时会进行扩容操作，datas是用来存储数据的动态数组，数组大小动态分配。
|
||
|
||
## 顺序表的初始化
|
||
```c
|
||
|
||
// 初始化顺序表
|
||
void initOrderList(OrderList* list,int maxsize) {
|
||
list->datas = (int*)malloc(maxsize * sizeof(int));
|
||
list->maxsize = maxsize;
|
||
list->size = 0;
|
||
}
|
||
```
|
||
|
||
在初始化时定义一个预先分配的最大值，通过malloc函数进行分配内存，maxsize相应进行赋值，size分配为0
|
||
|
||
## 顺序表扩容
|
||
```c
|
||
/// <summary>
|
||
/// 顺序表扩容，扩容为原来内容的两倍
|
||
/// </summary>
|
||
/// <param name="list"></param>
|
||
void expansion(OrderList *list) {
|
||
// 申请两倍当前maxsize的内存
|
||
int* new_data = malloc(2 * list->maxsize * sizeof(int));
|
||
if (!new_data)
|
||
{
|
||
printf("申请内存失败\n");
|
||
return;
|
||
}
|
||
// 转移数据
|
||
for (int i = 0; i < list->size; i++)
|
||
{
|
||
new_data[i] = list->datas[i];
|
||
}
|
||
// 释放之前分配的内存
|
||
free(list->datas);
|
||
list->datas = new_data;
|
||
list->maxsize = 2 * list->maxsize;
|
||
printf("顺序表已扩容，扩容后大小 ==》 %d\n", list->maxsize);
|
||
}
|
||
```
|
||
首先分配一个与当前maxsize两倍空间的一个数组，然后将之前数组中的值转移到新数组中来，然后释放之前的数组，同时将顺序表的指针指向新的数组
|
||
|
||
|
||
## 顺序表的插入
|
||
```c
|
||
/// <summary>
|
||
/// 顺序表插入数据
|
||
/// </summary>
|
||
/// <param name="list"></param>
|
||
/// <param name="data"></param>
|
||
/// <param name="position"></param>
|
||
/// <returns></returns>
|
||
int OrderListInsert(OrderList *list,int data,int position) {
|
||
if (list->size == list->maxsize) {
|
||
expansion(list);
|
||
}
|
||
if (position == -1) {
|
||
list->datas[list->size] = data;
|
||
list->size++;
|
||
return 0;
|
||
}
|
||
for (int i = list->size - 1; i >= position; i--)
|
||
{
|
||
list->datas[i + 1] = list->datas[i];
|
||
}
|
||
list->datas[position] = data;
|
||
list->size++;
|
||
return 0;
|
||
}
|
||
```
|
||
首先在插入之前判断当前是否需要扩容，然后判断position为-1时我们直接将数据插入的结尾，退出函数，如果数据需要插入到中间，那么我们将数组从后向前遍历，直到需要插入的位置，然后将数据依次向后移动一个位置，然后插入数据。
|
||
|
||
## 顺序表的删除
|
||
```c
|
||
int OrderDelete(OrderList* list,int position) {
|
||
if (position > list->size - 1) {
|
||
return 0;
|
||
}
|
||
for (int i = position; i <= list->size-2; i++)
|
||
{
|
||
list->datas[i] = list->datas[i+1];
|
||
}
|
||
list->size--;
|
||
}
|
||
```
|
||
顺序表的删除和插入同理，当然遍历方式从删除的位置向末尾遍历，直到结尾的前一个元素，然后依次把数据向前移动一位，就覆盖掉了需要删除的内容。
|
||
|
||
## 顺序表的修改
|
||
```c
|
||
/// <summary>
|
||
/// 更新某个位置的数据
|
||
/// </summary>
|
||
/// <param name="list"></param>
|
||
/// <param name="data"></param>
|
||
/// <param name="position"></param>
|
||
/// <returns></returns>
|
||
int OrderUpdate(OrderList* list, int data, int position) {
|
||
if (position > list->size-1) {
|
||
return 0;
|
||
}
|
||
list->datas[position] = data;
|
||
return 1;
|
||
}
|
||
```
|
||
顺序表的修改可以说没得难度，直接修改数组内内容就可以了
|
||
|
||
## 顺序表的查询
|
||
```c
|
||
/// <summary>
|
||
/// 获取某个位置的数据
|
||
/// </summary>
|
||
/// <param name="list"></param>
|
||
/// <param name="position"></param>
|
||
/// <returns></returns>
|
||
int OderGetData(OrderList* list, int position) {
|
||
if (position > list->size - 1) {
|
||
return -1;
|
||
}
|
||
else
|
||
{
|
||
return list->datas[position];
|
||
}
|
||
}
|
||
```
|
||
顺序表的查询直接返回对于位置的内容即可
|
||
|
||
## 顺序表的遍历
|
||
```
|
||
/// <summary>
|
||
/// 遍历顺序表
|
||
/// </summary>
|
||
/// <param name="list"></param>
|
||
void OderForEach(OrderList* list) {
|
||
for (int i = 0; i < list->size; i++)
|
||
{
|
||
printf("%d ", list->datas[i]);
|
||
}
|
||
}
|
||
```
|
||
|
||
## 测试
|
||
```c
|
||
int main() {
|
||
OrderList list;
|
||
initOrderList(&list,10);
|
||
for (int i = 0; i < 40; i++)
|
||
{
|
||
OrderListInsert(&list, i+1, i);
|
||
}
|
||
OderForEach(&list);
|
||
for (int i = 0; i < 20; i++)
|
||
{
|
||
OrderDelete(&list, 0);
|
||
}
|
||
printf("\n删除前20个元素\n");
|
||
OderForEach(&list);
|
||
return 0;
|
||
}
|
||
/*
|
||
顺序表已扩容，扩容后大小 ==》 20
|
||
顺序表已扩容，扩容后大小 ==》 40
|
||
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
||
删除前20个元素
|
||
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
||
*/
|
||
```
|
||
|
||
# 引申
|
||
顺序表可以引申出顺序队，顺序栈，只需要编写特定的方法即可 |