2.2有序表的合并.doc

数 据 结 构 实 验 报 告实验题目：有序表的合并姓名： 张耀班级： 计嵌151学号： 1513052017一、 实验目的把两个有序表归并为一个有序表。二、 数据结构设计(1) 存储设计：采用带头结点的单链表存储数据。输入：数据通过键盘有序输入输出：屏幕显示两个有序表及归并后的表(2) 函数设计：CreateList(int n)；/ 创建具有n个元素的线性链表ListDisplay()；/输出表元素Combine(LinkList LA, LinkList LB);/归并单链表LA,LB(3) 两个有序表合并算法描述：Step1:初始化。1.1设置工作指针pa,pb,分别指向两个有序表LA,LB的首元结点。1.2生成新表LC的头结点，工作指针pc指向LC。Step2:只要pa和pb有所指，循环执行下列操作。2.1生成一新节点，链到LC表尾，pc指向它。2.2如果pa-datadata:pc-data=pa-data;pa后移。2.3否则：pc-data=pb-data;pb后移。Step3:如果pa空，把pb开始的结点依次复制到pc后。Step4: 如果pb空，把pa开始的结点依次复制到pc后。三、 算法设计与N-S图(1) 算法设计：求归并表的过程是在元素有序的情况下不断地从两表中取出元素，添加到新表中，所以元素采取表尾插入。设两个有序表SA，SB，归并后的有序表为SC，取元素的过程是：依次扫描SA，SB中的元素，比较当前元素的值，将较小的元素赋给SC，直到一个顺序有序表扫描完毕，然后将另一个顺序有序表中余下元素复制到SC中。(2) 程序流程图开始初始化：pa = LA.Head-next;pb = LB.Head-next;pc = Head;pc-data = pa-data;pa = pa-next;pc-data = pb-data;pb = pb-next;pa-datadata生成新节点，连接到LC表尾，pc指向它pa和pb都不为空把pb开始的结点依次复制到pc后面pa=NULLPb!=NULL把pa开始的结点依次复制到pc后面pb=NULLPa!=NULL结束四、 程序清单#includeusing namespace std;#includeprocess.hstruct Nodeint data;/数据域，存放表元素Node *next;/指针域，指向下一个结点;class LinkListprivate:Node *Head;/ 链表头指针public:LinkList();/构造函数， 创建空链表void CreateList(int n);/创建具有n个元素的线性链表void ListDisplay();/输出表元素void Combine(LinkList, LinkList);/合并;LinkList:LinkList()/构建函数，建一空链表Head = new Node;Head-next = NULL;void LinkList:CreateList(int n)/尾插法(正序)创建具有n个元素的线性表Node *p, *s;/设置工作指针。p指向尾结点p = Head;cout 请依次输入 n 个元素值： endl;for (int i = 1; i s-data;/输入新建数据元素值s-next = p-next;/新结点链入表尾p-next = s;p = s;void LinkList:ListDisplay()/遍历显示链表Node *p;/设置工作指针p = Head-next;/从首元结点开始遍历int i = 1;/元素位序while (p)cout data next;i+;cout next;pb = LB.Head-next;pc = Head;while (pa!= NULL&pb != NULL)Node*p =new Node;p-next= NULL;pc-next= p;pc = p;if (pa-data data)pc-data = pa-data;pa = pa-next;elsepc-data = pb-data;pb = pb-next;if (pa = NULL)while (pb != NULL)Node*p1 = new Node;p1-next = NULL;pc-next = p1;pc = p1;pc-data = pb-data;pb = pb-next;else if (pb = NULL)while (pa != NULL)Node*p2 = new Node;p2-next = NULL;pc-next = p2;pc = p2;pc-data = pa-data;pa = pa-next;void main()LinkList SA, SB, SC;int la_len, lb_len;cout la_len;cout endl;SA.CreateList(la_len);cout lb_len;cout endl;SB.CreateList(lb_len);cout SA: endl;SA.ListDisplay();cout endl;cout SB: endl;SB.ListDisplay();cout endl;SC.Combine(SA, SB);cout SC: endl;SC.ListDisplay();cout endl;五、 运行与测试1、测试数据如下：SASBSC11,22,33,441,13,17,391,11,13,17,22,33,39,44111,13,17,391,11,13,17,3911,22,33,4411,11,22,33,4411,22,33,44Void11,22,33,44Void1,13,17,391,13,17,39VoidVoidVoid551,13,17,391,13,17,39,552、运行结果如下： 六、 实验分析及体会分析：本次实验，输入两个有序表实现了两个有序表的合并