《數(shù)據(jù)結(jié)構(gòu)》各章節(jié)復(fù)習(xí)范圍

1、第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)的運算。但運算的實現(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）索引存

2、儲方法 （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）可行性 （4）有輸入 （5）有輸出 4.算法分析 (1)算法的時間復(fù)雜度：是指其基本運算在算法中重復(fù)執(zhí)行的次數(shù)。算法中基本運算次數(shù)T(n)是問題規(guī)模n的某個函數(shù)f(n)，記作： T(n)=O(f(n) 記號“O”讀作“

3、大O”，它表示隨問題規(guī)模n的增大算法執(zhí)行時間的增長率和f(n)的增長率相同。 (2)算法空間復(fù)雜度：是對一個算法在運行過程中臨時占用的存儲空間大小的量度 。對于空間復(fù)雜度為O(1)的算法稱為原地工作或就地工作算法。 第2章 線性表 1.線性表的定義 線性表是具有相同特性的數(shù)據(jù)元素的一個有限序列。該序列中所含元素的個數(shù)叫做線性表的長度，用n表示，n0。當(dāng)n=0時，表示線性表是一個空表，即表中不包含任何元素。 1.線性表的順序存儲結(jié)構(gòu)順序表 typedef struct ElemType elemMaxSize;/*存放順序表元素*/ int length;/*存放順序表的長度*/ SqList;

4、順序表基本運算的實現(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)位置上，并保持線性表的有序性。void Insert(SqList &A,ElemType x) int i=0,j; while (iA.length & AS.elemi=i;j-) A.elemj+1=A.elem

5、j;A.elemi=x; A.length+; 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è)計的基礎(chǔ)?！纠?.1】 設(shè)C=a1,b1

6、,a2,b2,an,bn為一線性表，采用帶頭結(jié)點的hc單鏈表存放，編寫一個就地算法，將其拆分為兩個線性表，使得： A=a1,a2,an，C=b1,b2,bnvoid fun(LinkList *hc, LinkList *&ha,LinkList *&hb)LinkList *p=hc-next,*ra,*rb;ha=hc; /*ha的頭結(jié)點利用hc的頭結(jié)點*/ra=ha; /*ra始終指向ha的末尾結(jié)點*/hb=(LinkList *)malloc(sizeof(LinkList);/*創(chuàng)建hb頭結(jié)點*/rb=hb; /*rb始終指向hb的末尾結(jié)點*/while (p!=NULL)ra-ne

7、xt=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域置空*/ 整個算法實際上是采用尾插法建表。（2）雙鏈表基本運算的實現(xiàn) 重點：插入和刪除結(jié)點的算法。（3）循環(huán)鏈表基本運算的實現(xiàn) 重點：判斷最后一個結(jié)點。第3章 棧和隊列 3.1 棧1.棧的定義 棧是一種只能在一端進行插入或刪除操作的線性表。表中允許進行插入、刪除操作的一端稱為棧頂。表的另一端稱為棧底。當(dāng)棧中沒有數(shù)據(jù)元素時，稱為空棧。棧的插入操作通常稱為進?；蛉霔＃瑮５膭h除

8、操作通常稱為退棧或出棧。2.棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)typedef struct ElemType elemMaxSize; int top;/*棧指針*/ SqStack;?？諚l件:s-top=-1棧滿條件:s-top=MaxSize-13.棧的鏈式存儲結(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.隊列的定義 隊列簡稱隊，它也是一種運算

9、受限的線性表，其限制僅允許在表的一端進行插入，而在表的另一端進行刪除。進行插入的一端稱做隊尾（rear），進行刪除的一端稱做隊首（front）。2.隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)typedef struct ElemType 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

10、+1)MaxSize 隊尾指針進1：rear=(rear+1)MaxSize隊空條件：q-rear=q-front 隊滿條件：(q-rear+1) % MaxSize=q-front3.隊列的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn)struct qnode ElemType data; struct qnode *next; QNode;typedef struct QNode *front; QNode *rear; LiQueue;第4章 串 1.串的定義 串（或字符串)，是由零個或多個字符組成的有窮序列。含零個字符的串稱為空串，用表示。串中所含字符的個數(shù)稱為該串的長度（或串長）。 2.串的順序存儲

11、結(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)存單元中。 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

12、-1），則稱其為n階對稱矩陣。 A0.n-10.n-1-B0.n(n+1)/2 i(i+1)/2 +j 當(dāng)ij時k= j(j+1)/2 +i 當(dāng)ij時 (2)三角矩陣 采用類似的壓縮方法.4.稀疏矩陣 (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章 樹和二叉樹 6.1 樹1.樹的定義 樹是由n（n0）個結(jié)點組成的有限集合（記為T）。其中， 如果

13、n=0，它是一棵空樹，這是樹的特例； 如果n0，這n個結(jié)點中存在（有僅存在）一個結(jié)點作為樹的根結(jié)點，簡稱為根（root），其余結(jié)點可分為m （m0）個互不相交的有限集T1,，T2，Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。2.樹的表示法 (邏輯表示方法)(1) 樹形表示法 (2) 文氏圖表示法 (3) 凹入表示法 (4) 括號表示法 3.樹的遍歷先根遍歷算法為： （1）訪問根結(jié)點； （2）按照從左到右的次序先根遍歷根結(jié)點的每一棵子樹。后根遍歷算法為： （1）按照從左到右的次序后根遍歷根結(jié)點的每一棵子樹； （2）訪問根結(jié)點。4.樹(森林)與二叉樹之間的相互轉(zhuǎn)換6.2

14、二叉樹 1.二叉樹的定義 二叉樹也稱為二次樹或二分樹，它是有限的結(jié)點集合，這個集合或者是空，或者由一個根結(jié)點和兩棵互不相交的稱為左子樹和右子樹的二叉樹組成。 完全二叉樹,滿二叉樹的定義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é)點的編號

15、為1，則編號為49的結(jié)點的左孩子編號為 。 A.98 B.99 C.50 D.48 答：A 【例6.2】 深度為5的二叉樹至多有 個結(jié)點。 A.16 B.32 C.31 D.10 答：相同滿度時滿二叉樹結(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） 先序遍歷

16、void preorder（BTNode t） printf(“%d”,t-data);preorder(t-lchild);preorder(t-rchild); （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

17、）個不同結(jié)點的二又樹，都可由它的中序序列和先序序列惟一地確定。 任何n（n0）個不同結(jié)點的二又樹，都可由它的中序序列和后序序列惟一地確定。 掌握它們的構(gòu)造方法。6.線索二叉樹 (1)線索二叉樹的概念 對于具有n個結(jié)點的二叉樹，采用二叉鏈存儲結(jié)構(gòu)時，每個結(jié)點有兩個指針域，總共有2n個指針域，又由于只有n-1個結(jié)點被有效指針?biāo)赶颍涓Y(jié)點沒有被有效指針域所指向），則共有2n-(n-1)=n+1個空鏈域。遍歷二叉樹的結(jié)果是一個結(jié)點的線性序列。可以利用這些空鏈域存放指向結(jié)點的前驅(qū)和后繼結(jié)點的指針。這樣的指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作線索。 對二叉樹以某種方式遍歷使其變?yōu)榫€索二叉樹的

18、過程稱作按該方式對二叉樹進行線索化。 (2) 二叉樹進行線索化的過程 不要求掌握算法。6.3 哈夫曼樹1.哈夫曼樹的定義在n個帶權(quán)葉子結(jié)點構(gòu)成的所有二叉樹中，帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹（或最優(yōu)二叉樹） 。2.哈夫曼樹的構(gòu)造過程 3.哈夫曼編碼的構(gòu)造過程 第7章 廣義表相關(guān)概念: 一個廣義表中所含元素的個數(shù)稱為它的長度. 一個廣義表中括號嵌套的最大次數(shù)為它的深度.表的第一個元素a1為廣義表GL的表頭，其余部分(a2，ai，ai+1，an)為GL的表尾. 第8章 圖 1.圖的基本概念(1)頂點的度、入度和出度 (2)完全圖 (3)子圖 (4)路徑和路徑長度 (5)連通、連通圖和連通

19、分量 (6)強連通圖和強連通分量 (7)權(quán)和網(wǎng) 2.圖的存儲結(jié)構(gòu) (1) 鄰接矩陣存儲方法(2)鄰接表存儲方法 掌握兩種存儲方法的優(yōu)缺點，同一種功能在不同存儲結(jié)構(gòu)上的實現(xiàn)算法。3.圖的遍歷 （1）深度優(yōu)先搜索遍歷 void DFS(ALGraph *G,int v) ArcNode*p;Visitedv=1; /*置已訪問標(biāo)記*/ printf(%d ,v); /*輸出被訪問頂點的編號*/ p=G-adjlistv.firstarc;/*p指向頂點v的第一條弧的弧頭結(jié)點*/while (p!=NULL) if (visitedp-adjvex=0) DFS(G,p-adjvex); p=p-n

20、extarc; /*p指向頂點v的下一條弧的弧頭結(jié)點*/（2）廣度優(yōu)先搜索遍歷 void BFS(ALGraph *G,int v) ArcNode *p;int queueMAXV,front=0,rear=0; /*定義循環(huán)隊列并初始化*/int visitedMAXV; /*定義存放結(jié)點的訪問標(biāo)志的數(shù)組*/int w,i;for (i=0;in;i+) visitedi=0;/*訪問標(biāo)志數(shù)組初始化*/printf(%2d,v);visitedv=1; /*置已訪問標(biāo)記*/rear=(rear+1)%MAXV;queuerear=v; /*v進隊*/while (front!=rear)

21、/*若隊列不空時循環(huán)*/front=(front+1)%MAXV;w=queuefront; /*出隊并賦給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)之間是否有路徑。 解：先置全局變量visi