数据结构-顺序表详解专题

目录

顺序表

1.简单了解顺序表

2.顺序表的分类

2.1静态顺序表

2.2动态顺序表

2.3typedef命名作用

3.动态顺序表的实现

SeqList.h

SeqList.c

test.c

---

顺序表

1.简单了解顺序表

顺序表是线性表的一种，线性表是在逻辑上是线性结构，在物理逻辑上并不是一定连续的。

顺序表的低层结构是数组，对数组的封装，实现了对数据的增删查改等功能。

2.顺序表的分类

顺序表可以分为静态顺序和动态顺序表

2.1静态顺序表

#define MAX 100
typedef int SLDataType;
//静态顺序表
typedef struct SeqList
{SLDataType a[MAX];//这个是开辟100大小的空间，而不是已经使用有效的空间int size; //计算存放的有效数据
}SL;

静态顺序表缺陷：空间给少了不够用会造成数据丢失，给多了造成空间浪费。

2.2动态顺序表

//动态顺序表
typedef struct SeqList
{SLDataType * arr; //类似于数组指针，作为存储数据的低层结构int capacity;//容量，记录顺序表的空间大小，也就是要开辟的空间大小int size;//就是记录当前存放了多少有效数据。
}SL;
//两种相同的命名写法。
//typedef sturuct SeqLits SL;

动态顺序表能够实现需要使用空间时候开辟，这样更方便数据的管理，所以推荐用动态顺序表。

2.3typedef命名作用

为什么要用typedef呢

因为当你写int的一堆代码，如果想要把int改成char类型的时候，如果没用到typedeff的话，就要一个一个的改，如果使用了typedef的话直接修改int 换成char就可以了。

3.动态顺序表的实现

分成了三个板块，分别为SeqList.h , SeqList.c ,test.c

SeqList.h

//动态顺序表
typedef struct SeqList
{SLDataType * arr; //类似于数组指针，作为存储数据的低层结构int capacity;//容量，记录顺序表的空间大小，也就是要开辟的空间大小int size;//就是记录当前存放了多少有效数据。
}SL;
//两种相同的命名写法。
//typedef sturuct SeqLits SL;
void SLinit(SL *ps);
void SLPrint(SL* ps); //打印void SLPushBack(SL * ps ,SLDataType x);  //尾插 
void SLPushFront(SL* ps, SLDataType x);  //头插
void SLCheckcapacity(SL* ps); //扩容void SLPopBack(SL* ps); //尾删
void SLPopFront(SL* ps); //头删void SLInsert(SL* ps, int pos, SLDataType x);//指定位置插入
void SLErase(SL* ps, int pos);//指定位置删除void SLFind(SL* ps, SLDataType x);//查找
void SLDestroy(SL* ps);//销毁void SLAlter(SL* ps, int pos, SLDataType x);//修改数据

SeqList.c

#include "Sqlist.h"
//初始化
void SLinit(SL* ps)
{ps->arr = NULL;ps->capacity = 0;ps->size = 0;}
//打印
void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d  ", ps->arr[i]);}printf("\n");
}/扩容放在这里，因为等下头插也会用到，设置成公共的，减少代码
void SLCheckcapacity(SL *ps)
{//扩容//先判断是不是空间满了if (ps->size == ps->capacity){//扩容先给arr申请开劈空间 SLDataType * arr; //realloc头文件 stdlib.h,  void  realloc (这是要在已有的空间情况下继续扩容，扩容的大小)//ps->arr = (SLDataType*)realloc(ps->arr,2* ps ->capacity  );//扩容2倍2* ps ->capacity//但是上面这个是不可取的，因为ps ->capacity刚刚被初始化现在为0。//因此要事先判断当 ps ->capacity为0 时，要先赋值,如果不为0 那么开辟2倍的空间int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; //三目运算符/*ps->arr = (SLDataType*)realloc(ps->arr, newcapacity);*///这样写还是不够准确，这个时候newcapacity是比特大小，不是字节，//这个时候要* 一个sizeof(SLDataType),因为要类型的大小字节不同/*ps->arr = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));*///即使这样还是不行，因为你不知道是否申请成功，所以还要创建一个临时变量，然后进行判断realloc是否成功SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));//判断realloc是否申请空间成功if (tmp == NULL)//如果没空那么是没成功{perror("realloc fail!"); //这个为啥这么写还真不知道exit(1); //扩容失败直接中断程序}//到这步说明已经申请空间成功//free(ps->arr);//不需要这个，realloc他会自己销毁ps->arr = tmp;ps->capacity = newcapacity;}
}//尾插
//参数列表中有一个指向SL结构体的指针ps，
//和一个用来存储数据的参数x。
//函数内部先用assert函数判断st是否为空，
//然后判断栈是否已经满了。如果栈满了，
//就进行扩容操作，将原数组大小翻倍(如果原来大小是0则扩容为4)，
//然后利用realoc函数重新分配内存空间，并将原数组中的数据拷贝到新的空间中。,拷贝的时候要销毁空间
//最后将数据x压入栈的顶部，并将栈顶指针top加一。
void SLPushBack(SL* ps, SLDataType x) //用来存储数据的参数x，x是用来插入数据的内容
{//assert 如果不成立那么会直接中断报错，并且会说明在哪里错误。//assert(ps);assert(ps != NULL); //温柔的判断解决，不会报错/*if (ps != NULL){return;}*///尾插分为情况//1.第一个是空间已经满了需要扩容//2.第二个是还有空间，直接在尾部，也就是ps -> size 位置插入即可。//空间不够SLCheckcapacity(ps);//空间没有满，直接进行尾插ps->arr[ps->size] = x; //为啥存放到arr里面，那capacity干嘛的//arr是结构体指针指向的是地址然后用来存放内容的，capacity只是用来存放目前空间大小的容量而已ps->size++;}
//头插
void SLPushFront(SL* ps, SLDataType x)
{//头插也是两种情况，一种是满了要开空间，另一种是没满，要把旧数据往后移动，然后留首位置插入assert(ps != NULL);SLCheckcapacity(ps);//将旧数据往后移动，从后面开始移动for (int  i = ps->size ; i > 0 ; i--) //让i指向size位置。{ps->arr[i] = ps->arr[i - 1]; //让i-1位置移动到i位置，就是往后移动一个位置。}ps->arr[0] = x; //首位置放新元素，头插ps->size++;
}//尾删
void SLPopBack(SL* ps)
{//两种情况，第一种是全为空，无法删除，第二种是直接可以删尾部数据assert(ps != NULL);assert(ps->size != 0);//顺序表不能为空//进行第二种情况//ps->arr[ps->size - 1] = NULL; //当size --，那么即使size位置里面有数据，也不会影响打印，插入，删除//因为默认size位置是不进行处理的。相当于看不见等于没有ps->size--;}void SLPopFront(SL* ps)
{//两种情况，第一种是全为空，无法删除，第二种是删除头部，把数据往前移动assert(ps != NULL);assert(ps->size != 0);//顺序表不能为空for (int i = 0 ; i < ps ->size -1 ; i++) //因为size要往前移动一个，i最大只能说ps ->size-2{ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
//在指定位置插入元素
void SLInsert(SL* ps, int pos, SLDataType x)
{assert(ps);//要限制pos的大小，不然会出错，pos要小于size，也要大于0assert(pos >= 0 && pos <= ps->size);//扩容SLCheckcapacity(ps);//首先要知道要插入的pos位置，然后把pos后面的数据往后移动，留pos位置插入for (int i = ps->size; i > pos; i--){//最后一位size，所以从size开始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 );//让pos后面的数据往前移动for (int i = pos ; i < ps->size - 1 ; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}
//查找
void SLFind(SL* ps, SLDataType x)
{assert(ps);//判断顺序表是否为空for (int  i = 0; i < ps->size; i++){if (ps->arr[i] == x)//判断是否有该元素{printf("查找成功，该元素下标为%d \n", i);return;}}//全部查找一遍。printf("查找失败。不存在该元素。 \n");
}//销毁
void SLDestroy(SL* ps)
{//先判断是否为空表，然后释放arr的空间，接着就是让arr指向nullassert(ps);//if (ps->arr != NULL)if (ps->arr){free(ps->arr);}ps->arr = NULL;ps->capacity = ps->size = 0;}
//修改
void SLAlter(SL* ps, int pos, SLDataType x)
{assert(ps);//先找到对应的数据，然后修改for (int i = 0; i < ps->size; i++){if (ps->arr[i] == pos){ps->arr[i] = x;}}}

test.c

#include "Sqlist.h"
void slinit()
{SL sl;
SLinit(&sl);//ctrl +d 快速复制//测试尾插
SLPushBack(&sl, 1); //因为是int类型，一开始空间是四个
SLPushBack(&sl, 2);
SLPushBack(&sl, 3);
SLPushBack(&sl, 4);
/*SLPushBack(&sl, 1);
SLPushBack(&sl, 1);*/
SLPrint(&sl);
//当传过去的是null空地址
//SLPushBack(NULL, 4); //传空地址乱码，要用accert判断
/*SLPushBack(&sl, 5);
SLPrint(&sl);*///测试头插
SLPushFront(&sl, 5);
SLPushFront(&sl, 6);
SLPushFront(&sl, 7);
SLPrint(&sl);//测试尾删
/*SLPopBack(&sl);
SLPopBack(&sl);
SLPopBack(&sl);
SLPrint(&sl);*///测试头删
SLPopFront(&sl);
SLPopFront(&sl);
SLPrint(&sl);
//测试指定位置插入
SLInsert(&sl, 0, 102);
SLInsert(&sl, 3, 15);
SLInsert(&sl, 4, 22);
SLPrint(&sl);//测试指定位置删除
SLErase(&sl, 0);
SLErase(&sl, 2);
SLPrint(&sl);//测试查找
SLFind(&sl, 2);//测试修改
SLAlter(&sl, 2, 3);
SLPrint(&sl);//测试销毁
SLDestroy(&sl);
SLPrint(&sl);
}
int main()
{slinit();return 0;
}