數(shù)據(jù)結(jié)構(gòu)[C語言版]第三四章習(xí)題答案及解析

22、就是在尾結(jié)點(diǎn)處插入元素 　　　　QueueNode *p= malloc >;//申請新結(jié)點(diǎn) 　　　　p->data=x; p->next=Q->rear->next;//初始化新結(jié)點(diǎn)并鏈入 　　　　Q-rear->next=p;? 　　　　Q->rear=p;//將尾指針移至新結(jié)點(diǎn) 　　　} 　<4>出隊(duì) 　　Datatype DeQueue< LinkQueue *Q> 　　　{//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下 　　　　Datatype t; 　　　　QueueNode *p; 　　　　if

23、Queue< Q >> 　　　　　　Error<"Queue underflow">; 　　　　p=Q->rear->next->next; //p指向?qū)⒁碌慕Y(jié)點(diǎn) 　　　　x=p->data; //保存結(jié)點(diǎn)中數(shù)據(jù) 　　　　if rear> 　　　　　{//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí),p結(jié)點(diǎn)出隊(duì)后,要將隊(duì)尾指針指向頭結(jié)點(diǎn) 　　　　　　Q->rear = Q->rear->next; Q->rear->next=p->next;} 　　　　else? 　　　　　　Q->rear->next->next=p->next;//摘下結(jié)點(diǎn)p 　　　　free

;//釋放

24、被刪結(jié)點(diǎn) 　　　　return x; 　　　} 〔7假設(shè)以數(shù)組Q[m]存放循環(huán)隊(duì)列中的元素, 同時(shí)設(shè)置一個(gè)標(biāo)志tag,以tag== 0和tag == 1來區(qū)別在隊(duì)頭指針和隊(duì)尾指針相等時(shí),隊(duì)列狀態(tài)為"空"還是"滿"。試編寫與此結(jié)構(gòu)相應(yīng)的插入和刪除算法。 [解答] 循環(huán)隊(duì)列類定義 #include template classQueue { //循環(huán)隊(duì)列的類定義 public: Queue ; ~Queue < > { del

25、ete [ ] Q;} void EnQueue ; Type DeQueue <>; TypeGetFront < >; void MakeEmpty < >{ front = rear = tag = 0;} //置空隊(duì)列 intIsEmpty < >const{ return front == rear && tag == 0;} //判隊(duì)列空否 intIsFull < >const{ return front == rear && tag == 1;} //判隊(duì)列滿否 private: intrear, front, tag;

26、//隊(duì)尾指針、隊(duì)頭指針和隊(duì)滿標(biāo)志 Type *Q; //存放隊(duì)列元素的數(shù)組 intm; //隊(duì)列最大可容納元素個(gè)數(shù) } 構(gòu)造函數(shù) template Queue:: Queue < intsz > : rear <0>,front <0>, tag<0>, m { //建立一個(gè)最大具有m個(gè)元素的空隊(duì)列。 Q =new Type[m]; //創(chuàng)建隊(duì)列空間 assert < Q != 0 >; //斷言:動態(tài)存儲分配成功與否 } 插入函數(shù) template

27、> voidQueue ::EnQueue < Type &item> { assert < ! IsFull < > >;//判隊(duì)列是否不滿,滿則出錯(cuò)處理 rear = < rear + 1 > % m;//隊(duì)尾位置進(jìn)1, 隊(duì)尾指針指示實(shí)際隊(duì)尾位置 Q[rear] = item; //進(jìn)隊(duì)列 tag = 1; //標(biāo)志改1,表示隊(duì)列不空 } 刪除函數(shù) template Type Queue ::DeQueue < > { assert < ! IsEmpty < > >;//判斷隊(duì)列是否不

28、空,空則出錯(cuò)處理 front =< front + 1 > % m; //隊(duì)頭位置進(jìn)1, 隊(duì)頭指針指示實(shí)際隊(duì)頭的前一位置 tag = 0; //標(biāo)志改0, 表示棧不滿 return Q[front]; //返回原隊(duì)頭元素的值 } 讀取隊(duì)頭元素函數(shù) template Type Queue ::GetFront < > { assert < ! IsEmpty < > >;//判斷隊(duì)列是否不空,空則出錯(cuò)處理 return Q[ % m]; //返回隊(duì)頭元素的值 } <8如果允許在循

29、環(huán)隊(duì)列的兩端都可以進(jìn)行插入和刪除操作。要求： ① 寫出循環(huán)隊(duì)列的類型定義； ② 寫出"從隊(duì)尾刪除"和"從隊(duì)頭插入"的算法。 [題目分析] 用一維數(shù)組 v[0..M-1]實(shí)現(xiàn)循環(huán)隊(duì)列,其中M是隊(duì)列長度。設(shè)隊(duì)頭指針 front和隊(duì)尾指針rear,約定front指向隊(duì)頭元素的前一位置,rear指向隊(duì)尾元素。定義front=rear時(shí)為隊(duì)空,%m=front 為隊(duì)滿。約定隊(duì)頭端入隊(duì)向下標(biāo)小的方向發(fā)展,隊(duì)尾端入隊(duì)向下標(biāo)大的方向發(fā)展。 〔1#define M 隊(duì)列可能達(dá)到的最大長度 typedefstruct { elemtp data[M]; int front,re

30、ar; } cycqueue; 〔2elemtp delqueue < cycqueue Q> //Q是如上定義的循環(huán)隊(duì)列,本算法實(shí)現(xiàn)從隊(duì)尾刪除,若刪除成功,返回被刪除元素,否則給出出錯(cuò)信息。 { if {printf<"隊(duì)列空">; exit<0>;} Q.rear=%M; //修改隊(duì)尾指針。 return%M]>; //返回出隊(duì)元素。 }//從隊(duì)尾刪除算法結(jié)束 void enqueue

31、// Q是順序存儲的循環(huán)隊(duì)列,本算法實(shí)現(xiàn)"從隊(duì)頭插入"元素x。 {if %M> {printf<"隊(duì)滿"; exit<0>;> Q.data[Q.front]=x; //x 入隊(duì)列 Q.front=%M; //修改隊(duì)頭指針。 }// 結(jié)束從隊(duì)頭插入算法。 〔9已知Ackermann函數(shù)定義如下: ① 寫出計(jì)算Ack的遞歸算法,并根據(jù)此算法給出出Ack<2,1>的計(jì)算過程。 ② 寫出計(jì)算Ack的非遞歸算法。 int Ack {if

32、0> return; elseif return>; elsereturn>; }//算法結(jié)束 〔1Ack<2,1>的計(jì)算過程 Ack<2,1>=Ack<1,Ack<2,0>> //因m<>0,n<>0而得 =Ack<1,Ack<1,1>> //因m<>0,n=0而得 =Ack<1,Ack<0,Ack<1,0>>> // 因m<>0,n<>0而得

33、 = Ack<1,Ack<0,Ack<0,1>>> // 因m<>0,n=0而得 =Ack<1,Ack<0,2>> // 因m=0而得 =Ack<1,3> // 因m=0而得 =Ack<0,Ack<1,2>> //因m<>0,n<>0而得 = Ack<0,Ack<0,Ack<1,1>>> //因m<>0,n<>0而得 = Ack<0,Ack<0,Ack<0,Ack<1,0>>

34、>> //因m<>0,n<>0而得 = Ack<0,Ack<0,Ack<0,Ack<0,1>>>> //因m<>0,n=0而得 = Ack<0,Ack<0,Ack<0,2>>> //因m=0而得 = Ack<0,Ack<0,3>> //因m=0而得 = Ack<0,4> //因n=0而得 =5 //因n=0而得 〔2int Ackerman< int m,

35、 int n> {int akm[M][N];int i,j; for akm[0][j];=j+1; for {akm[i][0]=akm[i-1][1]; for akm[i][j]=akm[i-1][akm[i][j-1]]; } return; }//算法結(jié)束 〔10已知f為單鏈表的表頭指針, 鏈表中存儲的都是整型數(shù)據(jù),試寫出實(shí)現(xiàn)下列運(yùn)算的遞歸算法： ①求鏈表中的最大整

36、數(shù)； ②求鏈表的結(jié)點(diǎn)個(gè)數(shù)； ③ 求所有整數(shù)的平均值。 #include //定義在頭文件"RecurveList.h"中 class List; classListNode { //鏈表結(jié)點(diǎn)類 friend classList; private: intdata; //結(jié)點(diǎn)數(shù)據(jù) ListNode *link; //結(jié)點(diǎn)指針 ListNode < const intitem > : data, link { } //構(gòu)造函數(shù) }; class List { //鏈表類 priv

37、ate: ListNode *first, current; intMax; int Num; floatAvg ; public: List < > :first, current { } //構(gòu)造函數(shù) ~List<>{ } //析構(gòu)函數(shù) ListNode* NewNode < const intitem >; //創(chuàng)建鏈表結(jié)點(diǎn), 其值為item voidNewList < const intretvalue >; //建立鏈表, 以輸入ret

38、value結(jié)束 voidPrintList < >; //輸出鏈表所有結(jié)點(diǎn)數(shù)據(jù) intGetMax < > { return Max < first >; } //求鏈表所有數(shù)據(jù)的最大值 int GetNum < > { returnNum < first >; } //求鏈表中數(shù)據(jù)個(gè)數(shù) float GetAvg < > { return Avg < first >; } //求鏈表所有數(shù)據(jù)的平均值 }; ListNode* List::NewNode < const int item > { //創(chuàng)建新鏈表結(jié)點(diǎn) ListNode *newnode = new

39、 ListNode ; returnnewnode; } voidList::NewList{ //建立鏈表, 以輸入retvalue結(jié)束 first=NULL;intvalue;ListNode *q; cout<<"Input your data:\n"; //提示 cin >> value; //輸入 while< value != retvalue>{//輸入有效 q=NewNode; //建立包含value的新結(jié)點(diǎn) if < first == NULL > first =

40、current = q; //空表時(shí), 新結(jié)點(diǎn)成為鏈表第一個(gè)結(jié)點(diǎn) else {current->link= q;current = q; } //非空表時(shí), 新結(jié)點(diǎn)鏈入鏈尾 cin >> value; //再輸入 } current->link = NULL; //鏈尾封閉 } voidList::PrintList<>{ //輸出鏈表 cout<<"\nThe List is:\n"; ListNode *p = first; while{ cout<data<<' ';p=p->link;} cout << ‘

41、\n’; } intList::Max{ //遞歸算法 : 求鏈表中的最大值 iflink==NULL>returnf->data; //遞歸結(jié)束條件 inttemp=Maxlink>; //在當(dāng)前結(jié)點(diǎn)的后繼鏈表中求最大值 ifdata>temp>returnf->data; //如果當(dāng)前結(jié)點(diǎn)的值還要大, 返回當(dāng)前檢點(diǎn)值 else returntemp; //否則返回后繼鏈表中的最大值 } intList ::Num < ListNode *f > { //遞歸算法:求鏈表中結(jié)點(diǎn)個(gè)數(shù)

42、 if < f == NULL > return 0; //空表, 返回0 return 1+ Num < f ->link >; //否則, 返回后繼鏈表結(jié)點(diǎn)個(gè)數(shù)加1 } floatList ::Avg < ListNode *f, int&n>{//遞歸算法 : 求鏈表中所有元素的平均值 if < f ->link == NULL > //鏈表中只有一個(gè)結(jié)點(diǎn), 遞歸結(jié)束條件 {n = 1; return< float > data >; } else { float Sum =Avg link, n> * n;n++;retur

43、n < f->data+Sum > / n; } } #include "RecurveList.h" //定義在主文件中 intmain < int argc, char* argv[ ] > { List test; intfinished; cout << "輸入建表結(jié)束標(biāo)志數(shù)據(jù) ："; cin >> finished; //輸入建表結(jié)束標(biāo)志數(shù)據(jù) test.NewList< finished>; //建立鏈表 test.PrintList < >; //打印鏈表 cout << "\nThe Max is : " << te

44、st.GetMax < >; cout << "\nThe Num is : " << test.GetNum < >; cout << "\nThe Ave is : " << test.GetAve <> << '\n'; printf < "Hello World!\n" >; return 0; } 第4章 串、數(shù)組和廣義表 習(xí)題 1．選擇題 〔1串是一種特殊的線性表,其特殊性體現(xiàn)在〔 。 A．可以順序存儲 B．?dāng)?shù)據(jù)元素是一個(gè)字符 C．可以鏈?zhǔn)酱鎯? D．?dāng)?shù)據(jù)元素可以是多個(gè)字符若 〔2串

45、下面關(guān)于串的的敘述中,〔 是不正確的？ A．串是字符的有限序列 B．空串是由空格構(gòu)成的串 C．模式匹配是串的一種重要運(yùn)算 D．串既可以采用順序存儲,也可以采用鏈?zhǔn)酱鎯? 〔3串"ababaaababaa"的next數(shù)組為〔 。 〔4串"ababaabab"的nextval為〔 。 A．010104101 B．010102101C．010100011 D．010101011 〔5串的長度是指〔 。 A．串中所含不同字母的個(gè)數(shù) B．串中所含字符的個(gè)數(shù) C．串中所含不同字符的個(gè)數(shù) D．串中所含非空格字符的個(gè)數(shù) 〔6假設(shè)以行序?yàn)橹餍虼?/p>

46、儲二維數(shù)組A=array[1..100,1..100],設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲單元,基地址為10,則LOC[5,5]=〔 。 A．808 B．818 C．1010 D．1020 〔7設(shè)有數(shù)組A[i,j],數(shù)組的每個(gè)元素長度為3字節(jié),i的值為1到8,j的值為1到10,數(shù)組從內(nèi)存首地址BA開始順序存放,當(dāng)用以列為主存放時(shí),元素A[5,8]的存儲首地址為〔 。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 〔8設(shè)有一個(gè)10階的對稱矩陣A,采用壓縮存儲方式,

47、以行序?yàn)橹鞔鎯?a11為第一元素,其存儲地址為1,每個(gè)元素占一個(gè)地址空間,則a85的地址為〔 。 A．13 B．33 C．18 D．40 〔9若對n階對稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對角線上所有元素>依次存放于一維數(shù)組B[1..>/2]中,則在B中確定aij〔i/2+j B．j*/2+i C．i*/2+j D．j*/2+i 〔10A[N,N]是對稱矩陣,將下面三角〔包括對角線以行序存儲到一

48、維數(shù)組T[N/2]中,則對任一上三角元素a[i][j]對應(yīng)T[k]的下標(biāo)k是〔 。 A．i/2+j B．j/2+iC．i/2+1 D．j/2+1 〔11設(shè)二維數(shù)組A[1.. m,1.. n]〔即m行n列按行存儲在數(shù)組B[1.. m*n]中,則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為〔 。 A．*n+j B．*n+j-1 C．i* D．j*m+i-1 〔12數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)〔 。 A．55 B．45

49、C．36 D．16 〔13廣義表A=,>>,則Head>>>>的值為〔 。 A． B． C．c D．d 〔14廣義表<>的表頭是〔,表尾是〔 。 A．a(chǎn) B．< > C． D． 〔15設(shè)廣義表L=<>,則L的長度和深度分別為〔 。 A．1和1 B．1和3

50、C．1和2 D．2和3 〔1已知模式串t=‘a(chǎn)bcaabbabcab’寫出用KMP法求得的每個(gè)字符對應(yīng)的next和nextval函數(shù)值。 模式串t的next和nextval值如下： j 1 2 3 4 5 6 7 8 9 10 11 12 t串 a b c a a b b a b c a b next[j] 0 1 1 1 2 2 3 1 2 3 4 5 nextval[j] 0 1 1 0 2 1 3 0 1 1 0 5 〔2設(shè)目標(biāo)為t="abcaabbabcabaacb

51、acba",模式為p="abcabaa" ①計(jì)算模式p的naxtval函數(shù)值； ②不寫出算法,只畫出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過程。 ①p的nextval函數(shù)值為0110132?！瞤的next函數(shù)值為0111232。 ②利用KMP<改進(jìn)的nextval>算法,每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab 第二趟匹配： abcaabbabcabaacbacba abc 第三趟匹配： abcaabbabcabaacbacb

52、a a 第四趟匹配： abcaabbabcabaac bacba <成功> abcabaa 〔3數(shù)組A中,每個(gè)元素A[i,j]的長度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9,列下標(biāo)從1到11,從首地址S開始連續(xù)存放主存儲器中,主存儲器字長為16位。求： ①存放該數(shù)組所需多少單元？ ②存放數(shù)組第4列所有元素至少需多少單元？ ③數(shù)組按行存放時(shí),元素A[7,4]的起始地址是多少？ ④數(shù)組按列存放時(shí),元素A[4,7]的起始地址是多少？ 每個(gè)元素32個(gè)二進(jìn)制位,主存字長16位,故每個(gè)

53、元素占2個(gè)字長,行下標(biāo)可平移至1到11。 〔1242 〔222 〔3s+182 〔4s+142 <4>請將香蕉banana用工具 H< >—Head< >,T< >—Tail< >從L中取出。 L=>,peach>,pear> H〔H〔T〔H〔T〔H〔T〔L 〔5寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件〔字符串中的合法字符為A-Z這26個(gè)字母和0-9這10個(gè)數(shù)字。 void Count〔 //統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。 ｛int i,num[36]； c

54、har ch； for〔i＝0；i<36；i++num[i]＝０；// 初始化 while〔〔ch＝getchar〔!=‘#’ //‘#’表示輸入字符串結(jié)束。 if〔‘0’<=ch<=‘9’｛i=ch－48;num[i]++；｝ // 數(shù)字字符 elseif〔‘A’<=ch<=‘Z’｛i=ch-65+10;num[i]++；｝// 字母字符 for〔i=0；i<10；i++ // 輸出數(shù)字字符的個(gè)數(shù) printf〔"數(shù)字％d的個(gè)數(shù)＝％d\n",i,num[i]； for〔i＝10；i<36；i++// 求出字母字符的個(gè)數(shù) printf〔"字母字符％c的個(gè)數(shù)＝％

55、d\n",i＋55,num[i]； ｝// 算法結(jié)束。 〔6寫一個(gè)遞歸算法來實(shí)現(xiàn)字符串逆序存儲,要求不另設(shè)串存儲空間。 [題目分析]實(shí)現(xiàn)字符串的逆置并不難,但本題"要求不另設(shè)串存儲空間"來實(shí)現(xiàn)字符串逆序存儲,即第一個(gè)輸入的字符最后存儲,最后輸入的字符先存儲,使用遞歸可容易做到。 void InvertStore //字符串逆序存儲的遞歸算法。 { char ch; static int i = 0;//需要使用靜態(tài)變量 scanf <"%c",&ch>; if //規(guī)定'.'是字符串輸入結(jié)束標(biāo)志 {InvertStore

56、>; A[i++] = ch;//字符串逆序存儲 } A[i] = '\0'; //字符串結(jié)尾標(biāo)記 }//結(jié)束算法InvertStore。 〔7編寫算法,實(shí)現(xiàn)下面函數(shù)的功能。函數(shù)void insert將字符串t插入到字符串s中,插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入?！舱f明：不得使用任何庫函數(shù) [題目分析]本題是字符串的插入問題,要求在字符串s的pos位置,插入字符串t。首先應(yīng)查找字符串s的pos位置,將第pos個(gè)字符到字符串s尾的子串向后移動字符串t的長度,然后將字符串t復(fù)制到字符串s的第pos位置后。

57、 對插入位置pos要驗(yàn)證其合法性,小于1或大于串s的長度均為非法,因題目假設(shè)給字符串s的空間足夠大,故對插入不必判溢出。 void insert //將字符串t插入字符串s的第pos個(gè)位置。 {int i=1,x=0; char *p=s,*q=t; //p,q分別為字符串s和t的工作指針 if {printf<"pos參數(shù)位置非法\n">;exit<0>;} while<*p!=’\0’&&i {p++;i++;} //查pos位置 //若pos小于串s長度,則查到pos位置時(shí),i=pos。

58、 if<*p == '/0'> {printf<"%d位置大于字符串s的長度",pos>;exit<0>;} else //查找字符串的尾 while<*p!= '/0'> {p++; i++;} //查到尾時(shí),i為字符‘\0’的下標(biāo),p也指向‘\0’。 while<*q!= '\0'> {q++; x++; } //查找字符串t的長度x,循環(huán)結(jié)束時(shí)q指向'\0'。 for=pos ;j-->{*=*p; p--;}//串s的pos后的子串右移,空出串t的位置。 q--; //指針q回退到串t的最后一個(gè)字符 for

59、+> *p--=*q--; //將t串插入到s的pos位置上 [算法討論] 串s的結(jié)束標(biāo)記<'\0'>也后移了,而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中。 〔8已知字符串S1中存放一段英文,寫出算法format,將其按給定的長度n格式化成兩端對齊的字符串S2, 其多余的字符送S3。 [題目分析]本題要求字符串s1拆分成字符串s2和字符串s3,要求字符串s2"按給定長度n格式化成兩端對齊的字符串",即長度為n且首尾字符不得為空格字符。算法從左到右掃描字符串s1,找到第一個(gè)非空格字符,計(jì)數(shù)到n,第n個(gè)拷入字符串s2的字符不得為空格,然后將余下字符復(fù)制到字符串s3中。 vo

60、id format //將字符串s1拆分成字符串s2和字符串s3,要求字符串s2是長n且兩端對齊 {char *p=s1, *q=s2; int i=0; while<*p!= '\0' && *p== ' '> p++;//濾掉s1左端空格 if<*p== '\0'> {printf<"字符串s1為空串或空格串\n">;exit<0>; } while< *p!='\0' && i{*q=*p; q++; p++; i++;}//字符串s1向字符串s2中復(fù)制 if<*p =='\0'>{ printf<"字符串s1沒有%d個(gè)有效字符\

61、n",n>; exit<0>;} if<*<--q>==' ' > //若最后一個(gè)字符為空格,則需向后找到第一個(gè)非空格字符 {p-- ; //p指針也后退 while<*p==' '&&*p!='\0'> p++;//往后查找一個(gè)非空格字符作串s2的尾字符 if<*p=='\0'> {printf<"s1串沒有%d個(gè)兩端對齊的字符串\n",n>; exit<0>; } *q=*p; //字符串s2最后一個(gè)非空字符 *<++q>='\0'; //置s2字符串結(jié)束標(biāo)記 } *q=s3;p++; //將s1串其余

62、部分送字符串s3。 while <*p!= '\0'> {*q=*p; q++; p++;} *q='\0'; //置串s3結(jié)束標(biāo)記 } <9>設(shè)二維數(shù)組a[1..m, 1..n] 含有m*n 個(gè)整數(shù)。 ①寫一個(gè)算法判斷a中所有元素是否互不相同?輸出相關(guān)信息； ②試分析算法的時(shí)間復(fù)雜度。 [題目分析]判斷二維數(shù)組中元素是否互不相同,只有逐個(gè)比較,找到一對相等的元素,就可結(jié)論為不是互不相同。如何達(dá)到每個(gè)元素同其它元素比較一次且只一次？在當(dāng)前行,每個(gè)元素要同本行后面的元素比較一次〔下面第一個(gè)循環(huán)控制變量p的for循環(huán),然后同第i+1行及以后各行元素比較

63、一次,這就是循環(huán)控制變量k和p的二層for循環(huán)。 int JudgEqual //判斷二維數(shù)組中所有元素是否互不相同,如是,返回1；否則,返回0。 {for for { for //和同行其它元素比較 if {printf<"no">; return<0>; } //只要有一個(gè)相同的,就結(jié)論不是互不相同 for //和第i+1行及以后元素比較 for

64、p++> if {printf<"no">; return<0>; } }// for printf; return<1>; //元素互不相同 }//算法JudgEqual結(jié)束 〔2二維數(shù)組中的每一個(gè)元素同其它元素都比較一次,數(shù)組中共m*n個(gè)元素,第1個(gè)元素同其它m*n-1個(gè)元素比較,第2個(gè)元素同其它m*n-2 個(gè)元素比較,……,第m*n-1個(gè)元素同最后一個(gè)元素比較一次,所以在元素互不相等時(shí)總的比較次數(shù)為 ++…+2+1=〔m*n

65、1>/2。在有相同元素時(shí),可能第一次比較就相同,也可能最后一次比較時(shí)相同,設(shè)在個(gè)位置上均可能相同,這時(shí)的平均比較次數(shù)約為〔m*n/4,總的時(shí)間復(fù)雜度是O。 <10>設(shè)任意n個(gè)整數(shù)存放于數(shù)組A<1:n>中,試編寫算法,將所有正數(shù)排在所有負(fù)數(shù)前面〔要求算法復(fù)雜性為0。 [題目分析]本題屬于排序問題,只是排出正負(fù),不排出大小?？稍跀?shù)組首尾設(shè)兩個(gè)指針i和j,i自小至大搜索到負(fù)數(shù)停止,j自大至小搜索到正數(shù)停止。然后i和j所指數(shù)據(jù)交換,繼續(xù)以上過程,直到 i=j為止。 void Arrange //n個(gè)整數(shù)存于數(shù)組A中,本算

66、法將數(shù)組中所有正數(shù)排在所有負(fù)數(shù)的前面 {int i=0,j=n-1,x; //用類C編寫,數(shù)組下標(biāo)從0開始 while {while0> i++; while j--; if {x=A[i]; A[i++]=A[j]; A[j--]=x; }//交換A[i] 與A[j] } }//算法Arrange結(jié)束. [算法討論]對數(shù)組中元素各比較一次,比較次數(shù)為n。最佳情況<已排好,正數(shù)在前,負(fù)數(shù)在后>不發(fā)生交換,最差情況<負(fù)數(shù)均在正數(shù)前面>發(fā)生n/2次交換。用類c編寫,數(shù)組界偶是0..n-1。空間復(fù)雜度為O<1>. .