數(shù)據(jù)結(jié)構(gòu)教案

緒論基本概念和術(shù)語(yǔ)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)數(shù)據(jù)：凡能被計(jì)算機(jī)存儲(chǔ)、加工的對(duì)象，通稱(chēng)為數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，普通含有完整、擬定的實(shí)際意義。數(shù)據(jù)項(xiàng)：是數(shù)據(jù)不可分割的最小單位。注意：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)是數(shù)據(jù)組織的三個(gè)層次。如：（80，90，100，110，120）、表格數(shù)據(jù)的邏輯構(gòu)造邏輯構(gòu)造：數(shù)據(jù)元素之間的“鄰接”關(guān)系四種邏輯構(gòu)造線(xiàn)性構(gòu)造：數(shù)據(jù)元素之間存在“一對(duì)一”的關(guān)系樹(shù)形構(gòu)造：數(shù)據(jù)元素之間存在“一對(duì)多”的關(guān)系圖狀構(gòu)造：數(shù)據(jù)元素之間存在“多對(duì)多”的關(guān)系集合：數(shù)據(jù)元素之間沒(méi)有鄰接關(guān)系數(shù)據(jù)的存儲(chǔ)構(gòu)造存儲(chǔ)構(gòu)造：數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的寄存方式兩種存儲(chǔ)構(gòu)造次序存儲(chǔ)：將數(shù)據(jù)元素依次寄存到一組持續(xù)的存儲(chǔ)單元中。鏈?zhǔn)酱鎯?chǔ)：將數(shù)據(jù)元素寄存到非持續(xù)的存儲(chǔ)單元中，并運(yùn)用指針將各個(gè)存儲(chǔ)單元鏈接起來(lái)。數(shù)據(jù)的基本操作加工型操作：變化數(shù)據(jù)元素的個(gè)數(shù)或數(shù)據(jù)元素的內(nèi)容引用型操作：數(shù)據(jù)元素的個(gè)數(shù)或數(shù)據(jù)元素的內(nèi)容均未變化數(shù)據(jù)構(gòu)造1．含義：涉及三方面的內(nèi)容：邏輯構(gòu)造：反映數(shù)據(jù)元素之間的鄰接”關(guān)系存儲(chǔ)構(gòu)造：反映數(shù)據(jù)元素在計(jì)算機(jī)內(nèi)的寄存方式數(shù)據(jù)的操作2.數(shù)據(jù)按構(gòu)造分，可分為4類(lèi)，每一類(lèi)對(duì)應(yīng)著一種邏輯構(gòu)造數(shù)據(jù)邏輯構(gòu)造線(xiàn)性表線(xiàn)性構(gòu)造樹(shù)樹(shù)型構(gòu)造圖圖狀構(gòu)造查找表集合1.3算法描述算法：解決問(wèn)題的辦法和環(huán)節(jié)。算法的描述辦法框圖非形式語(yǔ)言：如中文類(lèi)C語(yǔ)言程序C語(yǔ)言程序1.4算法分析對(duì)同一問(wèn)題，能夠設(shè)計(jì)多個(gè)不同的算法，但必有一種算法的時(shí)間效率最高。估算一種算法的運(yùn)行時(shí)間=1\*GB3①擬定問(wèn)題的輸入規(guī)模n。=2\*GB3②根據(jù)問(wèn)題的特點(diǎn)，選擇一種操作作為“原則操作”。（普通以條件判斷或賦值語(yǔ)句為原則操作）=3\*GB3③擬定在給定輸入下共執(zhí)行多少次原則操作，從而算出運(yùn)行時(shí)間T。算法的時(shí)間復(fù)雜度對(duì)算法的運(yùn)行時(shí)間T(n)，無(wú)視全部的常數(shù)、低次項(xiàng)，無(wú)視最高項(xiàng)的系數(shù)，稱(chēng)為算法的時(shí)間復(fù)雜度，以O(shè)表達(dá)。運(yùn)行時(shí)間時(shí)間復(fù)雜度T(n)=c常數(shù)階O(1)T(n)=cn線(xiàn)性階O(n)T(n)=cn2平方階O(n2)指數(shù)階O()對(duì)數(shù)階O()指針和構(gòu)造一、什么是指針1．存儲(chǔ)單元的地址每一種存儲(chǔ)單元由一種或多個(gè)字節(jié)構(gòu)成，存儲(chǔ)單元中第一種字節(jié)的編號(hào)稱(chēng)為存儲(chǔ)單元的地址。2．什么叫指針？指針總是指向某個(gè)變量。指針的值是所指向變量的地址，指針的類(lèi)型是所指向變量的類(lèi)型。二、指針變量1．指針變量的定義類(lèi)型*指針變量名;例：int*p;解釋?zhuān)憾x一種指針p，它只能指向int型變量。2．兩個(gè)運(yùn)算符&：取地址運(yùn)算符，例&i*：指針運(yùn)算符，例*p例：int*p,i=3;p=&i;printf("%d,%d\n",i,*p);闡明：①&和*互為逆運(yùn)算，即：&*p=p，*&i=i②定義指針變量時(shí)，指針變量名前面的“*”不是指針運(yùn)算符。=3\*GB3③指針能夠與整數(shù)進(jìn)行加、減運(yùn)算。指針±n=指針的原值±sizeof(指針的類(lèi)型)×n=4\*GB3④同類(lèi)型的兩個(gè)指針能夠互相賦值。三、指針與數(shù)組1．?dāng)?shù)組名代表該數(shù)組的首地址，例a==&a[0]2．設(shè)inta[6]，則a[i]，*(a+i)是等價(jià)的&a[i]，a+i是等價(jià)的3．表達(dá)數(shù)組元素的辦法下標(biāo)法：例a[i]指針?lè)ǎ豪?(a+i)4．設(shè)指針p指向數(shù)組a的某一種元素，則p++：使p指向數(shù)組的下一種元素；四、構(gòu)造1．定義構(gòu)造類(lèi)型struct構(gòu)造名{組員定義列表}例：structperson{intno;charname[6];};2．定義構(gòu)造變量structpersonx;引用構(gòu)造變量的組員構(gòu)造變量名．組員名構(gòu)造變量的初始化構(gòu)造指針例：已知structpersonx,*p;p=&x;則表達(dá)x的no組員有三種形式：x.no，p->no，(*p).no線(xiàn)性表2．1線(xiàn)性表的定義1．線(xiàn)性表的表達(dá)形式：

L=（a1，a2，a3，…，an）2．線(xiàn)性表的基本操作每種操作都采用一種函數(shù)來(lái)完畢，這些函數(shù)是自定義函數(shù)，使用之前必須先定義。2．2線(xiàn)性表的次序存儲(chǔ)構(gòu)造一、次序表的類(lèi)型定義次序表實(shí)際是一種構(gòu)造變量，涉及兩個(gè)域：datas：寄存線(xiàn)性表的元素，last：寄存線(xiàn)性表的長(zhǎng)度。typedefstruct{類(lèi)型datas[maxsize];intlast;}sequenlist;sequenlistL;二、為線(xiàn)性表L=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種次序表，規(guī)定L的第1個(gè)元素存入數(shù)組的1號(hào)元素中。typedefstruct{chardatas[20];intlast;}sequenlist;voidmain(){sequenlistL;charch;inti=1;ch=getchar();while(ch!='\n'){L.datas[i]=ch;i++; ch=getchar();}L.last=i-1;for(i=1;i<=L.last;i++) printf("%4c",L.datas[i]);printf("\n");}三、基本操作在次序表上的實(shí)現(xiàn)1．insert(a,x,i)：將元素x插入到次序表a的第i號(hào)元素之前2．delete(a,i)：刪除次序表a的第i號(hào)元素第3章鏈?zhǔn)酱鎯?chǔ)構(gòu)造3．1線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造一、次序表的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：空間運(yùn)用率高，能夠隨機(jī)讀取表中任一元素。缺點(diǎn)：插入、刪除操作要移動(dòng)大量的數(shù)據(jù)，時(shí)間性能差。二、單鏈表1．單鏈表的構(gòu)成每個(gè)單鏈表由多個(gè)結(jié)點(diǎn)構(gòu)成，每個(gè)結(jié)點(diǎn)包含兩個(gè)域：數(shù)據(jù)域data：寄存線(xiàn)性表的元素指針域next：寄存下一種結(jié)點(diǎn)的地址2．單鏈表的類(lèi)型定義typedefstructnode{類(lèi)型data;structnode*next;}linklist;linklist*head;闡明：不帶頭結(jié)點(diǎn)的單鏈表為空的條件：head==null帶頭結(jié)點(diǎn)的單鏈表為空的條件：head->next==null3．單鏈表的建立（尾插入法）例：為L(zhǎng)=（'a'，'b'，'c'，'d'，……）創(chuàng)立單鏈表。#include"malloc.h"#include"stdio.h"typedefstructnode{chardata;structnode*next;}linklist;voidmain(){charch;//定義三根指針，head指向頭結(jié)點(diǎn)，t指向新產(chǎn)生的結(jié)點(diǎn)，last指向最后的結(jié)點(diǎn)linklist*head,*t,*last;t=malloc(sizeof(linklist));t->next=NULL;head=t;last=t;ch=getchar();while(ch!='\n'){t=malloc(sizeof(linklist));t->data=ch; t->next=NULL; last->next=t; last=t; ch=getchar();}}4．單鏈表的插入需設(shè)立兩支指針：p、t。p：指向待插入結(jié)點(diǎn)的前一種結(jié)點(diǎn)t：指向新產(chǎn)生的結(jié)點(diǎn)5．單鏈表的刪除需設(shè)立兩支指針：p、t。p：指向待刪除結(jié)點(diǎn)的前一種結(jié)點(diǎn)t：指向待刪除結(jié)點(diǎn)三、其它鏈表單鏈表單向循環(huán)鏈表（循環(huán)鏈表）雙向循環(huán)鏈表（雙向鏈表）循環(huán)鏈表最后一種結(jié)點(diǎn)的指針域不是NULL，而是指向頭結(jié)點(diǎn)。雙鏈表每個(gè)結(jié)點(diǎn)包含三個(gè)域：一種數(shù)據(jù)域和兩個(gè)指針域。雙鏈表的特點(diǎn)是找結(jié)點(diǎn)的前趨和后繼都很容易。第4章棧和隊(duì)列4．1棧一、棧的定義1．基本概念棧頂、棧底、進(jìn)棧、出棧、空棧2．棧的表達(dá)形式S=（a1，a2，a3，…，an）按a1，a2，a3，…，an次序進(jìn)棧，但按an，…，a3，a2，a1次序出棧。a1稱(chēng)為棧底元素，an稱(chēng)為棧頂元素。棧又稱(chēng)后進(jìn)先出線(xiàn)性表（LIFO）表。二、棧的次序存儲(chǔ)構(gòu)造1．次序棧的類(lèi)型定義次序棧事實(shí)上是一種構(gòu)造變量，涉及兩個(gè)域：data：寄存棧中元素，top：寄存棧頂元素所在單元的編號(hào)。typedefstruct{類(lèi)型data[maxsize];inttop;}seqstack;seqstacks;?？諚l件：s.top=0；棧滿(mǎn)條件：s.top=maxsize-12．為S=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種次序棧，規(guī)定S的第1個(gè)元素存入數(shù)組的1號(hào)元素中。typedefstruct{chardata[20];inttop;}seqstack;voidmain(){seqstacks;charch;inti=1;ch=getchar();while(ch!='\n'){s.data[i]=ch;i++; ch=getchar();}s.top=i-1;for(i=1;i<=S.top;i++) printf("%-4c",s.data[i]);printf("\n");}三、棧的鏈?zhǔn)酱鎯?chǔ)構(gòu)造1．鏈棧的類(lèi)型定義typedefstructnode{類(lèi)型data;structnode*next;}linkstack;linkstack*top;注意：=1\*GB3①鏈棧總是以棧頂指針top開(kāi)頭，top用于標(biāo)記整個(gè)鏈棧。=2\*GB3②鏈棧只會(huì)出現(xiàn)?？諣顩r，?？諚l件為:top==NULL。2．鏈棧的建立（頭插入法）例：為S=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種鏈棧。#include"malloc.h"#include"stdio.h"typedefstructnode{chardata;structnode*next;}linkstack;voidmain(){linkstack*top,*t;charch;top=NULL;ch=getchar();while(ch!='\n'){t=malloc(sizeof(linkstack));t->data=ch; t->next=top; top=t;ch=getchar();}printf("出棧次序?yàn)?\n");while(top->next!=NULL){printf("%-4c",top->data);top=top->next;}printf("\n");}4．2隊(duì)列一、隊(duì)列的定義1．基本概念隊(duì)頭、隊(duì)尾、空隊(duì)2．隊(duì)列的表達(dá)形式：Q=（a1，a2，a3，…，an）按a1，a2，a3，…，an次序進(jìn)隊(duì)，仍按a1，a2，a3，…，an次序出隊(duì)。隊(duì)列又稱(chēng)先進(jìn)先出線(xiàn)性表（FIFO表）二、隊(duì)列的次序存儲(chǔ)構(gòu)造1．次序隊(duì)的類(lèi)型定義次序隊(duì)事實(shí)上是一種構(gòu)造變量，涉及三個(gè)域：data：寄存隊(duì)列的元素；front：寄存隊(duì)頭元素所在單元的前一種單元的編號(hào)；rear：寄存隊(duì)尾元素所在單元的編號(hào)。typedefstruct{類(lèi)型data[maxsize];intfront,rear;}seqqueue;seqqueueq;2．次序隊(duì)的建立例：為Q=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種次序隊(duì)。typedefstruct{chardata[20];intfront,rear;}seqqueue;voidmain(){seqqueueq;charch;inti=0;ch=getchar();while(ch!='\n'){q.data[i]=ch;i++; ch=getchar();}q.front=-1;q.rear=i-1;//輸出隊(duì)列元素for(i=0;i<=q.rear;i++) printf("%-4c",q.data[i]);printf("\n");}次序隊(duì)的隊(duì)空、隊(duì)滿(mǎn)=1\*GB3①隊(duì)空條件：q.front=q.rear=2\*GB3②隊(duì)滿(mǎn)條件：q.rear=maxsize-1隊(duì)真滿(mǎn)：q.front＝-1;q.rear＝maxsize-1隊(duì)假滿(mǎn)：q.front≠-1;q.rear＝maxsize-14．次序隊(duì)的插入、刪除操作=1\*GB3①插入新元素：rear后移而front不變q.rear=q.rear+1;q.data[q.rear]=x;=2\*GB3②刪除元素：front后移而rear不變q.front=q.front+1;三、循環(huán)隊(duì)1．為充足運(yùn)用存儲(chǔ)空間，克服“假滿(mǎn)”，能夠把數(shù)組看作首尾相接的圓環(huán)，形成“循環(huán)隊(duì)”。2．循環(huán)隊(duì)的性質(zhì)=1\*GB3①存儲(chǔ)單元的編號(hào)從0開(kāi)始，按順時(shí)針?lè)较颍幪?hào)逐步增大，最后一種存儲(chǔ)單元的編號(hào)為maxsize-1。=2\*GB3②在循環(huán)隊(duì)中，當(dāng)q.rear=maxsize-1時(shí)，只要數(shù)組有兩個(gè)以上的存儲(chǔ)單元為空，就能夠把新元素插入到空單元中。=3\*GB3③當(dāng)隊(duì)列中元素的個(gè)數(shù)為maxsize-1時(shí)，就認(rèn)為隊(duì)滿(mǎn)。3．循環(huán)隊(duì)的插入、刪除操作=1\*GB3①插入新元素：rear順時(shí)針移動(dòng)而front不變q.rear=(q.rear+1)%maxsize;q.data[q.rear]=x;=2\*GB3②刪除元素：front順時(shí)針移動(dòng)而rear不變q.front=(q.front+1)%maxsize;4．循環(huán)隊(duì)的隊(duì)空、隊(duì)滿(mǎn)隊(duì)空條件：q.front=q.rear隊(duì)滿(mǎn)條件：(q.rear+1)%maxsize=q.front四、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)構(gòu)造1．鏈隊(duì)的類(lèi)型定義=1\*GB3①鏈隊(duì)是一種含有隊(duì)頭指針front和隊(duì)尾指針rear的單鏈表；②front指向隊(duì)頭結(jié)點(diǎn)的前一種結(jié)點(diǎn)，rear指向隊(duì)尾結(jié)點(diǎn)；=3\*GB3③鏈隊(duì)由包含front和rear的構(gòu)造變量lq標(biāo)記。typedefstructnode_st{類(lèi)型data;structnode_st*next;}node;typedefstruct{node*front;node*rear;}linkqueue; linkqueuelq;2．鏈隊(duì)的建立（尾插入法）例：為Q=（'a'，'b'，'c'，'d'，……）創(chuàng)立一種鏈隊(duì)。#include"malloc.h"#include"stdio.h"typedefstructnode_st{chardata;structnode_st*next;}node;typedefstruct{node*front;node*rear;}linkqueue; voidmain(){charch;linkqueuelq;node*p;p=malloc(sizeof(node));p->next=NULL;lq.front=p;lq.rear=p;ch=getchar();while(ch!='\n'){p=malloc(sizeof(node));p->data=ch; p->next=NULL; lq.rear->next=p; lq.rear=p; ch=getchar();}//輸出隊(duì)列中的元素p=lq.front->next;while(p!=NULL){printf("%-4c",p->data);p=p->next;}printf("\n");}3．鏈隊(duì)的隊(duì)空條件lq.front=lq.rear各式鏈?zhǔn)酱鎯?chǔ)構(gòu)造比較表有無(wú)頭結(jié)點(diǎn)用何指針標(biāo)記創(chuàng)立方法鏈表有頭指針head尾插入法鏈棧無(wú)棧頂指針top頭插入法鏈隊(duì)有由包含front和rear的構(gòu)造變量lq標(biāo)記。尾插入法第6章樹(shù)和二叉樹(shù)6．1樹(shù)的定義和基本操作一、樹(shù)型構(gòu)造和線(xiàn)性構(gòu)造樹(shù)型構(gòu)造：每個(gè)結(jié)點(diǎn)能夠有多個(gè)直接后繼線(xiàn)性構(gòu)造：每個(gè)結(jié)點(diǎn)只有一種直接后繼二、樹(shù)的定義樹(shù)是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，任意一棵非空樹(shù)滿(mǎn)足：=1\*GB3①有且只有一種根結(jié)點(diǎn)；=2\*GB3②其它結(jié)點(diǎn)被分成若干個(gè)互不相交的集合，每個(gè)集合又是一棵樹(shù)。三、樹(shù)的特點(diǎn)=1\*GB3①除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且只有一種直接前趨；=2\*GB3②除最底層的結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)能夠有多個(gè)直接后繼；=3\*GB3③若某棵樹(shù)有多個(gè)結(jié)點(diǎn)，則每個(gè)結(jié)點(diǎn)能夠看作根結(jié)點(diǎn)，要么是整棵樹(shù)的根結(jié)點(diǎn)，要么是某棵子樹(shù)的根結(jié)點(diǎn)。四、基本術(shù)語(yǔ)=1\*GB3①結(jié)點(diǎn)的度、樹(shù)的度=2\*GB3②葉子結(jié)點(diǎn)、分支結(jié)點(diǎn)度為0的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)；度不不大于0的結(jié)點(diǎn)稱(chēng)為分支結(jié)點(diǎn)。=3\*GB3③孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)含有同一雙親的結(jié)點(diǎn)互為兄弟=4\*GB3④結(jié)點(diǎn)的子孫、結(jié)點(diǎn)的祖先=5\*GB3⑤結(jié)點(diǎn)的層數(shù)、樹(shù)的高度結(jié)點(diǎn)的層數(shù)：從樹(shù)根開(kāi)始算起，根的層數(shù)為1；樹(shù)的高度：樹(shù)中全部結(jié)點(diǎn)層數(shù)的最大值。6．2二叉樹(shù)一、二叉樹(shù)的定義：參考P73二、二叉樹(shù)的性質(zhì)（1）二叉樹(shù)的第i層上最多有個(gè)結(jié)點(diǎn)。（2）深度為k的二叉樹(shù)最多有個(gè)結(jié)點(diǎn)。（3）滿(mǎn)二叉樹(shù)：除最底層的結(jié)點(diǎn)外，其它結(jié)點(diǎn)的度均為2的二叉樹(shù)。（4）完全二叉樹(shù)：如果對(duì)一棵滿(mǎn)二叉樹(shù)的最底層從最右邊開(kāi)始，持續(xù)刪去若干個(gè)結(jié)點(diǎn)，就得到完全二叉樹(shù)。（5）對(duì)一棵完全二叉樹(shù)的結(jié)點(diǎn)進(jìn)行編號(hào)，則對(duì)編號(hào)為i的結(jié)點(diǎn)，其左孩子的編號(hào)為2i，右孩子的編號(hào)為2i+1，雙親結(jié)點(diǎn)的編號(hào)為三、二叉樹(shù)的存儲(chǔ)構(gòu)造1．次序存儲(chǔ)構(gòu)造：◆先將二叉樹(shù)的結(jié)點(diǎn)依次編號(hào)，再將結(jié)點(diǎn)存入一維數(shù)組中，數(shù)組元素的序號(hào)對(duì)應(yīng)結(jié)點(diǎn)的編號(hào)。◆對(duì)二叉樹(shù)的結(jié)點(diǎn)進(jìn)行編號(hào)，編號(hào)原則是：=1\*GB3①根結(jié)點(diǎn)的編號(hào)為1。=2\*GB3②對(duì)于編號(hào)為i的結(jié)點(diǎn)，其左孩子的編號(hào)為2i，右孩子的編號(hào)為2i+1。滿(mǎn)二叉樹(shù)、完全二叉樹(shù)普通采用次序存儲(chǔ)構(gòu)造，普通二叉樹(shù)則采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造。2．鏈?zhǔn)酱鎯?chǔ)構(gòu)造：=1\*GB3①二叉鏈表：每個(gè)結(jié)點(diǎn)涉及三個(gè)域：數(shù)據(jù)域data，左指針域lchild，右指針域rchild=2\*GB3②對(duì)二叉樹(shù)的訪(fǎng)問(wèn)只能從根指針root開(kāi)始，二叉樹(shù)為空的條件：root=NULL。四、二叉樹(shù)的遍歷1．什么叫二叉樹(shù)的遍歷？按照一定規(guī)律訪(fǎng)問(wèn)二叉樹(shù)的全部結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪(fǎng)問(wèn)一次且僅被訪(fǎng)問(wèn)一次。2．二叉樹(shù)由三部分構(gòu)成：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)3．三種遍歷次序=1\*GB3①先根遍歷：根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)=2\*GB3②中根遍歷：左子樹(shù)、根結(jié)點(diǎn)、右子樹(shù)=3\*GB3③后根遍歷：左子樹(shù)、右子樹(shù)、根結(jié)點(diǎn)6．3樹(shù)和森林一、對(duì)樹(shù)中各結(jié)點(diǎn)編號(hào)從根結(jié)點(diǎn)開(kāi)始，按層依次編號(hào)，且根結(jié)點(diǎn)的編號(hào)為0。二、樹(shù)的存儲(chǔ)構(gòu)造雙親鏈表孩子鏈表孩子兄弟鏈表1．雙親鏈表（1）每個(gè)結(jié)點(diǎn)包含兩個(gè)域名：數(shù)據(jù)域：寄存該結(jié)點(diǎn)的數(shù)據(jù)元素指針域：寄存該結(jié)點(diǎn)之雙親的編號(hào)（2）將全部結(jié)點(diǎn)組織成一維數(shù)組，并以各結(jié)點(diǎn)的編號(hào)作為數(shù)組元素的序號(hào)。2．孩子鏈表（1）為每個(gè)結(jié)點(diǎn)建立一種“孩子鏈表”。（2）結(jié)點(diǎn)x的孩子鏈表是一種帶頭結(jié)點(diǎn)的單鏈表，用于存儲(chǔ)該結(jié)點(diǎn)的全部孩子的編號(hào)。（3）將全部頭結(jié)點(diǎn)組織成一維數(shù)組。3．孩子兄弟鏈表（1）每個(gè)結(jié)點(diǎn)含有三個(gè)域：數(shù)據(jù)域：寄存該結(jié)點(diǎn)的數(shù)據(jù)元素孩子域：用于指向該結(jié)點(diǎn)的第一種孩子兄弟域：用于指向該結(jié)點(diǎn)的第一種兄弟（2）二叉樹(shù)的二叉鏈表與樹(shù)的孩子兄弟鏈表在組織構(gòu)造完全相似。二叉鏈表孩子兄弟鏈表數(shù)據(jù)域數(shù)據(jù)域左指針域孩子域右指針域兄弟域三、樹(shù)與二叉樹(shù)的轉(zhuǎn)換1．樹(shù)轉(zhuǎn)換為二叉樹(shù)=1\*GB3①將樹(shù)轉(zhuǎn)換為二叉樹(shù)，只要將樹(shù)中各結(jié)點(diǎn)的第一種孩子看作左孩子，第一種兄弟看作右孩子即可。=2\*GB3②任一棵樹(shù)對(duì)應(yīng)的二叉樹(shù)的右子樹(shù)必空。2．森林轉(zhuǎn)換為二叉樹(shù)=1\*GB3①將每棵樹(shù)先轉(zhuǎn)換為二叉樹(shù)B1，B2，…，Bn=2\*GB3②以B1為基準(zhǔn)，將B2作為B1根結(jié)點(diǎn)的右子樹(shù)，將B3作為B2根結(jié)點(diǎn)的右子樹(shù)，…3．二叉樹(shù)轉(zhuǎn)換為森林=1\*GB3①將二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)撤去，得到多棵二叉樹(shù)B1，B2，…，Bn=2\*GB3②將二叉樹(shù)分別轉(zhuǎn)換為樹(shù)T1，T2，…，Tn。四、樹(shù)的遍歷先根遍歷：根結(jié)點(diǎn)、各棵子樹(shù)后根遍歷：各棵子樹(shù)、根結(jié)點(diǎn)層次遍歷6．4哈夫曼樹(shù)和鑒定樹(shù)一、基本術(shù)語(yǔ)1．葉子結(jié)點(diǎn)的途徑長(zhǎng)度：從根結(jié)點(diǎn)到某個(gè)葉子結(jié)點(diǎn)所通過(guò)的分支數(shù)。2．樹(shù)的途徑長(zhǎng)度：樹(shù)中各葉子結(jié)點(diǎn)的途徑長(zhǎng)度之和。3．葉子結(jié)點(diǎn)的權(quán)：各葉子結(jié)點(diǎn)出現(xiàn)的概率。4．帶權(quán)途徑長(zhǎng)度（WPL）各個(gè)葉子結(jié)點(diǎn)的權(quán)wi與對(duì)應(yīng)的途徑長(zhǎng)度li乘積之和，稱(chēng)為樹(shù)的帶權(quán)途徑長(zhǎng)度。二、哈夫曼樹(shù)1．什么叫哈夫曼樹(shù)？帶權(quán)途徑長(zhǎng)度WPL最小的二叉樹(shù)，稱(chēng)為哈夫曼樹(shù)。特點(diǎn)：=1\*GB3①普通地說(shuō)，權(quán)值越大的葉子結(jié)點(diǎn)離根越近。=2\*GB3②哈夫曼樹(shù)的時(shí)間性能最佳，是最優(yōu)的二叉樹(shù)。=3\*GB3③哈夫曼樹(shù)中各結(jié)點(diǎn)的度只能是0或2。=4\*GB3④含有n個(gè)結(jié)點(diǎn)的哈夫曼樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。2．如何構(gòu)造一棵哈夫曼樹(shù)？（參考P88）3．哈夫曼編碼對(duì)一棵哈夫曼樹(shù)商定：指向左孩子的分支表達(dá)為0，指向右孩子的分支表達(dá)為1。取從根到葉子結(jié)點(diǎn)一路上的“0”或“1”構(gòu)成的序列，稱(chēng)為葉子結(jié)點(diǎn)的三、分類(lèi)和鑒定樹(shù)1．用于描述分類(lèi)問(wèn)題的二叉樹(shù)稱(chēng)為鑒定樹(shù)。鑒定樹(shù)的每個(gè)分支結(jié)點(diǎn)對(duì)應(yīng)一種判斷，每個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)一種分類(lèi)成果。2．一種分類(lèi)問(wèn)題對(duì)應(yīng)著若干棵鑒定樹(shù)，其中必有一棵鑒定樹(shù)的WPL最小，WPL又稱(chēng)平均比較次數(shù)。3．一棵鑒定樹(shù)對(duì)應(yīng)著一種算法，哈夫曼樹(shù)對(duì)應(yīng)的算法的時(shí)間性能最佳。4．如何對(duì)一種分類(lèi)問(wèn)題寫(xiě)最優(yōu)的算法？①對(duì)分類(lèi)成果畫(huà)哈夫曼樹(shù)；②根據(jù)哈夫曼樹(shù)寫(xiě)算法；第7章圖7．1圖的定義和術(shù)語(yǔ)一、圖的定義圖G由頂點(diǎn)集V和邊集E構(gòu)成，記為G=（V，E）。=1\*GB3①最簡(jiǎn)樸的圖只有一種頂點(diǎn)；=2\*GB3②每條邊由其連接的兩個(gè)頂點(diǎn)表達(dá)：例：無(wú)向邊（v1，v2）；有向邊<v1，v2>，<v2，v1>二、術(shù)語(yǔ)1．鄰接點(diǎn)若頂點(diǎn)vi，vj存在一條邊，則vi，vj互為鄰接點(diǎn)。在有向邊<vi，vj>中，稱(chēng)vi為起點(diǎn)，vj為終點(diǎn)。2．頂點(diǎn)的入邊，出邊若存在一條有向邊<vi，vj>，則稱(chēng)它為vi的出邊，vj的入邊。3．頂點(diǎn)的入度，出度=1\*GB3①頂點(diǎn)的度：與頂點(diǎn)v有關(guān)聯(lián)的邊數(shù)，記為D（v）；=2\*GB3②頂點(diǎn)的入度，出度：在有向圖中，頂點(diǎn)v的入邊的數(shù)目，稱(chēng)為入度，記為ID（v）；頂點(diǎn)v的出邊的數(shù)目，稱(chēng)為出度，記為OD（v）；D（v）=ID（v）+OD（v）4．無(wú)向完全圖，有向完全圖無(wú)向完全圖：任意兩個(gè)頂點(diǎn)之間都存在一條邊的無(wú)向圖；有向完全圖：任意兩個(gè)頂點(diǎn)之間都存在方向相反的兩條邊的有向圖；子圖設(shè)有兩個(gè)圖G=（V，E）和G′=（V′，E′），若V′是V的子集，E′是E的子集，則G′是G的子圖。連通圖和連通分量連通：在無(wú)向圖中，若兩個(gè)頂點(diǎn)有途徑，則稱(chēng)兩頂點(diǎn)是連通的；連通圖：任意兩個(gè)頂點(diǎn)都連通的無(wú)向圖；連通分量：無(wú)向圖中的極大連通子圖。強(qiáng)連通圖和強(qiáng)連通分量強(qiáng)連通：在有向圖中，若vi到vj，vj到vi都有途徑，則稱(chēng)vi，vj是強(qiáng)連通的；強(qiáng)連通圖：任意兩個(gè)頂點(diǎn)都強(qiáng)連通的有向圖；強(qiáng)連通分量：有向圖中的極大連通子圖。8．帶權(quán)圖：又稱(chēng)網(wǎng)帶權(quán)有向圖（有向網(wǎng)）帶權(quán)無(wú)向圖（無(wú)向網(wǎng)）7．2圖的存儲(chǔ)構(gòu)造一、鄰接矩陣1．鄰接矩陣的構(gòu)建=1\*GB3①將各個(gè)頂點(diǎn)排成一行和一列，形成矩陣。=2\*GB3②若行、列頂點(diǎn)之間存在一條邊，則對(duì)應(yīng)元素記1，否則，對(duì)應(yīng)元素記0。2．鄰接矩陣的特點(diǎn)無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，有向圖的鄰接矩陣普通不對(duì)稱(chēng)。3．用鄰接矩陣表達(dá)加權(quán)圖只要把1元素?fù)Q成對(duì)應(yīng)邊的權(quán)值，0元素?fù)Q成∞即可。鄰接矩陣的用途便于查找每個(gè)頂點(diǎn)的度、入度、出度。無(wú)向圖：每個(gè)頂點(diǎn)的度等于該頂點(diǎn)對(duì)應(yīng)的行或列中1元素的個(gè)數(shù)。有向圖：每個(gè)頂點(diǎn)的出度等于該頂點(diǎn)對(duì)應(yīng)行中1元素的個(gè)數(shù)，入度等于對(duì)應(yīng)列中1元素的個(gè)數(shù)。二、鄰接鏈表樹(shù)的孩子鏈表、圖的鄰接鏈表組織構(gòu)造相似。1．鄰接鏈表的構(gòu)建=1\*GB3①為每個(gè)頂點(diǎn)建立一種鄰接鏈表，一種圖有幾個(gè)頂點(diǎn)，就有幾個(gè)鄰接鏈表。=2\*GB3②頂點(diǎn)x的鄰接鏈表是一種帶頭結(jié)點(diǎn)的單鏈表，用于存儲(chǔ)與x相鄰接的頂點(diǎn)序號(hào)。=3\*GB3③將全部頭結(jié)點(diǎn)組織成一維數(shù)組。2．鄰接鏈表的用途便于求頂點(diǎn)的度、出度。無(wú)向圖：每個(gè)頂點(diǎn)的度等于它的鄰接鏈表中表結(jié)點(diǎn)的個(gè)數(shù)。有向圖：每個(gè)頂點(diǎn)的出度等于它的鄰接鏈表中表結(jié)點(diǎn)的個(gè)數(shù)。3．如何求頂點(diǎn)的入度？構(gòu)造一種逆鄰接鏈表，即頂點(diǎn)x的逆鄰接鏈表存儲(chǔ)的是與x的入邊有關(guān)聯(lián)的頂點(diǎn)序號(hào)。注：一種圖的鄰接矩陣是唯一的，但鄰接表普通不唯一。7．3圖的遍歷1．樹(shù)的遍歷先根遍歷：根結(jié)點(diǎn)、各棵子樹(shù)后根遍歷：各棵子樹(shù)、根結(jié)點(diǎn)層次遍歷2．圖的遍歷：適應(yīng)于無(wú)向圖，也適應(yīng)于有向圖。深度優(yōu)先搜索遍歷：類(lèi)似樹(shù)的先根遍歷。廣度優(yōu)先搜索遍歷：類(lèi)似樹(shù)的層次遍歷3．深度優(yōu)先搜索遍歷：首先訪(fǎng)問(wèn)出發(fā)點(diǎn)Vi，然后任選一種Vi的未訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)Vj，以Vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索。深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列不唯一。7．4圖的應(yīng)用一、最小生成樹(shù)1．什么叫生成樹(shù)？從n個(gè)頂點(diǎn)的連通圖G中，取它的全部頂點(diǎn)和n-1條邊構(gòu)成子圖G′，如果這些邊剛好將G′的全部頂點(diǎn)連通但又不形成回路，則稱(chēng)子圖G′是G的一棵生成樹(shù)。注意：=1\*GB3①一種連通圖能夠有多棵生成樹(shù)。=2\*GB3②生成樹(shù)是邊數(shù)極少的連通子圖。=3\*GB3③連通分量：指極大連通子圖。=4\*GB3④根據(jù)圖的寬度優(yōu)先遍歷或深度優(yōu)先遍歷可構(gòu)造生成樹(shù)。2．最小生成樹(shù)①生成樹(shù)的權(quán)：各條邊權(quán)值之和權(quán)值最小的生成樹(shù)，稱(chēng)為最小生成樹(shù)。=2\*GB3②帶權(quán)無(wú)向圖才可構(gòu)造最小生成樹(shù)。求造價(jià)最低的通訊網(wǎng)問(wèn)題，實(shí)際是求最小生成樹(shù)問(wèn)題。3．構(gòu)造最小生成樹(shù)的算法：Prim（普里姆）算法二、拓?fù)渑判?．拓?fù)湫蛄性谟邢驁D中，若不存在回路，則全部頂點(diǎn)可排成一種線(xiàn)性序列，方便列出各頂點(diǎn)的前后關(guān)系，稱(chēng)此序列為拓?fù)湫蛄小?．拓?fù)渑判颍簩?shí)現(xiàn)有向圖的一種拓?fù)湫蛄械倪^(guò)程。任何一種有向無(wú)環(huán)圖，其全部頂點(diǎn)能夠排成一種拓?fù)湫蛄?，且其拓?fù)湫蛄胁晃ㄒ?。若圖中入度為0的頂點(diǎn)和出度為0的頂點(diǎn)都是唯一的，則其拓?fù)湫蛄惺俏ㄒ坏摹?．構(gòu)成有向圖拓?fù)湫蛄械倪^(guò)程=1\*GB3①?gòu)膱D中選擇一種入度為0的頂點(diǎn)，輸出該頂點(diǎn)。=2\*GB3②從圖中刪除該頂點(diǎn)及其有關(guān)聯(lián)的全部邊。=3\*GB3③重復(fù)執(zhí)行1，2，直到找不到入度為0的頂點(diǎn)。三、最短途徑1．最短途徑問(wèn)題=1\*GB3①帶權(quán)有向圖才存在最短途徑問(wèn)題。=2\*GB3②圖的途徑長(zhǎng)度：一條途徑上各條邊的權(quán)值之和。2．求一種源點(diǎn)到其它各個(gè)頂點(diǎn)的最短途徑：Dijkstra迪杰斯特拉）算法從源點(diǎn)到其它各個(gè)頂點(diǎn)的最短途徑中，先求最短的一條，再求次短的一條，以此次序，最后求最長(zhǎng)的一條。3．Dijkstra算法描述=1\*GB3①假設(shè)S為頂點(diǎn)集合，初值為源點(diǎn)v0。=2\*GB3②首先從v0出發(fā)的全部邊中找出權(quán)值最小的邊的終點(diǎn)加入到S中。=3\*GB3③下一條最短途徑是終點(diǎn)不在S中，中間只通過(guò)S中的頂點(diǎn)且途徑長(zhǎng)度最短，找到后將終點(diǎn)加入到S中。=4\*GB3④重復(fù)執(zhí)行（3），直到全部頂點(diǎn)都加入到S中。例：根據(jù)P115圖7.17，求頂點(diǎn)V1到其它各頂點(diǎn)的最短途徑。終點(diǎn)V2V3V4V5集合S第1次10∞30100{V1，V2}第2次106030100{V1，V2，V4}第3次10503090{V1，V2，V4，V3}第4次10503060{V1，V2，V4，V3，V5}V1到各頂點(diǎn)的最短途徑是：V1→V2：（V1，V2）V1→V4：（V1，V4）V1→V3：（V1，V4，V3）V1→V5：（V1，V4，V3，V5）第8章查找8．1基本概念一、多個(gè)數(shù)據(jù)的邏輯構(gòu)造數(shù)據(jù)邏輯構(gòu)造特點(diǎn)線(xiàn)性表線(xiàn)性構(gòu)造數(shù)據(jù)元素之間存在著一對(duì)一的邏輯關(guān)系。樹(shù)樹(shù)型構(gòu)造數(shù)據(jù)元素之間存在著一對(duì)多的邏輯關(guān)系。圖圖狀構(gòu)造數(shù)據(jù)元素之間存在著多對(duì)多的邏輯關(guān)系。查找表集合數(shù)據(jù)元素之間不存在任何關(guān)系。二、查找表1．定義：查找表是一種以集合為邏輯構(gòu)造，以查找為核心運(yùn)算的數(shù)據(jù)構(gòu)造。例：一種平面表格，當(dāng)各條統(tǒng)計(jì)能夠任意排列時(shí)，就成為查找表。2．核心字：由一種或多個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，可標(biāo)記若干條統(tǒng)計(jì)；主鍵：由一種或多個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，能唯一標(biāo)記一條統(tǒng)計(jì)。3．查找：在查找表中尋找核心字值等于給定值的統(tǒng)計(jì)，若找到，則返回統(tǒng)計(jì)號(hào)；否則，則查找失敗。4．靜態(tài)查找表和動(dòng)態(tài)查找表靜態(tài)查找表：只做建表、查找操作；動(dòng)態(tài)查找表：做建表、查找、插入、刪除操作。8．2靜態(tài)查找表◆靜態(tài)查找表的存儲(chǔ)構(gòu)造：次序表、有序表、索引次序表次序表上的查找次序表的類(lèi)型定義typedefstruct{intkey;類(lèi)型data;...}