江苏大学-数据结构实验报告-实验一

上机实验报告课程名称：数据结构A实验题目：单链表操作专业班级：计算机科学与技术1601学号：3160409053姓名：蒋权完成日期：2017.10.11成绩：一.实验内容、目的和要求1.实验内容单链表的创建、合并和输出。2.实验目的(1).熟悉用VisualC++进行程序设计的方法。(2).掌握单链表的创建、查找、插入和合并等运算。3.实验要求本实验要求实现以下功能：(1).从键盘输入顺序任意的5个整数，按有序插入的要求生成第一个有序单链表，将该链表输出显示。(2).再从键盘输入顺序任意的5个整数，按有序插入的要求生成第二个有序单链表，将该链表输出显示。(3).将这两个有序单链表合并成一个有序单链表，要求使用两个单链表的原有空间进行合并，将生成的有序单链表输出显示。【测试数据】输入第一组整数：2345117834输出的有序单链表应为：1123344578输入第二组整数：9013456610输出的有序单链表应为：1013456690合并两个单链表，输出合并后的结果应为：10111323344545667890二.程序中使用的数据结构及符号说明结点类（classNode）date——数据域*next——指针域Node(void)——无参构造函数单链表类（classLinkList）*first——头指针LinkList(void)——建立附加头节点的构造函数~LinkList(void)——析构函数voidSort()——数据排序voidInput()——输入voidOutput()——输出Node*Getfirst()——返回头结点voidfun(LinkList&d)——合并三.程序的主要流程图开始输入第一组整数排序排序输出输出合并并排序输出结束输入第一组整数四.程序主要模块的功能说明date——数据域*next——指针域Node(void)——无参构造函数LinkList(void)——建立附加头节点的构造函数~LinkList(void)——析构函数voidSort()——数据排序voidInput()——输入数据voidOutput()——输出数据Node*Getfirst()——返回头结点voidfun(LinkList&d)——合并链表五.程序运行时的初值和运行结果初值(调用并执行a.Input())输入第一组整数：2345117834预期——(先调用并执行voidSort()为输入的第一组数据排序后，再调用并执行Output()输出排序后的数)输出的有序单链表应为：1123344578初值——(调用并执行b.Input())输入第二组整数：9013456610预期(先调用并执行voidSort()为输入的第一组数据排序后，再调用并执行Output()输出排序后的数)输出的有序单链表应为：1013456690预期——（调用并执行voidfun(LinkList&d)将前面两组数合并并排序后，再调用并执行Output()将数输出）合并两个单链表，输出合并后的结果应为：10111323344545667890最后，经调试运行后最后输出结果如下图所示六.收获及体会七.源程序【这部分要求所列出来的源程序的代码的字号大小为“小五”，行距为“固定值”12磅，字体为TimesNewRoman】“Node.h”#pragmaonce#includeiostreamusingnamespacestd;classNode{public:intdate;Node*next;Node(void);};Node::Node(void){next=NULL;}“LinkList.h”#pragmaonce#includeNode.hclassLinkList{public:LinkList(void);//构造函数~LinkList(void);//析构函数voidSort();//排序voidInput();//输入voidOutput();//输出Node*Getfirst();//返回头结点voidfun(LinkList&d);//合并private:Node*first;};LinkList::LinkList(void)//建立附加头节点{Node*p=newNode;first=p;}LinkList::~LinkList(void){}voidLinkList::Input()//输入函数{cout请输入个整数endl;Node*p=Getfirst();for(inti=1;i=5;i++){p-next=newNode;p=p-next;cinp-date;coutendl;}Sort();}voidLinkList::Output()//输出函数{Node*p=Getfirst()-next;inti(0);while(p!=NULL){if(i%5==0)coutendl;i++;cout''p-date'';p=p-next;}coutendlendlendl;}voidLinkList::Sort()//排序{Node*p1=Getfirst()-next;Node*p2=p1-next;ints(0);Node*p=p1;for(inti=1;i=4;i++){p=p1;p2=p1-next;for(intj=1;j=5-i;j++){if(p-datep2-date)p=p2;p2=p2-next;}s=p1-date;p1-date=p-date;p-date=s;p1=p1-next;}}Node*LinkList::Getfirst(){returnfirst;}voidLinkList::fun(LinkList&d)//合并{Node*p1=Getfirst()-next;Node*p2=d.Getfirst()-next;Node*p,*pre_p;pre_p=Getfirst();while(p2!=NULL){if((p1==NULL)||(p2-date)=(p1-date)){p=newNode;p-date=p2-date;p-next=p1;pre_p-next=p;pre_p=p;p2=p2-next;}else{p1=p1-next;pre_p=pre_p-next;}}}“main.cpp”#includeiostream#includeNode.h#includeLinkList.husingnamespacestd;voidmain(){LinkLista,b;a.Input();a.Output();b.Input();b.Output();a.fun(b);a.Output();}