devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

手撕数据结构---顺序表

作者：笔触狂放9 | 2024-07-24 20:52:40

赞

踩

手撕数据结构---顺序表

头文件：

  1. #ifndef _SEQLIST_H_
  2.  
  3. #define _SEQLIST_H_
  4.  
  5.  
  6.  
  7. #include<stdio.h>
  8.  
  9. #include<malloc.h>
  10.  
  11. #include<assert.h>
  12.  
  13.  
  14.  
  15. #define SEQLIST_INIT_SIZE 8
  16.  
  17. typedef int ElemType;
  18.  
  19. typedef struct SeqList
  20.  
  21. {
  22.  
  23.     ElemType *base;          //开辟空间，数据表开辟的连续空间
  24.  
  25.     int      capacity;       //容量，最大长度
  26.  
  27.     int      size;           //表的长度，实际长度
  28.  
  29. }SeqList;
  30.  
  31.  
  32.  
  33. void InitSeqList(SeqList *list);
  34.  
  35. void push_back(SeqList *list,ElemType x);
  36.  
  37. void show_list(SeqList *list);
  38.  
  39. void push_front(SeqList *list,ElemType x);
  40.  
  41. void pop_back(SeqList *list);
  42.  
  43. void pop_front(SeqList *list);
  44.  
  45. void insert_pos(SeqList *list,ElemType x,int pos);
  46.  
  47. int find(SeqList *list,ElemType key);
  48.  
  49. int length(SeqList *list);
  50.  
  51. void delete_pos(SeqList *list,int pos);
  52.  
  53. void delete_val(SeqList *list,ElemType x);
  54.  
  55. void sort(SeqList *list);
  56.  
  57. void reserve(SeqList *list);
  58.  
  59. void clear(SeqList *list);
  60.  
  61. void destroy(SeqList *list);
  62.  
  63.  
  64.  
  65.  
  66. #endif //_SEQLIST_H_

具体方法实现(顺序表创建回收，增删改查等操作)：

  1. #include"SeqList.h"
  2.  
  3. #include <stdbool.h>
  4.  
  5. /*
  7. *线性表初始化
  9. */
  10.  
  11. void InitSeqList(SeqList *list)
  12.  
  13. {
  14.  
  15.     list->base = (ElemType *)malloc(sizeof(ElemType) * SEQLIST_INIT_SIZE);    //开辟连续空间
  16.  
  17.     assert(list->base != NULL);
  18.  
  19.     list->capacity = SEQLIST_INIT_SIZE;
  20.  
  21.     list->size = 0;
  22.  
  23. }
  24.  
  25. /*
  27. *尾插法（插入数据必须要判断表是否为满）
  29. */
  30.  
  31. void push_back(SeqList *list, ElemType x)
  32.  
  33. {
  34.  
  35.     if(list->base == NULL)
  36.  
  37.     {
  38.  
  39.         printf("list is not exist!\n");
  40.  
  41.         return;
  42.  
  43.     }
  44.  
  45.     if (list->size >= list->capacity)
  46.  
  47.     {
  48.  
  49.         printf("list full!\n");
  50.  
  51.         return;
  52.  
  53.     }
  54.  
  55.     list->base[list->size] = x;
  56.  
  57.     list->size++;
  58.  
  59. }
  60.  
  61.  
  62.  
  63. void show_list(SeqList *list)
  64.  
  65. {
  66.  
  67.     int i = 0;
  68.  
  69.     if(list->base == NULL)
  70.  
  71.     {
  72.  
  73.         printf("list is not exist!\n");
  74.  
  75.         return;
  76.  
  77.     }
  78.  
  79.     if(list->size == 0||list->base == NULL)
  80.  
  81.     {
  82.  
  83.         printf("list empty!");
  84.  
  85.         return;
  86.  
  87.     }
  88.  
  89.     for(i=0;i<list->size;i++)
  90.  
  91.     {
  92.  
  93.         printf("%d ",list->base[i]);
  94.  
  95.     }
  96.  
  97.     printf("\n");
  98.  
  99.  
  100.  
  101. }
  102.  
  103. /*
  105. *头插法（插入数据必须要判断表是否为满）
  107. */
  108.  
  109. void push_front(SeqList *list,ElemType x)
  110.  
  111. {
  112.  
  113.     int i = 0;
  114.  
  115.     if(list->base == NULL)
  116.  
  117.     {
  118.  
  119.         printf("list is not exist!\n");
  120.  
  121.         return;
  122.  
  123.     }
  124.  
  125.     if(list->size >= list->capacity)
  126.  
  127.     {
  128.  
  129.         printf("list full!");
  130.  
  131.         return;
  132.  
  133.     }
  134.  
  135.     for(i=list->size;i>0;i--)
  136.  
  137.     {
  138.  
  139.         list->base[i] = list->base[i-1];
  140.  
  141.     }
  142.  
  143.     list->base[0] = x;
  144.  
  145.     list->size++;
  146.  
  147. }
  148.  
  149.  
  150.  
  151. /*
  153. *尾删法（删除数据必须要判断表是否为空）
  155. */
  156.  
  157. void pop_back(SeqList *list)
  158.  
  159. {
  160.  
  161.     if(list->base == NULL)
  162.  
  163.     {
  164.  
  165.         printf("list is not exist!\n");
  166.  
  167.         return;
  168.  
  169.     }
  170.  
  171.     if(list->size <= 0)
  172.  
  173.     {
  174.  
  175.         printf("list empty!");
  176.  
  177.         return;
  178.  
  179.     }
  180.  
  181.     list->size--;
  182.  
  183. }
  184.  
  185. /*
  187. *头删法（删除数据必须要判断表是否为空）
  189. */
  190.  
  191. void pop_front(SeqList *list)
  192.  
  193. {
  194.  
  195.     int i = 0;
  196.  
  197.     if(list->base == NULL)
  198.  
  199.     {
  200.  
  201.         printf("list is not exist!\n");
  202.  
  203.         return;
  204.  
  205.     }
  206.  
  207.     if(list->size <= 0)
  208.  
  209.     {
  210.  
  211.         printf("list empty!");
  212.  
  213.         return;
  214.  
  215.     }
  216.  
  217.     printf("%d ",list[0]);
  218.  
  219.     for(i=0;i<list->size-1;i++)
  220.  
  221.     {
  222.  
  223.         list->base[i]=list->base[i+1];
  224.  
  225.     }
  226.  
  227.     list->size--;
  228.  
  229. }
  230.  
  231. /*
  233. *在指定位置pos插入元素x
  235. */
  236.  
  237. void insert_pos(SeqList *list,ElemType x ,int pos)
  238.  
  239. {
  240.  
  241.     int i = 0;
  242.  
  243.     if(list->base == NULL)
  244.  
  245.     {
  246.  
  247.         printf("list is not exist!\n");
  248.  
  249.         return;
  250.  
  251.     }
  252.  
  253.     if(list->size >= list->capacity)
  254.  
  255.     {
  256.  
  257.         printf("list full!");
  258.  
  259.         return;
  260.  
  261.     }
  262.  
  263.     if(pos <= 0 || pos > list->capacity)
  264.  
  265.     {
  266.  
  267.         printf("pos is illegal!");
  268.  
  269.         return;
  270.  
  271.     }
  272.  
  273.     if(pos == 1)
  274.  
  275.     {
  276.  
  277.         /*list->base[0] = x;
  279.         return;*/
  280.  
  281.         push_front(list,x);    //当插入位置为第一位时，可直接用头插法插入数据
  282.  
  283.     }
  284.  
  285.     else if(pos == list->size+1)
  286.  
  287.     {
  288.  
  289.         /*list->base[pos-1] = x;
  291.         return;*/
  292.  
  293.         push_back(list,x);   //当插入位置为最后一位时，可直接用尾插法插入数据
  294.  
  295.     }
  296.  
  297.     else{
  298.  
  299.         for(i=list->size;i>=pos;i--)
  300.  
  301.         {
  302.  
  303.             list->base[i]=list->base[i-1];
  304.  
  305.         }
  306.  
  307.         list->base[pos-1]=x;
  308.  
  309.         list->size++;
  310.  
  311.     }
  312.  
  313.    
  314.  
  315. }
  316.  
  317. /*查找给出元素的位置,每个元素只出现一次，若有多个相同元素考虑使用数组*/
  318.  
  319. int find(SeqList *list, ElemType key)
  320.  
  321. {
  322.  
  323.     int i = 0;
  324.  
  325.     if(list->base == NULL)
  326.  
  327.     {
  328.  
  329.         printf("list is not exist!\n");
  330.  
  331.         return -1;
  332.  
  333.     }
  334.  
  335.     for(i=0;i<list->size;i++)
  336.  
  337.     {
  338.  
  339.         if(key == list->base[i])
  340.  
  341.         {
  342.  
  343.             return i+1;
  344.  
  345.         }
  346.  
  347.     }
  348.  
  349.     return -1;
  350.  
  351. }
  352.  
  353. /*顺序表的长度*/
  354.  
  355. int length(SeqList *list)
  356.  
  357. {
  358.  
  359.     if(list->base == NULL)
  360.  
  361.     {
  362.  
  363.         printf("list is not exist!\n");
  364.  
  365.         return -1;
  366.  
  367.     }
  368.  
  369.     return list->size;
  370.  
  371. }
  372.  
  373. /*删除指定位置的元素*/
  374.  
  375. void delete_pos(SeqList *list, int pos)
  376.  
  377. {
  378.  
  379.     if(list->base == NULL)
  380.  
  381.     {
  382.  
  383.         printf("list is not exist!\n");
  384.  
  385.         return;
  386.  
  387.     }
  388.  
  389.     if(pos <= 0 || pos > list->size)
  390.  
  391.     {
  392.  
  393.         printf("pos is illegal!\n");
  394.  
  395.         return;
  396.  
  397.     }
  398.  
  399.     if(pos == 1)
  400.  
  401.     {
  402.  
  403.         pop_front(list);
  404.  
  405.     }
  406.  
  407.     else if(pos == list->size)
  408.  
  409.     {
  410.  
  411.         pop_back(list);
  412.  
  413.     }
  414.  
  415.     else
  416.  
  417.     {
  418.  
  419.         for(int i = pos;i<list->size;i++)
  420.  
  421.         {
  422.  
  423.             list->base[i-1] = list->base[i];
  424.  
  425.         }
  426.  
  427.         list->size--;
  428.  
  429.     }
  430.  
  431. }
  432.  
  433.  
  434.  
  435. void delete_val(SeqList *list, ElemType x)
  436.  
  437. {
  438.  
  439.     int pos;
  440.  
  441.     if(list->base == NULL)
  442.  
  443.     {
  444.  
  445.         printf("list is not exist!\n");
  446.  
  447.         return;
  448.  
  449.     }
  450.  
  451.     pos = find(list,x);
  452.  
  453.     if(pos == -1)
  454.  
  455.     {
  456.  
  457.         printf("value is not exist!\n");
  458.  
  459.         return;
  460.  
  461.     }
  462.  
  463.     delete_pos(list,pos);
  464.  
  465. }
  466.  
  467.  
  468.  
  469. void sort(SeqList *list)
  470.  
  471. {  
  472.  
  473.     //C99的C语言支持bool类型，而Visual Studio Code不支持（C++是支持的）。一些编译器认为使用该类型不够安全，加入#include<stdbool.h>
  474.  
  475.     bool flag = false;  
  476.  
  477.     ElemType a;
  478.  
  479.     if(list->base == NULL)
  480.  
  481.     {
  482.  
  483.         printf("list is not exist!\n");
  484.  
  485.         return;
  486.  
  487.     }
  488.  
  489.     for(int i = 0;i<list->size-1;i++)
  490.  
  491.     {
  492.  
  493.         flag = false;
  494.  
  495.         for(int j = 0;j<list->size-1-i;j++)
  496.  
  497.         {
  498.  
  499.             if(list->base[j]>list->base[j+1])
  500.  
  501.             {
  502.  
  503.                 a = list->base[j];
  504.  
  505.                 list->base[j] = list->base[j+1];
  506.  
  507.                 list->base[j+1] = a;
  508.  
  509.                 flag = true;
  510.  
  511.             }
  512.  
  513.         }
  514.  
  515.         /*如果某一轮排序中无任何位置变化，则顺序表已经排好序，直接跳出循环*/
  516.  
  517.         if(flag == false)
  518.  
  519.         {
  520.  
  521.             break;
  522.  
  523.         }
  524.  
  525.     }
  526.  
  527. }
  528.  
  529.  
  530.  
  531. void reserve(SeqList *list)
  532.  
  533. {
  534.  
  535.     ElemType temp;
  536.  
  537.     if(list->base == NULL)
  538.  
  539.     {
  540.  
  541.         printf("list is not exist!\n");
  542.  
  543.         return;
  544.  
  545.     }
  546.  
  547.     if(list->size == 0||list->size == 1)
  548.  
  549.     {
  550.  
  551.         return;
  552.  
  553.     }
  554.  
  555.     for(int i = 0;i < list->size/2;i++)
  556.  
  557.     {
  558.  
  559.         temp = list->base[i];
  560.  
  561.         list->base[i] = list->base[list->size-i-1];
  562.  
  563.         list->base[list->size-i-1] = temp;
  564.  
  565.     }
  566.  
  567. }
  568.  
  569. /*清除数据，表仍存在*/
  570.  
  571. void clear(SeqList *list)
  572.  
  573. {
  574.  
  575.     if(list->base == NULL)
  576.  
  577.     {
  578.  
  579.         printf("list is not exist!\n");
  580.  
  581.         return;
  582.  
  583.     }
  584.  
  585.     list->size = 0;
  586.  
  587.     return;
  588.  
  589. }
  590.  
  591. /*清除数据，释放表，删除base所指的顺序表空间*/
  592.  
  593. void destroy(SeqList *list)
  594.  
  595. {
  596.  
  597.     free(list->base);
  598.  
  599.     list->base = NULL;
  600.  
  601.     list->capacity = 0;
  602.  
  603.     list->size = 0;
  604.  
  605.     return;
  606.  
  607. }

主程序：

  1. #include"SeqList.h"
  2.  
  3. #include<stdio.h>
  4.  
  5. int main()
  6.  
  7. {
  8.  
  9.     SeqList myList;
  10.  
  11.     InitSeqList(&myList);
  12.  
  13.  
  14.  
  15.     ElemType Item;
  16.  
  17.     int pos;
  18.  
  19.     int len = 0;
  20.  
  21.     int select = 1;
  22.  
  23.     while(select)
  24.  
  25.     {
  26.  
  27.         printf("***********************************\n");
  28.  
  29.         printf("* [1] push_back    [2] push_front *\n");
  30.  
  31.         printf("* [3] show_list    [4] pop_back   *\n");
  32.  
  33.         printf("* [5] pop_front    [6] insert_pos *\n");
  34.  
  35.         printf("* [7] find         [8] length     *\n");
  36.  
  37.         printf("* [9] delete_pos   [10] delete_val*\n");
  38.  
  39.         printf("* [11] sort        [12] reserve   *\n");
  40.  
  41.         printf("* [13] clear       [14*] destroy  *\n");
  42.  
  43.         printf("* [0] quit_system                 *\n");
  44.  
  45.         printf("***********************************\n");
  46.  
  47.         printf("请选择：>");
  48.  
  49.         scanf("%d",&select);
  50.  
  51.         if(select == 0)
  52.  
  53.             break;
  54.  
  55.         switch(select)
  56.  
  57.         {
  58.  
  59.             case 1:
  60.  
  61.                 printf("请输入要插入的数据(-1结束)：>");
  62.  
  63.                 while(scanf("%d",&Item),Item!=-1)
  64.  
  65.                 {
  66.  
  67.                     push_back(&myList,Item);
  68.  
  69.                 }
  70.  
  71.                 break;
  72.  
  73.             case 2:
  74.  
  75.                 printf("请输入要插入的数据(-1结束)：>");
  76.  
  77.                 while(scanf("%d",&Item),Item!=-1)
  78.  
  79.                 {
  80.  
  81.                     push_front(&myList,Item);
  82.  
  83.                 }
  84.  
  85.                 break;
  86.  
  87.             case 3:
  88.  
  89.                 show_list(&myList);
  90.  
  91.                 break;
  92.  
  93.             case 4:
  94.  
  95.                 pop_back(&myList);
  96.  
  97.                 break;
  98.  
  99.             case 5:
  100.  
  101.                 pop_front(&myList);
  102.  
  103.                 break;
  104.  
  105.             case 6:
  106.  
  107.                 printf("请输入要插入的位置和数据(以输入数据为-1结束)：>");
  108.  
  109.                 while(scanf("%d %d",&pos,&Item))
  110.  
  111.                 {
  112.  
  113.                     if(Item == -1)
  114.  
  115.                     {
  116.  
  117.                         break;
  118.  
  119.                     }
  120.  
  121.                     insert_pos(&myList,Item,pos);
  122.  
  123.                 }
  124.  
  125.                 break;
  126.  
  127.             case 7:
  128.  
  129.                 printf("请输入要查找的数据：>");
  130.  
  131.                 scanf("%d",&Item);
  132.  
  133.                 pos = find(&myList,Item);
  134.  
  135.                 if(pos == -1)
  136.  
  137.                 {
  138.  
  139.                     printf("查找数据不存在\n");
  140.  
  141.                 }
  142.  
  143.                 else
  144.  
  145.                 {
  146.  
  147.                     printf("查找元素在第 %d 位\n",pos);
  148.  
  149.                 }
  150.  
  151.                 break;
  152.  
  153.             case 8:
  154.  
  155.                 len = length(&myList);
  156.  
  157.                 printf("顺序表中数据长度为 %d ",len);
  158.  
  159.                 break;
  160.  
  161.             case 9:
  162.  
  163.                 printf("请输入要删除数据元素的位置：>");
  164.  
  165.                 scanf("%d",&pos);
  166.  
  167.                 delete_pos(&myList,pos);
  168.  
  169.                 break;
  170.  
  171.             case 10:
  172.  
  173.                 printf("请输入要删除数据元素的值：>");
  174.  
  175.                 scanf("%d",&Item);
  176.  
  177.                 delete_val(&myList,Item);
  178.  
  179.                 break;
  180.  
  181.             case 11:
  182.  
  183.                 sort(&myList);
  184.  
  185.                 break;
  186.  
  187.             case 12:
  188.  
  189.                 reserve(&myList);
  190.  
  191.                 break;
  192.  
  193.             case 13:
  194.  
  195.                 clear(&myList);
  196.  
  197.                 break;
  198.  
  199.             /*case 14:
  201.                 destroy(&myList);
  203.                 break;*/
  204.  
  205.             default:
  206.  
  207.                 printf("输入的选择错误，请重新输入.\n");
  208.  
  209.                 break;
  210.  
  211.         }
  212.  
  213.     }
  214.  
  215.     destroy(&myList);
  216.  
  217.     return 0;
  218.  
  219. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/876694
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号