資料結構與算法 第三天 線性表（一）

所有筆記參考《大話資料結構》

1 定義

    線性表(List)：零個或多個資料元素的有限序列。

    強調：首先它是一個序列。也就是說，元素之間是有順序的，若元素存在多個，則第一個元素無前驅，最後一個元素無後繼，其他每個元素都有且隻有一個前驅和後繼。

    數學定義：

    若線性表記為(a1,...,ai-1,ai,ai+1,...,an)，則表中ai-1領先餘ai,ai領先于ai+1,稱ai-1是ai的直接前驅元素，ai+1是ai的直接後繼元素。當i=1,2,...,n-1時，ai有且進有一個後繼，當i=2,3,...,n時，ai有且僅有一個直接前驅。

    線性表元素的個數n(n>=0)定義為線性表的長度，當n=0時，稱為空表。

    在較複雜的線性表中，一個資料元素可以由若幹個資料項組成。

2 線性表的抽象資料類型

    ADT 線性表（List）

    Data

        線性表的資料對象集合為{a1,a2,...,an}，每個元素的類型均為DataType。其中，除第一個元素a1外，每一個元素有且隻有一個直接前驅元素，除了最後一個元素an外，每一個元素有且隻有一個直接後繼元素。資料元素之間的關系時一對一的關系。

    Operation

        InitList(*L)： 初始化操作，建立一個空的線性表L。

        ListEmpty(L):  若線性表為空，傳回true，否則傳回false。

        ClearList(*L): 将線性表清空。

        GetElem(L, i, *e)： 将線性表L中的第i個位置元素值傳回給e。

        LocateElem(L, e): 線上性表L中查找與給定值e相等的元素，如果查找成功，傳回該元素在表中序号表示成功； 否則，傳回0表示失敗。

        ListInsert(*L, i, e): 線上性表L中的第i個位置插入新元素e。

        ListDelete(*L, i, *e): 删除線性表L中第i個位置元素，并用e傳回其值。

        ListLength(L): 傳回線性表L中的元素個數

    endADT

3 線性表的順序存儲結構

    定義：用一段位址連續的存儲單元依次存儲線性表的資料元素。

    線性表的順序存儲的結構代碼。

    #define MAXSIZE 20      //存儲空間初始配置設定量

    typedef int ElemType;   //ElemType類型根據實際情況而定，這裡假設為int

    typedef struct{

        ElemType data[MAXSIZE]; //數組存儲資料元素，最大值為MAXSIZE

        int length;     //線性表目前長度

    }SqList;

    數組的長度時存放線性表的存儲空間的長度，存儲配置設定後這個量一般時不變的。

    線性表的長度是線性表中資料元素的個數，随着線性表插入和删除操作的進行這個量是變化的。

4 順序存儲結構的插入與删除

    4.1 擷取元素操作i

        将線性表L中的第i個位置元素值傳回。隻要i的數值在數組下标範圍内，就是把數組第i-1下标的值傳回即可。代碼：

    #define Ok 1

    #define ERROR 0

    #define TRUE 1

    #define FALSE 0

    typedef int Status;

    Status GetElem(SqList L, int i, ElemType *e){

        if(L.length == 0 || i < 1 || i > L.length)

            return ERROR;

        *e = L.data[i - 1];

        return OK;

    }

    4.2 插入操作

        思路：

            1. 如果插入位置不合理，抛出異常；

            2. 如果線性表長度大于等與數組長度，則抛出異常或動态增加容量；

            3. 從最後一個元素開始向前周遊到第i個位置，分别将他們都向後移動一個位置；

            4. 将要插入的元素插入位置i處；

            5. 表長加1。

        實作代碼如下

        Status ListInsert(SqList *L, int i, ElemType e){

            int k;

            if(L->length == MAXSIZE)    //順序表已滿

                return ERROR;

            //當i不再範圍内，i可以插入到末尾，此時線性表其他元素不用挪動，是以此處長度+1

            if(i < 1 || i > L->Length + 1)

                return ERROR;

            if(i <= L->length){  //若插入元素位置不在表尾

                for(k == L->length - 1; k >= i-1; k--){

                    L->data[k + 1] = L->data[k];

                }

            }

            L->data[i-1] = e;   //将新元素插入

            L->length++;

            return OK;

        }

    4.3 删除操作

        思路：

            1.如果删除位置不合理，抛出異常；

            2.取出删除元素；

            3.從删除元素位置開始周遊到最後一個元素位置，分别将他們都向前移動一個位置；

            4.表長減1

        實作代碼如下：

        Status ListDelete(SqList *L, int i, ElemType *e){

            int k;

            if(L->length == 0) //線性表已空

                return ERROR;

            if(i < 1 || i > L->length)  //删除位置不正确

                return ERROR;

            *e = L->data[i -1];

            if(i < L->length){ //如果删除的不是最後的元素

                for(k = i; k < L->length; i++){

                    L->data[k - 1] = L->data[k];

                }

            }

            L->length--;

            return OK;

        }

5. 實作中遇到的問題

    5.1 插入時隻在第一個元素處插入，後面元素都為0？

        if(i <= L->length){  //插入位置在中間，需要移動元素,插入的最後位置是+1處

            for ( k = L->length -1; k >= i - 1; k--) {

                L->data[k + 1] == L->data[k];   //此處把指派寫成了==比較，低級錯誤啊

            }

        }