線性表的順序存儲結構的c語言實作

線性表的順序存儲結構可以由一維數組實作；其查找第i個元素的時間複雜度是O(1),直接通路對應下标的數組值即可data[i-1](假設數組從0開始記)；但插入删除操作的時間複雜度是O(n)，因為删除/插入第i個元素時，i号元素其後的所有元素都要相應移動！

#include <stdio.h>
#include <stdlib.h>
//線性表的順序存儲結構
#define MAXSIZE 100
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;//定義元素基本資料類型


//定義結構
//順序存儲結構可以用一維數組實作
typedef struct {
    ElemType data[MAXSIZE];
    int length;//目前連結清單長度
}List;


//有哪些操作？

//1. 初始化，建立一個空的線性表
Status InitList(List *L){

    int i;
    i=0;
    while(i<MAXSIZE){
        L->data[i]=NULL;
        ++i;
    }
    L->length=0;//L->lehgth等同于(*L).length
    return OK;
}

//2. 判斷線性表是否為空
Status ListEmpty(List L){
    //若線性表為空，傳回true

    //此處不能用L->length,L->length等同于(*L).length
    if(0==L.length){
        return TRUE;
    }else {
        return FALSE;
    }

}

//3. 線性表的整表建立
Status CreateList(List *L,int n){
    //建立長度為n的線性表
    if(n>MAXSIZE || n<1){
        return ERROR;
    }
    srand(time(0));
    int i;
    for(i=0;i<n;i++){
        L->data[i]=rand()%100+1;
    }
    L->length=n;
    return OK;
}

//4. 線性表的元素擷取
Status GetElem(List L,int i,ElemType *e){
    //将線性表第i個位置上的元素傳回給e
    if(i>MAXSIZE || i<1 || i>L.length){
        return ERROR;
    }
    *e=L.data[i-1];
    return OK;
}

//5. 線性表 插入元素
Status InsertElem(List *L,int i,ElemType e){
//在第i号位置上插入元素e，i的範圍從1~L->length+1
    if(MAXSIZE==L->length){
            //線性表空間已經滿了
        printf("空間已滿！\n");
        return ERROR;
    }
    if(i<1 || i>(L->length+1)){
        printf("插入元素位置超界！\n");
        return ERROR;
    }
    //插入後，其後的元素都要後移
    int j;

    for(j=L->length;j>=i;j--){
        //原來線性表中第i個元素到最後一個元素要依次往後移動
        L->data[j]=L->data[j-1];

    }
    L->data[i-1]=e;
    //插入之後，線性表的長度加1
    ++(L->length);
    return OK;

}

//6. 線性表 删除元素
Status DeleteElem(List *L,int i,ElemType *e){
    // 删除第i個位置的元素，并把值傳回給e;i從1~L->length
    if(i<1 || i>L->length){
        printf("删除元素位置有誤");
        return ERROR;
    }
    *e=L->data[i-1];
    //原線性表中第i+1~L->length位置的元素依次前移
    int j;
    for(j=i;j<L->length;j++){
        L->data[j-1]=L->data[j];
    }
    --(L->length);
    return OK;
}
//7. 線性表的整表删除
Status DeleteList(List *L){
    if(TRUE==ListEmpty(*L)){
        printf("目前線性表已經為空，不必進行此項操作！");
        return ERROR;
    }
    int i;
    for(i=0;i<L->length;i++){
        L->data[i]=NULL;
    }
    L->length=0;
    return OK;
}
int main()
{
    List L;
    if(OK==InitList(&L)){
        printf("初始化成功，目前線性表長度為：%d\n",L.length);
    }else{
        printf("初始化失敗！\n");
    }

    if(TRUE==ListEmpty(L)){
        printf("線性表為空！\n");
    }

    printf("輸入想要建立的線性表(各項數值範圍為1~100)的長度:");
    int i,n;
    scanf("%d",&n);
    if(OK==CreateList(&L,n)){
        for(i=0;i<n;i++){
            printf("%d\t",L.data[i]);
        }
        printf("\n長度為%d\n",n);
    }

    printf("輸入想要插入的元素的位置及其值，用逗号分隔\n");
    int location,e;
    scanf("%d,%d",&location,&e);
    if(OK==InsertElem(&L,location,e)){
        printf("插入後的線性表為：\n");
        for(i=0;i<L.length;i++){
            printf("%d\t",L.data[i]);
        }
         printf("\n目前線性表的長度為%d\n",L.length);
    }
    printf("輸入想要删除的元素位置:");
    scanf("%d",&location);
    if(OK==DeleteElem(&L,location,&e)){
        printf("\n删除的第%d個元素是%d\n",location,e);
        printf("删除後的線性表為：\n");
        for(i=0;i<L.length;i++){
            printf("%d\t",L.data[i]);
        }
         printf("\n目前線性表的長度為%d\n",L.length);
    }
    printf("清空線性表！");
    if(OK==DeleteList(&L)){
        printf("線性表長度為%d,清空成功！\n",L.length);
    }else{
        printf("清空失敗！\n");
    }
    return 0;
}