《数据结构——C语言描述》习题及答案.pdf

第第 1 章章 绪绪 论论习题一、问答题1.什么是数据结构？2.四类基本数据结构的名称与含义。3.算法的定义与特性。4.算法的时间复杂度。5.数据类型的概念。6.线性结构与非线性结构的差别。7.面向对象程序设计语言的特点。8.在面向对象程序设计中，类的作用是什么？9.参数传递的主要方式及特点。10.抽象数据类型的概念。二、判断题1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。2.算法就是程序。3.在高级语言（如 C、或 PASCAL）中，指针类型是原子类型。三、计算下列程序段中 X=X+1 的语句频度for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;提示：i=1 时：1=(1+1)1/2=(1+12)/2 i=2 时：1+2=(1+2)2/2=(2+22)/2 i=3 时：1+2+3=(1+3)3/2=(3+32)/2 i=n 时：1+2+3+n=(1+n)n/2=(n+n2)/2f(n)=(1+2+3+n)+(12+22+32+n2)/2 =(1+n)n/2+n(n+1)(2n+1)/6 /2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3区分语句频度和算法复杂度：O(f(n)=O(n3)四、试编写算法求一元多项式 Pn(x)=a0+a1x+a2x2+a3x3+anxn的值 Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入 ai(i=0,1,n),x 和 n，输出为 Pn(x0).通常算法的输入和输出可采用下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。提示：float PolyValue(float a,float x,int n)核心语句：p=1;(x 的零次幂)s=0;i 从 0 到 n 循环s=s+ai*p;p=p*x;或：p=x;(x 的一次幂)s=a0;i 从 1 到 n 循环s=s+ai*p;p=p*x;实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案1.3 计算下列程序中 x=x+1 的语句频度 for(i=1;i=n;i+)for(j=1;j=i;j+)for(k=1;k=j;k+)x=x+1;【解答】x=x+1 的语句频度为：T(n)=1+(1+2)+（1+2+3）+（1+2+n）=n(n+1)(n+2)/61.4 试编写算法，求 pn(x)=a0+a1x+a2x2+.+anxn的值 pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为 ai(i=0,1,n)、x 和 n,输出为 Pn(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。【解答】（1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。（2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue()int i,n;float x,a,p;printf(“nn=”);scanf(“%f”,&n);printf(“nx=”);scanf(“%f”,&x);for(i=0;in;i+)scanf(“%f”,&ai);/*执行次数：n 次*/p=a0;for(i=1;i=n;i+)p=p+ai*x;/*执行次数：n 次*/x=x*x;printf(“%f”,p);算法的时间复杂度：T(n)=O(n)通过参数表中的参数显式传递float PolyValue(float a,float x,int n)float p,s;int i;p=x;s=a0;for(i=1;inext=S;（2）P-next=P-next-next;（3）P-next=S-next;（4）S-next=P-next;（5）S-next=L;（6）S-next=NULL;（7）Q=P;（8）while(P-next!=Q)P=P-next;（9）while(P-next!=NULL)P=P-next;（10）P=Q;（11）P=L;（12）L=S;（13）L=P;2.4 已知线性表 L 递增有序。试写一算法，将 X 插入到 L 的适当位置上，以保持线性表 L的有序性。提示：void insert(SeqList *L;ElemType x)（1）找出应插入位置 i，（2）移位，（3）参 P.2292.5 写一算法，从顺序表中删除自第 i 个元素开始的 k 个元素。提示：注意检查 i 和 k 的合法性。（集体搬迁，“新房”、“旧房”）以待移动元素下标 m（“旧房号”）为中心，计算应移入位置（“新房号”）：for(m=i1+k;mlast;m+)Lelem mk =Lelem m;同时以待移动元素下标 m 和应移入位置 j 为中心：以应移入位置 j 为中心，计算待移动元素下标：2.6 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于 mink 且小于 maxk 的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：mink 和 maxk 是给定的两个参变量，它们的值为任意的整数）。提示：注意检查 mink 和 maxk 的合法性：mink next;while(p!=NULL&pdata next;（2）找到最后一个应删结点的后继 s，边找边释放应删结点s=p;while(s!=NULL&sdata next;free(t);（3）prenext=s;2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1,a2.,an）逆置为（an,an-1,.,a1）。（1）以一维数组作存储结构，设线性表存于 a(1:arrsize)的前 elenum 个分量中。（2）以单链表作存储结构。方法 1：在原头结点后重新头插一遍方法 2：可设三个同步移动的指针 p,q,r，将 q 的后继 r 改为 p2.8 假设两个按元素值递增有序排列的线性表 A 和 B，均以单链表作为存储结构，请编写算法，将 A 表和 B 表归并成一个按元素值递减有序的排列的线性表 C，并要求利用原表（即 A 表和 B 表的）结点空间存放表 C.提示：参 P.28 例 2-1void merge(LinkList A;LinkList B;LinkList *C)pa=Anext;pb=Bnext;*C=A;(*C)next=NULL;while(pa!=NULL&pb!=NULL)if(padata data)smaller=pa;pa=panext;smallernext=(*C)next;/*头插法*/(*C)next=smaller;else smaller=pb;pb=pbnext;smallernext=(*C)next;(*C)next=smaller;while(pa!=NULL)smaller=pa;pa=panext;smallernext=(*C)next;(*C)next=smaller;while(pb!=NULL)smaller=pb;pb=pbnext;smallernext=(*C)next;(*C)next=smaller;LinkList merge(LinkList A;LinkList B)LinkList C；pa=Anext;pb=Bnext;C=A;Cnext=NULL;return C;2.9 假设有一个循环链表的长度大于 1，且表中既无头结点也无头指针。已知 s 为指向链表某个结点的指针，试编写算法在链表中删除指针 s 所指结点的前趋结点。提示：设指针 p 指向 s 结点的前趋的前趋，则 p 与 s 有何关系？2.10 已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。2.11 设线性表 A=(a1,a2,am)，B=(b1,b2,bn)，试写一个按下列规则合并 A、B 为线性表 C 的算法，使得：C=(a1,b1,am,bm,bm+1,bn)当 mn 时；或者 C=(a1,b1,an,bn,an+1,am)当 mn 时。线性表 A、B、C 均以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值 m 和 n 均未显式存储。提示：void merge(LinkList A;LinkList B;LinkList *C)或：LinkList merge(LinkList A;LinkList B)2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式中各自仅含奇次项或偶次项，并要求利用原链表中的结点空间来构成这两个链表。提示：注明用头指针还是尾指针。2.13 建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的 data域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算。提示：可将低位放在前面。2.14 设多项式 P(x)采用课本中所述链接方法存储。写一算法，对给定的 x 值，求 P(x)的值。提示：float PolyValue(Polylist p;float x)实习题1将若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。要求：（1）给定一个城市名，返回其位置坐标；（2）给定一个位置坐标 P 和一个距离 D，返回所有与 P 的距离小于等于 D 的城市。2约瑟夫环问题。约瑟夫问题的一种描述是：编号为 1，2，n 的 n 个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个整数作为报数上限值 m,从第一个人开始顺时针自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如 m 的初值为 20；n=7，7 个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为 6，1，4，7，2，3，5。第二章 答案 实习题二：约瑟夫环问题实习题二：约瑟夫环问题约瑟夫问题的一种描述为：编号 1,2,n 的 n 个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值 m,从第一个人开始顺时针自 1 开始顺序报数，报到 m 时停止报数。报 m 的人出列，将他的密码作为新的 m 值，从他在顺时针方向上的下一个人开始重新从 1 报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。例如，m 的初值为 20；n=7，7 个人的密码依次是：3,1,7,2,4,8,4，出列顺序为6,1,4,7,2,3,5。【解答】算法如下：typedef struct Nodeint password;int num;struct Node*next;Node,*Linklist;void Josephus()Linklist L;Node*p,*r,*q;int m,n,C,j;L=(Node*)malloc(sizeof(Node);/*初始化单向循环链表*/if(L=NULL)printf(n 链表申请不到空间!);return;L-next=NULL;r=L;printf(请输入数据 n 的值(n0):);scanf(%d,&n);for(j=1;jpassword=C;p-num=j;r-next=p;r=p;r-next=L-next;printf(请输入第一个报数上限值 m(m0):);scanf(%d,&m);printf(*n);printf(出列的顺序为:n);q=L;p=L-next;while(n!=1)/*计算出列的顺序*/j=1;while(jnext;j+;printf(%d-,p-num);m=p-password;/*获得新密码*/n-;q-next=p-next;/*p 出列*/r=p;p=p-next;free(r);printf(%dn,p-num);2.7 试分别以不同的存储结构实现单线表的就地逆置算法，即在原表的存储空间将线性表（a1,a2,an）逆置为(an,an-1,a1)。【解答】（1）用一维数组作为存储结构 void invert(SeqList *L,int *num)int j;ElemType tmp;for(j=0;jnext=NULL)return;/*链表为空*/p=L-next;q=p-next;p-next=NULL;/*摘下第一个结点，生成初始逆置表*/while(q!=NULL)/*从第二个结点起依次头插入当前逆置表*/r=q-next;q-next=L-next;L-next=q;q=r;2.11 将线性表 A=(a1,a2,am),B=(b1,b2,bn)合并成线性表 C,C=(a1,b1,am,bm,bm+1,.bn)当 mn 时,线性表 A、B、C 以单链表作为存储结构，且 C 表利用 A 表和 B 表中的结点空间构成。注意：单链表的长度值 m 和 n 均未显式存储。【解答】算法如下：LinkList merge(LinkList A,LinkList B,LinkList C)Node *pa,*qa,*pb,*qb,*p;pa=A-next;/*pa 表示 A 的当前结点*/pb=B-next;p=A;/*利用 p 来指向新连接的表的表尾，初始值指向表 A 的头结点*/while(pa!=NULL&pb!=NULL)/*利用尾插法建立连接之后的链表*/qa=pa-next;qb=qb-next;p-next=pa;/*交替选择表 A 和表 B 中的结点连接到新链表中；*/p=pa;p-next=pb;p=pb;pa=qa;pb=qb;if(pa!=NULL)p-next=pa;/*A 的长度大于 B 的长度*/if(pb!=NULL)p-next=pb;/*B 的长度大于 A 的长度*/C=A;return(C);第第 3 章章 限定性线性表限定性线性表 栈和队列栈和队列习 题1.按图 3.1(b)所示铁道（两侧铁道均为单向行驶道）进行车厢调度，回答：如进站的车厢序列为 123，则可能得到的出站车厢序列是什么？123、213、132、231、321（312）如进站的车厢序列为 123456，能否得到 435612 和 135426 的出站序列，并说明原因。（即写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X62.设队列中有 A、B、C、D、E 这 5 个元素，其中队首元素为 A。如果对这个队列重复执行下列 4 步操作：（1）输出队首元素；（2）把队首元素值插入到队尾；（3）删除队首元素；（4）再次删除队首元素。直到队列成为空队列为止，则是否可能得到输出序列：（1）A、C、E、C、C （2）A、C、E（3）A、C、E、C、C、C （4）A、C、E、C提示：A、B、C、D、E （输出队首元素 A）A、B、C、D、E、A （把队首元素 A 插入到队尾）B、C、D、E、A （删除队首元素 A）C、D、E、A （再次删除队首元素 B）C、D、E、A（输出队首元素 C）C、D、E、A、C （把队首元素 C 插入到队尾）D、E、A、C （删除队首元素 C）E、A、C （再次删除队首元素 D）3.给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？4.按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程：AB5.试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列 1&序列 2模式的字符序列。其中序列 1 和序列 2中都不含字符&，且序列 2是序列 1 的逆序列。例如，a+b&b+a是属该模式的字符序列，而+&则不是。提示：（1）边读边入栈，直到&（2）边读边出栈边比较，直到6.假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。提示：例：中缀表达式：a+b 后缀表达式:ab+中缀表达式：a+bc 后缀表达式:abc+中缀表达式：a+bc-d 后缀表达式:abc+d-中缀表达式：a+bc-d/e 后缀表达式:abc+de/-中缀表达式：a+b(c-d)-e/f 后缀表达式:abcd-+ef/-后缀表达式的计算过程：（简便）顺序扫描表达式，（1）如果是操作数，直接入栈；（2）如果是操作符 op，则连续退栈两次，得操作数 X,Y，计算 X op Y，并将结果入栈。如何将中缀表达式转换为后缀表达式？顺序扫描中缀表达式，（1）如果是操作数，直接输出；（2）如果是操作符 op2，则与栈顶操作符 op1比较：如果 op2 op1，则 op2入栈；如果 op2=op1，则脱括号；如果 op2 op1，则输出 op1；7.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设头指针），试编写相应的队列初始化、入队列和出队列的算法。提示：参 P.56 P.70 先画图.typedef LinkList CLQueue;int InitQueue(CLQueue*Q)int EnterQueue(CLQueue Q,QueueElementType x)int DeleteQueue(CLQueue Q,QueueElementType*x)8.要求循环队列不损失一个空间全部都能得到利用,设置一个标志域 tag,以 tag 为 0或 1 来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。提示：初始状态：front=0,rear=0,tag=0 队空条件：front=rear,tag=0 队满条件：front=rear,tag=1 其它状态：front!=rear,tag=0（或 1、2）入队操作：（入队）if(front=rear)tag=1；（或直接 tag=1）出队操作：（出队）tag=0；问题：如何明确区分队空、队满、非空非满三种情况？9.简述以下算法的功能（其中栈和队列的元素类型均为 int）：（1）void proc_1(Stack S)iint i,n,A255;n=0;while(!EmptyStack(S)n+;Pop(&S,&An);for(i=1;itop=-1 表示栈空。判断栈 S 满：如果 S-top=Stack_Size-1 表示栈满。（2）链栈（top 为栈顶指针，指向当前栈顶元素前面的头结点）判断栈空：如果 top-next=NULL 表示栈空。判断栈满：当系统没有可用空间时，申请不到空间存放要进栈的元素，此时栈满。3.4 照四则运算加、减、乘、除和幂运算的优先惯例，画出对下列表达式求值时操作数栈和运算符栈的变化过程：A-B*C/D+EF【解答】3.5 写一个算法，判断依次读入的一个以为结束符的字母序列，是否形如序列 1&序列2的字符序列。序列 1 和序列 2 中都不含&，且序列 2 是序列 1 的逆序列。例如，a+b&b+a是属于该模式的字符序列，而1+3&3-1则不是。【解答】算法如下：int IsHuiWen()Stack *S;Char ch,temp;InitStack(&S);Printf(“n 请输入字符序列：”);Ch=getchar();While(ch!=&)/*序列 1 入栈*/Push(&S,ch);ch=getchar();do /*判断序列 2 是否是序列 1 的逆序列*/ch=getchar();Pop(&S,&temp);if(ch!=temp)/*序列 2 不是序列 1 的逆序列*/return(FALSE);printf(“nNO”);while(ch!=&!IsEmpty(&S)if(ch=&IsEmpty(&S)return(TRUE);printf(“nYES”);/*序列 2 是序列 1 的逆序列*/else return(FALSE);printf(“nNO”);/*IsHuiWen()*/3.8 要求循环队列不损失一个空间全部都能得到利用，设置一个标志 tag,以 tag 为 0 或 1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。【解答】入队算法：int EnterQueue(SeqQueue *Q,QueueElementType x)/*将元素 x 入队*/if(Q-front=Q-front&tag=1)/*队满*/return(FALSE);if(Q-front=Q-front&tag=0)/*x 入队前队空，x 入队后重新设置标志*/tag=1;Q-elememtQ-rear=x;Q-rear=(Q-rear+1)%MAXSIZE;/*设置队尾指针*/Return(TRUE);出队算法：int DeleteQueue(SeqQueue *Q,QueueElementType *x)/*删除队头元素，用 x 返回其值*/if(Q-front=Q-rear&tag=0)/*队空*/return(FALSE);*x=Q-elementQ-front;Q-front=(Q-front+1)%MAXSIZE;/*重新设置队头指针*/if(Q-front=Q-rear)tag=0;/*队头元素出队后队列为空，重新设置标志域*/Return(TUUE);编写求解 Hanoi 问题的算法，并给出三个盘子搬动时的递归调用过程。【解答】算法：void hanoi(int n,char x,char y,char z)/*将塔座 X 上按直径由小到大且至上而下编号为 1 到 n 的 n 个圆盘按规则搬到塔座 Z上，Y 可用做辅助塔座*/if(n=1)move(x,1,z);else Hanoi(n-1,x,z,y);move(x,n,z);Hanoi(n-1,y,x,z);Hanoi(3,A,B,C)的递归调用过程：Hanoi(2,A,C,B):Hanoi(1,A,B,C)move(A-C)1 号搬到 C Move(A-B)2 号搬到 B Hanoi(1,C,A,B)move(C-B)1 号搬到 B Move(A-C)3 号搬到 CHanoi(2,B,A,C)Hanoi(1,B,C,A)move(B-A)1 号搬到 A Move(B-C)2 号搬到 C Hanoi(1,A,B,C)move(A-C)1 号搬到 C第第 4 章章串串习题1.设 s=I AM A STUDENT,t=GOOD,q=WORKER。给出下列操作的结果：StrLength(s);SubString(sub1,s,1,7);SubString(sub2,s,7,1);StrIndex(s,A,4);StrReplace(s,STUDENT,q);StrCat(StrCat(sub1,t),StrCat(sub2,q);参考答案StrLength(s)=14;sub1=I AM A_;sub2=_;StrIndex(s,A,4)=6;StrReplace(s,STUDENT,q)=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)=I AM A GOOD WORKER;2.编写算法，实现串的基本操作 StrReplace(S,T,V)。3.假设以块链结构表示串，块的大小为 1，且附设头结点。试编写算法，实现串的下列基本操作：StrAsign(S,chars)；StrCopy(S,T)；StrCompare(S,T)；StrLength(S)；StrCat(S,T)；SubString(Sub,S,pos,len)。说明：用单链表实现。4.叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。5.已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S 转换为 T.6.S 和 T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串 S 中首次与 T 匹配的子串逆置。7.S 是用结点大小为 4 的单链表存储的串,分别编写算法在第 k 个字符后插入串 T，及从第k 个字符删除 len 个字符。以下算法用定长顺序串：8.写下列算法：（1）将顺序串 r 中所有值为 ch1 的字符换成 ch2 的字符。（2）将顺序串 r 中所有字符按照相反的次序仍存放在 r 中。（3）从顺序串 r 中删除其值等于 ch 的所有字符。（4）从顺序串 r1 中第 index 个字符起求出首次与串 r2 相同的子串的起始位置。（5）从顺序串 r 中删除所有与串 r1 相同的子串。9.写一个函数将顺序串 s1 中的第 i 个字符到第 j 个字符之间的字符用 s2 串替换。提示：（1）用静态顺序串 （2）先移位，后复制10.写算法，实现顺序串的基本操作 StrCompare(s,t)。11.写算法，实现顺序串的基本操作 StrReplace(&s,t,v)。提示：（1）被替换子串定位（相当于第 9 题中 i）（2）被替换子串后面的字符左移或右移（为替换子串准备房间）（3）替换子串入住（复制）（4）重复上述，直到第四章答案4.1 设 s=I AM A STUDENT，t=GOOD，q=WORKER。给出下列操作的结果：【解答】StrLength(s)=14;SubString(sub1,s,1,7)sub1=I AM A;SubString(sub2,s,7,1)sub2=;StrIndex(s,4,A)=6;StrReplace(s,STUDENT,q);s=I AM A WORKER;StrCat(StrCat(sub1,t),StrCat(sub2,q)sub1=I AM A GOOD WORKER。4.2 编写算法，实现串的基本操作 StrReplace(S,T,V)。【解答】算法如下：int strReplace(SString S,SString T,SString V)/*用串 V 替换 S 中的所有子串 T*/int pos,i;pos=strIndex(S,1,T);/*求 S 中子串 T 第一次出现的位置*/if(pos=0)return(0);while(pos!=0)/*用串 V 替换 S 中的所有子串 T*/switch(T.len-V.len)case 0:/*串 T 的长度等于串 V 的长度*/for(i=0;ichpos+i=V.chi;case 0:/*串 T 的长度大于串 V 的长度*/for(i=pos+t.ien;ilen;i-)/*将 S 中子串 T 后的所有字符 S-chi-t.len+v.len=S-chi;前移 T.len-V.len 个位置*/for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len;case len-T.len+V.len)len-T.len+V.len;i=pos+T.len;i-)S-chi=S-chi-T.len+V.len;for(i=0;ichpos+i=V.chi;S-len=S-len-T.len+V.len;else /*替换后串长MAXLEN,但串 V 可以全部替换*/if(pos+V.len=pos+T.len;i-)S-chi=s-chi-T.len+V.len for(i=0;ichpos+i=V.chi;S-len=MAXLEN;else /*串 V 的部分字符要舍弃*/for(i=0;ichi+pos=V.chi;S-len=MAXLEN;/*switch()*/pos=StrIndex(S,pos+V.len,T);/*求 S 中下一个子串 T 的位置*/*while()*/return(1);/*StrReplace()*/附加题：用链式结构实现定位函数。【解答】typedef struct Node char data;struct Node *next;Node,*Lstring;int strIndex(Lstring S,int pos,Lstring T)/*从串 S 的 pos 序号起，串 T 第一次出现的位置*/Node *p,*q,*Ppos;int i=0，,j=0;if(T-next=NULL|S-next=NULL)return(0);p=S-next;q=T-next;while(p!=NULL&jnext;j+;if(j!=pos)return(0);while(p!=NULL&q!=NULL)Ppos=p;/*Ppos 指向当前匹配的起始字符*/if(p-data=q-data)p=p-next;q=q-next;else /*从 Ppos 指向字符的下一个字符起从新匹配*/p=Ppos-next;q=T-head-next;i+;if(q=NULL)return(pos+i);/*匹配成功*/else return(0);/*失败*/第五章第五章 数组和广义表数组和广义表习 题1.假设有 6 行 8 列的二维数组 A，每个元素占用 6 个字节，存储器按字节编址。已知 A的基地址为 1000，计算：（1）数组 A 共占用多少字节；（288）（2）数组 A 的最后一个元素的地址；（1282）（3）按行存储时，元素 A36的地址；（1126）（4）按列存储时，元素 A36的地址；（1192）注意：本章自定义数组的下标从 1 开始。2设有三对角矩阵（aij）nn,将其三条对角线上的元素逐行地存于数组 B(1:3n-2)中，使得Bk=aij，求：（1）用 i,j 表示 k 的下标变换公式；（2）用 k 表示 i,j 的下标变换公式。i=k/3+1,j=k%3+i-1=k%3+k/3 或：i=k/3+1,j=k-2(k/3)3.假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元组表 C 存放结果矩阵。提示：参考 P.28 例、P.47 例。4在稀疏矩阵的快速转置算法 5.2 中，将计算 positioncol的方法稍加改动，使算法只占用一个辅助向量空间。提示：（1）position k 中为第 k 列非零元素个数，k=1,2,n（2）position 0 =1;（第 1 列中第一个非零元素的正确位置）（3）position k =position k 1 +position k ,k=1,2,n（4）position k =position k 1 ,k=n,n 1,15写一个在十字链表中删除非零元素 aij的算法。提示：“删除”两次，释放一次。6画出下面广义表的两种存储结构图示：(a),b),(),d),(e,f)7求下列广义表运算的结果：（1）HEAD(a,b),(c,d);（2）TAIL(a,b),(c,d);（3）TAILHEAD(a,b),(c,d);（4）HEADTAILHEAD(a,b),(c,d);b（5）TAILHEADTAIL(a,b),(c,d);(d)第一种存储结构（自底向上看）第一种存储结构（自底向上看）111110f0e0a11111110b0d参考题8试设计一个算法，将数组 A（0:n-1）中的元素循环右移 k 位，并要求只用一个元素大小的附加存储，元素移动或交换次数为 O(n)。9假设按低下标优先（以最左的下标为主序）存储整数数组 A（1:8,1:2,1:4,1:7）时，第一个元素的字节地址是 100，每个整数占 4 个字节，问元素 A(4,2,3,5)的存储地址是什么？10.高下标优先（以最右的下标为主序）存储整数数组 A（1:8,1:2,1:4,1:7）时，顺序列出数组 A 的所有元素。11试编写一个以三元组形式输出用十字链表表示的稀疏矩阵中非零元素及其下标的算法。实习题1若矩阵 Amn中的某个元素 aij是第 i 行中的最小值，同时又是第 j 列中的最大值，则称此元素为该矩阵中的一个马鞍点。假设以二维数组存储矩阵，试编写算法求出矩阵中的所有马鞍点。第五章答案5.2 三对角矩阵 Ann,将其三条对角线上的元素逐行的存于数组 B1.3n-2中，使得 Bk=aij，求：（1）用 i,j 表示 k 的下标变换公式；（2）用 k 表示 i、j 的下标变换公式。【解答】（1）k=2(i-1)+j(2)i=k/3+1,j=k/3+k%3 （取整，%取余）5.4 稀疏矩阵的快速转置算法 5.2 中，将计算 positioncol的方法稍加改动，使算法只占用一个辅助向量空间。【解答】算法（一）FastTransposeTSMatrix(TSMartrix A,TSMatrix *B)/*把矩阵 A 转置到 B 所指向的矩阵中去，矩阵用三元组表表示*/int col,t,p,q;int positionMAXSIZE;B-len=A.len;B-n=A.m;B-m=A.n;if(B-len0)position1=1;for(t=1;t=A.len;t+)positionA.datat.col+1+;/*positioncol存放第 col-1 列非零元素的个数,即利用 poscol来记录第 col-1 列中非零元素的个数*/*求 col 列中第一个非零元素在 B.data 的位置，存放在 positioncol中*/for(col=2;col=A.n;col+)positioncol=positioncol+positioncol-1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e;Positioncol+;算法(二)FastTransposeTSMatrix(TSMartrix A,TSMatrix *B)int col,t,p,q;int positionMAXSIZE;B-len=A.len;B-n=A.m;B-m=A.n;if(B-len0)for(col=1;col=A.n;col+)positioncol=0;for(t=1;t0;col-)t=t-positioncol;positioncol=t+1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e;Positioncol+;5.6 画出下面广义表的两种存储结构图示：(a),b),(),d),(e,f)【解答】5.7 求下列广义表运算的结果：（6）HEAD(a,b),(c,d);(a,b)（7）TAIL(a,b),(c,d);(c,d)（8）TAILHEAD(a,b),(c,d);(b)（9）HEADTAILHEAD(a,b),(c,d);b（10）TAILHEADTAIL(a,b),(c,d);(d)第六章第六章 树和二叉树树和二叉树习 题1试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。2对题 1 所得各种形态的二叉树，分别写出前序、中序和后序