数据结构实验报告Word格式.docx
- 文档编号:3685241
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:62
- 大小:210.98KB
数据结构实验报告Word格式.docx
《数据结构实验报告Word格式.docx》由会员分享,可在线阅读,更多相关《数据结构实验报告Word格式.docx(62页珍藏版)》请在冰点文库上搜索。
:
SeqList(inta[],intn)
if(n>
Max)throw"
参数非法"
;
for(inti=0;
i<
n;
i++)
{
data[i]=a[i];
length=n;
}
voidSeqList:
Insert(inti,intx)
if(length>
=Max)throw"
上溢"
if(i<
1||i>
length+1)throw"
位置非法"
else
for(intj=length;
j>
=i;
j--)
data[j]=data[j-1];
//第j个元素存在数组下标为j-1处
data[i-1]=x;
length++;
intSeqList:
Delete(inti)
if(length==0)throw"
下溢"
length)throw"
intx=data[i-1];
for(intj=i;
j<
length;
j++)
data[j-1]=data[j];
length--;
returnx;
Locate(intx)
if(data[i]==x)returni+1;
return0;
//遍历函数
PrintList()
cout<
<
data[i]<
"
endl;
//主函数
voidmain()
{//操作前遍历
intr[5]={1,2,3,4,5};
SeqListL(r,5);
执行操作前的数据为:
"
<
L.PrintList();
//插入数据
L.Insert(2,7);
'
\n'
插入位置2数字7后顺序表的内容为:
L.PrintList();
//删除数据
intk;
请输入需要删除的数据序号:
cin>
>
k;
删除成功!
你所删除的数据为:
L.Delete(k)<
顺序表的内容为:
//按值查找
inty;
请输入要查找的数据:
y;
你所查找的值所在的位置为:
L.Locate(y)<
}
四.运行与测试
1.2单链表的实现
一.实验目的
1.掌握线性表的链接存储结构;
2.验证单链表及其基本操作实现;
3.进一步理解算法与程序的关系,能够将单链表算法转换为对应的程序。
1.用头插法(或尾插法)建立带头结点的单链表;
2.对已建立的单链表实现插入、删除、查找等基本操作。
stdio.h>
stdlib.h>
string.h>
typedefintElemType;
typedefstructNode{
ElemTypedata;
structNode*next;
}Node;
voidinitList(Node**pNode){
*pNode=NULL;
Node*create(Node*pHead){
Node*p1;
Node*p2;
p1=p2=(Node*)malloc(sizeof(Node));
//申请内存空间
memset(p1,0,sizeof(Node));
//存入数据域清空
scanf("
%d"
&
p1->
data);
p1->
next=NULL;
while(p1->
data>
0){//输入负数结束
if(pHead==NULL)
pHead=p1;
else
p2->
next=p1;
p2=p1;
p1=(Node*)malloc(sizeof(Node));
}
returnpHead;
voidprintList(Node*pHead){
if(NULL==pHead)
printf("
链表为空\n"
);
else{
while(pHead!
=NULL){
%d"
pHead->
pHead=pHead->
next;
\n"
*Node**pNode传入头结点空间地址
*inti传入要插入的结点位置
*/
voidinsert_data(Node**pNode,inti){
Node*temp;
Node*target;
Node*p;
intitem;
intj=1;
输入要插入的节点值:
item);
target=*pNode;
for(;
j<
i-1;
target=target->
next,++j);
//不断移动target位置,到要插入结点位置,
temp=(Node*)malloc(sizeof(Node));
temp->
data=item;
//存入要存入的数据位置
p=target->
target->
next=temp;
next=p;
voiddelete_data(Node**pNode,inti){
temp=target->
next=temp->
free(temp);
/*===============查找结点====================*/
intsearch_data(Node*pNode,intelem){
inti=1;
for(target=pNode;
target->
data!
=elem&
&
next!
=NULL;
++i,target=target->
next);
if(target->
next==NULL)
returni;
intmain(){
inti;
Node*pHead=NULL;
initList(&
pHead);
pHead=create(pHead);
printList(pHead);
输入插入节点位置\n"
i);
insert_data(&
pHead,i);
输入删除节点位置\n"
delete_data(&
输入查找节点\n"
节点所在位置:
search_data(pHead,i));
五.总结
通过这几节课的学习我对顺序表和单链表的认识又更深了。
实验课上我也认真的做实验了,但是效果还是不咋样。
仍然有许多东西不会,对顺序表的操作不熟练,很多实现不了。
数据结构有很强的逻辑性,因此我认为如果在上机之前先把逻辑搞清楚很重要,不管是对算法的设计还是对程序的调试都有很大帮助。
经过一次上机实践,我认为实践课很重要,上理论课只是纸上谈兵,只是被动地接受,而实践课上能将学过的知识利用起来,同时还有一些东西只能是自己上机实践才能慢慢探索出的。
学习数据结构就要多想,多写代码,多练习。
2.实验二栈和队列
2.1顺序栈的实现
1.掌握栈的顺序存储结构;
2.验证顺序栈及其基本操作实现;
3.验证栈的操作特性。
1.建立一个空栈;
2.对已建立的栈进行插入、删除、取栈顶元素等基本操作。
#defineSIZE100//基础容量
#definedtSIZE10//附加容量(可多次扩容)
structSqStack
int*top;
//栈顶指针
int*base;
//栈底指针
intsize;
//栈的当前容量
voidInit(SqStack&
s)//初始化栈
s.base=(int*)malloc(SIZE*sizeof(int));
//s.base=newint[SIZE];
//使用new不能追加空间
if(!
s.base)exit(-1);
//内存分配失败
s.top=s.base;
s.size=SIZE;
intPush(SqStack&
s,inte)//把元素e压入栈顶
if(s.top-s.base>
s.size)//栈满,追加dtSIZE大小的空间
s.base=(int*)realloc(s.base,(s.size+dtSIZE)*sizeof(int));
s.base)exit(-2);
s.size=s.size+dtSIZE;
*s.top=e;
//把e赋给栈顶
s.top++;
//栈顶指针+1
return1;
intPop(SqStack&
s,int&
e)//取出栈顶元素,并删除栈顶
if(s.top==s.base)//top与base重合时,栈为空
s.top--;
//top先减1,再取元素
e=*s.top;
intIsEmpty(SqStacks)//判空
if(s.top==s.base)
voidDestroy(SqStack&
s)//销毁栈
free(s.base);
//deletes.base;
//如果使用new分配内存,则用delete删除。
intmain()
SqStackslist;
Init(slist);
cout<
输入一串数字,(以非数字结束):
endl;
inte;
while(cin>
e)
Push(slist,e);
//将读取的数字压入栈顶
while(!
IsEmpty(slist))//栈不为空时
Pop(slist,e);
//取出栈顶元素,并删除栈顶
e<
Destroy(slist);
2.2链队列的实现
1.掌握队列的链接存储结构;
2.验证链队列的存储结构和基本操作的实现;
3.验证队列的操作特性。
1.建立一个空队列;
2.对已建立的队列进行插入、删除、取队头元素等基本操作。
1.代码如下
string>
#defineQUEUELEN10
structDATA{
stringname;
intage;
structSQType
{
DATAdata[QUEUELEN];
//队列数组
inthead;
//队头
inttail;
//队尾
SQType*SQTypeInit()
SQType*q;
if(q=newSQType)//申请队列的内存空间
{
q->
head=0;
//设置队首
tail=0;
//设置队尾
returnq;
returnNULL;
//返回空
intSQTypeIsEmpty(SQType*q)
return(q->
head==q->
tail);
intSQTypeIsFull(SQType*q)
tail==QUEUELEN);
voidSQTypeClear(SQType*q)
voidSQTypeFree(SQType*q)
if(q!
=NULL)deleteq;
intInSQType(SQType*q,DATAdata)
if(q->
tail==QUEUELEN)
队列已满!
操作失败!
}else
data[q->
tail++]=data;
//将元素入队列
DATA*OutSQType(SQType*q)
tail==q->
head)
return&
(q->
head++]);
DATA*PeekSQType(SQType*q)
if(SQTypeIsEmpty(q))
空队列"
head]);
intSQTypeLen(SQType*q)
tail-q->
head);
intmain()
SQType*stack;
DATAdata,*p;
stack=SQTypeInit();
//执行初始化操作
执行入队列操作:
输入姓名,年龄进行入队操作:
while
(1)
cin>
data.name>
data.age;
if(data.age==0)
break;
//若输入为0,则退出
InSQType(stack,data);
进行出栈操作:
p=OutSQType(stack);
p->
name<
"
age<
读取首结点数据:
p=PeekSQType(stack);
执行出栈操作:
if(SQTypeIsEmpty(stack))
所有数据出栈完毕"
SQTypeFree(stack);
在这次实验课上,我遇到了很多问题,比如不知道栈的操作,不知道如何取栈顶元素,但是经过了问同学,请教老师最后我还是解决了这个问题。
在学习上每个人都会遇到很多问题,只要我们不放弃,最终会被解决的。
通过这一次的实验,我不仅实现了栈和队列的算法,还解决了上次作业遗留下来的问题。
通过XX,我知道了“?
:
”操作符是需要返回值的,所以问号后面的和冒号后面的都是需要一个表达式,而不是一个完整的语句。
那么top==NULL?
return1:
return0;
语句就应该改为return(top==-1)?
1:
0;
语句,程序才得以运行成功。
当然,除了这一种方法以外,还可以使用ifelse语句。
虽然是同过搜索的,但是只要你能掌握,用什么方法都是可以的。
3.实验三树和二叉树
3.1二叉树的实现
1.掌握二叉树的逻辑结构;
2.掌握二叉树的二叉链表存储结构;
3.验证二叉树的二叉链表存储及遍历操作。
1.建立一棵含有n个结点的二叉树,采用二叉链表存储;
2.输出前序、中序和后序遍历该二叉树的遍历结果。
1.代码如下:
typedefstructnode*tree_pointer;
structnode{
charch;
tree_pointerleft_child,right_child;
tree_pointerroot=NULL;
tree_pointercreate(tree_pointerptr)
scanf("
%c"
ch);
if(ch=='
)
ptr=NULL;
else{
ptr=(tree_pointer)malloc(sizeof(node));
ptr->
ch=ch;
left_child=create(ptr->
left_child);
right_child=create(ptr->
right_child);
returnptr;
voidpreorder(tree_pointerptr)
if(ptr){
printf("
ptr->
preorder(ptr->
voidinorder(tree_pointerptr)
inorder(ptr->
voidpostorder(tree_pointerptr)
postorder(ptr->
voidmain()
构建一个二叉树(结点数为n):
root=create(root);
前序遍历二叉树:
preorder(root);
中序遍历二叉树:
inorder(root);
后序遍历二叉树:
postorder(root);
3.2树的实现
1.掌握树的逻辑结构;
2.掌握树的孩子兄弟存储结构;
3.验证树的孩子兄弟存储结构及遍历操作。
1.采用孩子兄弟表示法建立一棵树;
2.基于树的孩子兄弟表示法实现前序和后序遍历树的操作。
#include<
stddef.h>
#defineOK1
#defineERROR0
#defineFALSE0
#defineTRUE1
#defineOVERFLOW-2
typedefintStatus;
typedefcharElemType;
//结点的值设置为字符
typedefstructCSNode
structCSNod
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告