删除有序数组中重复元素.doc

数据结构（C+版）实验报告班 级1405 学 号 211415034姓 名徐妍题 目 单链表合并问题指导教师 王江涛计算机科学与技术学院2015年12月6日实验题目：将两个有序单链表合并1、 实验目的：1. 掌握单链表的建立（包括头插法和尾插法）2. 掌握栈的操作特性3. 掌握队列的操作特性2、 实验内容：将两个有序单链表合并如：单链表1：9，6，3，2，1； 单链表2：8，7，6，5，3，2，1，1，1； 合并成单链表3：9，8，7，6，5，3，2，13、 设计与编码1. 本实验用到的理论知识1 栈的特点：只能在表尾插入和删除；2 队列的特点：只能在一端插入，另一端删除；3 类模板的使用：存储“结点”的栈和队列；4 利用栈和队列的存储特点实现单链表的多次存储与排序2. 算法设计 关键算法与分析1 建立单链表（头插法）2 出栈3 入队列4 栈判空5 队列判空4、 运行与测试1) 出现的问题：单链表中还有重复结点的存在错误的运行结果：解决方法：添加一个删除单链表中重复结点的一个方法：void DeleteCF();/删除单链表中重复结点2) 正确的运行结果5、 总结与心得a. 这次的题目用到了栈和队列，跟别人的代码比起来似乎更加繁琐b. 而且在中间的时候还破坏了类的封装性（在调用类的first指针时）c. 还有很多想的不周到的地方，如上面刚刚出现的重复结点的问题；还有可以简化不需要用栈和队列来实现的问题（自己想复杂了），但是也算对栈和队列的复习与巩固了；d. 总体上来说还是不错的，首先想好做法，有想法，列好草稿，再开始下手写6、 附录（程序完整代码）SeqStack.h#ifndef SeqStack_H#define SeqStack_H const int StackSize=10;templateclass SeqStackprivate:T dataStackSize;int top;public:SeqStack()top=-1;void Push(T x);T Pop();T GetTop();bool Empty();#endifSeqStack.cpp#include#include SeqStack.htemplatevoid SeqStack:Push(T x)if(top=StackSize-1)throw栈满上 溢;top+;datatop=x;templateT SeqStack:Pop()T x;if(top=-1)throw栈空下溢;x=datatop;top-;return x;templateT SeqStack:GetTop()if(top!=-1)return datatop;templatebool SeqStack:Empty()if(top=-1)return 1;elsereturn 0;LinkQueue.h#ifndef LinkQueue_H#define LinkQueue_Hconst int QueueSize=100;template class LinkQueueprivate:T dataQueueSize;int rear,front;public:LinkQueue()front=rear=QueueSize-1;void EnQueue(T x);/入队操作T DeQueue();/出队操作T GetQueue();/取到队头元素bool Empty();int GetLength();#endifLinkQueue.cpp#include LinkQueue.htemplatevoid LinkQueue:EnQueue(T x)if(rear+1)%QueueSize=front)throw 队满上溢;elserear=(rear+1)%QueueSize;datarear=x;templateT LinkQueue:DeQueue()if(front=rear)throw队空下溢;elsefront=(front+1)%QueueSize;return datafront;templateT LinkQueue:GetQueue()if(rear=front)throw队空下溢;elseint i=(front+1)%QueueSize;return datai;templateint LinkQueue:GetLength() return (rear-front+QueueSize)%QueueSize;templatebool LinkQueue:Empty()if(rear=front)return 1;else return 0;LinkList.h#ifndef LinkList_H#define LinkList_Htemplate struct Node/结点Node里面有data数据和next指针构成DataType data;/data数据类型是DataTypeNode *next;/next是指向类型为DataType的data数据的指针;template class LinkList/单链表public:Node *first;/建立first头结点public:LinkList();/无参构造函数，创建一个只有头结点的空链表LinkList(DataType a,int n);/有参构造函数，建立一个有n个元素的单链表void PrintList();/按序号输出单链表的各个元素void DeleteCF();/删除单链表中重复结点;#endifLinkList.cpp#include#includeLinkList.htemplate LinkList:LinkList()/无参构造函数，创建一个只有头结点的空链表first=new Node;/生成头结点first-next=NULL;/头结点的指针域置空，即单链表为空/初始化一个空链表template LinkList:LinkList(DataType a,int n)/有参构造函数，建立一个有n个元素的单链表first=new Node;/生成头结点first-next=NULL;/头结点的指针域置空，即单链表为空/初始化一个空链表Node *s;/建立一个s头结点for(int i=0;in;i+)s=new Node;/生成头结点s-data=ai;/将用户所要插入的元素赋值给结点s，即为每个元素建立一个结点s-next=first-next;first-next=s;/将结点s插入到头结点之后template void LinkList:PrintList()/按序号输出单链表的各个元素Node *p;/建立一个p头结点p=first-next;/当p！=NULL的时候，单链表才算有元素，有首结点/只有首结点才算第一个结点while(p!=NULL)coutdatanext;coutendl;templatevoid LinkList:DeleteCF()Node *p,*q;p=first-next;while(p-next)if(p-data=p-next-data)q=p-next;p-next=q-next;delete q;elsep=p-next;主函数main.cpp#include#includeLinkList.cpp#includeLinkQueue.cpp#includeSeqStack.cppusing namespace std;void main()int a5=1,4,4,7,9;LinkList LL1(a,5);/建立单链表LL1cout第一个单链表LL1的输出endl;LL1.PrintList();/输出单链表LL1，输出为:9,7,4,1SeqStack Node * S1;/声明一个存储“结点”类型的栈Node *p1=LL1.first-next;/单链表的首结点while(p1!=NULL)/遍历单链表S1.Push(p1);/当结点不为空的时候，将该结点进栈S1p1=p1-next;/coutdata;/输出为：1/类似地，建立一个单链表LL2，并将其进栈S2int b6=2,3,7,8,14,15;LinkList LL2(b,6);cout第二个单链表LL2的输出endl;LL2.PrintList();/输出单链表LL2，输出为:15,14,8,7,3,2SeqStack Node * S2;Node *p2=LL2.first-next;while(p2!=NULL)S2.Push(p2);p2=p2-next;/coutdata;/输出为：2LinkQueueNode * Q;/声明一个存储结点的队列while(S1.Empty()!=1&S2.Empty()!=1)/当两个栈S1和S2均不为空时Node *a;/定义结点a,数据域为整形变量的结点Node *b;Node *p=S1.GetTop();/栈S1中数据域最小的结点pNode *q=S2.GetTop();/栈S2中数据域最小的结点qif(p-datadata)/若栈S1中p小于栈S2中的qa=S1.Pop();/栈S1中的p所指的那个结点出栈Q.EnQueue(a);/并进入存储结点的队列Qif(p-dataq-data)b=S2.Pop();Q.EnQueue(b);if(p-data=q-data)/相等的话a=S1.Pop();/就都出栈b=S2.Pop();Q.EnQueue(a);/任意选取其中一个进入存储结点的队列Qwhile(S1.Empty()!=1)/当栈S1不为空时Node *p3=S1.Pop();/将栈S1中所有结点都出栈Q.EnQueue(p3);/并存入存储结点的队列Qwhile(S2.Empty()!=1)/当栈S2不为空时Node *p4=S2.Pop();/将栈S2中所有结点都出栈Q.EnQueue(p4);/并存入存储结点的队列Qcout队列Q存储的是两个单链表LL1和LL2的结点endl;cout队列Q的长度为-Q.GetLength()endl;cout队列Q的首元素为-dataendl;/Q.PrintLinkQueue();没有作用/int z=Q.GetLength();int x100;/定义一个存储队列Q所有结点的数据域的数组int n=0;while(Q.Empty()!=1)/当队列Q不为空的时候Node *p5;p5=Q.DeQueue();/p5是队列Q的结点,从“头结点”一直遍历到“尾结点”xn=p5-data;/存储队列Q从“头结点”一直到“尾结点”的数据域n+;cout队列Q共有结点的个数 nendl;/此时xn是存储队列Q所有结点的数据域的数组，但是是从小到大排序的/下面是将数组xn从大到小排列的程序LinkList LL3(x,n);LL3.DeleteCF();/删除LL3中重复结点cout将两个有序单链表LL1和L