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)表的初始化運(yùn)算:將線性表置為空表。
--- ?2)求表長度運(yùn)算:統(tǒng)計線性表中表元素個數(shù)。
--- ?3)查找運(yùn)算:查找線性表中第i個表元素或查找表中具有給定關(guān)鍵字值的表元素。
--- ?4)插入運(yùn)算:將新表元素插入到線性表第i個位置上,或插入到具有給定關(guān)鍵字值的表元素的前面或后面。
--- ?5)刪除運(yùn)算:刪除線性表第i個表元素或具有給定關(guān)鍵字值的表元素。
--- ?6)讀?。ㄔL問)運(yùn)算:讀取線性表第i個表元素的值。
--- ?7)復(fù)制運(yùn)算:復(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é)點。如下圖所示: