数据结构实验报告排版模板及要求.doc

实 验 报 告
实验名称
单链表基本操作
评分：
实验课时
2课时
实验地点
综合楼E405
实验时间
2013年9月23日 星期一 第4周
实验目的
及要求
实验目的：
通过单链表实验，进一步熟悉理论教学内容，掌握基本的知识点，发现理论学习中的不足；理清学习脉络；能独立思考，根据具体的问题组织数据，合理的安排，给出解决问题的较好方法。
实验要求：
（1）用结构体描述一个字符型的单链表；
（2）实现线性表的链式存储结构（单链表）的基本运算，包括初始化线性表、销毁线性表、判断线性表是否为空、求线性表长度、输出线性表、求线性表中元素值、元素查找、插入元素、删除元素、求元素前驱节点和后继结点、线性表节点逆置；
实验设备
（软件、硬件及耗材）
软件环境：Vc++6.0；Windows XP;
硬件环境：1GB内存；Intel core I5;

实验内容
（算法、程序、步骤、方法及数据记录）

实验内容
（算法、程序、步骤、方法及数据记录）

实验内容
（算法、程序、步骤、方法及数据记录）

实验内容
（算法、程序、步骤、方法及数据记录）

实验内容
（算法、程序、步骤、方法及数据记录）

实验内容
（算法、程序、步骤、方法及数据记录）

本次试验采用封装的编程理念来完成程序设计。
本例程序共有两个文件。分别为主函数文件main.cpp和功能函数文件list.cpp。其中主函数文件用来调用过各个功能函数，在输出端显示最终的试验成果。功能函数文件则用来具体实现程序的各种功能。两个文件通过建立工程的方式链接。
本例程序共有除主函数main()之外的11个函数。分别实现：初始化链表、释放链表、判断链表是否为空、求链表的元素个数、输出链表、获取链表中的某个元素、查找链表中的某个元素、在链表中插入元素、在链表中删除元素、求元素前驱结点、求元素后继结点、链表元素逆置等功能。每个功能通过调用相应函数来实现。函数内部封装，主函数通过接口调用。
其余思路及算法设计详见程序代码及注释。
//文件名main
#include<stdio.h>
#include<malloc.h>
typedef char elemtype;
typedef struct lnode
{
elemtype data;
struct lnode *next;
}linklist;
extern void initlist(linklist *&l);
extern void destroylist(linklist *&l);
extern int listempty(linklist *l);
extern int listlength(linklist *l);
extern void displist(linklist *l);
extern int getelem(linklist *l,int i,elemtype &e);
extern int locateelem(linklist *l,elemtype e);
extern int listinsert(linklist *&l,int i,elemtype e);
extern void listdelete(linklist *&l,int i,elemtype &e);
extern int priorelem(linklist *l,elemtype cur_e,elemtype &pre_e);
extern int nextelem(linklist *l,elemtype cur_e,elemtype &nex_e);
extern void reverse(linklist *&l);
void main()
{
linklist *l;
elemtype e,s;
printf("（1）初始化顺序表L\n");
initlist(l);
printf("（2）采用尾插入法插入a,b,c,d,e元素\n");
listinsert(l,1,'a');
listinsert(l,2,'b');
listinsert(l,3,'c');
listinsert(l,4,'d');
listinsert(l,5,'e');
printf("（3）输出顺序表L\n");
displist(l);
printf("（4）顺序表L长度=%d\n",listlength(l));
printf("（5）顺序表L为=%s\n",(listempty(l)?"空":"非空"));
getelem(l,3,e);
printf("（6）顺序表L的第3个元素=%c\n",e);
printf("（7）元素a的位置=%d\n",locateelem(l,'a'));
printf("（8）在第4个元素位置上插入f元素\n");
listinsert(l,4,'f');
printf(" (9)输出顺序表L:\n");
displist(l);
printf("(10)删除L的第3个元素\n");
listdelete(l,3,e);
printf("(11)输出顺序表L\n");
displist(l);
//（输入节点，完成主函数部分该节点的前驱节点的显示）
printf("请输入要查找的节点: ");
scanf("%c",&s);
if(!priorelem(l,s,e))
printf("(12)该节点没有前驱节点!\n\n");
else
printf("(12)该节点的前驱节点为:%c\n",e);
if(!nextelem(l,s,e))
printf("(13)该节点没有后继节点!\n\n");
else
printf("(13)该节点的后继节点为:%c\n\n",e);

reverse(l);
printf("(14)逆置后的链表为:\n");
displist(l);
printf("(15)释放顺序表L\n\n");
}
文件名algo2_2
#include <stdio.h>
#include <malloc.h>
#include <math.h>
typedef char elemtype;
typedef struct lnode
{
elemtype data;
struct lnode *next;
}linklist;
void initlist(linklist *&l)
{
l=(linklist *)malloc(sizeof(linklist));
l->next=NULL;
}
void destroylist(linklist *&l)
{
linklist *p=l,*q=p->next;
while(q!=NULL)
{
free(p);
p=q;
p=p->next;
}
free(p);
}
int listempty(linklist *l)
{
return (l->next==NULL);
}
int listlength(linklist *l)
{
int n=0;
linklist *p=l;
while(p->next!=NULL)
{
n++;
p=p->next;
}
return (n);
}
void displist(linklist *l) //输出线性表
{
linklist *p=l->next;
while(p!=NULL)
{
printf(" %c ",p->data);
p=p->next;
}
printf("\n");
}
int getelem(linklist *l,int i,elemtype &e) //求线性表中某个数据元素的值
{
int j=0;
linklist *p=l;
while(j<i&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return false;
else
{
e=p->data;
return true;
}
}
int locateelem(linklist *l,elemtype e)
{
int i=1;
linklist *p=l->next;
while(p!=NULL&&p->data!=e)
{
p=p->next;
i++;
}
if(p==NULL)
return(0);
else
return (i);
}
int listinsert(linklist *&l,int i,elemtype e) //插入数据元素
{
int j=0;
linklist *p=l,*s;
while(j<i-1&&p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
return false;
else
{
s=(linklist *)malloc(sizeof(linklist));
s->data=e;
s->next=p->next;
p->next=s;
return true;
}
}
void listdelete(linklist *&l,int i,elemtype &e) //删除数据元素
{
int j=0;
linklist *p=l,*q;
while(j<i-1 && p!=NULL)
{
j++;
p=p->next;
}
if(p==NULL)
// return 0;
printf("不存在该节点1\n");
else
{
q=p->next;
if(q==NULL)
// return 0;
printf("不存在该节点2\n");

e=q->data;
p->next=q->next;
free(q);
// return 1;
printf("删除成功\n");
}
}
int priorelem (linklist *l, elemtype cur_e, elemtype &pre_e) //前驱节点
{
linklist *q,*p;
p=l->next;//p指向第一个节点
while(p->next)//p指向节点有后继
{
q=p->next;//q为p的后继
if(q->data==cur_e){
pre_e=p->data;
return 1;
}
p=q;//p向后移
}
return 0;
}
//若cur_e是l的数据元素，且不是第一个，则用pre_e返回它的前驱，
//返回1，否则操作失败，pre_e无定义，返回0
int nextelem (linklist *l, elemtype cur_e, elemtype &nex_e) //后继节点
{
linklist *p=l->next;//p指向第一个节点
while(p->next) //p所指节点有后继
{
if(p->data==cur_e){
nex_e=p->next->data;
return 1;
}
p=p->next;
}
return 0;
}
//若cur_e是l的数据元素，且不是第一个，则用nex_e返回它的前驱，
//返回1，否则操作失败，pre_e无定义，返回0
//反转链表（对于实验书上没有的内容，需要加入的，请多增加注释说明）
void reverse(linklist *&l)
{
linklist *p,*q,*r;
q=NULL;
p=l->next;
while(p!=NULL)
{
r=p->next;
p->next=q;
q=p;
p=r;
}
l->next=q;

}
结 论
(结果及体会)

指导老师评 议

指导老师签名：
年 月 日