数据结构课程课后习题集答案解析

}

(6)有一个整数元素建立的单链表A,设计一个算法,将其拆分成两个单链表A和B,使得A单链表中含有所有的偶数结点,B单链表中所有的奇数结点,且保持原来的相对次序。

解:采用重新单链表的方法,由于要保持相对次序,所以采用尾插法建立新表A、B。用p遍历原单链表A的所有数据结点,若为偶数结点,将其链到A中,若为奇数结点,将其链到B中。对应的算法如下:

void Split(SLink *&A,SLink *&B) { }

SLink *p=A->next,*ra,*rb; ra=A;

B=(SLink *)malloc(sizeof(SLink)); //建立头结点 rb=B; { }

ra->next=rb->next=NULL;

//r总是指向B链表的尾结点

while (p!=NULL)

if (p->data%2==0) { } else { }

//奇数结点

//将*p结点链到B中

rb->next=p; rb=p; p=p->next; ra->next=p; ra=p; p=p->next;

//偶数结点

//将*p结点链到A中

本算法的时间复杂度为O(n),空间复杂度为O(1)。 (7)有一个有序单链表(从小到大排列),表头指针为L,设计一个算法向该单链表中插入一个元素为x的结点,使插入后该链表仍然有序。

解:先建立一个待插入的结点,然后依次与链表中的各结点的数据域比较大小,找到插入该结点的位置,最后插入该结点。对应的算法如下:

void inorderList(SLink *&L,ElemType x) {

SLink *s,*p,*q;

s=(SLink *)malloc(sizeof(SLink)); //建立一个待插入的结点 s->data=x;s->next=NULL; if (L==NULL || xdata) { } else {

q=L;

//寻找插入位置,p指向待比较的结点,q指向p的前驱结点

p=q->next; s->next=L; L=s;

//若单链表为空或x小于第1个结点date域 //把*s结点插入到头结点之后

数据结构简明教程

}

}

while (p!=NULL && x>p->data) //若x小于p所指结点的data域值

if (x>p->data) { }

//将s结点插入到*q和*p之间

q=p; p=p->next;

s->next=p; q->next=s;

(8)有一个单链表L,其中可能出现值域重复的结点,设计一个算法删除值域重复的结点。并分析算法的时间复杂度。

解:用p遍历单链表,用r遍历*p结点之后的结点,q始终指向*r结点的直接前驱结点,若r->data==p->data,则删除*r结点,否则q、r同步后移一个结点。对应的算法如下:

void dels1(SLink *&L) { }

SLink *p=L->next,*q,*r,*t; while (p!=NULL) { }

q=p; r=q->next; while (r!=NULL) { }

p=p->next;

if (r->data==p->data) //r指向被删结点 { } else { }

q=r; r=r->next; t=r->next; q->next=t; free(r); r=t;

本算法的时间复杂度为O(n2)。

(9)有一个递增有序单链表(允许出现值域重复的结点),设计一个算法删除值域重复的结点。并分析算法的时间复杂度。

解:由于是有序表,所以相同值域的结点都是相邻的。用p遍历递增单链表,若*p结点的值域等于其后结点的值域,则删除后者。对应的算法如下:

void dels(SLink *&L) {

SLink *p=L->next,*q; while (p->next!=NULL) {

if (p->data==p->next->data)

//找到重复值的结点

}

}

{ }

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结点不是尾结点 //先删除*p结点

//将*p结点插入到*q结点之后

return 0;

q=p->next; if (q!=NULL) { } else

//*p结点是尾结点

//无法与后继结点交换,返回0

return 0;

if (p==NULL) else

p->prior->next=q; q->prior=p->prior; p->next=q->next; if (q->next!=NULL)

q->next->prior=p;

q->next=p; p->prior=q; return 1;

(11)对于有n(n≥1)个数据结点的循环单链表L,设计一个算法将所有结点逆置。 解:采用头插法重建循环单链表L的思路,先建立一个空的循环单链表,用p遍历所有数据结点,每次将*p结点插入到前端。对应的算法如下:

void Reverse(SLink *&L) {

SLink *p=L->next,*q;

数据结构简明教程

}

L->next=L; while (p!=L) { }

q=p->next; p->next=L->next; L->next=p; p=q;

//将*p结点插入到前端

//建立一个空循环单链表

上机实验题2

有两个整数集合采用有序单链表存储,设计尽可能高效的算法求两个集合的并集、交集和差集。并用相关数据进行测试。

#include #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->datadata) { }

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;

//求并集

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4