【C数据结构】解决动态顺序表以及常见问题

文章目录

• • 
    

    一、顺序表的本质

  • 
    

    二、动态顺序表的实现

  • • 1、测试页与接口调用页
    • 2、初始化顺序表
    • 3、扩充储存容量
    • 4、插入数据
    • 5、删除数据
    • 6、查找数据
    • 7、销毁顺序表
  • 
    

    三、总结

一、顺序表的本质

  顺序表本质上就是数组，但在数组上加了两点，一是分为静态和动态，二是要求数据从头开始存并且是连续存储，不能跳跃间隔。

  由于动态顺序表相较于静态顺序表，除了在空间开辟上更有优势，其他大体一样，所以在这里我们讨论动态的顺序表。

 
 

二、动态顺序表的实现

 
  动态顺序表与直接用数组实现的静态顺序表不同在于，动态顺序表用的是指针，动态顺序表通过指针变量储存的地址指向一个经过动态内存开辟的空间。

对于这个空间，我们可以在它满的时候能给它扩大空间（也就是数组中的数存满了），所以为了知道这个空间什么时候存满，我们就需要知道它存储的有效数据数量(size)，和当前能存的最大空间容量(capacity)。

 

所以我们可以定义一个结构体变量，并且将它放在一个名为SqList.h的源文件中

//SqList.h
typedef int DateType;//当用其他数据类型，只需要把int改了就行
typedef struct SeqList {
	int size; //有效数据数量
	int capacity;//最大空间容量
	DateType* a;//指向数组空间的指针
}SL;

 
 

1、测试页与接口调用页

首先我们会创建一个名为Test.c的源文件

//Test.c
//测试页
#include"SqList.h"
void Test1(){
	SL ps;
	/*
	在这里通过调用函数进行测试
	如:
	SeqListInit(&ps);
	*/
}
int main()
{
	Test1();
	return 0;
}

 
SqList.h页面

//SqList.h
#include
#include //malloc、realloc、free需要的
#include//assert()需要的
typedef int DateType;//当用其他数据类型，只需要把int改了就行
typedef struct SeqList {
	int size; //有效数据数量
	int capacity;//最大空间容量
	DateType* a;//指向数组空间的指针
}SL;

//接口
void SeqListInit(SL *ps);
void SeqListCheckCapacity(SL *ps);
....

而接下来的函数实现则需要放入SqList.c中，并且包括SqList.h

//SqList.c
#include"SqList.h"
...

 
 

2、初始化顺序表

接下来的函数实现我们将写在源文件为SqList.c的源文件中

//SqList.c
//初始化顺序表
void SeqListInit(SL* ps) {
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

  为什么要初始化？
  首先a是一个未初始化的指针，在使用未初始化的指针时，VS编译器是会出现读取错误的。

  而size是因为需要从0累计算的，容量capacity目前也没有，这些方便处理后期使用的数据。

 

3、扩充储存容量

首先回顾一下malloc和realloc，malloc是简单的分配内存空间，realloc是扩充空间返回新的地址，而realloc当指针为空的时候，作用是和malloc一样的，所以。

//SqList.c
//检查容量
void SeqListCheckCapacity(SL* ps) {
	while (ps->size == ps->capacity) {     //当有效数据数量等于最大容量
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2; //新的容量大小就将扩大两倍，为0时容量就从4开始
		DateType* tmp = (DateType*)realloc(ps->a,sizeof(DateType) * newcapacity);//realloc扩充容量返回地址给新指针tmp
		if (tmp == NULL) {				  //检查有没有扩充失败
			printf("realloc fail!");
			exit(-1);
		}
		ps->a = tmp;					 //将返回的新指针赋值给a
		ps->capacity = newcapacity;		 //将新容量赋值给接下来调用的容量
	}
}

 

• 在容量为0的时候，也能扩充。
  

  
  

• 这个 *** 作可以让我们在每次插入新的数据时，都可以直接调用它检查容量是否满了。
  

  
  

• 当然每次容量扩充也不一定是2倍，开始分配的容量也不一定是4，这里是可以自由写的。
  

  
  

 

4、插入数据

//SqList.c
//指定位置插入
void SeqListInsert(SL* ps, int pos, DateType x) {
	SeqListCheckCapacity(ps);
	assert(pos >= 0 && pos <= ps->size);	//当pos<0或者pos>ps->size 程序报错
	for (int end = ps->size; end > pos; end--) {
		ps->a[end] = ps->a[end - 1];		//当在[1,2,3,4]  1位置(a[1])插入0时 2,3,4都得往后退一位
	}
	ps->a[pos] = x; //指定位置插入
	ps->size++;	//有效数据数量加一
}

首先来聊聊 assert()----断言，当括号内为False时将会报错中止程序，当括号内为True时继续程序运行。

 

 

5、删除数据

//SqList.c
//指定位置删除
void SeqListErase(SL* ps, int pos) {
	assert(pos > 0 && pos < ps->size);
	for (int begin = pos; begin < ps->size; begin++) {
		ps->a[begin] = ps->a[begin + 1];  //当在[1,0,2,3,4]  1位置(a[1])删除0时 2,3,4都得往前进一位
	}
	ps->size--;
}

当然你也可以通过更改实参的数据pos-1来实现pos=1,删除a[0]的数据。

 

6、查找数据

//SqList.c
//查找指定数据位置
int SeqListFind(SL* ps, TypeDate x){
	int i = 0;
	while (i < ps->size) {
		if (x == ps->a[i]) {
			return i;
		}
		i++;
	}
	return -1;
}

没有数据返回-1。

配合删除数据，如果有多个数据相同，则可以在测试板块通过以下代码，来实现删除相同数据。

//Test.c
int pos=SeqListFind(&ps, 2);
	while (pos != -1) {
		SeqListErase(&ps, pos);
		pos = SeqListFind(&ps, 2);
	}

7、销毁顺序表

//SqList.c
//销毁顺序表
void SeqListDestroy(SL* ps) {
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

释放指针a指向空间,并将指针a置空,其他数据也赋为这时候的实际值。

三、总结

这是一个简单的动态顺序表，只有顺序表的原理以及具体 *** 作代码的实现，这一块个人感觉简单的理解完后，最重要的还是多敲代码熟练一下。

以上后续随着我的知识面的提升，还会继续改进。

希望对你有帮助。

详细代码：
动态顺序表详细代码