1、線性表的定義

---- 通常，定義線性表為n（n>=0）個(gè)數(shù)據(jù)元素(或稱為表元)的有限序列。記為L=(a1,a2,...,an). 其中L是表名，ai是表中的結(jié)點(diǎn)，

是不可再分割的數(shù)據(jù)。n是表中表元的個(gè)數(shù)，也稱為表的長度，若n=0叫做空表。

---- 在非空的數(shù)據(jù)元素集合中，線性表的特點(diǎn)是：

--- ?1）存在唯一的一個(gè)稱作“第一個(gè)”的元素。

--- ?2）存在唯一的一個(gè)稱作“最后一個(gè)”的元素。

--- ?3）除第一個(gè)元素外，集合中的每個(gè)元素均只有一個(gè)直接前驅(qū)。

--- ?4）除最后一個(gè)元素外，集合中的每個(gè)元素均只有一個(gè)直接后繼。

其中3）4）兩個(gè)特點(diǎn)體現(xiàn)了線性表中元素之間的邏輯關(guān)系。

理解線性表的要點(diǎn):

--- 表中元素具有邏輯上的順序性，在序列中各元素排列有其先后次序。

--- 表中元素個(gè)數(shù)有限。

--- 表中元素都是數(shù)據(jù)元素。即每一個(gè)表元素都是不可再分的原子數(shù)據(jù)。

--- 表中元素的數(shù)據(jù)類型都相同。即每一個(gè)表元素占有相同數(shù)量的存儲(chǔ)空間。

--- 表中元素具有抽象性。僅討論表元素之間的邏輯關(guān)系，不考慮元素究竟表示什么內(nèi)容。

2、線性表的操作

---- 線性表的主要操作有：

--- ?1）表的初始化運(yùn)算：將線性表置為空表。

--- ?2）求表長度運(yùn)算：統(tǒng)計(jì)線性表中表元素個(gè)數(shù)。

--- ?3）查找運(yùn)算：查找線性表中第i個(gè)表元素或查找表中具有給定關(guān)鍵字值的表元素。

--- ?4）插入運(yùn)算：將新表元素插入到線性表第i個(gè)位置上，或插入到具有給定關(guān)鍵字值的表元素的前面或后面。

--- ?5）刪除運(yùn)算：刪除線性表第i個(gè)表元素或具有給定關(guān)鍵字值的表元素。

--- ?6）讀?。ㄔL問）運(yùn)算：讀取線性表第i個(gè)表元素的值。

--- ?7）復(fù)制運(yùn)算：復(fù)制線性表所有表元素到另一個(gè)線性表中。

3、線性表的實(shí)現(xiàn)

3.1、線性表的順序存儲(chǔ)

------ 線性表的順序存儲(chǔ)又稱為順序表。它用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的數(shù)據(jù)元素，從而使得邏輯關(guān)系相鄰的兩個(gè)

元素在物理位置上也相鄰。因此順序表的特點(diǎn)是表中各元素的邏輯順序與其物理順序相同。

------ 順序表的靜態(tài)存儲(chǔ)分配

#define?MaxSize?100?????????//顯式的定義表的最大容量
typedef?int?ElemType;???????//定義表元素的數(shù)據(jù)類型
typedef?struct?{????????????//順序表的定義
	ElemType?data[MaxSize];?//靜態(tài)分配存儲(chǔ)表元素的數(shù)組
	int?n;??????????????????//實(shí)際表元素個(gè)數(shù)，0<=n<=MaxSize
}Sqlist;

在這種存儲(chǔ)方式下，表元素ai存儲(chǔ)在data[i-1]位置，存儲(chǔ)結(jié)構(gòu)如下圖：

假設(shè)順序表A的起始存儲(chǔ)位置為Loc(1),第i個(gè)表項(xiàng)的存儲(chǔ)位置為Loc(i),則有：Loc(i)=Loc(1)+(i-1) x sizeof(ElemType)

其中，Loc(1)是第一個(gè)表項(xiàng)的存儲(chǔ)位置，即數(shù)組中第0個(gè)元素位置。sizeof(ElemType)是表中每個(gè)元素所占空間的大小。根據(jù)這個(gè)計(jì)算

關(guān)系，可隨機(jī)存取表中的任一個(gè)元素。一維數(shù)組可以是靜態(tài)分配的，也可以是動(dòng)態(tài)分配的。

----- ?在靜態(tài)分配存儲(chǔ)的情形下，由于數(shù)組的大小和空間事先已經(jīng)固定分配，一旦數(shù)據(jù)空間占滿，再加入新的數(shù)據(jù)就將產(chǎn)生溢出，此時(shí)

存儲(chǔ)空間不能擴(kuò)充，就會(huì)導(dǎo)致程序停止工作。

----- ?在動(dòng)態(tài)分配存儲(chǔ)的情形下，存儲(chǔ)數(shù)組的空間是在程序執(zhí)行過程中通過動(dòng)態(tài)存儲(chǔ)分配的語句分配的，一旦數(shù)據(jù)空間占滿，可以另外

再分配一塊更大的存儲(chǔ)空間，用以代換原來的存儲(chǔ)空間，從而達(dá)到擴(kuò)充存儲(chǔ)數(shù)組空間的目的，同時(shí)需將表示數(shù)組大小的常量maxSize

放在順序表的結(jié)構(gòu)內(nèi)定義，可以動(dòng)態(tài)地記錄擴(kuò)充后數(shù)組空間的大小，提高結(jié)構(gòu)的靈活性。

------ 順序表的動(dòng)態(tài)存儲(chǔ)分配

#define?InitSize?100		//表長度的初始定義
typedef?int?ElemType;		//定義表元素的數(shù)據(jù)類型
typedef?struct?{		//順序表的定義
	ElemType?*data;		//指示動(dòng)態(tài)分配數(shù)組的指針
	int?maxSize,n;		//數(shù)據(jù)的最大容量和當(dāng)前表元素的個(gè)數(shù)
}Seqlist;
//初始的動(dòng)態(tài)分配語句為
data?=?(ElemType?*)malloc(sizeof(ElemType)*InitSize);
//C++?data=new?ElemType[InitSize];
maxSize?=?InitSize;n=0;

3.2、線性表的鏈?zhǔn)酱鎯?chǔ)

------ ?線性表的鏈?zhǔn)酱鎯?chǔ)又稱為線性鏈表。在這種結(jié)構(gòu)中數(shù)據(jù)元素存儲(chǔ)在結(jié)點(diǎn)中，結(jié)點(diǎn)之間在空間上可以連續(xù)，也可以不連續(xù)，通過

結(jié)點(diǎn)內(nèi)附的鏈接指針來表示元素之間的邏輯關(guān)系。因此在線性鏈表中邏輯上相鄰的表元素在物理上不一定相鄰。

以前在順序結(jié)構(gòu)中，每個(gè)數(shù)據(jù)元素只需要存數(shù)據(jù)元素信息就可以了，現(xiàn)在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存數(shù)據(jù)元素信息外，還要存儲(chǔ)它的后繼

元素的存儲(chǔ)地址。因此，為了表示每個(gè)數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素a(i+1)之間的邏輯關(guān)系，對數(shù)據(jù)元素ai來說，除了存儲(chǔ)其本身

的信息之外，還需存儲(chǔ)一個(gè)指示其直接后繼的信息（即直接后繼的存儲(chǔ)地址/位置）。

------ ?存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲(chǔ)直接后繼位置的域稱為指針域。指針域中存儲(chǔ)的信息稱做指針或鏈。這兩部分信息組成

數(shù)據(jù)元素ai的存儲(chǔ)映像，稱為結(jié)點(diǎn)（Node）。n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈表，即為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

最簡單的線性鏈表是單鏈表（鏈表的每個(gè)結(jié)點(diǎn)中只包含一個(gè)指針域），用C語言描述如下：

typedef?int?ElemType;		//定義表元素的數(shù)據(jù)類型
typedef?struct?node?{		
	ElemType?data;
	struct?node?*next;
}Node,*LinkList;

此時(shí)，使用一個(gè)指向鏈表結(jié)點(diǎn)的指針head標(biāo)識(shí)鏈表的表頭：

Node?*head;LinkList?head;

為了表示鏈表收尾，鏈表最后一個(gè)結(jié)點(diǎn)的鏈接指針應(yīng)置為空。

4、其他線性鏈表的形式

---- 根據(jù)結(jié)點(diǎn)中指針信息的實(shí)現(xiàn)方式，還有其他幾種鏈表結(jié)構(gòu)：

--- ?1）雙向鏈表：每個(gè)結(jié)點(diǎn)包含兩個(gè)指針，指明直接前驅(qū)和直接后繼元素，可在兩個(gè)方向上遍歷其后及其前的元素。

--- ?2）循環(huán)鏈表：表尾結(jié)點(diǎn)的后繼指針指向表中的第一個(gè)結(jié)點(diǎn)，可在任何位置上遍歷整個(gè)鏈表。

--- ?3）靜態(tài)鏈表：借助數(shù)組來描述線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（兩個(gè)數(shù)據(jù)域，一個(gè)存放數(shù)據(jù)元素，一個(gè)存儲(chǔ)該元素的后繼在數(shù)組中的下標(biāo)）

在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，只需要一個(gè)指針（頭指針）指向第一個(gè)結(jié)點(diǎn)，就可以順序訪問到表中的任意一個(gè)元素。為了簡化對鏈表狀態(tài)的判定

和處理，特別引入一個(gè)不存儲(chǔ)數(shù)據(jù)元素的結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，將其作為鏈表的第一個(gè)結(jié)點(diǎn)并令頭指針指向該結(jié)點(diǎn)。

頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表長度等類的附加信息，頭結(jié)點(diǎn)的指針域存儲(chǔ)指向第一個(gè)結(jié)點(diǎn)的指針（即第一個(gè)

元素結(jié)點(diǎn)的存儲(chǔ)位置）。此時(shí)，單鏈表的頭指針指向頭結(jié)點(diǎn)。如下圖所示：