中国石油大学数据结构上机实验2

《数据结构》实验报告学号2015011512姓名胡明禹专业数学与应用数学时间2018.3.20一、实验题目实验2单链表基本操作二、实验目的1.熟练掌握线性表的顺序存储方式下，基本操作的实现算法，巩固和体会单链表操作特点；2.理解体会动态内存申请与释放；3.通过本次实验，熟练掌握C语言指针的使用三、算法设计分析（一）实验内容1.创建一个空的带头结点的单链表2.采用头插法在单链表中插入n个元素3.删除单链表中第i个元素4．实现单链表按关键字查找操作5.计算单链表的表长并输出单链表6.销毁单链表（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。例如：1.构造一个空的单链表的函数；2.插入函数；3.删除函数4.查找函数；5.计算并输出函数；6.销毁函数。其功能描述如下：（1）主函数：统筹调用各个函数以实现相应功能voidmain()（2）①构造一个空的单链表的函数StatusInitList_L(LinkList&L){L=(LinkList)malloc(sizeof(LNode));//构造一个空的线性表Lf(!L)exit(OVERFLOW);//存储分配失败L-next=NULL;//空表长度为0system(cls);//清空屏幕printf(\n\n初始化成功\n\n\n);system(PAUSE);//按任意键继续returnOK;}voidCreateList_L(LinkList&L){//创建一个新表inti,count;LinkListp;system(cls);//清屏printf(\n输入总结点数:);scanf(%d,&count);printf(\n输入各个结点数值，每输一个按下回车：\n);for(i=count;i0;i--){p=(LinkList)malloc(sizeof(LNode));scanf(%d,&p-data);p-next=L-next;L-next=p;//赋值}system(cls);//清屏printf(\n录入成功\n);}②插入函数StatusListInsert_L(LinkList&L,inti,intnewnode){//在顺序线性表L中第i个位置之前插入新的元素LinkListp=L;LinkLists;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)//i插入的位置不合法{printf(error\n);}s=(LinkList)malloc(sizeof(LNode));s-data=newnode;s-next=p-next;//将p的后继结点给s的后继结点p-next=s;//将s给p的后继结点returnOK;}③删除函数StatusListDelete_L(LinkList&L,inti){//在顺序线性表L中删除第i个元素，并用e返回其值LinkListp=L;LinkListq;intj=0;while(p-next&&ji-1)//如果满足这样的条件{p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;//删除位置非法q=p-next;//将p的后继结点给qp-next=q-next;//将q的后继结点给p的后继结点printf(\n\n删除成功\n\n被删除的结点是：%d\n,q-data);free(q);returnOK;}④查找函数StatusFindElemList_L(LinkList&L){//单链表按照关键字查询LinkListp;inti=1,NUMBER;intn=0;p=L-next;printf(\n输入查询数字：);scanf(%d,&NUMBER);while(p){if(p-data==NUMBER){printf(\n查询成功！该数字位于结点%d\n,i);n++;}p=p-next;i++;}if(!n){printf(\n查询失败！未找到该元素！\n);}returnOK;}}⑤计算并输出函数StatusPrintList_L(LinkList&L){//输出链表m=0;LinkListp;p=L;printf(\n);while(p-next!=NULL)//当链表非空{p=p-next;printf(%d:%d\n,++m,p-data);//输出}printf(\n);returnOK;}⑥销毁函数StatusDestroyList_L(LinkList&L)//销毁单链表{LinkListp,q;p=L;while(p){q=p;p=p-next;free(q);//释放}if(p==NULL)printf(\n成功，请退出\n\n);elseprintf(失败\n);returnOK;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目所要求的插入，删除，查找等基本操作。五、实验总结附录实验程序代码(该部分请加注释)#includestdio.h#includestdlib.h#includemalloc.h#defineMAX1000#defineOVERFLOW-2#defineOK1#defineERROR0intm=0;typedefintElemType;typedefintStatus;typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;StatusInitList_L(LinkList&L){L=(LinkList)malloc(sizeof(LNode));//构造一个空的线性表Lif(!L)exit(OVERFLOW);//存储分配失败L-next=NULL;//空表长度为0system(cls);//清空屏幕printf(\n\n初始化成功\n\n\n);system(PAUSE);//按任意键继续returnOK;}voidCreateList_L(LinkList&L){//创建一个新表inti,count;LinkListp;system(cls);//清屏printf(\n输入总结点数:);scanf(%d,&count);printf(\n输入各个结点数值，每输一个按下回车：\n);for(i=count;i0;i--)//循环嵌套{p=(LinkList)malloc(sizeof(LNode));scanf(%d,&p-data);p-next=L-next;L-next=p;//赋值}system(cls);//清屏printf(\n录入成功\n);}StatusListInsert_L(LinkList&L,inti,intnewnode){//在顺序线性表L中第i个位置之前插入新的元素LinkListp=L;LinkLists;intj=0;while(p&&ji-1){p=p-next;++j;}if(!p||ji-1)//i插入的位置不合法{printf(error\n);}s=(LinkList)malloc(sizeof(LNode));s-data=newnode;s-next=p-next;//将p的后继结点给s的后继结点p-next=s;//将s给p的后继结点returnOK;}StatusListDelete_L(LinkList&L,inti){//在顺序线性表L中删除第i个元素，并用e返回其值LinkListp=L;LinkListq;intj=0;while(p-next&&ji-1)//如果满足这样的条件{p=p-next;++j;}if(!(p-next)||ji-1)returnERROR;//删除位置非法q=p-next;//将p的后继结点给qp-next=q-next;//将q的后继结点给p的后继结点printf(\n\n删除成功\n\n被删除的结点是：%d\n,q-data);free(q);returnOK;}StatusFindElemList_L(LinkList&L){//单链表按照关键字查询LinkListp;inti=1,NUMBER;intn=0;p=L-next;printf(\n输入查询数字：);scanf(%d,&NUMBER);while(p){if(p-data==NUMBER){printf(\n查询成功！该数字位于结点%d\n,i);n++;}p=p-next;i++;}if(!n){printf(\n查询失败！未找到该元素！\n);}returnOK;}StatusPrintList_L(LinkList&L){//输出链表m=0;LinkListp;p=L;printf(\n);while(p-next!=NULL)//当链表非空{p=p-next;printf(%d:%d\n,++m,p-data);//输出}printf(\n);returnOK;}StatusDestroyList_L(LinkList&L)//销毁单链表{LinkListp,q;p=L;while(p){q=p;p=p-next;free(q);//释放}if(p==NULL)printf(\n成功，请退出\n\n);elseprintf(失败\n);returnOK;}voidmainmenu()//输出菜单{printf(\n菜单);printf(\n***********************\n\n);printf(*1.建立单链表*\n);printf(*2.录入新元素*\n);printf(*3.插入新元素*\n);printf(*4.删除已有元素*\n);printf(*5.查找元素*\n);printf(*6.输出单链表*\n);printf(*7.销毁线性表*\n);printf(*0.退出*\n);printf(\n***********************\n);}voidmain(){intchoose,location,value;LinkListL;while(1){mainmenu();printf(\n输入选择：);scanf(%d,&choose);switch(choose){case1:InitList_L(L);system(cls);break;case2:CreateList_L(L);PrintList_L(L);system(PAUSE);system(cls);break;case3:system(cls);PrintList_L(L);printf(请输入插入位置:);scanf(%d,&location);printf(请输入要插入的数值:);scanf(%d,&value);system(cls);ListInsert_L(L,location,value);PrintList_L(L);system(PAUSE);system(cls);break;default:printf(\n输入错误，重新输入！\n);case4:system(cls);PrintList_L(L);printf(\n请输入删除结点位置:);scanf(%d,&location);ListDelete_L(L,location);PrintList_L(L);system(PAUSE);system(cls);break;case5:system(cls);FindElemList_L(L);PrintList_L(L);system(PAUSE);system(cls);break;case6:system(cls);m=0;PrintList_L(L);printf(\n单链表的表长为：%d\n\n,m);m=0;system(PAUSE);system(cls);break;case7:system(cls);DestroyLis