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

1、習(xí)題課一習(xí)題課一1.5 1.5 確定下列各程序段的程序步，確定劃線語(yǔ)句的執(zhí)行確定下列各程序段的程序步，確定劃線語(yǔ)句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度。次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度。習(xí)題一（第習(xí)題一（第1818頁(yè)）頁(yè)）(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)答：答： 劃線語(yǔ)句的執(zhí)行次數(shù)為劃線語(yǔ)句的執(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 劃線語(yǔ)句的執(zhí)行次數(shù)為劃線語(yǔ)句的執(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劃線語(yǔ)句的執(zhí)行次數(shù)為劃線語(yǔ)句的執(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提供的操作，實(shí)現(xiàn)兩個(gè)

5、集合的交和差運(yùn)算。提供的操作，實(shí)現(xiàn)兩個(gè)集合的交和差運(yùn)算。習(xí)題二（第習(xí)題二（第3737頁(yè)）頁(yè)）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 中增加一個(gè)成員函數(shù)，將順序表逆置，實(shí)現(xiàn)中增加一個(gè)成員函數(shù)，將順序表逆置，實(shí)現(xiàn)該函數(shù)并分析算法的時(shí)間復(fù)雜度。不利用類該函數(shù)并分析算法的時(shí)間復(fù)雜度。不利用類SeqList SeqList 提供的操作直接提供的操作直接實(shí)現(xiàn)。實(shí)現(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中增加一個(gè)成員函數(shù)，將單鏈表逆置運(yùn)算，中增加一個(gè)成員函數(shù)，將單鏈表逆置運(yùn)算，直接實(shí)現(xiàn)該函數(shù)并分析其時(shí)間復(fù)

9、雜度。直接實(shí)現(xiàn)該函數(shù)并分析其時(shí)間復(fù)雜度。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é)點(diǎn)按元素值遞增鏈接，在類單鏈表中結(jié)點(diǎn)按元素值遞增鏈接，在類SingleListSing

10、leList中增加一個(gè)成員中增加一個(gè)成員函數(shù)，直接實(shí)現(xiàn)刪除結(jié)點(diǎn)值在函數(shù)，直接實(shí)現(xiàn)刪除結(jié)點(diǎn)值在a a至至b b之間的結(jié)點(diǎn)之間的結(jié)點(diǎn)(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é)點(diǎn)思考結(jié)點(diǎn)a a和和b b有沒有刪除掉？有沒有刪除掉？2 5 2 5 7 97 9 13 15 13 15firstfirsta=5a=5，b=13b=132.8 2.8 設(shè)有單循環(huán)鏈表類設(shè)有單循環(huán)鏈表類CircularListCircularList，要求在類，要求在類CircularListCircularList中增加一個(gè)中增加一個(gè)成員函數(shù)，在不增加新結(jié)點(diǎn)的情況下，直接實(shí)現(xiàn)兩個(gè)鏈表合并為一個(gè)鏈表成員函數(shù)，在不增加新結(jié)點(diǎn)的情況下，直接實(shí)現(xiàn)兩個(gè)鏈表合并為一個(gè)鏈表的算法，并分析其時(shí)間復(fù)雜度。的算法，并分析其時(shí)間

12、復(fù)雜度。/ / 解法解法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)習(xí)題三（第習(xí)題三（第5050頁(yè)）頁(yè)）3.13.1 設(shè)設(shè)A A、B B、C C、D D、E E五個(gè)元素依次進(jìn)棧五個(gè)元素依次進(jìn)棧( (進(jìn)棧后可立即出棧進(jìn)棧后可立即出棧

15、) )，問能，問能否得到下列序列。若能得到，則給出相應(yīng)的否得到下列序列。若能得到，則給出相應(yīng)的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）不能。對(duì)）不能。對(duì)2 2）中的）中的E E，B B，D D而言，而言，E E最先出棧則表明，此最先出棧則表明，此時(shí)時(shí)B B和和D D均在棧中，由于，均在棧中，由于，B B先于先于D D進(jìn)棧，所

16、以應(yīng)有進(jìn)棧，所以應(yīng)有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 設(shè)計(jì)共享?xiàng)?。設(shè)計(jì)共享?xiàng)！?定義一個(gè)足夠大的?？臻g。該空間的兩端分別設(shè)為兩個(gè)棧的定義一個(gè)足夠大的?？臻g。該空間

17、的兩端分別設(shè)為兩個(gè)棧的棧底，用棧底，用bottom1bottom1和和bottom2bottom2指示，讓兩個(gè)棧的棧頂，用指示，讓兩個(gè)棧的棧頂，用top1top1和和top2top2指示，都向中間伸展，直到兩個(gè)棧的棧頂相遇，才會(huì)發(fā)生指示，都向中間伸展，直到兩個(gè)棧的棧頂相遇，才會(huì)發(fā)生溢出。溢出。棧空，兩棧均空：?？眨瑑蓷＞眨簍op1=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寫出下列表達(dá)式的

18、后綴形式。寫出下列表達(dá)式的后綴形式。 /+ab+cd -b2*4ac -*ac/bc2 +*+abc/d+ef -*+ab+*cde*ac3.93.9 利用?？梢詸z查表達(dá)式中括號(hào)是否配對(duì)，試編寫算法實(shí)現(xiàn)之。利用棧可以檢查表達(dá)式中括號(hào)是否配對(duì)，試編寫算法實(shí)現(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、解法二解法二 不用棧，用一個(gè)字符數(shù)組不用棧，用一個(gè)字符數(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ù)組，只用一個(gè)計(jì)數(shù)器不用棧，也不用數(shù)組，只用一個(gè)計(jì)數(shù)器top,top,記錄記錄“(”(”的個(gè)數(shù)的個(gè)數(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 聲明并實(shí)現(xiàn)鏈?zhǔn)綏ｎ惵暶鞑?shí)現(xiàn)鏈?zhǔn)綏ｎ怢inkedStackLinkedStack。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的存儲(chǔ)地址的存儲(chǔ)地址loc(Aijk)loc(Aijk)。習(xí)題四（第習(xí)題四（第6868頁(yè)）頁(yè)）答：答： 設(shè)有三維數(shù)組聲明為設(shè)有三維數(shù)組聲明為AnAn1 1nn2 2nn3 3 ，每個(gè)元素占，每個(gè)元素占m m個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，則則 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設(shè)三對(duì)角矩陣設(shè)三對(duì)角矩陣A An n n n, ,將其將其3 3條對(duì)角線上元素按對(duì)角線存入二維數(shù)組條對(duì)角線上元素按對(duì)角線存入二維數(shù)組B3nB3n中，使得中，使得Buv=AijBuv=Aij。求。求 （1 1）用）用i,ji,j表示表示u,vu,v的下標(biāo)變換公式；的下標(biāo)變換公式；)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 設(shè)三對(duì)角矩陣設(shè)三對(duì)角矩陣A An n n n, ,將其將其3 3條對(duì)角線上元素存入大小為條對(duì)角線上元素存入大小為(3n-2)(3n-2)的的一維數(shù)組一維數(shù)組BB中，使得中，使得Bk=AijBk=Aij。求。求 （1 1）用）用i,ji,j表示表示k k的下標(biāo)變換公式；的下標(biāo)變換公式； （2 2）用）用k k表示表示i,ji,j的下標(biāo)變換公式的下標(biāo)變換公式) 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)先順序存儲(chǔ)的三元組表。順序存儲(chǔ)的三元組表。 4.6 4.6 對(duì)題圖對(duì)題圖4-54-5的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時(shí)數(shù)組的稀疏矩陣執(zhí)行矩陣轉(zhuǎn)置時(shí)數(shù)組numnum和和kk的值。的值。5.2 5.2 設(shè)計(jì)一個(gè)遞歸算法，實(shí)現(xiàn)對(duì)一個(gè)有序表的順序搜索。設(shè)計(jì)一個(gè)遞歸算法，實(shí)現(xiàn)對(duì)一個(gè)有序表的順序搜索。習(xí)題五（第習(xí)題五（第8181頁(yè)）頁(yè)）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 畫出對(duì)長(zhǎng)度為畫出對(duì)長(zhǎng)度為1212的有序表進(jìn)行對(duì)半查找的二叉判定樹的有序表進(jìn)行對(duì)半查找的二叉判定樹，并求等概率搜索時(shí)，成功搜索的平均搜索長(zhǎng)度，并求等概率搜索時(shí)，成功搜索的平均搜索長(zhǎng)度解：解：1 1 二叉判定樹如下：二叉判定樹如下：成功搜索的平均搜索長(zhǎng)度成功搜索的平均搜

34、索長(zhǎng)度 由于第由于第i i層有層有2 2i i個(gè)結(jié)點(diǎn)，故平均搜索長(zhǎng)度為：個(gè)結(jié)點(diǎn)，故平均搜索長(zhǎng)度為：ASL ASL log log2 2(n+1) /P.77(n+1) /P.77習(xí)題六（第習(xí)題六（第107107頁(yè)）頁(yè)）6.26.2（2 2）對(duì)于三個(gè)結(jié)點(diǎn)）對(duì)于三個(gè)結(jié)點(diǎn)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叉樹的特點(diǎn)是：第叉樹的特點(diǎn)是：

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