線性表

線性表的定義和基本操作

InitList(&L)：初始化表。構(gòu)造一個(gè)空的線性表L，分配內(nèi)存空間。

DestroyList(&L)：銷毀操作。銷毀線性表，并釋放線性表L所占用的內(nèi)存空間。

ListInsert(&L,i,e)：插入操作。在表L中的第i個(gè)位置上插入指定元素e。

ListDelete(&L,i,&e)：刪除操作。刪除表L中第i個(gè)位置的元素，并用e返回刪除元素的值。

LocateElem(L,e)：按值查找操作。在表L中查找具有給定關(guān)鍵字值的元素。

GetElem(L,i)：按位查找操作。獲取表L中第i個(gè)位置的元素的值。

其他常用操作：

Length(L)：求表長。返回線性表L的長度，即L中數(shù)據(jù)元素的個(gè)數(shù)。

PrintList(L)：輸出操作。按前后順序輸出線性表L的所有元素值。

Empty(L)：判空操作。若L為空表，則返回true，否則返回false。

Tips：

①對數(shù)據(jù)的操作（記憶思路） —— 創(chuàng)銷、增刪改查

②C語言函數(shù)的定義 —— <返回值類型> 函數(shù)名 (<參數(shù)1類型> 參數(shù)1，<參數(shù)2類型> 參數(shù)2，……)

③實(shí)際開發(fā)中，可根據(jù)實(shí)際需求定義其他的基本操作

④函數(shù)名和參數(shù)的形式、命名都可改變（Reference：嚴(yán)蔚敏版《數(shù)據(jù)結(jié)構(gòu)》）

⑤什么時(shí)候要傳入引用“&” —— 對參數(shù)的修改結(jié)果需要“帶回來”

線性表的順序表示

邏輯上相鄰的兩個(gè)元素物理上也相鄰

InitList(&L)的使用

靜態(tài)分配

#include?
#define?MaxSize?10

//?定義結(jié)構(gòu)體
typedef?struct?{
????int?data[MaxSize];
????int?length;
}?SqList;

//?順序表初始化函數(shù)
void?InitList(SqList?&L)?{
????for?(int?i?=?0;?i?????????L.data[i]?=?0;//將所有元素的初始值默認(rèn)設(shè)置為0
????????//這一步其實(shí)可以省略，但是省略之后，有可能受到內(nèi)存中"臟數(shù)據(jù)"的影響
????}
????L.length?=?0;?//因?yàn)榇藭r(shí)還沒存入元素，所以是零，上面只是初始化，不算存入

}

//?主函數(shù)
int?main()?{
????SqList?L;
?InitList(L);
?for?(int?i?=?0;?i???printf("data[%d]=%d\n",?i,?L.data[i]);
?}
????return?0;
}

動(dòng)態(tài)分配

#include?
#include?
#?define?InitSize?10

//?定義結(jié)構(gòu)體
typedef?struct?{
?//?Elem?Type?*data;
?int?*data;
?int?MaxSize;
?int?length;
}SeqList;

//?初始化函數(shù)
void?InitList(SeqList?&L)?{
?L.data?=?(int?*)malloc(InitSize*sizeof(int));
?L.MaxSize?=?InitSize;
?for?(int?i?=?0;?i???L.data[i]?=?i+1;//為了后續(xù)動(dòng)態(tài)擴(kuò)展操作效果，將所有元素存入值
?}
?L.length?=?10;
}

//?增加動(dòng)態(tài)數(shù)組的長度
void?IncreaseSize(SeqList?&L,?int?len){
?int?*p?=?L.data;
?L.data?=?(int?*)malloc((L.MaxSize+len)*sizeof(int));
?for?(int?i?=?0;?i???L.data[i]?=?p[i];
?}
?L.MaxSize?=?InitSize?+?len;
?free(p);
}

//?主函數(shù)
int?main(){
?SeqList?L;
?InitList(L);
?IncreaseSize(L,?5);
?for?(int?i?=?0;?i???printf("data[%d]=%d\n",?i,?L.data[i]);
?}
?return?0;
}

順序表的特點(diǎn)：

①隨機(jī)訪問，即可以在 O(1) 時(shí)間內(nèi)找到第 i 個(gè)元素。②存儲密度高，每個(gè)節(jié)點(diǎn)只存儲數(shù)據(jù)元素 ③拓展容量不方便（即便采用動(dòng)態(tài)分配的方式實(shí)現(xiàn)，拓展長度的時(shí)間復(fù)雜度也比較高） ④插入、刪除操作不方便，需要移動(dòng)大量元素

順序表的基本操作——插入

ListInsert(&L,i,e)的使用

#include?
#define?MaxSize?10?//定義最大長度

//定義結(jié)構(gòu)體
typedef?struct{
?int?data[MaxSize];?//用靜態(tài)的數(shù)組存放數(shù)據(jù)元素
?int?length;?//?順序表的當(dāng)前長度
}SqList;??//?順序表的類型定義

//?初始化函數(shù)
void?InitList(SqList?&L)?{
????for?(int?i?=?0;?i?????????L.data[i]?=?0;//將所有元素的初始值默認(rèn)設(shè)置為0
????????//這一步其實(shí)可以省略，但是省略之后，有可能受到內(nèi)存中"臟數(shù)據(jù)"的影響
????}
????L.length?=?0;?//因?yàn)榇藭r(shí)還沒存入元素，所以是零，上面只是初始化，不算存入
}

//插入元素函數(shù)
bool?ListInsert(SqList?&L,?int?i,?int?e){
?if(i<1||i>L.length+1){
??return?false;??//?容錯(cuò)，判斷i是否有效
?}
?if(L.length>=MaxSize){
??return?false;??//容錯(cuò)，當(dāng)前存儲空間已滿，不能插入
?}
?for(int?j=L.length;?j>=i;?j--){
??L.data[j]=L.data[j-1];?//?將i之后的元素依次后移
?}
?L.data[i-1]=e;??//將位置i放入e
?L.length++;?//長度+1
?return?true;
}

//?主函數(shù)
int?main(){
?SqList?L;?//聲明一個(gè)順序表
?InitList(L);?//初始化順序表
?for?(int?i?=?0;?i?5;?i++)?{
??L.data[i]?=?i+1;//為了后續(xù)插入操作效果，將前5個(gè)元素存入值
??L.length++;
?}
?if?(ListInsert(L,?100,?3)){
??printf("插入成功\n");
?}
?else?{
??printf("插入失敗\n");
?}
?for?(int?i?=?0;?i???printf("data[%d]=%d\n",?i,?L.data[i]);
?}
}

插入操作的時(shí)間復(fù)雜度

O(n)

順序表的基本操作——?jiǎng)h除

ListDelete(&L,i,&e)的使用

#include?
#define?MaxSize?10?//定義最大長度

//定義結(jié)構(gòu)體
typedef?struct{
?int?data[MaxSize];?//用靜態(tài)的數(shù)組存放數(shù)據(jù)元素
?int?length;?//?順序表的當(dāng)前長度
}SqList;??//?順序表的類型定義

//?初始化函數(shù)
void?InitList(SqList?&L)?{
????for?(int?i?=?0;?i?????????L.data[i]?=?0;//將所有元素的初始值默認(rèn)設(shè)置為0
????????//這一步其實(shí)可以省略，但是省略之后，有可能受到內(nèi)存中"臟數(shù)據(jù)"的影響
????}
????L.length?=?0;?//因?yàn)榇藭r(shí)還沒存入元素，所以是零，上面只是初始化，不算存入
}

//插入元素函數(shù)
bool?ListDelete(SqList?&L,?int?i,?int?&e){
?if(i<1||i>L.length+1){
??return?false;??//?容錯(cuò)，判斷i是否有效
?}
?e?=?L.data[i-1];
?for(int?j=i;?j??L.data[j-1]=L.data[j];?//?將i之后的元素依次前移
?}
?L.length--;?//長度-1
?return?true;
}

//?主函數(shù)
int?main(){
?SqList?L;?//聲明一個(gè)順序表
?InitList(L);?//初始化順序表
?for?(int?i?=?0;?i?5;?i++)?{
??L.data[i]?=?i+1;//為了后續(xù)插入操作效果，將前5個(gè)元素存入值
??L.length++;
?}
?int?e?=?-1;
?if?(ListDelete(L,?3,?e)){
??printf("刪除成功[%d]\n",?e);
?}
?else?{
??printf("刪除失敗\n");
?}
?for?(int?i?=?0;?i???printf("data[%d]=%d\n",?i,?L.data[i]);
?}
}

刪除操作的時(shí)間復(fù)雜度

O(n)

順序表的按位查找

GetElem(L,i)的使用

#include?
#include?
#define?InitSize?10?//順序表的初始長度
typedef?struct{
?int?*data;?//指示動(dòng)態(tài)分配數(shù)組的指針
?int?MaxSize;?//順序表的最大容量
?int?length;?//順序表的當(dāng)前長度
}?SeqList;?//順序表的類型定義（動(dòng)態(tài)分配方式）

//?初始化函數(shù)
void?InitList(SeqList?&L)?{
?L.data?=?(int?*)malloc(InitSize*sizeof(int));
?L.MaxSize?=?InitSize;
?for?(int?i?=?0;?i???L.data[i]?=?i+1;?//所有的值給定i+1
??L.length++;
?}
}

//?按位查找
int?GetElem(SeqList?L,?int?i){
?return?L.data[i-1];?
}

//?主函數(shù)
int?main()?{
????SeqList?L;
?InitList(L);
?printf("get?data[%d]\n",?GetElem(L,?3));
?for?(int?i?=?0;?i???printf("data[%d]=%d\n",?i,?L.data[i]);
?}
?
????return?0;
}

按位查找的時(shí)間復(fù)雜度

O(1)

順序表的按值查找

LocateElem(L,e)的使用

#include?
#include?
#define?InitSize?10?//順序表的初始長度
typedef?struct{
?int?*data;?//指示動(dòng)態(tài)分配數(shù)組的指針
?int?MaxSize;?//順序表的最大容量
?int?length;?//順序表的當(dāng)前長度
}?SeqList;?//順序表的類型定義（動(dòng)態(tài)分配方式）

//?初始化函數(shù)
void?InitList(SeqList?&L)?{
?L.data?=?(int?*)malloc(InitSize*sizeof(int));
?L.MaxSize?=?InitSize;
?for?(int?i?=?0;?i???L.data[i]?=?i*i;?//所有的值給定i+1
??L.length++;
?}
}

//?按位查找
int?LocateElem(SeqList?L,?int?e){
?for(int?i=0;i??if(L.data[i]==e)
??return?i+1;?//數(shù)組下標(biāo)為i的元素值等于e，返回其位序i+1
?}
?return?0;?
}

//?主函數(shù)
int?main()?{
????SeqList?L;
?InitList(L);
?printf("e的位序[%d]\n",?LocateElem(L,?9));
?for?(int?i?=?0;?i???printf("data[%d]=%d\n",?i,?L.data[i]);
?}
?
????return?0;
}

按值查找的時(shí)間復(fù)雜度

O(n)