一、引言
在计算机科学中，数据结构是一种存储和组织数据的方式，它使得数据的插入、删除和访问变得更加高效。顺序表（Array List）是一种基本的数据结构，它在内存中连续存储元素，为我们提供了操作数据的一种简单而有效的方法。本文将介绍顺序表的基本概念、分类，并展示如何在C语言中实现动态顺序表。
二、顺序表的基本概念与结构
1.概念
顺序表（也称为线性表）是一种线性数据结构，其中元素按照顺序在内存中连续存储。它的主要特点包括：
连续存储：所有元素在内存中占据一块连续的空间。
索引访问：可以通过索引快速访问任意元素。
固定大小：在静态实现中，顺序表的大小在创建时确定，无法动态调整。• 顺序表和数组的区别
◦ 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
2.基本结构
在C语言中，顺序表通常用一个数组来实现。以下是一个顺序表的基本结构：
//静态顺序表 typedef int DataType;重定义类型名字 #define MAX_SIZE 100 typedef struct { DataType data[MAX_SIZE];//定长数组 int size; // 有效数据个数 } SL;
三、顺序表的分类
顺序表可以根据其存储方式和大小变化的特性分为以下几类：
静态顺序表
定义：使用静态数组实现的顺序表，其存储空间在编译时分配，大小固定不变。
特点：
空间分配在栈区或全局数据区。
容量固定，不易扩展。
动态顺序表
定义：使用动态数组实现的顺序表，其存储空间在运行时动态分配，可以根据需要进行扩展或缩减。
特点：
空间分配在堆区。
容量可变，通过 malloc 、 realloc 和 free 等操作进行管理。
四、动态顺序表的实现
1.结构定义
typedef struct SeqList { DataType* arr; int size;//有效数据个数 int capacity;//容量 }SL;
2.相关功能实现
1.初始化
void SLInit(SL* p) { p->arr = NULL; p->size = p->capacity = 0; }
2.销毁
void SLDestory(SL* p) { if (p->arr) { free(p->arr); } p->arr = NULL; p->size = p->capacity = 0; }
3.扩容
void checkcapacity(SL*p) { if (p->size == p->capacity) { int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity; DataType*tmp= (DataType*)realloc(p->arr,newcapacity * sizeof(DataType)); if (tmp == NULL) { perror("realloc fail"); exit(1); } //空间申请成功 p->arr = tmp; p->capacity = newcapacity; } }
4.打印
void SLPrint(SL s) { for (int i = 0; i < s.size; i++) { printf("%d", s.arr[i]); } }
5.头插
void SLPushHead(SL* p, DataType x) { assert(p); checkcapacity(p); for (int i = p->size; i>=1; i--) { p->arr[i] = p->arr[i - 1]; } p->arr[0] = x; p->size++; }
6.尾插
void SLPushBack(SL* p, DataType x) { assert(p); checkcapacity(p); p->arr[p->size++] = x; }
7.头删
void SLDelHead(SL* p) { assert(p); assert(p->size);//顺序表不为空 for (int i = 1; i <=p->size-1; i++) { p->arr[i - 1] = p->arr[i]; } p->size--; }
8.尾删
void SLDelBack(SL* p) { assert(p); assert(p->size);//顺序表不为空 (p->size)--; }
9.指定插入
void SLInsert(SL* p, int pos, DataType x) { assert(p); assert(pos >= 0 && pos <=p->size); for (int i = p->size-1; i >=pos; i--) { p->arr[i + 1] = p->arr[i]; } p->arr[pos] = x; p->size++; }
10.指定删除
void SLErase(SL* p, int pos) { assert(p); assert(pos >= 0 && pos < p->size); for (int i = pos; i <=p->size-2; i++) { p->arr[i] = p->arr[i+1]; } p->size--; }
11.查找
int SLFind(SL *p, DataType x) { assert(p); for (int i = 0; i < p->size; i++) { if (p->arr[i]==x) { return i;//找到了 } } return -1;//没有找到 }
五、完整代码
1.SeqList.h
该部分放顺序表结构定义、函数的声明
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int DataType; //动态顺序表 typedef struct SeqList { DataType* arr; int size;//有效数据个数 int capacity;//容量 }SL; //初始化顺序表 void SLInit(SL* p); //销毁顺序表 void SLDestory(SL* p); //打印顺序表 void SLPrint(SL s); //顺序表头插 void SLPushHead(SL* p, DataType x); //顺序表尾插 void SLPushBack(SL* p, DataType x); //顺序表头删 void SLDelHead(SL* p); //顺序表尾删 void SLDelBack(SL* p); //在指定位置前插入数据 void SLInsert(SL* p, int pos, int x); //删除指定位置的数据 void SLErase(SL* p, int pos); //顺序表的查找 int SLFind(SL* p, DataType x);
2.SeqList.c
该部分是函数功能的实现，也就是上述第四点的代码
#define _CRT_SECURE_NO_WARNINGS #include"SeqList.h" //初始化顺序表 void SLInit(SL* p) { p->arr = NULL; p->size = p->capacity = 0; } //销毁顺序表 void SLDestory(SL* p) { if (p->arr) { free(p->arr); } p->arr = NULL; p->size = p->capacity = 0; } //检查容量判断是否扩容 void checkcapacity(SL*p) { if (p->size == p->capacity) { int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity; DataType*tmp= (DataType*)realloc(p->arr,newcapacity * sizeof(DataType)); if (tmp == NULL) { perror("realloc fail"); exit(1); } //空间申请成功 p->arr = tmp; p->capacity = newcapacity; } } //打印顺序表 void SLPrint(SL s) { for (int i = 0; i < s.size; i++) { printf("%d", s.arr[i]); } } //顺序表头插 void SLPushHead(SL* p, DataType x) { assert(p); checkcapacity(p); for (int i = p->size; i>=1; i--) { p->arr[i] = p->arr[i - 1]; } p->arr[0] = x; p->size++; } //顺序表尾插 void SLPushBack(SL* p, DataType x) { assert(p); checkcapacity(p); p->arr[p->size++] = x; } //顺序表头删 void SLDelHead(SL* p) { assert(p); assert(p->size);//顺序表不为空 for (int i = 1; i <=p->size-1; i++) { p->arr[i - 1] = p->arr[i]; } p->size--; } //顺序表尾删 void SLDelBack(SL* p) { assert(p); assert(p->size);//顺序表不为空 (p->size)--; } //在指定位置前插入数据 void SLInsert(SL* p, int pos, DataType x) { assert(p); assert(pos >= 0 && pos <=p->size); for (int i = p->size-1; i >=pos; i--) { p->arr[i + 1] = p->arr[i]; } p->arr[pos] = x; p->size++; } //删除指定位置的数据 void SLErase(SL* p, int pos) { assert(p); assert(pos >= 0 && pos < p->size); for (int i = pos; i <=p->size-2; i++) { p->arr[i] = p->arr[i+1]; } p->size--; } //顺序表的查找 int SLFind(SL *p, DataType x) { assert(p); for (int i = 0; i < p->size; i++) { if (p->arr[i]==x) { return i;//找到了 } } return -1;//没有找到 }
3.test.c
该部分用来测试我们写的函数(函数的调用)，可以随便改
#define _CRT_SECURE_NO_WARNINGS #include"SeqList.h" void SLtest01()//测试 { SL sl; SLInit(&sl); //增删查改操作 SLPushHead(&sl,1);//头插1 1 SLPushHead(&sl,3);//头插3 31 SLPushBack(&sl, 5);//尾插5 315 SLInsert(&sl,3,7);//在下标为3的位置插入7 3157 SLErase(&sl,2);//删除下标为2的数据 317 SLPrint(sl); int find = SLFind(&sl, 3); if (find>=0) { printf("找到了，下标为%d\n", find); } else { printf("没有找到"); } SLDestory(&sl); } int main() { SLtest01(); return 0; }
六、总结
顺序表是一种简单而强大的数据结构，通过连续内存存储实现高效的随机访问。根据需要，我们可以选择静态或动态顺序表来适应不同的应用场景。动态顺序表通过动态调整大小，提供了更大的灵活性和效率。希望本文对你理解顺序表及其实现有所帮助！
