}
else p=p->next; }
5．设计一个带头结点的单链表L中删除一个最小值结点的算法。 Status DelMin(LinkList &L) { if(L->next) return ERROR;
minpre=ppre=L; minp=p=L->next; while(p)
{if(p->data
minpre->next=minp->next; free(minp); }
6．已知3个单链表A、B、C中的结点均依元素值自小至大非递减排列（可能存在两个以上值相同的结点），设计一个算法使链表A中仅留下3个表中均包含的数据元素的结点，且没有值相同的结点，并释放所有无用结点。限定算法的时间复杂度为O（m+n+p），其中m、n、和p分别为3个表的长度。
7．两个整数序列A=（a1，a2，…，am）和B=（b1，b2，…，bn）用两个单链表存储，设计一个算法，判断序列B是否是序列A的子序列。 Status SubList(LinkList A,LinkList B) { pa=A->next; while(pa) { pb=B->next;
while(pa&&pa->data!=pb->data) pa=pa->next; //找到第一个元素相同的结点 ta=pa;
while(ta&&pb&&ta->data==pb->data) { ta=ta->next; pb=pb->next;} if(!pb) return TRUE; if(pa) pa=pa->next;
}
return FALSE; }
8．假设表达式中允许包含3种括号：圆括号、方括号、大括号。设计一个算法采用顺序栈判断表达式中的括号是否正确配对。
9．设以整数序列1，2，3，4作为顺序栈st的输入，利用push（进栈）和pop（出栈）操作，写出所有可能的输出并编程实现算法。
void p(SqStack &S,int k,int *out,int i)//从k开始的可能的出栈序列放到out[i]中 { int x;
if(k<=n) //第一种情况：如果站外有车,那么车k入站. { Push(S,k); p(S,k+1,out,i);
Pop(S,x); //恢复为原来的状态,即把车k恢复在站外的位置(回溯) }
if(!StackEmpty(S)) //第二种情况：如果站内有车,车m出站; { Pop(S,x); out[i++]=x;
if(i>=n&&StackEmpty(S)) //判断如果已经全部出站,那么我们可以打印了. print(out,i); p(S,k,out,i);
Push(S,x); i--; //恢复站内的状态，即把车m退回到站内;(这里也是回溯) } }
10．设计一个算法，利用栈的InitStack（）、Push（）、Pop（）和StackEmpty( )等基本运算返回指定栈中栈底元素。 Status GetBase(Stack S, SElemType &e) { InitStack(T);
while(!StackEmpty (S)) {Pop(S,e); Push(T,e);} while(!StackEmpty (T)) {Pop(T,e); Push(S,e);} return OK; }
11．假设I和O分别表示入栈和出栈操作，栈的初态和终态均为空，入栈和出栈
的操作序列可表示为仅由I和O组成的序列。 （1）下面所示的序列中那些是合法的？ A．IOIIOIOO B．IOOIOIIO C．IIIOIOIO D．IIIOOIOO
（2）通过对（1）的分析，写出一个算法判定所给的操作序列是否合法。若合法返回1，否则返回0（假设被判定的操作序列已存入一维数组中） Status Panduan(char *t) { InitStack(S); while(*t)
{switch(*t)
{case ‘I’: Push(S,*t); break;
case ‘O’:if(!StackEmpty (S)) { Pop(S,e); break;} else return 0;
} t++; }
if(!EmptyStack(T)) return 1; return 0; }
12．设计一个算法，利用队列的基本运算返回指定队列中的队尾元素。 Status GeTail(Queue Q, QElemType &e) { InitQueue(T);
while(!QueueEmpty (Q))
{DeQueue(Q,e); EnQueue(T,e);} while(!QueueEmpty (T))
{DeQueue(T,e); EnQueue(Q,e);} return OK; }
13．设计一个环形队列，用front和rear分别作为队头和队尾指针，另外用一个
标志tag表示队列是空（0）还是不空（1），这样就可以用front=rear作为队满的条件，要求设计队列的相关基本运算方法
#define MAXQSIZE 100 ∥最大队列长度 typedef struct
{QElemType *base; ∥初始化的动态分配存储空间
int front; ∥头指针,若队列不空,指向队列头元素
int rear; ∥尾指针,若队列不空,指向队列尾元素的下一个位置 int tag; //队列是否满的标识 }SqQueue;
Statue InitQueue(SqQueue &Q) {∥ 构造一个空队列Q
Q.base = (QElemType *)malloc(MAXQSIZE *
sizeof(QElemType)); if (!Q.base) exit(OVERFLOW); ∥存储分配失败 Q.front = Q.rear = 0;
Q.tag=0; //不满 return OK;
}
Status EnQueue(SqQueue &Q,QElemType e) {∥ 插入元素e为Q的新的队尾元素
if(Q.tag==1) return ERROR; Q.base[Q.rear] = e;
Q.rear = (Q.rear+1)% MAXQSIZE; if(Q.rear == Q.front) Q.tag=1; return OK; }
Status DeQueue(SqQueue &Q, QElemType &e) {∥ 删除队头元素，送给变量e
if(Q.tag==0) return ERROR; ∥队列空 e=Q.base[Q.front];
Q.front = (Q.front+1)% MAXQSIZE; if(Q.front= =Q.rear) Q.tag=0; return OK; }
∥队列满
