《数据结构》实验报告二及其答案.docVIP

《数据结构》实验报告二 学校： 班级： 09软工A1 学号： 09XXXXX 姓名： XXX 日期： 2010 .04.08 程序名： L2311.CPP 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入20个整数，产生带表头的单链表，并输入结点值。 从键盘输入1个整数，在单链表中查找该结点。若找到，则显示“找到了”；否则，则显示“找不到”。 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。 （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 三、源程序及注释： #include iostream.h //单链表的定义： typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char typedef struct node //结点类型定义 { DataType data; //结点的数据域 struct node *next; //结点的指针域 }ListNode,*LinkList; //typedef ListNode *LinkList; void main() { int i; DataType key,x; LinkList head; //ListNode *p; LinkList p; LinkList CreateList(void); void PrintList(LinkList head); LinkList LocateNode(LinkList head,DataType key); LinkList GetNode(LinkList head,int i); void InsertList(LinkList head,DataType x,int i); void DeleteList(LinkList head,int i); void DeleteManyList(LinkList head); void DeleteEvenList(LinkList head); void ChangeCircList(LinkList head); void PrintCircList(LinkList head); head=CreateList(); //建立单链表 PrintList(head); //打印单链表 cout输入要查找的值:; cinkey; p=LocateNode(head,key); //单链表查找 cout输入要查找的位置:; cini; p=GetNode(head, i); cout请输入欲插入元素的位置:; cini; cout请输入欲插入的元素(整数):; cinx; InsertList(head,x,i); //单链表插入 PrintList(head); //打印单链表 cout请输入欲删除结点的位置:; cini; DeleteList(head,i); //单链表删除 PrintList(head); //打印单链表 DeleteManyList(head); //删除重复值 PrintList(head);