1、線性表的定義

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

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

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

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

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

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

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

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

理解線性表的要點:

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

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

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

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

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

2、線性表的操作

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

--- ?1）表的初始化運算：將線性表置為空表。

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

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

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

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

--- ?6）讀?。ㄔL問）運算：讀取線性表第i個表元素的值。

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

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

3.1、線性表的順序存儲

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

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

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

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

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

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

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

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

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

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

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

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

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

------ 順序表的動態(tài)存儲分配

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

3.2、線性表的鏈?zhǔn)酱鎯?/p>

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

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

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

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

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

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

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

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

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

此時，使用一個指向鏈表結(jié)點的指針head標(biāo)識鏈表的表頭：

Node?*head;LinkList?head;

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

4、其他線性鏈表的形式

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

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

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

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

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

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

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

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