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

数据结构：顺序表

news 来源：原创 2024/5/17 15:27:57

一.顺序表

1.1概念以及结构

1.2动态顺序表实现

1.2.1文件创建：

1.2.2接口实现

1.顺序表打印

2.顺序表初始化

3.顺序表尾插

4.顺序表头插

5.顺序表尾删

6.顺序表头删

7.顺序表在pos位置插入x

8.顺序表删除pos位置的值

9.顺序表销毁

二.顺序表问题

一.顺序表

1.1概念以及结构

顺序表（一般是用数组存储）是一种线性数据结构，其将相同类型元素存储在连续的内存空间中。

顺序表一般可以分为：

静态顺序表：使用定长数组存储元素
动态顺序表：使用动态开辟（malloc）的数组存储。

静态顺序表：

#include<stdio.h>
#include<stdlib.h>#define number 7
typedef int SLDataType;
typedef struct SeqList
{SLDataType array[number];//定长数组size_t size;//有效数据个数
}SL;

动态顺序表：

#include<stdio.h>
#include<stdlib.h>typedef int SLDataType;
typedef struct SeqList
{SLDataType* a;//指向动态开辟的数组int size;//有效数据个数int capacity;//容量空间大小
}SL;

1.2动态顺序表实现

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

1.2.1文件创建：

在seq.h文件中对顺序表结构和接口（增删查改等）函数进行声明
在seq.c文件中对顺序表接口函数进行实现
在test.c文件中一步步对顺序表及其接口进行测试

1.2.2接口实现

对于顺序表我们要实现以下几个功能：

顺序表打印（可视化每一步的成果）
顺序表初始化
顺序表尾插
顺序表头插
顺序表尾删
顺序表头删
顺序表在pos位置插入x
顺序表删除pos位置的值
顺序表销毁

1.顺序表打印

//存储整数的顺序表打印
void SLPrint(SL* psl)
{assert(psl);int i = 0;for (i = 0; i < psl->size; i++){printf("%d ", psl->a[i]);}printf("\n");
}

2.顺序表初始化

//顺序表初始化
void SLInit(SL* psl)
{assert(psl);psl->a = NULL;psl->size = 0;psl->capacity = 0;}

3.顺序表尾插

// 顺序表尾插
void SLPushBack(SL* psl, SLDataType x)
{assert(psl);//尾插时 检查顺序表容量大小if (psl->size == psl->capacity){//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//realloc开辟空间和扩容SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fali:");return;}psl->a = tmp;psl->capacity = newcapacity;}//尾插元素psl->a[psl->size] = x;psl->size++;
}

写出函数后进行一次测试：

//顺序表尾插测试
void test1()
{//定义一个顺序表变量SL sl1;//初始化这个顺序表变量SLInit(&sl1);SLPushBack(&sl1, 1);SLPushBack(&sl1, 2);SLPushBack(&sl1, 3);SLPushBack(&sl1, 4);SLPushBack(&sl1, 5);SLPrint(&sl1);}
int main()
{test1();return 0;
}

4.顺序表头插

// 顺序表头插
void SLPushFront(SL* psl, SLDataType x)
{assert(psl);//头插时 检查顺序表容量大小if (psl->size == psl->capacity){//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//realloc开辟空间和扩容SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fali:");return;}psl->a = tmp;psl->capacity = newcapacity;}//与尾插不同的是在进行头插之前我们需要将所有元素先向后移动一位int odd_size_to_move = psl->size;int i = 0;for (i = 0; i < psl->size; i++){psl->a[odd_size_to_move] = psl->a[odd_size_to_move - 1];odd_size_to_move--;}//头插元素psl->a[0] = x;psl->size++;
}

写出函数后进行一次测试：

//顺序表头插测试
void test2()
{//	定义一个顺序表变量SL sl2;//初始化这个顺序表变量SLInit(&sl2);//	先尾插SLPushBack(&sl2, 0);SLPushBack(&sl2, 0);SLPushBack(&sl2, 0);SLPushBack(&sl2, 0);//	再头插SLPushFront(&sl2, 5);SLPushFront(&sl2, 4);SLPushFront(&sl2, 3);SLPushFront(&sl2, 2);SLPushFront(&sl2, 1);SLPrint(&sl2);SLDestory(&sl2);}
int main()
{test2();return 0;
}

5.顺序表尾删

// 顺序表尾删
void SLPopBack(SL* psl)
{//温柔检查//要保证顺序表空了就不再删除了，根除错误源头if (psl->size == 0){return;}//暴力检查//assert(psl->size > 0);psl->size--;}

写出函数后进行一次测试：

//顺序表尾删测试
void test3()
{//定义一个顺序表变量SL sl2;//初始化这个顺序表变量SLInit(&sl2);//先尾插SLPushBack(&sl2, 100);SLPushBack(&sl2, 99);SLPushBack(&sl2, 98);SLPushBack(&sl2, 97);//再头插SLPushFront(&sl2, 5);SLPushFront(&sl2, 4);SLPushFront(&sl2, 3);SLPushFront(&sl2, 2);SLPushFront(&sl2, 1);SLPrint(&sl2);//尾删SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);SLPopBack(&sl2);//上面只有九个元素，当我们再调用删除的时候将会报错或者直接退出该函数调用。SLPopBack(&sl2);//头插                       SLPushFront(&sl2, 5);SLPushFront(&sl2, 4);SLPushFront(&sl2, 3);SLPushFront(&sl2, 2);SLPushFront(&sl2, 1);SLPrint(&sl2);SLDestory(&sl2);
}
int main()
{test3();return 0;
}

6.顺序表头删

// 顺序表头删
void SLPopFront(SL* psl)
{assert(psl);//挪动覆盖int i = (psl->size) - 1;int j = 0;while (i){psl->a[j] = psl->a[j + 1];j++;i--;}psl->size--;
}

写出函数后进行一次测试：

//顺序表头删测试
void test4()
{//定义一个顺序表变量SL sl2;//初始化这个顺序表变量SLInit(&sl2);//先尾插SLPushBack(&sl2, 100);SLPushBack(&sl2, 99);SLPushBack(&sl2, 98);SLPushBack(&sl2, 97);//再头插SLPushFront(&sl2, 5);SLPushFront(&sl2, 4);SLPushFront(&sl2, 3);SLPushFront(&sl2, 2);SLPushFront(&sl2, 1);SLPrint(&sl2);//头删SLPopFront(&sl2);SLPrint(&sl2);SLDestory(&sl2);
}
int main()
{test4();return 0;
}

7.顺序表在pos位置插入x

// 顺序表在pos位置插入x
void SLInsert(SL* psl, size_t pos, SLDataType x)
{assert(psl);//插入元素前先检查顺序表容量大小是否足够if (psl->size == psl->capacity){//将初始化为0的capacity改变    如果为零，赋值为4四，之后两倍扩容int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//realloc开辟空间和扩容SLDataType* tmp = (SLDataType*)realloc(psl->a, newcapacity * sizeof(SLDataType));if (tmp == NULL){perror("realloc fali:");return;}psl->a = tmp;psl->capacity = newcapacity;}int n = psl->size;while (n > pos){psl->a[n] = psl->a[n - 1];n--;}psl->a[pos] = x;(psl->size)++;}

写出函数后进行一次测试：


//顺序表pos位置插入测试
void test5()
{//定义一个顺序表变量SL sl2;//初始化这个顺序表变量SLInit(&sl2);//先尾插SLPushBack(&sl2, 100);SLPushBack(&sl2, 99);SLPushBack(&sl2, 98);SLPushBack(&sl2, 97);//再头插SLPushFront(&sl2, 5);SLPushFront(&sl2, 4);SLPushFront(&sl2, 3);SLPushFront(&sl2, 2);SLPushFront(&sl2, 1);//pos位置插入xSLInsert(&sl2, 3, 5000);SLPrint(&sl2);SLDestory(&sl2);
}
int main
{test5();return 0;
}

8.顺序表删除pos位置的值

// 顺序表删除pos位置的值
void SLErase(SL* psl, size_t pos)
{assert(psl);while (pos < ((psl->size) - 1)){psl->a[pos] = psl->a[pos + 1];pos++;}(psl->size)--;
}

写出函数后进行一次测试：

//顺序表pos位置删除测试
void test6()
{//定义一个顺序表变量SL sl2;//初始化这个顺序表变量SLInit(&sl2);//先尾插SLPushBack(&sl2, 100);SLPushBack(&sl2, 99);SLPushBack(&sl2, 98);SLPushBack(&sl2, 97);//再头插SLPushFront(&sl2, 5);SLPushFront(&sl2, 4);SLPushFront(&sl2, 3);SLPushFront(&sl2, 2);SLPushFront(&sl2, 1);//pos位置删除SLErase(&sl2, 3);SLPrint(&sl2);SLDestory(&sl2);
}
int main()
{test6();return 0;
}

9.顺序表销毁

//顺序表销毁
void SLDestory(SL* psl)
{assert(psl);//检查动态开辟的顺序表内存最后是否被释放，没有释放则释放psl->a并且将顺序表全部初始化为最初的形态if (psl->a != NULL){free(psl->a);psl->a = NULL;psl->size = 0;psl->capacity = 0;}
}