算法与数据结构实验报告详解.doc

2015-2016学年第二学期 《算法与数据结构》课程实验报告 专业软件工程学生姓名成晓伟班级软件141学号1410075094实验学时16实验教师徐秀芳 信息工程学院 实验一 单链表的基本操作 一、实验目的 1.熟悉C语言上机环境，进一步掌握C语言的基本结构及特点。 2.掌握线性表的各种物理存储表示和C语言实现。 3.掌握单链表的各种主要操作的C语言实现。 4.通过实验理解线性表中的单链表存储表示与实现。 二、主要仪器及耗材 普通计算机 三、实验内容与要求 1、用C语言编写一个单链表基本操作测试程序。 （1）初始化单链表 （2）创建单链表 （3）求单链表长度 （4）输出单链表中每一个结点元素 （5）指定位置插入某个元素 （6）查找第i个结点元素的值 （7）查找值为e 的结点，并返回该结点指针 （8）删除第i个结点 （9）销毁单链表 2、实验要求 （1）程序中用户可以选择上述基本操作。 程序启动后，在屏幕上可以菜单形式显示不同功能，当按下不同数字后完成指定的功能，按其他键，则显示错误后重新选择。 （2）要求用线性表的顺序存储结构，带头结点的单链表存储结构分别实现。 （3）主函数实现对基本操作功能的调用。 3、主要代码 （1）初始化单链表 LinkList *InitList(){ //创建一个空链表,初始化线性表 LinkList *L; L=(LinkList *)malloc(sizeof(LinkList)); L-next=NULL; return L; } （2）创建单链表//头插法 void CreateListF(LinkList *L){ LinkList *s; int i=1,a=0; while(1){ printf(输入第%d个元素(0表示终止),i++); scanf(%d,a); if(a==0) break; s=(LinkList *)malloc(sizeof(LinkList)); s-data=a; s-next=L-next; L-next=s; } } （3）求链表长度 int ListLength(LinkList *L){ //求链表长度 int n=0; LinkList *p=L; while(p-next!=NULL) { p=p-next; n++; } return(n); } （4）在指定位置插入元素 int InsertList(LinkList *L,int i,ElemType e){ LinkList *p=L,*s; int j=0; while(p!=NULLji-1){ p=p-next; j++; } //找出要插入的位置的前一个位置 if(p==NULL){ return 0; } else{ s=(LinkList *)malloc(sizeof(LinkList)); s-data=e; s-next=p-next; p-next=s; return 1; } } （5）输出链表 void DispList(LinkList *L){ //输出链表 LinkList *p=L-next; while(p!=NULL) { printf(%d,p-data); p=p-next; } printf(\n); } （6）查找链表中指定元素 int GetElem(LinkList *L,int i){ //查找链表中指定元素 LinkList *p=L; int j=0; while(jip!=NULL){ j++; p=p-next; } if(p==NULL){ return 0; } else{ return p-data; } } （7）查找值是e的结点并返回该指针 LinkList *LocateElem(LinkList *L,ElemType e){ //查找值是e的结点并返回该指针 int i=1; LinkList *p=L; while(p!=NULL) { if(p-data==e) return p; } if(p==NULL){ return NULL; } } （8）删除元素 int ListDelete(LinkList *L,int i,ElemType *e){ //删除元素 LinkList *p=L,*q; int j=0; while(p!=NULLji-1){ p=p-next; j++; } //找到要删除