p->next=q;//将*p结点的直接后继指针指向*q结点 } 关闭
2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同 解：
本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
具体算法：
void DeleteList ( LinkList L ) {
ListNode *p , *q , *s; p=L-next;
while( p->next&&p->next->next) {
q=p;//由于要做删除操作，所以q指针指向要删除元素的直接前趋
while (q->next)
if (p->data==q->next->data)
{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点
}
else q=q->next; p=p->next; } } 关闭
2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。 解：
已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。 算法如下：
void DeleteNode( ListNode *s)
{//删除单循环链表中指定结点的直接前趋结点 ListNode *p, *q; p=s;
while( p->next->next!=s) p=p->next; //删除结点
q=p->next;
p->next=q->next; free(p); //释放空间 } 注意：
若单循环链表的长度等于1，则只要把表删空即可。 关闭
2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。 解：
要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。 算法如下：
//设已建立三个带头结点的空循环链表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->data<='z'|| p->data>='A' &&p->data<='Z') {
q=p->next;
p=p->next;//指向下一结点
q->next=A->next;//将字母结点链到A表中 A->next=q;A=q; }
else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next;
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; }
} }//结束
关闭
2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。 解：
LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q后就可以了。 算法如下：
//双向链表的存储结构
typedef struct dlistnode{ DataType 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的结点 else { p->freq++;//freq加1
q=p->prior;//以q为扫描指针寻找第一个频度大于或等于*p频度的结点
while(q!=L&&q->freq
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; } } }
第三章 栈和队列
3.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,4312 关闭
3.2 链栈中为何不设置头结点? 答：
链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。 关闭
3.3 循环队列的优点是什么? 如何判别它的空和满? 答：
循环队列的优点是：它可以克服顺序队列的\假上溢\现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的\空\或\满\不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。 关闭
3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间
为何? 若只设尾指针呢? 答：
当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。 关闭
3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ;
while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr); } //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 ))