北邮数据结构实验报告实验一线性表

数据结构实验报告实验名称：实验一线性表——题目1学生姓名：申宇飞班级：信通3班班内序号：03学号：2012210064日期：2013年11月4日1.实验要求实验目的：熟练掌握线性表的基本操作，包括：创建、插入、删除、查找、输出、求长度、合并等运算，以及各类操作在顺序存储结构和链式存储结构上的实现。实验内容：根据线性表的抽象数据类型的定义，选择下面任一种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选一）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：1、构造：使用头插法、尾插法两种方法2、插入：要求建立的链表按照关键字从小到大有序3、删除4、查找5、获取链表长度6、销毁7、其他：可自行定义编写测试main()函数测试线性表的正确性。2.程序分析2.1存储结构链表的具体存储表示为：①用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）②链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址信息（称为指针）链表的结点结构┌──┬──┐│data│next│└──┴──┘data域--存放结点值的数据域next域--存放结点的直接后继的地址（位置）的指针域（链域）地址内存单元1000H头指针1020H1080H10C0Hfront…………2.2关键算法分析1、关键算法：1：头插法自然语言描述：a:在堆中建立新结点b:将a[i]写入到新结点的数据域c:修改新结点的指针域d:修改头结点的指针域。将新结点加入链表中伪代码描述a:NodeT*s=newNodeTb:s-data=a[i]c:s-next=front-next;d:front-next=s2：尾插法自然语言描述：a:在堆中建立新结点：b:将a[i]写入到新结点的数据域：a[3]1080H……a[1]10C0H……a[4]^……a[2]1000H……c:将新结点加入到链表中d:修改修改尾指针伪代码描述a:NodeT*s=newNodeTb:s-data=a[i]c:r-next=s;d:r=s3：析构/删除函数自然语言描述：a:新建立一个指针，指向头结点b:判断要释放的结点是否存在，c:暂时保存要释放的结点d:移动a中建立的指针e:释放要释放的指针伪代码描述a:NodeT*p=frontb:while(p)c:front=pd:p=p-nexte:deletefront4：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，直到p为空或者j等于1b1：p指向下一个结点b2：j加1c:若p为空，说明第i个元素不存在，抛出异常d:否则，说明p指向的元素就是所查找的元素，返回元素地址伪代码描述a:NodeT*p=front-next;j=1;b:while(p&&j!=1)b1:p=p-nextb2:j++c:if(!p)throw”error”d:returnp5：按位查找函数自然语言描述：a:初始化工作指针p和计数器j，p指向第一个结点，j=1b:循环以下操作，找到这个元素或者p指向最后一个结点b1：判断p指向的结点是不是要查找的值，如果是，返回j，否则p指向下一个结点，并且j的值加一c:如果找到最后一个结点还没有找到要查找的元素，返回查找失败信息伪代码描述a:NodeT*p=front-next;j=1;b:while(p)b1:if(p-next==x)returnjp=p-nextj++c:return“error”6：插入函数自然语言描述：a:在堆中建立新结点b:将要插入的结点的数据写入到新结点的数据域c:修改新结点的指针域d:修改前一个指针的指针域，使其指向新插入的结点的位置伪代码描述a:NodeT*s=newNodeT;b:s-data=p-datac:s-next=p-nextd:p-next=se:p-data=x7：删除函数自然语言描述：a:从第一个结点开始，查找要删除的位数i前一个位置i-1的结点b:设q指向第i个元素c:将q元素从链表中删除d:保存q元素的数据e:释放q元素伪代码描述a:q=p-nextb:p-next=q-nextc:x=q-datad:deleteq8：遍历打印函数自然语言描述：a:判断该链表是否为空链表，如果是，报错b:如果不是空链表，新建立一个temp指针c:将temp指针指向头结点d:打印temp指针的data域e:逐个往后移动temp指针，直到temp指针的指向的指针的next域为空伪代码描述Iffront-next==NULLThrow”anemptylist”NodeT*temp=front-next;while(temp-next){couttemp-data;temp=temp-next;}9：获取链表长度函数自然语言描述：a:判断该链表是否为空链表，如果是，输出长度0b:如果不是空链表，新建立一个temp指针，初始化整形数n为0c:将temp指针指向头结点d:判断temp指针指向的结点的next域是否为空，如果不是，n加一，否则returnne:使temp指针逐个后移，重复d操作，直到temp指针指向的结点的next域为0，返回n伪代码描述intn=0ifront-next==NULLn=0;else{NodeT*temp=front-next;while(temp-next)n++;temp=temp-next;}returnn;2、代码详细分析：（1）从第一个结点开始，查找节点，使它的数据比x大，设p指向该结点：while(xp-data){p=p-next;}（2）新建一个节点s，把p的数据赋给s：s-data=p-data;（3）把s加到p后面：s-next=p-next;p-next=s;（4）p节点的数据用x替换：p-data=x;示意图如图所示pxp-datas3、关键算法的时间复杂度：O（1)3.程序运行结果程序截图1.流程图：开始初始化一个对象2.测试条件：插入、删除元素的位置一定要在链表的长度范围之内。3.测试结论：可以正确的对链表进行插入，删除，取长度，输出操作。且插入任意一个元素后，链表的顺序依然是由小到大。4.总结1.调试时出现的问题及解决的方法：（1）刚开始时用NULL置空最后一个节点的指针域，发现调试时出现NULL未声明的情况。最后发现用0去置空最后一个节点的指针域，调试成功。（2）刚开始遍历总是不能完全遍历链表。最后发现循环语句中两个句子顺序写反，更正顺序后，调试成功。2.心得体会：这道题是相对比较基础，目的是实现线性表的基本功能，书上也几乎给出了所有的模板类的定义，但是在自己进行编程时还是出了很多问题。通过这个实例，我对模板类的定义与使用有了个初步的了解，了解了单链表的基本的操作和函数实现。以后必须自己动手编，实现理论与实践相结合，提高自己的编程能力。3.下一步的改进：这个程序的交互性不强，可以改进的地方应该是可以从外部输入数组而不仅仅是编程者给定。此外，显示的界面不够友好，有待改善，而且可以增加完善的报错机制。此外，也希望老师初始化一个整形数组，作为赋值准备分别利用头插法和尾插法初始化，并且用遍历打印函数来显示数值执行删除函数，之后遍历打印函数来测试是否真的删除执行插入函数，之后遍历打印函数来测试是否真的插入执行按位查找和按值查找函数结束能在课上给出更多的优化指导。代码#includeiostreamusingnamespacestd;templateclassTstructNode{Tdata;structNode*next;};templateclassTclassLinkList{public:LinkList()//无参构造{front=newNodeT;front-next=NULL;}LinkList(Ta[],intn);//头插法//LinkList(Ta[],intn);//尾插法voidPrintList();//按次序遍历intGetLength();//获取线性表的长度NodeT*Get(inti);//获取第i个位置上的元素结点的地址intLocate(Tx);//查找voidInsert(inti,Tx);//插入TDelete(inti);//删除~LinkList();//销毁private:NodeT*front;};templateclassTLinkListT::LinkList(Ta[],intn)//头插法{front=newNodeT;front-next=NULL;for(inti=n-1;i=0;i--){NodeT*s=newNodeT;//建立新结点s-data=a[i];//给新结点数据域赋值s-next=front-next;//修改新结点的指针域front-next=s;//修改头指针的指针域}}/*templateclassTLinkListT::LinkList(Ta[],intn)//尾插法{front=newNodeT;NodeT*r=front;for(inti=0;in;i++){NodeT*s=newNodeT;s-data=a[i];r-next=s;r=s;}r-next=NULL;}*/templateclassTvoidLinkListT::PrintList(){NodeT*p=front;-p=p-next;while(p-next!=NULL){p=p-next;coutp-dataendl;}}templateclassTintLinkListT::GetLength(){NodeT*p=front;intn=0;while(p-next!=NULL){p=p-next;n++;}returnn;}templateclassTNodeT*LinkListT::Get(inti){NodeT*p=front-next;intj=1;while(p&&j!=i){p=p-next;j++;}returnp;}templateclassTvoidLinkListT::Insert(inti,Tx){NodeT*p=front;if(i!=1)p=Get(i-1);if(p){NodeT*s=newNodeT;s-data=x;s-next=p-next;p-next=s;}elsethrow位置错误;}templateclassTTLinkListT::Delete(inti){NodeT*p=front;if(i!=1){p=Get(i-1);NodeT*s=p-next;Tx=s-data;p-next=s-next;returnx;deletes;}elsethrow位置错误;}templateclassTLinkListT::~LinkList(){NodeT*p=front;while(p){p=p-next;deletefront;front=p;}}intmain(){constintn=10;inta[n]={1,2,3,4,5,6,7,8,9,10};LinkListintlist(a,n);//list.hLinkList(a,n);//list.rLinkList(a,n);coutlist.GetLength()endl;coutendl;list.PrintList();coutendl;list.Insert(1,0);list.PrintList();coutlist.Get(