【数据结构】C语言实现顺序表的主要功能

一.数据结构整体框架

架构解释：

集合：无序但唯一；只关心元素是否存在而不关心元素的顺序；当尝试插入重复的元素时，集合会忽略掉那个重复的元素。

线性表：元素按照顺序排列的集合；每个元素只有一个直接前驱和一个直接后继；要注意线性表所说的顺序排列是我们看到的表的样子是按顺序排列的，至于底层里这个表的物理地址是否也是按顺序排列的是不确定的，由此就有两种实现线性表的方式：顺序表、链表。顺序表是通过一块连续的内存区域来存储线性表中的元素，不止是我们看起来这个表是按顺序存储数据的，每个数据它的物理地址也是按照线性表中的顺序排列的，通常使用数组来实现。链表的存储空间不需要是连续的，每个元素通过指针连接起来，也就是说表中的数据我们看着是按a（3）、b（2）、c（1）、d（4）排列的，（）中的数字表示地址顺序，但是底层里，它们的地址顺序可能是c（1）、b（2）、a（3）、d（4）这样的顺序，我们通过串连起它们的地址，达到了我们想要的表的顺序，比如如果我们以3214的顺序连接起这些地址，就可以达到abcd这样看起来是顺序排列的线性表。

栈和队列：栈和队列是线性表的一种特殊形式，是对元素的访问顺序进行了限制的线性表。具体来说，对于线性表我们一般可以对它进行增删改查的操作，对于普通的线性表，如果我们想要进行增的操作，我们可以把新元素加入在开头，也可以将新元素加入到结尾，甚至可以加在指定位置。但是对于栈来说，它只能加在栈顶的位置，对于队列来说它只能加在队尾的位置。删除操作也同样受限。这是因为我们规定对于栈来说不管是要删除还是要加入都只能从栈顶这一个位置进行操作，对于队列来说加入只能从队尾，删除只能从队头。

非线性表：元素不是按照顺序排列的集合；或者说每个元素不一定只有一个直接前驱和一个直接后继；树是一种典型的非线性结构，它由节点和连接这些节点的边组成。树的节点之间有层次结构，通常是父节点和子节点的关系。对于一个父节点来说它往往可以有多个子节点，也就是多个后继，但是对于一个子节点来说往往只能有一个父节点。总的来说是一种一对多的关系。图是一种由节点和连接节点的边组成的结构。图比树更加灵活，因为它允许节点之间有多种连接方式。对于其中一个节点，它可以连接很多其它节点作为它的后继，同时该节点的前驱也可以有很多个。总的来说是一种多对多的关系。

二.顺序表的实现

这篇文章我们先来介绍顺序表的实现，也就是用数组的形式来实现线性表

1.实现的功能：

-顺序表的初始化

-向顺序表中增加一个数据（头、尾、指定位置）

-删除顺序表中的一个数据（头、尾、指定位置）

-修改顺序表中某个位置的数据

-查找顺序表中某个位置的数据

2.顺序表的初始化

初始化就是拿到一个可以放数据的空间然后把它变成空顺序表的状态

1.静态顺序表：

怎么拿到空间？我们的顺序表通常是struct的结构，其中放数据的部分是数组类型，记录表中数据个数的是int类型，当我们定义这个struct结构后，就会给我们分配对应的一个struct空间。

顺序表的struct结构示意图：

顺序表的struct代码：

typedef int DataType;
# 我们这里假设顺序表中的数据类型为int，可根据实际情况修改
# 创建一个静态顺序表 
typedef struct SeqList{
	DataType data[N];  //Data数组
	int length;	       //表中数据个数
}SeqList;

顺序表的初始化：

void InitList(SeqList* L){
	assert(L);       //如果传入的空指针，后面对它进行解引用就会报错
	L->length = 0;	
    for (int i = 0; i < N; i++) {
        L->data[i] = 0;
    }
    //因为我的顺序表是int型的，为了保证初始化的顺序表“干净”全部设为0
    //在我的顺序表中0表示无值
}

使用assert（）函数需要引入头文件： #include <assert.h>

是否疑惑？

为什么这里传参要传一个指针型的变量呢？为什么不直接传参SeqList L呢？按理说，直接实例化SeqList这个结构体后，把这个结构体传过去不就可以操作了吗？这里就涉及到C语言中传值和传指针的区别了

传值：

传值传的只是实际变量的副本，就比如在这里，如果我们执行下边的代码：

int main() {
    SeqList L;  // 定义一个顺序表变量
    SLInit(L);  // 传递 L 作为值传递
}

它进行的操作是先开辟的一个名为L的SeqList类型的结构体空间，但是在执行第二句，在传参时，系统会copy一份跟L一样的struct空间，但是这个空间是一个新的空间，函数内的一切操作都是对这个新空间里的副本进行的操作，当函数执行结束后这些副本空间就会被释放，之前执行的操作也就随之消失，只会留下什么也没改变的实例化的L。为了解决这个问题所以我们要传指针

传指针：

传指针传的就是当下的这个变量，指定的就是这个地址下的这个变量，在函数中进行的一系列操作也都是真真实实的发生在了这个实例化的L上的。

上述的顺序表结构由固定大小的数组来实现，若要改变顺序表的大小需要手动修改N的大小，称为静态顺序表，一旦实例化这个表，大小就不能改变。有没有什么办法可以实现让表的大小可以根据数据量的多少来自动调节呢？接下来我们引入动态顺序表

2.动态顺序表：

动态顺序表的实现主要是不再给Data 数组分配固定的空间，另外需要一个表示容量的变量，通过比较length（表中数据个数）与capacity（当前顺序表可存数据个数）来判断是否需要扩容

动态顺序表的struct代码：

//顺序表的动态存储
typedef int DataType;
typedef struct SeqList
{
	DataType* data;      //尚未分配空间的数组
	int length;         //有效数据个数
	int capacity;     //空间容量的大小
}SeqList;

在这里我们的Data 数组是尚未分配空间的一个数组，只是有数组的地址，一般在初始化列表时通过malloc（）函数分配空间，至于动态数组的动态性往往会在向顺序表中增加数据时体现,其中关键代码如下：

if (L->length == L->capacity) {  // 如果数组满了，就扩展
        L->capacity *= 2;  // 通常扩容是将容量翻倍
        L->data = (DataType*)realloc(L->Data, L->capacity * sizeof(DataType));  // 重新分配更大的内存
    }

realloc（）函数会返回一个新的指针，指向扩展后的内存区域，原来的数据会被复制过去。

动态顺序表的初始化：

void SLInit(SeqList* L, int initial_capacity) {
    assert(L);  // 确保传入的指针有效
    L->data = (DataType*)malloc(initial_capacity * sizeof(DataType));  // 为 Data 数组分配内存
    if (L->data == NULL) {  // 检查内存分配是否成功
        printf("Memory allocation failed!\n");
        return;
    }
    L->length = 0;         // 初始时顺序表没有任何元素
L->capacity = initial_capacity;  // 设置顺序表的初始容量
}

使用malloc（）函数需要引入头文件：#include <stdlib.h>

malloc（）函数并不能保证分配的空间是干净的，要保证顺序表干净，初始化顺序表时可以使用calloc（）函数

L->data = (DataType*)calloc(initial_capacity, sizeof(DataType));  // 为 Data 数组分配内存并初始化为零

3.向顺序表中增加数据

不管是在哪里加入数据都需要先判断表是否已满，是否需要扩容？

1.在顺序表头加入数据

void Add_Head(SeqList* L, DataType newdata ) {
	assert(L); 
	// 判断列表是否已满
	if(L->length==L->capacity){
		L->capacity=2*L->capacity;
		L->data = (DataType*)realloc(L->data, L->capacity * sizeof(DataType));
		if (L->data == NULL) {
            printf("Memory allocation failed!\n");
            return;
        } 
	} 
	//在顺序表开头插入数据	
	
	//将顺序表中原来的数据都向后移动一位 
	for (int i = L->length - 1; i >= 0; i--) {
    L->data[i + 1] = L->data[i];
    }   
    //插入新值
	L->data[0]=newdata;
	L->length++;	

}

是否疑惑？

为什么在后移原始顺序表中的数值时要用从后到前的遍历方法？你是否在自己写代码的时候用的是下边的移动方式？即从前往后遍历？


	for(int i=0;i<L->length;i++) {
		L->data[i+1]=L->data[i];	
	}

这么做，并且做过测试的同学可能发现顺序表的输出结果与我们期待的那样不符，这是由于我们尚未保存i+1位的数据就已经被第i位的数据给替代了，最后的结果往往是只有前两位的数据是正确的

如果从后往前遍历，则情况会大不一样，在第i位要移动到第i+1位之前，第i+1位已经移动到了第i+2位，并且由于头插顺序表的尾部都是空的，所以并不会覆盖任何有用数据，这样就可以完美实现表头加入数据了

2.在顺序表尾加入数据

在表尾插数据就比较简单了，只需要在data[length]处添加数据即可，当然因为是插入数据肯定要先判断顺序表是否已满，同表头插入数据

L->data[L->length] = newdata;  // 直接插入到当前有效数据个数的位置

3.在指定位置加入数据

在指定位置插入数据也类似于在顺序表头插入，把原始数据从指定位置挨个往后移动一位即可，核心代码如下：

注意：顺序表中的序号与数组下标序号相差1，即表中的第4个数据是数组下标为3的数据

	for(int j=L->length-1;j>=index-1;j--){
		L->data[j+1]=L->data[j]; 	
	}
	L->data[index-1]=newdata;

4.删除顺序表中的数据

不管在哪里删除数据都需要先判断表中是否还有数据？

1.在顺序表头删除数据

void Delete_Head(SeqList* L ) {
	assert(L);
	assert(L->length>0);   //判断是否为空表，为空则报错，表示不能进行删除操作
	// 挨个往前移动一位
	for (int i=0;i<L->length;i++){
		L->data[i]=L->data[i+1];
	} 
	L->length--;	
}

往后就没啥技术含量了感觉，删除跟插入差不多

对于表头插入来说表末是可用空间，所以从后往前遍历，去挨个替换

对于表头删除来说表头是可用空间，所以从前往后遍历，去挨个替换

2.在顺序表尾删除数据

	L->data[L->length-1] = 0;

3.在指定位置删除数据

for (int i=index-1;i<L->length;i++){
		L->data[i]=L->data[i+1];
	}

5.修改顺序表中的数据

void change_data(SeqList* L ,int index,DataType newdata){
	assert(L);
	assert(index>0&&index<L->length);
	L->data[index-1] = newdata;	
}

6.查找顺序表指定位置的数据

void get_data(SeqList* L ,int index){
	assert(L);
	assert(index>0&&index<L->length);
    printf("\n%d",L->data[index-1]);
	
}

7.顺序表代码完整版（含测试）

# include<stdio.h>
# define N 10
#include <assert.h>
#include <stdlib.h>

/*
typedef int DataType;
# 我们这里假设顺序表中的数据类型为int，可根据实际情况修改

# 创建一个静态顺序表 
typedef struct SeqList{
	DataType data[N];
	int length;	
}SeqList;

void InitList(SeqList* L){
	assert(L);       //如果传入的空指针，后面对它进行解引用就会报错
	L.data = Null;
	L.length = 0;	
} 

*/
//顺序表的动态存储
typedef int DataType;
typedef struct SeqList
{
	DataType* data;      //尚未分配空间的数组
	int length;         //有效数据个数
	int capacity;     //空间容量的大小
}SeqList;


void SLInit(SeqList* L, int initial_capacity) {
    assert(L);  // 确保传入的指针有效
    L->data = (DataType*)malloc(initial_capacity * sizeof(DataType));  // 为 Data 数组分配内存
    if (L->data == NULL) {  // 检查内存分配是否成功
        printf("Memory allocation failed!\n");
        return;
    }
    L->length = 0;         // 初始时顺序表没有任何元素
    L->capacity = initial_capacity;  // 设置顺序表的初始容量
}

void Add_Head(SeqList* L, DataType newdata ) {
	assert(L); 
	// 判断列表是否已满
	if(L->length==L->capacity){
		L->capacity=2*L->capacity;
		L->data = (DataType*)realloc(L->data, L->capacity * sizeof(DataType));
		if (L->data == NULL) {
            printf("Memory allocation failed!\n");
            return;
        } 
	} 
	//在顺序表开头插入数据	
	/*
	for(int i=0;i<L->length;i++) {
		L->data[i+1]=L->data[i];	
	}
	*/
	//将顺序表中原来的数据都向后移动一位 
	for (int i = L->length - 1; i >= 0; i--) {
    L->data[i + 1] = L->data[i];
    }   
    
	L->data[0]=newdata;
	L->length++;	

}
void Add_End(SeqList* L, DataType newdata ) {
	assert(L); 
	// 判断列表是否已满
	if(L->length==L->capacity){
		L->capacity=2*L->capacity;
		L->data = (DataType*)realloc(L->data, L->capacity * sizeof(DataType));
		if (L->data == NULL) {
            printf("Memory allocation failed!\n");
            return;
        } 
	} 
	L->data[L->length]=newdata;
	L->length++;	

}
void Add_Pos(SeqList* L, DataType newdata,int index ) {
	assert(L); 
	assert(index>0&&index<L->length+1);
	// 判断列表是否已满
	if(L->length==L->capacity){
		L->capacity=2*L->capacity;
		L->data = (DataType*)realloc(L->data, L->capacity * sizeof(DataType));
		if (L->data == NULL) {
            printf("Memory allocation failed!\n");
            return;
        } 
	} 
	for(int j=L->length-1;j>=index-1;j--){
		L->data[j+1]=L->data[j]; 	
	}
	L->data[index-1]=newdata;
	L->length++;	

}


void Delete_Head(SeqList* L ) {
	assert(L);
	assert(L->length>0);   //判断是否为空表，为空则报错，表示不能进行删除操作
	// 挨个往前移动一位
	for (int i=0;i<L->length;i++){
		L->data[i]=L->data[i+1];
	} 
	L->length--;	
}

void Delete_End(SeqList* L ) {
	assert(L);
	assert(L->length>0);   //判断是否为空表，为空则报错，表示不能进行删除操作
	
	L->data[L->length-1] = 0;
	
	L->length--;	
}

void Delete_Pos(SeqList* L ,int index) {
	assert(L);
	assert(L->length>0);   //判断是否为空表，为空则报错，表示不能进行删除操作
	assert(index>0&&index<L->length);
	// 挨个往前移动一位
	for (int i=index-1;i<L->length;i++){
		L->data[i]=L->data[i+1];
	} 
	L->length--;	
}

void change_data(SeqList* L ,int index,DataType newdata){
	assert(L);
	assert(index>0&&index<L->length);
	L->data[index-1] = newdata;	
}

void get_data(SeqList* L ,int index){
	assert(L);
	assert(index>0&&index<L->length);
    printf("\n%d",L->data[index-1]);
	
}


// 打印顺序表
void print_List(SeqList* L){
	for(int i=0;i<L->length;i++){
		DataType realdata=L->data[i];
		printf("%d",realdata);
	}
} 

int main(){
	SeqList L;
	SLInit(&L,3);
	
    Add_Head(&L,3);
	Add_Head(&L,2);
	Add_Head(&L,5);
	Add_Head(&L,1);
	Add_Head(&L,6);
	Add_Head(&L,9);
	Add_Pos(&L,4,4);
	Delete_Head(&L);
	Delete_Head(&L);	
    Add_End(&L,2);
    Delete_End(&L);
    Delete_Pos(&L, 3);
    change_data(&L,2,4);
    
	print_List(&L);
    get_data(&L ,3);
}