1. 首页
  2. IT资讯

数据结构:线性表的顺序实现2.2

对于一个线性表如果我们使用顺序的实现,那么在insert或者delete一个值的时候最坏渐进时间复杂度
趋近于数据的规模n及
f(n)=O(n);
可以看到这个时候代价比较高,所以我们一般使用链试实现,关于这个算法我用C语言进行如下实现。
当使用链试实现的时候代替 时间复杂度为O(1) 出于演示并没有写free 释放内存
但是我们也可以想到关于固定位置的元素查找顺序实现其时间复杂度为O(1),而链表结构则为O(n)

点击(此处)折叠或打开

  1. /*************************************************************************
  2.     > File Name: sqlist.c
  3.     > Author: gaopeng
  4.     > Mail: gaopp_200217@163.com
  5.     > Created Time: Tue 04 Oct 2016 09:12:11 PM CST
  6.  ************************************************************************/
  7. #include<stdio.h>
  8. #include<stdlib.h>
  9. #include<string.h>
  10. #define INITSIZE 10
  11. typedef unsigned int uint;
  12. typedef int Etype;
  13. typedef struct sqlist
  14. {
  15.         Etype* elem; //pointer of sqlist base address
  16.         uint length; //current length of elem
  17.         uint m_size; //
  18. } SQLIST;
  19. void initsqlist(SQLIST* inlist)
  20. {
  21.         inlist>elem = (Etype* )malloc(sizeof(Etype)*(INITSIZE+2) + 1);
  22.         inlist>length = 0;
  23.         inlist>m_size = INITSIZE; //maxsize
  24. }
  25. void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion) //insert elem before postion
  26. {
  27.         int i;
  28.         Etype* newbase;
  29.         if(postion > inlist>length + 1 || postion < 1)
  30.         {
  31.                 printf(“line table must continuous or postion must>0!n”);
  32.                 exit(1);
  33.         }
  34.         if(inlist>length + 1 >= inlist>m_size ) //if memory small will give more memory
  35.         {
  36.                 if(!(newbase =(Etype* )realloc(inlist>elem,(inlist>length+INITSIZE+2)* sizeof(Etype)+1)))
  37.                 {
  38.                         printf(“mem alloc failed!n”);
  39.                         exit(2);
  40.                 }
  41.                 inlist>elem = newbase;
  42.                 inlist>m_size = inlist>m_size+INITSIZE;
  43.         }
  44.         for(i=0;i<(inlist>lengthpostion+2);i++) //every elem +1
  45.         {
  46.                 *(inlist>elem+inlist>length+1i) = * (inlist>elem+inlist>lengthi);
  47.         }
  48.         *(inlist>elem+inlist>length+1i) = ielem; //give value
  49.         inlist>length =inlist>length+1;
  50. }
  51. void delsqldel(SQLIST* inlist,uint postion) //delete elem of postion every elem -1
  52.         int i;
  53.         if((postion > inlist>length) ||(postion <1))
  54.         {
  55.                 printf(“give postion is must large than 1 and less than current lengthn”);
  56.         }
  57.         for(i=0;i<(inlist>lengthpostion) ;i++)
  58.         {
  59.                 *(inlist>elem+postion+i) = *(inlist>elem+postion+i+1);
  60.         }
  61.         inlist>length =inlist>length1;
  62. }
  63. void view(SQLIST* inlist)
  64. {
  65.         int i;
  66.         if(inlist>length ==0 )
  67.         {
  68.                 printf(“init data arrary! no data found!n”);
  69.                 exit(3);
  70.         }
  71.         for(i=0;i<inlist>length;i++)
  72.         {
  73.                 printf(“node:%d values is:%d data length:%d max_size:%d n”,i,*(inlist>elem+i),inlist>length,inlist>m_size);
  74.         }
  75. }
  76. int main(void)
  77. {
  78.     SQLIST a;
  79.         initsqlist(&a);
  80.         printf(“insert two valuesn”);
  81.         initsqlinsert(&a,5,1);
  82.         initsqlinsert(&a,10,1);
  83.         view(&a);
  84.         printf(“delete one valuesn”);
  85.         delsqldel(&a,2);
  86.         view(&a);
  87.         printf(“insert more than 10 valuesn”);
  88.         initsqlinsert(&a,10,1);
  89.         initsqlinsert(&a,20,1);
  90.         initsqlinsert(&a,30,1);
  91.         initsqlinsert(&a,40,1);
  92.         initsqlinsert(&a,50,1);
  93.         initsqlinsert(&a,10,1);
  94.         initsqlinsert(&a,10,1);
  95.         initsqlinsert(&a,10,1);
  96.         initsqlinsert(&a,10,1);
  97.         initsqlinsert(&a,10,1);
  98.         initsqlinsert(&a,10,1);
  99.         view(&a);
  100.         return 0;
  101. }

运行如下:
gaopeng@bogon:~/datas/part2$ ./a.out 
insert two values
node:0 values is:10 data length:2 max_size:10 
node:1 values is:5 data length:2 max_size:10 
delete one values
node:0 values is:10 data length:1 max_size:10 
insert more than 10 values
node:0 values is:10 data length:12 max_size:20 
node:1 values is:10 data length:12 max_size:20 
node:2 values is:10 data length:12 max_size:20 
node:3 values is:10 data length:12 max_size:20 
node:4 values is:10 data length:12 max_size:20 
node:5 values is:10 data length:12 max_size:20 
node:6 values is:50 data length:12 max_size:20 
node:7 values is:40 data length:12 max_size:20 
node:8 values is:30 data length:12 max_size:20 
node:9 values is:20 data length:12 max_size:20 
node:10 values is:10 data length:12 max_size:20 
node:11 values is:10 data length:12 max_size:20 

上图演示的是删除data3的方式。插入相反

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2124937/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183857.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code