数据结构---顺序表

目录1.线性表2.顺序表2.1动态顺序表初始化销毁扩容尾插头插尾删头删在指定位置pos插入元素在指定位置pos删除元素查找元素打印1.线性表线性表linear list是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串...线性表在逻辑上是线性结构也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。2.顺序表顺序表是用一段物理地址连续的存储单元依次存储数据元素的顺序结构一般情况下采用数组存储在数组上完成数据的增删查改。其中顺序表分为动态顺序表和静态顺序表静态顺序表使用定长数组存储元素缺陷开少了不够用、开多了浪费动态顺序表使用动态开辟的数组存储按需申请2.1动态顺序表关于动态顺序表这里我们要定义一个结构体其中的空间问题不是直接利用数组去开辟由于定义数组空间是固定的不利于后面的操作增删改查//定义的结构体 typedef int SLDataType;//方便调整类型 //动态顺序表按需申请 typedef struct SeqList { SLDataType* arr;//使当前顺序表方便扩容/调整类型 int size; //有效数据个数 int capacity; //空间容量 }SL;初始化void SLInit(SL* ps) { ps-arr NULL; ps-size ps-capacity 0; }销毁//顺序表的销毁 void SLDestroy(SL* ps) { if (ps-arr) //等价于 if(ps-arr ! NULL) { free(ps-arr); } ps-arr NULL; ps-size ps-capacity 0; }动态顺序表空间是我们自己申请的使用结束的时候都需要进行释放将空间使用权限归还给操作系统否则就会导致内存泄漏。扩容判断是否扩容这是比静态顺序表多出来的在动态顺序表中我们要扩容就要自己进行调节void SLCheckCapacity(SL* ps) { //插入数据之前先看空间够不够 if (ps-capacity ps-size) { //申请空间 //malloc calloc realloc int arr[100] ---增容realloc //三目表达式 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 SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps);//进行容量检查 //ps-a[ps-size] x; //ps-size; ps-arr[ps-size] x; }尾插时需要先判断顺序表是否满了满了要先进行扩容才能继续进行扩容。size表示有效元素个数同时也是顺序表中最后一个元素后一个位置的下标。成功插入后要对有效数据个数size加一。头插//头插 void SLPushFront(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); //先让顺序表中已有的数据整体往后挪动一位 for (int i ps-size; i 0; i--) { ps-arr[i] ps-arr[i - 1];//arr[1] arr[0] } ps-arr[0] x; ps-size; }头插需要先进行容量检查再把原顺序表中的元素全部往后挪动一位最后再进行插入。尾删//尾删 void SLPopBack(SL* ps) { //assert(ps-size 0)//暴力检查 if (ps-size 0)//如果size0说明顺序表已经没有数据了也就不用再尾删 { return; } ps-size--; }头删void SLPopFront(SL* ps) { assert(ps); assert(ps-size); //数据整体往前挪动一位 for (int i 0; i ps-size-1 ; i) { ps-arr[i] ps-arr[i 1]; //arr[size-2] arr[size-1] } ps-size--; }头删需要从第二个元素开始把后面的所有元素往前挪动一位。在指定位置pos插入元素//在pos位置处插入 void SLInsert(SL* ps, int pos, SLDataType x) { assert(ps); assert(pos 0 pos ps-size); SLCheckCapacity(ps); //把从pos位置开始的所有数据往后挪动一位 int end ps-size - 1; while (end pos) { ps-arr[end 1] ps-arr[end]; end--; } ps-arr[pos] x; ps-size; }在指定位置pos删除元素//删除pos位置元素 void SLErase(SL* ps, int pos) { assert(ps); assert(pos 0 pos ps-size);//size位置不能删不是顺序表中的有效位置 //把pos位置后面的所有元素往前挪动一位 int str pos 1; while (str ps-size) { ps-arr[str - 1] ps-arr[str]; str; } ps-size--; }查找元素//查找 int SLFind(SL* ps, SLDataType x) { assert(ps); int str 0; while (str ps-size) { if (ps-arr[str] x) { return str; } str; } return -1; }打印void SLPrint(SL s) { for (int i 0; i s.size; i) { printf(%d , s.arr[i]); } printf(\n); }