資料結構：線性表的順序實作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的方式。插入相反