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

对于一个线性表如果我们使用顺序的实现，那么在insert或者delete一个值的时候最坏渐进时间复杂度

趋近于数据的规模n及

f(n)=O(n);

可以看到这个时候代价比较高，所以我们一般使用链试实现，关于这个算法我用C语言进行如下实现。

当使用链试实现的时候代替 时间复杂度为O(1) 出于演示并没有写free 释放内存

但是我们也可以想到关于固定位置的元素查找顺序实现其时间复杂度为O(1)，而链表结构则为O(n)

点击(此处)折叠或打开

/*************************************************************************

    > File Name: sqlist.c

    > Author: gaopeng

    > Mail: [email protected]

    > 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

        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)

        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);

        printf("insert more than 10 values\n");

        initsqlinsert(&a,20,1);

        initsqlinsert(&a,30,1);

        initsqlinsert(&a,40,1);

        initsqlinsert(&a,50,1);

        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的方式。插入相反