数据结构实验二.doc

文档介绍：《数据结构》实验报告二学校:班级:学号:姓名:日期:程序名:一、上机实验的问题和要求:单链表的查找、插入与删除。设计算法,实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求:从键盘输入20个整数,产生不带表头的单链表,并输入结点值。从键盘输入1个整数,在单链表中查找该结点的位置。若找到,则显示“找到了”;否则,则显示“找不到”。从键盘输入2个整数,一个表示欲插入的位置i,另一个表示欲插入的数值x,将x插入在对应位置上,输出单链表所有结点值,观察输出结果。从键盘输入1个整数,表示欲删除结点的位置,输出单链表所有结点值,观察输出结果。将单链表中值重复的结点删除,使所得的结果表中个结点值均不相同,输出单链表所有结点值,观察输出结果。删除其中所有数据值为偶数的结点,输出单链表所有结点值,观察输出结果。把单链表变成带表头结点的循环链表,输出循环单链表所有结点值,观察输出结果。(★)将单链表分解成两个单链表A和B,使A链表中含有原链表中序号为奇数的元素,而B链表中含有原链表中序号为偶数的元素,且保持原来的相对顺序,分别输出单链表A和单链表B的所有结点值,观察输出结果。二、程序设计的基本思想,原理和算法描述:(包括程序的结构,数据结构,输入/输出设计,符号名说明等)这是一个带头结点的线性链表,数据域存放整形数据,由用户输入。头结点数据域存链表长度,所以程序中有个求链表长度的函数intLengthList(LinkListL);//求链表长度L是指向头结点的指针,将长度值存入语句为L->data=LengthList(L);为了实时观察链表情况,程序中有个输出链表数据的函数voidPrintList(LinkListL);//输出链表程序可以实现8种不同的操作,这8种不同的操作由8个函数实现,分别是voidCreateList(LinkList&L);//创建链表voidLocate(LinkListL);//查询数值voidInsertList(LinkList&L);//插入数值voidDeleteList(LinkList&L);//选择删除voidDeleterepeat(LinkList&L);//删除重复结点voidDeleteEven(LinkList&L);//删除数值为偶数的结点voidRotate(LinkList&L);//变为循环链表voidDivide(LinkList&L);//分解成两个链表这些基本操作的实现算法都比较简单,有些跟书本上一样,有些需要自己稍作思考才能写出,具体程序见第三部分8种不同的操作可以由用户通过按A-H这八个字母键来选择,分别是A:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数G:变为循环链表H:分解为两个链表,见第四部分输出截图,可以清晰的看到整个过程主程序中用开关语句实现:charoperate;printf("\n\n输入字符选择链表操作类型\nA:创建B:查询C:插入D:选择删除E:删除重复F:删除偶数\nG:变为循环链表H:分解为两个链表\n");scanf("%c",&operate); switch(operate) { case'a':case'A':CreateList(L);break; case'b': case'B':Locate(L);break; case'c': case'C':InsertList(L);break; case'd': case'D':DeleteList(L);break; case'e': case'E':Deleterepeat(L);break; case'f': case'F':DeleteEven(L);break; case'g': case'G':Rotate(L);break; case'h': case'H':Divide(L);break; case'\n':gotolabel;default:printf("输入有误,请重新输入!");break; }源程序及注释:#include<>#include<>typedefstructLNode//链表结点{ intdata; structLNode*next;}LNode,*LinkList;intover_flag=0;//主函数结束标识符voidCreateList(LinkList&L);//创建链表voidLocate(LinkListL);//查询数值voidInsertList(LinkList&L);//插入数值voidDeleteList(LinkList&L);//选择删除voidDeleterepeat(LinkList&L);//删除重复结点voidDeleteEven(LinkList&L);