实验2-不带头结点的单链表

上海电力学院数据结构实验报告（2014/2015学年第2学期）课程编号250504704课程名称数据结构院（系）专业班级学号姓名实验名称实验2不带头结点的单链表任课老师卢芳芳注：实验报告内容包括：实验目的与要求、实验原理与内容、实验步骤与记录、实验分析与结论等。2实验2不带头结点的单链表1【实验目的与要求】1、熟练掌握动态链表结构及有关算法的设计方法。2、理解不带表头结点的单链表的特点，掌握其基本操作。3、熟练掌握运用不带头结点链表表示特定形式的数据的方法，并设计出有关算法。2【实验内容和步骤】已知不带头结点的链表结构定义及头插法建表、尾插法建表和打印链表等函数定义如下（详见slnklist.h文件），基于该文件完成实验题1-实验4.#includestdio.h#includestdlib.h/**************************************//*链表实现的头文件，文件名slnklist.h*//**************************************/typedefintdatatype;typedefstructlink_node{datatypeinfo;structlink_node*next;}node;typedefnode*linklist;/**********************************//*函数名称：creatbystack()*//*函数功能：头插法建立单链表*//**********************************/linklistcreatbystack(){linklisthead,s;datatypex;head=NULL;printf(请输入若干整数序列:\n);scanf(%d,&x);while(x!=0)/*以0结束输入*/{s=(linklist)malloc(sizeof(node));/*生成待插入结点*/s-info=x;s-next=head;/*将新结点插入到链表最前面*/head=s;scanf(%d,&x);}returnhead;/*返回建立的单链表*/}/**********************************//*函数名称：creatbyqueue()*//*函数功能：尾插法建立单链表*//**********************************/linklistcreatbyqueue(){linklisthead,r,s;datatypex;head=r=NULL;printf(请输入若干整数序列:\n);scanf(%d,&x);while(x!=0)/*以0结束输入*/{s=(linklist)malloc(sizeof(node));注：实验报告内容包括：实验目的与要求、实验原理与内容、实验步骤与记录、实验分析与结论等。3s-info=x;if(head==NULL)/*将新结点插入到链表最后面*/head=s;elser-next=s;r=s;scanf(%d,&x);}if(r)r-next=NULL;returnhead;/*返回建立的单链表*/}/**********************************//*函数名称：print()*//*函数功能：输出不带头结点的单链表*//**********************************/voidprint(linklisthead){linklistp;inti=0;p=head;printf(Listis:\n);while(p){printf(%5d,p-info);p=p-next;i++;if(i%10==0)printf(\n);}printf(\n);}/**********************************//*函数名称：delList()*//*函数功能：释放不带头结点的单链表*//**********************************/voiddelList(linklisthead){linklistp=head;while(p){head=p-next;free(p);p=head;}}1.编写函数lnklistdelx(linklisthead,datatypex)，删除不带头结点单链表head中第一个值为x的结点。并构造测试用例进行测试。程序源代码（注意添加注释）运行结果（直接截取结果图）2.线性表（a1,a2,a3,…,an）采用不带头结点的单链表存储，请设计算法函数linklistreverse1(linklisthead)和voidreverse2(linklist*head)将不带头结点的单链表head倒置，使表变成（an,an-1,an-2,…,a2,a1）.。并构造测试用例注：实验报告内容包括：实验目的与要求、实验原理与内容、实验步骤与记录、实验分析与结论等。4进行测试。程序源代码（注意添加注释）运行结果（直接截取结果图）3.假设不带头结点的单链表head是升序排列的，设计算法函数linklistinsert(linklisthead,datatypex)，将值为x的结点插入到链表head中，并保持链表有序性。分别构造插入到表头、表中和表尾三种情况的测试用例进行测试。程序源代码（注意添加注释）运行结果（直接截取结果图）4.编写函数lnklistdelallx(linklisthead,datatypex)，删除不带头结点单链表head中所有值为x的结点。并构造测试用例进行测试。程序源代码（注意添加注释）运行结果（直接截取结果图）3【实验遇到的问题及解决方法】注：实验报告内容包括：实验目的与要求、实验原理与内容、实验步骤与记录、实验分析与结论等。54【实验结论与体会】1、结合上课内容，写出程序，并调试程序，要给出测试数据和实验结果。2、添加适当注释，注意书写的层次结构。3、整理上机步骤，总结经验和体会。4、上交实验报告