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

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

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

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

4、度。(1)for (i=0; i<n; i+) x+;【解答】：時間復(fù)雜度為O(n)。(2)for (i=0; i<n; i+) for (j=0; j<=i; j+) x+;【解答】：時間復(fù)雜度為O(n2)。(3)i=1; while (i<n) i*=2;【解答】：時間復(fù)雜度為O(log2n)。/*設(shè)k次，則2k=n，所以k=log2n*/例：下列程序段的時間復(fù)雜性的量級為 。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 ，則 時間復(fù)雜性的量級為 O ( n 2 )。【解答】： O ( n 2 )(4)（矩陣的乘積）【解答】：時間復(fù)雜度為O(n3)。常見時間復(fù)雜性的量級有：常數(shù)階 O ( 1 )(即算法的時間復(fù)雜性與輸入規(guī)模 n 無關(guān)或 n 恒為常數(shù))、對數(shù)階 O ( log 2 n )、線性階 O ( n )、平方階 O ( n 2 )和指數(shù)階 O ( 2 n )?？臻g復(fù)雜性：主要關(guān)心一個算法除輸入數(shù)據(jù)占用存儲空間之外的附加存儲空間的大小。（算法復(fù)雜度）線性表：線性表L是指n個元素a1，a2，an組成的有限序列。記作：L=( a1，a

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

7、ypedef struct datatype datamaxsize; /順序表中元素的類型用datatype泛指  int last; /表長sqlist;由上述定義不難發(fā)現(xiàn)，順序表具有這樣的特點：邏輯上相鄰的元素，其存儲地址也相鄰。順序表中基本運算的實現(xiàn)1初始化順序表建立一個空的順序表L，只需將表長置為0即可。void initiate(sqlist *L) L->last=0; 2求表長即返回順序表L的last值。int length(sqlist L) return (L.last); 3按給定序號取元素序號為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中的每個元素與給定的值x進行比較。若找到則返回其序號（下標(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）首先要判斷能否進行插入，即表是否為滿以及插入位置i是否合理。（2）如果可以進行插入，需要執(zhí)行下列步驟： 為了給待插入元素x騰出一個空位，需要將aian往后移一位。 將x插入到第i個位置上。 插入后，順序表L的長度last要加1。void insert (sqlist *L, datatype x, int i ) int j;  if (i<1 | i>L->last+1) error ("插入位置錯誤");  else if (L->

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

11、#160;  L->datai-1=x; /插入x                L-> last +;  /修改表長          算法分析：（P20）當(dāng)插入位置i=1，2n+1時，移動元素的次數(shù)分別為n，n-1,1，0。因此平均移動次數(shù)為：(0+1+n) / ( n+1) = n / 2，所以插入算法的時間復(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 -；    算法的時間復(fù)雜度為O(n)。單鏈表在順序表中插入和刪除元素時，需要做大量移動元素的操作，比較浪費時間。要想在插入和刪除時不需移動元素，可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，此時線性表中每個元素稱為一個結(jié)點，如下圖所示：   每個結(jié)點包括兩個部分：數(shù)據(jù)域data，用于存儲元素的值。指針域next，用于存儲后繼結(jié)點的地址。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表稱為鏈表。本節(jié)介紹的鏈表，每個結(jié)點只有一個指

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

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

16、160;  p=p->next;     return n ;3按給定序號取元素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é)點的data值逐個地與x進行比較，若找到則返回該結(jié)點的指針，否則繼續(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插入如下圖所示，插入操作主要由兩條語句來實現(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 ("插入序號錯");  else s= (node * ) malloc (sizeof (node);         s->data=x;           s->next=p->next;  p->n

19、ext=s; 6刪除如下圖所示，刪除ai結(jié)點需執(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 ("插入序號錯");  else u=p->next;       /指向要刪除的結(jié)點  

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

21、（循環(huán)）鏈表若想不需經(jīng)過搜索就可以直接求出任一結(jié)點的前趨，可以采用雙鏈表。雙鏈表中每個結(jié)點除了后繼指針外，還增加了一個指向其前趨的指針。雙鏈表也可以是循環(huán)的。帶頭結(jié)點的雙循環(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)鏈表上基本運算的實現(xiàn)主要討論以下兩個：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); （雙鏈表）棧的基本概念和運算棧：是只能在一端進行插入和刪除的線性表。它是一種運算受到限制的特殊的線性表。如下圖所示的棧，插入和刪除元素的一端稱為棧頂，另一端稱為棧底。插入元素和刪除元素的操作分別稱為入棧和出棧。  &

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

24、 top; /top值等于棧頂元素的下標(biāo) SqStackTp;順序棧S的結(jié)構(gòu)如下圖所示：    順序棧上運算的實現(xiàn):1初始化：因為top的值等于順序棧中元素的個數(shù)減1，所以建立一個空棧只需將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-;鏈棧（棧的鏈接實現(xiàn)）用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的棧稱為鏈棧。一般采用不帶頭結(jié)點的單鏈表，并且用表頭作為棧頂，其結(jié)構(gòu)如下圖所示：   在鏈棧上上實現(xiàn)關(guān)于棧的基本運算運算，與單鏈表的運算相似，只需注意：入棧和出棧操作相當(dāng)于在鏈表的表頭進行插入和刪除，故此處不再詳細(xì)討論。typedef struct node DataType data;     /存放元素值  struct node *next; /指示后繼結(jié)點的指針LStackTp

27、;(1)初始化void InitStack(LStackTp *ls) ls=NULL;(2)進棧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;隊列的基本概念隊列：是只能在一端進行插入、在另一端進行刪除的線性表，它也是運算受到限制的線性表。通常把插入元素的一端叫做隊尾，而把刪除元素的一端叫做隊頭。把隊列的插入和刪除運算分別叫做入隊和出隊。隊列的結(jié)構(gòu)如下圖所示：    由于隊列只能在隊頭進行出隊、在隊尾進行入隊，所以隊列具有先進先出的特

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

45、(T!=NULL)     visite(T); /訪問T的根結(jié)點       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é)點        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é)點簡單順序查找對一個順序表進行查找，最簡單的方法就是從順序表的一端開始，逐個進行比較。這種方法無論順序表是否有序都可以。算法如下：#define maxsize 靜態(tài)查找表表長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-; /從后往前進行查找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-; /從后往前進行查找return(i);簡單順序查找在查找成功時的平均查找長度為：ASL=(1+2+n)/n=(n+1)/2，查找失敗時的查找長度為n+1。有序表的查找對于任何一個順序表，若其中的所有結(jié)點按鍵值的某種次序排列，則稱為有序表。如果順序表中的元素是按關(guān)鍵字遞增（減）有序排列的，可以采用二分查找（折半查找）來提高查找的時間性能。二分查找的過程如下：設(shè)查找區(qū)域的首尾下標(biāo)分別用變

50、量low和high表示，將中間元素（下標(biāo)為mid=(low+high)/2）的關(guān)鍵字與給定值x進行比較，有三種情況： (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ū)域為空，查找失敗

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);另外一種通過遞歸實現(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)倒序即交換。冒泡排序冒泡排序的基本思想是：從后往前（或從前往后）依次比較相鄰的兩個元素，發(fā)現(xiàn)倒序即交換，每一趟都能將待排序列中最?。ɑ蜃畲螅┑脑亟粨Q到其最終位置上。例：對下列鍵值進行冒泡排序。87，63，29，90，31，56，12從以上過程可以看出，每一趟排序都有一個當(dāng)前最小的元素被放到它的最終位置上，就象一串氣泡按照從輕到重的次序依次冒出水面一樣，所以稱之為冒泡排序。冒泡排序的算法如下:void bubblesort(datatype A ,int n) for (i=1;i<=n-1;i+ )&