顺序表

• 顺序表
• • 顺序表初始化
  • 顺序表的销毁
  • 顺序表的头/尾插
  • 顺序表的头/尾删
  • 顺序表插入数据
  • 顺序表查找数据
• 顺序表完整代码

顺序表

顺序表是线性表的一种。
线性表:具有相同特性的数据结构，线性表在逻辑结构上一定是连续的，在物理结构上不一定是连续的。
顺序表：用顺序存储的方式实现线性表，把逻辑上相邻的两个变量在物理位置也相邻的存储。

顺序表的底层是数组
（文章结尾处放完整代码）
顺序表分类：

• 静态顺序表：底层是一个静态数组。静态顺序表并不方便，当数组的空间给大时，会造成空间浪费；当数组的空间给小了，会造成数据的丢失。

• 动态顺序表：一个指针，动态开辟内层。可以动态的增容。

创建一个顺序表：
(静态顺序表顺序表)

typedef struct SeqList { 	int arr[100]; 	int size;//记录的是顺序表有效数据个数 	int capacity;//记录的是有效空间大小 } 

静态顺序表这里不过多阐述，主要动态顺序表。

typedef int SLDatatype;//为什么要对Int重命名？ typedef struct SeqList { 	SLDatatype* arr; 	SLDatatype size;//记录的是顺序表有效数据个数 	SLDatatype capacity;//记录的是有效空间大小 } 

为什么要对int重命名？如果我们后面需求变更，要在顺序表中存储的数据类型是char类型，只需要修改typedef int SLDatatype;即可。

顺序表初始化

void SeqListInit(SL* ps) { 	ps->arr = NULL; 	ps->size = ps->capacity = 0; } 

为什么要对顺序表初始化？我们知道，顺序表的空间是我们动态内层分配的来的，在将这块空间分配给顺序表前，这块空间中可能已经存储了其他值（脏数据），那么，我们在使用顺序表的时候可能会得到一些不是我们想要的值。

顺序表的销毁

//顺序表的销毁 void SeqListDestory(SL* ps) { 	if (ps->arr) 	{ 		free(ps->arr); 	} 	ps->capacity = ps->size = 0; } 

在使用完顺序表后，要将空间归还，否则会造成内存泄漏。如果不归还，可能在当下不会有什么问题，但时间久了，被占用的空间多了，程序就会出现问题。

顺序表的头/尾插

 void SLCheckCapacity(SL* ps)//检查顺序表的空间是否足够 { 	if (ps->capacity == ps->size)//如果空间不足，则增容。当有效数据个数与顺便的空间大小相等时，表示空间以用完。 	{ 		int newCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity); 		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype)); 		if (tmp == NULL) 		{ 			perror("realloc Fail"); 			exit(1); 		} 		ps->arr = tmp; 		ps->capacity = newCapacity; 	} }  void SeqPushBack(SL*ps,SLDatatype x)//尾插 { 	assert(ps);//传入的数值不能为NULL，因为不能对空指针解引用 	SLCheckCapacity(ps);//检查顺序表空间是否足够 	ps->arr[ps->size++] = x; } void SeqPushFront(SL*ps,SLDatatype x)//头插 { 	assert(ps); 	SLCheckCapacity(ps);//检查顺序表空间是否足够  	for (int i = ps->size; i > 0; i--) 	{ 		ps->arr[i] = ps->arr[i - 1]; 	} 	ps->arr[0] = x; 	ps->size++; } 

顺序表的头/尾删

void SeqPopBcack(SL*ps)//尾删 { 	assert(ps); 	assert(ps->size); 	//ps->arr[ps->size - 1] = 0;  可要可不要 	ps->size--;//当作数组来理解，就是把数组的长度减1 }  void SeqPopFront(SL*ps)//头删 { 	assert(ps); 	assert(ps->size); 	for (int i = 0; i < ps->size - 1; i++) 	{ 		ps->arr[i] = ps->arr[i + 1];//当作数组来理解，头删就是将所有数据前移一位，第一个数据直接被后面的数据覆盖掉。 	} 	ps->size--; } 

顺序表插入数据

void SLInsert(SL*ps,SLDatatype x,int pos)//在指定位置之前插入数据 { 	assert(ps); 	assert(pos >= 0 && pos <= ps->size); 	SLCheckCapacity(ps); 	for (int i = ps->size; i > pos; i--)//当作数组来理解，就是从pos下标处开始，（包括pos下标处），每个元素后移一位，再在pos处插入数据 	{ 		ps->arr[i] = ps->arr[i - 1]; 	} 	ps->arr[pos] = x;//在Pos位置插入数据 	ps->size++; } void SLErase(SL *ps,int pos)//删除指定位置的数据 { 	assert(ps); 	assert(pos >= 0 && pos < ps->size); 	for(int i=pos;isize-1;i++) 	{ 		ps->arr[i] = ps->arr[i + 1];//当作数组,就是从pos下标开始(不包括pos下标位置)，每个元素前移一位，把Pos位置处的数据覆盖掉 	} 	ps->size--; } 

顺序表查找数据

int SLFind(SL *ps,SLDatatype x )//查找数据 { 	assert(ps); 	for (int i=0;isize;i++) 	{ 		if (ps->arr[i]==x) 		{ 			return i; 		} 	} 	return -1; } 

顺序表完整代码

将顺序表的代码分别放在两个个文件下，一个.h头文件，一个.c文件，最好在创建一个test.c文件对顺序表代码进行测试就行了。
SeqList.h文件 头文件

#pragma once #include #include #include   typedef int SLDatatype;  //顺序表 typedef struct SeqList { 	SLDatatype* arr; 	SLDatatype size;//元素个数 	SLDatatype capacity;//空间大小 }SL;  void SeqPrint(SL ps);//打印  void SeqListInit(SL*ps);//顺序表初始化  void SeqListDestory(SL*ps);//顺序表的销毁  void SeqPushBack(SL*ps,SLDatatype x);//尾插 void SeqPushFront(SL*ps,SLDatatype x);//头插  void SeqPopBcack(SL*ps);//尾删 void SeqPopFront(SL*ps);//头删  void SLInsert(SL*ps,SLDatatype x,int pos);//在指定位置之前插入数据 void SLErase(SL *ps,int pos);//删除指定位置的数据  int SLFind(SL *ps,SLDatatype x );//查找数据 

SeqList.c文件，放的是顺序表函数的实现

#include"SeqList.h"  void SeqPrint(SL ps) { 	for (int i=0;i 		printf("%d ", ps.arr[i]); 	} 	printf("\n"); }  //顺序表的初始化 void SeqListInit(SL* ps) { 	ps->arr = NULL; 	ps->size = ps->capacity = 0; }   //顺序表的销毁 void SeqListDestory(SL* ps) { 	if (ps->arr) 	{ 		free(ps->arr); 	} 	ps->capacity = ps->size = 0; }  void SLCheckCapacity(SL* ps) { 	 	if (ps->capacity == ps->size) 	{ 		int newCapacity = (ps->capacity == 0 ? 4 : 2 * ps->capacity); 		SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype)); 		if (tmp == NULL) 		{ 			perror("realloc Fail"); 			exit(1); 		} 		ps->arr = tmp; 		ps->capacity = newCapacity; 	} }  //尾插 void SeqPushBack(SL* ps, SLDatatype x) { 	assert(ps); 	SLCheckCapacity(ps); 	ps->arr[ps->size++] = x; }  //头插 void SeqPushFront(SL* ps, SLDatatype x) { 	assert(ps); 	SLCheckCapacity(ps);  	for (int i = ps->size; i > 0; i--) 	{ 		ps->arr[i] = ps->arr[i - 1]; 	} 	ps->arr[0] = x; 	ps->size++;  }  void SeqPopBcack(SL* ps)//尾删 { 	assert(ps); 	assert(ps->size); 	//ps->arr[ps->size - 1] = 0;  可要可不要 	ps->size--;  }   void SeqPopFront(SL* ps)//头删 { 	assert(ps); 	assert(ps->size); 	for (int i = 0; i < ps->size - 1; i++) 	{ 		ps->arr[i] = ps->arr[i + 1]; 	} 	ps->size--; }  void SLInsert(SL* ps, SLDatatype x, int pos)//在指定位置之前插入数据 { 	assert(ps); 	assert(pos >= 0 && pos <= ps->size); 	SLCheckCapacity(ps); 	for (int i = ps->size; i > pos; i--) 	{ 		ps->arr[i] = ps->arr[i - 1]; 	} 	ps->arr[pos] = x; 	ps->size++; } void SLErase(SL* ps, int pos)//删除指定位置的数据 { 	assert(ps); 	assert(pos >= 0 && pos < ps->size); 	for(int i=pos;isize-1;i++) 	{ 		ps->arr[i] = ps->arr[i + 1]; 	} 	ps->size--; }  int SLFind(SL* ps, SLDatatype x)//查找数据 { 	assert(ps); 	for (int i=0;isize;i++) 	{ 		if (ps->arr[i]==x) 		{ 			return i; 		} 	} 	return -1; } 

test.c测试文件，这个文件可以不用看了，但是为了文章的完整性，所有我写在了这里。

#include"SeqList.h"  void test1() { 	SL s; 	SeqListInit(&s); 	/* 	SeqPushBack(&s,1); 	SeqPushBack(&s,2); 	SeqPushBack(&s,3); 	SeqPushBack(&s,4); 	SeqPrint(s);*/  	SeqPushFront(&s,1); 	SeqPushFront(&s,2); 	SeqPushFront(&s,3); 	SeqPrint(s);  	//SeqPopBcack(&s); 	//SeqPrint(s);  	//SeqPopBcack(&s); 	//SeqPrint(s);  	//SeqPopBcack(&s); 	//SeqPrint(s);  	//SeqPopBcack(&s); 	//SeqPrint(s);  	/*1111*/  	/*SeqPopFront(&s); 	SeqPrint(s);*/   	/*SLInsert(&s,9,s.size); 	SeqPrint(s); 	SLErase(&s,s.size-1); 	SeqPrint(s);*/  	int find=SLFind(&s,2); 	if (find==-1) 	{ 		printf("没找到"); 	} 	else 	{ 		printf("找到了"); 	}  	SeqListDestory(&s); }  int main() { 	test1(); 	return 0; }