• 数据结构-顺序表


     一、顺序表的常用操作

    1、创建顺序表--CreateList

    1. //建立顺序表
    2. typedef int ElemType;
    3. void CreateList(SqList*& L, ElemType a[], int n) { //由a中的n个元素建立顺序表
    4. int i = 0,k = 0; // k表示L中元素的个数,初始值为0
    5. L = (SqList*)malloc(sizeof(SqList)); // 分配存放线性表的空间
    6. while (i < n) { //i扫描数组a的元素
    7. L->data[k] = a[i]; //将元素a[i]存放到L中
    8. k++; i++;
    9. }
    10. L->length = k; //设置L的长度k
    11. }

    2、初始化线性表--InitList(&L)

    1. //初始化线性表
    2. void InitList(SqList*& L) {
    3. L = (SqList*)malloc(sizeof(SqList)); //分配存放线性表的空间
    4. L ->length = 0; //置空线性表的长度
    5. }

    3、销毁线性表--DestroyList(&L)

    1. //销毁线性表
    2. void DestroyList(SqList*& L) {
    3. free(L); //释放L所指的顺序表空间
    4. }

    4、判断线性表是否为空--ListEmpty(L)

    1. //判断线性表是否为空表
    2. bool ListEmpty(SqList * L){
    3. return(L->length==0);
    4. }

    5、求线性表的长度--ListLength(L)

    1. //求线性表的长度
    2. int ListLength(SqList* L) {
    3. return(L->length);
    4. }

    6、输出线性表--DispList(L)

    1. //输出线性表
    2. void DispList(SqList* L) {
    3. for (int i = 0; i < L->length; i++) { //遍历顺序表的元素
    4. printf("%d ", L->data[i]);
    5. }
    6. printf("\n");
    7. }

    7、获取L中的第i个元素的值--GetElem(L,i,&e)

    1. //获取L中的第i个元素的值
    2. int GetElem(SqList* L, int i, ElemType& e) {
    3. if (i<1 || i>L->length) {
    4. return false;
    5. }
    6. e = L->data[i - 1]; //第i个元素的下标为i-1
    7. return true;
    8. }

    8、查找第一个值为e的元素的逻辑序号(即元素下标+1)--LocateElem( L, e) 

    1. //查找第一个值为e的元素的逻辑序号(即元素下标+1)
    2. int LocateElem(SqList* L, ElemType e) {
    3. for (int i = 0; i < L->length; i++) {
    4. if (L->data[i] == e) {
    5. return i + 1; //找到元素e,返回逻辑序号(即元素下标+1)
    6. }
    7. }
    8. return 0; //未找到时返回0
    9. }

    9、插入数据元素(在第i个位置插入元素e)--ListInsert(& L, i, ElemType e)

    1. //插入数据元素(在第i个位置插入元素e)
    2. bool ListInsert(SqList*& L, int i, ElemType e) {
    3. if (i<1 || i>L->length + 1 || L->length == MaxSize) {
    4. return false; //参数i错误时,返回false
    5. }
    6. i--; //将逻辑序号转换成物理序号(即下标)
    7. for (int j = L->length; j > i; j--) {
    8. L->data[j] = L->data[j - 1]; //将data[i]及后面的元素向后移动一个位置
    9. }
    10. L->data[i] = e; //插入元素e
    11. L->length++; //顺序表的长度增加1
    12. return true; //成功插入返回true
    13. }

    10、删除元素(在第i个位置的元素e)--ListDelete(& L, i, & e)

    1. //删除元素(在第i个位置的元素e)
    2. bool ListDelete(SqList*& L, int i, ElemType& e) {
    3. if(i<1 || i>L->length) {
    4. return false; //参数错误时,返回false
    5. }
    6. i--; //将逻辑序号转换成物理序号(即下标)
    7. e = L->data[i];
    8. for (int j = i; j < L->length-1; j++) {
    9. L->data[j] = L->data[j + 1]; //将data[i]之后的元素向前移动一个位置
    10. }
    11. L->length--; //顺序表的长度减1
    12. return true; //成功删除,返回true
    13. }

     整体代码

    1. #include
    2. using namespace std;
    3. #define MaxSize 50
    4. //声明线性表的顺序存储类型
    5. typedef struct {
    6. ElemType data[MaxSize]; //存放线性表中的元素
    7. int length; //存放线性表的长度
    8. }SqList; //顺序表类型
    9. //建立顺序表
    10. typedef int ElemType;
    11. void CreateList(SqList*& L, ElemType a[], int n) { //由a中的n个元素建立顺序表
    12. int i = 0,k = 0; // k表示L中元素的个数,初始值为0
    13. L = (SqList*)malloc(sizeof(SqList)); // 分配存放线性表的空间
    14. while (i < n) { //i扫描数组a的元素
    15. L->data[k] = a[i]; //将元素a[i]存放到L中
    16. k++; i++;
    17. }
    18. L->length = k; //设置L的长度k
    19. }
    20. //初始化线性表
    21. void InitList(SqList*& L) {
    22. L = (SqList*)malloc(sizeof(SqList)); //分配存放线性表的空间
    23. L ->length = 0; //置空线性表的长度
    24. }
    25. //销毁线性表
    26. void DestroyList(SqList*& L) {
    27. free(L); //释放L所指的顺序表空间
    28. }
    29. //判断线性表是否为空表
    30. bool ListEmpty(SqList * L){
    31. return(L->length==0);
    32. }
    33. //求线性表的长度
    34. int ListLength(SqList* L) {
    35. return(L->length);
    36. }
    37. //输出线性表
    38. void DispList(SqList* L) {
    39. for (int i = 0; i < L->length; i++) { //遍历顺序表的元素
    40. printf("%d ", L->data[i]);
    41. }
    42. printf("\n");
    43. }
    44. //获取L中的第i个元素的值
    45. int GetElem(SqList* L, int i, ElemType& e) {
    46. if (i<1 || i>L->length) {
    47. return false;
    48. }
    49. e = L->data[i - 1]; //第i个元素的下标为i-1
    50. return true;
    51. }
    52. //查找第一个值为e的元素的逻辑序号(即元素下标+1)
    53. int LocateElem(SqList* L, ElemType e) {
    54. for (int i = 0; i < L->length; i++) {
    55. if (L->data[i] == e) {
    56. return i + 1; //找到元素e,返回逻辑序号(即元素下标+1)
    57. }
    58. }
    59. return 0; //未找到时返回0
    60. }
    61. //插入数据元素(在第i个位置插入元素e)
    62. bool ListInsert(SqList*& L, int i, ElemType e) {
    63. if (i<1 || i>L->length + 1 || L->length == MaxSize) {
    64. return false; //参数i错误时,返回false
    65. }
    66. i--; //将逻辑序号转换成物理序号(即下标)
    67. for (int j = L->length; j > i; j--) {
    68. L->data[j] = L->data[j - 1]; //将data[i]及后面的元素向后移动一个位置
    69. }
    70. L->data[i] = e; //插入元素e
    71. L->length++; //顺序表的长度增加1
    72. return true; //成功插入返回true
    73. }
    74. //删除元素(在第i个位置的元素e)
    75. bool ListDelete(SqList*& L, int i, ElemType& e) {
    76. if(i<1 || i>L->length) {
    77. return false; //参数错误时,返回false
    78. }
    79. i--; //将逻辑序号转换成物理序号(即下标)
    80. e = L->data[i];
    81. for (int j = i; j < L->length-1; j++) {
    82. L->data[j] = L->data[j + 1]; //将data[i]之后的元素向前移动一个位置
    83. }
    84. L->length--; //顺序表的长度减1
    85. return true; //成功删除,返回true
    86. }
    87. int main() {
    88. return 0;
    89. }

    二、顺序表的应用

    假设一个线性表采用顺序表表示,设计一个算法,删除其中所有值等于x的元素,要求算法的时间复杂度为O(n),空间复杂度为O(1)

    解法一:整体建表法

    1. //整体建表法
    2. void delnode1(SqList*& L, ElemType x) {
    3. int k = 0; //k记录不等于x的元素的个数,即保留的元素的个数
    4. for (int i = 0; i < L->length; i++) {
    5. if (L->data[i] != x) { //若当前元素不为x,将其插入到L中
    6. L->data[k] = L->data[i];
    7. k++; //插入一个元素时,L中元素的个数增加1
    8. }
    9. }
    10. L->length = k; //顺序表的长度为k
    11. }

     解法二:元素平移法

    1. //元素平移法
    2. void delnode2(SqList*& L, ElemType x) {
    3. int k = 0; //k记录等于x的元素的个数,即要删除的元素的个数
    4. for (int i = 0; i < L->length; i++) {
    5. if (L->data[i] == x) { //当前元素为x,x的个数增加1
    6. k++;
    7. }
    8. else {
    9. L->data[i - k] = L->data[i]; //当前元素前面有几个x,就把当前元素向前移动几个位置
    10. }
    11. }
    12. L->length -= k; //顺序表的长度减小k
    13. }

  • 相关阅读:
    万字博客带你了解Spring Framework 的全貌
    2011-2021年“第四期”数字普惠金融指数与上市公司匹配(根据省份匹配)/上市公司数字金融指数匹配
    2019年亚太杯APMCM数学建模大赛A题基于图像分析的二氧化硅熔化表示模型求解全过程文档及程序
    DataWhale - 吃瓜教程学习笔记(二)
    线程安全问题的产生条件、解决方式
    东盟与中日韩(10+3)中小企业人工智能产业论坛
    由于找不到vcruntime140_1.dll文件的解决方法,带你了解vcruntime140_1.dll这个dll
    服务金融机构数字化升级,阿里云发布一体化金融移动端平台
    Java多线程详解
    RocketMQ的适用场景有哪些?
  • 原文地址:https://blog.csdn.net/2303_80050865/article/details/142305711