《合并单链表==数据结构实训报告》由会员分享，可在线阅读，更多相关《合并单链表==数据结构实训报告（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构数据结构实训报告实训报告院系院系_软件学院软件学院_ 专业专业 _软件工程软件工程_姓名姓名_朱勇朱勇_ 学号学号_2010118131_10_级级 _2_班班 _2013-5-24_ 1实训题目实训题目 假设两个元素值递增有序的单链表 La 和 Lb。编写算法实现将表 La 和 Lb 合并成一个元素值递减有序的单链表 Lc，并要求利用原表结点空间。2需求分析需求分析要求用 VC 编写一个演示程序，首先建立一个带头结点的整型单链表，然 后把第一个和最后一个互换位置。 （1） 初始化单链表功能 单链表头结点 next 域为 NULL （2） 建立单链表功能 使用尾插法建立单链表。 （3）
2、 便利单链表功能 输出单链表内的所有节点的值 （4） 合并单链表功能 把关于两个单链表合并为一个新的单链表3概要设计概要设计（1）为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：数据结构： typedef struct Nodeint elem; struct Node * next; Node,*LinkList;基本操作：InitLinkList(LinkList *L)操作前提：L 是一个未初始化的线性表操作结果：将 L 初始化为一个空的线性表CreateFromTail(LinkList *L)操作前提：L 是一个已初始化的空表操作结果：建立一个非空的线性表 LForeac
3、hLinkList(LinkList *L) 操作前提：线性表 L 已存在操作结果：输出线性表 L 的所有节点值LinkList* MergeLinkList(LinkList *LA, LinkList *LB)操作前提：线性表 LA，LB 已存在 操作结果：两个单链表合并为一个升序单链表（2） 本程序包含 6 个函数： 主函数 main() 初始化单链表函数 InitLinkList() 尾插法建立单链 CreateFromTail () 插入元素函数 ForeachLinkList () 合并单链表函数 LinkList* MergeLinkList( ()各函数间调用关系如下：main
4、初始化单链 表函数 InitLinkList() 尾插法建立 单链 CreateFromT ail () 插入元素函 数 ForeachLink List () 合并单链表函数 LinkList* MergeLinkList( ()采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪 码算法定义如下：4附录附录#include #includetypedef struct Node int elem; struct Node * next; Node,*LinkList;void InitLinkList(LinkList *L) *L = (Node*)malloc(sizeof(
5、Node); (*L)-next = NULL; /尾插法建单链表 void CreateFromTail(LinkList *L) int num; scanf(“%d“, Node *s, *r; r=(*L); while(num != -1) s=(Node*)malloc(sizeof(Node); s-elem = num; r-next = s; r = s; scanf(“%d“, r-next = NULL; void ForeachLinkList(LinkList *L) Node * temp = (*L)-next; while( temp!= NULL) print
6、f(“%d “,temp-elem); temp = temp-next; LinkList* MergeLinkList(LinkList *LA, LinkList *LB) Node *pa = (*LA)-next; Node *pb = (*LB)-next;/新建单链表 LC，并初始化 LinkList *LC = new LinkList(); InitLinkList(LC);Node *r = (*LC);/指向 LC 的下一个节点while(pa != NULL r = pa; pa = pa -next; else r-next = pb; r = pb; pb = pb
7、 -next; if(pa = NULL ) r-next = pb; else r-next = pa; free(LA); free(LB); return LC;/* 假设两个元素值递增有序的单链表 La 和 Lb。 编写算法实现将表 La 和 Lb 合并成一个元素值递减有序的单链表 Lc，并要求利 用原表结点空间。 */ int main() LinkList *LA = new LinkList(); InitLinkList(LA);printf(“升序单链表 LA:n“); CreateFromTail(LA); printf(“LA 链表内容“); ForeachLinkList(LA);LinkList *LB = new LinkList(); InitLinkList(LB); printf(“n 升序单链表 LB:n“); CreateFromTail(LB); printf(“LB 链表内容“); ForeachLinkList(LB); /合并LinkList *LC = MergeLinkList(LA,LB); printf(“nLC 链表内容“); ForeachLinkList(LC);
