数据结构习题23562

1、第一章绪论 习题p10 1.17 已知k阶菲波那契序列的定义为：f0=0, f1=0, .,fk-2=0, fk-1=1 /即前k-1项均为0，第k项等于1，注意第一个下标从0开始计数fn=fn-1+fn-2+.+fn-k, n=k, k+1, . /即前k项之和试写求k阶菲波那契序列的第m项值得函数算法，k和m均以值调用的形式在函数参数中表中出现。解：算法的基本思想：利用数组f0.Max存放菲波那契序列的第0，1，2，., m项值, f0, f1, f2, .fm-1,fm分别存放在数组元素f0, f1, f2, .fm-1, fm中。f0, f1, f2, .fk-2, fk-1按照定义通

2、过赋值语句完成。fk, fk+1, .fm通过循环语句累加数组前k项之和得到。最后返回fm的值即完成题目要求。#define Max 1000long Fib(int k, int m) /求k阶菲波那契序列的第m项long fMax; /用来存放前m项菲波那契序列值int i, j; /循环控制变量for (i=0; i<m; i+) /初始化fi=0;if (k<=1 | m<=1) /判断参数的正确性 printf(“nArgument error! “); return (0); fk-1=1;for (i=k; i<=m, i+) /求第k项至第m项 for

3、(j=1; j<=k; j+) /每一项为前面的k项之和 fi=fi+fi-j;return(fm);p10 1.18 假设A, B, C, D, E五个高等院校进行田经对抗赛，各院校的单项成绩均已存入计算机，并构成一张表，表中的每一项的形式为：项目名称性别校名成绩得分编写算法，处理上述表格，以统计各院校的男、女总分和团体总分，并输出。解：根据题目的叙述得知比赛的成绩已经以文件形式存入磁盘中，所以用三个算法分别完成数据输入（用文件中输入）、统计、输出（显示在屏幕上）三个功能。统计算法基本思想：根据数据中学校名称和性别统计每个学校的男子总分和女子总分，最后这二个值之和，就是团体总分，最后用

4、输出语句分别输出5个学校的三个统计值。#define n 1000typedef enum A, B, C, D, E SchoolName;typedef enum Female, Male SexType;typedef struct char event3;/项目名称 SexType sex; /男子项目或女子项目 SchoolName school; /学校名称 float mark; /成绩，如100米的时间等 int score; /得分 Component；typedef struct int malesum; /男子总分int femalesum； /女子总分int total

5、sum; /团体总分 Sum;inputdata(Component r , int & len);outputsum(Sum rt );void compute(Component r , int len, Sum rt ) /计算男子、女总分及团体总分int i;for (i=0; i<5, i+) rti. malesum=0; rti.femalesum=0; rti. totalsum=0; for (i=0; i<len; i+) switch ri. school case A: if (ri.sex=male) rtA. malesum= rtA. male

6、sum+ri.score; else rtA. femalesum= rtA. femalesum+ri.score; break; case B: if (ri.sex=male) rtB. malesum= rtB. malesum+ri.score; else rtB. femalesum= rtB. femalesum+ri.score; break; case C: if (ri.sex=male) rtC. malesum= rtC. malesum+ri.score; else rtC. femalesum= rtC. femalesum+ri.score; break; cas

7、e D: if (ri.sex=male) rtD. malesum= rtD. malesum+ri.score; else rtA. femalesum= rtA. femalesum+ri.score; break; case E: if (ri.sex=male) rtE. malesum= rtE. malesum+ri.score; else rtE. femalesum= rtE. femalesum+ri.score; break; for (i=0; i<5, i+) rti. totalsum= rti. malesum= rti. femalesum; ;main(

8、 )Component reportn; /存放每个项目得分情况，/假设对抗赛有M个项目，那么n>=5*M*2Sum result5; /5个学校的男子总分，/女子总分，团体总分int num , select=1;while (select!=0) printf(“n1: input data 2:output ”) printf(“n3: compute 0:exit ”); printf(“n1Please input your choicen ”); scanf(“%d”, &select); switch( select) case 1: inputdata( repo

9、rt, &num); break;case 2: outputsum(result); break;case 3: compute(report, num, result) break; case 0: return; default printf(“n Your choice is wrong! “); getchar();第二章 线性表习题编写一个算法将单链表中指针P所指结点与其后继结点进行交换，HEAD是该链表的头指针，P指向该链表中某一结点。解：算法基本思想：首先要找到P所指向结点的前驱，修改该前驱的next域，让其指向P的后继，P的后继的next指向P，P的next指向原后继

10、的后继。Status Swap( LinkList &HEAD , LNode * P ) /HEAD为带头结点的单链表的头指针 LNode* q; /局部变量if( P=HEAD | P=NULL | P->next=NULL ) return ERROR;/判断参数的合法性 q = HEAD; /寻找p的前驱，因为需要修改p的前驱的next指针域 while( q->next!=NULL && q->next != P ) q=q->next; /找p的前驱结点，if ( q->next= =NULL ）return ERROR; /未

11、找到p的前驱q->next = P->next; /找到了p的前驱，q指向p的前驱，修改相关指针 P->next = q->next->next; q->next->next = P; /交换p和p的后继结点 return OK;/Swapp17 2.19 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素），同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。解：算法基本思

12、想：元素已经按其值递增有序排列，所以采用循环语句从头开始顺序扫描链表中的每一个结点，看其值是否大于mink并且小于maxk，有2种情况可能退出循环：一是直到链表尾也没有找到满足其值大于mink并且小于maxk的结点，无须做删除操作。第二个找到了第一个其值大于mink并且小于maxk的结点（注意保留该结点的前驱位置），删除该结点并回收空间，并用循环语句顺序检查该结点的后续结点的值是否也是大于mink并且小于maxk，若是，同样删除结点并回收空间。为了检验该算法，必须先创建有序链表，下面先给出了一个以头插方式创建线性链表的算法。因为要求所创建的链表必须递增有序，所以要求按照值从大到小的顺序输入线性

13、表的数据。#include <alloc.h>#include <stdio.h>#define LEN sizeof(LNode) typedef struct node /定义结点结构 double data; struct node * next; LNode;LNode* create( ) /以头插方式创建线性链表，要求从大到小输入的顺序输入数据 LNode*Head, *p; double x=1; Head=(LNode*)malloc(LEN); /创建头结点，Head为头指针，指向头结点 Head->next = NULL; while (x!=

14、0.0) /输入的数据以0作为结束 printf (“n Please input data: ( end with 0.0)”); scanf(“%lf”, &x); if (x=0.0) return (Head);else p=(LNode*)malloc(LEN); if (p=NULL) printf(“n Memory Allocation failure ! “); return(Head); else p->data= x; p->next=Head->next; Head->next=p; return (Head);void output(L

15、Node* Head) /遍历整个链表LNode* p; int i=0; p=Head->next; i printf(“n All data: ”); while(p!=NULL) if (i%5= =0) printf(“n”);i+;printf(“%10lf”, p->data); p=p->next; LNode* delete( LNode*Head, double mink, double maxk) /*删除值大于mink且小于maxk的元素，Head为指向带头结点链表的头指针，返回头指针*/ LNode*p, *q, *r; p=Head->next

16、; /p从第一个结点开始顺序指向正在检查的每个结点 q=Head; /q指向p的前驱 while( p!=NULL && p->data <=mink) q=p; p=p->next; /二种情况会退出循环，一到链尾，二找到了符合条件的结点while( p!=NULL && (p->data>mink &&p->data<maxk) /删除每一个满足条件的结点 r =p->next; free(p); p=r;q->next=p; /修改q的next域return (Head);main()i

17、nt select=1;double maxnum ,minnum,LNode* head;while ( select !=0) printf(“n 1: create 2:Delete”);printf(“n 3: Output 0:Exit”); printf(“n Please input your select:”);scanf(“%d”,&select)switch(select) case 1: head= create(); break;case 2: printf(“n Please maxnum and minnumn”); scanf(“%d,%d”,&m

18、axnum, &minnum); head=delete(head, minnum, maxnum); break;case 3: printf(“n the list is n”); output(head); break; p18 2.21 试写一算法，实现顺序表的就地逆置，即利用原标的存储空间将线性表（a1, a2, .,an)逆置为（an, an-1, ., a2, a1)。解：算法基本思想：如果n为偶数，将a1.an/2顺序与an.an/2+1进行交换，如果n为奇数，将a1.an/2-1顺序与an.an/2+2进行交换。用数组元素a0作辅助空间。#define Maxsize

19、 100typedef struct elemtype dataMaxsize+1;int length; SqList; /定义线性表的顺序存储结构void reverse (SqList* L) int i, j; for (i=1, j=L->length; i<j ; i+, j-) L->data0=L->datai; /利用0号单元作辅助空间 L->datai=L->dataj; L->dataj=L->data0;p18 2.22 试写一算法，对单链表实现就地逆置。解：算法基本思想：顺序修改每个结点的next域，a1的next指向N

20、ULL，a2的next指向a1，a3的next指向a2.，an的next指向an-1，最后头结点的next指向an。算法中用到3个临时指针变量p1，p2，p3。p2总是指向当前扫描的结点，p1指向p2所指结点的原前驱（置逆后变成后继），p3指向p2所指结点的原后继。#define LEN sizeof(LNode)typedef struct node /定义线性链表的存储结构elemtype data;struct node* next; LNode, *LinkList;void reverse1 (LNode* Head) /将以head为头指针的带头结点的单链表就地逆置 LinkLis

21、t p1, p2, p3; p1=NULL; p2=Head->next; /初始化 while (p2!=NULL) p3=p2->next; p2->next=p1; p1=p2; p2=p3; Head->next=p1;算法2的基本思想：首先做一个只有头结点的新的空链表，然后顺序从原链表中摘下每一个结点，采用头插的方式插入到新的链表中。void reverse2 (LNode* Head) /将以head为头指针带头结点的单链表就地逆置,采用头插方式 LinkList p1, p2; p1=Head->next; /p1指向从第一个结点开始顺序指向链表中的

22、每一个结点Head->next=NULL; /先建成空链表，将每个结点顺序的插入到链表空 while (p1!=NULL) p2=p1->next; p1->next=Head->next; Head->next=p1; p1=p2; p18 2.24 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。解：算法的基本思想：首先创建一个只有头结点的新的空链表，然后顺序从A、B摘取值较小的结点，按

23、头插的方式插入到新的链表中。为了得到按元素值增有序排列的线性表A和B，下面先讲解创建一个按元素值递增有序链表的创建算法。先创建一个只有头结点的空链表，然后随意输入数据值，对每一个数据值，创建新结点存放新数据值，然后从链表头开始查找新结点插入点的前驱，p指向该前驱，修改指针域：newp->next=p->next; p->next= newp。#define LEN sizeof(LNode)typedef int elemtype;typedef struct nodeelemtype data;struct node* next; LNode, *LinkList;void

24、 create(LinkList Head) /构造带头结点的递增有序链表，其数据值从键盘输入LNode* p, *newp;elemtype x;Head=(LNode*) malloc(LEN); /创建头结点Head->next=NULL;printf("n Please input data, end with -99n")scanf("%d", %x);while (x!=-99)newp=(LNode*) malloc(LEN); /创建新结点newp->data=x;p=Head;while (p->next!=NULL

25、&& p->next->data<x) /寻找插入点的前驱。若需创建递减有序，将"<"改为“>"。p=p->next;newp->next=p->next;p->next=newp;printf("n Please input data, end with -99n")scanf("%d", %x); void merge (LNode* C, LNode* A, LNode* B ) /将A、B为带头结点的单链表的头指针,采用头插方式实现归并 LinkL

26、ist pa, pb, p; pa=A->next; pb=B->next; C=A; C->next=NULL; while (pa!=NULL&& pb!=NULL) if pa->data<= pb->data; p=pa->next; pa->next=C->next; C->next=pa; pa=p; else p=pb->next; pb->next=C->next; C->next=pb; pb=p; while (pa!=NULL) p=pa->next; pa->

27、next=C->next; C->next=pa; pa=p; while (pb!=NULL) p=pb->next; pb->next=C->next; C->next=pb; pb=p; B->next=NULL; /将B链表置为空表第三章 栈和队列 习题p23 3.10试将下列递归过程改成非递归过程。#include <stdio.h>void test(int* sum) int x;scanf("%d",&x);if (x= =0) *sum=0; else test(sum); *sum =*sum

28、+x; printf("%3d", *sum); main()int s; printf("input integer, end by 0n");test(&s);scanf("%d", &s);解：首先要搞清楚上面的递归函数test到底完成什么。它是把输入的数据累加并打印出来，每累加一个数据打印一次，累加的顺序予输入数据的数据相反，最后输入的数据最先累加，最先输入的数据最后累加。以0作为递归出口。例如输入：3，5，7，8，0，输出的结果是 0 8 15 20 23。如果输入的数据是1，2，3，4，5，0，则输出的结果

29、是0 5 9 12 14 15 将递归算法该为非递归算法，需要有堆栈（实现后进先出），需要循环语句，把非出口的那些操作用循环语句实现。具体到该算法，就是先输入若干整数，对每一个输入的非0值的数据都依次压入堆栈，直到输入0为止（这是递归的出口，也是循环的终止条件）。然后依次将堆栈中的数据弹出，每弹出一个数据，就进行一次累加，同时打印累加的结果，直到堆栈中的数据全部弹出为止。void test(int* sum) stack s;int x;initstack(s);scanf("%d",&x);while (x!=0) push(s, x); scanf("

30、%d",&x); *sum=0; push(s, 0);while ( !StackEmpty(s) x=pop(s); *sum =*sum+x; printf("%3d", *sum);p24 3.15 假设以顺序存储结构实现一个双向栈，即在一维数组的存储空间中存放着两个栈，它们的栈底分别设在数组的两个端点。试编写实现这个双向栈tws的三个操作：初始化initstack(tws)、入栈push(tws, i, x)和出栈pop(tws, i)的算法，其中i为0或1，用以分别指示设在数组两端的两个栈，并讨论按过程（正/误状态变量可设为参数）或函数设计这些

31、操作算法各有什么优缺点。解：算法的基本思想：首先初始化时将两个栈的栈底分别设为-1和Max。进栈时，首先判断是否栈满（top0+1= =top1即栈满），若压入0号栈，top0进行加1运算，若压入1号栈，top1进行减1运算。出栈时，先判断栈空，若出0号栈，top0进行减1操作，若出1号栈，top1进行加1操作。#include <stdio.h>#include <malloc.h>#define Max 100 /*堆栈的最大长度*/typedef int elemtype;typedef struct /顺序存储结构下的双向栈elemtype dataMax;in

32、t top0, top1; /分别为2个栈的栈顶指针 SDStack;void init(SDStack *tws, int i)if (i= =2)tws->top0= -1; tws->top1=Max; else if (i= =0) tws->top0=-1;else if (i= =1) tws->top1=Max;else printf(“n Argument error!”);int push(SDStack*tws, int i, elemtype x) /成功压栈返回1，出错返回0 if (tws->top0+1=tws->top1 ) /

33、判堆栈时候满printf(“Memory overflown”);return(0); if (i= =0) /x压入0号栈tws->top0+;tws->datatws->top0=x; elseif (i= =1) / x压入1号栈 tws->top1-;tws-datatws->top1=x; else printf(“n argument errorn”); /出错 return(0);return (1);elemtype pop(SDStack*tws, int i) /出栈，返回出栈的元素 if (i= =0)if (tws->top0= =-

34、1 ) /出0号栈，判0号栈是否为空printf(“Stack0 is empty. n”);return(NULLELEM); elsetws->top0-;return(tws->datatws->top0+1); elseif (i= =1)if (tws->top1=Max ) /出1号栈，判1号栈是否为空printf(“Stack1 is empty. n”);return(NULLELEM); else tws->top1+;return(tws-datatws->top1-); else printf(“n argument errorn”);

35、 return(NULLELEM);int Empty(SDStack s, int i) /判空，返回0表示非空，表示为空 if (i= =0) return (tws.top0= =-1); /判0号栈是否为空 else if (i= =1) return (tws.top1= =Max); /判1号栈是否为空else printf(“nargument error!”); main()SDStack s;int num, select, result;elemtype t；while ( ) printf(“n 1: Init 2:Push”);printf(“n 3: Pop 4:Is

36、empty”);printf(“n 5: IsFull 0:Exit”); printf(“n Please input your select:”);scanf(“%d”,&select)switch(select) case 1: printf(“n Init stack1(0) or stack2(1), or two stack(2)?”); scanf(“%d”,&num); init(&s, num); break;case 2: printf(“n Push stack1(0) or stack2(1)? Which data you want to pu

37、sh?”); scanf(“%d,%d”,&num, &t); push(&s, num, t); break;case 3: printf(“n Pop stack0(0) or stack1(1)?”); scanf(“%d”,&num); t=pop(&s, num); printf(“n pop number is %d”,t); break; p25 3.21 假设表达式由单字母变量和双目四则运算符构成。试写一个算法，将一个通常书写形式且书写正确的表达式转变成逆波兰式。解：算法基本思想：通常格式的表达式作为字符数组型的参数带入算法。需要用到运算

38、符堆栈，先进行堆栈的初始化，为了算法的处理，将代表最小优先级的#号压入堆栈。结果字符串初始化为空串。顺序从头至尾扫描通常格式的表达式的每一个符号，如果是运算数，就原封不动放入结果中，扫描下一字符。若是运算符，将此运算符与栈顶的运算符进行优先级的比较，若栈顶的优先级高，弹出堆栈的栈顶，将其加入到结果之中，该运算符再与新的栈顶比较优先级；若栈顶运算符优先级低，扫描到的运算符进栈，再扫描下一符号。若与栈顶的优先级相等，则丢弃弹出的栈顶，扫描下一符号。#include <string.h> /其中定义了字符处理函数typedef char elemtype; /定义堆栈的数据元素类型voi

39、d postfix(char *infix, char result) /通常书写形式的表达式存放在一个字符串中, 参数infix为带入的通常书写形式的表达式，返回与之等价的后缀表达式 stacktype S; /stacktype堆栈类型int i=0; /为正在处理的数组元素的下表 Initstack(S); /堆栈初始化 Push(S, #); /首先压入一个 #, 便于算法的运作 result= “ ”; /存放转换的结果 do switch(infixi) case “#”: /扫描到结束标志 while (!StackEmpty(S) strcat(result, Pop(S);

40、/弹出栈中的所有运算符, 输出到后缀表达式中, 后缀表达式也以 #作结束标志. return (result); /结束, 返回后缀表达式 case +, -, *, /, (, ): /运算符 while (priority(Top(S), infixi)=>) /第一种情况 strcat(result, Pop(S); if (priority(Top(S), infixi)=) Pop(S); /第三种情况 else Push(S, infixi); /第二种情况break; default: /运算数, 原样输出到后缀表达式中 strcat(result, infixi); br

41、eak; i+; /判断下一个字符 while (1); p25 3.22 试写一个算法、，对以逆波兰式表示的表达式求值解：算法基本思想：逆波兰式作为字符数组参数带入算法，算法将计算结果返回。要完成运算需要一个运算数堆栈。首先进行堆栈的初始化。对逆波兰式从左至右进行扫描，若扫描到的是运算数就压入到堆栈，如果扫描到的是运算符，则从堆栈中弹出2个运算数（注意先弹出的是右运算数，后弹出的是左运算数），进行运算后，结果仍然压于运算数栈。最终运算数栈的唯一值就是运算结果。#include <math.h>void compute (stacktype& S, char op) / S

42、为栈 int tag; /标志域, 记载取操作数的操作是否正确 double oprand1, oprand2; tag=GetTwoOperands(oprand1, operand2); /tag为1时, 表示取操作数函数运行正确 if (tag=1) switch(op) case + : push(S, operand2+ operand1); /加结果入栈 break; case - : push(S, operand2- operand1); /减结果入栈 break;case * : push(S, operand2* operand1); /乘结果入栈 break; case

43、/ : if (operand 1=0.0) /判断是否0除 printf(“ Divide by 0!n”); /0除错误 clear(S); /清除堆栈 else push(S, operand2 / operand1);/除结果入栈 break; case : push(S, pow(operand2, operand1); /指数运算,结果入栈. <math.h>中定义了pow break; else clear(S); /出错, 清除堆栈int GetTwoOperands(stacktype& S, double& opnd1, double&

44、opnd2) /取两个运算数 if (StackEmpty(S) /检查是否有第二运算数 printf(“ Missing Operands!n”); /缺少运算数 return (0); /取运算数操作不正确 opnd1=Pop(S); /取右运算数 if (StackEmpty(S) /检查是否有第一运算数 printf(“ Missing Operands!n”); /缺少运算数 return (0); /取运算数操作不正确 opnd2=Pop(S); /取左运算数 return (1); /正确取得两个运算数double Evaluation(char suffix) /表达式求值st

45、acktype S char c; int i=0, index; double newopnd;InitStack(s);while(c=suffixi; c != =) /从键盘输入表达式, 直到= switch(c) case +: case -: case *: case /: case : compute(S, c); /扫描到运算符, 计算 i+; break;default: /不是运算符, 肯定是运算数，假定运算数是实型运算数 newopnd=0.0 while (suffixi>='0'&&suffix<='9' )

46、 newopnd=newopnd*10+(suffixi-'0'); i+; if (suffixi= = '.') index=10; i+; /i 指到小数点后第一位 while (suffixi>='0'&&suffix<='9' ) newopnd=newopen+ (suffixi-'0')/index; i+; index=index*10; Push(S, newopnd); /运算数压入到堆栈中 break; /结束switch /结束while 循环 if (!Stac

47、kEmpty(S) /判断表达式是否正确, 输出结果，返回计算结果 printf(“ %lf”, Top(S); return(Top(s); p25 3.28 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应队列初始化、入队列和出队列的算法。解：算法基本思想：初始化时创建一个只有头结点的空队列，按题目要求，尾指针rear指向该头结点，并构成循环链表（rear->next=rear;)。入队时元素插入到队尾，修改尾指针，但注意保持为循环链表，(newp->next=rear->next; rear->next=newp;

48、rear = newp;)。差异较大的是出队算法，出队的是队头元素，注意该链表有附加头结点，所以要出队的结点为rear->next->next。出队时首先要判断队列是否为空；另外出队后还需判断原队列是否只有最后一个元素，若是，出队之后，该队列为空队列，需要修改rear指针，让其指向附加的头结点。#define LEN sizeof(LNode)typedef int elemtype;typedef struct nodeelemtype data;struct node* next; QNode, *LinkQ;QNode* InitQueue( QNode* rear) /初始

49、化带头结点的循环链表表示的队列rear=(QNode*) malloc(LEN); /创建头结点rear->next= rear; /构成循环return (rear);void EnQueue(QNode* rear, elemtype x) /入队操作QNode* newp;newp=(QNode*) malloc(LEN); /创建新结点newp->data=x;newp->next=rear->next;rear->next=newp;rear=newp;elemtype EnQueue(QNode* rear) /出队操作QNode* p;Elemtyp

50、e x;if (rear->next= =rear) return (NULLELEM); /队列为空p=rear->next->next; /注意有头结点x= p->data;if (p= =rear) /说明原队列只有一个元素，删除了这个元素，对列为空队列rear = rear->next; rear->next = rear; /构成只有头结点的循环空队列else rear->next->next=p->next; free(p);p26 3.30 假设将循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的位置和

51、内含元素的个数。试给出此循环队列的队满条件，并写出相应的入队列和出队列的算法（在出队列的算法中要返回队头元素）。解：队满的条件是 length= =Max(数组的最大长度），队空的条件是 length=0。算法基本思想：队列初始化时置rear=0，length=0。进队时，先判断是否队满；修改尾指针，注意构成循环队列(Q->rear=(Q->rear+1) % Max; Q->dataQ->rear=x;)，注意length进行加1操作。出队操作的差异较大，先判断队是否空；需要通过rear和length值求得队头的位置（front=(Q->rear+Max-q->length+1) % Max; )，注意length要进行减1操作，并返回出队的元数值。#define Max 100 /*定义最大循环队列长度*/队满的条件：length值等于Maxtypedef struct Elemtype dataMax; int rear, length ; SqQueue; /循环队列的存储结构int