数据结构试验.docx
- 文档编号:17916669
- 上传时间:2023-08-04
- 格式:DOCX
- 页数:57
- 大小:41.39KB
数据结构试验.docx
《数据结构试验.docx》由会员分享,可在线阅读,更多相关《数据结构试验.docx(57页珍藏版)》请在冰点文库上搜索。
数据结构试验
数据结构上机实验指导
编写人时巍
职业技术学院2009年
上机训练一线性表的插入删除操作
一、实验目的
1.通过实验进一步掌握线性表的基本概念和存储方式。
2.掌握不同存储方式下线性表基本操作的实现,完成程序的编写和调试工作。
二、实验内容
1.线性表顺序存储结构的定义。
2.线性表顺序存储结构的插入、删除操作。
3.线性表链式存储结构结点定义。
4.线性表链式存储结构的基本操作。
三、代码编写及调试结果
1.线性表的顺序存储结构
(1)顺序表插入操作参考程序(前插)
#include
#defineMAXLEN100/*MAXLEN要大于实际线性表的长度*/
typedefintelementtype;/*根据需要,elementtype也可以定义为其它任何类型*/
typedefstruct/*定义线性表*/
{
elementtypes[MAXLEN];/*定义线性表中元素,MAXLEN为线性表的最大容量*/
intlen;/*定义线性表的表长*/
}SqList;
intinsertsqlist(inti,elementtypex,SqList*sql)
{/*在顺序表(*sql)的第i个元素之前插入一个新元素x*/
intj;
if((i<1)||(i>sql->len))/*i值非法,返回值为0*/
return(0);
else
{
for(j=sql->len;j>=i;j--)
sql->s[j+1]=sql->s[j];/*向后移动数据,腾出要插入的空位*/
sql->s[j+1]=x;/*修正插入位置为j+1,将新元素插入到s[j+1]位置*/
(sql->len)++;/*表长加1*/
return
(1);/*插入成功,返回值为1*/
}
}
main()/*主程序*/
{
intb=9,c,k;
elementtyped=9;
SqLista={0,1,2,3,4,5,6,7,8};/*赋线性表各元素初值,为与前概念描述一致,a.s[0]闲置不用*/
a.len=8;/*赋线性表长度值*/
for(k=1;k<=a.len;k++)
{
printf("%3d",a.s[k]);/*输出插入前结果*/
}
printf("\n");
c=insertsqlist(b,d,&a);/*调用插入函数*/
if(c==0)
printf("error");
else
{
for(k=1;k<=a.len;k++)
printf("%3d",a.s[k]);/*输出插入后结果*/
}
printf("\n");
}
程序运行后结果:
12345678
129345678
(2)顺序表删除操作参考程序
#include
#defineMAXLEN100/*MAXLEN要大于实际线性表的长度*/
typedefintelementtype;/*根据需要,elementtype也可以定义为其它任何类型*/
typedefstruct/*定义线性表*/
{
elementtypes[MAXLEN];/*定义线性表中元素,MAXLEN为线性表的最大容量*/
intlen;/*定义线性表的表长*/
}SqList;
intdelsqlist(inti,SqList*sql)/*删除顺序表(*sql)的第i个元素*/
{
intj;
if((i<1)||(i>sql->len))/*i值非法,返回值为0*/
return(0);
else
{
for(j=i+1;j<=sql->len;j++)
sql->s[j-1]=sql->s[j];/*向前移动数据,覆盖前一数据*/
(sql->len)--;/*表长度减1*/
return
(1);/*删除成功,返回值为1*/
}
}
main()/*主程序*/
{
intb=4,c,k;
SqLista={0,1,2,3,4,5,6,7,8};/*赋线性表各元素初值,为与前概念描述一致,a.s[0]闲置不用*/
a.len=8;/*赋线性表长度值*/
for(k=1;k<=a.len;k++)
{
printf("%3d",a.s[k]);/*输出删除前结果*/
}
printf("\n");
c=delsqlist(b,&a);/*调用删除函数*/
if(c==0)
printf("error\n");
else
{
for(k=1;k<=a.len;k++)
printf("%3d",a.s[k]);/*输出删除后结果*/
}
printf("\n");
}
程序运行后结果:
12345678
1235678
2.线性表的链式存储结构单链表
(1)创建单链表
typedefstructnode
{
intdata;
structnode*next;
}NODE;
NODE*create()/*此函数采用后插入方式建立单链表*/
{NODE*head,*q,*p;/*定义指针变量*/
charch;
inta;
head=(NODE*)malloc(sizeof(NODE));
/*申请新的存储空间,建立表头结点*/
q=head;
ch='*';
printf("\nInputthelist:
");
while(ch!
='?
')
/*"ch"为是否建立新结点的标志,若"ch"为"?
"则输入结束*/
{scanf("%d",&a);/*输入新元素*/
p=(NODE*)malloc(sizeof(NODE));
p->data=a;
q->next=p;
q=p;
ch=getchar();/*读入输入与否的标志*/
}
q->next=NULL;
return(head);/*返回表头指针head*/
}
(2)单链表上的插入运算参考程序
voidinsert(NODE*p,intx)/*在链表的p结点后插入给定元素x*/
{
NODE*q;
q=(NODE*)malloc(sizeof(NODE));/*申请新的存储空间*/
q->data=x;
q->next=p->next;
p->next=q;/*将新结点q链接到p结点之后*/
}
main()/*主程序*/
{
intx,position;/*x为将插入的元素,position为插入位置的序号*/
inti=0,j=0;
NODE*c,*d;
c=create();/*建立单向链表*/
d=c->next;
while(d!
=NULL)/*统计单向链表中结点数,置j中*/
{
d=d->next;
j++;
}
d=c;
do
{
printf("Inputposition(again):
");
scanf("%d",&position);/*position可为0,表示表头结点*/
}while((position>j)||position<0);/*position值超过单向链表结点数,重新输入*/
printf("Inputx:
");
scanf("%d",&x);
while(i!
=position)/*由position值确定其在单向链表中的位置d*/
{
d=d->next;
i++;
}
insert(d,x);
printf("Outputthelist:
");
while(c->next!
=NULL)/*输出插入x后的单向链表各元素*/
{
c=c->next;
printf("%5d",c->data);
}
printf("ok");
}
程序运行结果:
Inputnumberofthelist:
5(回车)
Inputthelist:
56789(回车)
Inputposition:
3(回车)
Inputx:
33(回车)
Outputthelist:
5673389ok
(3)单链表上的删除运算参考程序
voiddelete(NODE*head,intx)/*删除链表中的给定元素x*/
{NODE*p,*q;
q=head;
p=q->next;
while((p!
=NULL)&&(p->data!
=x))/*查找要删除的元素*/
{q=p;
p=p->next;
}
if(p==NULL)
printf("%dnotfound.\n",x);/*x结点未找到*/
else
{q->next=p->next;/*链接x直接后继结点*/
free(p);/*删除x结点,释放x结点空间*/
}
}
main()/*主程序*/
{
intx;
NODE*a,*b;
a=create();
printf("Inputx:
");
scanf("%5d",&x);
delete(a,x);
b=a;
b=b->next;
printf("Outputthelist:
");
while(b!
=NULL)
{
printf("%5d",b->data);/*输出删除x后的单向链表*/
b=b->next;
}
}
程序第一次运行结果(删除成功):
Inputnumberofthelist:
5(回车)
Inputthelist:
12345(回车)
Inputx:
4(回车)
Outputthelist:
1235
程序第二次运行结果(删除元素未找到):
Inputnumberofthelist:
5(回车)
Inputthelist:
12345(回车)
Inputx:
6(回车)
6notfound
Outputthelist:
12345
四、实验习题
1.将前面顺序表的插入算法改成“后插”的算法,即在顺序表的第i个元素的后面插入新元素。
2.设计一个算法,从顺序表中删除自第i个元素开始的k个结点。
3.设计一个算法,将顺序表中所有数据元素为x的结点替换成数据元素y。
4.设计一个算法,产生一个有四个结点的单链表,这些结点的数据域分别是a,b,c,d,且表头指针是head。
5.设计一个算法,将结点数据域依次是a1,a2……an(n>3)的一个单链表的所有结点逆置,即第一个几点的数据域变为an,最后一个结点的数据域变为a1。
上机训练二栈的基本操作
一、实验目的
1.通过实验进一步掌握栈的基本概念和存储方式。
2.掌握不同存储方式下栈基本操作的实现,完成程序的编写和调试工作。
二、实验内容
1.栈顺序存储结构的定义及初始化操作。
2.栈顺序存储结构的取栈顶元素、入栈、出栈、判断栈空等基本操作。
3.栈链式存储结构的结点定义。
4.栈链式存储结构的基本操作。
三、代码编写及调试结果
1.顺序栈的基本操作
#include
#defineMAXLEN10
typedefintelementtype;
typedefstruct/*栈的顺序存储结构定义*/
{
elementtypeelement[MAXLEN];/*存放栈元素的数组*/
inttop;/*栈指针*/
}SqStack;
SqStackInitStack_sq()/*建立一个空栈s*/
{
SqStacks;
s.top=-1;
return(s);
}
intGetTop_sq(SqStack*s,elementtype*x)/*取栈顶元素,若栈s非空,用*x返回栈顶元素*/
{
if(s->top==-1)
return(0);/*栈空返回0*/
else
{
*x=s->element[s->top];
return
(1);
}
}
intPush_sq(SqStack*s,elementtypex)/*进栈操作,若栈s未满,将元素x进栈*/
{
if(s->top==MAXLEN-1)
return(0);/*栈满返回0*/
s->top++;
s->element[s->top]=x;
return
(1);
}
intPop_sq(SqStack*s,elementtype*x)/*出栈操作,若栈s非空,删除s的栈顶元素,并用*x返回栈顶元素*/
{
if(s->top==-1)
return(0);/*栈空返回0*/
*x=s->element[s->top];
s->top--;
return
(1);
}
intEmpty_sq(SqStack*s)/*判断栈s是否为空,空则返回1,非空返回0*/
{
return(s->top==-1);
}
voidprint(SqStacks)/*输出栈元素*/
{
inti;
if(s.top!
=-1)/*栈非空,输出栈元素*/
{
printf("Outputelementsofstack:
");
for(i=0;i<=s.top;i++)
printf("%d",s.element[i]);
}
else
printf("Thestackisempty!
!
!
");
printf("\n");
}
main()/*主程序*/
{
SqStackstack;
inti;
elementtypey;
elementtypez;
stack=InitStack_sq();/*建立空栈stack*/
if(Empty_sq(&stack)!
=0)/*判断栈stack是否为空*/
printf("\nThestackisempty!
");
else
printf("\nThestackisnotempty!
");
printf("\nPush5elementstostack:
");
for(i=1;i<=5;i++)/*入栈5个元素*/
{
scanf("%d",&y);
Push_sq(&stack,y);
}
print(stack);/*入栈5个元素后输出栈元素*/
GetTop_sq(&stack,&z);/*取栈顶元素,送z*/
printf("Elementoftopis:
%d\n",z);/*输出栈顶元素z*/
printf("Pop3elementsfromstack:
");
for(i=1;i<=3;i++)/*出栈3个元素*/
{
Pop_sq(&stack,&z);
printf("%d",z);/*按出栈次序输出栈元素*/
}
printf("\n");
print(stack);/*出栈3个元素后输出栈元素*/
if(Empty_sq(&stack)!
=0)/*判断栈stack是否为空*/
printf("Thestackisempty!
\n");
else
printf("Thestackisnotempty!
\n");
printf("Pop2elementsfromstack:
");
for(i=1;i<=2;i++)/*出栈2个元素*/
{
Pop_sq(&stack,&z);
printf("%d",z);/*按出栈次序输出栈元素*/
}
printf("\n");
print(stack);/*出栈2个元素后输出栈元素*/
if(Empty_sq(&stack)!
=0)/*判断栈stack是否为空*/
printf("Thestackisempty!
\n");
else
printf("Thestackisnotempty!
\n");
}
程序运行结果:
Thestackisempty!
Push5elementstostack:
12345(回车)
Outputelementsofstack:
12345
Elementoftopis:
5
Pop3elementsfromstack:
543
Outputelementsofstack:
12
Thestackisnotempty!
Pop2elementsfromstack:
21
Thestackisempty!
!
!
Thestackisempty!
2.链栈的基本操作
#include
typedefstructnode/*定义链栈结点*/
{
intdata;/*这里以整型数据为例*/
structnode*next;/*指针类型,存放下一个结点地址*/
}NODE;
NODE*crea_linkstack()/*建立链栈*/
{
NODE*top,*p;/*定义栈顶指针top*/
inta,n;
top=NULL;
printf("\nInputnumberofpushlinkstack:
");
scanf("%d",&n);/*入链栈的元素个数*/
if(n>0)/*若n<=0,建立空栈*/
{
printf("Input%delementsofpushlinkstack:
",n);
while(n>0)
{
scanf("%d",&a);/*输入新元素*/
p=(NODE*)malloc(sizeof(NODE));
p->data=a;
p->next=top;
top=p;
n--;
}
}
return(top);/*返回栈顶指针*/
}
NODE*pushstack(NODE*top,intx)/*进栈操作*/
{
NODE*p;
p=(NODE*)malloc(sizeof(NODE));
p->data=x;/*将要插入的数据x存储到结点p的数据域中*/
p->next=top;/*将p插入链表头部,即链栈顶部*/
top=p;
return(top);
}
voidprint(NODE*top)/*输出链栈中各元素*/
{
NODE*p;
p=top;
if(p!
=NULL)
{
printf("Outputthelinkstack:
");
while(p!
=NULL)
{
printf("%3d",p->data);
p=p->next;
}
}
else
printf("\nThestackisempty!
!
!
");
}
NODE*popstack(NODE*top,int*p)
{
NODE*q;/*定义q结点*/
if(top!
=NULL)/*如果栈不空*/
{
q=top;
*p=top->data;/*将栈顶元素放入*p中*/
top=top->next;/*修改top指针*/
free(q);/*释放原栈顶空间*/
}
return(top);/*返回栈顶指针*/
}
main()/*主程序*/
{
inty;/*将入栈的元素*/
NODE*a;
a=crea_linkstack();/*建立链栈*/
print(a);/*输出整个链栈*/
printf("\nPushaelementtolinkstack:
");
scanf("%d",&y);/*输入进栈元素y*/
a=pushstack(a,y);/*y进栈*/
print(a);/*输出整个链栈*/
a=popstack(a,&y);/*出栈一个元素到y*/
printf("\nOutputtheelementofpoplinkstack:
%d\n",y);
print(a);/*输出整个链栈*/
}
程序运行结果:
Inputnumberofpushlinkstack:
5(回车)
Input5elementsofpushlinkstack:
12345(回车)
Outputthelinkstack:
54321
Pushaelementtolinkstack:
6(回车)
Outputthelinkstack:
654321
Outputtheelementofpoplinkstack:
6
Outputthelinkstack:
54321
五、实验习题
1.设有一组数据1,2,3,4,5,6,7,8,9为整数。
利用这些数据完成下列操作:
(1)初始化顺序栈
(2)将9个数据入栈
(3)将9,8,7,6出栈
(4)判断栈是否为空。
2.将题1中的存储结构改为链栈,重新编写算法。
上机训练三队列的基本操作
一、实验目的
1.通过实验进一步掌握队列的基本概念和存储方式。
2.掌握不同存储方式下队列基本操作的实现,完成程序的编写和调试工作。
二、实验内容
1.队列存储结构的定义及初始化操作。
2.队列顺序存储结构的入队、出队操作。
3.循环队列的判队空、队满操作。
4.队列链式存储结构的入队、出队操作。
三、代码编写及调试结果
1.队列顺序存储结构基本操作
#include
#defineMAXLEN10
typedefintelementtype;
typedefstruct/*队列的顺序存储结构定义*/
{
elementtypeelement[MAXLEN];/*存放队列元素的数组*/
intfront,rear;/*队列头、尾指针*/
}SeQueue;
SeQueueInitQueue_sq()/*建立一个空队列q*/
{
SeQueueq;
q.front=-1;
q.rear=-1;
return(q);
}
intGetFront_sq(SeQueue*q,elementtype
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 试验