算法与数据结构习题答案.doc

算法与数据结构习题答案3.3 在顺序表中插入和删除一个结点需平均移动多少个结点?具体的移动次数取决于哪两个因素?答：在等概率情况下，顺序表中插入一个结点需平均移动n/2个结点。删除一个结点需平均移动(n-1)/2个结点。具体的移动次数取决于顺序表的长度n以及需插入或删除的位置i。i越接近n则所需移动的结点数越少。3.12 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。解：要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。算法如下：/设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针.void DivideList( LinkList L, LinkList A, LinkList B, LinkList C)ListNode *p=L-next, *q;while ( p )if ( p-data=a &p-datadata=A &p-datanext; p=p-next;/指向下一结点q-next=A-next;/将字母结点链到A表中A-next=q;A=q;else if( p-data=0 & p-datanext; p=p-next;/指向下一结点q-next=B-next;/将数字结点链到B表中B-next=q;B=q;else /分出其他字符结点q=p-next; p=p-next;/指向下一结点q-next=C-next;/将其他结点链到C表中C-next=q;C=q;/结束3.13 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 解：LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q后就可以了。算法如下：/双向链表的存储结构typedef struct dlistnodeDataType data;struct dlistnode *prior,*next;int freq;DListNode;typedef DListNode *DLinkList;void LocateNode( LinkList L, DataType x)ListNode *p, *q;p=L-next; /带有头结点while( p&p-data!=x )p=p-next;if (!p) ERROR(x is not in L);/双链表中无值为x的结点else p-freq+;/freq加1 q=p-prior;/以q为扫描指针寻找第一个频度大于或等于*p频度的结点while(q!=L&q-freqfreq)q=q-prior;if (q-next!=p)/若* q结点和*p结点不为直接前趋直接后继关系， /则将*p结点链到* q结点后p-prior-next=p-next;/将*p从原来位置摘下p-next-prior=p-prior;q-next-prior=p;/将*p插入*q之后。p-next=q-next;q-next=p;p-prior=q;4.1 设将整数 1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题：(1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?(2) 能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。 答：(1)出栈序列为：1324 (2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：1423,2413,3124,3142,3412,4123,4132,4213,4231,43124.3 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间。每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。4.5 回文是指正读反读均相同的字符序列，如abba和abdba均是回文，但good不是回文。试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)解：根据提示，算法可设计为：/ishuiwen.h 存为头文件int IsHuiwen( char *S)SeqStack T;int i , l;char t;InitStack( &T);l=strlen(S); /求向量长度for ( i=0; iPush( &T, Si);while( !EmptyStack( &T)/ 每弹出一个字符与相应字符比较t=Pop (&T);if( t!=Sl-i) return 0 ;/ 不等则返回0i-;return -1 ; / 比较完毕均相等则返回 -1/ 以下程序用于验证上面的算法/以下是栈定义( 存为stack.h)/出错控制函数#include#includevoid Error(char * message)fprintf(stderr, Error: %sn,message);exit(1);/ 定义栈类型#define StackSize 100typedef char Datatype;typedef structDatatype dataStackSize;int Top; SeqStack;void InitStack( SeqStack *S)/初始化(置空栈)S-Top=-1;int EmptyStack(SeqStack *S) /判栈空return S-Top = -1;int FullStack (SeqStack *S) / 判栈满return S-Top=StackSize-1;void Push (SeqStack *S , Datatype x) /进栈if(FullStack(S)Error(Stack overflow);S-data+S-Top=x;Datatype Pop(SeqStack *S) / 出栈(退栈)if (EmptyStack( S) )Error( Stack underflow);return S-dataS-Top-;/取栈顶元素(略)/-/以下是主程序#include#include#include stack.h#include ishuiwen.hvoid main( )char Str100=;printf(输入一个字符串:n);scanf(%s,Str);if( IsHuiwen(Str)printf( n这个字符串是回文。);else printf(n这个字符串不是回文。);4.6(类似题) 利用栈的基本操作， 写一个返回S中结点个数的算法 int StackSize( SeqStack S),并说明S为何不作为指针参数?解：算法如下：int StackSize (SeqStack S)/计算栈中结点个数int n=0;if(!EmptyStack(&S)Pop(&S);n+;return n;类似于上面的原因，我们要计算栈中元素个数就要弹出元素才能数得出来，那如果用指针做参数的话，就会把原来的栈中元素弹光，要恢复还得用别的办法给它装回去，而不用指针做参数，则可以避免对原来的栈中元素进行任何操作，系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数就可以了。4.8 一个双向栈S是在同一向量空间内实现的两个栈，它们的栈底分别设在向量空间的两端。 试为此双向栈设计初始化InitStack ( S ) 、入栈Push( S , i , x) 和出栈Pop( S , i )等算法， 其中i为0 或1， 用以表示栈号。解：双向栈其实和单向栈原理相同，只是在一个向量空间内，好比是两个头对头的栈放在一起，中间的空间可以充分利用。双向栈的算法设计如下：/双向栈的栈结构类型与以前定义略有不同#define StackSize 100 / 假定分配了100个元素的向量空间#define char Datatypetypedef structDatatype DataStackSizeint top0; /需设两个指针int top1;DblStackvoid InitStack( DblStack *S ) /初始化双向栈S-top0 = -1;S-top1 = StackSize; /这里的top2也指出了向量空间，但由于是作为栈底，因此不会出错4.10 对于循环向量中的循环队列，写出求队列长度的公式。解：公式如下：Queuelen= 0 当EmptyQueueQueuelen= rear - front当rearfrontQueuelen= rear+QueueSize-front当rearQueuelen= QueueSize 当FullQueue4.11 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：知道了尾指针和元素个数，当然就能知道队头元素了。算法如下：int FullQueue( CirQueue *Q)/判队满,队中元素个数等于空间大小return Q-quelen=QueueSize;void EnQueue( CirQueue *Q, Datatype x)/ 入队if(FullQueue( Q)Error(队已满，无法入队);Q-DataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize;/在循环意义上的加1Q-quelen+;Datatype DeQueue( CirQueue *Q)/出队if(Q-quelen=0)Error(队已空，无元素可出队);int tmpfront; /设一个临时队头指针if(Q-rear Q-quelen)/计算头指针位置tmpfront=Q-rear - Q-quelen;elsetmpfront=Q-rear + QueueSize - Q-quelen;quelen-;return Q-Datatmpfront;5.1 暂缺。5.4 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节?A的终端结点a47的起始地位为何?