线性表（一）顺序表示与实现

引言

线性表是最常用且最简单的一种数据结构，一个线性表是n个数据元素的有限序列。它的数据元素ElemType可以有不同的含义，可以是一个数，也可以是一本书，具体取决于ElemType实际定义。线性表中元素的个数n(>=0)定义为线性表的长度，n=0时称为空表。线性表一个相当灵活的数据结构，对线性表不仅可以进行访问，还可以进行插入和删除等操作。

顺序表示

定义： 线性表的顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素，这种表示称为线性表的顺序存储结构。通常称这种线性表为顺序表。它的特点是：表中相邻的元素a_i和a_i+1在计算机内的物理存储位置也相邻。
优点：只要确定了存储顺序表的起始位置，表中任一元素均可随机存取。
缺点：在作插入或删除操作时，需移动大量元素。

具体实现

元素定义

线性表中元素类型ElemType需根据实际需要来定义，本文定义为int类型。

typedef int ElemType;

ElemType也可以定义为结构体，例如在后续讲多项式的时候，ElemType定义为：

typedef  struct {
         float coef;
         int exp;
} ElemType;

顺序表定义

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct {
        ElemType *base;
        int length;
        int listsize;
}SqList;

在上述定义中，数组elem指示顺序表的基地址，length指示顺序表的当前长度。listsize指示顺序表当前分配的存储空间大小，一旦因插入导致空间不足，可进行再分配，为顺序表增加一个LISTINCREMENT个数据元素的空间。

基本操作

#include <stdio.h> 
#include <stdlib.h>
#define LIST_INIT_SIZE 100      //列表存储空间的初始分配量
#define LIST_INCREMENT 10       //列表存储空间分配增量
#define TRUE 1  //真值
#define FALSE 0 //假值
#define SUCCESS 1        //成功标识
#define FAILURE -1      //失败标识

typedef int ElemType;    // 基本数据元素

//ElemType相关函数
//比较, 需根据elem类型实时更改, 这里ElemType定义为为int类型
int compare(ElemType e1, ElemType e2){
        if(e1 == e2) return 0;
        else if(e1 > e2) return 1;
        else if(e1 < e2) return -1;    
}

//visit ElemType元素
int visit(ElemType e){ 
        printf("%d ", e); 
        return SUCCESS;
}

typedef struct{
        ElemType *elem;
        int length;     //当前长度
        int listsize;   //当前分配的存储容量
}SqList;

int InitList_Sq(SqList *L){
        // 构造一个空的线性表L
        L->elem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType));
        if (!L->elem) exit(-1);         //容量分配失败
        L->length = 0;
        L->listsize = LIST_INIT_SIZE;
        return SUCCESS; 
} 

int ListInsert_Sq(SqList *L, int i, ElemType e){ 
        // 在第i个位置之前插入e
        // i的有效位置为1<=i<=L->length
        if(i<1 || i>L->length+1) return FAILURE; 
        if(L->length >= L->listsize){   //空间已满
                ElemType *elem = (ElemType *)realloc(L->elem, 
                                LIST_INCREMENT*sizeof(ElemType));
                if(!elem){
                        printf("内存分配失败，即将退出\n");
                        exit(-1);       //重新分配失败
                }   
                L->elem = elem;
                L->listsize += LIST_INCREMENT;
        }   
        ElemType *p = L->elem + i - 1;
        ElemType *q = L->elem + L->length - 1;
        for(; q>=p; --q) *(q+1) = *q; 
        *p = e;
        L->length++;
        return SUCCESS;    
}

int ListDelete_Sq(SqList *L, int i, ElemType *e){
        // 删除顺序表中第i位置元素
        if (i < 1 || i > L->length) return FAILURE; 
        ElemType *p = L->elem + i-1;    //被删除元素的位置      
        *e = *p;        //返回被删除元素        
        ElemType *q = L->elem + L->length - 1;
        for(p;p<q; ++p) *p = *(p+1);
        L->length--;
        return SUCCESS;
}

int LocateElem_Sq(SqList L, ElemType e, int (*compare)(ElemType, ElemType)){
        // 返回L中第一个与e满足compare关系为0的元素的位序，如无则返回-1
        int i = 1;
        ElemType *p = L.elem;
        while(i <= L.length && compare(*p++, e) != 0) i++;
        if (i<= L.length) return i;
        return FAILURE;
}

void MergeList_Sq(SqList La, SqList Lb, SqList *Lc){
        //已知La和Lb为非递减的顺序表序列
        //归并La和Lb为新的顺序表Lc，Lc中元素非递减排列
        ElemType *pa = La.elem, *pb = Lb.elem;

        Lc->listsize = Lc->length = La.length + Lb.length;
        ElemType *pc = Lc->elem = (ElemType *)malloc(Lc->listsize *
                        sizeof(ElemType));
        if(!Lc->elem) exit(-1); //存储分配失败
        ElemType *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++ = *pb++;
}

int ListEmpty_Sq(SqList L){
        //判断L是否为空
        if(L.length == 0){
                return TRUE;
        } else {
                return FALSE;
        }
}

int ListLength_Sq(SqList L){
        //如果L为顺序表，返回L长度
        if(L.elem != NULL){
                return L.length;
        } else {
                return -1;
        }
}

int PriorElem_Sq(SqList L, ElemType cur_e, ElemType *pre_e){
        //若cur_e为L中元素，且不是第一个，则用pre_e返回它的前驱
        ElemType *p = L.elem, *q = L.elem + L.length - 1;
        while(p < q){
                if(*(p+1) == cur_e){
                        *pre_e = *p;
                        return SUCCESS;
                }
                p++;
        }
        return FAILURE;
}

int NextElem_Sq(SqList L, ElemType cur_e, ElemType *next_e){
        //若cur_e是L中数据元素，且不是最后一个，则用next_e返回它的后继元素
        int pos = LocateElem_Sq(L, cur_e, compare);
        if(pos >= L.length || pos < 1) return FAILURE;  //查找失败
        int i = 1;
        ElemType *p = L.elem;
        while(i <= pos) {
                p++;
                i++;
        }
        *next_e = *p;
        return SUCCESS;
}

int ListTraverse_Sq(SqList L, int(*visit)(ElemType)){
        ElemType *p = L.elem;   // 起始位置
        ElemType *p_last = L.elem + L.length - 1;       // 结束位置
        while(p <= p_last){
                if(!(visit(*p++))) return FAILURE;
        }
        return SUCCESS;
}

void DestroyList_Sq(SqList *L){
        //销毁线性表L
        if(L->elem != NULL){
                free(L->elem); //释放内存空间
                L->elem = NULL;
                L->length = 0;
                L->listsize = 0;
        }
}

void ClearList_Sq(SqList *L){
        if(L->elem != NULL){
                L->length = 0;  //是否为空判断依据
        }
}

int main(){
        ElemType a[10] = {2,4,5,6,7,8,9,3,5,7};
        // declare L
        SqList *L;
        // init
        InitList_Sq(L);
        printf("\nInit list *************\n");
        printf("Init List, L.length: %d, L.size: %d\n", L->length, L->listsize);
        // insert element 
        printf("\nInsert element ***********\n");
        int i;
        for(i=1;i<=10;i++){
                if(!ListInsert_Sq(L, i, a[i-1])){
                        printf("insert failure!");
                }
        }
        printf("Insert List, now L.length: %d, L.size: %d\n", L->length,
                        L->listsize);
        // traverse
        printf("\ntraverse ********************\n");
        printf("now elems: ");
        ListTraverse_Sq(*L, visit);
        printf("\n");
        // delete
        printf("\ndelete element **********************\n");
        ElemType e;
        if(ListDelete_Sq(L, 5, &e) > 0){
                printf("Success delete value at 5 index: %d\n", e);
        } else {
                printf("delete value at 5 index failure\n");
        }
        // another delete
        ElemType f;
        if(ListDelete_Sq(L, 11, &f) > 0){
                printf("Success delete value at 11 index: %d", f);
        } else {
                printf("delete value at 11 index failure");
        }
        printf("\nnow elem: ");
        ListTraverse_Sq(*L, visit);
        printf("\nAfter delete: length: %d, size: %d\n", L->length,
                        L->listsize);
        // search elem
        printf("\nSearch elem **********************\n");
        int pos1 = LocateElem_Sq(*L, 3, compare);
        int pos2 = LocateElem_Sq(*L, 11, compare);
        if(pos1 >= 0){
                printf("success find 3 at index: %d\n", pos1);
        } else {
                printf("failure find 3 at list L!");
        }
        if(pos2 >= 0){
                printf("success find 11 at index: %d\n", pos2);
        } else {
                printf("failure find 11 in list L!\n");
        }
        // merge list
        printf("\nMerge Sort List*******************\n");
        int b[] = {1, 4, 5};
        int c[] = {5, 6, 9, 12};
        SqList L1, L2, L3;
        InitList_Sq(&L1);
        InitList_Sq(&L2);
        InitList_Sq(&L3);
        for(i=0;i<3;i++){
                ListInsert_Sq(&L1,i+1,b[i]);
        }
        for(i=0;i<4;i++){
                ListInsert_Sq(&L2, i+1, c[i]);
        }
        printf("Start Merge*********\n");
        MergeList_Sq(L1, L2, &L3);
        printf("L1 elem: ");
        ListTraverse_Sq(L1, visit);
        printf("\nL2 elem: ");
        ListTraverse_Sq(L2, visit);
        printf("\nL3 elem: ");
        ListTraverse_Sq(L3, visit);
        // get length
        printf("\nL3 length is: %d\n", ListLength_Sq(L3));
        // is empty
        if(ListEmpty_Sq(L3)) printf("L3 is empty!\n");
        else printf("L3 is not empty!\n");
        // get prior elem
        ElemType pre_e, next_e;
        int p1, p2, p3, p4;
        p1 = PriorElem_Sq(L3, 1 , &pre_e);
        if(p1 < 0) printf("pre find 1 failure in L3!\n");
        p2 = PriorElem_Sq(L3, 12, &pre_e);
        if(p2 >= 0) printf("prior 12 in L3 is %d\n", pre_e);
        p3 = NextElem_Sq(L3, 1, &next_e);
        if(p3 >= 0) printf("next 1 in L3 is %d\n", next_e);
        p4 = NextElem_Sq(L3, 12, &next_e);
        if(p4 < 0) printf("next find 12 in L3 failure!\n");
        // clear list
        printf("\n\nClear List **********************\n");
        ClearList_Sq(L);
        printf("L length: %d, L size: %d, L elem: %p\n", L->length, L->listsize,
                        L->elem);
        // destroy list
        printf("\nDestroy List **********************\n");
        DestroyList_Sq(L);
        printf("L length: %d, L size: %d, L elem: %p\n", L->length, L->listsize,
                        L->elem);
        if(L->elem){
                printf("L elem: %p\n", L->elem);
        } else {
                printf("L elem is NULL\n");
        }
}

运行结果

*************** Init list *************
Init List, L.length: 0, L.size: 100

*************** Insert element ***********
Insert List, now L.length: 10, L.size: 100

************** traverse ********************
now elems: 2 4 5 6 7 8 9 3 5 7 

************* delete element **********************
Success delete value at 5 index: 7
delete value at 11 index failure
now elem: 2 4 5 6 8 9 3 5 7 
After delete: length: 9, size: 100

************ Search elem **********************
success find 3 at index: 7
failure find 11 in list L!

*********** Merge Sort List*******************
Start Merge*********
L1 elem: 1 4 5 
L2 elem: 5 6 9 12 
L3 elem: 1 4 5 5 6 9 12 
L3 length is: 7
L3 is not empty!
pre find 1 failure in L3!
prior 12 in L3 is 9
next 1 in L3 is 4
next find 12 in L3 failure!


*********** Clear List **********************
L length: 0, L size: 100, L elem: 0x232d010

*********** Destroy List **********************
L length: 0, L size: 0, L elem: (nil)
L elem is NULL