部分習題參考答案(數(shù)據(jù)結(jié)構(gòu) 李春葆).ppt

1、練習題2 習題2.2、2.3、2.4、2.5和2.6。,2.2 設計一個算法，將x插入到一個有序（從小到大排序）的線性表（順序存儲結(jié)構(gòu)）的適當位置上，并保持線性表的有序性。,void Insert(SqList * ,2.3 設計一個算法，將一個帶頭結(jié)點的數(shù)據(jù)域依次為a1，a2，an（n3）的單鏈表的所有結(jié)點逆置，即第一個結(jié)點的數(shù)據(jù)域變?yōu)閍n，最后一個結(jié)點的數(shù)據(jù)域為a1。,void Reverse(LinkList */讓p指向下一個結(jié)點 ,2.4 設有一個雙鏈表，每個結(jié)點中除有prior、data和next三個域外，還有一個訪問頻度域freq，在鏈表被起用之前，其值均初始化為零。每當進行Lo

2、cateNode(h，x)運算時，令元素值為x的結(jié)點中freq域的值加1，并調(diào)整表中結(jié)點的次序，使其按訪問頻度的遞減序排列，以便使頻繁訪問的結(jié)點總是靠近表頭。試寫一符合上述要求的LocateNode運算的算法。,bool LocateNode(DLinkList *h,ElemType x) DLinkList *p=h-next,*q; while (p!=NULL ,2.5 設ha=(a1,a2,an)和hb=(b1,b2, ,bm) 是兩個帶頭結(jié)點的循環(huán)單鏈表，編寫將這兩個表合并為帶頭結(jié)點的循環(huán)單鏈表hc的算法。,void Merge(LinkList *ha, LinkList *hb

3、, LinkList */構(gòu)成循環(huán)單鏈表 free(hb)；/釋放hb單鏈表的頭節(jié)點 ,2.6 設非空線性表ha和hb都用帶頭節(jié)點的循環(huán)雙鏈表表示。設計一個算法Insert(ha,hb,i)。其功能是：i=0時，將線性表hb插入到線性表ha的最前面；當i0時，將線性表hb插入到線性表ha中第i個節(jié)點的后面；當i大于等于線性表ha的長度時，將線性表hb插入到線性表ha的最后面。,void Insert(DLinkList * ,if (i=0)/將hb的所有數(shù)據(jù)結(jié)點插入到ha的頭結(jié)點和第1個數(shù)據(jù)結(jié)點之間 p=hb-prior;/p指向hb的最后一個結(jié)點/ p-next=ha-next;/將*p鏈

4、到ha的第1個數(shù)據(jù)結(jié)點前面 ha-next-prior=p; ha-next=hb-next; hb-next-prior=ha; /將ha頭結(jié)點與hb的第1個數(shù)據(jù)結(jié)點鏈起來 else if (inext; while (jnext; j+; q=p-next;/q指向*p結(jié)點的后繼結(jié)點/ p-next=hb-next;/hb-prior指向hb的最后一個結(jié)點 hb-next-prior=p; hb-prior-next=q; q-prior=hb-prior; ,else/將hb鏈到ha之后 ha-prior-next=hb-next; /ha-prior指向ha的最后一個結(jié)點 hb-nex

5、t-prior=ha-prior; hb-prior-next=ha; ha-prior=hb-prior; free(hb);/釋放hb頭結(jié)點 ,練習題3 習題3.1、3.2、3.3、3.4和3.6。,3.1 有5個元素，其進棧次序為：A、B、C、D、E，在各種可能的出棧次序中，以元素C、D最先出棧（即C第一個且D第二個出棧）的次序有哪幾個？,答：要使C第一個且D第二個出棧，應是A進棧，B進棧，C進棧，C出棧，D進棧，D出棧，之后可以有以下幾種情況： （1）B出棧，A出棧，E進棧，E出棧，輸出序列為CDBAE； （2）B出棧，E進棧，E出棧，A出棧，輸出序列為CDBEA； （3）E進棧，E出

6、棧，B出棧，A出棧，輸出序列為CDEBA。 所以可能的次序有：CDBAE、CDBEA、CDEBA。,3.2 假設以I和O分別表示進棧和出棧操作，棧的初態(tài)和終棧均為空，進棧和出棧的操作序列可表示為僅由I和O組成的序列。 （1）下面所示的序列中哪些是合法的？ A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO （2）通過對（1）的分析，寫出一個算法判定所給的操作序列是否合法。若合法返回1；否則返回0。（假設被判定的操作序列已存入一維數(shù)組中）。,解：（1）A、D均合法，而B、C不合法。因為在B中，先進棧一次，立即出棧三次，這會造成棧下溢。在C中共進棧五次，出棧三次

7、，棧的終態(tài)不為空。,（2）本題使用一個鏈棧來判斷操作序列是否合法，其中A為存放操作序列的字符數(shù)組，n為該數(shù)組的元素個數(shù)（這里的ElemType類型設定為char）。對應的算法如下： int judge(char A,int n) int i; ElemType x; LiStack *ls; InitStack(ls); for (i=0;in;i+) if (Ai=I)/進棧 Push(ls,Ai); else if (Ai=O)/出棧 if (StackEmpty(s) return 0;/?？諘r返回0 else Pop(ls,x); else return 0;/其他值無效退出 retu

8、rn (StackEmpty(ls);/棧為空時返回1；否則返回0 ,3.3 假設表達式中允許包含3種括號：圓括號、方括號和大括號。編寫一個算法判斷表達式中的括號是否正確配對。,解：用棧來判斷。,3.4 設從鍵盤輸入一整數(shù)序列a1，a2，.an，試編程實現(xiàn)：當ai0時，ai進隊，當ai0時，將隊首元素出隊，當ai=0時，表示輸入結(jié)束。要求將隊列處理成環(huán)形隊列，入隊和出隊操作單獨編寫算法，并在異常情況時（如隊滿）打印出錯。,typedef struct ququeue ElemType dataQueueSize; int front,rear;/隊首和隊尾指針 SqQueue;,void ma

9、in() ElemType a,x; SqQueue *qu;/定義隊列 qu=(SqQueue *)malloc(sizeof(SqQueue);/隊列初始化 qu-rear=qu-front=0; while (1) printf(輸入a值:);scanf(%d, ,3.6 輸入n（由用戶輸入）個10以內(nèi)的數(shù)，每輸入i（0i9），就把它插入到第i號隊列中。最后把10個隊中非空隊列，按隊列號從小到大的順序串接成一條鏈，并輸出該鏈的所有元素。,typedef struct node int data; struct node *next; QNode;,void Insert(QNode *Q

10、H,QNode *QT,int x) /將x插入到相應隊列中 QNode *s; s=(QNode *)malloc(sizeof(QNode);/創(chuàng)建一個節(jié)點 s-data=x;s-next=NULL; if (QHx=NULL)/對應的隊列為空隊時 QHx=s; QTx=s; else QTx-next=s; /將*s節(jié)點鏈到QTx所指節(jié)點之后 QTx=s;/讓QTx仍指向尾節(jié)點 ,void Create(QNode *QH,QNode *QT)/根據(jù)用戶輸入創(chuàng)建隊列 int n,x,i; printf(n:); scanf(%d, ,void Link(QNode *QH,QNode *

11、QT)/將非空隊列鏈接起來并輸出 QNode *head,*tail;/總鏈表的首節(jié)點指針和尾節(jié)點指針 int first=1,i; for (i=0;inext=QHi; tail=QTi; printf(n輸出所有元素:); while (head!=NULL) printf(%d ,head-data); head=head-next; printf(n); ,void main() int i; QNode *QHMAXQNode,*QTMAXQNode; /各隊列的隊頭QH和隊尾指針QT for (i=0;iMAXQNode;i+) QHi=QTi=NULL;/置初值 Create(

12、QH,QT);/建立隊列 Link(QH,QT);/鏈接各隊列并輸出 ,練習題4 習題4.1、4.2和4.3。,4.1 采用順序結(jié)構(gòu)存儲串，編寫一個實現(xiàn)串通配符匹配的算法pattern_index()，其中的通配符只有?，它可以和任一字符匹配成功，例如，pattern_index(?re，there are)返回的結(jié)果是2。,int Pattern_Index(SqString substr,SqString str) int i,j,k; for (i=0;i=substr.length) return(i); return(-1); ,4.2 有兩個串s1和s2，設計一個算法求一個這樣的串

13、，該串中的字符是s1和s2中公共字符（不是子串關系）。,SqString CommChar(SqString s1,SqString s2) SqString s3; int i,j,k=0; for (i=0;is1.length;i+) for (j=0;js2.length;j+) if (s2.dataj=s1.datai) break; if (js2.length)/s1.datai是公共字符 s3.datak=s1.datai; k+; s3.length=k; return s3; ,4.3 設目標為t=abcaabbabcabaacbacba，模式p=abcabaa。 （1）

14、計算模式p的nextval函數(shù)值。 （2）不寫算法，只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。,練習題55.1和5.2題。,5.1 已知An為整數(shù)數(shù)組，編寫一個遞歸算法求n個元素的平均值。,5.2 設有一個不帶表頭節(jié)點的單鏈表L，其節(jié)點類型如下： typedef int ElemType; typedef struct node ElemType data; struct node *next; Node; 設計如下遞歸算法： （1）求以L為首節(jié)點指針的單鏈表的節(jié)點個數(shù)； （2）正向顯示以L為首節(jié)點指針的單鏈表的所有節(jié)點值； （3）反向顯示以L為首節(jié)點指針的單鏈表的所有節(jié)點值； （4

15、）刪除以L為首節(jié)點指針的單鏈表中值為x的第一個節(jié)點； （5）刪除以L為首節(jié)點指針的單鏈表中值為x的所有節(jié)點； （6）輸出以L為首節(jié)點指針的單鏈表中最大節(jié)點值； （7）輸出以L為首節(jié)點指針的單鏈表中最小節(jié)點值。,練習題6 習題6.2、6.3、6.4、6.7和6.8。,6.2 n階對稱矩陣A采用壓縮存儲在一維數(shù)組B中，則B包含多少個元素？,6.3 設有三對角矩陣Ann（從A1,1開始），將其三對角線上元素逐行存于數(shù)組B1.m中，使Bk=Ai,j，求： （1）用i，j表示k的下標變換公式； （2）用k表示i，j的下標變換公式。,6.4 用十字鏈表表示一個有k個非0元素的mn的稀疏矩陣，則其總的節(jié)點數(shù)

16、為多少？,答：該十字鏈表有一個十字鏈表表頭節(jié)點，MAX(m,n)個行、列表頭節(jié)點。另外，每個非0元素對應一個節(jié)點，即k個元素節(jié)點。所以共有MAX(m,n)+k+1個節(jié)點。,6.7 設3個廣義表為：A=(a,b,c)，B=(A,(c,d)，C=(a,(B,A),(e,f)，請給出下列各運算的結(jié)果： （1）headA； （2）tailB； （3）headheadheadtailC,答：（1）headA=a （2）tailB=(c,d) （3）headheadheadtailC=headheadhead(B,A),(e,f) =headhead(B,A)= headB= head(A,(c,d)=A

17、=(a,b,c),6.8 設計一個算法Same(*g1,*g2)，判斷兩個廣義表g1和g2是否相同。,bool Same(GLNode *g1,GLNode *g2) if (g1=NULL ,練習題7 7.1、7.2、7.3、7.4、7.5、7.7、7.9,7.1 設二叉樹bt的一種存儲結(jié)構(gòu)如表7.1所示。其中，bt為樹根節(jié)點指針，lchild、rchild分別為節(jié)點的左、右孩子指針域，在這里使用節(jié)點編號作為指針域值，0表示指針域值為空；data為節(jié)點的數(shù)據(jù)域。請完成下列各題： （1）畫出二叉樹bt的樹形表示； （2）寫出按先序、中序和后序遍歷二叉樹bt所得到的節(jié)點序列； （3）畫出二叉樹b

18、t的后序線索樹。,表7.1 二叉樹bt的一種存儲結(jié)構(gòu),答：（1）二叉樹bt的樹形表示如圖7.1所示。,圖7.1 二叉樹bt的邏輯結(jié)構(gòu),圖7.2 二叉樹bt的后序線索化樹,（2）先序遍歷序列：abcedfhgij 中序遍歷序列：ecbhfdjiga 后序遍歷序列：echfjigdba （3）二叉樹bt的后序遍歷序列為echfjigdba，則后序線索樹如圖7.2所示。,7.2 已知一棵二叉樹的中序序列為cbedahgijf，后序序列為cedbhjigfa，給出該二叉樹樹形表示。,7.3 設給定權集合W=2,3,4,7,8,9，試構(gòu)造關于W的一棵哈夫曼樹，并求其帶權路徑長度WPL。 答：由權值集合W

19、極選的哈夫曼樹如圖7.4所示。其帶權路徑長度WPL=(9+7+8)2+43+(2+3)4=80。,7.4 一棵具有n個節(jié)點的完全二叉樹以順序方式存儲在數(shù)組A中，假設每個節(jié)點的元素為單個字符，沒有對應節(jié)點時A中元素取值為#。設計一個算法構(gòu)造該二叉樹的二叉鏈存儲結(jié)構(gòu)。,void Ctree(BTNode */遞歸構(gòu)造*b的右子樹 ,7.5 假設二叉樹中每個節(jié)點的值為單個字符，設計一個算法將一棵以二叉鏈方式存儲的二叉樹b轉(zhuǎn)換成對應的順序存儲結(jié)構(gòu)A。,void Ctree(BTNode *b,SqBTree A,int i) if (b!=NULL) Ai=b-data; Ctree(b-lchild

20、,A,2*i); Ctree(b-rchild,A,2*i+1); else Ai=#; ,7.7 假設二叉樹采用二叉鏈存儲結(jié)構(gòu)，t指向根節(jié)點，p所指節(jié)點為任一給定的節(jié)點，設計一個算法，輸出從根節(jié)點到p所指節(jié)點之間路徑。,int Path(BTNode *t,BTNode *s) BTNode *StMaxSize; BTNode *p; int i,flag,top=-1;/棧頂指針置初值 do while (t)/將t的所有左節(jié)點進棧 top+; Sttop=t; t=t-lchild; p=NULL; /p指向當前節(jié)點的前一個已訪問的節(jié)點 flag=1; /設置t的訪問標記為已訪問過,w

21、hile (top!=-1 /其他情況時返回0 ,7.9 假設二叉樹采用二叉鏈存儲結(jié)構(gòu)，設計一個算法判斷一棵二叉樹是否是對稱同構(gòu)。所謂對稱同構(gòu)是指其左右子樹的結(jié)構(gòu)是對稱的。 解：判斷二叉樹是否對稱同構(gòu)的遞歸模型如下： f(b)=true若b=NULL或b-lchild與b-rchild均為NULL f(b)=false若b-lchild與b-rchild中之一為NULL f(b)=f(b-lchild) ArcNode *p; printf(鄰接表:n); for (i=0;in;i+) p=G-adjlisti.firstarc; printf(%2d: ,i); while (p!=NUL

22、L) printf(%2d,p-adjvex); p=p-nextarc; printf(n); ,8.6 假設圖G采用鄰接表存儲，分別設計實現(xiàn)以下要求的算法： （1）求出圖G中每個頂點的出度； （2）求出圖G中出度最大的一個頂點，輸出該頂點編號； （3）計算圖G中出度為0的頂點數(shù)； （4）判斷圖G中是否存在邊。 解：對應（1）、（2）、（3）和（4）的功能的函數(shù)分別是OutDs()、MaxOutDs()、ZeroDs()和Arc()。,int OutDegree(ALGraph *G,int v) ArcNode *p; int n=0; p=G-adjlistv.firstarc; whi

23、le (p!=NULL) n+; p=p-nextarc; return n; ,void OutDs(ALGraph *G) /求出圖G中每個頂點的出度 int i; printf(1)各頂點出度:n); for (i=0;in;i+) printf( 頂點%d:%dn,i,OutDegree(G,i); ,void MaxOutDs(ALGraph *G) /求出圖G中出度最大的一個頂點 int maxv=0,maxds=0,i,x; for (i=0;in;i+) x=OutDegree(G,i); if (xmaxds) maxds=x; maxv=i; printf(2)最大出度:

24、頂點%d的出度=%dn,maxv,maxds); ,void ZeroDs(ALGraph *G) /計算圖G中出度為0的頂點數(shù) int i,x; printf(3)出度為0的頂點:); for (i=0;in;i+) x=OutDegree(G,i); if (x=0) printf(%2d,i); printf(n); ,void Arc(ALGraph *G) /判斷圖G中是否存在邊 int i,j; ArcNode *p; printf(4)輸入邊:); scanf(%d%d, ,練習9 教材中p271習題1、2、3和5。,9.1 對于A0.10有序表，采用二分查找法時，求成功和不成功

25、時的平均查找長度。并對于有序表12,18,24,35,47,50,62,83,90,115,134，當用二分查找法查找 90時，需進行多少次查找可確定成功；查找47時需進行多少次查找可確定成功；查找100時，需進行多少次查找才能確定不成功。,答：對于A0.10有序表構(gòu)造的判定樹如圖9.1(a)所示。因此有： ASLsucc= =3 ASLunsucc= =3.67,9.2 將整數(shù)序列4,5,7,2,1,3,6中的數(shù)依次插入到一棵空的二叉排序樹中，試構(gòu)造相應的二叉排序樹，要求用圖形給出構(gòu)造過程，不需編寫程序。,9.3 將整數(shù)序列4,5,7,2,1,3,6依次插入到一棵空的平衡二叉樹中，試構(gòu)造相應的平衡二叉樹，要求用圖形給出構(gòu)造過程，不需編寫程序。,9.5 編寫一個算法，判斷給定的二叉樹是否是二叉排序樹。,KeyType predt=-32768; /predt為全局變量,保存當前節(jié)點中序前趨的值,初值為- bool JudgeBST(BSTNode *bt) bool b1,b2; if (bt=NULL) return true; else b1=JudgeBST(bt-lchild);/判斷左子樹 if (!b1 | predt=bt-ke