電子科大820數(shù)據(jù)結(jié)構(gòu)考綱考點(diǎn)歸納

1、ch1. 數(shù)據(jù)結(jié)構(gòu)及算法的相關(guān)概念和術(shù)語(yǔ)（1） 數(shù)據(jù)結(jié)構(gòu)及算法的概念；數(shù)據(jù)：所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱。數(shù)據(jù)元素：數(shù)據(jù)的基本單位，一個(gè)數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)項(xiàng)組成。數(shù)據(jù)項(xiàng)：構(gòu)成數(shù)據(jù)元素的不可分割的最小單位。* 關(guān)系：數(shù)據(jù)>數(shù)據(jù)元素>數(shù)據(jù)項(xiàng)數(shù)據(jù)對(duì)象：性質(zhì)相同的數(shù)據(jù)元素的集合。數(shù)據(jù)類型：原子類型、結(jié)構(gòu)類型、抽象數(shù)據(jù)類型。數(shù)據(jù)結(jié)構(gòu)：相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。（2）數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)；數(shù)據(jù)結(jié)構(gòu)三要素： 數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算數(shù)據(jù)的邏輯結(jié)構(gòu)：線性結(jié)構(gòu)（線性表）、非線性結(jié)構(gòu)（集合、樹和圖）。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)：優(yōu)點(diǎn)：可

2、以隨機(jī)存取，每個(gè)元素占用最少存儲(chǔ)空間缺點(diǎn)：可能產(chǎn)生較多碎片現(xiàn)象鏈?zhǔn)酱鎯?chǔ)：優(yōu)點(diǎn)：不會(huì)出現(xiàn)碎片現(xiàn)象缺點(diǎn)：每個(gè)元素占用較多存儲(chǔ)空間，只能實(shí)現(xiàn)順序存儲(chǔ)索引存儲(chǔ)：優(yōu)點(diǎn)：檢索速度快缺點(diǎn)：增加了附加的索引表，會(huì)占用較多存儲(chǔ)空間散列存儲(chǔ)：優(yōu)點(diǎn)：檢索、增加和刪除結(jié)點(diǎn)的操作都很快缺點(diǎn)：可能出現(xiàn)存儲(chǔ)單元的沖突，解決沖突會(huì)增加時(shí)間和空間的開銷（3）算法的定義及特性；算法：對(duì)特定問(wèn)題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個(gè)或多個(gè)操作。算法的特性：有窮性、確定性、可行性、輸入、輸出算法設(shè)計(jì)的要求：正確性、可讀性、健壯性、效率與低存儲(chǔ)量需求* 同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低（4）算法時(shí)

3、間復(fù)雜度和空間復(fù)雜度的分析方法。時(shí)間復(fù)雜度：主要分析語(yǔ)句頻度（一條語(yǔ)句在算法中被重復(fù)執(zhí)行的次數(shù)）之和t(n)的數(shù)量級(jí)加法原則：t(n)=t1(n)+t2(n)=o(max(f(n),g(n)乘法原則：t(n)=t1(n)t2(n)=o(f(n)·g(n)* 常見時(shí)間復(fù)雜度比較：o(1)<o(n)<o(nlogn)<o(n2)<o(n3)<o(2n)<o(n!)<o(nn)空間復(fù)雜度：算法所耗費(fèi)的存儲(chǔ)空間，s(n)=o(g(n)算法原地工作是指算法所需輔助空間是常量，即o(1)ch2線性表（1）線性表的定義線性表：具有相同數(shù)據(jù)類型的n(n0)個(gè)

4、數(shù)據(jù)元素的有限序列，一般表示如下：l=(a1, a2, , ai+1, , an)其中，a1是唯一的“第一個(gè)”數(shù)據(jù)元素，稱為表頭元素；an是唯一的“最后一個(gè)”數(shù)據(jù)元素，稱為表尾元素；除第一個(gè)元素外，每個(gè)元素有且僅有一個(gè)直接前趨；除最后一個(gè)元素外，每個(gè)元素有且僅有一個(gè)直接后繼。線性表的特點(diǎn)：表中元素具有邏輯上的順序性，表中元素都是數(shù)據(jù)元素，表中元素的數(shù)據(jù)類型都相同，表中元素具有抽象性。（2）線性表的基本操作及在順序存儲(chǔ)及鏈?zhǔn)酱鎯?chǔ)上的實(shí)現(xiàn)；線性表的基本操作：initlist(&l) 構(gòu)造一個(gè)空的線性表listlength(l) 求表長(zhǎng)，即求線性表中數(shù)據(jù)結(jié)點(diǎn)（如果是帶頭結(jié)點(diǎn)單鏈表，則不含頭結(jié)

5、點(diǎn)）的個(gè)數(shù)locateelem(l, e) 按值查找getelem(l, i) 按位查找listinsert(&l, i, e) 在表l中的第i個(gè)位置插入指定元素listdelete(&l, i, &e) 刪除表l中的第i個(gè)位置的元素，并輸出其值printlist(l) 按前后順序輸出線性表l的所有元素值listempty(l) 判空，若l為空表，返回true，否則返回falsedestroylist(&l) 銷毀線性表，并釋放表l占用的內(nèi)存空間clearlist(&l) 將l重置為空表priorelem(l,cur_e,&pre_e) 若cur

6、_e是表l的數(shù)據(jù)元素，且不是第一個(gè)，用pre_e返回其前驅(qū)nextelem(l,cur_e,&next_e) 若cur_e是表l的元素，且不是最后一個(gè)，用next_e返回其后繼listtraverse(l,visit() 表的遍歷，即依次對(duì)l的每個(gè)元素調(diào)用函數(shù)visit()線性表的順序存儲(chǔ)（順序表）：線性表中第i+1個(gè)數(shù)據(jù)元素的存儲(chǔ)位置loc(ai+1)和第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置loc(ai)之間關(guān)系：loc(ai+1)= loc(ai)+l線性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置：loc(ai)= loc(a1)+(i-1)·l順序表的特點(diǎn)：可以進(jìn)行隨機(jī)存取，即通過(guò)首地址和元素

7、序號(hào)可以在o(1)的時(shí)間內(nèi)找到指定元素，但插入和刪除元素操作需要移動(dòng)大量元素順序表結(jié)構(gòu)的定義：順序表的靜態(tài)分配：#define maxsize 50typedef structelemtype datamaxsize;int length;sqlist;順序表的動(dòng)態(tài)分配：#define initsize 50typedef structelemtype *data;int listsize,length;sqlist;* 動(dòng)態(tài)分配語(yǔ)句：l.data=(elemtype *)malloc(sizeof(elemtype)*initsize);順序表基本操作的實(shí)現(xiàn)：初始化操作：構(gòu)造一個(gè)空的順序表l

8、bool initlist_sq(sqlist &l)l.data=(elemtype *)malloc(initsize*sizeof(elemtype);if(!l.data) exit(overflow);l.length=0;l.listsize=initsize;return true;/initlist_sq插入操作：在第i(1in)個(gè)元素之前插入一個(gè)元素，需將第n至第i(共n-i+1)個(gè)元素向后移動(dòng)一個(gè)位置。bool listinsert_sq(sqlist &l,int i,elemtype e)/在順序表l中的第i個(gè)位置插入新元素e/i的合法值為1il.len

9、gth+1if(i<1|i>l.length+1) return false; /i值不合法if(l.length>=listsize) /當(dāng)前存儲(chǔ)空間已滿，不能插入return false;for(i=l.length;j>=i;j-) /將第i個(gè)位置及之后元素后移l.dataj=l.dataj-1;l.datai-1=e;/在位置i處放入el.length+;/表長(zhǎng)加1return true;/listinsert_sq時(shí)間復(fù)雜度：最好情況：在表尾插入，無(wú)須移動(dòng)元素，t(n)=o(1)最壞情況：在表頭插入，需要移動(dòng)第一個(gè)元素后面所有元素，t(n)=o(n)平均情況：

10、t(n)=n/2=o(n)刪除操作：在順序表l中刪除第i(1in)個(gè)元素，需將第n至第i(共n-i+1)個(gè)元素向前移動(dòng)一個(gè)位置。bool listdelete_sq(sqlist &l,int i,elemtype e)/在順序表l中刪除第i個(gè)元素，并用e返回其值/i的合法值為1il.lengthif(i<1|i>l.length) return false; /i值不合法e=l.datai-1;for(int j=i;j<l.length;j+)l.dataj-1=l.dataj;l.length-;return true;/listdelete_sq時(shí)間復(fù)雜度t(

11、n)：最好情況：刪除表尾元素，無(wú)須移動(dòng)元素，t(n)=o(1)最壞情況：刪除表頭元素，需要移動(dòng)第一個(gè)元素后面所有元素，t(n)=o(n)平均情況：t(n)=(n-1)/2=o(n)按值查找（順序查找）:int locateelem(sqlist l,int i,elamtype e)/查找順序表中值為e的元素，若查找成功，返回元素位序，否則返回0for(int i=0;i<l.length;i+)if(l.datai=e) return i+1; /下標(biāo)為i的元素值等于e，返回其位號(hào)i+1return 0;/locateelem順序表的歸并：t(n)=o(la.length+lb.len

12、gth)void mergelist_sq(sqlist la, sqlist lb, sqlist &lc)/已知順序表la和lb的元素按值非遞減排列/歸并la和lb得到新的順序表lc，lc的元素也按值非遞減排列pa=la.data;pb=lb.data;lc.listsize=lc.length=la.length+lb.length;pc=lc.data=(elemtype *)malloc(lc.listsize*sizeof(elemtype);if(!lc.data) exit(overflow);pa_last=la.data+la.length-1;pb_last=lb

13、.data+lb.length-1;while(pa<=pa_last&&pb<=pb_last) /開始?xì)w并if(*pa<=*pb) *pc+=*pa+;else *pc+=*pb+;while(pa<=pa_last) *pc+=*pa+;while(pb<=pb_last) *pc+=*pb+;/mergelist_sq線性表的鏈?zhǔn)酱鎯?chǔ)（單鏈表）：?jiǎn)捂湵斫Y(jié)構(gòu)的定義：typedef struct lnodeelemtype data;struct lnode *next;lnode,*linklist;引入頭結(jié)點(diǎn)的單鏈表：頭結(jié)點(diǎn)的數(shù)據(jù)域可以不設(shè)

14、任何信息，也可以記錄表長(zhǎng)等信息，頭結(jié)點(diǎn)的指針域指向線性表的第一個(gè)結(jié)點(diǎn)。* 引入頭結(jié)點(diǎn)的兩個(gè)優(yōu)點(diǎn)：(1) 由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致，無(wú)須進(jìn)行特殊處理(2) 無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域空），因此空表和非空表的處理也就統(tǒng)一了單鏈表基本操作的實(shí)現(xiàn)：?jiǎn)捂湵淼慕?（頭插法）：時(shí)間復(fù)雜度o(n)void createlist1_l(linklist &l,int n)/從表尾到表頭逆位序輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表l/每次均在頭結(jié)點(diǎn)之后插入元素l=(linklist)

15、malloc(sizeof(lnode); /創(chuàng)建頭結(jié)點(diǎn)l->next=null; /初始為空表for(i=n;i>0;i-)p=(linklist)malloc(sizeof(lnode); /創(chuàng)建新結(jié)點(diǎn)scanf(&p->data);p->next=l->next;l->next=p;/將新結(jié)點(diǎn)插入表中/createlist1_l單鏈表的建立2（尾插法）：時(shí)間復(fù)雜度o(n)void createlist2_l(linklist &l,int n)/從表頭到表尾正向輸入n個(gè)元素的值，建立帶頭結(jié)點(diǎn)的單鏈表l/每次均在表尾插入元素l=(link

16、list)malloc(sizeof(lnode); /創(chuàng)建頭結(jié)點(diǎn)l->next=null; /初始為空表q=l; /表尾指針for(i=n;i>0;i-)p=(linklist)malloc(sizeof(lnode); /創(chuàng)建新結(jié)點(diǎn)scanf(&p->data);r->next=p;r=p;/將新結(jié)點(diǎn)插入表中r->next=null;/表尾指針置空/createlist2_l單鏈表的查找1（按位置查找）：lnode* getelem_l(linklist l,int i)/l為帶頭結(jié)點(diǎn)的單鏈表的頭指針/當(dāng)?shù)趇個(gè)元素存在時(shí)，返回第i個(gè)結(jié)點(diǎn)的指針，否則返回

17、nullint j=1;/計(jì)數(shù)，初始為1p=l->next;/初始化，p指向每一個(gè)結(jié)點(diǎn)while(p&&j<i)/順時(shí)針向后查找，直到p指向第i個(gè)元素或p為空p=p->next;j+;if(!p|j>i) return null; /若i大于表長(zhǎng)，p=null直接返回nullreturn p;/返回第i個(gè)結(jié)點(diǎn)的指針/getelem_l單鏈表的查找2（按值查找）：lnode* locateelem_l(linklist l,elemtype e)/l為帶頭結(jié)點(diǎn)的單鏈表的頭指針/當(dāng)值查找成功時(shí)返回?cái)?shù)據(jù)域值等于e的結(jié)點(diǎn)指針，否則返回nullint i=0;p=

18、l->next;while(p&&p->data!=e) /順時(shí)針向后查找，直到p指向值為e的元素或p為空p=p->next;return p;/找到后返回該結(jié)點(diǎn)指針，否則返回null/locateelem_l插入操作(前插)：先找到前驅(qū)結(jié)點(diǎn)*p，然后完成在*p后插入*s，時(shí)間復(fù)雜度t(n)=o(n)bool listinsert_l(linklist &l,int i,elemtype e)/在帶頭結(jié)點(diǎn)的單鏈表l中第i個(gè)位置插入元素ep=getelem_l(l,i-1);/查找插入位置的前趨結(jié)點(diǎn)if(!p) return false;/插入位置不合法

19、s=(linklist)malloc(sizeof(lnode);/生成新結(jié)點(diǎn)s->data=e;/插入l中s->next=p->next;p->next=s;return true;/listinsert_l插入操作（后插）：設(shè)p指向單鏈表中某結(jié)點(diǎn)，s指向待插入值為e的新結(jié)點(diǎn)，將*s插入到*p之后。時(shí) 間復(fù)雜度t(n)=o(1)/只給出關(guān)鍵代碼段s->next=p->next;/修改指針域，順序不能顛倒p->next=s;e=p->data;/交換數(shù)據(jù)域部分p->data=s->data;s->data=e刪除操作1：先找到被

20、刪結(jié)點(diǎn)的前趨，然后完成在*p后刪除被刪結(jié)點(diǎn)，時(shí)間復(fù)雜度t(n)=o(n)bool listdelete_l(linklist &l,int i,elemtype &e)/在帶頭結(jié)點(diǎn)的單鏈表l中，刪除第i個(gè)元素，并由e返回其值p=getelem_l(l,i-1); /查找第i個(gè)結(jié)點(diǎn)，并令p指向其前趨if(!p) return false;/刪除位置不合法q=p->next;/令q指向被刪除結(jié)點(diǎn)p->next=q->next;/將*q結(jié)點(diǎn)從鏈中斷開e=q->data;/取其數(shù)據(jù)域的值free(q);/釋放結(jié)點(diǎn)的存儲(chǔ)空間return true;/listdel

21、ete_l刪除操作2：將結(jié)點(diǎn)*p后繼結(jié)點(diǎn)的值賦予其自身，然后刪除后繼結(jié)點(diǎn)，時(shí)間復(fù)雜度t(n)=o(1)/只給出關(guān)鍵代碼段q=p->next;/修改指針域，順序不能顛倒p->data=p->next->data; /和后繼結(jié)點(diǎn)交換數(shù)據(jù)域e=p->data;p->next=q->next; /將*q結(jié)點(diǎn)從鏈中斷開free(q);/釋放結(jié)點(diǎn)的存儲(chǔ)空間單鏈表的歸并：void mergelist_l(linklist la, linklist lb, linklist &lc)/已知單鏈表la和lb的元素按值非遞減排列/歸并la和lb得到新的單鏈表lc，

22、lc的元素也按值非遞減排列pa=la->next;pb=lb->next;lc=pc=la;/用la的頭結(jié)點(diǎn)作為lc的頭結(jié)點(diǎn)while(pa&&pb)/開始?xì)w并if(pa->data<=pb->data)pc->next=pa;pc=pa;pa=pa->next;elsepc->next=pb;pc=pb;pb=pb->next;pc->next=pa?pa:pb;/插入剩余段free(lb); /釋放lb頭結(jié)點(diǎn)/mergelist_l（3）各種變形鏈表（循環(huán)鏈表、雙向鏈表、帶頭結(jié)點(diǎn)的鏈表等）的表示和基本操作的實(shí)現(xiàn)；循

23、環(huán)鏈表：循環(huán)單鏈表：表尾結(jié)點(diǎn)的next域指向l，表中沒有指針域?yàn)閚ull的結(jié)點(diǎn)，因此循環(huán)單鏈表的判空條件是看它的頭結(jié)點(diǎn)的指針域是否等于頭指針；循環(huán)單鏈表在任何一個(gè)位置上插入和刪除操作都是等價(jià)的，無(wú)需判斷是否表尾；循環(huán)單鏈表可以從表中任一結(jié)點(diǎn)開始遍歷整個(gè)鏈表。循環(huán)單鏈表不設(shè)頭指針而只設(shè)尾指針，可使一些操作效率更高。循環(huán)雙鏈表：與循環(huán)單鏈表不同的是，循環(huán)雙鏈表中頭結(jié)點(diǎn)的prior指針還指向表尾結(jié)點(diǎn)；在循環(huán)雙鏈表l中，某結(jié)點(diǎn)*p為尾結(jié)點(diǎn)時(shí)，p->next=l；當(dāng)循環(huán)雙鏈表為空時(shí)，對(duì)其頭結(jié)點(diǎn)*p，有p->prior=p->next=l。雙向鏈表：其結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向直接后繼，

24、另一個(gè)指向直接前趨，雙向鏈表的插入、刪除結(jié)點(diǎn)算法的時(shí)間復(fù)雜度為o(1)。雙向鏈表結(jié)構(gòu)的定義：typedef struct dulnodeelemtype data;struct lnode *prior,*next;dulnode, *dulinklist;雙向鏈表的插入操作：/只給出關(guān)鍵代碼段/在結(jié)點(diǎn)*p之后插入值為e的新結(jié)點(diǎn)*ss->data=e;s->next=p->next;p->next->prior=s;/語(yǔ)句執(zhí)行順序不唯一，但這兩步必須在最后一步之前s->prior=p;p->next=s;/在結(jié)點(diǎn)*p之前插入值為e的新結(jié)點(diǎn)*ss->

25、;data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;雙向鏈表的刪除操作：/只給出關(guān)鍵代碼段/刪除結(jié)點(diǎn)*p的后繼結(jié)點(diǎn)*q，并用e返回其值e=q->data;p->next=q->next;q->next->prior=p;free(q);/刪除結(jié)點(diǎn)*q的前趨*p，并用e返回其值e=p->data;q->prior=p->prior;p->prior->next=q;free(p);帶頭結(jié)點(diǎn)的鏈表：帶頭結(jié)點(diǎn)的鏈表結(jié)構(gòu)定義：typ

26、edef struct lnode/結(jié)點(diǎn)類型elemtype data;struct lnode *next;*link,*position;typedef struct/鏈表類型link head,tail;/分別指向鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)int length;/線性表中元素的個(gè)數(shù)linklist;ch3棧與隊(duì)列（1）棧和隊(duì)列的基本概念；棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)及其存儲(chǔ)特點(diǎn)；棧：限定在表尾進(jìn)行插入或刪除操作（頭進(jìn)尾出）的線性表，表尾稱為棧頂（top），表頭稱為棧底（bottom），不含任何元素的棧稱為空棧，棧又被稱為后進(jìn)先出（lifo）線性表。隊(duì)列：只允許在表的一端進(jìn)行插入，另一端

27、進(jìn)行刪除操作（尾進(jìn)頭出），允許插入的一端叫做隊(duì)尾（rear）， 允許刪除的一端叫做隊(duì)頭（front），是一種先進(jìn)先出（fifo）的線性表。棧的基本操作：initstack(&s) 初始化，構(gòu)造一個(gè)空棧sstackempty(s) 棧s判空stacklength(s) 求棧長(zhǎng)，即棧s的元素個(gè)數(shù)push(&s,x) 入棧，插入元素為x的新棧頂元素pop(&s,x) 出棧，刪除棧s的棧頂元素，并用x返回其值gettop(s,&x) 取棧頂，用x返回棧s的棧頂元素clearstack(&s) 將棧s清空destroystack(&s) 銷毀棧，并釋放其存

28、儲(chǔ)空間棧的順序存儲(chǔ)（順序棧）：可能發(fā)生上溢基本操作：/只給出關(guān)鍵語(yǔ)句initstack(&s) /棧滿條件s.top-s.base=s.stacksizes.top=s.base;s.stacksize=initsize; /?？諚l件s.top=s.basegettop(s, &e)e=*(s.top-1);push(&s,e)*s.top+=e;/入棧時(shí)棧頂指針先加1，再送值到棧頂元素pop(&s,&e)e=*-s.top;/出棧時(shí)先取棧頂元素值，再將棧頂指針減1棧的鏈?zhǔn)酱鎯?chǔ)（鏈棧）：便于多個(gè)棧共享存儲(chǔ)空間和提高其效率，不存在棧滿上溢的情況，規(guī)定鏈棧沒

29、有頭結(jié)點(diǎn)，lhead指向棧頂元素?；静僮鳎?只給出關(guān)鍵語(yǔ)句initstack(&s)/初始化p->next=s->next;s->next=p;push(&s,e)/入棧p->data=e;s->next=p;p->next=s->next;pop(&s,&e)/出棧p=s->next;e=p->data; s->next=p->next;free(p);destroystack（&s）/銷毀棧p=s;s=s->next;free(p);隊(duì)列的鏈?zhǔn)酱鎯?chǔ)（鏈隊(duì)列）：基本操作：/只給出

30、關(guān)鍵語(yǔ)句initqueue(&q)/初始化q.front=q.rear=(queueptr)malloc(sizeof(qnode);q.front->next=null;destroyqueue(&q)/銷毀隊(duì)列q.rear=q.front->next;free(q.front);q.front=q.rear;enqueue(&q,e)/入隊(duì)p->data=e;p->next=null;q.rear->next=p;q.rear=p;dequeue（&q,&e）/出隊(duì)p=q.front->next;e=p->d

31、ata;q.front->next=p->next;if(q.rear=p)q.rear=q.front;free(p);隊(duì)列的順序存儲(chǔ)（循環(huán)隊(duì)列）：約定初始化建空隊(duì)列時(shí)，令front=rear=0，每當(dāng)插入新的元素時(shí)，尾指針增1，當(dāng)刪除隊(duì)列元素時(shí)，頭指針增1，因此在非空隊(duì)列中，頭指針始終指向頭元素，尾指針始終指向隊(duì)列尾元素的下一個(gè)位置* 如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列，則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度，若用戶無(wú)法預(yù)估所用隊(duì)列的最大長(zhǎng)度，宜采用鏈隊(duì)列（2）循環(huán)隊(duì)列的判滿、判空方法；方法一：另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿方法二：犧牲一個(gè)單元來(lái)區(qū)分隊(duì)空和隊(duì)滿，入隊(duì)時(shí)少用一個(gè)隊(duì)列單元

32、，約定以隊(duì)頭指針在隊(duì)尾指針的下一位置作為隊(duì)滿的標(biāo)志隊(duì)滿條件：(q.rear+1)%maxsize=q.front隊(duì)空條件：q.rear=q.front隊(duì)列中元素個(gè)數(shù)：（q.rear-q.front+maxsize）%maxsize（3）棧和隊(duì)列的應(yīng)用棧的應(yīng)用：數(shù)制轉(zhuǎn)換、括號(hào)匹配、表達(dá)式求值、迷宮求解、實(shí)現(xiàn)遞歸隊(duì)列的應(yīng)用：層次遍歷、解決主機(jī)與外部設(shè)備之間速度不匹配的問(wèn)題，解決由多用戶引起的資源競(jìng)爭(zhēng)問(wèn)題（4）遞歸過(guò)程的特點(diǎn)及實(shí)現(xiàn)方法；遞歸的兩個(gè)必要條件：1) 遞歸表達(dá)式（遞歸體）2) 邊界條件（遞歸出口）* 遞歸的精髓在于能否將原始問(wèn)題轉(zhuǎn)的為屬性相同但規(guī)模較小的問(wèn)題（5）特殊矩陣的壓縮儲(chǔ)存； 數(shù)組

33、的存儲(chǔ)結(jié)構(gòu)：行優(yōu)先：loc(i,j)=loc(0,0)+(b2·i+j)l列優(yōu)先：loc(i,j)=loc(0,0)+(b2·j+i)l 特殊矩陣的壓縮存儲(chǔ)：對(duì)稱矩陣：將n2個(gè)元素壓縮存儲(chǔ)到n(n+1)/2個(gè)元素的空間中，可以行序?yàn)橹餍虼鎯?chǔ)基下三角（含對(duì)角線）中的元素，以一維數(shù)組san(n+1)/2作為n價(jià)對(duì)稱矩陣a的存儲(chǔ)結(jié)構(gòu)，則sak和矩陣元aij之間存在著一一對(duì)應(yīng)關(guān)系：k= i(i-1)2+j-1, &ij (下三角區(qū)和主對(duì)角線元素)j(j-1)2+i-1, &i<j (上三角區(qū)元素aij=aji)=tm×n稀疏矩陣：假設(shè)在m×

34、n的矩陣中，有t個(gè)元素不為零，令稱為矩陣的稀疏因子，通常認(rèn)0.05時(shí)稱為稀疏矩陣，存儲(chǔ)時(shí)只存儲(chǔ)稀疏矩陣的非零元，可用三元組順序表和十字鏈表兩種方式存儲(chǔ)。行號(hào)列號(hào)元素值ije三元組表格式：十字鏈表：在鏈表中，每個(gè)非零元可用一個(gè)含5個(gè)域的結(jié)點(diǎn)表示，其中i、j和e這3個(gè)域分別表該非零元所在的行、列和非零元的值，向右域right用以鏈接同一行中下一個(gè)非零元，向下域down用以鏈接同一列中下一個(gè)非零元 /十字鏈表結(jié)構(gòu)定義 typdef struct olnode int i,j;elemtype e;struct olnode *right,*down; olnode;*olink; typedef s

35、tructolink *rhead,*chead;int mu,nu,tu; crosslist;ch4廣義表的基本概念、存儲(chǔ)結(jié)構(gòu)和基本操作廣義表的定義：廣義表一般記作ls=(1，2，n)其中，ls是廣義表(1，2，n)的名稱，n是它的長(zhǎng)度，i可以是單個(gè)元素，也可以是廣義表，分別稱為ls的原子和子表，當(dāng)廣義表ls非空時(shí)，稱第一個(gè)元素1為ls的表頭(head)，稱其余元素組成的表(2，3，n)是ls的表尾(tail)幾類廣義表：a=()a是一個(gè)空表，它的長(zhǎng)度為零b=(e)列表b只有一個(gè)原子e，b的長(zhǎng)度為1c=(a,(b,c,d)列表c長(zhǎng)度為2，兩個(gè)元素分別為原子a和子表(b,c,d)d=(a,b

36、,c)列表d的長(zhǎng)度為3，3個(gè)元素都是列表，代入a、b和c的值后，有d=(),(e),(a,(b,c,d)e=(a,e)列表e是一個(gè)遞歸的表，它的長(zhǎng)度為2，深度為廣義表的存儲(chǔ)結(jié)構(gòu)：頭尾鏈表、擴(kuò)展線性鏈表擴(kuò)展線性鏈表中結(jié)點(diǎn)的類型：表結(jié)點(diǎn)：tag=1hptp原子結(jié)點(diǎn)：tag=0atomtp廣義表的主要操作：gethead(ls) 取表頭（第一個(gè)元素）gettail(ls) 取表尾（除第一個(gè)元素外其余元素組成的表）ch5樹和二叉樹（1）樹與森林的基本概念樹的定義：樹是n(n0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：(1) 有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)；(2) 當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m&g

37、t;0)個(gè)互不相交的有限集t1，t2，tm，其中每一個(gè)集合本身又是一棵樹，并稱為根的子樹。樹是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，樹作為一種邏輯結(jié)構(gòu)，同時(shí)也是一種分層結(jié)構(gòu)。樹的特點(diǎn)：1) 樹的根結(jié)點(diǎn)沒有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)2) 樹中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)樹的一些基本術(shù)語(yǔ)：結(jié)點(diǎn)的度：樹中一個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)數(shù)樹的度：樹中結(jié)點(diǎn)的最大度數(shù)分支結(jié)點(diǎn)：度大于0的結(jié)點(diǎn)（非終端結(jié)點(diǎn)）葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)（終端結(jié)點(diǎn)）結(jié)點(diǎn)的層次：從根開始定義起，根為第一層，根的孩子為第二層，若某結(jié)點(diǎn)在第l層，則其子樹的根就在第l+1層樹的深度（高度）：樹中結(jié)點(diǎn)的最大層次森林：m(m>0)棵互不相交

38、的樹的集合，對(duì)樹中的每個(gè)結(jié)點(diǎn)而言，基子樹的集合即為森林* 注：由于樹中的分支是有向的，所以樹中的路徑是從上到下的，同一雙親結(jié)點(diǎn)的兩個(gè)孩子結(jié)點(diǎn)之間不存在路徑樹的性質(zhì)：1) 樹中結(jié)點(diǎn)數(shù)=所有結(jié)點(diǎn)的度數(shù)(樹中的邊數(shù))+12) 度為m的樹中第i層上至多有mi-1個(gè)結(jié)點(diǎn)(i1)3) 高度為h的m叉樹至多有(mh-1)/(m-1)個(gè)結(jié)點(diǎn)4) 具有n個(gè)結(jié)點(diǎn)的m叉樹的最小高度為<logm(n(m-1)+1)>（<x>表示不小于x的最小整數(shù)）（2）二叉樹的定義及6大性質(zhì)二叉樹的定義：二叉樹是別一種樹型結(jié)構(gòu)，其特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且二叉樹的子

39、樹有左右之分，其次序不能任意顛倒二叉樹的性質(zhì)：性質(zhì)1：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i1)性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)(k1)滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹完全二叉樹：深度為k的有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱之為完全二叉樹，其特點(diǎn)是：(1) 葉子結(jié)點(diǎn)只可能在層次最大的兩層出現(xiàn)；(2) 對(duì)任一結(jié)點(diǎn)，若其右分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1性質(zhì)3：對(duì)任何一棵二叉樹t，如果其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1，設(shè)b為分支數(shù)

40、，n為結(jié)點(diǎn)總數(shù)，則有n=n1+2n2+1=b+1性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為log2n+1（x表示不大于x的最大整數(shù)）性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按編號(hào)（從第1層到第log2n+1層，每層從左到右），則對(duì)任一結(jié)點(diǎn)i(1in)，有：1) 如果i=1則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；如果i>1，則其雙親parent(i)是結(jié)點(diǎn)i/2（x表示不大于x的最大整數(shù)），即當(dāng)i為偶數(shù)時(shí)，其雙親為結(jié)點(diǎn)i/2；當(dāng)i為奇數(shù)時(shí)，其雙親為結(jié)點(diǎn)(i-1)/22) 如果2i>n，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子lchild(i)是結(jié)點(diǎn)2i3) 如果2i+1>n

41、，則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子rchild(i)是結(jié)點(diǎn)2i+1性質(zhì)6： 給定n個(gè)節(jié)點(diǎn)，能構(gòu)成h(n)種不同的二叉樹。（嚴(yán)版教材未給出，科大考綱涉及）*注：h(n)為卡特蘭數(shù)的第n項(xiàng)。計(jì)算方法為：hn=c2nnn+1（3）二叉樹的順序儲(chǔ)存與鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)順序存儲(chǔ)：約定用一組地址連續(xù)的存儲(chǔ)單元依次自上而下，自左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素，即將完全二叉樹上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為i-1的分量中，以0表示不存在的結(jié)點(diǎn)，這種順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹。結(jié)構(gòu)定義：#define maxsize 100/二叉樹最大結(jié)點(diǎn)數(shù)typedef telemtype sqbitreemaxsiz

42、e;/0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)sqbitree bt;* 最壞情況：一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹，需要長(zhǎng)度為2k-1的一維數(shù)組鏈?zhǔn)酱鎯?chǔ)：二叉鏈表結(jié)點(diǎn)包含3個(gè)域，數(shù)據(jù)域和左、右指針域（三叉鏈表還增加了指向其雙親結(jié)點(diǎn)的parent指針域），鏈表的頭指針指向二叉樹的根結(jié)點(diǎn)，易證在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域。結(jié)構(gòu)定義：typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;bitnode,*bitree;（4）二叉樹的先序、中序、后序三種遍歷方式的關(guān)系以及實(shí)現(xiàn)；層序遍歷的實(shí)現(xiàn)先序遍歷：根左右若二叉樹非空，則先

43、訪問(wèn)根結(jié)點(diǎn)，然后先序遍歷左子樹，最后先序遍歷右子樹（遞歸過(guò)程）/算法實(shí)現(xiàn)：先序遍歷的遞歸算法bool preordertraverse(bitree t,bool(*visit)(telemtype e)if(t)if(visit(t->data)if(preordertraverse(t->lchild,visit)if(preordertraverse(t->rchild,visit) return true;return false;else return true;/preordertraverse/先序建立二叉樹：按先序依次輸入二叉樹中結(jié)點(diǎn)的值，空格表示空樹bool

44、 createbitree(bitree &t)scanf(&ch);if(ch= ) t=null;elseif(!(t=(bitnode *)malloc(sizeof(bitnode) return false;t->data=ch;createbitree(t->lchild);createbitree(t->rchild);return true;/createbitree中序遍歷：左根右若二叉樹非空，則先中序遍歷左子樹，然后訪問(wèn)根結(jié)點(diǎn)，最后中序遍歷右子樹（遞歸過(guò)程）/算法實(shí)現(xiàn)：中序遍歷的非遞歸算法（棧實(shí)現(xiàn)）bool inordertraverse1

45、(bitree t,bool(*visit)(telemtype e)initstack(s);push(s,t); /根指針進(jìn)棧while(!stackempty(s)while(gettop(s,p)&&p)push(s,p->lchild);/向左走到盡頭pop(s,p);/空指針退棧if(!stackempty(s)/訪問(wèn)結(jié)點(diǎn)，向右一步pop(s,p);if(!visit(p->data) return false;push(s,p->rchild);/inordertraverse1return true;/inordertraverse/第2種非遞

46、歸算法bool inordertraverse2(bitree t,bool(*visit)(telemtype e)initstack(s);p=t;while(p|!stackempty(s)if(p)push(s,p);p=p->lchild;elsepop(s,p);if(!visit(p->data) return false;p=p->rchild;return true;/inodertraverse2后序遍歷：左右根若二叉樹非空，則先后序遍歷左子樹，然后后序遍歷右子樹，最后訪問(wèn)根結(jié)點(diǎn)（遞歸過(guò)程）/算法實(shí)現(xiàn)：后序遍歷的遞歸算法bool postordertrav

47、erse(bitree t,bool(*visit)(telemtype e)if(t)if(postordertraverse(t->lchild,visit)if(postordertraverse(t->rchild,visit)if(visit(t->data) return true;return false;else return true;/postordertraverse層次遍歷：從上到下、從左到右按層次遍歷二叉樹/算法描述（隊(duì)列實(shí)現(xiàn)）void levelordertraverse(bitree t,bool(*visit)(telemtype e)init

48、queue(q);p=t;visit(p->data);/ 訪問(wèn)根節(jié)點(diǎn)enqueue(q,p);/根結(jié)點(diǎn)入隊(duì)while(p|!queueempty(q)dequeue(q,p);/隊(duì)頭元素出隊(duì)visit(p->data);/訪問(wèn)當(dāng)前節(jié)點(diǎn)if(p->lchild)enqueue(q,p->lchild);/若存在左孩子，左孩子進(jìn)隊(duì)列if(p->rchild)enqueue(q,p->rchild);/若存在右孩子，右孩子進(jìn)隊(duì)列/levelordertraverse由遍歷序列構(gòu)造二叉樹：1) 先序遍歷中，第一個(gè)結(jié)點(diǎn)一定是二叉樹的根結(jié)點(diǎn)2) 中序遍歷中，根結(jié)點(diǎn)必然

49、將中序序列分割成兩個(gè)子序列3) 后序序列的最后一個(gè)結(jié)點(diǎn)一定是二叉樹的根結(jié)點(diǎn)4) 由二叉樹的遍歷能否唯一地確定一棵二叉樹先序中序后序?qū)有蛳刃?#215;×中序后序××層序××（5）線索二叉樹的基本概念與構(gòu)造方法線索二叉樹：引入線索二叉樹的是為了加快查找結(jié)點(diǎn)前驅(qū)和后繼的速度規(guī)定：若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rchild域指示其右孩子，否則令rchild域指示其后繼。結(jié)點(diǎn)增加兩個(gè)標(biāo)志域ltag和rtag，結(jié)點(diǎn)結(jié)構(gòu)變?yōu)椋簂childltagdatartagrchild其中：ltag

50、= 0 lchild域指示結(jié)點(diǎn)的左孩子1 lchild域指示結(jié)點(diǎn)的前驅(qū) rtag= 0 lchild域指示結(jié)點(diǎn)的右孩子1 lchild域指示結(jié)點(diǎn)的后繼結(jié)構(gòu)定義：線索鏈表/指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹/對(duì)typedef enum pointertaglink,thread;typedef struct bithrnodetelemtype data;struct bithrnode *lchild,*rchild;pointertag ltag,rtag;bithrnode,*bithrtree;線索二叉樹的構(gòu)造：線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)

51、或后繼的線索，而前驅(qū)或后繼的信息只有遍歷時(shí)才能得到，因此，線索化的過(guò)程即為在遍歷的過(guò)程中修改空指針的過(guò)程。中序建立中序線索化鏈表：bool inorderthreading1(bitree &thrt,bithrtree t)/構(gòu)造算法1/附設(shè)一個(gè)指針pre始終指向剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)/若指針p指向當(dāng)前訪問(wèn)的結(jié)點(diǎn)，則pre指向它的前驅(qū)if(!(thrt=(bithrtree)malloc(sizeof(bithrnode)return false;thrt->ltag=link;thrt->rtag=thread;thrt->rchild=thrt;if(!t) thrt

52、->lchild=thrt;elsethrt->lchild=t;pre=thrt;inthreading(t);pre->lchild=thrt;pre->rtag=thread;thrt->rchild=pre;return true;/inorderthreading1void inthreading(bithrtree p)/構(gòu)造算法2if(p)inthreading(p->lchild);if(!p->lchild)p->ltag=thread;p->lchild=pre;if(!pre->rchild)pre->rtag=thread;pre->rchid=p;pre=p;inthreading(p->rchild);/inthreading* 中序線索樹中結(jié)點(diǎn)前驅(qū)的后繼的確定：根據(jù)中序遍歷的規(guī)律，結(jié)點(diǎn)的后繼應(yīng)是遍