数据结构实验1.docx
- 文档编号:10165100
- 上传时间:2023-05-24
- 格式:DOCX
- 页数:17
- 大小:98.09KB
数据结构实验1.docx
《数据结构实验1.docx》由会员分享,可在线阅读,更多相关《数据结构实验1.docx(17页珍藏版)》请在冰点文库上搜索。
数据结构实验1
数据结构《实验1》实验报告
实验项目1:
线性表存储及运算
学 号
1309030322
姓 名
曹思远
课程号
实验地点
指导教师
时间
评语:
按时完成实验;实验内容和过程记录完整;回答问题完整、正确;实验报告的撰写认真、格式符合要求;无抄袭的行为。
成绩
教师签字
线性表链式存储(双向链表)插入、删除运算
1、预习要求:
线性表的插入、删除相关概念及运算,完成线性表元素的插入、删除。
2、实验目的:
(1)了解线性表的插入、删除相关概念;
(2)理解线性表的插入、删除过程和结构定义;
(3)掌握算法转换为程序的过程中的变化。
3、实验内容及要求:
(1)分别建立包含10个数据元素的链式存储线性表;
(2)从键盘输入一个数据元素,插入到线性表中第k(包含0号位置)个位置;
(3)从键盘输入一个数据元素关键字或位置k(包含1号位置),从线性表中删除相应数据元素;
(4)给出程序及插入、删除前和插入、删除后线性表结果。
4、实验设备(环境)及要求
硬件:
支持IntelPentiumⅡ及其以上CPU,内存128MB以上、硬盘1GB以上容量的微机。
软件:
配有Windows98/2000/XP操作系统,安装VisualC++。
5、实验时间:
6学时
6、该文档的文件名不要修改,存入<学号><姓名>命名的文件夹中
7、该表中的数据只需填空,已有内容不要修改
实验结果(运行结果界面及源程序,运行结果界面放在前面):
#defineSTUDENTEType
//#defineboolStatus
#defineHeadETypeint
#include
#include
#include
#include
usingnamespacestd;
//以下是数据类型的定义
enumStatus{OK,ERROR};
typedefstruct
{
charnumber[10];
charname[10];
charsex[4];
charage[4];
charplace[20];
}STUDENT;
structDoubleNode
{
ETypedata;
DoubleNode*plink;
DoubleNode*nlink;
};
structHeadNode
{
HeadETypeHdata;
DoubleNode*first;
};
typedefHeadNode*DoubleChainList;
voidCreat(DoubleChainList&L)
{//构造一个空链表
L=newHeadNode;
L->first=NULL;
//L->Hdata="HeadNode的数据值";
}
voidOutput(DoubleChainList&L)
{//逐个地输出链表L中的数据元素
DoubleNode*current=L->first;
while(current)
{
cout< current=current->nlink; } } intLength(DoubleChainList&L) {//返回链表L中数据元素结点数 DoubleNode*current=L->first; intlen=0; while(current) { len++; current=current->nlink; } returnlen; } voidDestroy(DoubleChainList&L) {//删除链表L中所有数据结点,并释放结点空间 DoubleNode*current; current=L->first; while(L->first) { current=current->nlink; deleteL->first; L->first=current; } } boolGetElem(DoubleChainList&L,intk,EType&x) {//L中第k个元素取至x中,如不存在返回false,找到返回true,x带回 if(k<1)returnfalse; DoubleNode*current=L->first; intindex=1; while(index { current=current->nlink; index++; } if(current) { x=current->data; returntrue; } returnfalse; } /*DoubleNode*Search(DoubleChainList&L,EType&x) {//查找x,如果找到返回x所在的地址;如果未找到返回NULL DoubleNode*current=L->first; while(current&¤t->data! =x) current=current->nlink; if(current)returncurrent; returnNULL; }*/ boolInsetDoubleNodeChainList(DoubleChainList&L,intk,EType&x) {//在链表L中第k个数据元素之后中插入元素x运算 //如果不存在第k个元素或线性表空间已满,则返回出错状态码 if(k<0)returnfalse; intindex=1; DoubleNode*current=L->first; while(index {//找第k个节点 index++; current=current->nlink; } if(k>0&&! current)returnfalse; DoubleNode*q=newDoubleNode; q->data=x; if(k) {q->nlink=current->nlink; q->plink=current; DoubleNode*p=current->nlink; if(p) p->plink=q; current->nlink=q; } else { q->nlink=L->first; q->plink=NULL; DoubleNode*p=L->first; if(p) p->plink=q; L->first=q; } returntrue; } boolDeleteDoubleNodeChainList(DoubleChainList&L,intk) {//在线性表L中删除第k个数据元素,如果不存在第k个元素返回出错状态码 if(k<1||! L->first)returnfalse; DoubleNode*current=L->first; DoubleNode*p; if(k==1)//删除的是链表中的第一个节点 { p=current->nlink; if(p) p->plink=NULL; L->first=p; } else { DoubleNode*q=L->first; for(intindex=1;index q=q->nlink; if(! q)returnfalse; current=q;//current指向第k个节点 q=current->plink; p=current->nlink; q->nlink=p; if(p) p->plink=q; } deletecurrent;//释放被删除节点current的空间 returntrue; } //下面是主程序 intmain() { DoubleNode*p; DoubleNode*q; DoubleChainListL; intchoice,n; //*****构造链表**************************** Creat(L); //*****链表初始化************************** charn1[][11]={"","001001","001002","001003","001004","001005","001006","001007","001008","001009","001010"}; charn2[][11]={"","吴仁耀","朱慧菲","杜子腾","梅杰超","魏生芷","庞光大","雷仁","李超凡","王林","夏琉"}; charn3[][11]={"","男","女","男","男","女","男","男","男","男","男"}; charn4[][11]={"","18","19","17","19","18","22","21","19","19","21"}; charn5[][11]={"","诺克萨斯","艾欧尼亚","征服之海","影流","皮城","守望之海","祖安","班德尔城","德玛西亚","花果山"}; for(intk=1;k<11;k++) { p=newDoubleNode; strcpy(p->data.number,n1[k]);//cout< strcpy(p->data.name,n2[k]);//cout< strcpy(p->data.sex,n3[k]);//cout< strcpy(p->data.age,n4[k]);//cout< strcpy(p->data.place,n5[k]);//cout< if(k! =1) { p->plink=q; q->nlink=p; } else { p->plink=NULL; L->first=p; } q=p; } //q->nlink=L->first; p->nlink=NULL; while(true) { cout<<"************************线性表顺序存储的运算***********************"< cout<<"*1--------输出双向链表中的所有元素*"< cout<<"*2--------在双向链表中查找第K个元素*"< cout<<"*3--------在双向链表中查找符合查找关键字x(地址)的元素*"< cout<<"*4--------在双向链表中插入新元素到第k个元素后面*"< cout<<"*5--------在双向链表中删除第k个元素*"< cout<<"*0--------退出*"< cout<<"********************************************************************"< cout<<"请选择处理功能: ";cin>>choice; cout< //system("cls"); switch(choice){ case1: {//输出所有元素 cout<<"*******************输出双向链表中的所有元素***********************"< cout< Output(L); cout< break; } case2: {//******查找第K个结点********************* intk=1; ETypex; cout<<"输入查找第K个记录的K值: ";cin>>k; if(GetElem(L,k,x)) { cout<<"第"< } else cout<<"K值范围不正确! "< break; } /*case3: {//*******查找给定关键字对应的结点********************* charx[8]; cout<<"输入查找关键字x的值: ";cin>>x; k=Search(L,x); cout< cout<<"*****查找结果如下: "< if()//搁置 }*/ case4: { ETypex; //********插入X结点到第K个结点后面********************* cout<<"************在线性表中插入新元素到第k个元素后面***********"< cout<<"此操作前线性表状态: "< Output(L); cout< cout<<"插入第几个后面? ";cin>>n; //cout< cout<<"输入要插入的元素的各值: "< strcpy(x.number,"10086"); strcpy(x.name,"哎呀妈呀"); strcpy(x.sex,"男"); strcpy(x.age,"99"); strcpy(x.place,"天王星"); cout<<"学号: "< cout<<"姓名: "< cout<<"性别: "< cout<<"年龄: "< cout<<"住址: "< if(InsetDoubleNodeChainList(L,n,x)) { cout<<"插入元素到第"< "< Output(L); cout< } else cout<<"@@@@@找不到插入点,K值范围不对! @@@@@"< break; } case5: { //*****删除第K个结点******************** cout<<"*****************在现行表中删除第k个元素******************"< cout<<"此操作前线性表状态: "< Output(L); cout< cout<<"删除第几个节点? ";cin>>n; if(DeleteDoubleNodeChainList(L,n)) { cout<<"删除后的结果是: "< Output(L); } else { cout<<"您输入的数字有错误! "< } break; } //*****将第K个结点移至第1个结点位置***** //k=9;//cin>>k; //cout< "< //if(MoveFirst(L,k)==ERROR) //cout<<"K值不存在! "< //else //Output(L); //*****将链表逆向***** //cout< "< //Invert(L); //Output(L); //*****删除链表中所有结点************************** cout< "< Destroy(L); Output(L); deleteL; return0; } } }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验