数据结构[C语言版]第三四章习题答案及解析

22、就是在尾结点处插入元素 　　　　QueueNode *p= malloc >;//申请新结点 　　　　p->data=x; p->next=Q->rear->next;//初始化新结点并链入 　　　　Q-rear->next=p;  　　　　Q->rear=p;//将尾指针移至新结点 　　　} 　<4>出队 　　Datatype DeQueue< LinkQueue *Q> 　　　{//出队,把头结点之后的元素摘下 　　　　Datatype t; 　　　　QueueNode *p; 　　　　if

23、Queue< Q >> 　　　　　　Error<"Queue underflow">; 　　　　p=Q->rear->next->next; //p指向将要摘下的结点 　　　　x=p->data; //保存结点中数据 　　　　if rear> 　　　　　{//当队列中只有一个结点时,p结点出队后,要将队尾指针指向头结点 　　　　　　Q->rear = Q->rear->next; Q->rear->next=p->next;} 　　　　else  　　　　　　Q->rear->next->next=p->next;//摘下结点p 　　　　free

;//释放

24、被删结点 　　　　return x; 　　　} 〔7假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag,以tag== 0和tag == 1来区别在队头指针和队尾指针相等时,队列状态为"空"还是"满"。试编写与此结构相应的插入和删除算法。 [解答] 循环队列类定义 #include template classQueue { //循环队列的类定义 public: Queue ; ~Queue < > { del

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

26、//队尾指针、队头指针和队满标志 Type *Q; //存放队列元素的数组 intm; //队列最大可容纳元素个数 } 构造函数 template Queue:: Queue < intsz > : rear <0>,front <0>, tag<0>, m { //建立一个最大具有m个元素的空队列。 Q =new Type[m]; //创建队列空间 assert < Q != 0 >; //断言:动态存储分配成功与否 } 插入函数 template

27、> voidQueue ::EnQueue < Type &item> { assert < ! IsFull < > >;//判队列是否不满,满则出错处理 rear = < rear + 1 > % m;//队尾位置进1, 队尾指针指示实际队尾位置 Q[rear] = item; //进队列 tag = 1; //标志改1,表示队列不空 } 删除函数 template Type Queue ::DeQueue < > { assert < ! IsEmpty < > >;//判断队列是否不

28、空,空则出错处理 front =< front + 1 > % m; //队头位置进1, 队头指针指示实际队头的前一位置 tag = 0; //标志改0, 表示栈不满 return Q[front]; //返回原队头元素的值 } 读取队头元素函数 template Type Queue ::GetFront < > { assert < ! IsEmpty < > >;//判断队列是否不空,空则出错处理 return Q[ % m]; //返回队头元素的值 } <8如果允许在循

29、环队列的两端都可以进行插入和删除操作。要求： ① 写出循环队列的类型定义； ② 写出"从队尾删除"和"从队头插入"的算法。 [题目分析] 用一维数组 v[0..M-1]实现循环队列,其中M是队列长度。设队头指针 front和队尾指针rear,约定front指向队头元素的前一位置,rear指向队尾元素。定义front=rear时为队空,%m=front 为队满。约定队头端入队向下标小的方向发展,队尾端入队向下标大的方向发展。 〔1#define M 队列可能达到的最大长度 typedefstruct { elemtp data[M]; int front,re

30、ar; } cycqueue; 〔2elemtp delqueue < cycqueue Q> //Q是如上定义的循环队列,本算法实现从队尾删除,若删除成功,返回被删除元素,否则给出出错信息。 { if {printf<"队列空">; exit<0>;} Q.rear=%M; //修改队尾指针。 return%M]>; //返回出队元素。 }//从队尾删除算法结束 void enqueue

31、// Q是顺序存储的循环队列,本算法实现"从队头插入"元素x。 {if %M> {printf<"队满"; exit<0>;> Q.data[Q.front]=x; //x 入队列 Q.front=%M; //修改队头指针。 }// 结束从队头插入算法。 〔9已知Ackermann函数定义如下: ① 写出计算Ack的递归算法,并根据此算法给出出Ack<2,1>的计算过程。 ② 写出计算Ack的非递归算法。 int Ack {if

32、0> return; elseif return>; elsereturn>; }//算法结束 〔1Ack<2,1>的计算过程 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; }//算法结束 〔10已知f为单链表的表头指针, 链表中存储的都是整型数据,试写出实现下列运算的递归算法： ①求链表中的最大整

36、数； ②求链表的结点个数； ③ 求所有整数的平均值。 #include //定义在头文件"RecurveList.h"中 class List; classListNode { //链表结点类 friend classList; private: intdata; //结点数据 ListNode *link; //结点指针 ListNode < const intitem > : data, link { } //构造函数 }; class List { //链表类 priv

37、ate: ListNode *first, current; intMax; int Num; floatAvg ; public: List < > :first, current { } //构造函数 ~List<>{ } //析构函数 ListNode* NewNode < const intitem >; //创建链表结点, 其值为item voidNewList < const intretvalue >; //建立链表, 以输入ret

38、value结束 voidPrintList < >; //输出链表所有结点数据 intGetMax < > { return Max < first >; } //求链表所有数据的最大值 int GetNum < > { returnNum < first >; } //求链表中数据个数 float GetAvg < > { return Avg < first >; } //求链表所有数据的平均值 }; ListNode* List::NewNode < const int item > { //创建新链表结点 ListNode *newnode = new

39、 ListNode ; returnnewnode; } voidList::NewList{ //建立链表, 以输入retvalue结束 first=NULL;intvalue;ListNode *q; cout<<"Input your data:\n"; //提示 cin >> value; //输入 while< value != retvalue>{//输入有效 q=NewNode; //建立包含value的新结点 if < first == NULL > first =

40、current = q; //空表时, 新结点成为链表第一个结点 else {current->link= q;current = q; } //非空表时, 新结点链入链尾 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; //递归结束条件 inttemp=Maxlink>; //在当前结点的后继链表中求最大值 ifdata>temp>returnf->data; //如果当前结点的值还要大, 返回当前检点值 else returntemp; //否则返回后继链表中的最大值 } intList ::Num < ListNode *f > { //递归算法:求链表中结点个数

42、 if < f == NULL > return 0; //空表, 返回0 return 1+ Num < f ->link >; //否则, 返回后继链表结点个数加1 } floatList ::Avg < ListNode *f, int&n>{//递归算法 : 求链表中所有元素的平均值 if < f ->link == NULL > //链表中只有一个结点, 递归结束条件 {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 << "输入建表结束标志数据 ："; cin >> finished; //输入建表结束标志数据 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章 串、数组和广义表 习题 1．选择题 〔1串是一种特殊的线性表,其特殊性体现在〔 。 A．可以顺序存储 B．数据元素是一个字符 C．可以链式存储 D．数据元素可以是多个字符若 〔2串

45、下面关于串的的叙述中,〔 是不正确的？ A．串是字符的有限序列 B．空串是由空格构成的串 C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储,也可以采用链式存储 〔3串"ababaaababaa"的next数组为〔 。 〔4串"ababaabab"的nextval为〔 。 A．010104101 B．010102101C．010100011 D．010101011 〔5串的长度是指〔 。 A．串中所含不同字母的个数 B．串中所含字符的个数 C．串中所含不同字符的个数 D．串中所含非空格字符的个数 〔6假设以行序为主序存

46、储二维数组A=array[1..100,1..100],设每个数据元素占2个存储单元,基地址为10,则LOC[5,5]=〔 。 A．808 B．818 C．1010 D．1020 〔7设有数组A[i,j],数组的每个元素长度为3字节,i的值为1到8,j的值为1到10,数组从内存首地址BA开始顺序存放,当用以列为主存放时,元素A[5,8]的存储首地址为〔 。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 〔8设有一个10阶的对称矩阵A,采用压缩存储方式,

47、以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为〔 。 A．13 B．33 C．18 D．40 〔9若对n阶对称矩阵A以行序为主序方式将其下三角形的元素<包括主对角线上所有元素>依次存放于一维数组B[1..>/2]中,则在B中确定aij〔i/2+j B．j*/2+i C．i*/2+j D．j*/2+i 〔10A[N,N]是对称矩阵,将下面三角〔包括对角线以行序存储到一

48、维数组T[N/2]中,则对任一上三角元素a[i][j]对应T[k]的下标k是〔 。 A．i/2+j B．j/2+iC．i/2+1 D．j/2+1 〔11设二维数组A[1.. m,1.. n]〔即m行n列按行存储在数组B[1.. m*n]中,则二维数组元素A[i,j]在一维数组B中的下标为〔 。 A．*n+j B．*n+j-1 C．i* D．j*m+i-1 〔12数组A[0..4,-1..-3,5..7]中含有元素的个数〔 。 A．55 B．45

49、C．36 D．16 〔13广义表A=,>>,则Head>>>>的值为〔 。 A． B． C．c D．d 〔14广义表<>的表头是〔,表尾是〔 。 A．a B．< > C． D． 〔15设广义表L=<>,则L的长度和深度分别为〔 。 A．1和1 B．1和3

50、C．1和2 D．2和3 〔1已知模式串t=‘abcaabbabcab’写出用KMP法求得的每个字符对应的next和nextval函数值。 模式串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设目标为t="abcaabbabcabaacb

51、acba",模式为p="abcabaa" ①计算模式p的naxtval函数值； ②不写出算法,只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 ①p的nextval函数值为0110132。〔p的next函数值为0111232。 ②利用KMP<改进的nextval>算法,每趟匹配过程如下： 第一趟匹配： abcaabbabcabaacbacba abcab 第二趟匹配： abcaabbabcabaacbacba abc 第三趟匹配： abcaabbabcabaacbacb

52、a a 第四趟匹配： abcaabbabcabaac bacba <成功> abcabaa 〔3数组A中,每个元素A[i,j]的长度均为32个二进位,行下标从-1到9,列下标从1到11,从首地址S开始连续存放主存储器中,主存储器字长为16位。求： ①存放该数组所需多少单元？ ②存放数组第4列所有元素至少需多少单元？ ③数组按行存放时,元素A[7,4]的起始地址是多少？ ④数组按列存放时,元素A[4,7]的起始地址是多少？ 每个元素32个二进制位,主存字长16位,故每个

53、元素占2个字长,行下标可平移至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写一个算法统计在输入字符串中各个不同字符出现的频度并将结果存入文件〔字符串中的合法字符为A-Z这26个字母和0-9这10个数字。 void Count〔 //统计输入字符串中数字字符和字母字符的个数。 ｛int i,num[36]； c

54、har ch； for〔i＝0；i<36；i++num[i]＝０；// 初始化 while〔〔ch＝getchar〔!=‘#’ //‘#’表示输入字符串结束。 if〔‘0’<=ch<=‘9’｛i=ch－48;num[i]++；｝ // 数字字符 elseif〔‘A’<=ch<=‘Z’｛i=ch-65+10;num[i]++；｝// 字母字符 for〔i=0；i<10；i++ // 输出数字字符的个数 printf〔"数字％d的个数＝％d\n",i,num[i]； for〔i＝10；i<36；i++// 求出字母字符的个数 printf〔"字母字符％c的个数＝％

55、d\n",i＋55,num[i]； ｝// 算法结束。 〔6写一个递归算法来实现字符串逆序存储,要求不另设串存储空间。 [题目分析]实现字符串的逆置并不难,但本题"要求不另设串存储空间"来实现字符串逆序存储,即第一个输入的字符最后存储,最后输入的字符先存储,使用递归可容易做到。 void InvertStore //字符串逆序存储的递归算法。 { char ch; static int i = 0;//需要使用静态变量 scanf <"%c",&ch>; if //规定'.'是字符串输入结束标志 {InvertStore

56、>; A[i++] = ch;//字符串逆序存储 } A[i] = '\0'; //字符串结尾标记 }//结束算法InvertStore。 〔7编写算法,实现下面函数的功能。函数void insert将字符串t插入到字符串s中,插入位置为pos。假设分配给字符串s的空间足够让字符串t插入。〔说明：不得使用任何库函数 [题目分析]本题是字符串的插入问题,要求在字符串s的pos位置,插入字符串t。首先应查找字符串s的pos位置,将第pos个字符到字符串s尾的子串向后移动字符串t的长度,然后将字符串t复制到字符串s的第pos位置后。

57、 对插入位置pos要验证其合法性,小于1或大于串s的长度均为非法,因题目假设给字符串s的空间足够大,故对插入不必判溢出。 void insert //将字符串t插入字符串s的第pos个位置。 {int i=1,x=0; char *p=s,*q=t; //p,q分别为字符串s和t的工作指针 if {printf<"pos参数位置非法\n">;exit<0>;} while<*p!=’\0’&&i {p++;i++;} //查pos位置 //若pos小于串s长度,则查到pos位置时,i=pos。

58、 if<*p == '/0'> {printf<"%d位置大于字符串s的长度",pos>;exit<0>;} else //查找字符串的尾 while<*p!= '/0'> {p++; i++;} //查到尾时,i为字符‘\0’的下标,p也指向‘\0’。 while<*q!= '\0'> {q++; x++; } //查找字符串t的长度x,循环结束时q指向'\0'。 for=pos ;j-->{*=*p; p--;}//串s的pos后的子串右移,空出串t的位置。 q--; //指针q回退到串t的最后一个字符 for

59、+> *p--=*q--; //将t串插入到s的pos位置上 [算法讨论] 串s的结束标记<'\0'>也后移了,而串t的结尾标记不应插入到s中。 〔8已知字符串S1中存放一段英文,写出算法format,将其按给定的长度n格式化成两端对齐的字符串S2, 其多余的字符送S3。 [题目分析]本题要求字符串s1拆分成字符串s2和字符串s3,要求字符串s2"按给定长度n格式化成两端对齐的字符串",即长度为n且首尾字符不得为空格字符。算法从左到右扫描字符串s1,找到第一个非空格字符,计数到n,第n个拷入字符串s2的字符不得为空格,然后将余下字符复制到字符串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中复制 if<*p =='\0'>{ printf<"字符串s1没有%d个有效字符\

61、n",n>; exit<0>;} if<*<--q>==' ' > //若最后一个字符为空格,则需向后找到第一个非空格字符 {p-- ; //p指针也后退 while<*p==' '&&*p!='\0'> p++;//往后查找一个非空格字符作串s2的尾字符 if<*p=='\0'> {printf<"s1串没有%d个两端对齐的字符串\n",n>; exit<0>; } *q=*p; //字符串s2最后一个非空字符 *<++q>='\0'; //置s2字符串结束标记 } *q=s3;p++; //将s1串其余

62、部分送字符串s3。 while <*p!= '\0'> {*q=*p; q++; p++;} *q='\0'; //置串s3结束标记 } <9>设二维数组a[1..m, 1..n] 含有m*n 个整数。 ①写一个算法判断a中所有元素是否互不相同?输出相关信息； ②试分析算法的时间复杂度。 [题目分析]判断二维数组中元素是否互不相同,只有逐个比较,找到一对相等的元素,就可结论为不是互不相同。如何达到每个元素同其它元素比较一次且只一次？在当前行,每个元素要同本行后面的元素比较一次〔下面第一个循环控制变量p的for循环,然后同第i+1行及以后各行元素比较

63、一次,这就是循环控制变量k和p的二层for循环。 int JudgEqual //判断二维数组中所有元素是否互不相同,如是,返回1；否则,返回0。 {for for { for //和同行其它元素比较 if {printf<"no">; return<0>; } //只要有一个相同的,就结论不是互不相同 for //和第i+1行及以后元素比较 for

64、p++> if {printf<"no">; return<0>; } }// for printf; return<1>; //元素互不相同 }//算法JudgEqual结束 〔2二维数组中的每一个元素同其它元素都比较一次,数组中共m*n个元素,第1个元素同其它m*n-1个元素比较,第2个元素同其它m*n-2 个元素比较,……,第m*n-1个元素同最后一个元素比较一次,所以在元素互不相等时总的比较次数为 ++…+2+1=〔m*n

65、1>/2。在有相同元素时,可能第一次比较就相同,也可能最后一次比较时相同,设在个位置上均可能相同,这时的平均比较次数约为〔m*n/4,总的时间复杂度是O。 <10>设任意n个整数存放于数组A<1:n>中,试编写算法,将所有正数排在所有负数前面〔要求算法复杂性为0。 [题目分析]本题属于排序问题,只是排出正负,不排出大小。可在数组首尾设两个指针i和j,i自小至大搜索到负数停止,j自大至小搜索到正数停止。然后i和j所指数据交换,继续以上过程,直到 i=j为止。 void Arrange //n个整数存于数组A中,本算

66、法将数组中所有正数排在所有负数的前面 {int i=0,j=n-1,x; //用类C编写,数组下标从0开始 while {while0> i++; while j--; if {x=A[i]; A[i++]=A[j]; A[j--]=x; }//交换A[i] 与A[j] } }//算法Arrange结束. [算法讨论]对数组中元素各比较一次,比较次数为n。最佳情况<已排好,正数在前,负数在后>不发生交换,最差情况<负数均在正数前面>发生n/2次交换。用类c编写,数组界偶是0..n-1。空间复杂度为O<1>. .