实验报告专用纸.docx
《实验报告专用纸.docx》由会员分享，可在线阅读，更多相关《实验报告专用纸.docx（41页珍藏版）》请在冰点文库上搜索。
实验报告专用纸
延安大学计算机学院实验报告专用纸
学号
12
姓名
陈世龙
班级
计科15-1
课程名称
数据结构
实验项目名称
线性表
任课教师
曹军梅
指导教师
曹军梅
实验组别
第组
同组者
教师评语及成绩：
实验成绩：
教师签字：
（请按照实验报告的有关要求书写，一般必须包括：
1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题及解决方法；6、实验结果、结果分析与体会等内容。
）
1、实验目的：
（1）、掌握线性表的基本运算；
（2）、掌握顺序存储的概念，学会对顺序存储结构进行操作；
（3）、加深对顺序存储数据结构的理解，解决实际问题。
2、实验内容：
（1）、线性表的顺序存储的基本操作；
（2）、线性表的链式存储的基本操作；
（3）、线性表的应用---一元多项式的表示及相加都基本操作。
3、实验步骤与方法：
（1）、采用线性表的链式存储结构；
（2）、用菜单的形式完成线性表链式存储结构的基本操作；
（3）、采用线性表的顺序存储结构；
（4）、用菜单的形式完成线性表顺序存储结构的基本操作；
（5）、运用线性表链式存储结构解决常见实际应用问题；
（6）、运用线性表顺序结构解决常见实际应用问题。
4、实验数据与程序清单：
实验一：
线性表中查找元素位置
#include
#include
#defineNULL0
#defineOVERFLOW-2
实验室：
机号：
实验日期：
年月日
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/
typedefstruct
{
ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/
intlast;/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/
}SeqList;
intLocate（SeqListL,ElemTypee）
{
inti=0;/*i为扫描计数器，初值为0，即从第一个元素开始比较*/
while（（i<=L.last）&&（L.elem[i]!
=e））
i++;
if（i<=L.last）
return（i+1）;/*若找到值为e的元素，则返回其序号*/
else
return（-1）;/*若没找到，则返回空序号*/
}
voidmain（）
{
SeqListl;
intp,q,r;
inti;
printf（"请输入线性表的长度:
"）;
scanf（"%d",&r）;
l.last=r-1;
printf（"请输入线性表的各元素值:
\n"）;
for（i=0;i<=l.last;i++）
{
scanf（"%d",&l.elem[i]）;
}
printf（"请输入要查找的元素值:
\n"）;
scanf（"%d",&q）;
p=Locate（l,q）;
if（p==-1）
printf（"在此线性表中没有该元素!
\n"）;
else
printf（"该元素在线性表中的位置为:
%d\n",p）;
}
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
实验二：
线性表中插入元素操作
#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/
typedefstruct
{
ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/
intlast;/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/
}SeqList;
intInsList（SeqList*L,inti,ElemTypee）
{
intk;
if（（i<1）||（i>L->last+2））/*首先判断插入位置是否合法*/
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
{
printf（"插入位置i值不合法"）;
return（ERROR）;
}
if（L->last>=MAXSIZE-1）
{
printf（"表已满无法插入"）;
return（ERROR）;
}
for（k=L->last;k>=i-1;k--）/*为插入元素而移动位置*/
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e;/*在C语言数组中，第i个元素的下标为i-1*/
L->last++;
return（OK）;
}
voidmain（）
{
SeqList*l;
intp,q,r;
inti;
l=（SeqList*）malloc（sizeof（SeqList））;
printf（"请输入线性表的长度:
"）;
scanf（"%d",&r）;
l->last=r-1;
printf（"请输入线性表的各元素值:
\n"）;
for（i=0;i<=l->last;i++）
{
scanf（"%d",&l->elem[i]）;
}
printf（"请输入要插入的位置:
\n"）;
scanf（"%d",&p）;
printf（"请输入要插入的元素值:
\n"）;
scanf（"%d",&q）;
InsList（l,p,q）;
for（i=0;i<=l->last;i++）
{
printf（"%d",l->elem[i]）;
}
}
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
实验三：
线性表中删除元素操作
#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/
typedefstruct
{
ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/
intlast;/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/
}SeqList;
intDelList（SeqList*L,inti,ElemType*e）
{
intk;
if（（i<1）||（i>L->last+1））
{
printf（"删除位置不合法!
"）;
return（ERROR）;
}
*e=L->elem[i-1];/*将删除的元素存放到e所指向的变量中*/
for（k=i;i<=L->last;k++）
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
L->elem[k-1]=L->elem[k];/*将后面的元素依次前移*/
L->last--;
return（OK）;
}
voidmain（）
{
SeqList*l;
intp,r;
int*q;
inti;
l=（SeqList*）malloc（sizeof（SeqList））;
q=（int*）malloc（sizeof（int））;
printf（"请输入线性表的长度:
"）;
scanf（"%d",&r）;
l->last=r-1;
printf（"请输入线性表的各元素值:
\n"）;
for（i=0;i<=l->last;i++）
{
scanf（"%d",&l->elem[i]）;
}
printf（"请输入要删除的元素位置:
\n"）;
scanf（"%d",&p）;
DelList（l,p,q）;
printf（"删除的元素值为:
%d\n",*q）;
}
实验四：
线性表的合并
#include
#include
#include
#defineOK1
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineElemTypeint
#defineMAXSIZE100/*此处的宏定义常量表示线性表可能达到的最大长度*/
typedefstruct
{
ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/
intlast;/*记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/
}SeqList;
voidmerge（SeqList*LA,SeqList*LB,SeqList*LC）
{
inti,j,k;
i=0;j=0;k=0;
while（i<=LA->last&&j<=LB->last）
if（LA->elem[i]<=LB->elem[j]）
{
LC->elem[k]=LA->elem[i];
i++;
k++;
}
else
{
LC->elem[k]=LB->elem[j];
j++;
k++;
}
while（i<=LA->last）/*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/
{
LC->elem[k]=LA->elem[i];
i++;
k++;
}
while（j<=LB->last）/*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/
{
LC->elem[k]=LB->elem[j];
j++;
k++;
}
LC->last=LA->last+LB->last+1;
}
voidmain（）
{
SeqList*la,*lb,*lc;
intr;
inti;
la=（SeqList*）malloc（sizeof（SeqList））;
printf（"请输入线性表A的长度:
"）;
scanf（"%d",&r）;
la->last=r-1;
printf（"请输入线性表A的各元素值:
\n"）;
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
for（i=0;i<=la->last;i++）
{
scanf（"%d",&la->elem[i]）;
}
lb=（SeqList*）malloc（sizeof（SeqList））;
printf（"请输入线性表B的长度:
"）;
scanf（"%d",&r）;
lb->last=r-1;
printf（"请输入线性表B的各元素值:
\n"）;
for（i=0;i<=lb->last;i++）
{
scanf（"%d",&lb->elem[i]）;
}
lc=（SeqList*）malloc（sizeof（SeqList））;
merge（la,lb,lc）;
printf（"合并后线性表C中的元素为:
\n"）;
for（i=0;i<=lc->last;i++）
{
printf（"%d",lc->elem[i]）;
}
}
实验五：
用头插法建立单链表
#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#include
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
#defineElemTypechar
typedefstructNode/*结点类型定义*/
{
ElemTypedata;
structNode*next;
}Node,*LinkList;/*LinkList为结构指针类型*/
LinkListCreateFromHead（）
{
LinkListL;
Node*s;
charc;
intflag=1;
L=（LinkList）malloc（sizeof（Node））;/*建立头结点*/
L->next=NULL;/*建立空的单链表L*/
while（flag）/*flag初值为1，当输入"$"时，置flag为0，建表结束*/
{
c=getchar（）;
if（c!
='$'）
{
s=（Node*）malloc（sizeof（Node））;/*建立新结点s*/
s->data=c;
s->next=L->next;/*将s结点插入表头*/
L->next=s;
}
else
flag=0;
}
returnL;
}
voidmain（）
{
LinkListl;
Node*p;
printf（"用头插法建立单链表,请输入链表数据,以$结束!
\n"）;
l=CreateFromHead（）;
p=l->next;
while（p!
=NULL）
{
printf（"%c\n",p->data）;
p=p->next;
}
}
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
实验六：
用尾插法建立单链表
#include
#include
#include
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefcharElemType;
typedefstructNode/*结点类型定义*/
{
ElemTypedata;
structNode*next;
}Node,*LinkList;/*LinkList为结构指针类型*/
voidinit_linklist（LinkList*l）/*对单链表进行初始化*/
{
*l=（LinkList）malloc（sizeof（Node））;
（*l）->next=NULL;
}
voidCreateFromTail（LinkListL）
{
Node*r,*s;
charc;
intflag=1;/*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while（flag）/*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar（）;
if（c!
='$'）
{
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
s=（Node*）malloc（sizeof（Node））;
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/
}
}
}
voidmain（）
{
LinkListl;
Node*p;
init_linklist（&l）;
printf（"用尾插法建立单链表,请输入链表数据,以$结束!
\n"）;
CreateFromTail（l）;
p=l->next;
while（p!
=NULL）
{
printf（"%c\n",p->data）;
p=p->next;
}
}
实验七：
查找线性表结点值
#include
#include
#include
#defineOK1
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefcharElemType;
typedefstructNode/*结点类型定义*/
{
ElemTypedata;
structNode*next;
}Node,*LinkList;/*LinkList为结构指针类型*/
voidinit_linklist（LinkList*l）/*对单链表进行初始化*/
{
*l=（LinkList）malloc（sizeof（Node））;
（*l）->next=NULL;
}
voidCreateFromTail（LinkListL）
{
Node*r,*s;
charc;
intflag=1;/*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while（flag）/*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar（）;
if（c!
='$'）
{
s=（Node*）malloc（sizeof（Node））;
s->data=c;
r->next=s;
r=s;
}
else
{
flag=0;
r->next=NULL;/*将最后一个结点的next链域置为空，表示链表的结束*/
}
}
}
Node*Get（LinkListL,inti）
{
intj;
Node*p;
p=L;
j=0;/*从头结点开始扫描*/
while（（p->next!
=NULL）&&（j{
p=p->next;/*扫描下一结点*/
j++;/*已扫描结点计数器*/
}
if（i==j）
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
returnp;/*找到了第i个结点*/
else
returnNULL;/*找不到，i≤0或i>n*/
}
voidmain（）
{
LinkListl;
Node*p;
intj;
init_linklist（&l）;
printf（"请输入链表数据,以$结束!
\n"）;
CreateFromTail（l）;
p=l->next;
while（p!
=NULL）
{
printf（"%c\n",p->data）;
p=p->next;
}
printf（"请输入要查找的结点序号:
\n"）;
scanf（"%d",&j）;
p=Get（l,j）;
if（p!
=NULL）
printf（"该结点的值为:
%c\n",p->data）;
else
printf（"未找到此结点!
\n"）;
}
实验八：
判断线性表长度
#include
#include
#include
延安大学计算机学院实验报告附页
学号
12
姓名
陈世龙
班级
计科15-1
实验名称
线性表
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
typedefcharElemType;
typedefstructNode/*结点类型定义*/
{
ElemTypedata;
structNode*next;
}Node,*LinkList;/*LinkList为结构指针类型*/
voidinit_linklist（LinkList*l）/*对单链表进行初始化*/
{
*l=（LinkList）malloc（sizeof（Node））;
（*l）->next=NULL;
}
voidCreateFromTail（LinkListL）
{
Node*r,*s;
charc;
intflag=1;/*设置一个标志，初值为1，当输入"$"时，flag为0，建表结束*/
r=L;/*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/
while（flag）/*循环输入表中元素值，将建立新结点s插入表尾*/
{
c=getchar（）;
if（c!
='$'）
{
升级会员 