线性表的链式表示和实现(含源程序)

数学与计算科学学院实验报告实验项目名称线性表的链式表示和实现所属课程名称数据结构实验类型验证型实验日期2013年10月31日班级学号姓名成绩1一、实验概述：【实验目的】1.线性表的逻辑结构特征1.1总存在第一个和最后一个元素；1.2除第一个元素以外，每个元素总存在唯一一个直接前驱元素；1.3除最后一个元素以外，每个元素总存在唯一一个直接后继元素。2.掌握单链表的基本操作在链式存储结构上的实现。【实验原理】1.线性链表的特点1.1线性链表是一种动态分配的存储结构；1.2每一个结点的指针域指向其直接后继结点（伪结点除外）；1.3指针为数据元素之间的逻辑关系的映像。2.线性表的单链表存储结构TypedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;【实验环境】VC++6.0二、实验内容：【实验方案】编写主函数，调用线性链表的初始化建空表，查找、插入和删除算法，调试运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）一．典型错误举例及改正措施例2错误分析：过于大意，直接将上一次算法之前的定义之类的内C语言复制过来，导致将线性表的单链表存储结构输成线性表的动态分配顺序存储结构。然后就出来上述LinkList未定义，L未定义，还有掉分号，掉括号之类的各种错误。二．完善主函数及过程错误分析3以上输出窗口这种形式的输出容易使人输完一步，然后忘记下一步该干嘛，于是这时候完善一下主函数，使得输出窗口每一步操作之前都加上提示语会更好。以下是完善主函数的过程：1.在主函数每一项输入之前加上一串汉字提示下一步的操作，于是主函数部分变为然后调试，发现报出如下错误：4（后面还有好多行，这里只列举一部分）错误分析：printf后面括号中的引号应为因为格式，这里却输成中文格式了，故报出以上错误。错误改正之后，调试：0错误，0警告。运行结果：2.观察上述运行结果发现，输出窗口还是不够完善，这里只有提示下一步的操作，但是没有显示操作之后输出的一串数字具体是什么。于是在主函数中继续加相应格式的汉字提示，得到：然后调试：0错误，0警告。运行结果：5至此，主函数完善完毕。三．测试数据1.前面几次运行，单链表的数字都比较简单且连续，于是换些比较复杂一点的数字测试，结果：观察输出窗口，发现该组数据测试无误。2．当实际输入的元素个数小于理论上应该输入的个数n时，就按了Enter键，第三行不会显示任何数据，但是有一个闪动光标暗示我们还需继续输入，当输入个数刚好等于n时，按Enter键，还是一样会逆序位输出原来的单链线性表L。但是当实际输入元素个数大于n时，会自动逆序位输出前n个元素，除了查找元素会报错，其他都按前n个元素输入正常运行。3.当输入的链表中的元素不是数字而是字母时会报错：6【实验结论】（结果）【实验小结】（收获体会）通过此次上机实验，除了对程序中主函数的编写及程序的完善有了很大的突破之外，还熟悉并实践了单链线性表的逆序位输出、查找、插入和删除算法。由于吸取上次教训，此次敲算法时格外小心注意，因此这次一些语句语法错误之类的错误就没有了，但是对程序的完善过程却有了很大感悟，一个好的程序不仅只是要把结果运行出来，而且要让人们在操作时更加便捷。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理73.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1：源程序#includestdio.h#includestdlib.h#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidCreateList_L(LinkList&L,intn){//逆序位输入n个元素的值，建立带表头结点的单链线性表L。8inti;LinkListp;L=(LinkList)malloc(sizeof(LNode));L-next=NULL;//先建立一个带表头结点的单链表for(i=n;i0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点scanf(%d,&p-data);p-next=L-next;L-next=p;}}//CreateList_LStatusGetElem_L(LinkListL,inti,ElemType&e){//L为带表头结点的单链表的头指针。//当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORintj;LinkListp;p=L-next;j=1;//初始化，p指向第一个结点，j为计数器while(p&&ji){//顺指针向后查找，直到p指向第i个元素或p为空p=p-next;++j;}if(!p||ji)returnERROR;//第i个元素不存在e=p-data;//取第i个元素returnOK;}//GetElem_L9StatusListInsert_L(LinkListL,inti,ElemTypee){//在带头结点的单链线性表L中第i个位置之前插入元素eLinkListp,s;intj;p=L;j=0;while(p&&ji-1){p=p-next;++j;}//寻找第i-1个结点if(!p||ji-1)returnERROR;//i小于1或者大于表长加1s=(LinkList)malloc(sizeof(LNode));//生成新结点s-data=e;s-next=p-next;p-next=s;returnOK;}//ListInsert_LStatusListDelete_L(LinkList&L,inti,ElemType&e){//在带表头结点的单链线性表L中，删除第i个元素，并由e返回其值intj;LinkListp,q;p=L;j=0;while(p-next&&ji-1){//寻找第i个结点并令p指向其前驱p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;//删除并释放结点e=q-data;free(q);returnOK;}//ListDelete_Lvoidmain()10{LinkListL,q;intn,i;printf(请输入您要创建的单链线性表L中的元素个数：);scanf(%d,&n);CreateList_L(L,n);//创建一个单链线性表Lprintf(您创建的单链线性表L为：);for(q=L-next;q!=NULL;q=q-next)printf(%d,q-data);printf(\n);ElemTypee;//定义函数参数为ElemType类型printf(请输入您需要查找元素的位置i：);scanf(%d,&i);GetElem_L(L,i,e);//查找单链线性表L中第i个位置上的元素，并用e返回其值printf(您查找的元素为：);printf(e=%d\n,e);printf(请输入您需要插入的元素的位置i及相应的元素值e：);scanf(%d%d,&i,&e);ListInsert_L(L,i,e);//在单链线性表L中第i个位置之前插入新的数据元素eprintf(插入后的单链线性表L为：);for(q=L-next;q!=NULL;q=q-next)printf(%d,q-data);printf(\n);printf(请输入您需要删除的元素的位置i：);11scanf(%d,&i);ListDelete_L(L,i,e);//删除单链线性表L中第i位置上的数据元素printf(删除第i个位置上的元素e后的单链线性表L为：);for(q=L-next;q!=NULL;q=q-next)printf(%d,q-data);printf(\n);}附录2：实验报告填写说明1．实验项目名称：要求与实验教学大纲一致。2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理：简要说明本实验项目所涉及的理论知识。4．实验环境：实验用的软、硬件环境。5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7．实验结论（结果）：根据实验过程中得到的结果，做出结论。8．实验小结：本次实验心得体会、思考和建议。9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。