《数据结构与算法(徐凤生)》题答案

数据结构与算法习题答案目录 第1章 2 第2章 7 第3章 13 第4章 21 第5章 26 第6章 32 第7章 42 第8章 54 第9章 60 第10章 64习题11.解释下列术语：数据、数据元素、数据对象、数据结构.解：数据是用于描述客观事物的数值、字符以与一切可以输入到计算机中并由计算机程序加以处理的符号的集合,是计算机操作的对象的总称.数据元素是数据的基本单位,它是数据中的一个个体.有时,一个数据元素可有若干数据项组成,.数据项是数据的不可分割的最小单位.数据对象是具有相同性质的数据元素的集合,是数据的一个子集.数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合.2.数据类型和抽象数据类型是如何定义的？两者有何异同？抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？解：数据类型是一个值的集合和定义在此集合上的一组操作的总称.例如,C语言中的整型变量,其值为某个区间上的整数,定义在其上的操作为加、减、乘、除和取模等算术运算.抽象数据类型是指一个数学模型以与定义在此数学模型上的一组操作.例如,整数是一个抽象数据类型,其数学特性和具体的计算机或语言无关.抽象的意义在于强调数据类型的数学特性.抽象数据类型和数据类型实质上是一个概念,只是抽象数据类型的范围更广,除了已有的数据类型外,抽象数据类型还包括用户在设计软件系统时自己定义的数据类型.ADT的定义取决于它的一组逻辑特性,与其在计算机内的表示和实现无关.因此,不论ADT的内部结构如何变化,只要其数学特性不变,都不影响其外部的使用.抽象数据类型的最重要的特点是抽象和信息隐蔽.抽象的本质是抽取反映问题本质的东西,忽略非本质的细节,从而使所设计的数据结构更具有一般性,可以解决一类问题.信息隐蔽就是对用户隐蔽数据存储和操作实现的细节,使用者仅需了解抽象操作,或界面服务,通过界面中的服务来访问这些数据.一个含抽象数据类型的软件模块通常应包含定义、表示和实现三部分.3.数据元素之间的关系在计算机中有几种表示方法？各有什么特点？解：数据元素之间的关系在计算机中有四种不同的表示方法：顺序存储方法.数据元素顺序存放,每个结点只含有一个元素.存储位置反映数据元素间的逻辑关系.存储密度大,但有些操作效率较差.链式存储方法.每个结点除包含数据元素信息外还包含一组指针.指针反映数据元素间的逻辑关系.这种操作不要求存储空间连续,便于进行插入和删除等操作,但存储空间利用率较低.另外,由于逻辑上相邻的数据元素在存储空间上不一定相邻,所以不能对其进行随机存取.索引存储方法.除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表.索引表中的索引指示结点的存储位置,兼有动态和静态特性.哈希存储方法.通过哈希函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将哈希函数的值作为该数据元素的存储地址.其特点是存取速度快,只能按关键字随机存取,不能顺序存储,也不能折半存取.4.简述数据结构的三个层次、五个要素.解：数据结构的三个层次是指抽象、实现和评价三个层次,五个要素是指逻辑结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面.5.举一个数据结构的例子,说明其逻辑结构、存储结构与其运算三个方面的内容.并说明数据的逻辑结构、存储结构与其运算之间的关系.解：例如复数数据结构,其逻辑结构是复数的表示,而存储结构是指复数在计算机内的表示,运算是指对复数初始化、相加等操作.数据的逻辑结构反映数据元素之间的逻辑关系.数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示与其关系的表示.数据的运算是对数据定义的一组操作,运算是定义在逻辑结构上的,和存储结构无关,而运算的实现则依赖于存储结构.6.设为整数,试给出下列各程序段中标号为的语句的频度.1i=1;whilei i=i+2;2i=1;k=0;whilei k+=10*i; i+; 3i=1;k=0;whilei i+; k+=10*i; 4i=1;j=0;whilei+j ifjj+;else i+; 5x=n;y=0;/n是不小于1的常数while=* y+; 6x=91;y=100;while0 if100x-=10;y-;else x+; 解：1；2n-1；3n-1；4；5；61007.调用下列C函数,回答下列问题：1试指出值的大小,并写出值的推导过程.2假定=5,试指出值的大小和执行时的输出结果.int finti,j,k,sum=0;fori=1;ifori-1;j-fork=1;ksum+;printf; return ;解：第一层for循环判断n+1次,往下执行n次,第二层for执行次数为n+1,第三层循环体受第一层循环和第二层循环的控制,其执行次数如下表：i= 1 2 3 nj=n n n n nj=n-1 n-1 n-1 n-1 j=3 3 3 3 j=2 2 2j=1 1执行次数为+n=n*n/2-n/6.在n=5时,=55,执行过程中,输出结果为：sum=15,sum=29,sum=41,sum=50,sum=55.8.试写一算法,从小到大依次输出顺序读入的3个整数、和的值.解：void print_descending/按从大到小顺序输出三个数int temp;scanf; ifxtemp=x;x=y;y=temp; ifytemp=y;y=z;z=temp; ifxtemp=x;x=y;y=temp; printf;9.将下列各函数,按它们在时的无穷阶数,从小到大排序：,.解：从大到小排列为：,.10.已知阶裴波那契序列的定义为,=,+1,试编写求阶裴波那契序列的第项值的函数算法,和均以值调用的形式在函数参数表中出现.解：int fib/求k阶斐波那契序列的第m项的值fint tempMAX,i,j,sum; ifk2|m return 0;ifm f=0;else if f=1;elsefori=0;i tempi=0;tempk-1=1; /初始化fori=k;i/求出序列第k至第m个元素的值sum=0;forj=i-k;j sum+=tempj;tempi=sum;f=tempm; return 1;习题21.描述头指针、头结点、首元结点的区别,并说明头指针和头结点的作用.解：在线性表的链式存储结构中,头指针是指链表的指针,若链表有头结点则是链表的头结点的指针,头指针具有标识作用.故常用头指针冠以链表的名字.头结点是为了操作的统一、方便而设立的,放在第一个结点之前,其数据域一般无意义,有结点后,对在第一个元素结点前插入结点和删除第一个结点,其操作与对其他结点的操作统一了.而且无论链表是否为空,头指针均不为空.首元结点也就是第一个元素结点,它是头结点后面的第一个结点.2.在顺序表中插入和删除一个结点需平均移动多少个元素？具体的移动次数取决于哪两个因素？解：在顺序表中插入和删除一个结点需平均移动表中一半元素.具体的移动次数取决于表长和该元素在表中的位置两个因素.3.在单链表和双向链表中,是否从当前结点出发访问到任何一个结点？解：在单链表中不能从当前结点出发访问到任何一个结点,但在双向链表中可以从当前结点出发访问到任何一个结点.4.若较频繁地对一个线性表进行插入和删除操作,该线性表宜采用何种存储结构？为什么？解：采用链式存储结构,它根据实际需要申请内存空间,而当不需要时又可将不用的结点空间返还给系统.在链式存储结构中插入和删除操作不需要移动元素.5.有线性表,采用单链表存储,头指针为,每个结点中存放线性表中的一个元素,现查找某个元素值为的结点.分别写出下面三种情况的查找语句,要求时间尽量少.1线性表中元素无序.2线性表中元素按递增有序.3线性表中元素递减有序.解：设单链表带头结点,工作指针p初始化为p=H-next.1whiledata!=xp=p-next;ifreturn NULL;/查找失败else return p;/查找成功2whiledatap=p-next;ifdataxreturn NULL;/查找失败else return p;/查找成功3whiledataxp=p-next;ifdatareturn NULL;/查找失败else return p;/查找成功6.下面是一算法的核心部分,试说明该算法的功能.pre=L-next;/L是一带头结点的单链表,结点有数据域data和指针域nextifwhilenext!=NULLp=pre-next;ifdata=pre-data pre=p;else return;return;解：该算法的功能是判断链表L是否非递减有序,若是则返回TRUE,否则返回FALSE.pre指向当前结点,p指向pre的后继.7.设、分别指向两个带头结点的有序从小到大单链表.阅读下列程序,并回答问题：1程序的功能；2、2中的值的含义；3、中值的含义.void examp1=pa-next;p2=pb-next;pa-next=NULL;s1=0;s2=0;whileswitchcasedatadata:p=p1;p1=p1-next;s2+;delete p;casedatap2-data:p2=p2-next;casedata=p2-data:p=p1;p1=p1-next;p2-next=p2-next;pa-next=p;p2=p2-next;s1+;whilep=p1;p1=p1-next;delete p;s2+;解：本程序的功能是将pa和pb链表中值相同的结点保留在pa链表中pa中与pb中不同的结点删除,pa是结果链表的头指针.链表中结点值与从前逆序.s1记结果链表中结点个数即pa与pb中相等的元素个数,s2记原pa链表中删除的结点个数.8.假设长度大于1的循环单链表中,既无头结点也无头指针,为指向该链表中某一结点的指针,编写一算法删除该结点的前驱结点.解：int Delete_PreLNode *q,*temp;q=p;whilenext-next!=pq=q-next;temp=q-next;q-next=p;delete temp;return OK;9.已知两个单链表La和Lb分别表示两个集合,其元素递增排列.编写一算法求其交集Lc,要求Lc以元素递减的单链表形式存储.解：void Inter_setLNode *pa,*pb,*pc;pa=La-next; pb=Lb-next;Lc=new LNode;Lc-next=NULL;whileifdata=pb-datapc=new LNode; pc-data=pa-data;pc-next=Lc-next;Lc-next=pc;pa=pa-next;pb=pb-next;else ifdatadata pa=pa-next;else pb=pb-next;10.已知单链表是一个递增有序表,试写一高效算法,删除表中值大于min且小于max的结点若表中有这样的结点,同时释放被删除结点的空间,这里min和max是两个给定的参数.请分析你的算法的时间复杂度.解：void Delete_BetweenLNode *p,*q,*s;p=L;whilenext-datap=p-next;ifq=p-next;whiledatas=q;q=q-next;delete s;p-next=q;11.已知非空单链表的头指针为,试写一算法,交换所指结点与其下一个结点在链表中的位置设指向的不是链表最后那个结点.解：void ExchangeLNode *q,*pre;q=L-next; pre=L;whilepre=q;q=q-next;ifnext=NULLprintf;else q=p-next; pre-next=q;p-next=q-next;q-next=p;12.线性表中有n个元素,每个元素是一个字符,现存于数组Rn中,试写一算法,使R中元素的字符按字母字符、数字字符和其它字符的顺序排列.要求利用原来的空间,元素移动次数最小.解：void process int low,high;char k;low=0;high=n-1;whilelow/将字母放在前面whilelowhigh&fchlow+;whilelowhigh&!fchhigh-;iflowk=Rlow; Rlow=Rhigh;Rhigh=k;high=n-1;whilelow/将数字放在字母后面,其它字符前面whilelowhigh&!fnumlow+;whilelowhigh&fnumhigh-;iflowk=Rlow; Rlow=Rhigh;Rhigh=k;13.试编写在带头结点的单链表中删除一个最小值结点的高效算法.解：void Delete LNode *p,*q,*pre;p=L-next;pre=L;q=p;whilenext!=NULLifnext-datadatapre=p; q=p-next;p=p-next;pre-next=q-next;delete q; 14.已知两个单链表La和Lb,其元素递增排列.编写一算法,将La和Lb归并成一个单链表Lc,其元素递减排列允许表中有相同的元素,要求不另辟新的空间.解：void interactionLNode *pa,*pb,*s;pa=La-next; pb=Lb-next;La-next=NULL;delete Lb;whileifdatadatas=pa;pa=pa-next;s-next=La-next;La-next=s;else s=pb;pb=pb-next;s-next=La-next;La-next=s;whiles=pa;pa=pa-next;s-next=La-next;La-next=s;whiles=pb;pb=pb-next;s-next=La-next;La-next=s;15.设以带头结点的双向循环链表表示的线性表.试写一时间复杂度为的算法,将改造为.解：void OEReformDuLNode *p;p=L-next; whilenext!=L&p-next-next!=L p-next=p-next-next;p=p-next;ifnext=Lp-next=L-prior-prior;else p-next=L-prior;p=p-next;whileprior-prior!=Lp-next=p-prior-prior;p=p-next;p-next=L;fornext!=L; p=p-nextp-next-prior=p;L-prior=p;16.设有一双向循环链表,每个结点除有prior、data和next三个域外,还有一个访问频度域frep.在链表被起用之前,频度域frep的值为0,而每当对链表进行一次LocateElem的操作后,被访问的结点的频度域frep的值增1,同时调整链表中结点之间的顺序,使其按访问频度非递增的次序顺序排列,以便始终保持被频繁访问的结点总是靠近表头结点.试写出符合上述要求的LocateElem操作的算法.解：void LocateElemDuLNode *p=L-next,*q;whiledata!=x&pp=p-next;ifp-frep+;q=p-prior;whilefrepfrep&q!=L q=q-prior; ifpriorp-prior-next=p-next;p-next-prior=p-prior;q-next-prior=p;p-next=q-next;q-next=p;p-prior=q; 习题31.名词解释：栈、队列、循环队列.解：栈是只能在一端进行插入和删除操作的线性表,允许插入和删除的一端叫栈顶,另一端叫栈底.最后插入的元素最先删除,故栈也称后进先出表.队列是允许在一端插入而在另一端删除的线性表,允许插入的一端叫队尾,允许删除的一端叫队头.最后插入的元素最先删除,故栈也称先进先出表.最先入队的元素最先删除,故队列也称先进先出表.用常规意义下顺序存储结构的一维数组表示队列,由于队列的性质队尾插入,队头删除,容易造成假溢出现象,即队尾已达到一维数组的高下标,不能再插入,然而队中元素个数小于队列的长度.循环队列是解决假溢出的一种方法.通常把一维数组看成首尾相接.在循环队列下,通常采用牺牲一个存储空间的方法解决队满和队空的判定问题.2.如果输入序列为1,2,3,4,5,6,试问能否通过栈结构得到以下两个序列：4,3,5,6,1,2和1,3,5,4,2,6；请说明为什么不能或如何才能得到.解：输入序列为1,2,3,4,5,6,不能得到4,3,5,6,1,2,其理由是：输出序列最后两个元素是1,2,前面四个元素4,3,5,6得到后,栈中元素剩下1,2,且2在栈顶,栈底元素1不可能在栈顶元素2出栈之前出栈.得到序列1,3,5,4,2,6的过程是：1入栈并出栈；然后2和3依次入栈,3出栈,部分输出序列是1,3；紧接着4和5入栈,5,4和2依次出栈,此时输出序列为1,3,5,4,2；最后6入栈并出栈,得到最终结果序列是1,3,5,4,2,6.3.试证明：若借助栈由输入序列1,2,得到序列,则在输出序列中不可能出现下列情形：存在着,使得.解：如果的情况,则说明要将压到之上,也就是在出栈之后才能出栈.这说明,对于,不可能出现的输出序列.4.当函数递归调用自身时,函数内定义的局部变量在函数的2次调用期间是否占用同一数据区？为什么？解：函数递归调用自身时,函数内定义的局部变量在函数的2次调用期间不占用同一数据区.每次调用都保留其数据区,这是由递归定义所决定的,用递归工作栈来实现.5.简要叙述循环队列的数据结构,并写出其初始状态、队列空、队列满时的队头指针和队尾指针的值.解：循环队列的数据结构略.typedef structElemType *elem;int front;int rear;S ueue,Q;1初始状态:Q.front=Q.rear=0;2队列空:Q.front=Q.rear=0;3队列满:Q.front=%MAXSIZE;6.设一个双端队列,元素进入该队列的次序为1,2,3,4.求既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列.解：既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列是：4,2,3,1.7.简述以下算法的功能.void algo1int i,n,A255; n=0;while!StackEmptyn+;Pop;fori=1;iPush;void algo2 Stack T;int d;InitStack;while!StackEmptyPop;ifPush;while!StackEmptyPop;Push;void algo3/栈和队列的元素类型均为intStack S;int d;InitStack;while!QueueEmptyDeQueue;Push;while!StackEmptyPop;EnQueue;解：1将栈中元素逆置.2将栈中的0元素删除.3将队列中元素逆置.8.试写一个算法,识别依次读入的一个以为结束符的字符序列是否为形如序列1&序列2”模式的字符序列.其中,序列1和序列2中不含字符,且序列2是序列1的逆序列.解：int IsReverse/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0SqStack s;char c,x;InitStack;whilec=getchar!=&Push;whilec=getchar!=ifStackEmptyreturn 0;Pop;ifreturn 0;if!StackEmptyreturn 0;return 1;9.在火车调度站的入口处有节硬席或软席车厢等待调度,试写一算法,输出对这节车厢进行调度的操作序列,以使所有的软席车厢都被调整到硬席车厢之前.解：typedef char SSMAX; void Train_arrange/这里用字符串train表示火车,H表示硬席,S表示软席SqStack s;char *p,*q,c;p=train;q=train;InitStack;whileifPush;/把H存入栈中else *=*p; /把S调到前部p+;while!StackEmptyPop;*=c;/把H接在后部10.试写出求递归函数的递归算法,并消除递归：解：int F_recursive/递归算法ifn return ERROR;if s=n+1;elseF_recursive;s=n*s;return OK;/F_recursive typedef struct ElemType a;ElemType b;node;typedef struct node *data;int top;/栈顶指针int stacksize;SqStack;void F_nonrecursive/非递归算法SqStack T;node x,t;ifn exit;if s=n+1;else InitStack; whilex.a=n;x.b=n/2;Push;n=x.b;/whiles=1;while!StackEmptyPop;s*=t.a;/while/F_nonrecursive11.试将下列递归函数改为非递归函数.void testint x;scanf;ifsum=0;elsetest;sum+=x;printf;解：void testint x,sum=0,top=-1,s10;scanf;whiles+top=x; scanf;printf;while-1sum+=stop-; printf;12.设整数列,给出求解最大值的递归程序.解：int MaxValueint max;ifmax=a0;else ifMaxValuemax=an-1;else max=MaxValue;return max;13.假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点,试编写相应的队列初始化、入队和出队的算法.解：void InitQueuerear=new LNode;rear-next=rear; void EnQueue LNode *s;s=new LNode;s-data=x;s-next=rear-next;rear-next=s;rear=s;void DnQueueLNode *s;ifnext=rearprintf;exit;s=rear-next-next;/s指向队头元素rear-next-next=s-next;/队头元素出队x=s-data;ifrear=rear-next;/空队delete s;14.假设称正读和反读都相同的字符序列为回文,试写一个算法判别读入的一个亿为结束符的字符序列是否是回文.解：int Test/判别输入的字符串是否回文序列,是则返回1,否则返回0SqStack S;S ueue Q;char c;ElemType a,b;InitStack;InitQueue;whilec=getchar!=Push;EnQueue; /同时使用栈和队列两种结构while!StackEmptyPop;DeQueue;if return ERROR;return OK;15.写一算法,借助于栈将一个单链表逆序输出.解：void processLNode *p;SqStack s;ElemType x;p=L-next;InitStack;while Pushdata;p=p-next;while !StackEmptyPop;printf;16.假设循环队列中只设rear和length来分别指示队尾元素的位置和队中元素的个数,试给出此循环队列的队满条件,并写出相应的入队和出队算法,要求出队时需返回队头元素.解：typedef struct ElemType *base;/动态分配存储空间int length;/队列长度int rear;/尾指针,指向队列尾元素S ueue;int EnQueue/带length域的循环队列入队算法ifreturn ERROR;/队列满Q.rear=%MAX;Q.baseQ.rear=x;Q.length+;return OK;int DeQueue /带length域的循环队列出队算法int head;ifreturn ERROR;/队列空head=%MAX;x=Q.basehead;Q.length-;return OK;int InitQueue/构造一个空循环队列QQ.base=new ElemTypeMAX;ifexit;Q.rear=0;Q.length=0;return OK;习题41.名词解释：串、空串、空格串、子串.解：串是有限的字符序列,从数据结构角度讲,串属于线性结构.与线性表的不同之处在于串的元素是字符.空串是不含任何字符的串,其长度为0.空格是一个字符,其ASCII码值是32.空格串是由空格组成的串,其长度等于空格的个数.串中任意连续的若干字符组成的子序列称为该串的子串.2.已知三个字符串分别为,.利用串的基本运算得到结果串为,要求写出得到结果串所用的函数与执行算法.解：串可看作由以下两部分组成：和,设这两部分分别叫串s1和s2,要设法从、中得到这两部分,然后使用连接操作连接s1和s2得到.i=index;/s1=substr,i,length-i+1;/取出串s1j=index;/求串在串中的起始位置,串中后是s2=substr,j+3,length-j-2;/形成串s2=concat;3.已知字符串中存放一段英文,写出算法,将其按给定的长度格式化成两端对齐的字符串,其多余的字符存入.解：题目要求将字符串S1拆分成字符串S2和S3,要求字符串S2按给定长度n格式化为两端对齐的字符串,即长度为n且首尾字符不能为空格字符.算法从左到右扫描字符串S1,找到第一个非空格字符,计数到n,第n个拷入字符串S2的字符不能为空格,然后将余下字符复制到字符串S3中.void formatchar *p=S1,*q=S2;int i=0;whilep+;/滤掉S1左端空格ifprintf;exit;while*p!= 0&i*q=*p;q+;p+;i+;/字符串S1向字符串S2中复制ifprintf;exit;if*= /若最后一个字符为空格,则需要向后找到第一个非空格字符p-;/p指针也后退whilep+;/往后查找一个非空格字符作为串S2的尾字符ifprintf;exit;*q=*p;/字符串S2最后一个非空字符*= 0;/S2字符串结束标记q=S3;p+;/将S1串其余部分送字符串S3while*q=*p;q+;p+;*q= 0;/置串S3结束标记4.假设采用定长顺序存储结构表示串,编写算法,求串的含不同字符的总数和每个字符的个数.解：typedef struct char ch;int num;mytype;void StrAnalyze/统计串S中字符的种类和个数int i,j;char c;mytype T100; /用结构数组T存储统计结果fori=1;iTi-1.ch=0;fori=1;ic=Si;j=0;whilej+; /查找当前字符c是否已记录过if Tj.num+;else Tj.ch=c;Tj.num=1;/forforprintf;/StrAnalyze5.假设采用定长顺序存储结构表示串,编写算法,从串中删除所有和串相同的子串.解：void SubString_Delete/从串s中删除所有与t相同的子串,num为删除次数int i,j,k;fori=1;iforj=1;j;ift0/找到了与t匹配的子串fork=i;ksk=sk+t0; /左移删除s0-=t0;num+;/for/Delete_SubString6.编写算法,实现堆存储结构的串的置换操作Replace.解：void HString_Replace/堆结构串上的置换操作,返回置换次数int i,j,k,m;fori=0;iforj=i,k=0;k;if /找到了与T匹配的子串:分三种情况处理ifform=1;m S.chi+m-1=V.chm-1;/新子串长度与原子串相同时:直接替换else ifT.length /新子串长度大于原子串时:先将后部右移 for=i+T.length;m-S.chm+V.length-T.length=S.chm; form=0;mS.chi+m=V.chm;else /新子串长度小于原子串时:先将后部左移form=i+V.length;mS.chm=S.chm-V.length+T.length;form=0;mS.chi+m=V.chm;S.length+=V.length-T.length;i+=V.length;num+;/if/for/HString_Replace7.编写算法,实现堆存储结构的串基本操作Concat.解：void HString_Concat /将堆结构表示的串s1和s2连接为新串tint i,j;if free;t.ch=new chars1.length+s2.length;fori=1;i t.chi-1=s1.chi-1;forj=1;j t.chi-1=s2.chj-1;t.length=s1.length+s2.length;/HString_Concat8.假设以块链结构表示串,试编写判别给定字符串是否具有对称性的算法,并要求算法的时间复杂度为.解：int LString_Palindrome /判断以块链结构存储的串L是否为回文序列,是则返回1,否则返回0 InitStack; p=S.head;i=0;k=1; /i指示元素在块中的下标,k指示元素在整个序列中的序号 fork=1;k ifk Pushchi; /将前半段的字符入串 else if/2 Pop; /将后半段的字符与栈中的元素相匹配 ifchi!=c return 0; /失配 if /转到下一个元素,当为块中最后一个元素时,转到下一块 p=p-next; i=0; /for return 1; /成功匹配/LString_Palindrome9.令,试分别求出它们的next函数值和nextval函数值.解：j1234567串Sabcabaanextj0111232nextvalj0110132J1234567891011121314151617181920串Tabcaabbabcabaacbacbanextj01112231234532211211Nextvalj0110213011053221021010.已知主串,模式串,写出模式串的nextval函数值,并由此画出KMP算法匹配的全过程.解：j12345678910串Tadabbadadanextvalj0102101040匹配过程略.习题51.假设有7行5列的二维数组A下标从1开始,每个元素占用6个字节,存储器按字节编址.已知A的基地址为1000,计算：数组A共占用多少存储单元；数组A的最后一个元素的地址；按行存储时元素A53的地址；按列存储时元素A53的地址.解： 数组A所占存储单元个数m=7*5*6=210. 数组A最后一个元素的地址d=1000+5*7-1*6=1204. 按行存储时元素A53的地址d53=1000+4*5+2*6=1132. 按列存储时元素A53的地址d53=1000+4*7+2*6=11802.若矩阵中的某个元素是第i行的最小值,同时又是第j列中的最大值,则称此元素为该矩阵中的一个马鞍点.假设以二维数组存储矩阵,试编写求出矩阵中所有马鞍点的算法,并分析算法在最坏情况下的时间复杂度.解：算法思想：先找到一行的最小元素,然后扫描该元素所在的列,看他是否是该列的最大元素,若是则判为鞍点并输出,如此逐行进行处理直至完毕.void Get_Saddle/求矩阵A中的马鞍点 fori=0;i formin=Ai0,j=0;j ifAij min=Aij; /求一行中的最小值 forj=0;j if /判断这个最小值是否鞍点 forflag=1,k=0;k ifmin flag=0; ifprintf; /for/Get_Saddle 算法最坏情况下的时间复杂度为O.3.设有三对角矩阵,将其三条对角线上的元素存于数组B3n中,使得元素Buv=aij,试推导出从到的下标变换公式.解：假设数组B的下标从1开始则：u=i-j+2, v=j.假设数组B的下标从0开始则：u=i-j+1, v=j-1.4.假设稀疏矩阵A和B都以三元组顺序表作为存储结构.试写出矩阵相加的算法,另设三元组表存放结构矩阵.解：void TSMatrix_Add/三元组表示的稀疏矩阵加法 C.mu=A.mu;C.nu=A.nu;C.tu=0; pa=1;pb=1;pc=1; forx=1;x /对矩阵的每一行进行加法 whileA.datapa.i pa+; whileB.data