}
}
{ }
else p=p->next;
q=p->next; free(q);
练习题及参考答案 //q指向这个重复值的结点 //删除*q结点
p->next=q->next;
本算法的时间复杂度为O(n)。
（10）有一个双链表L，设计一个算法查找第一个元素值为x的结点，将其与后继结点进行交换。
解：先找到第一个元素值为x的结点*p，q指向其后继结点，本题是将*p结点移到*q结点之后，实现过程是：删除*p结点，再将其插入到*q结点之后。对应的算法如下：
int swap(DLink *L,ElemType x) { DLink *p=L->next,*q; }
while (p!=NULL && p->data!=x) { }
p=p->next;
//未找到值为x的结点 //找到值为x的结点*p //q指向*p的后继结点 //*p结点不是尾结点
return 0;
q=p->next; if (q!=NULL) { } else
//*p结点是尾结点
//无法与后继结点交换，返回0
return 0;
if (p==NULL) else
p->prior->next=q; //先删除*p结点 q->prior=p->prior; p->next=q->next; if (q->next!=NULL)
q->next->prior=p; q->next=p; p->prior=q; return 1;
//将*p结点插入到*q结点之后
（11）对于有n（n≥1）个数据结点的循环单链表L，设计一个算法将所有结点逆置。 解：采用头插法重建循环单链表L的思路，先建立一个空的循环单链表，用p遍历所有数据结点，每次将*p结点插入到前端。对应的算法如下：
void Reverse(SLink *&L) { SLink *p=L->next,*q;
11
数据结构简明教程
}
L->next=L; while (p!=L) { }
q=p->next; p->next=L->next; L->next=p; p=q;
//将*p结点插入到前端
//建立一个空循环单链表
上机实验题2
有两个整数集合采用有序单链表存储，设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。
#include
void Union(SLink *L1,SLink *L2,SLink *&L3) {
SLink *p,*q,*s,*tc;
L3=(SLink *)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next;
while (p!=NULL && q!=NULL) {
if (p->data
else if (p->data>q->data) { } else {
s=(SLink *)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s;
s=(SLink *)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next;
s=(SLink *)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next;
//求并集
}
}
while (p!=NULL) { }
while (q!=NULL) { }
tc->next=NULL;
s=(SLink *)malloc(sizeof(SLink)); s->data=q->data; tc->next=s; tc=s; q=q->next;
s=(SLink *)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; }
p=p->next; q=q->next;
练习题及参考答案 void InterSection(SLink *L1,SLink *L2,SLink *&L3) { }
void Subs(SLink *L1,SLink *L2,SLink *&L3)
SLink *p,*q,*s,*tc;
L3=(SLink *)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next;
while (p!=NULL && q!=NULL) { }
tc->next=NULL;
if (p->data
p=p->next; q=q->next;
//p->data=q->data
s=(SLink *)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next; q=q->next;
else if (p->data>q->data) else
//求交集
//求差集
13
数据结构简明教程
{ }
void main() {
SLink *A,*B,*C,*D,*E;
ElemType a[]={1,3,6,8,10,20}; CreateListR(A,a,6);
//尾插法建表
printf(\集合A:\ElemType b[]={2,5,6,10,16,20,30}; CreateListR(B,b,7);
//尾插法建表
printf(\集合B:\printf(\求A、B并集C\\n\Union(A,B,C);
//求A、B并集C
printf(\集合C:\printf(\求A、B交集C\\n\InterSection(A,B,D);
//求A、B并集D
printf(\集合D:\SLink *p,*q,*s,*tc;
L3=(SLink *)malloc(sizeof(SLink)); tc=L3; p=L1->next; q=L2->next;
while (p!=NULL && q!=NULL) { }
while (p!=NULL) { }
tc->next=NULL;
s=(SLink *)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next;
if (p->data
else if (p->data>q->data) { }
q=q->next;
//p->data=q->data p=p->next; q=q->next; else
s=(SLink *)malloc(sizeof(SLink)); s->data=p->data; tc->next=s; tc=s; p=p->next;
}
printf(\求A、B差集E\\n\Subs(A,B,E);
练习题及参考答案 //求A、B差集E
printf(\集合E:\DestroyList(A); DestroyList(B); DestroyList(C); DestroyList(D); DestroyList(E);
练习题3
1. 单项选择题
（1）栈中元素的进出原则是（ ）。 A.先进先出 B.后进先出 C.栈空则进 D.栈满则出 答：B
（2）设一个栈的进栈序列是A、B、C、D（即元素A～D依次通过该栈），则借助该栈所得到的输出序列不可能是（ ）。
A.A,B,C,D B.D,C,B,A C.A,C,D,B D.D,A,B,C
答：D
（3）一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（ ）。 A.edcba B.decba C.dceab D.abcde 答：C
（4）已知一个栈的进栈序列是1，2，3，?，n，其输出序列的第一个元素是i（1≤i≤n）则第j（1≤j≤n）个出栈元素是（ ）。
A.i B.n-i C.j-i+1 D.不确定 答：D
（5）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈空的条件为（ ）。
A.st.top==-1 B.st.top!=-1 C.st.top!=MaxSize D.st.top==MaxSize 答：A
（6）设顺序栈st的栈顶指针top的初始时为-1，栈空间大小为MaxSize，则判定st栈为栈满的条件是 。
A.st.top!=-1 B.st.top==-1 C.st.top!=MaxSize-1 D.st.top==MaxSize-1 答：D
（7）队列中元素的进出原则是（ ）。 A.先进先出 B.后进先出 C.栈空则进 D.栈满则出
15