数据结构：线性表和顺序表

一、线性表线性表是一种逻辑结构表示元素与元素之间的相邻关系顺序表和链表是一种存储结构第一个元素具有唯一后继最后一个元素具有唯一前驱中间的元素具有唯一的前驱和后继二、顺序表顺序表是线性表的顺序存储用一段连续的内存空间依次存放数据元素逻辑地址相邻的元素内存地址也相邻优点支持随机访问空间利用率高尾插尾删效率高O(1)缺点扩容代价大头插按位置插删除需要搬动数据适用于适用于需要大量随机访问插入删除操作较少就算需要这些操作也是在尾部进行顺序表的分类分为定容顺序表和可扩容顺序表1. 顺序表的创建1.1 定容顺序表定长数组存储typedef int Elementype; #define N 6 //定容顺序表结构体定义 typedef struct seqlist { //连续存储空间 int arr[N]; //有效元素长度 int length; //最大容量 int maxsize; }seqlist;1.2 可扩容顺序表动态开辟的数组存储//可扩容顺序表 //类型重定义 typedef int Elementype; //初始格子数,初始化时malloc申请的格子数量 #define INTSIZE 10 //顺序表结构体定义 typedef struct seqlist { //内存连续的存储空间 Elementype* arr; //有效元素长度 int length; //最大容量 int maxsize; }seqlist;2. 顺序表的初始化//顺序表的初始化 void Init_seqlist(seqlist* plist) { //1.先安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.申请空间 plist-arr (ElemType*)malloc(INTSIZE * sizeof(ElemType)); //判空 if (plist-arr nullptr) exit(EXIT_FAILURE); //3.有效元素为0 plist-length 0; //4.初始申请的空间个数为 plist-maxsize INTSIZE; }首先要对函数进行安全判断DeBug版本用的是断言release版本用的是if-else判空然后用malloc在堆区购买一片连续的内存空间一开始有效元素个数为0,容量为初始宏定义的个数3. 顺序表扩容//扩容 bool InCrease(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.购买新结点 ElemType* p (ElemType*)realloc(plist-arr, plist-maxsize * 2 * sizeof(ElemType)); //3.判断空间是否申请成功成功的话再将新申请的空间给arr if (p NULL) return false; plist-arr p; //更新容量 plist-maxsize plist-maxsize * 2; return true; }首先需要安全处理然后使用新指针接收realloc购买2倍原来使用malloc和calloc购买的容量的大小注意这里不能是宏的二倍因为如果是宏定义的二倍会导致每一次扩容后的数量都是2*INTSIZE判断空间申请是否成功成功后再将地址传给顺序表否则会导致顺序表丢失4. 判满//判满 bool IsFull(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.若有效元素个数最大容量则已满 return plist-length plist-maxsize; }如果有效元素个数和申请的空间容量相等则已满返回true5. 判空//判空 bool IsEmpty(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.若有效元素个数0则为空 return plist-length 0; }如果有效元素个数0则为空返回true6. 顺序表插入6.1 头插//顺序表头插 bool Insert_head(seqlist* plist,int val) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判满若已满则扩容,如果扩容失败则退出 if (IsFull(plist)) { if (InCrease(plist) false) return false; } //3.将原来顺序表中的元素从尾部开始挨个后移 memmove(plist-arr 1, plist-arr, sizeof(ElemType) * plist-length); //4.再将新的元素插入arr[0] plist-arr[0] val; //5.再更新有效元素个数 plist-length; return true; }首先安全处理然后判满如果已满扩容如果扩容失败直接退出使用memmove将元素从尾部挨个后移【memmove在处理内存折叠时如果目标地址高于源地址从高地址往低地址复制避免未复制就被覆盖的现象】再将val插入空出来的地方再更新有效元素个数6.2 尾插//顺序表的尾插 bool Insert_back(seqlist* plist, int val) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判满 if (IsFull(plist)) { if (InCrease(plist) false) return false; } //3.尾部插入 plist-arr[plist-length] val; //4.更新有效元素个数 plist-length; return true; }首先安全处理然后判满如果已满扩容扩容失败则退出然后直接在尾部插入val插入完成后更新有效元素个数6.3 按位置插//按位置插 bool Insert_pos(seqlist* plist, int val, int pos) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判满 if (IsFull(plist)) { if (InCrease(plist) false) return false; } //3.边界判断 if (pos plist-length 1 || pos 0) return false; //4.在pos位置插入 //2 3 4 5 要在pos3 下标2位置插入 7 //2 3 7 4 5 memmove(plist-arr pos, plist-arr pos - 1, sizeof(ElemType) * (plist-length - pos 1)); plist-arr[pos - 1] val; plist-length; return true; }首先进行安全判断然后判满如果已满扩容扩容失败则退出然后进行位置插入的边界值判断然后将插入位置以及之后的元素从最后一个元素开始挨个往后移一位将val插入有效元素个数7. 顺序表删除7.1 头删//头删 bool delete_head(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.将所有元素从前往后挨个前移一位 memmove(plist-arr, plist-arr 1, sizeof(ElemType) * (plist-length - 1)); //4.更新有效元素个数 plist-length--; return true; }首先安全判断然后判断表是否为空如果表为空直接退出如果表不空将元素从头开始挨个前移然后将有效元素个数减一7.2 尾删//尾删 bool delete_back(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.尾部删除元素个数直接减一 plist-length--; return true; }首先安全判断然后判断表是否为空如果表为空直接退出如果表不空然后将有效元素个数减一7.3 按位置删//按位置删 bool delete_pos(seqlist* plist, int pos) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.判断要删除的位置的界限 if (pos 1 || pos plist-length 1)return false; //4.从前往后元素挨个前移 //2 3 4 5 要删除第3位的 memmove(plist-arr pos - 1, plist-arr pos, sizeof(ElemType) * (plist-length - pos)); //有效元素个数减1 plist-length--; return true; }首先安全判断然后判断表是否为空如果表为空直接退出如果表不空将pos位置之后的元素从前往后依次前移一位有效元素个数减一7.4 按值删只删除这个值出现的第一次//按值删只删除这个值出现的第一次 bool Del_val_first(seqlist* plist,int val) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.查找这个元素第一次出现的位置 int pos search_seqlist(plist, val) 1; //4.删除 memmove(plist-arr pos - 1, plist-arr pos, sizeof(ElemType) * (plist-length - pos)); plist-length--; return true; }首先安全判断然后判断表是否为空如果表为空直接退出如果表不空查找要删除元素的下标(注意此时返回的是下标pos是当前元素的位置所以需要1才是位置)然后赋值给pos将pos位置之后的元素从前往后依次前移一位有效元素个数减一7.4 按值删删除这个值出现的所有//按值删只删除这个值出现的所有次 bool Del_val_ALL(seqlist* plist, int val) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.判空 if (IsEmpty(plist)) return false; //3.将不是val的值存入一个从头开始存 int len 0; for (int i 0; i plist-length; i) { if (plist-arr[i] ! val) plist-arr[len] plist-arr[i]; } //4.更新有效元素个数 plist-length len; return true; }首先安全判断然后判断表是否为空如果表为空直接退出如果表不空申请一个新的计数器将不是val的值从头存入arr有效元素个数更新为计数器的值8. 查找有效元素是否存在遍历整个顺序表有效元素存在返回元素下标不存在返回-1int search_seqlist(seqlist* plist, int val) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.遍历顺序表查找有效元素 for (int i 0; i plist-length; i) { if (plist-arr[i] val)return i; } return -1; }9. 清空将有效元素个数置为0即可//清空 void clear(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } plist-length 0; }10. 销毁释放在堆区申请的空间然后将plist-arrnullptr目的是为了避免二次释放然后将有效元素个数和容量置为0即可//销毁 void Dstory(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.释放堆空间 free(plist-arr); plist-arr nullptr; plist-length 0; plist-maxsize 0; }11. 打印顺序表//打印函数 void show(seqlist* plist) { //1.安全处理 assert(plist ! nullptr); if (plist nullptr) { exit(EXIT_FAILURE); } //2.循环打印 printf(当前顺序表中的元素有); for (int i 0; i plist-length; i) { printf(%d , plist-arr[i]); } printf(\n); }12. 测试int main() { seqlist s; Init_seqlist(s); printf(length%d maxsize%d\n, s.length, s.maxsize); Insert_head(s, 2); show(s); Insert_back(s, 3); Insert_back(s, 4); Insert_back(s, 5); Insert_back(s, 3); Insert_back(s, 4); Insert_back(s, 5); Insert_back(s, 3); Insert_back(s, 4); Insert_back(s, 5); show(s); Insert_pos(s, 7, 1); show(s); delete_head(s); show(s); delete_pos(s, 4); show(s); Del_val_first(s, 4); show(s); Del_val_ALL(s, 3); show(s); clear(s); printf(%d\n,s.length); Dstory(s); }