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

数学与计算机学院计算机系实验报告课程名称： 数据结构年级：2011实验成绩：指导教师： 黄襄念姓名：abraham 实验教室：6A-412实验名称：单链表的建立/查找/插入/删除学号： 实验日期：2012/12/16实验序号：实验1实验时间：6:409:50实验学时：4撰写说明：填写上面相关栏目，须作相应修改。仔细阅读：最后“六、提交文档要求”有关说明。一、 实验目的1.熟悉掌握链表的创建、链表的常用算法：如查找节点，删除节点，插入节点等等。二、实验环境1. 操作系统：Windows XP2. 开发软件：VC+6.0三、实验内容l 程序功能本程序完成了以下功能：1. 可以逐个添加英文字到链中。2. 可以删除链中的任意一元素而保持其他元素整体不变。3. 可以查找链表中的任意一个元素，只要输入该元素在链表中的位置，就可以查找到该元素。4. 可以在该链表中插入任意一个元素不改变整体的顺序，输入你要插入的位置即可。l 数据结构本程序中使用的数据结构（若有多个，逐个说明）：1. 它的优缺点1） 能将物理地址散乱的链接在一起，更好的利用空间，可以动态的申请空间，如使用数组未必能申请到连续的空间但是用链表就可以解决这个问题。2） 能快速的删除节点，和增添节点。2. 逻辑结构图开始创建链表插入节点删除节点查找节点结束 3. 存储结构图 Head mNumNextNumNext 4. 存储结构的C/C+ 语言描述typedef struct node char data; struct node *next;link;l 算法描述（结合流程图或伪代码描述算法，若无可略）本程序中采用的算法（若有多个，逐个说明）1. 算法名称：创建链表 2. 算法原理或思想通过申请一个结构体指针，在用结果体指针申请一个空间，在输入信息后用前一个节点的Next指针将增加的结点与前面的结点链接，如此重复操作，就形成一个链表。3. 算法特点（优缺点，与可选或同类算法作对比）与数组相比较，是不连续的，它能随意的添加结点你需要多少就添加多少不会浪费多余的空间也不用提前去预测需要多少空间而其他的要考虑通用性，就必须申请较大的空间，而造成空间的浪费。l 程序说明1. 系统流程图（各个函数或类的调用流程图） MainCreate（head）Deleted(head)Find(head)Ins（head）退出2、程序模块（类或函数）代码：包括注释说明、模块功能、I/O参数等1） 创建链表模块：将链表创建录入数据。typedef struct node char data; struct node *next;link;link * get(link *m, int i) link *p;int j=0; p=m; while(ji) (p-next!=NULL) p=p-next;j+; if(j=i) return p; else return NULL;2） 删除模块：将链表中不需要的节点数据删除。link * del(link *m, int i) link *p,*s; p=get(m,i-1); if(p=NULL) cout输入有误endl; else s=p-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个位置.endl; j=1;p=p-next; if(j!=1) cout您查找的数据不在线性表中.endl; return m;4） 添加模块：添加你还需要添加的信息到链表中。link * ins (link *m, char ch,int i) link *p,*s; p=get(m,i-1); if(p=NULL) cout输入有误endl; else s=(link *)malloc(sizeof(link); s-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当前线性表为：endl; p=m;p=p-next; if(m!=NULL) do coutp-data ; p=p-next; while(p!=NULL);四、调试与运行1. 程序调试调试：程序开发过程不可能没有BUG，你用了哪些手段或方法发现并改正错误。本程序开发过程中，采用的调试方法或手段如下：1) 方法： 输出一些连表中的数据，看能不能正常显示，调试数据是否正确的录入了。2. 运行结果（贴图，JPG格式） 本次实验多个功能需分别截图，逐个说明。运行结果图1 运行结果图2运行结果图3五、实验总结1. 结果分析：本程序完成了对链表的创建和插入、删除、查找功能，但是还没有对字符串进行排序，2. 心得体会：通过这个实验让我掌握了了链表，指针等知识六、源代码#include iostreamusing namespace std;typedef struct node char data; struct node *next;link;link * get(link *m, int i) link *p;int j=0; p=m; while(ji) (p-next!=NULL) p=p-next;j+; if(j=i) return p; else return NULL;link * ins (link *m, char ch,int i) link *p,*s; p=get(m,i-1); if(p=NULL) cout输入有误endl; else s=(link *)malloc(sizeof(link); s-data=ch; s-next=p-next; p-next=s; return m;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个位置.endl; j=1;p=p-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输入有误endl; else s=p-next; p-next=s-next; free(s); return m;link * print(link *m) int i,k; char ch; link *p,*q; cout当前线性表为：endl; p=m;p=p-next; if(m!=NULL) do coutp-data ; p=p-next; while(p!=NULL); coutendl; cout请选择您要的操作：; cout 1、插入; cout 2、查找; cout 3、删除; cout 0、退出; coutendl; cink; if(k=1) cout请输入您要插入的数据值：; cinch; cout请输入您要插入的位置：; cini; p=ins(m,ch,i); q=print(m); else if(k=2) cout请输入您要查找的数据值：; cinch; p=find(m,ch); q=print(m); else if(k=3) cout请输入您要删除的数据的位置：; cini; p=del(m,i); q=print(m); else if(k=0) ; else cout输入错误!endl; q=print(m); return m;int main() cout请输入一串单字符数据，以*结束！endl; char ch; link *r,*p,*q,*m; m=(l