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

详解顺序表_静态顺序表的最大长度和动态顺序表初始什么意思

作者：花生_TL007 | 2024-04-23 15:34:44

赞

踩

静态顺序表的最大长度和动态顺序表初始什么意思

一.线性表的定义

线性表的顺序表示又称为顺序存储结构或顺序映像。

1.顺序表简介：

百度百科：顺序表是在计算机内存中以数组的形式保存的线性表，线性表的n是指用一组地址连续的存储单元依次存储线性表中的各个元素、使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，采用顺序存储结构的线性表通常称为顺序表。顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中。

 概念： 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序存储定义：逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

总之：逻辑上相邻，物理上也相邻。

线性表（A1,A2,A3.....An-1,An）

线性表的第一个数据元素A1的存储位置，称作线性表的起始位置或基地址。

存储结构：依次存储，地址连续，中间没有空出存储单元

259ea9c3c8db477798d0e335119ab531.png​

顺序表的特点：以物理位置相邻表示逻辑关系。任意元素可随机存取

顺序表元素：地址连续、依次存放、随机存取、类型相同

2.定义总结：

​

二.顺序表分类

分为静态顺序表与动态顺序表（如上图所示）

静态顺序表：使用定长数组存储元素。

动态顺序表：使用动态开辟的数组存储。

优缺点：

1.随机访问

2.存储密度高

3.扩展容量不方便

4.插入、删除数据元素不方便

三.代码实现

3.1 【1】定义顺序表的最大长度和动态顺序表的初始默认最大容量

  1. /*需要包含的头文件*/
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4.  
  5.  
  6. /*【1】定义顺序表的最大长度和动态顺序表的初始默认最大容量*/
  7. #define MaxSize  10
  8. #define InitSize 10
  9.  
  10.  
  11. /*程序演示开头展示*/
  12. char welcome[] = "~~~~~~~~~~~欢迎光临本程序~~~~~~~~~如有问题~~~~~~~请选择帮助联系开发人员\n顺序表初始化中......";

3.2  【2】自定义C语言的bool变量

  1. /*【2】自定义C语言的bool变量*/
  2. #define bool char
  3. #define true 1
  4. #define false 0

3.3  【3】自定义数据元素的数据类型

  1. /*【3】自定义数据元素的数据类型*/
  2. typedef int Elemtype;

3.4  【4】顺序表的结构体定义

  1. /*【4】顺序表的结构体定义*/
  2. //<1>静态顺序表的数据元素结构体
  3.  typedef struct SqList
  4.  {
  5.  
  6.     /*使用静态数组存放数据元素 */
  7.     Elemtype data[MaxSize];
  8.     /*顺序表的当前长度*/
  9.     int length;
  10.  
  11.  }SqList;
  12.   
  13. //<2>动态顺序表的数据元素结构体
  14.  typedef struct SeqList
  15.  {
  16.  
  17.     /*使用动态指针分配数组 */
  18.     Elemtype *data;
  19.     /*顺序表的当前长度*/
  20.     int length;
  21.     /*顺序表的当前长度*/
  22.     int maxsize;
  23.  
  24.  }SeqList;

3.5  【5】顺序表的初始化（这里初始化长度均为5，方便后面代码测试）

  1. /*【5】顺序表的初始化*/
  2. //<1>静态顺序表初始化
  3. bool InitSqList(SqList *L){
  4.     //初始化表长
  5.     L->length = 5;
  6.  
  7.     return true;
  8.  
  9. }
  10. //<2>动态顺序表初始化
  11. bool InitSeqList(SeqList *L){
  12.     //初始化表长
  13.     L->length = 5;
  14.  
  15.     //初始化最大容量
  16.     L->maxsize = InitSize;
  17.  
  18.     //给指针分配一片空间，空间大小依据maxsize决定
  19.     L->data = (Elemtype *)malloc(sizeof(Elemtype) * InitSize);
  20.  
  21.     return true;
  22. }

3.6  【6】顺序表的元素插入

  1. /*【6】顺序表的元素插入*/
  2. //<1>静态顺序表的插入
  3. bool SqListInsert(SqList *L, int i, Elemtype e){  //在顺序表的第i个位置插入新元素e
  4.  
  5.     //[1]判断插入操作是否合法
  6.     if (i<1 || i>L->length+1)
  7.     {
  8.         printf("【10001】这个位置插入不合法!\n");
  9.         return false;
  10.     }
  11.     if (L->length >= MaxSize)
  12.     {
  13.         printf("【10002】这张表已经满了!\n");
  14.         return false;
  15.     }
  16.     
  17.     //[2]将第i位和之后的元素位置往后移动一位
  18.     for (int j = L->length; j >= i; j--)
  19.     {
  20.         L->data[j] = L->data[j-1];
  21.     }
  22.  
  23.     //[3]将新元素插入到指定位置---区分数组下标和元素位序的排列
  24.     L->data[i - 1] = e;
  25.     //[4]表长加一
  26.     L->length++;
  27.     return true;
  28.     
  29. }
  30. //<2>动态顺序表的插入
  31. bool SeqListInsert(SeqList *L, int i, Elemtype e){
  32.      //[1]判断插入操作是否合法
  33.      if (i<1 || i>L->length+1)
  34.      {
  35.         printf("【10003】这个位置插入不合法!\n");
  36.         return false;       
  37.      }
  38.  
  39.      if(L->length >= L->maxsize){
  40.         printf("【10004】这张表已经满了!\n");
  41.         return false;       
  42.      }
  43.  
  44.      //[2]将第i位和之后的元素位置往后移动一位
  45.      for (int j = L->length; j >= i; j--)
  46.      {
  47.         L->data[j] = L->data[j-1];
  48.      }
  49.  
  50.      //[3]将新元素插入到指定位置
  51.      L->data[i-1] = e;
  52.  
  53.      //[4]表长加一
  54.      L->length++;
  55.      return true;
  56.      
  57.      
  58. }

3.7  【7】顺序表的元素删除

  1. /*【7】顺序表的元素删除*/
  2. //<1>静态顺序表的删除
  3. //将第i位元素删除
  4. bool SqListDetele(SqList *L,int i,Elemtype *e){
  5.  
  6.     //[1]判断操作合法性
  7.     if (i<1 || i>L->length+1)
  8.     {
  9.         printf("【10005】这个位置删除不合法!\n");
  10.         return false;          
  11.     }
  12.     if (L->length <= 0)
  13.     {
  14.         printf("【10006】这张表是空的!\n");
  15.         return false;   
  16.     }
  17.     
  18.     //[2]将要删除的值赋值给e
  19.     *e = L->data[i-1];
  20.     //[3]移动元素，将第i位和之后的元素赋值给前一位
  21.     for (int j = i; j < L->length; j++)
  22.     {
  23.         L->data[j-1] = L->data[j];
  24.     }
  25.     
  26.     //[4]表长减一
  27.     L->length--;
  28.     //[5]返回TRUE
  29.     return true;
  30.  
  31.     
  32. }
  33. //<2>动态顺序表的删除
  34. bool SeqListDetele(SeqList *L,int i,Elemtype *e){
  35.  
  36.     //[1]判断操作合法性
  37.     if (i<1 || i>L->length+1)
  38.     {
  39.         printf("【10005】这个位置删除不合法!\n");
  40.         return false;          
  41.     }
  42.     if (L->length <= 0)
  43.     {
  44.         printf("【10006】这张表是空的!\n");
  45.         return false;   
  46.     }
  47.     
  48.     //[2]将要删除的值赋值给e
  49.     *e = L->data[i-1];
  50.     //[3]移动元素，将第i位和之后的元素赋值给前一位
  51.     for (int j = i; j < L->length; j++)
  52.     {
  53.         L->data[j-1] = L->data[j];
  54.     }
  55.     
  56.     //[4]表长减一
  57.     L->length--;
  58.     //[5]返回TRUE
  59.     return true;
  60.  
  61.     
  62. }

3.8  【8】顺序表的查询(按值查询)

  1. /*【8】顺序表的查询(按值查询)*/
  2. //<1>静态顺序表的查询
  3. int SqListSelect(SqList L,Elemtype e){
  4.  
  5.     for (int i = 0; i < L.length; i++)
  6.     {
  7.         if (L.data[i] == e)
  8.         {
  9.             return i+1;
  10.         }       
  11.     }
  12.     return 0;    
  13. }
  14. //<2>动态顺序表的查询
  15. int SeqListSelect(SeqList L,Elemtype e){
  16.  
  17.     for (int i = 0; i < L.length; i++)
  18.     {
  19.         if (L.data[i] == e)
  20.         {
  21.             return i+1;
  22.         }      
  23.     }
  24.     return 0;    
  25. }

3.9  【9】动态顺序表的扩容

  1. /*【9】动态顺序表的扩容*/
  2. bool IncreaseSize(SeqList *L,int len){
  3.     //[1]生成指向原来顺序表存储空间的指针
  4.     Elemtype *p = L->data;
  5.  
  6.     //[2]开辟空间
  7.     L->data = (Elemtype *)malloc(sizeof(Elemtype) * (L->maxsize + len));
  8.  
  9.     //[3]转移数据
  10.     for (int i = 0; i < L->length; i++)
  11.     {
  12.         L->data[i] = p[i];
  13.     }
  14.     
  15.     //[4]修改顺序表长，值加len
  16.     L->maxsize += len;
  17.  
  18.     //[5]释放空间
  19.     free(p);
  20.  
  21.     return true;
  22.  
  23. }

3.10 【10】顺序表的输出

  1. /*静态顺序表的输出*/
  2. bool SqListPrint(SqList L){
  3.  
  4.     //判空
  5.     if (L.length == 0)
  6.     {
  7.         printf("This sequence table is emply!(空表)\n");
  8.     }else{
  9.         printf("SqList===");
  10.     }
  11.  
  12.     
  13.     for (int i = 0; i < L.length; i++)
  14.     {
  15.         printf("%d、",L.data[i]);
  16.         
  17.     }
  18.     printf("\n");
  19.     printf("end\n");
  20.     
  21. }
  22.  
  23. /*动态顺序表的输出*/
  24. bool SeqListPrint(SeqList L){
  25.  
  26.     //判空
  27.     if (L.length == 0)
  28.     {
  29.         printf("This sequence table is emply!(空表)\n");
  30.     }else{
  31.         printf("SeqList===");
  32.     }
  33.  
  34.     for (int i = 0; i < L.length; i++)
  35.     {
  36.         printf("%d、",L.data[i]);
  37.         
  38.     }
  39.     printf("\n");
  40.     printf("end\n");
  41. }

3.11  【11】main方法

  1. int main(){
  2.  
  3.     SqList L1;
  4.     SeqList L2;
  5.     int a,b,d,e,num,num1,choose;
  6.  
  7.  
  8.     	for(int i=0;i<strlen(welcome);i++)
  9. 	    {
  10. 		    printf("%c",welcome[i]);
  11. 		    for(int m=0;m<10000;m++)
  12. 			    for(int n=0;n<2800;n++)
  13. 			    {
  14. 				    
  15. 			    }
  16. 	    }
  17.  
  18.  
  19.     //对顺序表初始化
  20.     
  21.     if (InitSqList(&L1) == true && InitSeqList(&L2) == true)
  22.     {
  23.         printf("顺序表初始化成功！\n");
  24.     }else{
  25.         printf("初始化失败啦！快去找bug！\n");
  26.     }
  27.  
  28.  
  29.  
  30.  
  31.     while (choose != 9 )
  32.     {
  33.         printf("请选择需要调试的顺序表：\n");
  34.         printf("静态顺序表：【1】\n");
  35.         printf("动态顺序表：【2】\n");
  36.         printf("更多：【3】\n");
  37.         printf("帮助：【4】\n");
  38.         printf("关闭：【9】\n");
  39.  
  40.         scanf("%d",&choose);
  41.         //静态顺序表
  42.         
  43.         if (choose == 1)
  44.         {
  45.             while (num1 != 6)
  46.                     {
  47.                     printf("---------------------------------\n");
  48.                     printf("打印静态顺序表【0】\n");
  49.                     printf("设置静态顺序表的数据元素【1】\n");
  50.                     printf("静态顺序表中插入数据元素【2】\n");
  51.                     printf("静态顺序表中删除数据元素【3】\n");
  52.                     printf("重新初始化静态顺序表【4】\n");
  53.                     printf("按值查找元素位序【5】\n");
  54.  
  55.                     printf("退出【6】\n");
  56.                     printf("---------------------------------\n");
  57.                     printf("\n");
  58.  
  59.                     scanf("%d",&num1);
  60.                     switch (num1)
  61.                     {
  62.                     //选项0
  63.                     case 0:
  64.                         printf("静态顺序表打印结果===》\n");
  65.                         SqListPrint(L1);
  66.                         break;
  67.  
  68.                     //选项1
  69.                     case 1:
  70.                         for (int i = 1; i <= L1.length; i++)
  71.                         {
  72.                             printf("请输入第%d个数字：",i);
  73.                             scanf("%d",&a);
  74.                             L1.data[i-1] = a;
  75.                         
  76.                         }
  77.  
  78.                         printf("设置成功！\n");
  79.                         SqListPrint(L1);
  80.                         break;
  81.  
  82.                     //选项2
  83.                     case 2:
  84.                         //静态顺序表插入元素
  85.                         printf("请输入想要插入的位置====");
  86.                         scanf("%d",&a);
  87.  
  88.                         printf("请输入想要插入的数字====");
  89.                         scanf("%d",&b);
  90.  
  91.                         bool l = SqListInsert(&L1,a,b);
  92.                         if (l == false)
  93.                         {
  94.                             printf("插入失败！\n");
  95.                         }else{
  96.                             printf("插入成功！\n");
  97.                         }
  98.                         
  99.                         
  100.  
  101.                         
  102.                         printf("静态顺序表打印结果===》\n");
  103.                         SqListPrint(L1);
  104.  
  105.                         break;
  106.  
  107.  
  108.                     //选项3
  109.                     case 3:
  110.                         printf("请输入想要删除的位置====");
  111.                         scanf("%d",&a);
  112.  
  113.                         SqListDetele(&L1,a,&e);
  114.  
  115.                         printf("删除成功！已将%d删除\n",e);
  116.  
  117.                         printf("重新打印静态顺序表:\n");
  118.                         SqListPrint(L1);
  119.                         break;
  120.  
  121.                     //选项4
  122.                     case 4:
  123.  
  124.                         //对顺序表初始化
  125.                         printf("静态顺序表初始化中......\n");
  126.  
  127.                         if (InitSqList(&L1) == true)
  128.                         {
  129.                             printf("静态顺序表初始化成功！\n");
  130.                         }else{
  131.                             printf("初始化失败啦！快去找bug！\n");
  132.                         }
  133.  
  134.                         break;
  135.  
  136.                     //选项5
  137.                     case 5:
  138.                         printf("请输入想要查找的元素====");
  139.                         scanf("%d",&d);
  140.  
  141.                         printf("该值在第%d位第一次出现\n",SqListSelect(L1,d));
  142.                         break;
  143.                     //选项6
  144.                     // case 6:
  145.                     //     break;
  146.                     }
  147.  
  148.             }
  149.         
  150.  
  151.         }
  152.         //动态顺序表
  153.         else if(choose == 2)
  154.         {
  155.             while (num1 != 7){
  156.  
  157.             printf("---------------------------------\n");
  158.             printf("打印动态顺序表【0】\n");
  159.             printf("设置动态顺序表的数据元素【1】\n");
  160.             printf("动态顺序表中插入数据元素【2】\n");
  161.             printf("动态顺序表中删除数据元素【3】\n");
  162.             printf("重新初始化动态顺序表【4】\n");
  163.             printf("按值查找元素位序【5】\n");
  164.             printf("动态顺序表扩容【6】\n");
  165.  
  166.  
  167.             
  168.             printf("退出【7】\n");
  169.             printf("---------------------------------\n");
  170.             printf("\n");
  171.        
  172.  
  173.             scanf("%d",&num1);
  174.             switch (num1)
  175.             {
  176.             //选项0
  177.             case 0:
  178.                 printf("动态顺序表打印结果===》\n");
  179.                 SeqListPrint(L2);
  180.                 break;
  181.  
  182.             //选项1
  183.             case 1:
  184.                 for (int i = 1; i <= L2.length; i++)
  185.                 {
  186.                     printf("请输入第%d个数字：",i);
  187.                     scanf("%d",&a);
  188.                     L2.data[i-1] = a;
  189.             
  190.                 }
  191.  
  192.                 printf("设置成功！\n");
  193.                 SeqListPrint(L2);
  194.                 break;   
  195.  
  196.  
  197.             //选项2
  198.             case 2:
  199.  
  200.                 //动态顺序表插入元素
  201.                 printf("请输入想要插入的位置====");
  202.                 scanf("%d",&a);
  203.  
  204.                 printf("请输入想要插入的数字====");
  205.                 scanf("%d",&b);
  206.  
  207.                 bool l = SeqListInsert(&L2,a,b);
  208.  
  209.                         if (l == false)
  210.                         {
  211.                             printf("插入失败！\n");
  212.                         }else{
  213.                             printf("插入成功！\n");
  214.                         }
  215.                         
  216.  
  217.                 printf("动态顺序表打印结果===》\n");
  218.                 SeqListPrint(L2);
  219.  
  220.                 break;
  221.  
  222.  
  223.             //选项3
  224.             case 3:
  225.                 printf("请输入想要删除的位置====");
  226.                 scanf("%d",&a);
  227.  
  228.                 SeqListDetele(&L2,a,&e);
  229.  
  230.                 printf("删除成功！已将%d删除\n",e);
  231.                 printf("重新打印动态顺序表:\n");
  232.                 SeqListPrint(L2);
  233.                 break;
  234.  
  235.  
  236.             //选项4
  237.             case 4:
  238.  
  239.                 //对顺序表初始化
  240.                 printf("动态顺序表初始化中......\n");
  241.  
  242.                 if (InitSeqList(&L2) == true)
  243.                 {   
  244.                     printf("动态顺序表初始化成功！\n");
  245.                 }else{
  246.                     printf("初始化失败啦！快去找bug！\n");
  247.                 }
  248.  
  249.                 break;
  250.  
  251.             //选项5
  252.             case 5:
  253.                 printf("请输入想要查找的元素====");
  254.                 scanf("%d",&d);
  255.  
  256.                 printf("该值在第%d位第一次出现\n",SeqListSelect(L2,d));
  257.                 break;
  258.             
  259.             //选项6
  260.             case 6:
  261.                 printf("空间大小：%d\n",L2.maxsize);
  262.                 printf("想要扩容的大小=====");
  263.                 scanf("%d",&d);
  264.                 IncreaseSize(&L2,d);
  265.  
  266.                 printf("新的空间大小：%d\n",L2.maxsize);
  267.  
  268.                 break;
  269.  
  270.             //选项7
  271.                 //case 7:
  272.                 //break;
  273.             }
  274.             }
  275.         }else if (choose == 3)
  276.         {
  277.                 printf("还没开发\n");
  278.         }else if (choose == 4)
  279.         {
  280.             printf("~~~~~本程序由小露制作，用于了解顺序表的原理，并且示范两种顺序表的基本操作\n如有问题也没办法,程序员已经跑路了~~~~~\n");
  281.         }
  282.         
  283.         else if (choose == 9)
  284.         {
  285.             break;
  286.         }
  287.                
  288.         else{
  289.             printf("输入不合法！请重新输入！\n");
  290.         }
  291.         
  292.         
  293.  
  294.     }
  295.       
  296.  
  297. }

四.运行结果

1.静态顺序表：

23ad5f16fe8149b5954c09ed4c6ab5b7.png​

3.动态顺序表：

8da19f0086c44c1f9208bf246fb0bfe8.png​

五.小结

顺序表是一种常见的线性表数据结构，它通过数组实现，有固定的大小并且元素在内存中是连续存储的。下面是顺序表的小结：

特点：顺序表的元素在内存中是连续存储的，可以通过索引直接访问元素，具有随机访问的特性。它的大小是固定的，一旦定义了大小，就无法动态调整。
缺点：顺序表的大小固定，一旦初始化就无法改变，当元素数量超过顺序表大小时，需要重新申请更大的内存空间，并将元素复制到新的空间中。这个过程比较耗时。
插入和删除：在顺序表中插入和删除元素需要移动元素的位置，这可能涉及到大量的数据搬移操作，特别是在顺序表的中间位置插入或删除元素时，效率较低。
查找：在顺序表中查找元素的时间复杂度为O(n)，需要遍历整个顺序表，直到找到匹配的元素。如果需要经常进行查找操作，顺序表可能不是最佳选择。
动态扩展：由于顺序表的大小固定，当元素数量增加时，可能需要重新申请更大的内存空间。这个过程可能比较耗时，需要考虑内存分配和数据迁移的开销。

总之，顺序表是一种简单且常用的数据结构，适用于对元素随机访问频繁、元素数量固定且不需要频繁插入和删除的场景。但对于元素数量动态变化、插入和删除较频繁的情况，顺序表的性能可能不如链表等动态分配内存的数据结构。选择使用何种数据结构需要根据具体的需求和场景来进行权衡。
 

参考文献：

百度百科，CSDN，数据结构(C语言版)

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

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

  

闽ICP备14008679号