实验报告二——单链表.doc

《数据单链表结构》实验报告二单链表 实验二—单链表 分校：上海第二工业大学 班级：09安全01 学号：092631070 姓名：禹永根 日期：2010/11/23 程序名： L2311.CPP 一、上机实验的问题和要求： 单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求： 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。 （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。 二、程序设计的基本思想，原理和算法描述： （包括程序的结构，数据结构，输入/输出设计，符号名说明等） 用一组地址任意的存储单元存放线性表中的。 以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点(表示数据元素 或 数据元素的映象) 以“结点的序列”表示线性表 (( 称作线性链表（单链表） 　 　（1）、数据域：用来存储本身数据。 　（2）、链域或称为指针域：用来存储下一个结点地址或者说指向其直接后继的指针。 1、单链表的查找 对单链表进行查找的思路为：对单链表的结点依次扫描，检测其数据域是否是我们所要查好的值，若是返回该结点的指针，否则返回NULL。 2、单链表的插入 因为在单链表的链域中包含了后继结点的存储地址，所以当我们实现的时候，只要知道该单链表的头指针，即可依次对每个结点的数据域进行检测。 假设在一个单链表中存在2个连续结点p、q（其中p为q的直接前驱），若我们需要在p、q之间插入一个新结点s，那么我们必须先为s分配空间并赋值，然后使p的链域存储s的地址，s的链域存储q的地址即可。(p-＞link=s;s-＞link=q)，这样就完成了插入操作。 3、单链表的删除 删除运算思想方法删除运算是将表的第i个结点删去。具体步骤：找到a i-1 的存储位置p令p-next指向a i 的直接后继结点释放结点a i 的空间，将其归还给存储池。 #include stdio.h #include stdlib.h //单链表的定义： typedef int DataType; //DataType可以是任何相应的数据类型如int, float或char typedef struct node //结点类型定义 { DataType data; //结点的数据域 struct node *next; //结点的指针域 }ListNode; typedef ListNode *LinkList; int a[10]; void main() { int i; DataType key; DataType x; LinkList head; ListNode *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);