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

1、单链表的建立查找插入删除数学与计算机学院计算机系实验报告W转互森叛海荻12o11：*验成;一"II 构I ! I1lJiB ! KB 1 :! 3 KB i| >> U BLB 上 1S *!i ! U ，辛!:!">! U j> j指导教师：黄襄念I姓名 ：I实验教室：1 IIi1abraham 6A-412Ij1:I实验名称：单链表的I学号： I实验日期：I健立/查找/插入/删112012/12/16 |1除I I Ij-实验序号：实验1 I实验时间：6:实验学时：4 1 II4I9:50,>111撰写说明：填写上面相关栏目，须作相应修改。

2、仔细阅读：最后“六、提交文档要求”有关说明。一、 实验目的1.熟悉掌握链表的创建、链表的常用算法：如查找节点，删除节点，插 入节点等等。二、实验环境1 .操作系统： Windows XP2 .开发软件：VC+6.0三、实验内容程序功能本程序完成了以下功能：1 .可以逐个添加英文字到链中。2 .可以删除链中的任意一元素而保持其他元素整体不变。3 .可以查找链表中的任意一个元素，只要输入该元素在链表中 的位置，就可以查找到该元素。4 .可以在该链表中插入任意一个元素不改变整体的顺序，输入你要插入的位置即可。数据结构本程序中使用的数据结构（若有多个，逐个说明）：1. 它的优缺点1）能将物理地址散乱的

3、链接在一起，更好的利用空间，可Head以动态的申请空间，如使用数组未必能申请到连续的空间但是用 链表就可以解决这个问题。2）能快速的删除节点，和增添节点。2.逻辑结构图3.存储结构图Num P Num4. 存储结构的C/C+语言描述typedef struct node char data;struct node *next;link;算法描述（结合流程图或伪代码描述算法，若无可略）本程序中采用的算法（若有多个，逐个说明）1 .算法名称：创建链表2 . 算法原理或思想通过申请一个结构体指针，在用结果体指针申请一个空间，在输入信息 后用前一个节点的Next指针将增加的结点与前面的结点链接，如此重

4、 复操作，就形成一个链表。3 .算法特点（优缺点，与可选或同类算法作对比）与数组相比较，是不连续的，它能随意的添加结点你需要多少就添加多少不会浪费多余的空间也不用提前去预测需要多少空间而其他的要考虑通用性，就必须申请较大的空间，而造成空间的浪 费。程序说明1.系统流程图（各个函数或类的调用流程图）I/O参数等2、程序模块(类或函数)代码：包括注释说明、模块功能、 1)创建链表模块：将链表创建录入数据。typedef struct nodechar data;struct node *next;link;link * get(link *m, int i)link *p;int j=0;p=m;

5、while(j<i) && (p->next!=NULL)p=p->next;j+;if(j=i)return p;elsereturn NULL;2)删除模块：将链表中不需要的节点数据删除 link * del(link *m, int i)link *p,*s;p=get(m,i-1);if(p=NULL)coutvv"输入有误"<<endl;elses=p->next;p->next=s->next;free(s);return m;3)查找模块：查找你想要的信息。link * find(link *m,

6、 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

7、, char ch,int i) link *p,*s;p=get(m,i-1);if(p=NULL)coutvv"输入有误"<<endl;elses=(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

8、;if(m!=NULL)docout<<p->data<<""p=p->next;while（p!=NULL）;四、调试与运行1 .程序调试调试：程序开发过程不可能没有 BUG,你用了哪些手段或方法发 现并改正错误。本程序开发过程中，采用的调试方法或手段如下：1）方法：输出一些连表中的数据，看能不能正常显示，调试数据是否 正确的录入了。2 .运行结果（贴图，JPG格式）本次实验多个功能需分别截图，逐个说明。运行结果图1运行结果图2运行结果图3而"F: Web LigVabraham. exe慢输入一串单字符数搭 以曼吉泵mjer

9、tyuiop*,前线性表为：.vj e 好七 y Li 三 口 d步选择您要的操作；J插入2、查找3、删除以退出上跳入您要查找的数猾值我的数将在第2梯置.当前技性表范.k(evtyuiop情选择您要的操作.上插入九查找九删除以退出情畅入您薯插入的数强度-情窥入您要施入的位叠2当前线性表为播选择您要的操作;1.插入2.查找九删除9,退出五、实验总结1 .结果分析：本程序完成了对链表的创建和插入、删除、查找功能，但是 还没有对字符串进行排序，2 .心得体会：通过这个实验让我掌握了了链表，指针等知识六、源代码#include <iostream> using namespace std;

10、 typedef struct node char data;struct node *next;link;link * get(link *m, int i)link *p;int j=0;p=m；while(j<i) && (p->next!=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<<"输入有误"<<end

11、l;elses=(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->n

12、ext;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;elses=p->next;p->next=s->next;free(s);return m;link * print(link *m) int i,k;char ch;link *p,*q;cout<<"当前线性

13、表为："<<endl;p=m;p=p->next;if(m!=NULL)docout<<p->data<<""p=p->next;while(p!=NULL);cout«endl;cout<<"请选择您要的操作：cout«" 1 、插入”；cout«" 2、查找cout«" 3、删除”；cout«" 0、退出cout«endl;cin»k;if(k=1)(cout«&qu

14、ot;请输入您要插入的数据值：cin»ch;cout«"请输入您要插入的位置："cin»i;p=ins(m,ch,i);q=print(m);)else if(k=2)coutvv”请输入您要查找的数据值:II.cin>>ch;p=find(m,ch);q=print(m);else if(k=3)cout<<"请输入您要删除的数据的位置："cin>>i;p=del(m,i);q=print(m);else if(k=0) ;elsecout<<"输入错误!"<<endl;q=print(m); return m;int main()cout<<"请输入一串单字符数据，以 *结束!"<<endl;cha