資料結構與算法分析--線性表

在讀研開始，需要了解一些資料結構方面的知識，就自己努力的敲代碼啊。。。

在補習過程中，看了兩位大神的著作：程傑的《大話資料結構》、解學武老師的網頁文章。感覺很受用，再次表示感謝。

直接開始線性表：線性表、單連結清單、雙連結清單、循環連結清單、靜态連結清單。

線性表存儲方式：

//循環集合B中的每個元素，判斷目前元素是否在A中，若不存在，則插入到A中
void union(List *La,List *Lb){
    int La_len,Lb_len,i; 
    ElemType e; /*聲明La和Lb相同的資料元素e*/
    La_len=ListLength(La);    /*求線性表的長度*/
    Lb_len=LiatLength(Lb);
    for(i=0;i<Lb_len;i++){
        GetElem(Lb,i,e);    /*取Lb中第i個資料元素給e*/
        if(!LocatElem(La,e,equal))
            ListInsert(La,++La_len,e);    
    }
}


           

線性表的資料就結構實作：

#define MAXSIZE 20     /*存儲空間初試配置設定量*/
typedef int ElemType;    /*ElemType類型根據實際情況而定，假設int */
typedef struct｛
    ElemType data[MAXSIZE];    /*數組存儲資料元素，最大值MAXSIZE*/
    int length;    /*線性表目前長度*/
｝Sqliat;
           

順序存儲結構的操作：

獲得元素的實作：

/*初始條件：順序表L已經存在
實作結果：用e傳回L中第i個資料元素的值*/
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/*Status是函數的類型，其值是函數結果的狀态碼*/

Status GetElem(SqList L,int i,ElemType *e){
    if(L.length==0||i<1||i>L.length)
        return ERROR;
    *e=data[i-1];
    retrurn OK;
}
           

插入操作實作：

/*初始條件：順序表已經存在，
操作結果：在L中第i個位置之前插入新的資料元素e,L的長度加一*/
Status ListInsert(SqList *L,int i,ElemType e){
    int k;
    if(L->length==MAXSIZE)//表滿
        return ERROR;
    if(i<1||i>L->length-1) //當i不在範圍内
        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;
    
}
           

删除資料的實作：

/*初始條件：順序線性表已經存在
操作結果：删除L的第i個資料元素，并用e傳回其值，L的長度減一*/

Status ListDelete(SqList *L,int i,ElemType *e){
    int k;
    if(L->length==0) //線性表為空
        return ERROR;
    if(i<1||i>length)//删除位置不正确
        return ERROR;
    *e=L->data[i-1];
    if(i<L->length){    //删除位置不是最後位置
        for(k=i;k<L->length;k++)
            L->data[k-1]=L->data[k];
    }
    L->length--;
    return OK;
}
           

單連結清單存儲方式：

循環連結清單存儲方式：

靜态連結清單存存儲方式：

雙連結清單存儲方式：

實踐例子：