资源描述
线性结构习题解答习题解答3.设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。(1)for (int i = 1; i = n; i+) for (int j = 1; j = n; j+) cij = 0.0; for (int k = 1; k = n; k+) cij = cij + aik * bkj; (2)x = 0; y = 0; for (int i = 1; i = n; i+) for (int j = 1; j = i; j+) for (int k = 1; k = j; k+) x = x + y;(3)int i = 1, j = 1; while (i=n & j=n) i = i + 1; j = j + i; (4)*int i =1; do for (int j = 1; j = n; j+) i = i + j; while(iarraySize或者对于某一个k (0 k n)，使得k!*2k maxInt时，应按出错处理。可有如下三种不同的出错处理方式：(1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误；(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】#include const int arraySize = 100;const int MaxInt = 0x7fffffff;int calc( int T , int n ) int i, value = 1;T0=1;if ( n != 0 ) int edge = MaxInt / n / 2;for ( i = 1; i edge ) return 0;value *= n * 2;Tn = value;printf(A %d = %dn”,n,Tn);return 1;void main ( ) int AarraySize;int i;for ( i = 0; i length;for( int i = 0; i datai; A-datai = A-datan-i-1; A-datan-i-1 = tmp;时间复杂度：需进行n/2次循环，因此时间复杂度为O(n)；空间复杂度：使用一个整形辅助存储单元tmp，因此空间复杂度为O(1)。6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?【解答】若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(Averagy Moving Number )为删除时平均移动元素个数AMN为 7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。(1) 从顺序表中删除具有给定值x的所有元素。(2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。(4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc。(5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。【解答】(1) 从顺序表中删除具有给定值x的所有元素。void DelValue(listtype * L, int x )int i = 0, j;while ( i length )/*循环, 寻找具有值x的元素并删除它*/if (L-datai = x ) /*删除具有值x的元素, 后续元素前移*/for (j = i;j length-1; j+ ) L-dataj = L-dataj+1;L-length-; /*表长减1*/else i+;(2) 实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下：void DelValue_s_to_t (listtype *L,int s, int t)int i,j;if ( L-length = 0 | s = t ) printf(“List is empty or parameters are illegal!n”); exit(1); i = 0;while ( i length)/*循环, 寻找具有值x的元素并删除它*/if (L-datai=s &L-datai= t)/*删除满足条件的元素, 后续元素前移*/for ( j = i; j length-1; j+ ) L-dataj = L-dataj+1;L-length-; /*表长减1*/else i+;(3) 实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下：void DelValue_s_to_t_1 (listtype *L,int s int t)int i,j,k;if ( L-length = 0 | s = t ) printf(“List is empty or parameters are illegal!n”); exit(1); for (i = 0; i length; i+ ) /*循环, 寻找值 s 的第一个元素*/if ( L-datai = s ) break; /*退出循环时, i指向该元素*/if ( i length ) for (j = 1; i + j length; j+ )/*循环, 寻找值 t 的第一个元素*/if (L-datai+j t ) break;/*退出循环时, i+j指向该元素*/ for (k = i+j; k length; k+ ) /*删除满足条件的元素, 后续元素前移*/L-datak-j = L-datak; L-length-= j; /*表长减j*/(4) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：listtype * Merge(listtype *LA,listtype *LB )/*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回listtype *LC;int value1,value2;int i,j,k;initiatelist(LC);if (LA-length + LB-length MAXSIZE) printf(“表上溢/n”; exit(1); i = 0, j = 0, k = 0;value1 = LA-datai;value2 = LB-dataj;while (i length & j length ) /*循环, 两两比较, 小者存入结果表*/if (value1 datak = value1; i+; value1=LA-datai; else LC-datak = value2; j+; value2=LB-dataj;k+; while( i length)/*当LA表未检测完, 继续向结果表传送*/LC-datak = value1; i+; k+; value1 = LA-datai; while( j length)/*当LB表未检测完, 继续向结果表传送*/LC-datak = value2; j+; k+; value2 = LB-dataj;LC-length = k;return LC;(5) 实现从表中删除所有其值重复的元素的函数如下：void DelDouble(listtype *L)int i,j,k;int tmp;if(L-length = 0 ) printf(“表空n”; exit(1); i=0;while ( i length ) /*循环检测*/j = i + 1; tmp = L-datai;while( j length ) /*对于每一个i, 重复检测一遍后续元素*/if( tmp = L-dataj) /*如果相等,删除此结点，后续元素前移*/ for( k = j+1; k length; k+ ) L-datak-1 = L-datak;L-length-; /*表最后元素位置减1*/else j+; i+;/*检测完L-datai, 检测下一个*/8.线性表可用顺序表或链表存储。试问：(1) 两种存储表示各有哪些主要优缺点?(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解答】(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。(3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。/*-链表结构的定义.为简化起见，表元素我们使用整型数据-此链表带头结点-*/typedef struct mynodeint data; /*数据域：整型*/struct mynode *next; /*指针域*/ node, linklisttype;9.试写出计算线性链表长度的算法。int lengthsl(linklisttype *L)linklisttype * p;int len;if(L = NULL)return 1;p = L-next;/* p指向链表L的头结点*/len = 0;while(p != NULL)len+;p = p-next;return len;10.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。【解答】void LinkListInverse(linklisttype *L)linklisttype *p, *pre, *next;if(L = NULL | L-next = NULL ) return; /*表未初始化，或为空表*/ p = L-next;pre = L;while( p != NULL ) /*循环修改链表中所有结点的后继指针的指向*/next = p-next;/*取当前结点的后继指针*/p-next = pre;/*当前结点的后继改为指向其原来的前驱*/pre = p , p=next;/*指针后移*/L-next-next = NULL;/*原第一个结点改为最后一个结点*/L-next = pre;/*链表的头结点指向原最后一个结点*/11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。【解答】void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB)/*将链表L分解为LA、LB两个链表，其中LA中结点值均为正，LB中结点值均为负，并删除结点值为零的结点,最后释放L的头结点。*/linklisttype *p , *pt , *pa, * pb;LA = initiatesl();pa = LA;/*指向LA中的最后一个结点*/LB = initiatesl();pb = LB;/*指向LB中的最后一个结点*/If(L = NULL | L-next = NUUL) return;/*L为空指针或L为空表*/p = L-next;/*p指向链表L的第一个结点*/while(p != NULL)/*遍历链表L*/if(p-data 0)/*将p链入链表LA的pa后*/pa-next = p;pa = p;p = p-next;elseif(p-data next = p;pb = p;p = p-next;else/*删除值为0的结点*/pt = p-next;/*记录当前结点的后继，以便删除当前结点*/free(p);p = pt;pa-next = NULL;pb-next = NULL;free(L);12设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。【解答】void linklistMerge(linklisttype *LA,linklisttype *LB )/*合并有序链表LA与LB,结果存入LA中，并释放LB的头结点 */linklisttype *pa, *pb , *pre ,*pn;if(LA = NULL | LB = NULL |) return;if(LA-next = NULL)/*LA为空表，则直接将LB链入LA即可*/LA-next = LB-next;free(LB);retrun;if(LB-next = NULL) return;/*LB为空表，则直接返回即可*/pa = LA-next, pb = LB-next ,pre=LA;while (pa != NULL & pb != NULL)/*循环, 两两比较, 小者存入结果表*/if(pa-data pb-next)/*将pb链入LA，然后pb指针后移*/pre-next = pb;pn = pb-next;pb-next = pa;pb = pn;pre = pre-next else/*pa指针后移*/pa = pa-next;pre = pre-next;if(pb != NULL)/*将pb剩余结点链入LA*/pre-next = pb;free(LB);13设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。【解答】Linklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB )/*合并有序链表LA与LB,结果存入LC中，并释放LA、LB的头结点 ,函数返回LC*/linklisttype *pa, *pb , *p;if(LA = NULL | LB = NULL |) return;LC = initiatesl();pa = LA-next, pb = LB-next;while (pa != NULL & pb != NULL)/*循环, 两两比较, 大者存入LC*/if(pa-data pb-next)/*将pa链为LC的第一个结点*/p = pa-next;pa-next = LC-next;LC-next = pa;pa = p; else/*将pa链为LC的第一个结点*/p = pb-next;pb-next = LC-next;LC-next = pb;pb = p;while(pa != NULL)/*将pa剩余结点链入LC*/p = pa-next;pa-next = LC-next;LC-next = pa;pa = p;while(pb != NULL)/*将pb剩余结点链入LC*/p = pb-next;pb-next = LC-next;LC-next = pb;pb = p;free(LA);free(LB);14.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。【解答】设此循环链表为单链表，则其类型定义与一般单链表相同typedef struct mynode cyclelisttype;void search_movefirst(cyclelisttype *CL, int x)cyclelisttype * p , *pre;if(CL = NULL) return;p = CL-next;pre = CL;while(p != CL)/*查找x，注意与普通单链表在判断是否到表尾上的不同*/if(p-data = x)break;elsepre = p;p = p-next;if(p != CL)/*查找成功*/per-next = p-next;/*在原来位置删除p*/p-next = CL-next;/*p插入到CL后*/CL-next = p;16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。【解答】(1) 可能的不同出栈序列有 种。(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 13542617.试证明：若借助栈可由输入序列1, 2, 3, , n得到一个输出序列p1, p2, p3, , pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i j k，使得pj pk pi。(提示：用反证法)【解答】因为借助栈由输入序列1, 2, 3, , n，可得到输出序列p1, p2, p3, , pn ，如果存在下标i, j, k，满足i j k，那么在输出序列中，可能出现如下5种情况： i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pi pj pk, 不可能出现pj pk pi的情形； i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pi pk pj , 不可能出现pj pk pi的情形； i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj pi pk, 不可能出现pj pk pi的情形； i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk pi pj, 也不可能出现pj pk pi的情形； i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面pi 位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pk pj pi, 也不可能出现pj pk top0 top1 = MAXSIZE);判栈满int DoubleStackFull(DoubleStack * DS)return(DS-top1-DS-top0=1);入栈int PopDoubleStack(DoubleStack * DS,int StackNo,elemtype x)/*将数据元素x插入到栈StackNo中*/if(DoubleStackFull(DS) return(FALSE);/*栈满溢出*/if(StackNo=0)/*对第0栈插入*/DS-top0+;DS-datatop0=x;else/*对第1栈插入*/DS-top1-;DS-datatop1=x;return(TRUE);删除算法elemtype PushDoubleStack(DoubleStack * DS,int StackNo)/*从StackNo栈中删除并返回一个元素，若栈空，则返回NULL*/if(DoubleStackEmpty(DS,StackNo) return(NULL);if(StackNo=0)/*对0号栈进行操作*/DS-top0-;return(DS-dataDS-top0+1);elseDS-top1+;return(DS-dataDS-top1-1);19.改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。【解答】void push(stack * S,elemtype x) if(StackEmpty(S) stackFull(S);/栈满，做溢出处理S-top +;S-dataS-top = x;/进栈void stackFull(stack *S)elemtype *temp;temp=calloc(3*MAXSIZE,sizeof(elemtype); /创建体积大二倍的数组for ( int i = 0; i top; i+ ) /传送原数组的数据tempi = S-datai;free(S-data);/删去原数组MAXSIZE *= 3; /数组最大体积增长二倍S-data = temp;/新数组成为栈的数组空间20.根据教案中给出的优先级，回答以下问题：(1) 在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈(NS)中最多可存入多少个元素？(2) 如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？【解答】(1) 如果表达式e含有n个运算符和分界符，则可能的运算对象有n+1个。因此在利用后缀表达式求值时所用到的运算对象栈中最多可存入n+1个元素。(2) 同上。21.表达式的中缀表示为a * x - b / x2，试利用栈将它改为后缀表示ax * bx2/ -。写出转换过程中栈的变化。(表示乘方运算)【解答】若设当前扫描到的运算符ch的优先级为icp(ch)，该运算符进栈后的优先级为isp(ch)，则可规定各个算术运算符的优先级如下表所示。 运算符 ; ( *,/, % +, - ) isp 0 1 7 5 3 8 icp 0 8 6 4 2 1isp也叫做栈内(in stack priority)优先数，icp也叫做栈外(in coming priority)优先数。当刚扫描到的运算符ch的icp(ch)大于isp(stack)时，则ch进栈；当刚扫描到的运算符ch的icp(ch)小于isp(stack)时，则位于栈顶的运算符退栈并输出。从表中可知，icp(“(”)最高，但当“(”进栈后，isp(“(”)变得极低。其它运算符进入栈中后优先数都升1，这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求。运算符优先数相等的情况只出现在括号配对“)”或栈底的“;”号与输入流最后的“;”号配对时。前者将连续退出位于栈顶的运算符，直到遇到“(”为止。然后将“(”退栈以对消括号，后者将结束算法。步序扫描项项类型 动 作栈的变化 输 出 0F ; 进栈, 读下一符号; 1 a操作数F 直接输出, 读下一符号;A 2 *操作符F isp ( ; ) icp ( - ), 退栈输出; a x * F isp ( ; ) icp ( - ), 进栈, 读下一符号; -a x * 5 b操作数F 直接输出, 读下一符号; -a x * b 6 /操作符F isp ( - ) icp ( / ), 进栈, 读下一符号 ; -/a x * b 7 x操作数F 直接输出, 读下一符号; -/a x * b x 8 操作符F isp ( / ) icp ( ; ), 退栈输出; -/a x * b x 2 F isp ( / ) icp ( ; ), 退栈输出; -a x * b x 2/ F isp ( - ) icp ( ; ), 退栈输出; a x * b x 2/ - F 结束22.设循环队列的容量为70（序号从1到70），经过一系列入队和退队运算后，有：（1）front=15，rear=46；（2）front=45，rear=10问在上述两种情况下，循环队列中各有多少个元素？【解答】(1) 队列中元素的个数为(MAXSIZE+rear-front) %MAXSIZE = (70+46-15)%70=31(2) 队列中元素的个数为(MAXSIZE+rear-front) %MAXSIZE = (70+10-45)%70=3523.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。设此队列含头结点，队头指针front指向头结点，限定在表头端删除队列空：队尾指针指向头结点，即rear=front时，队空队列满：因为是链表，所以，只有内存空间不足时才会有队满的问题。void insertqueue(queuetype *Q,int location,elemtype x)/*Q:指向队列的指针；location:插入位置，0表示队头，1表示队尾；x:数据元素*/node *p;p=(node *)malloc(sizeof(node);p-data = x;if(location=0)/*在队头处插入*/p-next = Q-front-next;Q-front-next = p;if(Q-rear=Q-front)Q-rear = p;/*对空表插入*/else/*在队尾处插入*/p-next = NULL;Q-rear-next = p;Q-rear = p;elemtype deletequeue(queuetype *Q)elemtype x;node * p;if(Q-rear = Q-front) return(NULL); /*空队列*/p = Q-front-next;x = p-data;Q-front-next = p-next;if(Q-rear = p)Q-rear = Q-front/*对只有一个元素的队列进行删除*/free(p);return(x);24.所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。【解答1】将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。算法如下：int palindrome (string S) stacktype * st;int yes = 1, i = 0;while(Si != “0”)push (st,Si); i+; /*扫描字符串，所有字符进栈*/i = 0;while(Si != “0” )/*比较字符串*/ if(Si = st.GetTop( )pop(st); i+; else yes = 0; break; return(yes);【解答2】采用递归算法，判断从s到e中的字符串是否回文，通过函数返回是或不是。int palindrome(char A , int start, int end) if (Astart != Aend ) return 0; else if ( s e ) return 1; else palindrome ( A, start+1, end-1 );25.设Ann为一个上三角矩阵，将A中所有非零元素按列序顺次存入一维数组B中，则A与B元素的对应关系是什么？【解答】上三角矩阵如下所示其数据元素满足Aij=0，对所有的ij上三角矩阵正好是一个下三角矩阵的转秩，我们知道，一个下三角矩阵按行压缩存储时，矩阵元素与一维数组的对应关系为AijBi*(i+1)/2+j，对所有的ij；因此，下三角矩阵按列序存储在一维数组中的元素对应关系为AijBj*(j+1)/2+i，对所有的ij.26.编写串的替换函数Replace(str,str1,str2)，将主串str中所有子串str1替换为str2。【解答】见书p58第 17 页 共 16 页
展开阅读全文