对于一个线性表如果我们使用顺序的实现，那么在insert或者delete一个值的时候最坏渐进时间复杂度
趋近于数据的规模n及
f(n)=O(n);
可以看到这个时候代价比较高，所以我们一般使用链试实现，关于这个算法我用C语言进行如下实现。
当使用链试实现的时候代替 时间复杂度为O(1) 出于演示并没有写free 释放内存
但是我们也可以想到关于固定位置的元素查找顺序实现其时间复杂度为O(1)，而链表结构则为O(n)
运行如下：
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的方式。插入相反
趋近于数据的规模n及
f(n)=O(n);
可以看到这个时候代价比较高，所以我们一般使用链试实现，关于这个算法我用C语言进行如下实现。
当使用链试实现的时候代替 时间复杂度为O(1) 出于演示并没有写free 释放内存
但是我们也可以想到关于固定位置的元素查找顺序实现其时间复杂度为O(1)，而链表结构则为O(n)
点击(此处)折叠或打开
- /*************************************************************************
- > File Name: sqlist.c
- > Author: gaopeng
- > Mail: gaopp_200217@163.com
- > Created Time: Tue 04 Oct 2016 09:12:11 PM CST
- ************************************************************************/
-
- #include<stdio.h>
- #include<stdlib.h>
- #include<string.h>
- #define INITSIZE 10
-
- typedef unsigned int uint;
- typedef int Etype;
-
- typedef struct sqlist
- {
- Etype* elem; //pointer of sqlist base address
- uint length; //current length of elem
- uint m_size; //
- } SQLIST;
-
-
-
- void initsqlist(SQLIST* inlist)
- {
- inlist->elem = (Etype* )malloc(sizeof(Etype)*(INITSIZE+2) + 1);
- inlist->length = 0;
- inlist->m_size = INITSIZE; //maxsize
- }
-
-
- void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion) //insert elem before postion
- {
- int i;
- Etype* newbase;
- if(postion > inlist->length + 1 || postion < 1)
- {
- printf("line table must continuous or postion must>0!\n");
- exit(1);
- }
-
- if(inlist->length + 1 >= inlist->m_size ) //if memory small will give more memory
- {
- if(!(newbase =(Etype* )realloc(inlist->elem,(inlist->length+INITSIZE+2)* sizeof(Etype)+1)))
- {
- printf("mem alloc failed!\n");
- exit(2);
- }
- inlist->elem = newbase;
- inlist->m_size = inlist->m_size+INITSIZE;
- }
-
- for(i=0;i<(inlist->length-postion+2);i++) //every elem +1
- {
- *(inlist->elem+inlist->length+1-i) = * (inlist->elem+inlist->length-i);
- }
- *(inlist->elem+inlist->length+1-i) = ielem; //give value
- inlist->length =inlist->length+1;
- }
-
- void delsqldel(SQLIST* inlist,uint postion) //delete elem of postion every elem -1
- int i;
- if((postion > inlist->length) ||(postion <1))
- {
- printf("give postion is must large than 1 and less than current length\n");
- }
-
- for(i=0;i<(inlist->length-postion) ;i++)
- {
- *(inlist->elem+postion+i) = *(inlist->elem+postion+i+1);
- }
- inlist->length =inlist->length-1;
- }
-
- void view(SQLIST* inlist)
- {
- int i;
- if(inlist->length ==0 )
- {
- printf("init data arrary! no data found!\n");
- exit(3);
- }
- for(i=0;i<inlist->length;i++)
- {
- printf("node:%d values is:%d data length:%d max_size:%d \n",i,*(inlist->elem+i),inlist->length,inlist->m_size);
- }
- }
-
-
- int main(void)
- {
- SQLIST a;
- initsqlist(&a);
- printf("insert two values\n");
- initsqlinsert(&a,5,1);
- initsqlinsert(&a,10,1);
- view(&a);
-
- printf("delete one values\n");
- delsqldel(&a,2);
-
- view(&a);
-
- printf("insert more than 10 values\n");
- initsqlinsert(&a,10,1);
- initsqlinsert(&a,20,1);
- initsqlinsert(&a,30,1);
- initsqlinsert(&a,40,1);
- initsqlinsert(&a,50,1);
- initsqlinsert(&a,10,1);
- initsqlinsert(&a,10,1);
- initsqlinsert(&a,10,1);
- initsqlinsert(&a,10,1);
- initsqlinsert(&a,10,1);
- initsqlinsert(&a,10,1);
- view(&a);
-
-
- return 0;
- }
运行如下：
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的方式。插入相反
