基本數(shù)據(jù)結構及其運算

第二章基本數(shù)據(jù)構造及其運算2.1數(shù)據(jù)構造的基本概念2.2線性表及次序存儲構造2.3線性表鏈表及其運算2.4數(shù)組2.5樹與二叉樹2.6圖本章重要介紹:數(shù)據(jù)構造、數(shù)據(jù)邏輯構造、數(shù)據(jù)存儲構造的基本概念；幾個慣用的數(shù)據(jù)構造(線性表、棧、隊列、數(shù)組、樹與二叉樹、圖），闡明這些數(shù)據(jù)構造內在的邏輯關系，討論它們在計算機中存儲的慣用方式：次序存儲和鏈式存儲，以及在這些數(shù)據(jù)構造上進行多個運算的算法。重點：理解數(shù)據(jù)構造、數(shù)據(jù)邏輯構造和存儲構造的概念，掌握慣用的數(shù)據(jù)構造中各數(shù)據(jù)內在的邏輯關系，在計算機中的存儲方式，以及在其上進行多個運算的算法。難點：對的分辨數(shù)據(jù)邏輯構造和存儲構造，掌握慣用數(shù)據(jù)構造在計算機中的存儲方式，及在其上進行多個運算的算法。1、數(shù)據(jù)元素之間的固有邏輯關系，稱為數(shù)據(jù)的邏輯構造數(shù)據(jù)構造重要研究和討論三方面問題：2、數(shù)據(jù)元素及其關系在計算機中的存儲方式，稱為數(shù)據(jù)的物理構造或存儲構造3、施加在數(shù)據(jù)構造上的操作，稱為數(shù)據(jù)構造的運算。數(shù)據(jù)解決的本質就是對數(shù)據(jù)構造施加多個運算，常見的運算有：查找、排序、插入、刪除等。2.1數(shù)據(jù)構造的基本概念例1、無序表的次序查找與有序表的對分查找。2.1.1兩個例子2、盡量節(jié)省數(shù)據(jù)解決過程中所占用的存儲空間1、提高數(shù)據(jù)解決的速度重要目的是提高數(shù)據(jù)解決的效率：1234567891012345678910data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]132442772830121321242830427725(a)無序表

data[0]data[1]data[2]data[3]data[4]data[5]data[6]data[7]data[8]211225(b)有序表

圖2.1數(shù)據(jù)元素寄存次序不同的兩個表表(a)只能采用次序查找，將x與表中每一種元素進行比較，查找效率較低。因表(b)中的元素是有序排列，可找到其中間元素data[4]，將x與它進行比較，有三種可能：x=data[4]x>data[4]

x<data[4]找到拋棄表的前半部分，在表的后半部分用相似的辦法繼續(xù)查找拋棄表的后半部分，在表的前半部分用相似的辦法繼續(xù)查找用這種辦法查找，每次比較都可拋棄子表二分之一的元素，查找效率較高從該例可看出，數(shù)據(jù)元素在表中的排列次序對查找效率有很大的影響例2、學生狀況記錄表信息查詢學號姓名性別年齡成績970156張小明男2086970157李小青女1983970158趙凱男1970970159李啟明男2191970160劉華女1878970161曾小波女1990970162張軍男1880970163王偉男2065970164胡濤男1995……………9519男胡濤9701649019女曾小波9701619317女梅玲9701689121男李啟明970159成績年齡性別姓名學號成績在90分及以上的學生情況登記表成績在80~89分之間的學生情況登記表8018男張軍970162……………8319女李小青9701578620男張小明970156成績年齡性別姓名學號從該例可看出，在對數(shù)據(jù)進行解決時，可根據(jù)所做的運算不同，將數(shù)據(jù)組織成不同的形式，也可提高數(shù)據(jù)解決的效率成績在70~79分之間的學生情況登記表7818女劉華9701607520男劉健9701697019男趙凱970158成績年齡性別姓名學號成績在60~69分之間的學生情況登記表6520男王偉9701636118男呂永華970167成績年齡性別姓名學號2.1.2什么是數(shù)據(jù)構造數(shù)據(jù)構造：互相有關聯(lián)的數(shù)據(jù)元素的集合。例：向量和矩陣就是數(shù)據(jù)構造，在這兩個數(shù)據(jù)構造中，數(shù)據(jù)元素之間有位置上的關系數(shù)據(jù)：反映客觀事物信息集合，在現(xiàn)實生活中稱信息在計算機中稱數(shù)據(jù)；即數(shù)據(jù)是符號化的信息。它由數(shù)據(jù)元素構成數(shù)據(jù)元素(元素)：數(shù)據(jù)集合中的一種元素，是數(shù)據(jù)的基本單位。數(shù)據(jù)元素含有廣泛的含義，現(xiàn)實世界中的一切個體能夠是數(shù)據(jù)元素例：描述四季的季節(jié)名{春、夏、秋、冬}能夠作為季節(jié)(數(shù)據(jù))的數(shù)據(jù)元素描述學生特性的信息:(970158、趙凱、男、1970、70)，(970159、李啟明、男、21、91)，(970162、張軍、男、18、80)…能夠作為學生狀況記錄表(數(shù)據(jù))的數(shù)據(jù)元素甚至每一種客觀存在的事件：如一次借書、一次比賽等也可作為數(shù)據(jù)元素 總之，在數(shù)據(jù)解決領域，每一種需要解決的對象都可抽象成數(shù)據(jù)元素要表達一種數(shù)據(jù)構造，需表達出：1、數(shù)據(jù)元素的集合，記為D2、在D中各數(shù)據(jù)元素之間的關系，記為R則：數(shù)據(jù)構造B=(D,R)在數(shù)據(jù)解決領域，數(shù)據(jù)元素之間的任何關系都能夠用前后件關系描述例1：春、夏、秋、冬四季，春是夏的前件，夏是春的后件為反映春、夏、秋、冬這四個元素之間的前后件關系，普通采用二元組表達，也稱二元關系(春,夏)、(夏,秋)、(秋,冬)故：一年四季的數(shù)據(jù)構造可表達為D={春,夏,秋,冬}R={(春,夏),(夏,秋),(秋,冬)}B=(D,R)例2、n維向量X=(x1,x2,……xn)是一種數(shù)據(jù)構造，它可表達為：D={x1,x2,……,xn}R={(x1,x2),(x2,x3),…,(xn-1,xn)}B=(D,R)對于復雜的數(shù)據(jù)構造，它的數(shù)據(jù)元素能夠是另一種數(shù)據(jù)構造。它的每一行Ai=(ai1,ai2,…,ain)i=1,2,…,m能夠當作是它的一種數(shù)據(jù)元素,D={A1,A2,…,Am}D上的關系為:R={(A1,A2),(A2,A3),…(Am-1,Am)}例：m×n的矩陣是一種數(shù)據(jù)構造顯然,數(shù)據(jù)構造A中的每一種元素Ai (i=1,2,…,m)又是另一種數(shù)據(jù)構造,其數(shù)據(jù)元素,Di={ai1,ai2,…,aim}Di上的關系為:Ri={(ai1,ai2),(ai2,ai3),…(aim-1,aim)}可看出：②、數(shù)據(jù)的邏輯構造在計算機存儲器中的存儲方式稱為數(shù)據(jù)的物理構造（存儲構造）。③、要將一種數(shù)據(jù)存儲在計算機中應存儲：數(shù)據(jù)元素的集合D數(shù)據(jù)元素之間的關系R①、一種數(shù)據(jù)構造中的關系R，事實上是D上各數(shù)據(jù)元素之間的聯(lián)系，并不表達數(shù)據(jù)在計算機中的存儲位置，稱為數(shù)據(jù)的邏輯構造。綜上，數(shù)據(jù)的邏輯構造是數(shù)據(jù)本身所固有的，而存儲構造則可根據(jù)運算需要進行設計或構造（即一種邏輯構造可表達成多個存儲構造）。在進行數(shù)據(jù)解決時，應根據(jù)需要解決的不同，采用不同的存儲構造，以提高解決效率。D中的數(shù)據(jù)元素用中間標有元素值的方框表達，稱為數(shù)據(jù)結點（結點）；R中的關系用一條有向線段從前件結點指向后件結點。

§2.1.3數(shù)據(jù)構造的圖形表達例：設數(shù)據(jù)元素的集合為D={di|1≤i≤7的整數(shù)}，畫出對應于下列關系所構成的數(shù)據(jù)構造的圖形①、R1={(d1,d3),(d1,d7),(d4,d5),(d3,d6),(d2,d4)}②、R2={(di,dj)|i+j=5}③、R3={(d2,d3)(d3,d1),(d1,d4),(d4,d6),d6,d5),(d5,d7)}d2

d3

d1

d4

d6

d5

d7

(D,R3)(D,R1)d1

d3

d7

d6

d2

d4

d5

(D,R2)d1

d4d2

d3

d5

d7

d6

沒有前件的結點稱為根結點，沒有后件的結點稱為終端結點（葉子結點），其它的結點稱為內部結點線性構造：一種非空數(shù)據(jù)構造滿足下列三個條件，則稱該數(shù)據(jù)構造為線性構造：①、有且僅有一種根結點②、每個結點最多只有一種前件，也最多有一種后件③、插入和刪除結點后仍滿足①、②線性構造：從根結點到終止點之間只有一條由有向線段連起的途徑§2.1.4線性數(shù)據(jù)構造與非線性數(shù)據(jù)構造數(shù)據(jù)的邏輯構造可分為兩大類線性構造非線性構造不是線性構造非線性構造：不滿足線性構造特點的數(shù)據(jù)構造，即該構造中結點可能有多個前件和多個后件。典型的非線性構造為圖構造，樹是一種特殊的非線性構造。樹構造圖構造§2.2線性表及其次序構造§2.2.1線性表及其運算

1、什么是線性表線性表是由n(n0)個含有相似類型的數(shù)據(jù)元素a1,a2,,ai,…,an構成的一種有限序列。表中的每一種數(shù)據(jù)元素，除了第一種外，有且只有一種前件；除了最后一種外，有且只有一種后件。其中n為表長(n=0時為空表），ai為線性表中的第i個元素，ai能夠是一種數(shù)，符號或其它更復雜的信息。其數(shù)據(jù)構造表達為：D={a1,a2,,an} R={(a1,a2),(a2,a3),,(an-1,an)}a1

a2

a3

an

……圖形表達為：線性表是一種線性構造。邏輯構造例1：一種n維向量：X=(x1,x2,……xn)為一種線性表英語小寫字母表(a,b,c,…,z)也是一種線性表例2：某班學生狀況記錄表，是比較復雜的線性表學號姓名性別年齡成績970156張小明男2086970157李小青女1983970158趙凱男1970970159李啟明男2191970160劉華女1878970161曾小波女1990970162張軍男1880970163王偉男2065970164胡濤男1995……………2、線性表的次序存儲構造數(shù)據(jù)的邏輯構造在計算機存儲器中的存儲方式稱為數(shù)據(jù)的存儲構造，數(shù)據(jù)的存儲構造是指：根據(jù)存儲關系R的方式不同，存儲構造分為兩種：①、次序存儲構造②、鏈式存儲構造①、如何為數(shù)據(jù)元素分派存儲單元②、如何實現(xiàn)數(shù)據(jù)元素之間的關系 次序存儲構造是將（D,R）中邏輯上相鄰的數(shù)據(jù)元素存儲在物理上相鄰的存儲單元中，而數(shù)據(jù)元素之間關系由存儲單元的鄰接關系唯一擬定例：D={a,b,c,d,e,f},R=((b,c),(c,d),(d,a),(a,f),(f,e)}邏輯構造存儲構造efadcb100510061007100810091010(D,R)可看出：①、次序存儲構造重要用于存儲線性構造，而存儲非線性構造較困難②、次序存儲構造必須要有一片持續(xù)空間存儲數(shù)據(jù)元素，構造中各元素按它們之間的關系次序寄存將線性表的次序存儲構造稱為次序表。注意：線性表與次序表的區(qū)別數(shù)據(jù)邏輯構造數(shù)據(jù)存儲構造編程時，可用一維數(shù)組或用一組地址持續(xù)的存儲單元來依次存儲線性表中的數(shù)據(jù)元素。①、用數(shù)組v(1:m),構成可存儲m個數(shù)據(jù)元素的線性表v(1)=b,v(2)=c,v(3)=d,v(4)=a,v(5)=f,v(6)=e,表長n=6②、用C動態(tài)分派內存地址函數(shù)malloc構成可存儲m個數(shù)據(jù)元素的線性表#include“stdlib.h”voidinitsl(ET*v,intm,int*n){ v=(ET*)malloc(m*sizeof(ET)); v[0]=b；v[1]=c；v[2]=d； v[3]=a；v[4]=f；v[5]=e； *n=6；}其中：ET表達線性表中元素的數(shù)據(jù)類型，n表長在次序表中，設線性表中每一種數(shù)據(jù)元素占用k個存儲單元，線性表中任一元素ai的存儲地址可用下式來表達：存儲地址ADR(a1)ADR(a1)+k

ADR(a1)+(i-1)*k

ADR(a1)+(n-1)*k

序號內存a1a2

ai

an

12

i

n

mADR(ai)=ADR(a1)+(i-1)*k在次序表中讀取任何一種元素所用時間相似，讀取元素方便，也稱為隨機存儲構造線性表可進行重要運算：①、在線性表指定位置加入一種新元素（線性表插入）②、在線性表中刪除指定元素（線性表刪除）③、在線性表中查找某個特定的元素（線性表查找）④、對線性表中元素進行排序（線性表排序）⑤、將一種線性表分解成多個線性表（線性表分解）⑥、將多個線性表合并成一種線性表（線性表合并）⑦、復制一種線性表（線性表復制）⑧、逆轉一種線性表（線性表逆轉）注意：運算定義在邏輯構造上，在不同存儲構造下有不同的實現(xiàn)辦法（算法）3、線性表在次序存儲下的插入運算設長度為n的線性表為（a1,a2,

,ai-1,ai,,an),現(xiàn)在第i-1與第i個元素間插入一個新元素b，插入后得到長度為n+1的新表為

(a1,a2,…,ai-1,b,ai,…,an)順序表插入示意圖：12

i-1ii+1nn+112i-1ina1a2…ai-1ai…anba1a2…ai-1ai…an-1anbV[1]V[2]V[i-1]V[i]V[n]V[1]V[2]V[i-1]V[i]V[i+1]V[n]V[n+1]該算法涉及到的輸入、輸出數(shù)據(jù)：線性表插入異常狀況分析，重要分析：①、現(xiàn)在所擁有的條件能否讓算法順利執(zhí)行完畢②、根據(jù)算法特性第四條，規(guī)定對的的輸入信息對本算法，其異常狀況為：①、表滿時，不能插入②、插入點不在表中n=mi>ni<1設插在表尾，即i=n+1設插在表頭，即i=1要判斷異常狀況，需用到數(shù)據(jù)m，必須輸入m故：該算法應輸入、輸出的數(shù)據(jù)為：線性表插入v,b,i,n,mv,nPROCEDUREINSL(v,m,n,b,i)IF(n=m)THEN{overflow;RETURN}IF(i>n)THENi=n+1IF(i<1)THENi=1FORj=nTOiBY–1DOV(j+1)=V(j)V(i)=b 或 V(j+1)=bn=n+1RETURN其算法為：設長度為n的線性表為(a1,a2,,ai-1,ai,ai+1,,an),刪除第i個元素,刪除后的線性表為(a1,a2,

,ai-1,ai+1,,an)。3、線性表在次序存儲下的刪除運算12i-1ii+1na1a2…ai-1aiai+1…anV[1]V[2]V[i-1]V[i]V[i+1]V[n]12

i-1ii+1n-1na1a2…ai-1V[1]V[2]V[i-1]V[i]V[i+1]V[n-1]V[n]ai+1ai+1

…an

該算法涉及到的輸入、輸出數(shù)據(jù)：線性表刪除異常狀況為：①、表空時，不能刪除②、刪除點超出表范疇n=0i>n或i<1不能進行刪除其算法為：PROCEDUREDESL(V,n,i)IF(n=0)THEN{UNDERFLOW;RETURN}IF(i<1)or(i>n)THEN{printf(“Notthiselementinthelist”;RETURN}FORj=iTOn-1DOV(j)=V(j+1)n=n-1RETURN例：C++語言編寫次序表基本操作：表初始化、輸出、插入與刪除（C++幻燈20）次序表操作的特點：1次序表中數(shù)據(jù)元素的個數(shù)需要預先擬定；2由于次序表的隨機存取特性，訪問每個元素很方便；3插入和刪除操作需移動大量的元素，平均為個4、需一片持續(xù)空間，線性表容量不易擴充§2.2.2棧及其應用例：下列給出了含有嵌套調用的五個程序1、什么是棧MAIN:…CALLSUB1A:…SUB1…CALLSUB2B:…SUB2…CALLSUB3C:…SUB3…CALLSUB4D:…SUB3……RETURN返回地址：A、B、C、DA、B、C、D構成一種線性表，計算機系統(tǒng)在解決時可用一種線性表來動態(tài)記憶調用過程中的途徑，即建立一種空線性表，調用函數(shù)時將返回地址插入線性表，返回主程序時將返回地址從表中刪除；但如何解決插入與刪除的元素，才干讓調用過程不出差錯。要讓調用過程不出差錯，這四個元素的插入次序必須為A、B、C、D，而刪除次序剛好與這相反，為D、C、B、A，如規(guī)定只能在一端進行插入與刪除操作，可滿足上述規(guī)定。這種只能在一端進行插入與刪除操作的線性表稱為棧。允許插入和刪除的一端稱為棧頂，而不允許插入與刪除的一端稱為棧底。入棧次序：a1,a2,a3,…,an出棧次序：an,an-1,…a2,a1棧的操作原則：先進后出棧底

棧頂

插入(入棧)刪除(出棧)topbottom隨著入棧與出棧操作的進行，棧頂?shù)奈恢酶幼兓?，為反映這種變化，設立一種棧頂指針top，指向現(xiàn)在棧頂元素的存儲位置，設一種棧底指針bottom，指向棧底元素的存儲位置。2、棧的基本運算（1）入棧：在棧頂端插入一種新元素（2）出棧(退棧)：從棧頂刪除一種元素（3）取棧頂元素：在棧中讀棧頂元素3、棧的次序存儲構造及其運算棧是一種特殊的線性表，與普通次序存儲構造的線性表同樣，也可運用一片持續(xù)的存儲單元依次寄存自棧底到棧頂?shù)臄?shù)據(jù)元素，可用一維數(shù)組S(1:m)模擬棧，m為棧的容量普通?。篵ottom=1入棧：top=top+1S(top)=x出棧：top=top-1y=S(top)棧空：top=0棧滿：top=m初始狀態(tài)：top=0入棧出棧topbottoma0a1an。。。算法2.3在容量為m的棧s中插入一種元素xPROCEDUREPUSH(S,m,top,x)IF(top=m)THEN{stack-OVERFLOW;RETURN}top=top+1S(top)=xRETURN入棧運算異常狀況為：棧滿時，不能插入top=m該算法涉及到的輸入、輸出數(shù)據(jù)：算法2.4在容量為m的棧s中刪除一種元素PROCEDUREPOP(S,top,y)IF(top=0)THEN{stack-UNDERFLOW;RETURN}y=S(top)top=top-1RETURN出(退)棧運算異常狀況為：棧空時，不能刪除top=0該算法涉及到的輸入、輸出數(shù)據(jù)：算法2.5讀棧頂元素PROCEDURETOP(S,top,y)IF(top=0)THEN{stack-UNDERFLOW;RETURN}y=S(top)RETURN讀棧頂元素異常狀況為：?？諘r，無元素可讀top=0該算法涉及到的輸入、輸出數(shù)據(jù)：棧是最廣泛使用的數(shù)據(jù)構造之一，子程序的調用，遞歸過程的實現(xiàn)，體現(xiàn)式的計算都是棧應用的典型例子。自學P38體現(xiàn)式的計算 2.2.3隊列及其應用1、什么是隊列隊列也是一種特殊的線性表，它只允許在一端進行插入，而在另一端進行刪除，允許插入的一端稱為隊尾，用一種尾指針rear批示，允許刪除的一端稱為隊（排）頭，用一種排頭指針(front)批示。FEDCBA入隊(插入)出隊(刪除)front(頭)rear(尾)入隊次序：A,B,C,D,E,F出隊次序：A,B,C,D,E,F隊列的操作原則：先進后出同棧類似，在次序存儲構造下，可用一維數(shù)組Q(1:m)模擬隊列，m為隊列的容量入隊：rear=rear+1Q(rear)=x出隊：y=Q(front)隊空：front=rear隊滿：rear=m初始狀態(tài)：front=rear=0front=front+1FEDCBA入隊出隊front(頭)rear(尾)由于隊列只能在一端插入，在另一端刪除，隨著入隊與出隊運算不停進行，隊列中元素不停向隊尾方向移動，而在排頭產生一片不能用的空間，最后可能造成尾指針指向隊列最后一種位置，而排頭卻有一片無法運用的空閑區(qū)，這種現(xiàn)象稱為“假溢出”frontrear如何避免“假溢出”現(xiàn)象的發(fā)生：最簡樸的方法，在進行入隊與出隊運算時，調節(jié)隊列中元素在存儲空間中的位置，即出隊時將隊列中全部元素依次向排頭方向移動一種位置。但這種方法需移動大量的元素，在實際中普通不用，而是采用另一種方法。入隊出隊KJHm12、循環(huán)隊列將隊列存儲空間的最后一種位置饒到第一種位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用frontrear循環(huán)隊列示意圖HJKm1m1frontrearKJH隊列存儲空間入隊：rear=rear+1Q(rear)=x出隊：y=Q(front)隊空：front=rear隊滿：rear=front初始狀態(tài)：front=rear=mfront=front+1循環(huán)隊列的運算Ifrear=m+1Then rear=1Iffront=m+1Then front=1由此可見，循環(huán)隊列構造即使避免了“假溢出”現(xiàn)象，但卻帶來一種新問題，無法區(qū)別滿足條件front=rear的隊列是處在隊空還是隊滿的狀態(tài)，為解決這個問題，可采用兩種辦法：（1）、另設一種標志以區(qū)別隊空和隊滿s=01隊空隊非空隊滿條件：s=1andrear=front隊列初始狀態(tài)：s=0且front=rear=m隊空條件：s=0入隊操作：If(rear=front)and(s=1)Then{“隊滿”；Return}rear=rear+1Ifrear=m+1Then rear=1Q(rear)=xs=1出隊操作：If(s=0)Then{“隊空”；Return}front=front+1Iffront=m+1Then front=1y=Q(front)Ifrear=frontThens=0完整的算法見P43~44（2）、用隊尾指針追上排頭指針這一特性作為隊滿的條件frontrearKJHfrontKJHrearABC入隊時，將rear+1=front作為隊滿的條件即：rear=rear+1Ifrear=m+1Thenrear=1Ifrear=frontThen“隊滿”隊空：rear=front算法2.6a在容量為m的循環(huán)隊列Q中插入一種元素xPROCEDUREADDCQ(Q,m,rear,front,x)t=rear+1IF(t=m+1)THENt=1IF(t=front)THEN{“OVERFLOW”;RETURN}rear=tQ(rear)=xRETURN入隊運算異常狀況為：隊滿時，不能插入(rear+1)modm=front該算法涉及到的輸入、輸出數(shù)據(jù)：算法2.7a在容量為m的循環(huán)隊列Q中刪除一種元素PROCEDUREDELCQ(Q

,m,rear,front,y)IF(rear=front)THEN{“UNDERFLOW”;RETURN}front=front+1IF(front=m+1)THENfront=1y=Q(front)RETURN出(退)隊運算異常狀況為：隊空時，不能刪除rear=front該算法涉及到的輸入、輸出數(shù)據(jù)：隊列在計算機中也有廣泛的應用，凡可抽象為線性表并符合先到先服務的解決過程，均可用隊列模擬。例VB中的事件隊列；計算機中CPU與外設傳遞數(shù)據(jù)時，在內存中設立的緩沖區(qū)隊列。P48介紹了隊列在日常生活中應用，自學線性表次序存儲構造含有構造簡樸，讀取元素方便等優(yōu)點，適合小線性表或長度固定的線性表，但它存在下列幾方面的缺點：需一片持續(xù)空間，不能運用存儲器中的碎片，且線性表容量不易擴充不能對存儲空間進行動態(tài)分派；

插入和刪除操作需移動大量的元素，平均為個對于大的線性表或元素變化頻繁的線性表不適宜采用次序構造，而是采用鏈式存儲構造1、線性鏈表線性鏈表是線性表的鏈式存儲構造，在鏈式存儲構造中，數(shù)據(jù)元素可存儲在不持續(xù)的空間中，各數(shù)據(jù)元素之間的關系不是由存儲單元的鄰接關系擬定，而是由指針域擬定?！?.3線性鏈表及其運算

§2.3.1線性鏈表的基本概念在鏈式存儲構造中，每一種數(shù)據(jù)元素的表達由兩部分信息構成：一是數(shù)據(jù)元素的值；二是各數(shù)據(jù)元素的前后件關系存儲數(shù)據(jù)元素值存儲與該結點邏輯上相鄰的結點地址即：線性鏈表中每一種元素的存儲單元都由數(shù)據(jù)域和指針域兩部分構成，稱為存儲結點（結點）只有一種指針域時，其存儲內容為該結點后件的地址，無后件結點，指針域為“0”、“NULL”或“”例：已知數(shù)據(jù)構造B=(D,R)，D={a,b,c,d,e,f}，R={(b,c),(c,d),(d,a),(a,f),(f,e)}，其鏈式存儲構造為：注意：頭指針Head是整個鏈表的唯一標記，通過它可找到鏈表中任意元素數(shù)據(jù)元素間的邏輯關系是通過指針來反映的鏈式構造既可存儲線性構造，也可存儲非線性構造（多個后件用多個指針域指向，前件也可用指針域指出線性鏈表的物理狀態(tài)用鏈式構造存儲線性表時，每個結點的存儲空間可任意分派，它們能夠不持續(xù)，它們之間的關系由指針域擬定在程序設計時，慣用兩個一維數(shù)組V(1:m)，Next(1:m)存儲線性表，用V表達數(shù)據(jù)，Next表達指針域則第i個結點為數(shù)據(jù)元素值數(shù)據(jù)元素地址上例用數(shù)組存儲：R={(b,c),(c,d),(d,a),(a,f),(f,e)}V(1)=a、V(2)=b、V(3)=c、V(4)=d、V(5)=e、V(6)=fNext(1)=6Next(2)=3Next(3)=4Next(4)=1Next(5)=0Next(6)=5Head=2通過Head可找到鏈表中任意元素，例： V(Head)=V(2)=bp=Next(Head)=Next(2)=3,V(p)=V(3)=cNext(i)V(i)普通而言，線性鏈表（a1,a2,a3,ai,an）可用以下邏輯狀態(tài)圖來表達：上例可用下圖表達線性鏈表的邏輯狀態(tài)：V(1)=a、V(2)=b、V(3)=c、V(4)=d、V(5)=e、V(6)=fR={(b,c),(c,d),(d,a),(a,f),(f,e)}bcadfe0Head234165線性鏈表中的各結點在計算機中的存儲位置分布是雜亂的，但只要抓住了鏈表的頭指針Head，事實上就抓住了表中全部結點。當Head=0時為空表算法2.9依次輸出頭指針為Head的線性表中各結點值輸出鏈表中各元素異常狀況：該算法涉及到的輸入、輸出數(shù)據(jù)：空表時無輸出PROCEDUREPRTLL(V,Next,Head)j=HeadWhile(j0)Do{outputV(j)j=Next(j)}RETURNP55~56介紹了如何在C++語言中用動態(tài)分派內存的辦法實現(xiàn)鏈表，并用一段程序介紹在C++語言中如何創(chuàng)立鏈表，如何輸出鏈表中各元素，自學前面討論的鏈表每個結點只有一種指針域，指向其后件地址，由該指針能方便找到其后件，但不能找到前件，這種鏈表稱為線性單鏈表(單鏈表)，在單鏈表中，只能順指針向鏈尾方向掃描，當要尋找某個結點的前件時，只能從頭指針開始重新尋找。為彌補單鏈表的局限性，在應用中可設立兩個指針域，一種指向前件，稱為左指針；一種指向后件，稱為右指針。這樣的線性表稱為雙向鏈表Llink(i)Data(I)Rlink(i)第i個結點：邏輯狀態(tài)圖：a10a2a30an……Head…2、帶鏈的棧棧和隊列是線性表，故棧和隊列都可采用鏈式存儲構造Top…an-2an-1ana1棧頂指針相稱于鏈表頭指針0Top0…在實際應用中，帶棧的鏈能夠用來收集計算機存儲空間中含有相似構造的空閑存儲空間，這種帶鏈的棧稱為可運用棧。由于可運用棧鏈接了計算機存儲空間中含有相似構造的空閑結點，因此，當計算機系統(tǒng)或顧客程序需要存儲結點時，可從中取出棧頂結點，當計算機系統(tǒng)或顧客程序釋放一種存儲結點時，則將該結點放回到可運用棧的棧頂。p從可運用棧中獲得一種結點pp將結點p送回可運用棧Top0…用鏈式存儲構造解決實際問題時，首先分派一定的存儲空間形成可運用棧，再構造與可運用棧中結點含有相似構造的鏈表(可能有多個)，這些鏈表中元素的插入結點取至可運用棧，刪除的結點送回可運用棧。因此全部含有相似構造的鏈表可共用同一種可運用棧算法2.10從棧頂為Top的可運用棧獲得一種p輸入：

輸出：異常狀況：棧為空，獲得結點失敗返回值P=0可運用棧無空間分派失敗0可運用棧有空間分派成功PROCEDUREnew(p)p=TopIfp=0ThenReturnTop=Next(Top)Return算法2.11將結點p送回棧頂為Top的可運用棧輸入：輸出：異常狀況：無PROCEDUREdispose(p)Next(p)=TopTop=pReturn可運用棧是一種空表，是為其它鏈表服務的。下列算法是帶鏈的棧的入棧與出棧運算算法2.12在棧頂為Top1的帶鏈棧中插入一種元素x輸入：輸出：異常狀況：可運用棧為空分派新結點失敗pTop10…ana3a2a1xnew(p);ifp=0then“無空間”PROCEDUREPushLL(Top1,x)new(p)Ifp=0Then{“無空間”；Return}V(p)=xNext(p)=Top1Top1=pReturn算法2.13在棧頂為Top1的帶鏈棧中刪除棧頂元素p輸入：輸出：異常狀況：棧空，不能刪除Top1=0Top10…ana1a2a3PROCEDUREPOPLL(Top1,y)IfTop1=0Then{“棧空”；Return}y=V(Top1)p=Top1Top1=Next(Top1)dispose(p)Return在C語言中用函數(shù)malloc()分派空間，用free()釋放空間在C++語言中用new分派空間，用delete釋放空間3、帶鏈的隊列排頭指針(front)相稱于鏈表頭指針，尾指針(rear)指向鏈表最后一種元素front0…a3a2a1anrear隊空(front=rear=0)，變化頭指針和尾指針的值算法2.14在帶鏈隊列中插入一種元素x輸入：輸出：異常狀況：可運用棧為空，分派新結點失敗p0…ana3a2a1xnew(p);ifp=0then“無空間”rearfront0front=prear=pPROCEDUREADDLL(rear,front,x) new(p) Ifp=0Then{“無空間”；Return} V(p)=x Next(p)=0 Iffront0Then {Next(rear)=p rear=p } Else rear=front=p Return算法2.15在帶鏈隊列中刪除一種元素輸入：輸出：隊中只有一種結點，刪除該結點后，必須變化尾指針(rear)的值frontp0…a2a1a3anrear異常狀況：隊空，不能刪除front=0rear=0PROCEDUREDELLL(front,rear,y) Iffront=0Then{“隊空”；Return} y=V(front) p=front front=Next(front) Iffront=0Thenrear=0 dispose(p) Return線性鏈表可進行的基本運算即為線性表的基本運算，重要介紹前兩種運算，在線性鏈表中，結點之間的關系是由指針的鏈接關系關系來表達，在對線性鏈表進行插入與刪除時，只需變化指針即可線性表插入、線性表刪除、線性表查找、線性表排序、線性表分解、線性表合并、線性表復制、線性表逆轉2.3.2線性鏈表的基本運算一、在線性鏈表中包含x元素的結點之前插入一種新元素bpb1、為插入的新元素分派一種新結點p，V(p)=b2、在線性表中尋找包含元素x的前一種結點q3、將結點p插入到結點q之后…xa2…a2x…………bp單向鏈表雙向鏈表單向鏈表Next(p)=Next(q)Next(q)=p雙向鏈表Llink(p)=qRlink(p)=Rlink(q)Llink(Rlink(q)=pRlink(q)=pqqa2x……………xa2…二、在線性鏈表中刪除包含元素x的結點p1、在線性表中尋找包含元素x的前一種結點q2、刪除結點q的后一種結點3、釋放被刪除的結點p單向鏈表雙向鏈表單向鏈表Next(q)=Next(Next(q))雙向鏈表Rlink(q)=Rlink(Rlink(q))Llink(Rlink(Rlink(q)))=qqq從上面分析可看出，線性表的插入與刪除不涉及數(shù)據(jù)元素的移動，但也存在兩個問題：１、插入時，從何處得到空閑的結點作為新元素結點；刪除時，被刪除結點應釋放到何處才干被后來使用，即如何管理空閑結點(用可運用棧)2、在非空鏈表中尋找包含指定元素的前一種結點算法2.16在頭指針為Head的非空鏈表中尋找包含元素x的前一種結點q輸入：輸出：2、x在表中第一種元素異常狀況：1、空表3、x不在表中放入插入與刪除算法中考慮qPROCEDURELookST(Head,x,q)q=HeadWhile(Next(q)≠0)and(V(next(q))≠x)Doq=Next(q)Return如鏈表中未包含元素x，q指向鏈表最后一種元素即返回值Next(q)=0 x不在鏈表中Next(q)≠0q為x前件地址Head…a2a1xan0三、線性表的插入與刪除算法算法2.1７在頭指針為Head的線性鏈表中包含元素x的結點前插入結點b，如鏈表中無元素x，則將b插入到鏈表的末尾。②、x在表中第一種元素，插在表頭異常狀況：①、空表，插入結點為表中第一種結點③、x不在表中，插在表尾輸入：輸出：Head=0V(Head)=xLookST(Head,x,q)Next(q)=0④、無空間，不能插入pb…xa2…qPROCEDUREInsLst(Head,x,b)new(p)Ifp=0Then{“無空間”；Return}V(p)=bIfHead=0Then{Head=p;Next(p)=0;Return}IfV(Head)=xThen{Next(p)=Head;Head=p;Return}LookST(Head,x,q)Next(p)=Next(q)Next(q)=pReturn…xa2…算法2.1８在頭指針為Head的線性鏈表中刪除包含元素x的結點②、刪除元素為表中第一種結點異常狀況：①、空表，不能刪除③、x不在表中，不能刪除Head=0V(Head)=xLookST(Head,x,q)Next(q)=0PROCEDUREDelSt(Head,x)IfHead=0Then{“空表”;Return}IfV(Head)=xThen{p=Next(Head);dispose(Head);Head=p;Return}LookST(Head,x,q)IfNext(q)=0Then{“無此結點”;Return}p=Next(q)Next(q)=Next(p)Dispose(p)Returnpq線性鏈表插入與刪除示意圖見書P68圖2.26P70圖2.27輸入：輸出：四、循環(huán)鏈表增加一種表頭結點，數(shù)據(jù)域任意或根據(jù)需要設立，指針域指向線性鏈表的第一種結點，Head指向表頭結點最后一種結點指針域不為空，而是指向表頭結點空循環(huán)鏈表注意：①循環(huán)鏈表能夠從任何一種結點出發(fā)去訪問其它結點②循環(huán)鏈表和單鏈表鑒定表的結束標志的辦法不同：循環(huán)單鏈表的結束標志：Next(P)=Head單鏈表的結束標志：Next(P)=0④循環(huán)鏈表的插入和刪除算法和單鏈表類似。自學③循環(huán)鏈表和單鏈表鑒定空表的辦法不同：循環(huán)單鏈表為空表標志：Head=Next(Head)單鏈表為空表標志：Head=01.次序表占用的存儲空間最少，而雙鏈表占用的存儲空間最多2.次序表是一種隨機存儲構造，訪問表中的某一種元素方便；單鏈表元素的訪問則必須從頭指針開始按次序依次去尋找待訪問的元素。3.一種次序表一旦擬定則其大小就不能夠隨意變化，因此操作中需要進行“判滿”的工作，而鏈表的大小卻可方便的變化，但鏈表占用的存儲空間較多。4.次序表的操作重要消耗在元素的移動上，效率較低，單鏈表的操作消耗在指針的移動上，雙鏈表的操作極為方便，但卻是建立在存儲空間的消耗上的?？偨Y:五、線性表的應用一元多項式相加任何一種一元多項式Pn(x)都可按升冪表達為：Pn(x)=p0+p1x+p2x2+…+pixi+…+pnxn可見Pn(x)由n+1個系數(shù)（p0，p1，…，pi，…，pn）唯一擬定，可用一種線性表P來表達系數(shù)的集合，其中Pi(x)項的指數(shù)隱含在系數(shù)pi中。該線性表可表達為：P=（p0，p1，…，pi，…，pn）表長為n+1。同理，再設一種一元多項式Qm(x)，此多項式也可由一種線性表Q=（q0，q1，…，qi，…，qm）(表長為m+1)來表達。若要計算：Rn(x)=Pn(x)+Qm(x)，這里不失普通性，假定m<n。Rn(x)也可用線性表R=(p0+q0，p1+q1，…，pm+qm，pm+1,…，pn）來表達，顯然能夠對P、Q、R采用次序構造存儲，采用次序表形式解決這種多項式的相加。但是，若已知多項式為S(x）=1+3x10000+5x30000，此時再用將指數(shù)項隱含在系數(shù)中的方式，用系數(shù)次序表來表達S（x），則其表長為30001，而表中只有3個非零元素，浪費了大量的存儲空間。因此，普通狀況下的一元n次多項式可寫成：Pn(x)=P1xe1+P2xe2+…+Pixei+…+Pmxem，其中Pi是指數(shù)為ei的非零系數(shù)項，且滿足0≤e1<e2<…<em，可用每個元素有兩個數(shù)據(jù)項的線性表R=((P1,e1),(P2,e2),…，(Pm,em))來表達。此線性表可用次序和鏈式構造存儲。+=p0p1p2…pmpn…q0q1q2…qmp0+q0p1+q1p2+q2…pm+qm…pntypedefstructpoly{intcoef;intexp;}elemtype;typedefstructpolynty{elemtypedata[Max];intnum;}polynty;用次序表的形式表達的一元多項式，僅用于只對多項式進行求值等不變化多項式系數(shù)和指數(shù)項（即不進行插入、刪除等變化元素間的邏輯關系的操作）的運算。若要進行其它運算，則要采用鏈式存儲構造。如：要實現(xiàn)一元多項式的加法運算，須涉及到插入、刪除等變化元素邏輯關系的操作。用C描述此線性表的次序存儲構造以下：p1+e1p2+e2pm+emdata[0]data[1]data[m]data[Max-1]…num單鏈表元素數(shù)據(jù)類型和結點的C語言描述為：typedefstructnode{floatcoef;intexp;structnode*next;}node;數(shù)據(jù)域

指針域

一元多項式相加的運算規(guī)則：對兩個一元多項式中全部指數(shù)相似的項，對應指數(shù)相加，若其和不為零，則構成“和多項式”中的一項；對于兩個一元多項式中全部指數(shù)不相似的項，則插入到“和多項式”中。例、已知：A4(X)=7+3X+9X8+5X17B3(X)=8X+22X7-9X8

求：C(X)=A4(X)+B3(X)

pqp實現(xiàn)辦法和環(huán)節(jié)：在其中一種鏈表的基礎上構造“和多項式”將p,q指針分別指向A，B鏈表的第一種結點。

依次比較p,q指針所指向結點的數(shù)據(jù)域中的指數(shù)項。pqqif(pexp<qexp){p指針指向的結點是和多項式的結點(以A表為基礎，便不必插入）；p指針后移指向A表的下一種結點；}ppfree(*hb)elseif(p

exp==qexp){系數(shù)相加；(x=p

coef+qcoef)if(x!=0){以x做為該結點的系數(shù)項；釋放q結點；p,q指針同時后移；}else{刪除p,q結點；釋放p,q結點；p,q指針后移；}elseif(p

exp>qexp){q結點為和多項式的結點，將其插入到p結點之前；q指針后移；}始終比較到兩表中有一張表已到結束結點為止：if(A表到頭：pnext==NULL){將B表中剩余的結點插入到A表之后；}

釋放B表的頭結點。2.4數(shù)組數(shù)組是大家都已經很熟悉的一種數(shù)據(jù)類型，幾乎全部高級語言程序設計中都設定了數(shù)組類型。但數(shù)組是什么數(shù)據(jù)構造：一維數(shù)組(a1,a2,……an)能夠當作是一種長度為n的線性表二維數(shù)組

線性構造邏輯構造采用次序存儲構造存儲物理構造能夠當作一種長度為m的線性表，表內元素(ai1,ai2,……ain)又可當作一種長度為n的線性表；或當作一種長度為n的線性表，表內元素(a1i,a2i,……ami)當作一種長度為m的線性表2.4.1數(shù)組的次序存儲構造1、按行依次寄存數(shù)組中各元素(以行為主分派方式)VB、C中用2、按列依次寄存數(shù)組中各元素(以列為主分派方式)FORTRAN中用二維數(shù)組的次序存儲有以下兩種形式：amnam2am1a2na22a21a1na12a11…………amna2na1nam2a22a12am1a21a11…………以行為主存儲形式以列為主存儲形式數(shù)組中普通運算是，給定一種下標，擬定與之對應的數(shù)據(jù)元素存儲地址，設每個元素占用L個字節(jié)以行為主：ADR(aij)=ADR(a11)+[n*(i-1)+j-1]*LADR(a11)ADR(a11)以列為主：ADR(aij)=ADR(a11)+[m*(j-1)+i-1]*L2.4.2規(guī)則矩陣的壓縮存儲矩陣是一種二維數(shù)組，它是諸多科學與工程計算問題中研究的數(shù)學對象。矩陣能夠用行優(yōu)先或列優(yōu)先辦法次序寄存到內存中，但是，當矩陣的階數(shù)很大時將會占較多存儲單元。而當里面的元素分布呈現(xiàn)某種規(guī)律時，這時，從節(jié)省存儲單元出發(fā)，可考慮若干元素共用一種存儲單元，即進行壓縮存儲。所謂壓縮存儲是指：為多個值相似的元素只分派一種存儲空間，值為零的元素不分派空間。壓縮存儲時，節(jié)省了存儲單元，但如何在壓縮后找到某元素呢？因此還必須給出壓縮前的下標和壓縮后下標之間變換公式，才干使壓縮存儲變得故意義。規(guī)則矩陣：非零元素的分布有規(guī)則的矩陣上三角矩陣

下三角矩陣

1．三角矩陣

上三角矩陣和下三角矩陣

22211211..................nnnnacccaacaaaaij≠ci≥j=ci<jaij≠ci≤j=ci>jc為某一常量或為“０”222111..................1nacaacca2nanna...aij=B[i(i-1)/2+j](j≤i)C(j>i)

下三角矩陣壓縮存儲時，元素值為常數(shù)C或0的元素不必存，只需存下三角部分元素，n階下三角矩陣有n2元素，只需存下三角的元素,共:1+2+3+…+n=n(n+1)/2個可選用一維數(shù)組B依次寄存，只需存儲n(n+1)/2個元素，可節(jié)省大概二分之一的空間,存儲形式為:壓縮復原(解壓縮)a11a21a22a31a32a33…an1an2…ann以行為主a11a21an1a22a32…a33a34…an4…an2…ann以列為主或則，對于下三角矩陣中元素aij(j≤i)在一維數(shù)組中為第k個元素，即aij＝B[k]在以行為主的壓縮形式下：k=(1+2+3+…+i-1)+j=i*(i-1)/2+j下三角矩陣以列為主及上三角矩陣壓縮存儲見P85，自學k=1Fori=1TonForj=1Toi{B[k]=a[i,j]k=k+1}Fori=1TonForj=1Ton{Ifj≤ia[i,j]=B[i*(i-1)/2+j]Elsea[i,j]=0}222111..................1nacaacca2nanna...2．對稱矩陣aij=B[i(i-1)/2+j](j≤i)B[j(j-1)/2+i](j>i)只需存儲下三角元素即可,用B[1:n(n+1)/2]以行為主存儲,訪問時：j≤iaij=B[i(i-1)/2+j]j>iaij=aji=B[j(j-1)/2+i]即：3．對角矩陣若矩陣中全部非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0，則稱為對角矩陣。常見的有三對角矩陣、五對角矩陣、七對角矩陣等。例如，7×7的三對角矩陣有三條對角線上元素非0。一個7×7的三對角矩陣222111..................1naa2naaa1na12a2naann...aij=B[2(i-1)+j](i-1≤j≤i+1)0(j<i-1或j>i+1)三對角矩陣壓縮存儲時，只需存三對角元素，共3(n-2)+4=3n-2個，用B[1:3n-2]以行為主存儲，訪問時，i-1≤j≤i+1時aij=B[k]；其它aij=0aij=B[2(j-1)+i](i-1≤j≤i+1)0(j<i-1或j>i+1)同理，以列優(yōu)先依次寄存，要訪問i行j列元素aij的公式為：k=[3(i-1)-1]+(j-i+2)=2(i-1)+j2.4.3普通稀疏矩陣的表達在特殊矩陣中，元素的分布呈現(xiàn)某種規(guī)律，故一定能找到一種適宜的辦法，將它們進行壓縮寄存。但是，在實際應用中，我們還經常會碰到一類矩陣：其矩陣階數(shù)很大，非零元素個數(shù)較少，零元素諸多，但非零元素的排列沒有一定規(guī)律，我們稱這一類矩陣為稀疏矩陣。00300001000000009000000000007000000000600002030000500000例：以下7×8矩陣，56個元素中只有8個非零元素，其它均為零元素，而非零元素分布是無規(guī)則的。這類矩陣也可采用壓縮存儲，只存儲非零元素，但由于非零元素分布無規(guī)律，壓縮時，除寄存非零元素的值外，還必須存儲適宜的輔助信息，才干快速擬定一種非零元素是矩陣中的哪一種位置上的元素。1、稀疏矩陣的次序存儲為了使稀疏矩陣通過壓縮后，能方便地訪問其中每一種非零元素(訪問不到的為零元素)，普通需給出三個信息：①非零元素所在行號②非零元素所在列號③非零元素值即一種非零元素可用一種三元組(i,j,v)表達。上例三元組可表達為：IJV78813318131945757664266373500300001000000009000000000007000000000600002030000500000123456712345678所對應的三元組為：(1,3,3)(1,8,1)(3,1,9)(4,5,7)(5,7,6)(6,4,2)(6,6,3)(7,3,5)為表達唯一性，添加一種三元組:（總行數(shù)，總列數(shù)，非零元素個數(shù)），即(7,8,8)，表達稀疏矩陣的總體信息。因此，一種含有t個非零元素的稀疏矩陣可用t+1個三元組表達，其中第一種三元組用于表達稀疏矩陣的總體信息，其后各三元組依次表達各非零元素，且按以行為主的次序存儲。慣用三列二維的表格或數(shù)組形式表達(三列二維數(shù)組)，如圖。2、稀疏矩陣的鏈式存儲構造當稀疏矩陣中非零元素的位置或個數(shù)經常變動時，三元組的次序存儲構造就不適合，此時，采用鏈表作為存儲構造更為恰當。稀疏矩陣的鏈式存儲構造辦法有幾個，如帶行指針的單鏈表表達法和十字鏈表表達辦法。⑴．帶行指針的鏈表把含有相似行號的非零元素用一種單鏈表連接起來，稀疏矩陣中的若干行構成若干個單鏈表，合起來稱為帶行指針的鏈表。例如，上例稀疏矩陣的帶行指針的鏈表描述形式：73

5

^

4

57

^

5

218

^0030000100000000900000000000700001800006000020300005000001234567123456783

1

9

^1

3

31

8

1

^6

6

3

^6

4

2

1行指針2^45637這種辦法能方便找到同一行的全部非零元素，但不便尋找同一列的全部元素⑵．十字鏈表十字鏈表是稀疏矩陣的的一種較好的存儲辦法，在該辦法中，每一種非零元素用一種結點表達，結點中除了表達非零元素所在的行、列和值的三元組（i,j,v）外，還需增加兩個鏈域：行指針域(rptr)，用來指向本行中下一種非零元素；列指針域(cptr)，用來指向本列中下一種非零元素。稀疏矩陣中同一行的非零元素通過向右的rptr指針鏈接成一種鏈表。同一列的非零元素也通過cptr指針鏈接成一種鏈表。因此，每個非零元素既是第i行鏈表中的一種結點，又是第j列鏈表中的一種結點，相稱于處在一種十字交叉路口，故稱這種鏈表為十字鏈表。十字鏈表結點向右域向下域值域列域行域rowcolvaldownright指向本行下一種元素指向本列下一種元素另外，為了運算方便，我們規(guī)定行、列循環(huán)鏈表的表頭結點和表達非零元素的結點同樣，也定為五個域，且規(guī)定行、列、域值為0，并且將全部的行、列鏈表和頭結點一起鏈成一種循環(huán)鏈表。在行（列）表頭結點中，行、列域的值都為0，故兩組表頭結點能夠共用，即第i行鏈表和第i列鏈表共用一種表頭結點，這些表頭結點本身又能夠通過V域（非零元素值域，但在表頭結點中為next，指向下一種表頭結點）相鏈接。另外，再增加一種附加結點（由指針H批示，行、列域分別為稀疏矩陣的行、列數(shù)目），附加結點指向第一種表頭結點，則整個十字鏈表可由H指針惟一擬定。

5430070010200400000009123451234例：如圖稀疏矩陣的十字鏈表描述形式：147113344000000231549312000000H00000000在表頭結點中，行、列域的值都為0，故兩組表頭結點能夠共用，即第i行鏈表和第i列鏈表共用一種表頭結點，這些表頭結點本身又能夠通過V域相鏈接。再增加一種表頭結點H，則整個十字鏈表可由H指針惟一擬定2.5樹與二叉樹

樹是一種簡樸的非線性構造，在樹這種數(shù)據(jù)構造中，全部數(shù)據(jù)元素之間的關系含有明顯的層次特性。如圖，可用于描述含有層次關系的數(shù)據(jù)。如學校行政關系構造(P114圖2.40)ABCDEFGIHJ2.5.1樹的基本概念1、定義：樹是由n個（n>0）含有相似類型的結點元素構成的有限集合，且滿足下列的條件：1)其中有一種結點無直接前驅，稱為根（Root）；2)其它的結點元素可分為m個互不相交的子集T1,T2…Tm，這m個子集本身又構成樹，稱為Root的子樹。上右圖所示為一棵樹，其中A為根，它有三棵子樹：T1={B,E,F};T2={C,G,H,I,J};T3={D}在子樹T2中，C是該子樹的根，它有三棵子樹：T21={G}；T22={H}；T23={I，J}；T22和T21僅有一種根結點，沒有子樹。注意：（1）樹的定義中n>0，即沒有空樹的概念；（2）樹的定義中采用了遞歸定義的辦法，顯示了樹構造本身的這種遞歸的性質。2、樹的有關術語ABCDEFGIHJ根結點、父結點、子結點、葉子結點、內部結點或分支結點(度不為0的結點)兄弟結點(含有同一父結點的子結點稱為兄弟結點)結點的度、樹的度，樹的深度、子樹森林：是m(m>0)棵樹的集合有序樹樹中結點在同層中按從左到右有序排列，不能交換的樹稱有序樹，反之稱無序樹例:((a+(b+c/d))+(e*h-g*f(s,t,x+y))的體現(xiàn)式樹3、可用樹型構造描述一種體現(xiàn)式：用操作數(shù)代表樹葉，運算符代表非葉子結點，所構成的樹稱體現(xiàn)式樹。編譯系統(tǒng)中慣用的體現(xiàn)式表達辦法。體現(xiàn)式樹是有序樹,結點次序不可更改。+b+a-cd/+*eh+xy*gfts樹在計算機中可用多重鏈表表達，即每個結點有多個指針域，每個指針域指向它的一種子結點，每個結點的指針域數(shù)由該結點的度擬定4、樹的存儲值度Link1Link2…LinknABCDEFG例：ABCDEFG3210000BT1、定義：二叉樹是由n個（n0）含有相似類型的結點元素構成的有限集合，且滿足下列的條件：（1）由一種根結點和它的兩棵左右子樹構成；（2）其左右子樹分別又構成一棵二叉樹。注意：①二叉樹的定義中n0，即表達有空二叉樹的概念；②二叉樹的定義中也采用了遞歸定義的辦法，顯示了二叉樹構造本身的這種遞歸的性質。③二叉樹的子樹有左右之分，次序不能顛倒。由定義知二叉樹有五種基本形態(tài)，以下圖所示：2.5.2二叉樹及其基本性質空性質1在二叉樹的第K層上，最多有2k-1(1≤k)個結點。性質2深度為m的二叉樹最多有2m-1個結點。2、二叉樹的基本性質性質3在任意一棵二叉樹中，度為0的結點（即葉子結點）總是比度為2的結點多一種。性質4含有n個結點