数据结构上机报告单链表的建立和运算.docx
《数据结构上机报告单链表的建立和运算.docx》由会员分享，可在线阅读，更多相关《数据结构上机报告单链表的建立和运算.docx（33页珍藏版）》请在冰点文库上搜索。
数据结构上机报告单链表的建立和运算
《数据结构》上机报告
_2011_年_3_月_9_日
姓名_____学号__同组成员___无___
1.实验题目及要求
编写一个程序，实现单链表的各种基本运算
2.需求分析
建立一个单链表，实现单链表的初始化，插入、删除节点等功能，以及确定某一元素在单链表中的位置。
（1）初始化单链表；
（2）依次采用尾插入法插入a,b,c,d,e元素；
（3）输出单链表L；
（4）输出单链表L的长度；
（5）判断单链表L是否为空；
（6）输出单链表L的第三个元素；
（7）输出元素a的位置；
（8）在第4个元素位置上插入f元素；
（9）输出单链表L；
（10）删除L的第3个元素；
（11）输出单链表L；
（12）释放单链表。
3.概要设计
（1）为了实现上述程序功能，需要定义一个简化的线性表抽象数据类型：
ADTLinearList{
数据对象：
D={ai|ai∈IntegerSet,i=0,1,2,…,n,n≥0}
结构关系：
R={|ai,ai+1∈D}
基本操作：
InitList_L（L）
操作前提：
L是一个未初始化的线性表
操作结果：
将L初始化为一个空的线性表
CreateList_L（L）
操作前提：
L是一个已初始化的空表
操作结果：
建立一个非空的线性表L
ListInsert_L（L,pos,e）
操作前提：
线性表L已存在
操作结果：
将元素e插入到线性表L的pos位置
ListDelete_L（L,pos,e）
操作前提：
线性表L已存在
操作结果：
将线性表L中pos位置的元素删除，
删除的元素值通过e返回
LocateList_L（L,e）
操作前提：
线性表L已存在
操作结果：
在线性表L中查找元素e，
若存在，返回元素在表中的序号位置；
若不存在，返回-1
DestroyList_L（&L）
初始条件：
线性表L已存在
操作结果：
销毁线性表
ListEmpty_L（L）
初始条件：
线性表已存在
操作结果：
若L为空表，则返回ERROR，否则返回FALSE
ListLength_L（L）
初始条件：
线性表L已存在
操作结果：
返回L中数据元素个数
GetElem_L（L,I,&e）
初始条件：
线性表L已存在
操作结果：
用e返回L中第i个数据元素值
}
（2）本程序包含10个函数：
•主函数main（）
•初始化单链表函数InitList_L（）
•显示单链表内容函数DispList_L（）
•插入元素函数ListInsert_L（）
•删除元素函数ListDelete_L（）
•查找元素函数LocateList_L（）
•创建链表函数CreateList_L（）
•链表元素长度函数ListLength_L（）
•判断链表是否为空函数ListEmpty_L（）
•取值函数GetElem_L（）
各函数间调用关系如下：
（3）主函数的伪码
main（）
{说明一个单链表L；
初始化L；
建立L；
显示L；
}
4.详细设计
采用单链表实现概要设计中定义的抽象数据类型，有关的数据类型和伪码算法定义如下：
（1）类型定义
typedefintElemType;
typedefstructLNode
{ElemTypedata;//数据域
structLNode*next;//指针域
}LNode,*LinkList;
（2）基本操作的伪码算法
●初始化
BoolInitLinkList（LinkList*L）
{*L=申请新结点;
如果申请失败，返回失败标志；
（*L）->next=NULL;
返回成功标志；
}
●建立单链表
BoolCrtLinkList（LinkListL）
/*L是已经初始化好的空链表的头指针，通过键盘输入元素值，
利用尾插法建单链表L*/
{rear=L;
打印输入提示：
“请输入若干个正整数（用空格分隔），并用-1结束：
”
读入一个数x;
当x不是结束标志时，循环做如下处理：
{
申请一个新结点s；
如果申请失败，返回失败标志；
将x送到s的data域;
rear->next=s;
rear=s;
读入下一个数x;
}
rear->next=NULL;
返回成功标志；
}
●显示单链表（输出）
voidDispLinkList（LinkListL）
{
p=首元素结点地址;
while（p不空）
{
打印结点p的元素值；
p=下一个结点地址;
}
}
●插入操作
boolInsLinkList（LinkListL,intpos,ElemTypee）
/*在带头结点的单链表L中第pos个位置插入值为e的新结点s*/
{
从“头”开始，查找第i-1个结点pre;
if（查找失败）
{显示参数错误信息;
returnERROR;
}
else
{
申请一个新的结点s;
将e放入s的数据域;
将s插到pre后面;
returnOK;
}
}
●删除操作
boolDelLinkList（LinkListL,intpos,ElemType*e）
/*在带头结点的单链表L中删除第pos个元素，并将删除的元素保存到变量*e中*/
{
查找待删除结点i的前驱结点，并用pre指向它;
if（查找失败）
{显示参数错误信息;
returnERROR;
}
else
{
r=pre->next;
修改指针，删除结点r;
释放被删除的结点所占的内存空间;
returnOK;
}
}
●查找操作
intLocLinkList（LinkListL,ElemTypee）
/*在带头结点的单链表L中查找其结点值等于e的结点，
若找到则返回该结点的序号位置k，否则返回-1*/
{
p=首元素结点地址;
while（p不空）
if（p->data!
=e）
{p=p->next;k++;}
elsebreak;
if（p不空）returnk;
elsereturn-1;
}
5.调试分析
开始运行时会出现DebugError，DAMAGE:
AfterNormalblock，搜索后了解到是内存越界操作，检查后发现内存分配L和S=（LinkList）malloc（sizeof（LNode））写成了=（LinkList）malloc（sizeof（LinkList）），修改后正常。
6.使用说明
程序执行后，界面直接输出要求的结果
7.测试结果
8.附件
#include
#include
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineNULL0
typedefintStatus;
typedefintElemType;
typedefstructLNode{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
StatusInitList_L（LinkList&L）{//初始化线性表
L=（LinkList）malloc（sizeof（LNode））;//L指向头节点，头节点数据域为空
L->next=NULL;
returnOK;
}//InitList_L
StatusDispList_L（LinkList&L）{//输出线性表
LinkListp=L->next;
while（p!
=NULL）
{
printf（"%c",p->data）;
p=p->next;
}
returnOK;
}//DispList_L
StatusCreateList_L（LinkList&L,ElemTypea[],intn）{//尾插法建表
LinkLists,r;inti;
L=（LinkList）malloc（sizeof（LNode））;
r=L;
for（i=0;i{
s=（LinkList）malloc（sizeof（LNode））;
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
returnOK;
}//CreateList_L
StatusListLength_L（LinkListL）{//求线性表的长度
LinkListp=L;intn=0;
while（p->next!
=NULL）
{
n++;
p=p->next;
}
return（n）;
}//ListLength_L
StatusListEmpty_L（LinkListL）{//判断单链表是否为空
return（L->next==NULL）;
}//ListEmpty_L
StatusDestroyList_L（LinkList&L）{//销毁线性表
LinkListp=L,q=p->next;
while（q!
=NULL）
{
free（p）;
p=q;
q=p->next;
}
free（p）;
returnOK;
}//DestroyList_L
StatusGetElem_L（LinkListL,inti,ElemType&e）{
//L为带头节点的单链表的头指针。
//当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
intj=0;
LinkListp=L;
while（j=NULL）
{
j++;p=p->next;
}
if（p==NULL）
{
returnERROR;
}
else
{
e=p->data;
returnOK;
}
}//GetElem_L
StatusListInsert_L（LinkList&L,inti,ElemTypee）{//插入数据元素
intj=0;
LinkListp=L,s;
/*
找到插入节点的上一个元素，如果是头节点则退出，当i=1时表示头节点，i=2时，表示第一个元素
*/
while（j=NULL）
{
j++;
p=p->next;
}
if（p==NULL）
{
returnERROR;
}
else
{
s=（LinkList）malloc（sizeof（LNode））;
s->data=e;
s->next=p->next;
p->next=s;
returnOK;
}
}//ListInsret_L
StatusListDelete_L（LinkList&L,inti,ElemType&e）{//删除数据元素
intj=0;
LinkListp=L,q;
while（j=NULL）//查找删除元素的前一个节点
{
j++;
p=p->next;
}
if（p==NULL）
{
returnERROR;
}
else
{
q=p->next;//q为要删除的元素节点
if（q==NULL）
{
returnERROR;
}
e=q->data;//e为删除节点的数据区域
p->next=q->next;
free（q）;
returnOK;
}
}//ListDelete_L
intLocateElem_L（LinkListL,ElemTypee）{//按元素值查找元素
LinkListp=L->next;
inti=1;
while（p!
=NULL&&p->data!
=e）
{
p=p->next;i++;
}
//如果要插入的节点为头节点，则退出
if（p==NULL）
{
returnERROR;
}
else
{
return（i）;
}
}//LocateElem_L
intmain（）{
ElemTypee,a[5]={'a','b','c','d','e'};
LinkListL;
printf（"
（1）初始化单链表L\n"）;
InitList_L（L）;//初始化单链表L
printf（"
（2）依次采用尾插法插入a,b,c,d,e元素\n"）;
CreateList_L（L,&a[0],5）;//依次采用尾插入法插入a，b，c，d，e元素
printf（"（3）输出单链表L：
"）;
DispList_L（L）;//输出单链表L
printf（"\n"）;
printf（"（4）单链表L的长度为：
"）;
printf（"%d",ListLength_L（L））;//输出单链表L的长度
printf（"\n"）;
if（ListEmpty_L（L））
{
printf（"（5）该单链表为空\n"）;
}
else
{
printf（"（5）该单链表不为空\n"）;//判断单链表L是否为空
}
GetElem_L（L,3,e）;
printf（"（6）单链表L的第三个元素为：
"）;
printf（"%c",e）;printf（"\n"）;//输出单链表L的第3个元素
printf（"（7）单链表L中a的位置为：
"）;
printf（"%d",LocateElem_L（L,'a'））;//输出元素'a'的位置
printf（"\n"）;
ListInsert_L（L,4,'f'）;//在第4个元素位置插入'f'元素
printf（"（8）在第4个元素位置上插入f元素\n"）;
printf（"（9）输出单链表L：
"）;
DispList_L（L）;//输出单链表L
printf（"\n"）;
ListDelete_L（L,3,e）;//删除L的第3个元素
printf（"（10）删除L的第3个元素\n"）;
printf（"（11）输出单链表L:
"）;//输出单链表L
DispList_L（L）;
printf（"\n"）;
printf（"（12）释放单链表L\n"）;
DestroyList_L（L）;//释放单链表L
return0;
}
#include"stdio.h"
structlinklist1
{
intxh;
structlinklist1*next;
};
structlinklist2
{
intgrade;
structlinklist2*next;
};
structconlink
{
intxh;
intgrade;
structconlink*next;
};
structlinklist1*creat1（）
/**创建单链表a**/
{
inti;
structlinklist1*head,*p,*q;
head=（structlinklist1*）malloc（sizeof（structlinklist1））;
p=q=head;
printf（"pleaseinput5xh:
\n"）;
for（i=0;i<5;i++）
{p=（structlinklist1*）malloc（sizeof（structlinklist1））;
scanf（"%d",&（p->xh））;
p->next=0;
q->next=p;
q=p;
}
returnhead;
}
structlinklist2*creat2（）
/**创建单链表b**/
{inti;
structlinklist2*head,*p,*q;
head=（structlinklist2*）malloc（sizeof（structlinklist2））;
p=q=head;
printf（"pleaseinput5grade:
\n"）;
for（i=0;i<5;i++）
{p=（structlinklist2*）malloc（sizeof（structlinklist2））;
scanf（"%d",&（p->grade））;
p->next=0;
q->next=p;
q=p;
}
returnhead;
}
scann（structlinklist1*a,structlinklist2*b,structlinklist1**p,structlinklist2
**q）
/**查找单链表中学号最大的结点，存入*p,对应的成绩存入*q**/
{
structlinklist1*m=a->next;
printf（"scan（）...\n"）;
while（a->next&&b->next）
{
a=a->next;
b=b->next;
if（a->xh>=m->xh）
{
*p=a;
*q=b;
printf（"xh=%dgrade=%d\n",（*p）->xh,（*q）->grade）;
getch（）;
}
}
}
conlink（structconlink*head,structlinklist1*p,structlinklist2*q）
/**用头插法建立单链表c**/
{
structconlink*a;
printf（"conlink（）...\n"）;
a=（structconlink*）malloc（sizeof（structconlink））;
a->xh=p->xh;
a->grade=q->grade;
a->next=head->next;
head->next=a;
}
outlist1（structlinklist1*head,structlinklist1*p）
/**删除a单链表中学号最大的结点（最大的结点用scan函数已经找出）**/
{
while（head->next&&head->next!
=p）
head=head->next;
head->next=p->next;
free（p）;
}
outlist2（structlinklist2*head,structlinklist2*q）
/**删除b单链表中对应的结点**/
{
while（head->next&&head->next!
=q）
head=head->next;
head->next=q->next;
free（q）;
}
output（structconlink*head）
/**输出c链表**/
{
while（head->next!
=0）
{
printf（"%d%d\n",head->next->xh,head->next->grade）;
head=head->next;
}
}
main（）
{
structlinklist1*a;
structlinklist2*b;
structlinklist1*p;
structlinklist2*q;
structconlink*head;
a=creat1（）;
b=creat2（）;
head=（structconlink*）malloc（sizeof（structconlink））;
head->next=0;
while（a->next!
=0）
{
scan（a,b,&p,&q）;
conlink（head,p,q）;
outlist1（a,p）;
outlist2（b,q）;
}
output（head）;
getch（）;
}
#include
#include
#defineMAXSIZE100
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineOVERFLOW-2
#defineNULL0
typedefstructLNode
{
intdata;
structLNode*next;
}*Link,*Position;
typedefstruct
{
Linkhead,tail;
intlen;
}LinkList;
intMakeNode（Link&p,inte）
{
//分配由p指向的值为e的结点,并返回OK;若分配失败,则返回ERROR
if（!
（p=（Link）malloc（sizeof（Link））））returnERROR;
p->data=e;
p->next=NULL;
returnOK;
}
voidFreeNode（Link&p）
{
//释放p所指的结点
free（p）;
p=NULL;
}
intInitList（LinkList&L）
{
//构造一个空的线性链表L
Linkp;
p=（Link）malloc（sizeof（LNode））;
if（!
p）return（OVERFLOW）;
p->next=NULL;
L.tail=L.head=p;
L.len=0;
returnOK;
}
intClearList（LinkList&L）
{
//将线性链表L重置为空表,并释放原链表的结点空间
if（!
L.len）returnERROR;
Linkp,q;
q=L.head->next;
p=q;
L.head->next=NULL;
while（p!
=L.tail）
{
p=q->next;
FreeNode（q）;
q=p;
}
//FreeNode（q）;
L.tail=L.head;
L.len=0;
returnOK;
}
int
升级会员 