线性表的链式存储结构.doc

贵州大学实验报告学院：计算机科学与信息学院 专业： 班级： 姓名学号实验组实验2实验时间指导教师叶洁成绩实验项目名称实验二：线性表的链式存储结构实验目的1. 熟练掌握线性表的基本操作在链式存储上的实现；2. 以线性表的各种操作（建立、插入、删除等）的实现为重点；3. 掌握线性表的动态分配顺序存储结构的定义和基本操作的实现；实验环境运行Microsoft Visual Studio 2010的微机一台实验内容 1输入一组整型数据，建立带头结点的单链表。2实现该线性表的删除。3、实现该线性表的插入。4实现线形表中数据的显示。5实现线性表数据的查找和定位5、编写一个主函数,调试上述算法。实验数据1 未创建链表前选择其它操作会提示操作失败，选择【1】创建链表，在创建链表时，键入“no”来结束输入结点，如何先后键入-44，11，22，当键入“no”时，退出录入数据.如图2、 在选择【2】查找元素操作时，又会产生3个子选项，输入不合法的操作都会提示非法。选择【1】按元素查找时，输入相应的元素，会显示相应的查找结果，选择【2】按位置查找，键入位置值，会显示相应的查找结果，若位置值超出链表的长度则会查找失败。选择【3】退出查找并返回主菜单。3、 选择【3】插入元素时，也会弹出3个子菜单，键入13之外的任何字符都会提示非法操作。选择【1】按有序插入，若键入不任何非整型字符串都会提示非法并要求重新正确输入。或按有序插入12，会插入11与22之间，即第3个位置。选择【2】按位置插入，如在第5个位置插入45。如果选择位置45会提示位置值无效，因为链表总结点数也只有5个。选择【3】退出插入，则会退出插入并返回主菜单。具体操作实现如下：4、 选择【4】删除元素，则会生成3个了菜单。也只有输入相应的序号才能执行相应的功能，键入其它字符都会提示非法并要求重新输入。如选择【1】按元素删除，要求输入待删除的元素，若键入非法数据则会提示非法，键入一个数后会查找到这个数据并删除，若键入链表中不存在的数据则提示删除失败，执行完后又跳回子菜单。如选择【2】按位置删除，输入相应的位置值，若位置值超出了链表的长度会提示错误信息，若位置在链表长度之内，则会把相应位置的元素删除，选择【3】退出删除，则退出删除并返回主菜单。删除前,链表为：-44，11，12，22，12;删除后为：-44，11，12。具体实现如图：5、 选择【5】显示链表则会显示当前链表所有信息，包括每个结点中元素和链表结点数。如图所示：6、 为了测试【6】排序链表的功能，因为现有的链表为-44，11，12有序链表。不妨先按位置插入几个数使其成为无序表，再选择【6】排序链表，排序前后如图：7、 选择【7】清空链表，则会清空当前链表，清空链表后在再次创建一个链表前无法使用其它功能。具体实现如图：八、在主菜单的8个选项中若键入18之外任何其它信息则会提示选择的操作非法，并要求重新输入。若选择【8】退出系统，会出现，以保证不会因为意外操作面退出系统。选择“n”则不会退出系统，选择“y”则会退出系统。键入其它任何信息，则会提示操作非法，并要求重新选择。具体功能实现如图：实验总结 1.虽然实验要求在主函数中实现对各种功能函数的调用，但考虑到可能会在主函数中实现其实现其它功能，所有在写程序并没有把调用写在主函数中，而是统一写在void Menu( )函数中，再由主函数调用这个Menu函数，以实现对链表相应的操作。 2.为提高本程序的健壮性，在写程序时，我用到了int atoi(char *p)函数来将输入的合法的字符串转化成整型数据。由于键入整型数据地方很多，所以编写了int JudgeData()函数，在每次要输入数据的地方都调用这个函数来判断输入数据的合法性;同样在选择相应操作时，我也相应地编写了char JudgeOperation( )函数以判断选择操作的合法性，在每处需要选择相应操作的地方都调用这个函数来判断选择操作的合法性。利用这两个函数大大提高了程序的健壮性，解决了实验一中的输入不合法类型数据会进入死循环的现象。3.通过本次实验让我对链表的创建、插入、删除、清空、排序等操作都有了进一步的了解和深入的认识。4.本次实验和实验一和实验二比，在健壮性上有很大的提高，并且由于对char JudgeOperation( )和int JudgeData()的反复调用，节省了不少代码。5.和实验一相比，由于本次实验在输入数据的地方调用了int JudgeData()函数，因此只能将ElemType定义为int型，若定义为char类型，则运行程序不会产生预期的效果。这一点还望老师指正！指导教师意见签名： 年 月 日程序清单如下：/ 实验二-链表.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#includeusing namespace std;typedef int ElemType;struct LNodeElemType data;LNode* next;/初始化链表void InitList(LNode* &HL)HL-next =NULL;/判断输入的数据是否为整型int JudgeData()char c100;Judge:cinc;if(strcmp(c,no)=0)return(-879);else if(c0=-|c0=0&c0=9)for(int i=1;ci!=0;i+)if(ci9)cout您输入的数据非法！endl;cout请重新输入合法类型数据： ;goto Judge;return atoi(c);elsecout您输入的数据非法！endl;coutc;if(strlen(c)=1)if(c08)cout您输入的操作不合法！请重新选择：;goto judge;elsecout您输入的操作不合法！请重新选择：;goto judge;return (c0);/为链表录入数据void InputList(LNode* &HL)int i=0;LNode* ap,*cp;ap=HL;while(1)i+;cout（如数据已录入完毕，请输入“no”）请输入第 i 个数据： ;ElemType item=JudgeData(); if(item=-879)cout您录入 i-1 个数据完毕！next =cp;cp-data =item;ap=cp;ap-next=NULL;/显示链表所有信息void DisplayList(LNode* HL)int i=0;LNode* cp=HL-next;while(cp!=NULL)i+;coutdatanext;coutendl;cout链表中共有 i 个元素！next;if(pos-1)cout位置值无效，查找失败！next!=NULL)pos+;cp=cp-next;else if(pos=0)pos=1;while(cp!=NULL)if(cp-data=item)break;elsepos+;cp=cp-next;if(cp=NULL)cout没有找到您想要查找的元素！next;i+;if(cp=NULL)cout您输入的位置值已超过链表的总长度，查找失败！endl;return;cout查找成功！您所查找的元素 data 在链表第 pos 个位置！next;ap=HL;if(pos-1)cout位置值无效，插入失败！next;else if(pos=0)pos=1;while(cp!=NULL)if(item data) break;elseap=cp;cp=cp-next;pos+;elseint i=0;while(cp!=NULL)i+;if(i=pos) break;elseap=cp;cp=cp-next;if(i+1pos)cout位置值超出链表的长度，插入失败！data=item;if(pos=1)HL-next=tp;tp-next=cp;elseap-next=tp;tp-next=cp;cout插入成功！您已成功把元素 item 插入到第 pos 个位置！next;ap=HL;if(pos-1)cout您输入的位置值无效，删除失败！next!=NULL)pos+;ap=cp;cp=cp-next;else if(pos=0)pos=1;while(cp!=NULL)if(cp-data=item) break;elsepos+;ap=cp;cp=cp-next;if(cp=NULL)cout没有找到您要删除的元素，删除失败！next;if(cp=NULL)cout您输入的位置值已超过链表的长度，删除失败！next=cp-next;elseap-next=cp-next;ElemType tem=cp-data;delete cp;cout删除成功！您所要删除的元素 tem 已从链表中第 pos 个位置删除！next;if(HL-next=NULL)cout链表未创建或已被清空！next;delete tem;HL-next=NULL;cout清空链表成功！next;tem-next=NULL;while(cp!=NULL)InsertList(tem,cp-data,0);cp=cp-next;EmptyList(HL);cout链表更新成功！排序后链表如下：endl;HL=tem;/操作菜单void Menu()LNode* h;h=new LNode;InitList(h);ElemType item;int pos;menu:cout欢迎进入链表管理系统：endl;cout 1.创建链表endl;cout 2.查找元素endl;cout 3.插入元素endl;cout 4.删除元素endl;cout 5.显示链表endl;cout 6.排序链表endl;cout 7.清空链表endl;cout 8.退出系统endl;cout请选择您想要执行的操作：;switch(JudgeOperation()case 1:InputList(h);coutnext=NULL)cout链表未创建，查找失败！endlendl;goto menu;Find:cout查找操作有：1.根据元素查找位置endl;cout 2.根据位置查找元素endl;cout 3.退出查找操作endl;cout请选择相应的查找操作：;switch(JudgeOperation()case 1:cout请输入你要查找的元素： ;item=JudgeData();FindList(h,item,0);goto Find;case 2:cout请输入您要查找的位置(查看尾元素请键入-1)： ;pos=JudgeData();FindList(h,0,pos);goto Find;case 3:coutendl;goto menu;default :cout您选择的操作非法！next=NULL)cout链表未创建，插入失败！endlendl;goto menu;Insert:cout插入操作有：1.按有序插入endl;cout 2.按位置插入endl;cout 3.退出插入操作endl;cout请选择相应的操作： ;switch(JudgeOperation()case 1:cout请输入要插入的元素： ;item=JudgeData();InsertList(h,item,0);goto Insert;case 2:cout请输入要插入的位置： ;pos=JudgeData();cout请输入要插入的元素（在末尾插入请键入-1）： ;item=JudgeData();InsertList(h,item,pos);goto Insert;case 3:coutendl;goto menu;default:cout您选择的操作非法！next=NULL)cout链表未创建，删除失败！endlendl;goto menu;Delete:cout删除操作有：1.按元素删除endl;cout 2.按位置删除endl;cout 3.退出删除操作endl;cout请选择相应的操作： ;switch(JudgeOperation()case 1:cout请输入您想要删除的元素：; item=JudgeData();DeleteList(h,item,0);goto Delete;case 2:cout请输入您想要删除元素的位置（删除末尾元素请键入-1）： ;pos=JudgeData();DeleteList(h,0,pos);goto Delete;case 3:coutendl;goto menu;default:cout您选择的操作非法！next=NULL)cout链表未创建，请先创建！endlendl;goto menu;DisplayList(h);coutnext=NULL)cout链表未创建，排序失败！endlendl;goto menu;SortList(h);Disp