当前位置:   article > 正文

数据结构 --- c语言实现顺序表_定义一个数组,模拟为顺序表c语言怎么写

定义一个数组,模拟为顺序表c语言怎么写

线性表

  • 零个或多个数据元素 组成的有限序列,除了头部元素和尾部元素之外,其他的所有元素只有一个前驱元素(前面那个数据)

  • 线性表包括数据结构中的:数组,单链表,双链表 ,循环链表(尾部可以指向头部)等

顺序表(数组的操作)

  • 也是一个线性表

  • 用数组描述数据元素物理存储的连续性,实际上就是一个数组的操作

  • 理解为数组的操作即可 ---> 用来封装数组的常规操作(增、删、改、查)

  • 采用顺序存储描述的线性表叫做顺序表

  • 要知道顺序表的长相,抽象结构体代码的根本

45只有一个前驱元素(45前面只有一个元素12)

广义表(线性表的拓展)

  • 对前驱节点 | 前驱元素无任何限制

  • 深度的概念:看( )个数,不是看元素个数

了解广义表的表示方式:

  • 空表 E = ();  深度0

  • L = (a,b) 或  L (a,b);两个元素的表,表示:表中有a,b两个元素,长度为2      深度1

  • A = (x,L) = (x,(a,b));广义表中还有一个表叫L表,A表中有2个元素(其中一个为正常的数据,称为原子,另一个还是一个表)     深度2

  • B = (A,L) = ((a,b),(a,b,c));其他的组合情况:有两个子表,A表中有2个元素,L表中有3个元素    深度2

顺序表的实现

  • 用数组描述

  • maxSize:记录最大容量的变量

  • curSize:记录当前元素个数的变量(容器)

  • (顺序表中的定义需要有一个一级指针去做内存申请):定义一个数组指针 | 动态内存申请变成一个数组

sqlist.h

  1. #pragma once
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <assert.h> //断言|用于判空处理|申请内存可能失败
  5. #define MAX 10 //最大元素个数
  6. typedef int DataType; //数据通用性处理|可以给数据类型定义别名
  7. //结构体的抽象->抽象长相
  8. enum INFO {OK=1,ERROR=-1}; //枚举变量类型 -1:错误信息
  9. typedef struct
  10. {
  11. DataType* dataMemory; //一级指针动态内存申请变成一维数组
  12. int maxSize; //最大元素个数->容量
  13. int curSize; //当前元素个数
  14. }Sqlist,*LPSqlist; //结构体的别名|结构体指针别名

创建顺序表 

  • 用一个指针表示一个结构体变量,返回的是一个指针,创建过程就是初始化数据,有几个数据成员就给几个数据成员初始化即可

  • 任何一种结构都是一个结构体变量,只是表达方式不一样

  1. //声明
  2. LPSqlist createSqlist(int maxSize);
  3. //实现
  4. LPSqlist createSqlist(int maxSize) //参数:最大值
  5. {
  6. //创建过程,就是初始化数据->动态内存申请把指针变成变量
  7. LPSqlist sqlist = (LPSqlist)malloc(sizeof(Sqlist));
  8. assert(sqlist); //断言处理
  9. //给变量中的东西初始化
  10. sqlist->curSize = 0;
  11. sqlist->maxSize = maxSize;
  12. //指针变成一个数组->数组的内存需要二次申请
  13. sqlist->dataMemory = (DataType*)malloc(sizeof(DataType)*maxSize);
  14. assert(sqlist->dataMemory);
  15. return sqlist;
  16. }
  17. //sqlist中的一级指针也需要做内存申请 申请为数组从而可以存放多个数据

任何数据结构中都有的万金油函数 

  1. //声明
  2. int size(LPSqlist sqlist); //获取当前的元素个数(或者返回bool类型)
  3. int empty(LPSqlist sqlist); //判断是否为空
  4. //实现
  5. int size(LPSqlist sqlist)
  6. {
  7. if (sqlist == NULL) //大前提:sqlist不等于空
  8. return ERROR;
  9. return sqlist->curSize;
  10. }
  11. int empty(LPSqlist sqlist)
  12. {
  13. if (sqlist == NULL)
  14. return ERROR;
  15. return sqlist->curSize==0; //判断当前的curSize是不是为0
  16. }

顺序表的增删改查的实现  

获取顺序表中的元素---通过下标去获取元素

  • 参数:获取哪个顺序表中的元素 

  • 注意:表不能为空 & 下标是否满足要求

  • 下标不合格的情况:当前元素个数 curSize < 要访问的下标 index

  1. //声明
  2. DataType getData(LPSqlist sqlist, int index);
  3. //实现
  4. //参数: LPSqlist sqlist:获取哪个顺序表中的元素 int index:通过下标去获取元素
  5. DataType getData(LPSqlist sqlist, int index)
  6. {
  7. if (sqlist == NULL||sqlist->curSize==0) //为空(短路)
  8. {
  9. printf("sqlist is empty,unable to get......\n"); //错误提示 无法获取
  10. return ERROR;
  11. }
  12. if (sqlist->curSize < index) //下标是否满足要求?
  13. {
  14. printf("index is invalid,unable to get......\n"); //错误提示 invalid无效
  15. return ERROR;
  16. }
  17. //注意:index是第几个元素 第1个元素,第2个元素...没有第0个元素的概念
  18. return sqlist->dataMemory[index-1]; //下标正确 直接返回
  19. }

无序顺序表的插入

  • 元素不存在顺序,直接插到顺序表中即可

  • 参数:插入的顺序表 插入的下标  插入的数据

  • 顺序表的插入操作就是数组的插入操作

  • 数组实现的数据结构,放进去要考虑满的状态(链表不需要),拿出来要考虑空的状态

方案1 (依次交换)

  • 把要插入的元素放在最后面      

  • 让最后面的元素一直与前面的元素依次交换到指定的位置

  1. int insertSqlist(LPSqlist sqlist, int index, DataType data)
  2. {
  3. //大前提:无法插入
  4. if (sqlist == NULL)
  5. {
  6. printf("sqlist is empty,unable to insert......\n");
  7. return ERROR;
  8. }
  9. //满的情况:无法插入
  10. if (sqlist->curSize == sqlist->maxSize)
  11. {
  12. printf("sqlist is full,unbale to insert......\n");
  13. return ERROR;
  14. }
  15. //index==0 curSize==0 第一次插入特殊情况需要做判断
  16. if (index == 0)
  17. {
  18. sqlist->dataMemory[sqlist->curSize++] = data; //插入数据 后置++即可
  19. return OK;
  20. }
  21. //index为其他值,看下标是否满足要求 第一次插只能用index == 0的情况
  22. if (sqlist->curSize < 1 || sqlist->curSize < index)
  23. {
  24. printf("index is invalid,unable to insert......\n"); //下标无效 无法做插入
  25. return ERROR;
  26. }
  27. //其他情况正常插入
  28. int pos = sqlist->curSize; //pos==最后一个下标
  29. sqlist->dataMemory[pos] = data; //插在最后面 直接把元素插在当前下标下即可
  30. //调整位置
  31. while (pos != index)
  32. { //定义一个temp做交换
  33. DataType temp = sqlist->dataMemory[pos]; //第5个元素(index[0]-[4])
  34. sqlist->dataMemory[pos] = sqlist->dataMemory[pos - 1]; //交换pos和pos-1的位置
  35. sqlist->dataMemory[pos - 1] = temp; //把pos-1的值置为temp
  36. pos--;
  37. }
  38. sqlist->curSize++; //插入成功后curSize++
  39. }
  40. /*测试代码 参数:插入的下标 插入的元素 都是在第1个位置插入
  41. 第一次插入在下标[0]插入0 第一个元素
  42. 在第1个位置插入1
  43. 在第1个位置插入2
  44. 在第4个位置插入444
  45. ...*/
  46. LPSqlist sqlist = createSqlist(MAX);
  47. printf("test insert:\n");
  48. insertSqlist(sqlist, 0, 0); //0
  49. insertSqlist(sqlist, 1, 1); //1 0
  50. insertSqlist(sqlist, 1, 2); //2 1 0
  51. insertSqlist(sqlist, 1, 3); //3 2 1 0
  52. insertSqlist(sqlist, 4, 444); //3 2 1 444 0
  53. printSqlist(sqlist);

方案2 (挪位置)

  • 在第3个位置插入666 
  • 先挪位置,再做插入 把最后一个元素999挪到curSize的位置,再把77挪到999的位置...

  • 要从后面的元素开始挪(把k-1的值赋给k),如果从前面的元素开始挪,25会把77覆盖

  1. for (int k = sqlist->curSize; k >= index; k--)
  2. {
  3. sqlist->dataMemory[k] = sqlist->dataMemory[k - 1]; //把k-1的值赋给k
  4. }
  5. sqlist->dataMemory[index - 1] = data; //插入的第几个元素:在数组下标中一定是index-1
  6. sqlist->curSize++;
  7. return OK;

顺序表的打印---数组的打印

  1. void printSqlist(LPSqlist sqlist)
  2. {
  3. if (sqlist == NULL||sqlist->curSize==0) //两种为空的情况 无法打印
  4. {
  5. printf("sqlist is empty,unable to print......\n");
  6. return;
  7. }
  8. //能够打印
  9. for (int i = 0; i < sqlist->curSize; i++)
  10. {
  11. printf("%d\t", sqlist->dataMemory[i]); //打印数组
  12. }
  13. printf("\n");
  14. }

顺序表的删除(伪删除)---数组没有办法释放单一内存

  • 参数:要删除的表 要删除第几个元素(通过序号做删除)

  • 25是要删除的位置,先把77挪到25的位置,再把999挪到77的位置 

  • 只是77把25给覆盖了(逻辑上的删除),没有处理999的内存,元素999还在

  • 真正的删除是curSize从5变成了4,把记录大小的curSize做 - - 运算

  1. int deleteSqlist(LPSqlist sqlist, int index)
  2. {
  3. if (sqlist == NULL || sqlist->curSize == 0) //表为空无法删除
  4. {
  5. printf("sqlist is empty,unable to delete......\n");
  6. return ERROR;
  7. }
  8. if (sqlist->curSize < index) //判断下标是否满足规则
  9. {
  10. printf("index is invalid,unbale to delete......\n");
  11. return ERROR;
  12. }
  13. for (int k = index - 1; k < sqlist->curSize; k++)
  14. {
  15. sqlist->dataMemory[k] = sqlist->dataMemory[k + 1]; //把k+1的值挪到k的位置
  16. }
  17. sqlist->curSize--; //伪删除
  18. return OK;
  19. }
  20. //测试代码
  21. printf("test delete:\n"); //3 2 1 444 0
  22. deleteSqlist(sqlist, 4); //3 2 1 0
  23. printSqlist(sqlist);

头插 & 尾插 

  1. void push_front(LPSqlist sqlist, DataType data) //头部插入
  2. {
  3. insertSqlist(sqlist, 1, data); //在第一个位置插入数据
  4. }
  5. void push_back(LPSqlist sqlist, DataType data) //尾部插入
  6. {
  7. if (sqlist == NULL) //为空无法插入
  8. {
  9. printf("sqlist is empty,unable to pushback");
  10. return;
  11. }
  12. if (sqlist->curSize == sqlist->maxSize) //满了也无法做插入
  13. {
  14. printf("sqlist is full,unable to pushback");
  15. return;
  16. }
  17. sqlist->dataMemory[sqlist->curSize++] = data; //能够插入 插在最后面 后置++
  18. }
  19. //测试代码
  20. printf("test push:\n");
  21. push_front(sqlist, 666); //666 3 2 1 0
  22. push_back(sqlist, 999); //666 3 2 1 0 999
  23. printSqlist(sqlist);

头删 & 尾删 

  1. void pop_front(LPSqlist sqlist) //头部删除
  2. {
  3. deleteSqlist(sqlist, 1); //删除第一个位置
  4. }
  5. void pop_back(LPSqlist sqlist) //尾部删除
  6. {
  7. deleteSqlist(sqlist, sqlist->curSize); //删除最后一个位置
  8. }
  9. //测试代码
  10. pop_front(sqlist); //666 3 2 1 0 999
  11. pop_back(sqlist); //3 2 1 0 999
  12. printSqlist(sqlist); //3 2 1 0

顺序表的查找---通过元素去找下标 

  • 按数据去查找,返回找到数据的下标

  1. int searchSqlist(LPSqlist sqlist, DataType data)
  2. {
  3. if (sqlist == NULL) //为空无法查找
  4. {
  5. printf("sqlist is empty,unable to search......\n");
  6. return ERROR; //数组下标没有-1
  7. }
  8. //遍历数组
  9. for (int i = 0; i < sqlist->curSize; i++)
  10. {
  11. if (sqlist->dataMemory[i] == data) //当前元素==data
  12. {
  13. return i; //返回下标
  14. }
  15. }
  16. return ERROR; //没找到返回ERROR
  17. }
  18. //测试代码
  19. int pos = searchSqlist(sqlist, 3); //查找元素:3
  20. printf("pos:%d\n", pos); //输出:元素3在数组下标[0]的位置 pos:0

有序顺序表的问题---有序性插入

  • 插入后的序号由元素决定

  • 直接插入元素,不需要根据序号做插入,会自动根据数据做排序

  • 注意是在插入时做排序,不是先插完再排序

 

  1. void insert_sort(LPSqlist sqlist, DataType data)
  2. {
  3. if (sqlist == NULL) //为空无法插入
  4. {
  5. printf("sqlist is empty,unable to insert......\n");
  6. return;
  7. }
  8. if (sqlist->curSize == sqlist->maxSize) //满的情况无法插入
  9. {
  10. printf("sqlist is full,unable to insert......\n");
  11. return;
  12. }
  13. if (sqlist->curSize == 0) //直接插入
  14. {
  15. sqlist->dataMemory[sqlist->curSize++] = data;
  16. } //不等于0的情况 直接插在最后面
  17. /* int pos = sqlist->curSize; */
  18. sqlist->dataMemory[sqlist->curSize/* pos */] = data;
  19. for (int k = sqlist->curSize;k > 0; k--) //k 等于最后一个下标 k <= 0 也要退出循环
  20. {
  21. if (sqlist->dataMemory[k] < sqlist->dataMemory[k - 1]) //交换
  22. {
  23. DataType temp = sqlist->dataMemory[k];
  24. sqlist->dataMemory[k] = sqlist->dataMemory[k - 1];
  25. sqlist->dataMemory[k - 1] = temp;
  26. }
  27. else
  28. {
  29. break; //其他情况:大于|等于的情况 直接break即可
  30. }
  31. }
  32. sqlist->curSize++; //插入成功后++
  33. }
  34. //测试代码
  35. LPSqlist sortSqlist = createSqlist(MAX);
  36. insert_sort(sortSqlist, 1);
  37. insert_sort(sortSqlist, 100);
  38. insert_sort(sortSqlist, 77);
  39. insert_sort(sortSqlist, -1);
  40. printSqlist(sortSqlist); //-1 1 1 77 100

销毁顺序表 

  1. void destroySqlist(LPSqlist* sqlist)
  2. {
  3. if (*sqlist == NULL)
  4. {
  5. printf("sqlist is empty, unable to destory......\n");
  6. return;
  7. }
  8. free((*sqlist)->dataMemory);
  9. free(*sqlist);
  10. *sqlist = NULL;
  11. }
  12. //测试代码
  13. destroySqlist(&sortSqlist);
  14. destroySqlist(&sqlist);
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/508544
推荐阅读
相关标签
  

闽ICP备14008679号