數(shù)據(jù)結(jié)構(gòu)A習題課1

1、習題課一習題課一1.5 1.5 確定下列各程序段的程序步，確定劃線語句的執(zhí)行確定下列各程序段的程序步，確定劃線語句的執(zhí)行次數(shù)，計算它們的漸近時間復雜度。次數(shù)，計算它們的漸近時間復雜度。習題一（第習題一（第1818頁）頁）(1) i=1; k=0;(1) i=1; k=0; do do k=k+10k=k+10* *i; i+i; i+; ; while(i=n-1) while(i=n-1)答：答： 劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 n-1 n-1 。O(n)O(n)(2(2）i=1; x=0; i k(i=1; x=0; i k(循環(huán)次數(shù)循環(huán)次數(shù)) 2) 2* *i i do 1 1

2、 2 do 1 1 21 1nn 2 2 2 2 2 22 2nn x+; i=2x+; i=2* *i;i; 2 2k-1k-1 n 2 n 2k knn while while （inin）; 2; 2k kn, klogn, klog2 2n, k=n, k= loglog2 2n n 劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 loglog2 2n n 。O(logO(log2 2n)n)(3) for(int i=1;i=n;i+)(3) for(int i=1;i=n;i+) for(int j=1;j=i;j+) for(int j=1;j=i;j+) for (int k=1;k

3、=j;k+) for (int k=1;k=(y+1) while(x=(y+1)* *(y+1) (y+1) y+y+; nk; nk2 2劃線語句的執(zhí)行次數(shù)為劃線語句的執(zhí)行次數(shù)為 。O( )O( )nn#include #include #include seqlist0.h#include seqlist0.h#include conio.h#include conio.htemplate template void InterSection(SeqList &LA,SeqList &LB)void InterSection(SeqList &LA,SeqList &LB) int m=

4、LB.Length(); int m=LB.Length(); SeqList LC(10); SeqList LC(10); T x; T x; for (int i=1;i=m;i+) for (int i=1;i=m;i+) LB.Find(i,x); LB.Find(i,x); if (LA.Search(x) LC.Insert(LC.Length()+1,x); if (LA.Search(x) LC.Insert(LC.Length()+1,x); coutLC; coutLC; 2.1 2.1 利用線性表類利用線性表類LinearListLinearList提供的操作，實現(xiàn)兩個

5、集合的交和差運算。提供的操作，實現(xiàn)兩個集合的交和差運算。習題二（第習題二（第3737頁）頁）template template void Difference(SeqList &LA,SeqList &LB)void Difference(SeqList &LA,SeqList &LB) int m=LA.Length(); int m=LA.Length(); SeqList LC(10); SeqList LC(10); T x; T x; for (int i=1;i=m;i+) for (int i=1;i=m;i+) LA.Find(i,x); LA.Find(i,x); if (L

6、B.Search(x)=0) LC.Insert(LC.Length()+1,x); if (LB.Search(x)=0) LC.Insert(LC.Length()+1,x); coutLC; coutLC; void main()void main() SeqList LA(10),LB(10); SeqList LA(10),LB(10); for (int i=1;i=8;i+) LA.Insert(i,i); for (int i=1;i=8;i+) LA.Insert(i,i); for (i=1;i=3;i+) LB.Insert(i,i+3); for (i=1;i=3;i+

7、) LB.Insert(i,i+3); InterSection(LA,LB); InterSection(LA,LB); Difference(LA,LB); Difference(LA,LB); 2.2 (2) 2.2 (2) 在類在類LinearList LinearList 中增加一個成員函數(shù)，將順序表逆置，實現(xiàn)中增加一個成員函數(shù)，將順序表逆置，實現(xiàn)該函數(shù)并分析算法的時間復雜度。不利用類該函數(shù)并分析算法的時間復雜度。不利用類SeqList SeqList 提供的操作直接提供的操作直接實現(xiàn)。實現(xiàn)。template template void SeqList:Invert()void Se

8、qList:Invert() T e; T e; for (int i=0;i for (int i=0;ilength/2length/2;i+);i+) e=elementsi; e=elementsi; elementsi=elements elementsi=elementslength-i-1length-i-1; elementslength-i-1=e; elementslength-i-1=e; O(n)O(n)2.5 2.5 在類在類SingleListSingleList中增加一個成員函數(shù)，將單鏈表逆置運算，中增加一個成員函數(shù)，將單鏈表逆置運算，直接實現(xiàn)該函數(shù)并分析其時間復

9、雜度。直接實現(xiàn)該函數(shù)并分析其時間復雜度。template template void SingleList:invert() void SingleList:invert() Node Node * *p=first,p=first,* *q;q; first=NULL; first=NULL; while (p) while (p) q=p-link;q=p-link; p-link=first; p-link=first; first=p; first=p; p=q; p=q; 2.7 2.7 單鏈表中結(jié)點按元素值遞增鏈接，在類單鏈表中結(jié)點按元素值遞增鏈接，在類SingleListSing

10、leList中增加一個成員中增加一個成員函數(shù)，直接實現(xiàn)刪除結(jié)點值在函數(shù)，直接實現(xiàn)刪除結(jié)點值在a a至至b b之間的結(jié)點之間的結(jié)點(a(a b)b)。template template void SingleList:DeleteAb(T a,T b) void SingleList:DeleteAb(T a,T b) Node Node * *p=first,p=first,* *q=first;q=first; while (p & p-datadatadatadatalink; q=p; p=p-link; else else q-link=p-link; delete p; p=q-li

11、nk; q-link=p-link; delete p; p=q-link; 思考結(jié)點思考結(jié)點a a和和b b有沒有刪除掉？有沒有刪除掉？2 5 2 5 7 97 9 13 15 13 15firstfirsta=5a=5，b=13b=132.8 2.8 設有單循環(huán)鏈表類設有單循環(huán)鏈表類CircularListCircularList，要求在類，要求在類CircularListCircularList中增加一個中增加一個成員函數(shù)，在不增加新結(jié)點的情況下，直接實現(xiàn)兩個鏈表合并為一個鏈表成員函數(shù)，在不增加新結(jié)點的情況下，直接實現(xiàn)兩個鏈表合并為一個鏈表的算法，并分析其時間復雜度。的算法，并分析其時間

12、復雜度。/ / 解法解法1 1template template void Merge(CircularList &a, CircularList &b)void Merge(CircularList &a, CircularList &b) Node Node * *p=b.first;p=b.first; while (p-link!=b.first) while (p-link!=b.first) p=p-link; p=p-link; p-link=a.first-link; p-link=a.first-link; a.first-link=b.first-link; a.first

13、-link=b.first-link; b.first-link=b.first; b.first-link=b.first; b.length=0; b.length=0; / O(b.length)/ O(b.length)a ab b/ / 解法解法2 2 templatetemplatevoid Merge1(CircularList &a,CircularList &b)void Merge1(CircularList &a,CircularList &b) Node Node * *p=b.first-link;p=b.first-link; b.first-data=b.firs

14、t-link-data; b.first-data=b.first-link-data; b.first-link=a.first-link; b.first-link=a.first-link; a.first-link=p-link; a.first-link=p-link; p-link=p; p-link=p; b.first=p; b.first=p; b.length=0; b.length=0; / O(1)/ O(1)習題三（第習題三（第5050頁）頁）3.13.1 設設A A、B B、C C、D D、E E五個元素依次進棧五個元素依次進棧( (進棧后可立即出棧進棧后可立即出棧

15、) )，問能，問能否得到下列序列。若能得到，則給出相應的否得到下列序列。若能得到，則給出相應的pushpush和和poppop序列；若不能序列；若不能，則說明理由。，則說明理由。1) 1) A,B,C,D,E A,B,C,D,E 2)2) A,C,E,B,D A,C,E,B,D 3) C,A,B,D,E3) C,A,B,D,E 4) E,D,C,B,A4) E,D,C,B,A答：答：2 2）和）和3 3）不能。對）不能。對2 2）中的）中的E E，B B，D D而言，而言，E E最先出棧則表明，此最先出棧則表明，此時時B B和和D D均在棧中，由于，均在棧中，由于，B B先于先于D D進棧，所

16、以應有進棧，所以應有D D先出棧。同理先出棧。同理3 3）也）也不能。不能。(1)(1)能。能。 push,pop,push,pop,push,pop,push,pop,push,pop push,pop,push,pop,push,pop,push,pop,push,pop (4)(4)能。能。 push,push,push,push,push,pop,pop,pop,pop,poppush,push,push,push,push,pop,pop,pop,pop,pop3.2 3.2 設計共享棧。設計共享棧。 定義一個足夠大的?？臻g。該空間的兩端分別設為兩個棧的定義一個足夠大的棧空間。該空間

17、的兩端分別設為兩個棧的棧底，用棧底，用bottom1bottom1和和bottom2bottom2指示，讓兩個棧的棧頂，用指示，讓兩個棧的棧頂，用top1top1和和top2top2指示，都向中間伸展，直到兩個棧的棧頂相遇，才會發(fā)生指示，都向中間伸展，直到兩個棧的棧頂相遇，才會發(fā)生溢出。溢出。?？?，兩棧均空：?？?，兩棧均空：top1=0top1=0且且 top2=n-1top2=n-1棧滿：棧滿：top1=top2-1top1=top2-1 0 n-1 0 n-1 bottom1 top1 top2 bottom2 bottom1 top1 top2 bottom23.43.4寫出下列表達式的

18、后綴形式。寫出下列表達式的后綴形式。 /+ab+cd -b2*4ac -*ac/bc2 +*+abc/d+ef -*+ab+*cde*ac3.93.9 利用?？梢詸z查表達式中括號是否配對，試編寫算法實現(xiàn)之。利用?？梢詸z查表達式中括號是否配對，試編寫算法實現(xiàn)之。/若不匹配，則返回若不匹配，則返回true,true,否則返回否則返回false false /解法一解法一bool match(char a,int n) bool match(char a,int n) SeqStack s(n);SeqStack s(n);char c;char c;for (int i=0;in;i+)for (

19、int i=0;in;i+) if (ai=() s.Push(ai) if (ai=() s.Push(ai) /判棧滿？判棧滿？ else if (ai=) else if (ai=) if ( if (!s.Empty()!s.Empty() s.Pop(); ) s.Pop(); /繼續(xù)檢查繼續(xù)檢查 else else return true; /return true; /不匹配不匹配 if (if (!s.Empty()!s.Empty() ) return true; /return true; /不匹配不匹配return false; return false; /匹配匹配 /

20、解法二解法二 不用棧，用一個字符數(shù)組不用棧，用一個字符數(shù)組bool match(char a,int n) bool match(char a,int n) char cn;char cn;int top=-1;int top=-1;for (int i=0;in;i+)for (int i=0;i-1) if (top-1) stop=0; top-; stop=0; top-; /繼續(xù)檢查繼續(xù)檢查 else else return true; /return true; /不匹配不匹配 if (top-1) if (top-1) return true; /return true; /不匹

21、配不匹配return false; return false; /匹配匹配 /解法三解法三 不用棧，也不用數(shù)組，只用一個計數(shù)器不用棧，也不用數(shù)組，只用一個計數(shù)器top,top,記錄記錄“(”(”的個數(shù)的個數(shù)。bool match(char a,int n) bool match(char a,int n) int top=-1;int top=-1;for (int i=0;in;i+)for (int i=0;i-1) top-; if (top-1) top-; /繼續(xù)檢查繼續(xù)檢查 else else return true; /return true; /不匹配不匹配 if (top-1

22、) if (top-1) return true; /return true; /不匹配不匹配return false; return false; /匹配匹配 3.10 3.10 聲明并實現(xiàn)鏈式棧類聲明并實現(xiàn)鏈式棧類LinkedStackLinkedStack。template template class LinkedStack: public Stackclass LinkedStack: public Stack public:public:LinkedStack();LinkedStack();LinkedStack();LinkedStack();virtual bool IsEm

23、pty() const;virtual bool IsEmpty() const;virtual bool IsFull() const;virtual bool IsFull() const;virtual bool GetTop(T& x);virtual bool GetTop(T& x);virtual bool Push(const T x);virtual bool Push(const T x);virtual bool Pop();virtual bool Pop();virtual void SetNull();virtual void SetNull();private:p

24、rivate:Node Node * *top;top;/構(gòu)造函數(shù)構(gòu)造函數(shù)template template LinkedStack:LinkedStack()LinkedStack:LinkedStack() top=NULL;top=NULL; /析構(gòu)函數(shù)析構(gòu)函數(shù)template template LinkedStack:LinkedStack()LinkedStack:LinkedStack() Node Node * *q;q; while (top) while (top) q=top-link; q=top-link; delete top; delete top; top=q;

25、top=q; template template bool LinkedStack:IsEmpty() constbool LinkedStack:IsEmpty() const return !top;return !top; template template bool LinkedStack:IsFull() constbool LinkedStack:IsFull() const return false;return false;template template bool LinkedStack:GetTop(T &x)bool LinkedStack:GetTop(T &x) i

26、f (IsEmpty()if (IsEmpty() coutEmpty stackendl; return false; coutEmpty stackdata;x=top-data; return true;return true; template template bool LinkedStack:Push(const T x)bool LinkedStack:Push(const T x) Node Node * *q=new Node;q=new Node; q-data=x; q-data=x; q-link=top; q-link=top; top=q; top=q; retur

27、n true; return true; template template bool LinkedStack:Pop()bool LinkedStack:Pop() Node Node * *q=top;q=top; if (IsEmpty() if (IsEmpty() coutEmpty stackendl;coutEmpty stacklink; top=top-link; delete q; delete q; return true; return true; template template void LinkedStack:SetNull()void LinkedStack:

28、SetNull() Node Node * *q;q;while (top) while (top) q=top-link; q=top-link; delete top; delete top; top=q; top=q; 4.14.1給出三維數(shù)組元素給出三維數(shù)組元素AijkAijk的存儲地址的存儲地址loc(Aijk)loc(Aijk)。習題四（第習題四（第6868頁）頁）答：答： 設有三維數(shù)組聲明為設有三維數(shù)組聲明為AnAn1 1nn2 2nn3 3 ，每個元素占，每個元素占m m個存儲單元，個存儲單元，則則 loc(Aijk)=loc(A000)+mloc(Aijk)=loc(A000

29、)+m* *(i(i* *n n2 2* *n n3 3+j+j* *n n3 3+k)+k)4.24.2設三對角矩陣設三對角矩陣A An n n n, ,將其將其3 3條對角線上元素按對角線存入二維數(shù)組條對角線上元素按對角線存入二維數(shù)組B3nB3n中，使得中，使得Buv=AijBuv=Aij。求。求 （1 1）用）用i,ji,j表示表示u,vu,v的下標變換公式；的下標變換公式；)1)(1()1(2322211211100100000.00000.0nnnnaaaaaaaaaaa01a12a23a34a00a11a22a33a44a10a21a32a430 01 12 20 1 2 3 4

30、5 0 1 2 3 4 5 u=i-j+1u=i-j+1v=jv=j4.3 4.3 設三對角矩陣設三對角矩陣A An n n n, ,將其將其3 3條對角線上元素存入大小為條對角線上元素存入大小為(3n-2)(3n-2)的的一維數(shù)組一維數(shù)組BB中，使得中，使得Bk=AijBk=Aij。求。求 （1 1）用）用i,ji,j表示表示k k的下標變換公式；的下標變換公式； （2 2）用）用k k表示表示i,ji,j的下標變換公式的下標變換公式) 3 /) 1(23 / ) 1(kkjkik=2i+jk=2i+j)1)(1()1(2322211211100100000.00000.0nnnnaaaaa

31、aaaaaa00a01a10a11a12a21a22a230 1 2 3 4 5 6 7 80 1 2 3 4 5 6 7 85 5 65 5 65 5 65 5 6答：答：4.5 4.5 給出下列稀疏矩陣的行優(yōu)先和列優(yōu)先給出下列稀疏矩陣的行優(yōu)先和列優(yōu)先順序存儲的三元組表。順序存儲的三元組表。 4.6 4.6 對題圖對題圖4-54-5的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時數(shù)組的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時數(shù)組numnum和和kk的值。的值。5.2 5.2 設計一個遞歸算法，實現(xiàn)對一個有序表的順序搜索。設計一個遞歸算法，實現(xiàn)對一個有序表的順序搜索。習題五（第習題五（第8181頁）頁）templatetemplate

32、int SeqList:Search4(const T& x) constint SeqList:Search4(const T& x) const elementslength=1000; elementslength=1000; return Sch4(x,0); return Sch4(x,0); templatetemplateint SeqList:Sch4(const T& x,int i) constint SeqList:Sch4(const T& x,int i) const if (xelementsi) return 0;if (xelementsi) return 0;

33、 else if (x=elementsi) return +i; else if (x=elementsi) return +i; else return Sch4(x,i+1); else return Sch4(x,i+1); 6 63 39 94 411117 71 1121210108 86 65 52 25.3 5.3 畫出對長度為畫出對長度為1212的有序表進行對半查找的二叉判定樹的有序表進行對半查找的二叉判定樹，并求等概率搜索時，成功搜索的平均搜索長度，并求等概率搜索時，成功搜索的平均搜索長度解：解：1 1 二叉判定樹如下：二叉判定樹如下：成功搜索的平均搜索長度成功搜索的平均搜

34、索長度 由于第由于第i i層有層有2 2i i個結(jié)點，故平均搜索長度為：個結(jié)點，故平均搜索長度為：ASL ASL log log2 2(n+1) /P.77(n+1) /P.77習題六（第習題六（第107107頁）頁）6.26.2（2 2）對于三個結(jié)點）對于三個結(jié)點A A，B B和和C C，可分別組成多少不同的無序樹、有序，可分別組成多少不同的無序樹、有序樹和二叉樹？樹和二叉樹？答：（答：（1 1）無序樹：）無序樹：9 9棵棵 （2 2）有序樹：）有序樹：1212棵棵 （3 3）二叉樹：）二叉樹：3030棵棵6.3 6.3 （3 3）高度為）高度為h h的的k k叉樹的特點是：第叉樹的特點是：

35、第h h層的節(jié)點度為層的節(jié)點度為0 0，其余結(jié)點的度均，其余結(jié)點的度均為為k k。如果按從上到下，從左到右的次序從。如果按從上到下，從左到右的次序從1 1開始編號，則：開始編號，則： 各層的結(jié)點是多少？各層的結(jié)點是多少？第第i i層有層有k ki-1i-1個個 編號為編號為i i的結(jié)點的雙親的編號是多少？的結(jié)點的雙親的編號是多少？ (i-1)/k(i-1)/k 編號為編號為i i的結(jié)點的第的結(jié)點的第m m個孩子的編號是多少？個孩子的編號是多少？ k(i-1)+m+1k(i-1)+m+1 編號為編號為i i的結(jié)點的有有兄弟的條件是什么？的結(jié)點的有有兄弟的條件是什么？根據(jù)根據(jù)和和的結(jié)果有：的結(jié)果有：i k(i k(