山东大学数据结构第一次实验实验报告.docx
《山东大学数据结构第一次实验实验报告.docx》由会员分享，可在线阅读，更多相关《山东大学数据结构第一次实验实验报告.docx（12页珍藏版）》请在冰点文库上搜索。
山东大学数据结构第一次实验实验报告
山东大学数据结构第一次实验实验报告
实验1ADT表的编程与实现
C语言，是一种通用的、过程式的编程语言，广泛用于系统与应用软件的开发。
具有高效、灵活、功能丰富、表达力强和较高的可移植性等特点，在程序员中备受青睐。
MicrosoftVisualC++是Microsoft公司推出的开发Win32环境程序具有集成开发环境，可提供编辑C语言，C++以及C++/CLI语言等可视化集成编程系统。
它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点，而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2，WinSock网络、3D控制界面。
本课程实验要求学生运用C语言编程完成数据结构课程中抽象数据类型及排序算法的编程实现，加深对教学内容的理解。
实验目的：
加深对抽象数据类型ADT表的理解；
实验原理：
参照课本p.44-49，及Figure3.6-3.13.
实验内容：
编写程序实现ADT表的定义，及常用操作：
1）判断表是否为空；
2）获取第i个节点的内容
3）删除
4）插入
实验要求：
1）复习C语言相关知识；
2）实现完整的ADT表结构及操作，并给出应用。
实验源程序：
#include"stdafx.h"
#include"stdio.h"
#include"stdlib.h"
#include"malloc.h"
typedefstructnode
{
intdata;
structnode*pNext;//pNext为指向下一个节点的指针
}Node,*pNode;
pNodeCreateLinkList（）;//创建链表函数
boolIsEmpty（pNode）;//定义IsEmpty（pNode）为布尔值，判断链表是否为空
intFindTheNode（pNodepHead,inta,intlength）;//找出某一个节点的值
voidTraverseLinkList（pNodepHead）;//遍历链表，获取链表中的数值
intGetLengthLinklist（pNodepHead）;//获取链表长度
intDelete（pNodepHead,intx）;//删除元素
intInsert（pNodepHead,intb,intc）;//插入元素
voidFreeLinkList（pNodepHead）;//释放链表空间
////////////////////////////////////////////////////////////////////////////////
intmain（）//主函数
{inta,b,c,x,length;
pNodepHead=NULL;//初始化头节点pHead为NULL
pHead=CreateLinkList（）;//创建一个非循环单链表，并将该链表的头结点的地址赋给pHead
if（IsEmpty（pHead））//判断链表是否为空
{
printf（"链表为空！
\n"）;
return0;
pNew->data=a;
pTail->pNext=pNew;//pTail中的指针pNext指向pNew
pNew->pNext=NULL;
pTail=pNew;//新建的节点变为链尾
}
returnpHead;
}
////////////////////////////////////////////////////////////////////////////////
boolIsEmpty（pNodepHead）//判断列表是否为空
{
returnpHead->pNext==NULL;
}
/////////////////////////////////////////////////////////////////////////////////
intFindTheNode（pNodepHead,inta,intlength）//找出某一个节点的值
{
if（a>length）//判断要查找的节点位置是否正确
{printf（"链表中没有此节点\n"）;
return0;
}
else
{pNodep=pHead->pNext;
for（inti=0;i{
if（i==a-1）
{
printf（"第%d个节点的内容是:
%d",a,p->data）;}//当找到该节点时输出它的值
p=p->pNext;
}
printf（"\n"）;
return1;
}}
///////////////////////////////////////////////////////////////////////////
voidTraverseLinkList（pNodepHead）//遍历链表，获取链表中的数值
{
printf（"链表中各节点的值依次为：
"）;
pNodep=pHead->pNext;
while（p!
=NULL）//知道最后一个节点循环才停止
{printf（"%d",p->data）;
p=p->pNext;
}
printf（"\n"）;
}
///////////////////////////////////////////////////////////////////////////////
intGetLengthLinklist（pNodepHead）//获取链表长度
{
intlength=0;
pNodep=pHead->pNext;
while（p!
=NULL）
{length++;
p=p->pNext;
}
returnlength;
}
////////////////////////////////////////////////////////////////////////////////
intDelete（pNodepHead,intx）//删除元素
{
pNodep,q;
q=p=pHead;
p=p->pNext;//p指向头结点后第一个元素
while（p）
{
if（p->data==x）//找到要删除的元素
{
q->pNext=p->pNext;
free（p）;//释放该元素所在节点的空间
return1;
}
else
{q=p;//q始终指向p上一个节点
p=p->pNext;
}}
return0;
}
///////////////////////////////////////////////////////////////////////////
intInsert（pNodepHead,intb,intc）//插入元素
{
pNodep,q;
q=p=pHead;
p=p->pNext;
if（b>0&&b{
for（inti=1;b>i;i++）
{
q=p;//q始终指向p上一个节点
p=p->pNext;
}
pNodepNew=（pNode）malloc（sizeof（Node））;//创建新节点并动态分配内存
pNew->data=c;
pNew->pNext=p;
q->pNext=pNew;
return1;
}
elsereturn0;
}
////////////////////////////////////////////////////////////////////////////
voidFreeLinkList（pNodepHead）//释放链表空间
{pNodep,q;
p=pHead->pNext;
while（p!
=NULL）
{q=p->pNext;
free（p）;//释放各节点的空间
p=q;}
pHead->pNext=NULL;
}
实验结果：
1）判断表是否为空
①创建链表，链表不为空。
②链表为空。
2）获取第i个节点的内容
①输入要求获取的节点内容的位置正确，比如i=2，则得到第2个节点的内容为22。
②输入要求获取的节点内容的位置不在链表中，比如i=8，则显示链表中没有此节点。
③若输入节点位置不在链表中，则需继续输入正确位置，不然系统会一直要求输入
节点i的值直到我们输入正确的节点位置。
3）删除
①输入要删除的元素在链表中，比如删除元素44，则链表中剩下的元素有11、
22、33、55、66.
②若输入要删除的元素不在链表中，比如要删除元素77，则显示未找到该元素，
删除失败。
③若输入要删除的元素不在链表中，则需继续输入在链表中的元素，不然系统会
一直要求输入要删除的元素。
4）插入
①输入要插入的位置正确，比如插入到位置1中，则在位置1插入元素0后
链表中各节点的数值依次为0、11、22、33、55、66。
②若输入要插入的位置不正确，比如插入到位置8中，则显示未找到该
位置，插入失败。
③若输入要插入的位置不正确，则需继续输入正确的位置，不然系统会
一直要求输入正确的位置和要插入的节点的数值。
升级会员 