1、線性表的定義

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

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

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

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

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

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

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

其中3）4）兩個特點體現了線性表中元素之間的邏輯關系。

理解線性表的要點:

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

--- 表中元素個數有限。

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

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

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

2、線性表的操作

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

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

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

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

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

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

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

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

3、線性表的實現

3.1、線性表的順序存儲

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

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

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

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

在這種存儲方式下，表元素ai存儲在data[i-1]位置，存儲結構如下圖：

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

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

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

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

存儲空間不能擴充，就會導致程序停止工作。

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

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

放在順序表的結構內定義，可以動態(tài)地記錄擴充后數組空間的大小，提高結構的靈活性。

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

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

3.2、線性表的鏈式存儲

------ ?線性表的鏈式存儲又稱為線性鏈表。在這種結構中數據元素存儲在結點中，結點之間在空間上可以連續(xù)，也可以不連續(xù)，通過

結點內附的鏈接指針來表示元素之間的邏輯關系。因此在線性鏈表中邏輯上相鄰的表元素在物理上不一定相鄰。

以前在順序結構中，每個數據元素只需要存數據元素信息就可以了，現在鏈式結構中，除了要存數據元素信息外，還要存儲它的后繼

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

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

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

數據元素ai的存儲映像，稱為結點（Node）。n個結點鏈接成一個鏈表，即為線性表的鏈式存儲結構。

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

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

此時，使用一個指向鏈表結點的指針head標識鏈表的表頭：

Node?*head;LinkList?head;

為了表示鏈表收尾，鏈表最后一個結點的鏈接指針應置為空。

4、其他線性鏈表的形式

---- 根據結點中指針信息的實現方式，還有其他幾種鏈表結構：

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

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

--- ?3）靜態(tài)鏈表：借助數組來描述線性表的鏈式存儲結構。（兩個數據域，一個存放數據元素，一個存儲該元素的后繼在數組中的下標）

在鏈式存儲結構中，只需要一個指針（頭指針）指向第一個結點，就可以順序訪問到表中的任意一個元素。為了簡化對鏈表狀態(tài)的判定

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

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

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