【數據結構】線性表（一）：順序列表

　　線性表(linear_list)是最常用且最簡單的一種數據結構，簡言之，一個線性表是n個數據元素的有序序列。

?

例如：（a₁?, ... ,?a_i-1 , a_i , a_i+1 , ... , a_n)：a_i-1?是 a_i 的直接前驅，a_i+1 是 a_i 的直接后驅。

并且，當 i = 1，2，... ，n-1：a_i 有且只有一個直接后驅。當 i = 2，3，... ，n：a_i 有且只有一個直接前驅

　　

例子：已知線性表LA，LB中的數據元素按值非遞減有序排列，現將LA，LB按值非遞減排列合并為LC。其偽代碼為：

void MergeList(List La, List Lb, List &Lc) {
        initList(Lc);  //初始化Lc
        i = j = 1;
        k = 0;
        La_len = ListLength(La);
        Lb_len = ListLength(Lb);
        while((i <= La_len) && (j <= Lb_len){//La與Lb均非空
            GetElem(La, i, ai);
            GetElem(Lb, j, bj);
            if(ai <= bj) {ListInsert(Lc, ++k, ai); ++i; }
            else{ListInsert(Lc, ++k, bi); ++j;}
        }
        while(i <= La_len){       //La中剩余值插入Lc
            GetElem(La, i++, ai);
            ListInsert(Lc, ++k, ai);
        }
        while(j <= Lb_len){       //Lb中剩余值插入Lc
            GetElem(Lb, j++, bj);
            ListInsert(Lc, ++k, bj);
        }
}

　　分析：GetElem 和 ListInsert 這兩個操作的執行時間和表長無關，所以該算法的事件復雜度為O(ListLength(LA) + ListLength(LB))。

?

線性表的順序表示和實現：順序表示指的是用一組地址連續的存儲單元依次存儲線性表的數據元素。

所以可以用 LOC(a_i) = LOC(a₁) + (i-1) * l ?來表示a_i的地址（其中：l 表示每個元素所占存儲單元）

優點：輕松實現隨機存儲。

順序表的初始化、插入、刪除、合并的偽代碼如下：

?

// -------------線性表的動態分配順序存儲結構--------------
#define LIST_INIT_SIZE 100   //線性表存儲空間的初始化分配量
#define LISTINCREMENT 10     //線性表存儲空間的分配增量
typedef struct{
    ElemType *elem;     //存儲空間基址
    int length;         //當前長度
    int listsize;       //當前分配的存儲容量(以sizeof(ElemType)為單位)
}SqList;

//-----------初始化順序表--------------
Status InitList_Sq(SqList &L){
    //構造一個空的線性表
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if(! L.elem)  eixt(OVERFLOW);       //存儲分配失敗
    L.length = 0;                       //空表長度為0
    L.listsize = LIST_INIT_SIZE;        //初始存儲容量
    return OK;
}

//------------順序表的插入算法-------------時間復雜度為O(n)
Status ListInsert_Sq(SqList &L, int i, ElemType e) {
    //在順序線性表L中第i個位置之前插入新的元素e
    //i的合法值為1<=i<=ListLength_Sq(L)+1
    if((i<1) || (i>L.length+1))  return ERROR;        //i值不合法
    if(L.length >= L.listsize){           //當前存儲空間已滿，增加分配
        newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemTpye));
        if(!newbase) exit(OVERFLOW);        //存儲分配失敗
        L.elem = newbase;               //新基址
        L.listsize += LISTINCREMENT;        //增加存儲容量
    }
    q = &(L.elem[i-1]);         //q為插入位置
    for(p = &(L.elem[L.length-1]); p >= q; --p) 
        *(p+1) = *p;            //插入位置及之后的元素右移
        *q = e;             //插入e
        ++L.length;         //表長增一
        return OK;
}

//-------------順序表的刪除操作--------------時間復雜度為O(n)
Status ListDelete_Sq(SqList &L, int i, ElemType &e){
    //在順序線性表L中刪除第i個元素，并用e返回其值。
    if((i<1) || (i>L.length)) return ERROR;     //i值不合法
    p = &(L.elem[i-1]);             //p為被刪除元素的位置
    e = *p;         //被刪除元素的值賦給e
    q = L.elem + L.length-1;        //表尾元素的位置
    for(++p; p <= q; ++p){
        *(p-1) = *p;    //被刪除元素之后的元素左移
    }
    --L.length;         //表長減1
    return OK;
}

//-----------查找制定元素的位序---------------事件復雜度為O(n)
int LocateElem_Sq(SqList L, ElemType e, Status (* compare)(ElemType, ElemType)){
    //在順序線性表L中查找第1個值與e滿足compare()的元素的位序
    //若找到，則返回其在L中的位序，否則返回0
    i = 1;              //i的初值為第一個元素的位序
    p = L.elem;         //p的初值為第一個元素的存儲位置
    while(i <= L.length && !(* compare)(*p++, e)) ++i;
    if(i<L.length) return i;
    else return 0;
}

//------------對于順序表的合并------------------時間復雜度為O(La.length + Lb.length)
void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) {
    pa = La.elem;
    pb = Lb.elem;
    Lc.listsize = Lc.length = La.length + Lb.length;
    pc = Lc.elem = (ElemType *) malloc (Lc.listsize*sizeof(ElemType));
    if(!Lc.elem) exit(OVERFLOW);        //存儲分配失敗
    pa_last = La.elem + La.length -1;
    pb_last = Lb.elem + Lb.length -1;
    while(pa <= pa_last && pb <= pb_last){  //歸并
        if(*pa <= *pb) *pc++ = *pa++;
        else *pc++ = *pb++;
    }
    while(pa <= pa_last) *pc++ = *pa++;
    while(pb <= pb_last) *pc++ = *pa++;
}?

---

?

　　C語言代碼實現：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define LIST_INIT_SIZE 100      //線性表存儲空間初始分配量
#define LISTINCREMENT 10        //線性表存儲空間的分配增量

typedef struct {
    int *elem;      //存儲空間基址
    int length;     //當前長度
    int listsize;   //當前分配的存儲空間容量（以sizeof(int)為單位
}SqList;

//初始化一個新表
void InitList_Sq(SqList *L){
    //構造一個空的線性表L
    (*L).elem = (int *) malloc(LIST_INIT_SIZE*sizeof(int));
    if(!(*L).elem) exit(-1);     //存儲分配失敗
    (*L).length = 0;
    (*L).listsize = LIST_INIT_SIZE;
}

//向表中第i個位置出插入一個數e
void ListInsert_Sq(SqList *L, int i, int e){
    if(i<1 || i>(*L).length+1) {
        printf("插入時i值不合法...\n");
        exit(-1);
    }
    if((*L).length > (*L).listsize) {     //當前存儲空間已滿，增加分配
        int *newbase = (int *)realloc((*L).elem, ((*L).length+LISTINCREMENT)*sizeof(int));
        if(!newbase) exit(-1);
        (*L).elem = newbase;
        (*L).listsize += LISTINCREMENT;
    }
    int *q = &(*L).elem[i-1];
    for(int *p=&(*L).elem[(*L).length -1];p>=q;--p){
        *(p+1) = *p;
    }
    *q = e;
    ++(*L).length;
}

//刪除表中第i個位置的數并返回到e中
void ListDelete_Sq(SqList *L, int i, int *e){
    if(i<1 || i>(*L).length){
        printf("刪除時i值不合法...\n");
        exit(-1);
    }
    int *p = &(*L).elem[i-1];       //要刪除的元素
    *e = *p;                        //被刪除的元素賦值給e
    int *q = &(*L).elem[(*L).length-1];     //表尾元素
    for(++p;p<=q;p++){          //被刪除元素之后的元素左移
        *(p-1) = *p;            
    }
    --(*L).length;
}

void MergeList_Sq(SqList La, SqList Lb, SqList *Lc){
    //已知順序表La，Lb的元素按值非遞減排列
    //歸并La，Lb得到新的順序列表Lc，Lc的元素也按值非遞減排列
    int *pa = La.elem;
    int *pb = Lb.elem;
    (*Lc).listsize = (*Lc).length = La.length + Lb.length;
    int *pc = (*Lc).elem = (int *)malloc((*Lc).listsize * sizeof(int));
    if(!(*Lc).elem){
        printf("內存分配失敗...\n");
        exit(-1);
    }
    int *pa_last = La.elem + La.length -1;      //La的表尾元素地址
    int *pb_last = Lb.elem + Lb.length -1;      //Lb的表尾元素地址
    while(pa<=pa_last && pb<=pb_last){
        if(*pa <= *pb){
            *pc++ = *pa++;
        }else{
            *pc++ = *pb++;
        }
    }
    while(pa<=pa_last){         //插入La剩余的元素
        *pc++ = *pa++;          //插入Lb剩余的元素
    }
    while(pb <= pb_last){
        *pc++ = *pb++;
    }
}

//查看順序表中第一個的滿足compare()的元素的位序
int LocateElem_Sq(SqList L, int e, int (* compare)(int x, int y)){
    int i = 1;
    int *p = L.elem;
    while(i <= L.length && !(*compare)(*p++, e)){
        ++i;
    }
    if(i <= L.length){
        return i;
    }else{
        return 0;
    }
}

int cmp(int x, int y){
    if(x == y){
        //printf("x=y\n");
        return 1;
    }else{
        //printf("x!=y\n");
        return 0;
    }
}
int main(){
    SqList La;
    SqList Lb;
    SqList Lc;
    int N,e;
    InitList_Sq(&La);
    printf("輸入La元素的個數N：");
    scanf("%d",&N);
    printf("輸入La的元素：");
    while(N--){
        scanf("%d",&e);
        int i =La.length+1;
        ListInsert_Sq(&La,i,e);
    }
    InitList_Sq(&Lb);
    printf("輸入Lb元素的個數N：");
    scanf("%d",&N);
    printf("輸入Lb的元素：");
    while(N--){
        scanf("%d",&e);
        int i =Lb.length+1;
        ListInsert_Sq(&Lb,i,e);
    }
    printf("此時La中的元素順序表的值為：");
    for(int i=0;i<La.length;i++){
        printf("%d ",La.elem[i]);
    }
    printf("\nLa.length = %d\tLa.listsize = %d\n",La.length,La.listsize);
    printf("此時Lb中的元素順序表的值為：");
    for(int i=0;i<Lb.length;i++){
        printf("%d ",Lb.elem[i]);
    }
    printf("\nLb.length = %d\tLb.listsize = %d\n",Lb.length,Lb.listsize);
    ListDelete_Sq(&La,4,&e);
    printf("刪除第四個元素后La的元素順序表的值為：");
    for(int i=0;i<La.length;i++){
        printf("%d ",La.elem[i]);
    }
    printf("\nLa.length = %d\tLa.listsize = %d\te = %d\n",La.length,La.listsize,e);
    MergeList_Sq(La, Lb, &Lc);
    printf("La和Lb合并后得到Lc，其Lc的信息為：\n");
    printf("Lc的元素順序表為：");
    for(int i=0;i<Lc.length;i++){
        printf("%d ",Lc.elem[i]);
    }
    printf("\nLc.length = %d\tLc.listsize = %d\n",Lc.length,Lc.listsize);
    printf("輸入你要在Lc中查找的元素e：");
    scanf("%d",&e);
    printf("該元素e在Lc的位序位：%d\n",LocateElem_Sq(Lc, e, cmp));
158　　　free(La.elem);free(Lb.elem);free(Lc.elem);return 0;
}

---

　　結果為：

　　

?