(補(bǔ)充)數(shù)據(jù)結(jié)構(gòu)與算法

1、數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu) S 和 S 上的一個(gè)基本運(yùn)算集構(gòu)成的整體( S ，)。數(shù)據(jù)結(jié)構(gòu)的基本任務(wù)：數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)。數(shù)據(jù)的形式有很多種：    數(shù)據(jù)的邏輯結(jié)構(gòu)分為 4 種基本類型： 集合：集合中任何兩個(gè)數(shù)據(jù)元素之間都沒有邏輯關(guān)系，組織形式松散。 線性結(jié)構(gòu)：線性結(jié)構(gòu)中的結(jié)點(diǎn)按邏輯關(guān)系依次排列形成一個(gè)“鎖鏈”。 樹形結(jié)構(gòu)：樹形結(jié)構(gòu)具有分支、層次特性，其形態(tài)有點(diǎn)象自然界中的樹。 圖狀結(jié)構(gòu)：圖狀結(jié)構(gòu)中的結(jié)點(diǎn)按邏輯關(guān)系互相纏繞，任何兩個(gè)結(jié)點(diǎn)都可以鄰接。運(yùn)算：是指在任何邏輯結(jié)構(gòu)上施加的操作，即對(duì)邏輯結(jié)構(gòu)的加工。根據(jù)操作的效果，可將運(yùn)算分成以下兩種基本類型： 加

2、工型運(yùn)算 其操作改變了原邏輯結(jié)構(gòu)的“值”，如結(jié)點(diǎn)個(gè)數(shù)、某些結(jié)點(diǎn)的內(nèi)容等；如：初始化、插入、刪除、更新等操作。 引用型運(yùn)算 其操作不改變?cè)壿嫿Y(jié)構(gòu)的“值”，只從中提取某些信息作為運(yùn)算的結(jié)果。如：查找、讀取等操作。算法：算法就是解決問題的方法和步驟，可以用語言來描述。根據(jù)描述算法語言的不同，將算法分為三類：運(yùn)行終止的程序可執(zhí)行部分、偽語言算法和非形式算法。非形式算法：用自然語言(如漢語)，同時(shí)可能還使用了程序設(shè)計(jì)語言或偽程序設(shè)計(jì)語言描述的算法稱為非形式算法。算法與程序的關(guān)系：算法和程序都是用來表達(dá)解決問題的邏輯步驟，但算法獨(dú)立于具體的計(jì)算機(jī)，與具體的程序設(shè)計(jì)語言無關(guān)，而程序正好相反；程序是算法，但

3、算法不一定是程序。算法分析通常從以下幾個(gè)方面評(píng)價(jià)算法(包括程序)的質(zhì)量： 正確性 算法應(yīng)能正確地實(shí)現(xiàn)預(yù)定的功能(即處理要求)。 易讀性 算法應(yīng)易于閱讀和理解，以便于調(diào)試、修改和擴(kuò)充。 健壯性 當(dāng)環(huán)境發(fā)生變化(如遇到非法輸入)時(shí)，算法能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生不需要的運(yùn)行結(jié)果。 高效性 即達(dá)到所需要的時(shí)空性能。一個(gè)算法的時(shí)空性能是指該算法的時(shí)間性能(或時(shí)間效率)和空間性能(或空間效率)。 最壞情況時(shí)間復(fù)雜性和平均時(shí)間復(fù)雜性統(tǒng)稱為時(shí)間復(fù)雜性(或時(shí)間復(fù)雜度)，用 T ( n ) O ( f ( n )表示。其中 f ( n )是算法中頻度最大的那條語句頻度的數(shù)量級(jí)。例：求下列算法的時(shí)間復(fù)雜

4、度。(1)for (i=0; i<n; i+) x+;【解答】：時(shí)間復(fù)雜度為O(n)。(2)for (i=0; i<n; i+) for (j=0; j<=i; j+) x+;【解答】：時(shí)間復(fù)雜度為O(n2)。(3)i=1; while (i<n) i*=2;【解答】：時(shí)間復(fù)雜度為O(log2n)。/*設(shè)k次，則2k=n，所以k=log2n*/例：下列程序段的時(shí)間復(fù)雜性的量級(jí)為 。for ( i=1 ；i<=n；i+) for ( j=i ；j<n；j+) t=t +1 ；【分析】本題程序段中的執(zhí)行頻度最大的語句為雙循環(huán)體內(nèi)的 t=t+l ，它的執(zhí)行頻度為(

5、 n-1 ) + ( n-2 ) + +2+1=n ( n-1 ) / 2 ，則 時(shí)間復(fù)雜性的量級(jí)為 O ( n 2 )。【解答】： O ( n 2 )(4)（矩陣的乘積）【解答】：時(shí)間復(fù)雜度為O(n3)。常見時(shí)間復(fù)雜性的量級(jí)有：常數(shù)階 O ( 1 )(即算法的時(shí)間復(fù)雜性與輸入規(guī)模 n 無關(guān)或 n 恒為常數(shù))、對(duì)數(shù)階 O ( log 2 n )、線性階 O ( n )、平方階 O ( n 2 )和指數(shù)階 O ( 2 n )?？臻g復(fù)雜性：主要關(guān)心一個(gè)算法除輸入數(shù)據(jù)占用存儲(chǔ)空間之外的附加存儲(chǔ)空間的大小。（算法復(fù)雜度）線性表：線性表L是指n個(gè)元素a1，a2，an組成的有限序列。記作：L=( a1，a

6、2，an)。其中n>=0，稱為線性表的長(zhǎng)度，簡(jiǎn)稱表長(zhǎng)。當(dāng)n=0時(shí)線性表為空表，記作：L=（）。元素ai-1稱為ai的直接前趨，ai+1稱為ai的直接后繼。順序表：順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，是指在一個(gè)足夠大的連續(xù)的存儲(chǔ)空間里，將線性表中的元素按照邏輯上的次序依次進(jìn)行存儲(chǔ)。這樣得到的線性表稱為順序表。順序表的結(jié)構(gòu)如下圖所示：（P17）    其中數(shù)組datamaxlen用來存儲(chǔ)線性表中的各個(gè)元素，此外，設(shè)置一個(gè)變量listlen表示順序表中的元素個(gè)數(shù)（表長(zhǎng)）。順序表的類型定義如下：（P17）#define maxsize 100 /假設(shè)元素個(gè)數(shù)不超過100t

7、ypedef struct datatype datamaxsize; /順序表中元素的類型用datatype泛指  int last; /表長(zhǎng)sqlist;由上述定義不難發(fā)現(xiàn)，順序表具有這樣的特點(diǎn)：邏輯上相鄰的元素，其存儲(chǔ)地址也相鄰。順序表中基本運(yùn)算的實(shí)現(xiàn)1初始化順序表建立一個(gè)空的順序表L，只需將表長(zhǎng)置為0即可。void initiate(sqlist *L) L->last=0; 2求表長(zhǎng)即返回順序表L的last值。int length(sqlist L) return (L.last); 3按給定序號(hào)取元素序號(hào)為i的元素ai在數(shù)組中的下標(biāo)為i-1，若該元素存在，則返回相應(yīng)

8、的數(shù)組元素值。void get (sqlist L，int i, datatype *x) if（i<1 | i>L.listlen）error("該元素不存在");  else *x= L.datai-1;4查找（定位） locate(L,x)：依次將順序表L中的每個(gè)元素與給定的值x進(jìn)行比較。若找到則返回其序號(hào)（下標(biāo)+1），否則返回0。int locate (sqlist L, datatype x) int i;  for ( i=0; i<L.listlen; i+)  if (L.datai=x) return (i+

9、1);  return(0);5插入 insert(L,i,x)：算法思想如下：（1）首先要判斷能否進(jìn)行插入，即表是否為滿以及插入位置i是否合理。（2）如果可以進(jìn)行插入，需要執(zhí)行下列步驟： 為了給待插入元素x騰出一個(gè)空位，需要將aian往后移一位。 將x插入到第i個(gè)位置上。 插入后，順序表L的長(zhǎng)度last要加1。void insert (sqlist *L, datatype x, int i ) int j;  if (i<1 | i>L->last+1) error ("插入位置錯(cuò)誤");  else if (L->

10、 last =maxsize) error ("溢出");       else for (j=L-> last -1; j>=i-1; j-) /往后移動(dòng)元素              L->dataj+1=L->dataj;             &

11、#160;  L->datai-1=x; /插入x                L-> last +;  /修改表長(zhǎng)          算法分析：（P20）當(dāng)插入位置i=1，2n+1時(shí)，移動(dòng)元素的次數(shù)分別為n，n-1,1，0。因此平均移動(dòng)次數(shù)為：(0+1+n) / ( n+1) = n / 2，所以插入算法的時(shí)間復(fù)雜度為O(n)。6刪

12、除 delete (L,i)：void delete (sqlist *L, int i) int j；     if (L-> last <=0 | i>L-> last | i<=0) error("無法刪除");else for (j=i；j<=L-> last -1；j+)                L->dataj-1=L->da

13、taj；            L-> last -；    算法的時(shí)間復(fù)雜度為O(n)。單鏈表在順序表中插入和刪除元素時(shí)，需要做大量移動(dòng)元素的操作，比較浪費(fèi)時(shí)間。要想在插入和刪除時(shí)不需移動(dòng)元素，可以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，此時(shí)線性表中每個(gè)元素稱為一個(gè)結(jié)點(diǎn)，如下圖所示：   每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：數(shù)據(jù)域data，用于存儲(chǔ)元素的值。指針域next，用于存儲(chǔ)后繼結(jié)點(diǎn)的地址。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表稱為鏈表。本節(jié)介紹的鏈表，每個(gè)結(jié)點(diǎn)只有一個(gè)指

14、針域，稱為單鏈表。單鏈表的簡(jiǎn)單操作（1）靜態(tài)鏈表：用數(shù)組來存儲(chǔ)元素的值和地址。（2）動(dòng)態(tài)鏈表：根據(jù)實(shí)際需要，臨時(shí)動(dòng)態(tài)地分配存儲(chǔ)空間來存儲(chǔ)線性表中的元素。單鏈表的類型定義如下：typedef struct datatype data;     /存放元素值  struct node *next; /指示后繼結(jié)點(diǎn)的指針node;一個(gè)完整的單鏈表head如下圖所示：  其中，head稱為頭指針，第一個(gè)元素a1所在的結(jié)點(diǎn)稱為首結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。有時(shí)，為了使某些運(yùn)算更方便實(shí)現(xiàn)，在首結(jié)點(diǎn)之前增加了一個(gè)結(jié)點(diǎn)，稱為頭結(jié)點(diǎn)，并稱此時(shí)的鏈

15、表為帶頭結(jié)點(diǎn)的單鏈表。單鏈表中基本運(yùn)算的實(shí)現(xiàn)1建空表一個(gè)空的單鏈表只有一個(gè)頭結(jié)點(diǎn)，且后繼指針為空，如下圖所示：    void initiate (node *L) L= (node *) malloc (sizeof (node); /產(chǎn)生一個(gè)頭結(jié)點(diǎn)   L->next=NULL; /設(shè)置后繼指針為空2求單鏈表的長(zhǎng)度即求出單鏈表中元素的個(gè)數(shù)，用p指針依次指向每個(gè)元素結(jié)點(diǎn)并進(jìn)行計(jì)數(shù)，算法如下：int length (node *L) int n=0; node *p=L->next;   while (p!=NULL) n+; &#

16、160;  p=p->next;     return n ;3按給定序號(hào)取元素node *get (node *L, int i ) node *p=L->next; int j=0;  while ( j!=i && p!=NULL ) p=p->next;    j+;     return p;4查找（定位）將單鏈表中各結(jié)點(diǎn)的data值逐個(gè)地與x進(jìn)行比較，若找到則返回該結(jié)點(diǎn)的指針，否則繼續(xù)往后搜索，若直到表尾都沒有找到，則返回空指針。算法如下：node *locate (n

17、ode *L, datatype x ) node *p=L->next;  while (p!=NULL && p->data!=x )   p=p->next;  return p;5插入如下圖所示，插入操作主要由兩條語句來實(shí)現(xiàn)：s->next=p->next；    p->next=s；    完整的算法如下：void insert (node *L, int i, datatype x ) node *p=L; int k=0;  while (

18、k!=i-1 && p!=NULL) p=p->next;   k+;     if (p=NULL) error ("插入序號(hào)錯(cuò)");  else s= (node * ) malloc (sizeof (node);         s->data=x;           s->next=p->next;  p->n

19、ext=s; 6刪除如下圖所示，刪除ai結(jié)點(diǎn)需執(zhí)行的語句為：p->next=p->next->next；    完整的算法如下：void delete (node *L, int i) node *u , *p;  p=get(L，i-1);  if (p=NULL | p->next=NULL) error ("插入序號(hào)錯(cuò)");  else u=p->next;       /指向要?jiǎng)h除的結(jié)點(diǎn)  

20、60;    p->next=u->next; /繞過要?jiǎng)h除的結(jié)點(diǎn)         free (u);        /釋放結(jié)點(diǎn)的存儲(chǔ)空間單循環(huán)鏈表如果單鏈表中尾結(jié)點(diǎn)的后繼指針指向頭結(jié)點(diǎn)，則構(gòu)成了一個(gè)單循環(huán)鏈表，如下圖所示：   顯然，在單循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可以搜索到其它各個(gè)結(jié)點(diǎn)。單循環(huán)鏈表中基本運(yùn)算的實(shí)現(xiàn)與單鏈表類似：例如，若循環(huán)條件為p!=NULL，則改為p!=L即可。雙

21、（循環(huán)）鏈表若想不需經(jīng)過搜索就可以直接求出任一結(jié)點(diǎn)的前趨，可以采用雙鏈表。雙鏈表中每個(gè)結(jié)點(diǎn)除了后繼指針外，還增加了一個(gè)指向其前趨的指針。雙鏈表也可以是循環(huán)的。帶頭結(jié)點(diǎn)的雙循環(huán)鏈表如下圖所示： 雙循環(huán)鏈表的類型定義如下：typedef struct datatype data;  struct dunode *prior, *next;dunode;顯然，在雙循環(huán)鏈表中：p->prior->next = p->next->prior = p關(guān)于雙循環(huán)鏈表上基本運(yùn)算的實(shí)現(xiàn)主要討論以下兩個(gè)：1. 插入：    s->prior =

22、 p->prior;s->next = p;p->prior->next = s;p->prior = s;2刪除：（P33）    p->next->prior = p->prior;（下）p->prior->next = p->next; （上）free(p); （雙鏈表）棧的基本概念和運(yùn)算棧：是只能在一端進(jìn)行插入和刪除的線性表。它是一種運(yùn)算受到限制的特殊的線性表。如下圖所示的棧，插入和刪除元素的一端稱為棧頂，另一端稱為棧底。插入元素和刪除元素的操作分別稱為入棧和出棧。  &

23、#160; 由于入棧和出棧都只能在棧頂進(jìn)行，所以棧具有先進(jìn)后出 (或后進(jìn)先出)的特性。棧的基本運(yùn)算有以下幾種：(1)初始化InitStack (S)：建立一個(gè)空棧。(2)判斷棧是否為空EmptyStack(S)(3)取棧頂GetTop(S) ：返回棧頂元素的值。(4)入棧Push(S,x) ：將值為x的元素壓入到棧S中。(5)出棧Pop(S,x) ：刪除棧頂元素，并將它的值放到變量x中。順序棧（棧的順序?qū)崿F(xiàn)）以順序存儲(chǔ)方式存儲(chǔ)的棧稱為順序棧，其類型說明如下：#define maxsize 8typedef struct datatype datamaxsize;   int

24、 top; /top值等于棧頂元素的下標(biāo) SqStackTp;順序棧S的結(jié)構(gòu)如下圖所示：    順序棧上運(yùn)算的實(shí)現(xiàn):1初始化：因?yàn)閠op的值等于順序棧中元素的個(gè)數(shù)減1，所以建立一個(gè)空棧只需將top置為-1即可。void InitStack(SqStackTp *S) （注意與教材的區(qū)別P44） s->top=-1;   2判斷棧是否為空：BOOL EmptyStack (SqStackTp S) if (S.top=-1) return(TRUE);  else return(FALSE);3取棧頂：datatype GetTop(SqS

25、tackTp *S) if (EmptyStack(*S) )error("棧為空");   else return(s->datas->top);4入棧： void Push(SqStackTp *S, datatype x) if (S->top=maxsize-1 )error("溢出"); /判斷棧是否為滿  else S->data+s->top= x;5出棧： void Pop(SqStackTp *S, datatype *x) if (EmptyStack(*S) )error(

26、" ?？眨荒軇h除"); else *x=S->dataS->top-;鏈棧（棧的鏈接實(shí)現(xiàn)）用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的棧稱為鏈棧。一般采用不帶頭結(jié)點(diǎn)的單鏈表，并且用表頭作為棧頂，其結(jié)構(gòu)如下圖所示：   在鏈棧上上實(shí)現(xiàn)關(guān)于棧的基本運(yùn)算運(yùn)算，與單鏈表的運(yùn)算相似，只需注意：入棧和出棧操作相當(dāng)于在鏈表的表頭進(jìn)行插入和刪除，故此處不再詳細(xì)討論。typedef struct node DataType data;     /存放元素值  struct node *next; /指示后繼結(jié)點(diǎn)的指針LStackTp

27、;(1)初始化void InitStack(LStackTp *ls) ls=NULL;(2)進(jìn)棧void Push(LStackTp *ls,DataType x) LStackTp *p;p=( LStackTp *)malloc(sizeof(LStackTp );p->data=x;p->next=ls;ls=p;(3)出棧int Push(LStackTp *ls,DataType *x) LStackTp *p;if(ls!=NULL) p=ls;*x=p->data;free(p);return 1;return 0;(4)判?？読nt EmptyStack(L

28、StackTp *ls) if(ls=NULL)return 1;else return 0;(5)讀棧頂元素int GetTop(LStackTp *ls,DataType *x) if(ls!=NULL) *x=ls->data;return 1;return 0;隊(duì)列的基本概念隊(duì)列：是只能在一端進(jìn)行插入、在另一端進(jìn)行刪除的線性表，它也是運(yùn)算受到限制的線性表。通常把插入元素的一端叫做隊(duì)尾，而把刪除元素的一端叫做隊(duì)頭。把隊(duì)列的插入和刪除運(yùn)算分別叫做入隊(duì)和出隊(duì)。隊(duì)列的結(jié)構(gòu)如下圖所示：    由于隊(duì)列只能在隊(duì)頭進(jìn)行出隊(duì)、在隊(duì)尾進(jìn)行入隊(duì)，所以隊(duì)列具有先進(jìn)先出的特

29、性。隊(duì)列的基本運(yùn)算：(1)初始化InitQueue(Q)：設(shè)置一個(gè)空隊(duì)列Q。(2)判斷隊(duì)列是否為空EmptyQueue(Q)(3)取隊(duì)頭GetHead(Q)：返回隊(duì)頭元素的值。(4)入隊(duì)EnQueue(Q,x)：將值為x的元素插入隊(duì)列。(5)出隊(duì)OutQueue(Q) ：刪除隊(duì)頭元素，并返回它的值。順序隊(duì)列以順序存儲(chǔ)方式存儲(chǔ)的隊(duì)列稱為順序隊(duì)列?？梢杂靡粋€(gè)數(shù)組datamaxsize來存儲(chǔ)隊(duì)列中的元素，并設(shè)置一個(gè)變量rear（稱為尾指針）指向隊(duì)尾元素，還有一個(gè)變量front（稱為頭指針）指向隊(duì)頭元素的前一個(gè)位置。順序隊(duì)列的結(jié)構(gòu)如下圖所示：    順序隊(duì)列的類型定義如下

30、： #define maxsize 20typedef struct DataType datamaxsize;      int front,rear;SqQueueTp;為了解決"假溢出"的問題，一般采用如下圖 所示的循環(huán)隊(duì)列來存儲(chǔ)隊(duì)列。    在進(jìn)行入（出）隊(duì)運(yùn)算時(shí)，必須判斷隊(duì)列是否為滿（空）。為了解決這個(gè)問題，采用的方法是保留一個(gè)存儲(chǔ)單元不用，即僅剩一個(gè)空位置時(shí)認(rèn)為隊(duì)列為滿。循環(huán)隊(duì)列上基本運(yùn)算的實(shí)現(xiàn)：1初始化void InitCycQueue(CycQueueTp *Q) Q->f

31、ront=0; Q->rear=0; 2判斷隊(duì)列是否為空BOOL EmptyCycQueue (CycQueueTp Q) if (Q.front=Q.rear) return TRUE;else return FALSE;3取隊(duì)頭元素如果隊(duì)列不空，則返回隊(duì)頭元素的值。DataType GetCycQueueHead (CycQueueTp Q) if (EmptyCycQueue (Q)error(" 隊(duì)空");      else return (Q.data(Q.front+1)% maxsize); 

32、     /隊(duì)頭元素在頭指針front指向的下一個(gè)位置4入隊(duì)void EnCycQueue(CycQueueTp * Q,datatype x) if (1+Q->rear)% maxsize=Q->front) error(" 溢出"); /判斷隊(duì)列是否為滿else Q->rear=(1+Q->rear) % maxsize; /尾指針向后移一位        Q->dataQ->rear= x;5.出隊(duì)datatype Out

33、CycQueue(CycQueueTp * Q) if (EmptyCycQueue (*Q) )error(" 隊(duì)空，不能出隊(duì)");     else Q->front=(Q->front+1) % maxsize;            return Q->dataQ->front; 鏈隊(duì)列鏈隊(duì)列是指用鏈表存儲(chǔ)的隊(duì)列。一般采用帶頭結(jié)點(diǎn)的單鏈表，其結(jié)構(gòu)如下圖所示：   

34、鏈隊(duì)列的類型定義如下： typedef struct node *front,*rear;LkQueue;鏈隊(duì)列上基本運(yùn)算的實(shí)現(xiàn)如下：1. 初始化空的鏈隊(duì)列僅有一個(gè)頭結(jié)點(diǎn)，并且頭尾指針均指向頭結(jié)點(diǎn)。void InitQueue(LkQueue *Q) Q->front=(node *)malloc(sizeof(node); /產(chǎn)生一個(gè)頭結(jié)點(diǎn)  Q->rear=Q->front; /尾指針也指向頭結(jié)點(diǎn)  Q->front->next=NULL; /尾結(jié)點(diǎn)后繼指針設(shè)置為空2.判斷隊(duì)列是否為空BOOL EmptyQueue(LkQueue Q) r

35、eturn (Q.front=Q.rear);  3取隊(duì)頭元素void GetHead(LkQueue * Q, datatype * x); if (EmptyQueue (*Q) )error(" 隊(duì)空，不能取元素");  else *x=Q->front->next->data; /取隊(duì)頭元素（首結(jié)點(diǎn)）的值4入隊(duì)void EnQueue(LkQueue * Q, datatype x) node *P=(node *)malloc(sizeof(node);  P->data=x;  P->next

36、=NULL; /新隊(duì)尾的后繼指針為空  Q->rear->next=P; /插入到隊(duì)尾  Q->rear=P; /尾指針指向新的隊(duì)尾5出隊(duì)void OutQueue(LkQueue *Q, datatype *x) if (EmptyQueue (*Q) )error(" 隊(duì)空，不能出隊(duì)");  else x=Q->front->next->data; /取隊(duì)頭元素的值         node *u=Q->front-&g

37、t;next; /保存待刪結(jié)點(diǎn)的指針         Q->front->next=u->next; /刪除         free(u);        if (Q->front->next=NULL) /出隊(duì)最后一個(gè)結(jié)點(diǎn)時(shí)         Q-

38、>rear=Q->front;樹：是n個(gè)結(jié)點(diǎn)構(gòu)成的有限集合(n>0)，其中有一個(gè)結(jié)點(diǎn)稱為根，其余結(jié)點(diǎn)可劃分為m個(gè)互不相交的子集T1,T2Tm (m0)，這m個(gè)子集本身又構(gòu)成樹，稱為根的子樹。下圖所示為一棵樹，其中A為根，A有三棵子樹T1、T2和T3；其中在T1中，B是該子樹的根，B又有三棵子樹。    下面介紹關(guān)于樹的一些常見術(shù)語：結(jié)點(diǎn)：樹中的結(jié)點(diǎn)包含相應(yīng)元素的值及其子樹的信息。度：一個(gè)結(jié)點(diǎn)的子樹的數(shù)目稱為該結(jié)點(diǎn)的度。樹中各結(jié)點(diǎn)的最大度稱為樹的度。如上圖中樹的度為3。葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)（或終端結(jié)點(diǎn)）。否則稱為非終端結(jié)點(diǎn)（或分支結(jié)點(diǎn)

39、）。孩子結(jié)點(diǎn)：某結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)，相應(yīng)地該結(jié)點(diǎn)為其孩子結(jié)點(diǎn)的父親（或雙親）結(jié)點(diǎn)。如A的孩子為B，C，D；而H、I的雙親均為C。兄弟結(jié)點(diǎn)：同一結(jié)點(diǎn)的孩子之間互稱為兄弟。如E，F(xiàn)，G為兄弟。祖先：一個(gè)結(jié)點(diǎn)的祖先是指從根結(jié)點(diǎn)到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。后代：以某個(gè)結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)(不包括自身)為該結(jié)點(diǎn)的后代。結(jié)點(diǎn)的層次：根的層次為1，其余結(jié)點(diǎn)的層次為其父結(jié)點(diǎn)的層次數(shù)加1。樹的高度：樹中結(jié)點(diǎn)的最大層次數(shù)稱為樹的高度（或深度）。有序/無序樹：如果樹中結(jié)點(diǎn)的各子樹是看成按從左到右的次序排列的，則稱該樹為有序樹，否則稱為無序樹。在有序樹中，最左邊的子樹的根為第一個(gè)孩子。森林：是

40、m(m0)棵互不相交的樹的集合。（樹）樹的基本運(yùn)算(1)初始化Initiate(T)：建立一棵空樹。(2)求樹根Root(T)(3)求父親Parent(T,x)：求樹T中結(jié)點(diǎn)x的父親結(jié)點(diǎn)。(4)求孩子Child(T,x,i)：求樹T中結(jié)點(diǎn)x的第i個(gè)孩子結(jié)點(diǎn)。(5)求下一個(gè)兄弟：NextBrother(T,x)：求樹T中結(jié)點(diǎn)x的下一個(gè)兄弟結(jié)點(diǎn)。(6)建樹Create(T)(7)插入子樹Insert(T,i,x)：將以x為根的子樹插入到T中，作為T的第i棵子樹。(8)刪除子樹Delete(T,i)：刪除T的第i棵子樹。(9)遍歷樹Travel(T)：按某種順序依次訪問樹T中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)都要

41、訪問一次并且僅訪問一次。二叉樹：二叉樹T是n個(gè)結(jié)點(diǎn)的有限集合(n0)，當(dāng)n=0時(shí)，為空二叉樹，否則其中有一個(gè)結(jié)點(diǎn)為根，其余結(jié)點(diǎn)劃分為兩個(gè)互不相交的子集TL和TR，并且TL和TR也是二叉樹，稱為根的左子樹和右子樹。下圖為一棵二叉樹：    其中，A、C的兩棵子樹均不空；B的右子樹為空；E的左子樹為空；D、F、G的兩棵子樹均為空。二叉樹的運(yùn)算的定義與樹類似，略。二叉樹有五個(gè)重要的基本性質(zhì)： 性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。性質(zhì)2：深度為K的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：對(duì)任意一棵非空的二叉樹T，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0

42、=n2+1。滿二叉樹：深度為K并且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹。對(duì)滿二叉樹中的各個(gè)結(jié)點(diǎn)按從上往下、從左往右的順序進(jìn)行編號(hào)（根結(jié)點(diǎn)編號(hào)為1），然后按編號(hào)從大到小的順序依次刪除若干個(gè)結(jié)點(diǎn)，所得到的二叉樹稱為完全二叉樹。下圖為完全二叉樹：    性質(zhì)4：有n個(gè)結(jié)點(diǎn)的完全二叉樹(n>0)，其深度為log2n+1。性質(zhì)5：完全二叉樹中，編號(hào)為i的結(jié)點(diǎn)(1in)：(1)如果不為根（i>1）,其父親結(jié)點(diǎn)的編號(hào)為i/2。(2)如果有左孩子，其左孩子的編號(hào)為2i。(3)如果有右孩子，其右孩子的編號(hào)為2i+1。二叉樹的存儲(chǔ)結(jié)構(gòu)二叉鏈表中結(jié)點(diǎn)的結(jié)構(gòu)如下：  

43、;   類型定義為： typedef struct btnode *bitreptr;struct btnode datatype data;     bitreptr lchild,rchild;bitreptr root;順序存儲(chǔ)結(jié)構(gòu)將結(jié)點(diǎn)在完全二叉樹中的編號(hào)作為該結(jié)點(diǎn)在數(shù)組中的位置來存儲(chǔ)。上圖中完全二叉樹的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：    采用這種方式存儲(chǔ)，可以由性質(zhì)5知道各結(jié)點(diǎn)間的關(guān)系。可以比較方便 實(shí)現(xiàn)二叉樹的各種基本運(yùn)算顯然，用順序存儲(chǔ)方式存儲(chǔ)非完全二叉樹時(shí)，會(huì)導(dǎo)致存儲(chǔ)空間的浪費(fèi)。例如：

44、0; 二叉樹的遍歷1先序遍歷若二叉樹T不空，則：訪問T的根結(jié)點(diǎn) 先序遍歷T的左子樹 先序遍歷T的右子樹2中序遍歷若二叉樹T不空，則：中序遍歷T的左子樹 訪問T的根結(jié)點(diǎn) 中序遍歷T的右子樹3后序遍歷若二叉樹T不空，則：后序遍歷T的左子樹 后序遍歷T的右子樹 訪問T的根結(jié)點(diǎn)例：對(duì)下圖所示二叉樹分別進(jìn)行先序、中序和后序遍歷，所得到的訪問序列為：    先序序列：ABCDEFGHIJ中序序列：CBEDAGHFJI后序序列：CEDBHGJIFA先序遍歷的算法如下：（二叉樹的遍歷）void preorder (bitreptr T) / /先序遍歷以T為根指針的二叉樹 if

45、(T!=NULL)     visite(T); /訪問T的根結(jié)點(diǎn)       preorder(T->lchild); /先序遍歷T的左子樹       preorder(T->rchild); /先序遍歷T的右子樹    中序遍歷的算法如下： void inorder(bitreptr T) /中序遍歷 if (T!=NULL)      i

46、norder(T->lchild); /中序遍歷T的左子樹        visite(T); /訪問T的根結(jié)點(diǎn)        inorder(T->rchild); /中序遍歷T的右子樹      后序遍歷的算法如下void postorder(bitreptr T) /后序遍歷 if (T!=NULL)      postorder(T-&g

47、t;lchild); /后序遍歷T的左子樹        postorder(T->rchild); /后序遍歷T的右子樹       visite(T); /訪問T的根結(jié)點(diǎn)簡(jiǎn)單順序查找對(duì)一個(gè)順序表進(jìn)行查找，最簡(jiǎn)單的方法就是從順序表的一端開始，逐個(gè)進(jìn)行比較。這種方法無論順序表是否有序都可以。算法如下：#define maxsize 靜態(tài)查找表表長(zhǎng)typedef structkeytype key;rec;typedef structrec itemmaxsiz

48、e+1;int n;sqtable;int search_sqtable(sqtable R, keytype K) （P131） i=R.n; R.item0.key=K;          /設(shè)初始比較位置，設(shè)"崗哨"while (R.item i.key!=K ) i-; /從后往前進(jìn)行查找return(i); 也可以用R.itemn+1作為"崗哨"（程序如何改寫?）int seqsearch(datatype A, int n, keytype k) i=n

49、; A0.key=k;          /A0為"崗哨"while (Ai.key!=k ) i-; /從后往前進(jìn)行查找return(i);簡(jiǎn)單順序查找在查找成功時(shí)的平均查找長(zhǎng)度為：ASL=(1+2+n)/n=(n+1)/2，查找失敗時(shí)的查找長(zhǎng)度為n+1。有序表的查找對(duì)于任何一個(gè)順序表，若其中的所有結(jié)點(diǎn)按鍵值的某種次序排列，則稱為有序表。如果順序表中的元素是按關(guān)鍵字遞增（減）有序排列的，可以采用二分查找（折半查找）來提高查找的時(shí)間性能。二分查找的過程如下：設(shè)查找區(qū)域的首尾下標(biāo)分別用變

50、量low和high表示，將中間元素（下標(biāo)為mid=(low+high)/2）的關(guān)鍵字與給定值x進(jìn)行比較，有三種情況： (1) K= R.item mid.key: 則查找成功，返回mid的值。 (2) K< R.item mid.key: 在下標(biāo)從low到mid-1的區(qū)域中繼續(xù)查找。 (3) K> R.item mid.key: 在下標(biāo)從mid+1到high的區(qū)域中繼續(xù)查找。例：在下圖所示有序表中查找8。    在查找的過程中，查找區(qū)域不斷縮?。╨ow增大，high縮小，且low應(yīng)不大于high），若low>high，則表明查找區(qū)域?yàn)榭?，查找失?/p>

51、。二分查找的算法如下： int binsearch(sqtable R, keytype K) int mid,low=1,high=R.n; /初始化查找區(qū)域     while (low<=high) mid=(low+high)/2; switch case K= R.item mid.key : return (mid); case K < R.itemmid.key : high=mid-1; break; case K > R.itemmid.key : low=low+1; break;return (0);int bin

52、search(datatype A,int n, keytype x) int mid,low=1,high=n; /初始化查找區(qū)域     while (low<=high) mid=(low+high)/2; if (x=Amid.key) return (mid); else if (x<Amid.key) high=mid-1; else low=mid+1;return (0);另外一種通過遞歸實(shí)現(xiàn)的二分查找的算法如下：int binsearch(datatype A,int low，int high，keytype x) int

53、mid;if (low>high) return(0);else mid=(low+high)/2;     if (x=Amid.key) return (mid);     else if (x<Amid.key) return (binsearch(A, low，mid-1，x);     else return (binsearch(A, mid+1，high, x);交換排序交換類排序的基本思想是：兩兩比較待排序列的元素，發(fā)現(xiàn)倒序即交換。冒泡排序冒泡排序的基本思想是：從后往前（或從前往后）依次比較相鄰的兩個(gè)元素，發(fā)現(xiàn)倒序即交換，每一趟都能將待排序列中最?。ɑ蜃畲螅┑脑亟粨Q到其最終位置上。例：對(duì)下列鍵值進(jìn)行冒泡排序。87，63，29，90，31，56，12從以上過程可以看出，每一趟排序都有一個(gè)當(dāng)前最小的元素被放到它的最終位置上，就象一串氣泡按照從輕到重的次序依次冒出水面一樣，所以稱之為冒泡排序。冒泡排序的算法如下:void bubblesort(datatype A ,int n) for (i=1;i<=n-1;i+ )&