单链表的建立查找插入删除.doc

1、单链表的建立查找插入删除数学与计算机学院计算机系实验报告课程名称： 数据结 年级： 2011实验成绩：构指导教师： 黄襄念姓 名： 实验教室：abraham6A-412实验名称：单链表的 学号：实验日期：建立 /查找 /插入 /删2012/12/16除实验序号：实验 1实验时间：6:40实验学时： 4 9:50撰写说明：填写上面相关栏目，须作相应修改。仔细阅读： 最后“ 六、提交文档要求 ”有关说明。一、实验目的1. 熟悉掌握链表的创建、链表的常用算法：如查找节点，删除节点，插入节点等等。二、实验环境1. 操作系统： Windows XP2. 开发软件： VC+6.0三、实验内容程序功能本程序

2、完成了以下功能：1. 可以逐个添加英文字到链中。2. 可以删除链中的任意一元素而保持其他元素整体不变。3. 可以查找链表中的任意一个元素， 只要输入该元素在链表中的位置，就可以查找到该元素。4. 可以在该链表中插入任意一个元素不改变整体的顺序， 输入你要插入的位置即可。数据结构本程序中使用的数据结构（若有多个，逐个说明）：1. 它的优缺点1）能将物理地址散乱的链接在一起，更好的利用空间，可以动态的申请空间， 如使用数组未必能申请到连续的空间但是用链表就可以解决这个问题。2）能快速的删除节点，和增添节点。2. 逻辑结构图开始创插删查建入除找链节节节结束3. 存储结构图HeadmNumNum4.

3、存储结构的 C/C+ 语言描述 typedef struct nodechar data;struct node *next; link;算法描述（结合流程图或伪代码描述算法，若无可略）本程序中采用的算法（若有多个，逐个说明）1. 算法名称：创建链表2. 算法原理或思想通过申请一个结构体指针，在用结果体指针申请一个空间，在输入信息后用前一个节点的 Next 指针将增加的结点与前面的结点链接，如此重复操作，就形成一个链表。3. 算法特点（优缺点，与可选或同类算法作对比）与数组相比较，是不连续的，它能随意的添加结点 你需要多少就添加多少 不会浪费多余的空间 也不用提前去预测需要多少空间而其他的要考

4、虑通用性，就必须申请较大的空间，而造成空间的浪费。程序说明1. 系统流程图（各个函数或类的调用流程图）CreateDeleted退MaFind(he出Ins2、程序模块（类或函数）代码：包括注释说明、模块功能、I/O 参数等1） 创建链表模块：将链表创建录入数据。typedef struct nodechar data;struct node *next;link;link * get(link *m, int i)link *p;int j=0;p=m;while(jnext!=NULL)p=p-next;j+;if(j=i)return p;elsereturn NULL;2） 删除模块：

5、将链表中不需要的节点数据删除。link * del(link *m, int i)link *p,*s;p=get(m,i-1);if(p=NULL)cout 输入有误 next;p-next=s-next;free(s);return m;3） 查找模块：查找你想要的信息。link * find(link *m, char ch)link *p; int i=0; int j=0;p=m;while(p!=NULL) i+;if(p-data!=ch)p=p-next;else cout 您查找的数据在第 i-1 个位置 .next;if(j!=1)cout 您查找的数据不在线性表中.end

6、l;return m;4） 添加模块：添加你还需要添加的信息到链表中。link * ins (link *m, char ch,int i) link *p,*s; p=get(m,i-1); if(p=NULL)cout 输入有误 data=ch;s-next=p-next;p-next=s;return m;5）打印模块：打印出信息。link * print(link *m) int i,k; char ch; link *p,*q;cout 当前线性表为： next;if(m!=NULL)docoutdatanext;while(p!=NULL);四、调试与运行1. 程序调试调试：程序开

7、发过程不可能没有 BUG ，你用了哪些手段或方法发现并改正错误。本程序开发过程中，采用的调试方法或手段如下：1) 方法： 输出一些连表中的数据，看能不能正常显示，调试数据是否正确的录入了。2. 运行结果（贴图， JPG 格式）本次实验多个功能需分别截图，逐个说明。运行结果图 1运行结果图 2运行结果图 3五、实验总结1. 结果分析：本程序完成了对链表的创建和插入、删除、查找功能，但是还没有对字符串进行排序，2. 心得体会：通过这个实验让我掌握了了链表，指针等知识六、源代码#include using namespace std;typedef struct nodechar data;stru

8、ct node *next;link;link * get(link *m, int i)link *p;int j=0;p=m;while(jnext!=NULL)p=p-next;j+;if(j=i)return p;elsereturn NULL;link * ins (link *m, char ch,int i) link *p,*s;p=get(m,i-1);if(p=NULL)cout 输入有误 data=ch;s-next=p-next;p-next=s;return m;link * find(link *m, char ch)link *p; int i=0; int j=

9、0;p=m;while(p!=NULL) i+;if(p-data!=ch)p=p-next;else cout 您查找的数据在第 i-1 个位置 .next;if(j!=1)cout 您查找的数据不在线性表中 .endl; return m;link * del(link *m, int i)link *p,*s;p=get(m,i-1);if(p=NULL)cout 输入有误 next;p-next=s-next;free(s);return m;link * print(link *m) int i,k; char ch; link *p,*q;cout 当前线性表为： next;if(

10、m!=NULL)docoutdatanext;while(p!=NULL);coutendl;cout 请选择您要的操作： ; cout 1 、插入 ; cout 2 、查找 ;cout 3 、删除 ;cout 0 、退出 ;coutk;if(k=1)coutch;couti;p=ins(m,ch,i);q=print(m);else if(k=2)coutch;p=find(m,ch);q=print(m);else if(k=3)couti;p=del(m,i);q=print(m);else if(k=0);elsecout 输入错误 !endl;q=print(m);return m;int main()cout 请