线性表的链式表示和实现

数学与计算科学学院实验报告实验项目名称线性表的链式表示和实现所属课程名称数据结构实验类型验证型实验日期2013.10.31班级信计1201学号201253100109姓名成绩1一、实验概述：【实验目的】1、了解线性表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素外，每个元素总存在唯一一个直接前驱元素；除最后一个元素外，每个元素总有唯一一个直接后继元素。2、掌握单链表的基本操作在链式存储结构上的实现【实验原理】1、线性链表特点：是一种动态分配存储结构，每一个结点的指示域指向其直接后继结点（尾结点除外）；指针为数据元素之间的逻辑关系的映像。2、线性表的单链表存储结构：typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;【实验环境】VC++6.0二、实验内容：【实验方案】编写主函数，调用线性链表的初始化建空表、查找、插入和删除算法，调制运行，得出结果。【实验过程】（实验步骤、记录、数据、分析）1、输入线性链表的初始化建空表、查找、插入、删除算法以及主函数：//线性表的单链表存储结构typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。2………………}//CreateList_LStatusGetElem_L(LinkListL,inti,ElemType&e){//L为带头结点的单链表的头指针。//当第i个元素存在时，其值赋给e并返回OK,否则返回ERROR………………}//GetElem_LStatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的单链线性表L中第i个位置之前插入元素e………………}//ListInsert_LStatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值………………}//ListDelete_Lvoidmain(){………………}2、保存并开始调试，①出现如下错误：errorC2065:'i':undeclaredidentifiererrorC2065:'p':undeclaredidentifier即‘i’,’p’未定义，因i是整型，p是链表，故需在前面先进行定义：inti;LinkListp;②在scanf(&p-data);//输入元素值中出现错误：errorC2664:'scanf':cannotconvertparameter1from'int*'to'constchar*'.不能将参数1从'int*'到'constchar*'，因p-data表示的是一个数，故需说明输入的是一个十进制数，应修改为：scanf(“%d”,&p-data)；③在StatusListInsert_L(LinkList&L,inti,ElemTypee){int;p=L;j=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK;}//ListInsert_L中也出现错误：errorC2065:'p':undeclaredidentifier；errorC2440:'=':cannotconvertfrom'structLNode*'to'int'；3errorC2065:'s':undeclaredidentifier；主要是由于在该编码中p,s表示的是链表，但没给它们进行定义，不能直接把链表赋给它们，因此需在前面对它们进行定义：LinkListp,s;3、把错误修正过来后，运行：输入一个数5，表示链表空间数，回车，再输入任意五个数字如：12345，回车，得到：54321，完成了链表的建立，并把链表倒转过来；输入数字3，表示查找链表中的第三个元素，回车得出结果，完成链表查找算法；输入245，表示在链表第二个元素前插入45，回车得结果，完成链表插入算法；再输入4，表示删除链表第四个元素，回车得结果，完成链表的删除算法；最终完成链表的初始化建空表、查找、插入和删除的算法。【实验结论】（结果）【实验小结】（收获体会）在这次上机实验中，在进行调制时，自己慢慢调试，渐渐地了解了那些错误什么意思，如何修改，最终完成了线性表的链式表示和实现，对线性链表的初始化建空表、查找、插入、和删除算法有了进一步了解。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.4成绩：指导教师签名：批阅日期：附录1：源程序#includestdio.h#includestdlib.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;typedefstructLNode{ElemTypedata;structLNode*next;5}LNode,*LinkList;voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链线性表L。inti;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_LStatusListInsert_L(LinkList&L,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;//插入L中p-next=s;returnOK;}//ListInsert_LStatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值6LinkListp,q;intj;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(){LinkListL;LinkListp;intn,i;scanf(%d,&n);CreateList_L(L,n);for(p=L-next;p!=NULL;p=p-next)printf(%d,p-data);printf(\n);ElemTypee;scanf(%d,&i);GetElem_L(L,i,e);printf(e=%d\n,e);scanf(%d%d,&i,&e);ListInsert_L(L,i,e);for(p=L-next;p;p=p-next)printf(%d,p-data);printf(\n);scanf(%d,&i);ListDelete_L(L,i,e);for(p=L-next;p;p=p-next)printf(%d,p-data);printf(\n);}附录2：实验报告填写说明71．实验项目名称：要求与实验教学大纲一致。2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。3．实验原理：简要说明本实验项目所涉及的理论知识。4．实验环境：实验用的软、硬件环境。5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。概括整个实验过程。对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。对于创新性实验，还应注明其创新点、特色。6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。7．实验结论（结果）：根据实验过程中得到的结果，做出结论。8．实验小结：本次实验心得体会、思考和建议。9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。