合并单链表==数据结构实训报告.docVIP

《数据结构》实训报告 院系_____软件学院________ 专业 _____软件工程______ 姓名_____朱勇_______ 学号__2010118131____ ___10_____级 ___2____班 _2013-5-24___ 1．实训题目 假设两个元素值递增有序的单链表La和Lb。编写算法实现将表La和Lb合并成一个元素值递减有序的单链表Lc，并要求利用原表结点空间。 2．需求分析 要求用VC编写一个演示程序，首先建立一个带头结点的整型单链表，然后把第一个和最后一个互换位置。 初始化单链表功能 单链表头结点next域为NULL 建立单链表功能 使用尾插法建立单链表。 便利单链表功能 输出单链表内的所有节点的值 合并单链表功能 把关于两个单链表合并为一个新的单链表 3．概要设计 为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型： 数据结构： typedef struct Node{ int elem; struct Node * next; }Node,*LinkList; 基本操作： InitLinkList(LinkList *L) 操作前提：L是一个未初始化的线性表 操作结果：将L初始化为一个空的线性表 CreateFromTail(LinkList *L) 操作前提：L是一个已初始化的空表 操作结果：建立一个非空的线性表L ForeachLinkList(LinkList *L) 操作前提：线性表L已存在 操作结果：输出线性表L的所有节点值 LinkList* MergeLinkList(LinkList *LA, LinkList *LB) 操作前提：线性表LA，LB已存在 操作结果：两个单链表合并为一个升序单链表 本程序包含6个函数： 主函数main() 初始化单链表函数InitLinkList() 尾插法建立单链CreateFromTail () 插入元素函数ForeachLinkList () 合并单链表函数LinkList* MergeLinkList( () 各函数间调用关系如下： 采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义如下： 4．附录 #includestdio.h #includemalloc.h typedef struct Node{ int elem; struct Node * next; }Node,*LinkList; void InitLinkList(LinkList *L){ *L = (Node*)malloc(sizeof(Node)); (*L)-next = NULL; } //尾插法建单链表 void CreateFromTail(LinkList *L){ int num; scanf(%d,num); Node *s, *r; r=(*L); while(num != -1){ s=(Node*)malloc(sizeof(Node)); s-elem = num; r-next = s; r = s; scanf(%d,num); } r-next = NULL; } void ForeachLinkList(LinkList *L){ Node * temp = (*L)-next; while( temp!= NULL) { printf(%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 pb !=NULL) { if( pa-elem = pb-elem) { r-next = pa; r = pa; pa = pa -next; }else{ r-next = pb; r = pb; pb = pb -next; } } if(pa == NULL ) r-next = pb; else r-next = pa; fr