《數(shù)據(jù)結(jié)構(gòu)》期末總復(fù)習(xí)講解

1、第1章 緒論,第2章 線性表,第3章 棧和隊列,第4章 串,第5章 數(shù)組和稀疏矩陣,第6章 樹和二叉樹,第8章 圖,數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí),第9章 查找,第10章 內(nèi)排序,第7章 廣義表,第1章 緒論,1.數(shù)據(jù)結(jié)構(gòu)的定義,數(shù)據(jù)數(shù)據(jù)元素 數(shù)據(jù)項,數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)以及相互之間的聯(lián)系。包括： （1）數(shù)據(jù)的邏輯結(jié)構(gòu)。 （2）數(shù)據(jù)的存儲結(jié)構(gòu)（物理結(jié)構(gòu)）。 （3）施加在該數(shù)據(jù)上的運算。,數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。 數(shù)據(jù)的存儲結(jié)構(gòu)是邏輯結(jié)構(gòu)用計算機語言的實現(xiàn)（亦稱為映象），它是依賴于計算機語言的。 數(shù)據(jù)的運算是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的，每種邏輯結(jié)構(gòu)都有一組相應(yīng)的運算

2、。但運算的實現(xiàn)與數(shù)據(jù)的存儲結(jié)構(gòu)有關(guān)。,邏輯結(jié)構(gòu)主要有兩大類： （1）線性結(jié)構(gòu) （2）非線性結(jié)構(gòu)： 1）樹形結(jié)構(gòu) 2）圖形結(jié)構(gòu),存儲結(jié)構(gòu)分為如下四種：,（1）順序存儲方法 （2）鏈式存儲方法 （3）索引存儲方法 （4）散列存儲方法,2.抽象數(shù)據(jù)類型 抽象數(shù)據(jù)類型（Abstract Data Type簡寫為ADT）指的是用戶進行軟件系統(tǒng)設(shè)計時從問題的數(shù)學(xué)模型中抽象出來的邏輯數(shù)據(jù)結(jié)構(gòu)和邏輯數(shù)據(jù)結(jié)構(gòu)上的運算，而不考慮計算機的具體存儲結(jié)構(gòu)和運算的具體實現(xiàn)算法。,3.什么是算法,算法是對特定問題求解步驟的一種描述，它是指令的有限序列 。,算法的五個重要的特性 ： （1）有窮性 （2）確定性 （3）可行性

3、（4）有輸入 （5）有輸出,4.算法分析,(1)算法的時間復(fù)雜度：是指其基本運算在算法中重復(fù)執(zhí)行的次數(shù)。,算法中基本運算次數(shù)T(n)是問題規(guī)模n的某個函數(shù)f(n)，記作： T(n)=O(f(n) 記號“O”讀作“大O”，它表示隨問題規(guī)模n的增大算法執(zhí)行時間的增長率和f(n)的增長率相同。,(2)算法空間復(fù)雜度：是對一個算法在運行過程中臨時占用的存儲空間大小的量度 。,對于空間復(fù)雜度為O(1)的算法稱為原地工作或就地工作算法。,第2章 線性表,1.線性表的定義 線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。該序列中所含元素的個數(shù)叫做線性表的長度，用n表示，n0。當(dāng)n=0時，表示線性表是一個空表，

4、即表中不包含任何元素。,1.線性表的順序存儲結(jié)構(gòu)順序表,typedef struct ElemType elemMaxSize; /*存放順序表元素*/ int length; /*存放順序表的長度*/ SqList;,順序表基本運算的實現(xiàn),插入數(shù)據(jù)元素算法：元素移動的次數(shù)不僅與表長n有關(guān) ；插入一個元素時所需移動元素的平均次數(shù) n2。平均時間復(fù)雜度為O(n)。,刪除數(shù)據(jù)元素算法:元素移動的次數(shù)也與表長n有關(guān) 。刪除一個元素時所需移動元素的平均次數(shù)為(n-1)/2。刪除算法的平均時間復(fù)雜度為O(n)。,【例2.1】 設(shè)計一個算法，將x插入到一個有序（從小到大排序）的線性表（順序存儲結(jié)構(gòu)）的適當(dāng)

5、位置上，并保持線性表的有序性。,void Insert(SqList ,2.線性表的鏈式存儲結(jié)構(gòu)鏈表,定義單鏈表結(jié)點類型: typedef struct LNode ElemType data; struct LNode *next; /*指向后繼結(jié)點*/ LinkList;,定義雙鏈表結(jié)點類型: typedef struct DNode ElemType data; struct DNode *prior; /*指向前驅(qū)結(jié)點*/ struct DNode *next; /*指向后繼結(jié)點*/ DLinkList;,（1）單鏈表基本運算的實現(xiàn),重點：頭插法建表和尾插法建表算法，它是很多算法設(shè)計的

6、基礎(chǔ)。,【例2.1】 設(shè)C=a1,b1,a2,b2,an,bn為一線性表，采用帶頭結(jié)點的hc單鏈表存放，編寫一個就地算法，將其拆分為兩個線性表，使得： A=a1,a2,an，C=b1,b2,bn,void fun(LinkList *hc, LinkList * /*rb始終指向hb的末尾結(jié)點*/,while (p!=NULL) ra-next=p;ra=p; /*將*p鏈到ha單鏈表未尾*/ p=p-next; if (p!=NULL) rb-next=p;rb=p; /*將*p鏈到hb單鏈表未尾*/ p=p-next; ,ra=rb=NULL; /*兩個尾結(jié)點的next域置空* 整個算法實

7、際上是采用尾插法建表。,（2）雙鏈表基本運算的實現(xiàn),（3）循環(huán)鏈表基本運算的實現(xiàn),重點：插入和刪除結(jié)點的算法。,重點：判斷最后一個結(jié)點。,第3章 棧和隊列,3.1 棧,1.棧的定義 棧是一種只能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時，稱為空棧。棧的插入操作通常稱為進棧或入棧，棧的刪除操作通常稱為退?；虺鰲?。,2.棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn),typedef struct ElemType elemMaxSize; int top;/*棧指針*/ SqStack;,棧空條件:s-top=-1,棧滿條件:s-top=

8、MaxSize-1,3.棧的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn),typedef struct linknode ElemType data;/*數(shù)據(jù)域*/ struct linknode *next;/*指針域*/ LiStack;,帶頭結(jié)點的單鏈表來實現(xiàn)(也可不帶頭結(jié)點),?？諚l件:s-next=NULL 棧滿條件:?,3.2 隊列,1.隊列的定義 隊列簡稱隊，它也是一種運算受限的線性表，其限制僅允許在表的一端進行插入，而在表的另一端進行刪除。進行插入的一端稱做隊尾（rear），進行刪除的一端稱做隊首（front）。,2.隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn),typedef struct Ele

9、mType elemMaxSize； int front,rear；/*隊首和隊尾指針*/ SqQueue；,把數(shù)組的前端和后端連接起來，形成一個環(huán)形的順序表，即把存儲隊列元素的表從邏輯上看成一個環(huán)，稱為循環(huán)隊列。 循環(huán)隊列首尾相連，當(dāng)隊首指針front=MaxSize-1后，再前進一個位置就自動到0，這可以利用除法取余的運算()來實現(xiàn)： 隊首指針進1：front=(front+1)MaxSize 隊尾指針進1：rear=(rear+1)MaxSize,隊空條件：q-rear=q-front 隊滿條件：(q-rear+1) % MaxSize=q-front,3.隊列的鏈式存儲結(jié)構(gòu)及其基本運算

10、的實現(xiàn),struct qnode ElemType data; struct qnode *next; QNode; typedef struct QNode *front; QNode *rear; LiQueue;,第4章 串,1.串的定義 串（或字符串)，是由零個或多個字符組成的有窮序列。含零個字符的串稱為空串，用表示。串中所含字符的個數(shù)稱為該串的長度（或串長）。,2.串的順序存儲結(jié)構(gòu)順序串,3.串的鏈式存儲結(jié)構(gòu)鏈串,KMP算法不作要求。,第5章 數(shù)組和稀疏矩陣,1. 數(shù)組的定義 數(shù)組是n（n1）個相同類型數(shù)據(jù)元素 a1，a2，an 構(gòu)成的有限序列，且該有限序列存儲在一塊地址連續(xù)的內(nèi)存單

11、元中。,2.數(shù)組的順序存儲結(jié)構(gòu),對于數(shù)組Ac1.d1,c2.d2 以行序為主序 : LOC(ai,j)=LOC(ac1,c2)+(i-c1)*(d2-c2+1)+(j-c2)*k,以列序為主序 LOC(ai,j)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+(i-c1)*k,3.特殊矩陣的壓縮存儲,(1) 對稱矩陣 若一個n階方陣Ann中的元素滿足ai,j=aj,i（0i，jn-1），則稱其為n階對稱矩陣。,i(i+1)/2 +j 當(dāng)ij時 k= j(j+1)/2 +i 當(dāng)ij時,A0.n-10.n-1-B0.n(n+1)/2,(2)三角矩陣,采用類似的壓縮方法.,4.稀疏矩陣,

12、(1) 三元組表示 (2) 十字鏈表表示 各種表示的基本思路。,【 例5.1】 二維數(shù)組A44（即A0.30.3）的元素起始地址是loc(A00)=1000，元素的長度為2，則loc(A22)為多少？ 答：Loc(A22)=Loc(A00)+(2-0)*(3-0+1)+(2-0)*2=1020。,第6章 樹和二叉樹,1.樹的定義 樹是由n（n0）個結(jié)點組成的有限集合（記為T）。其中， 如果n=0，它是一棵空樹，這是樹的特例； 如果n0，這n個結(jié)點中存在（有僅存在）一個結(jié)點作為樹的根結(jié)點，簡稱為根（root），其余結(jié)點可分為m （m0）個互不相交的有限集T1,，T2，Tm，其中每一棵子集本身又是

13、一棵符合本定義的樹，稱為根root的子樹。,6.1 樹,2.樹的表示法 (邏輯表示方法),(1) 樹形表示法 (2) 文氏圖表示法 (3) 凹入表示法 (4) 括號表示法,3.樹的遍歷 先根遍歷算法為： （1）訪問根結(jié)點； （2）按照從左到右的次序先根遍歷根結(jié)點的每一棵子樹。 后根遍歷算法為： （1）按照從左到右的次序后根遍歷根結(jié)點的每一棵子樹； （2）訪問根結(jié)點。,4.樹(森林)與二叉樹之間的相互轉(zhuǎn)換,6.2 二叉樹,1.二叉樹的定義 二叉樹也稱為二次樹或二分樹，它是有限的結(jié)點集合，這個集合或者是空，或者由一個根結(jié)點和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。 完全二叉樹,滿二叉樹的定義

14、,2.二叉樹性質(zhì) 性質(zhì)1 非空二叉樹上葉結(jié)點數(shù)等于雙分支結(jié)點數(shù)加1。即n0=n2+1. 性質(zhì)2 非空二叉樹上第i層上至多有2i-1個結(jié)點（i1）。 性質(zhì)3 高度為h的二叉樹至多有2h-1個結(jié)點（h1） 。 性質(zhì)4 完全二叉樹的性質(zhì) 。 性質(zhì)5 具有n個（n0）結(jié)點的完全二叉樹的高度為log2n+1或log2n+1。,【例6.1】將一棵有100個結(jié)點的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點進行編號，根結(jié)點的編號為1，則編號為49的結(jié)點的左孩子編號為 。 A.98 B.99 C.50 D.48 答：A 【例6.2】 深度為5的二叉樹至多有 個結(jié)點。 A.16 B.32 C.31 D.1

15、0 答：相同滿度時滿二叉樹結(jié)點最多，h=5的滿二叉樹結(jié)點個數(shù)=25-1=31。本題答案應(yīng)為C。,3.二叉樹存儲結(jié)構(gòu),（1）二叉樹的順序存儲結(jié)構(gòu) （2）二叉鏈存儲結(jié)構(gòu) typedef struct node ElemType data; /*數(shù)據(jù)元素*/ struct node *lchild; /*指向左孩子*/ struct node *rchild; /*指向右孩子*/ BTNode;,4.二叉樹的遍歷,（1） 先序遍歷 void preorder（BTNode t） printf(“%d”,t-data); preorder(t-lchild); preorder(t-rchild);

16、,（2） 中序遍歷 void inorder（BTNode t） inorder(t-lchild); printf(“%d”,t-data); inorder(t-rchild); ,（3）后序遍歷 void postorder（BTNode t） postorder(t-lchild); postorder(t-rchild); printf(“%d”,t-data); 注意：重點掌握基于遍歷的遞歸算法設(shè)計。,5.二叉樹的構(gòu)造,任何n（n0）個不同結(jié)點的二又樹，都可由它的中序序列和先序序列惟一地確定。 任何n（n0）個不同結(jié)點的二又樹，都可由它的中序序列和后序序列惟一地確定。 掌握它們的構(gòu)

17、造方法。,6.線索二叉樹,(1)線索二叉樹的概念 對于具有n個結(jié)點的二叉樹，采用二叉鏈存儲結(jié)構(gòu)時，每個結(jié)點有兩個指針域，總共有2n個指針域，又由于只有n-1個結(jié)點被有效指針所指向（樹根結(jié)點沒有被有效指針域所指向），則共有2n-(n-1)=n+1個空鏈域。,遍歷二叉樹的結(jié)果是一個結(jié)點的線性序列?？梢岳眠@些空鏈域存放指向結(jié)點的前驅(qū)和后繼結(jié)點的指針。這樣的指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作線索。 對二叉樹以某種方式遍歷使其變?yōu)榫€索二叉樹的過程稱作按該方式對二叉樹進行線索化。 (2) 二叉樹進行線索化的過程 不要求掌握算法。,6.3 哈夫曼樹,1.哈夫曼樹的定義,在n個帶權(quán)葉子結(jié)點構(gòu)成

18、的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹（或最優(yōu)二叉樹） 。,2.哈夫曼樹的構(gòu)造過程 3.哈夫曼編碼的構(gòu)造過程,相關(guān)概念: 一個廣義表中所含元素的個數(shù)稱為它的長度. 一個廣義表中括號嵌套的最大次數(shù)為它的深度. 表的第一個元素a1為廣義表GL的表頭，其余部分(a2，ai，ai+1，an)為GL的表尾.,第7章 廣義表,第8章 圖,1.圖的基本概念,(1)頂點的度、入度和出度 (2)完全圖 (3)子圖 (4)路徑和路徑長度 (5)連通、連通圖和連通分量 (6)強連通圖和強連通分量 (7)權(quán)和網(wǎng),2.圖的存儲結(jié)構(gòu),(1) 鄰接矩陣存儲方法 鄰接表存儲方法 掌握兩種存儲方法的優(yōu)缺點，

19、同一種功能在不同存儲結(jié)構(gòu)上的實現(xiàn)算法。,3.圖的遍歷,（1）深度優(yōu)先搜索遍歷,void DFS(ALGraph *G,int v) ArcNode*p;Visitedv=1; /*置已訪問標記*/ printf(%d ,v); /*輸出被訪問頂點的編號*/ p=G-adjlistv.firstarc; /*p指向頂點v的第一條弧的弧頭結(jié)點*/,while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); p=p-nextarc; /*p指向頂點v的下一條弧的弧頭結(jié)點*/ ,（2）廣度優(yōu)先搜索遍歷,void BFS(ALGraph *G,int

20、v) ArcNode *p; int queueMAXV,front=0,rear=0; /*定義循環(huán)隊列并初始化*/ int visitedMAXV; /*定義存放結(jié)點的訪問標志的數(shù)組*/ int w,i; for (i=0;in;i+) visitedi=0; /*訪問標志數(shù)組初始化*/ printf(%2d,v); visitedv=1; /*置已訪問標記*/ rear=(rear+1)%MAXV; queuerear=v; /*v進隊*/,while (front!=rear) /*若隊列不空時循環(huán)*/ front=(front+1)%MAXV; w=queuefront; /*出隊并

21、賦給w*/ p=G-adjlistw.firstarc; while (p!=NULL) if (visitedp-adjvex=0) printf(%2d,p-adjvex); visitedp-adjvex=1; rear=(rear+1)%MAXV; queuerear=p-adjvex; p=p-nextarc; printf(n); ,(3)非連通圖的遍歷 采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下： DFS1(ALGraph *g) int i; for (i=0;in;i+) if (visitedi=0) DFS(g,i); ,采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下： BFS1(ALGraph *g) int i; for (i=0;in;i+) if (visitedi=0) BFS(g,i); ,【例7.1】 試以鄰接表為存儲結(jié)構(gòu)，分別寫出基于DFS和BPS遍歷的算法來判別頂點i和頂點j(ij)之間是否有路徑。 解：先置全局變量visited為0，然后從頂點i開始進行