数据结构第三章.doc

二、简述栈和线性表的区别。答：线性结构的特点是在数据元素的非空有限集中，存在惟一的一个被称为“第一个”的数据元素；存在惟一的一个被称做“最后一个”的数据元素；除第一个之外，集合中的每个数据元素均只有一个前驱；除最后一个之外，集合中每个数据元素均只有一个后继。线性表是最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以访问，还可在在任意位置进行插入和删除操作等。栈是一种特殊的线性结构，从数据的逻辑结构角度来看，栈是线性表，从操作的角度来看，栈的基本操作是线性表操作的子集，是操作受限制的线性表，其特点是栈限定仅在表尾进行插入和删除操作的线性表，它的存取特征是后进先出。三、写出下列程序段的输出结果（栈的元素类型Selem Type为char）。Void main( )stack s ; Char x,y; Initstack(s);x =c;y=k;Push(s,x);push(s,a);push(s,y);Pop(s,x);push(s,t);push(s,x);Pop(s,x);push(s,s);While(!stackempty(s) pop(s,y);printf(y);Printf(x);输出结果：stack四、简述以下算法的功能（栈的元素类型Selem Type为int）。1、status algol(stack s) Int I,n,A255; n=0; while(!stackempty(s) n+;pop(s,An); for(i=1;inext找到头结点，再通过头结点找到队头，即rear-next-next。图3-7 带头结点的循环链表队列【算法】 置空队LinkList SetNull()LinkList rear; rear=new LNode; rear-next=rear;return rear; 判队空int Empty(LinkList rear)if (rear-next=rear)return 1;/若队列为空返回1 elsereturn 0; /否则返回0 入队LinkList ENQUEUE(LinkList rear,DataType x)LinkList p;p=new LinkList;p-data=x;p-next=rear-next; /将p插入到rear-next之后rear-next=p;rear=p;return rear; /返回新的队尾指针 出队LinkList DEQUEUE(LinkList raer,DataType *x) LNode *p,*q;if (rear-next=rear) /若队空，则输出队空信息 coutnext;p=q-next;/否则q指向头结点，p指向队头 if (p=rear)rear=q; /若队中仅有一个元素，则将rear指向头结点 q-next=p-next; /将p所指结点出队 *x=p-data; delete p; /将对头结点的值赋给形参*x return rear; /返回队尾指针二十九、如果希望循环队列中的元素都能得到利用，则需设置一个标志域tag，并以tag的值为0或1来区分，尾指针和头指针值相同时的队列状态是“空”还是“满”。试编写与此结构相应的入队列和出队列的算法。解：Status EnCyQueue(CyQueue &Q,int x)/带tag域的循环队列入队算法if(Q.front=Q.rear&Q.tag=1) /tag域的值为0表示空,1表示满return OVERFLOW;Q.baseQ.rear=x;Q.rear=(Q.rear+1)%MAXSIZE;if(Q.front=Q.rear) Q.tag=1; /队列满/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x)/带tag域的循环队列出队算法if(Q.front=Q.rear&Q.tag=0) return INFEASIBLE;Q.front=(Q.front+1)%MAXSIZE;x=Q.baseQ.front;if(Q.front=Q.rear) Q.tag=1; /队列空return OK;/DeCyQueue三十、假设循环队列中只设rear和length 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。解：根据题意，可定义该循环队列的存储结构：#define QueueSize 100typedef char Datatype ; /设元素的类型为char型typedef struct int length;int rear;Datatype DataQueueSize;CirQueue;CirQueue *Q;循环队列的队满条件是：Q- length =QueueSize知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：(1)判断队满int FullQueue( CirQueue *Q)/判队满,队中元素个数等于空间大小return Q- length =QueueSize;(2)入队void EnQueue( CirQueue *Q, Datatype x)/ 入队if(FullQueue( Q)Error(队已满，无法入队);Q-DataQ-rear=x;Q-rear=(Q-rear+1)%QueueSize;/在循环意义上的加1Q- length +;(3)出队Datatype DeQueue( CirQueue *Q)/出队if(Q- length =0)Error(队已空，无元素可出队);int tmpfront; /设一个临时队头指针tmpfront=(QueueSize+Q-rear - Q-quelen+1)%QueueSize;/计算头指针位置Q- length -;return Q-Datatmpfront;三十一、回文是指正读和反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。试写一个算法判定给定的字符向量是否为回文。解：#include stdio.h#define stacksize 100typedef char datatype;typedef struct datatype datastacksize; int top;seqstack;stacknull(seqstack *p)p-top=-1;Int stackfull(seqstack *p) return p-top=stacksize-1;tackempty(seqstack *p) if(p-top=-1) return 1; else return 0;push(seqstack *p,datatype x) if(stackfull(p) printf(it is wrong.);exit(0); p-top+; p-datap-top=x;pop(seqstack *p)if(stackempty(p) printf(error);exit(0);return(p-datap-top-);main() char temp; int n,i,length=0; seqstack l; stacknull(&l); clrscr(); printf(the top is %d,l.top); printf(ninput char:); printf(ninput n:); scanf(%dn,&n); for(i=0;in;i+) scanf(%c,&l.datai); length+; printf(n); length=length-1; printf(nthe length is %d,length); for(i=0;i(length/2);i+) push(&l,l.datai); if(length%2=0) for(i;ilength;i+) if(temp=pop(&l)!=l.datai) printf(nit is error.);exit(0); printf(nit is true.);else for(i;ilength-1;i+) if(temp=pop(&l)!=l.datai+1) printf(nit is error.);exit(0); printf(nit is true.); 补充题：一、 设将整数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,4312二、 链栈中为何不设置头结点?答： 链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。三、 循环队列的优点是什么? 如何判别它的空和满?答：循环队列的优点是：它可以克服顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。四、设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢?答：当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。五、 指出下述程序段的功能是什么?(1) void Demo1(SeqStack *S)int i; arr64 ; n=0 ;while ( StackEmpty(S) arrn+=Pop(S);for (i=0, i n; i+) Push(S, arri); /Demo1(2) SeqStack S1, S2, tmp;DataType x;./假设栈tmp和S2已做过初始化while ( ! StackEmpty (&S1)x=Pop(&S1) ;Push(&tmp,x);while ( ! StackEmpty (&tmp) )x=Pop( &tmp);Push( &S1,x);Push( &S2, x);(3) void Demo2( SeqStack *S, int m) / 设DataType 为int 型SeqStack T; int i;InitStack (&T);while (! StackEmpty( S)if( i=Pop(S) !=m) Push( &T,i);while (! StackEmpty( &T)i=Pop(&T); Push(S,i);(4)void Demo3( CirQueue *Q) / 设DataType 为int 型int x; SeqStack S;InitStack( &S);while (! QueueEmpty( Q )x=DeQueue( Q); Push( &S,x);while (! StackEmpty( &s) x=Pop(&S); EnQueue( Q,x );/ Demo3(5) CirQueue Q1, Q2; / 设DataType 为int 型int x, i , n= 0;. / 设Q1已有内容， Q2已初始化过while ( ! QueueEmpty( &Q1) ) x=DeQueue( &Q1 ) ; EnQueue(&Q2, x); n+;for (i=0; i n; i+) x=DeQueue(&Q2) ;EnQueue( &Q1, x) ;