专升本数据结构试题解析(6)

时间:2025-07-10

数据结构上机实验与习题解析 亱店↘打烊oO

r=q;

q=q->next;

free(r);

}

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

}/*else*/

}/*while*/

}/*Delete_Equal */

7.试设计一个算法,对带头结点的单链表实现就地逆置。

【算法分析】

1)空表或长度为1的表,不做任何处理;

2)表长大于2时,做如下处理:

①首先将整个链表一分为二,即从链表的第一元素结点处断开;

②逐个地把剩余链表的当前元素q插入到链表的头部。

【算法源代码】

void LinkList_reverse(LinkList L)

{ if(!L->next||!L->next->next) return;

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

p->next=NULL; /*从链表的第一元素结点处断开*/

while(s->next)

{q->next=p;p=q;

q=s;s=s->next; /*把L的元素逐个插入新表表头*/

}

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

}/*LinkList_reverse*/

8.设线性表A=(a1,a2,…,am) 和 B=(b1,b2,…,bn),试设计一个按下列规则合并A,B为线性表C的算法,即使得

C=(a1,b1,…,am,bm,bm+1 ,…,bn )当 m≤n时;

或者

C=(a1,b1,…,an,bn,an+1 ,…,am )当m>n时。

线性表A,B和C均以单链表作存储结构,且C表利用A表和B表中的结点空间构成。注意:单链表的长度值m和n均未显式存储。

【算法分析】

1)初始化指针p指向链表A的当前元素,指针q指向链表B的当前元素;

2)当链表A和B均为结束时,做如下处理:

①将B的元素插入

②若A非空,将A的元素插入

③指针p和q同时后移

【算法源代码】

void merge1(LinkList A,LinkList B,LinkList *C)

{p=A->next;q=B->next;*C=A;

while(p&&q)

{ s=p->next;p->next=q; /*将B的元素插入*/

if(s)

{ t=q->next;

q->next=s; /*若A非空,将A的元素插入*/

}

p=s;q=t; /*指针p和q同时后移*/

}/*while*/

}/*merge1 */

9.假设有两个按元素值递增有序排列的线性表A和B,均以单链表作存储结构,请设计一个算法将A表和B表归并成一个按元素值递减有序(即非递增有序,允许表中含有值相同的元素)排列的线性表C,并要求利用原表(即 A表和B表)的结点空间构造C表。

【算法分析】按从小到大的顺序依次把A和B的元素插入新表的头部pc处,最后处理A或B的剩余

专升本数据结构试题解析(6).doc 将本文的Word文档下载到电脑

精彩图片

热门精选

大家正在看

× 游客快捷下载通道(下载后可以自由复制和排版)

限时特价:7 元/份 原价:20元

支付方式:

开通VIP包月会员 特价:29元/月

注:下载文档有可能“只有目录或者内容不全”等情况,请下载之前注意辨别,如果您已付费且无法下载或内容有问题,请联系我们协助你处理。
微信:fanwen365 QQ:370150219