《大数据结构》C语言版严蔚敏著实验指导文档格式.docx
《《大数据结构》C语言版严蔚敏著实验指导文档格式.docx》由会员分享,可在线阅读,更多相关《《大数据结构》C语言版严蔚敏著实验指导文档格式.docx(63页珍藏版)》请在冰点文库上搜索。
运行结果:
2、调试程序:
对一维数组中的元素进行逆序排列。
#defineN10
intmain(){
inta[N]={0,1,2,3,4,5,6,7,8,9},i,temp;
\ntheoriginalArrayis:
\n"
for(i=0;
N;
printf("
a[i]);
N/2;
i++){/*交换数组元素使之逆序*/
temp=a[i];
a[i]=a[N-i-1];
a[N-i-1]=temp;
}
\nthechangedArrayis:
3、调试程序:
在二维数组中,若某一位置上的元素在该行中最大,而在该列中最小,则该元素即为该二维数组的一个鞍点。
要求从键盘上输入一个二维数组,当鞍点存在时,把鞍点找出来。
#defineM3
#defineN4
inta[M][N],i,j,k;
\n请输入二维数组的数据:
M;
for(j=0;
j<
j++)
scanf("
%d"
&
a[i][j]);
i++){/*输出矩阵*/
printf("
a[i][j]);
i++){
k=0;
for(j=1;
j++)/*找出第i行的最大值*/
if(a[i][j]>
a[i][k])
k=j;
j++)/*判断第i行的最大值是否为该列的最小值*/
if(a[j][k]<
break;
if(j==M)/*在第i行找到鞍点*/
%d,%d,%d\n"
a[i][k],i,k);
4、调试程序:
利用指针输出二维数组的元素。
inta[3][4]={1,3,5,7,9,11,13,15,17,19,21,23};
int*p;
for(p=a[0];
p<
a[0]+12;
p++){
if((p-a[0])%4==0)printf("
*p);
5、调试程序:
设有一个教师与学生通用的表格,教师的数据有、年龄、职业、教研室四项,学生有、年龄、专业、班级四项,编程输入人员的数据,再以表格输出。
#include<
structstudent{
charname[8];
/**/
intage;
/*年龄*/
charjob;
/*职业或专业,用s或t表示学生或教师*/
union{
intclass;
/*班级*/
charoffice[10];
/*教研室*/
}depa;
}stu[N];
intn;
printf(“\n请输入人员数(<
10):
\n”);
scanf(“%d”,&
n);
n;
i++){/*输入n个人员的信息*/
\n请输入第%d人员的信息:
(nameagejobclass/office)\n"
i+1);
scanf("
%s,%d,%c"
stu[i].name,&
stu[i].age,&
stu[i].job);
if(stu[i].job==’s’)
stu[i].depa.class);
else
scanf("
%s"
stu[i].depa.office);
printf(“nameagejobclass/office”);
i++){/*输出*/
%s%3d%3c%d\n"
stu[i].name,stu[i].age,stu[i].job,stu[i].depa.class);
%s%3d%3c%s\n"
stu[i].name,stu[i].age,stu[i].job,stu[i].depa.office);
输入的数据:
2
Wang19s99061
Li36tcomputer
四、实验小结
五、教师评语
实验一顺序表与链表
1、掌握线性表中元素的前驱、后续的概念。
2、掌握顺序表与链表的建立、插入元素、删除表中某元素的算法。
3、对线性表相应算法的时间复杂度进行分析。
4、理解顺序表、链表数据结构的特点(优缺点)。
说明以下概念
1、线性表:
2、顺序表:
3、链表:
1、阅读下面程序,在横线处填写函数的基本功能。
并运行程序,写出结果。
malloc.h>
#defineERROR0
#defineOK1
#defineINIT_SIZE5/*初始分配的顺序表长度*/
#defineINCREM5/*溢出时,顺序表长度的增量*/
typedefintElemType;
/*定义表元素的类型*/
typedefstructSqlist{
ElemType*slist;
/*存储空间的基地址*/
intlength;
/*顺序表的当前长度*/
intlistsize;
/*当前分配的存储空间*/
}Sqlist;
intInitList_sq(Sqlist*L);
/**/
intCreateList_sq(Sqlist*L,intn);
intListInsert_sq(Sqlist*L,inti,ElemTypee);
/**/
intPrintList_sq(Sqlist*L);
/*输出顺序表的元素*/
intListDelete_sq(Sqlist*L,inti);
/*删除第i个元素*/
intListLocate(Sqlist*L,ElemTypee);
/*查找值为e的元素*/
intInitList_sq(Sqlist*L){
L->
slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));
if(!
L->
slist)returnERROR;
length=0;
listsize=INIT_SIZE;
returnOK;
}/*InitList*/
intCreateList_sq(Sqlist*L,intn){
ElemTypee;
inputdata%d"
e);
ListInsert_sq(L,i+1,e))
returnERROR;
}/*CreateList*/
/*输出顺序表中的元素*/
intPrintList_sq(Sqlist*L){
for(i=1;
=L->
length;
%5d"
L->
slist[i-1]);
}/*PrintList*/
intListInsert_sq(Sqlist*L,inti,ElemTypee){
intk;
if(i<
1||i>
length+1)
returnERROR;
if(L->
length>
listsize){
slist=(ElemType*)realloc(L->
slist,
(INIT_SIZE+INCREM)*sizeof(ElemType));
slist)
listsize+=INCREM;
for(k=L->
length-1;
k>
=i-1;
k--){
slist[k+1]=L->
slist[k];
slist[i-1]=e;
length++;
}/*ListInsert*/
/*在顺序表中删除第i个元素*/
intListDelete_sq(Sqlist*L,inti){
/*在顺序表中查找指定值元素,返回其序号*/
intListLocate(Sqlist*L,ElemTypee){
Sqlistsl;
intn,m,k;
pleaseinputn:
"
/*输入顺序表的元素个数*/
if(n>
0){
\n1-CreateSqlist:
InitList_sq(&
sl);
CreateList_sq(&
sl,n);
\n2-PrintSqlist:
PrintList_sq(&
\npleaseinputinsertlocationanddata:
(location,data)\n"
%d,%d"
m,&
k);
ListInsert_sq(&
sl,m,k);
\n3-PrintSqlist:
PrintList_sq(&
}
ERROR"
●运行结果
●算法分析
2、为第1题补充删除和查找功能函数,并在主函数中补充代码验证算法的正确性。
删除算法代码:
查找算法代码:
3、阅读下面程序,在横线处填写函数的基本功能。
/*定义表元素的类型*/
typedefstructLNode{/*线性表的单链表存储*/
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
LinkListCreateList(intn);
voidPrintList(LinkListL);
/*输出带头结点单链表的所有元素*/
intGetElem(LinkListL,inti,ElemType*e);
LinkListCreateList(intn){
LNode*p,*q,*head;
head=(LinkList)malloc(sizeof(LNode));
head->
next=NULL;
p=head;
q=(LinkList)malloc(sizeof(LNode));
inputdata%i:
q->
data);
/*输入元素值*/
q->
/*结点指针域置空*/
p->
next=q;
/*新结点连在表末尾*/
p=q;
returnhead;
voidPrintList(LinkListL){
LNode*p;
p=L->
next;
/*p指向单链表的第1个元素*/
while(p!
=NULL){
p->
p=p->
intGetElem(LinkListL,inti,ElemType*e){
intj=1;
while(p&
&
i){
j++;
p||j>
i)
*e=p->
data;
returnOK;
}/*GetElem*/
intn,i;
ElemTypee;
LinkListL=NULL;
/*定义指向单链表的指针*/
/*输入单链表的元素个数*/
\n1-CreateLinkList:
L=CreateList(n);
\n2-PrintLinkList:
PrintList(L);
\n3-GetElemfromLinkList:
inputi="
i);
if(GetElem(L,i,&
e))
No%iis%d"
i,e);
notexists"
}else
4、为第3题补充插入功能函数和删除功能函数。
并在主函数中补充代码验证算法的正确性。
插入算法代码:
以下为选做实验:
5、循环链表的应用(约瑟夫回环问题)
n个数据元素构成一个环,从环中任意位置开始计数,计到m将该元素从表中取出,重复上述过程,直至表中只剩下一个元素。
提示:
用一个无头结点的循环单链表来实现n个元素的存储。
●算法代码
6、设一带头结点的单链表,设计算法将表中值相同的元素仅保留一个结点。
指针p从链表的第一个元素开始,利用指针q从指针p位置开始向后搜索整个链表,删除与之值相同的元素;
指针p继续指向下一个元素,开始下一轮的删除,直至p==null为至,既完成了对整个链表元素的删除相同值。
实验二栈和队列
1、掌握栈的结构特性及其入栈,出栈操作;
2、掌握队列的结构特性及其入队、出队的操作,掌握循环队列的特点及其操作。
1、顺序栈:
2、链栈:
3、循环队列:
4、链队
1、阅读下面程序,将函数Push和函数Pop补充完整。
要求输入元素序列12345e,运行结果如下所示。
#defineSTACK_INT_SIZE10/*存储空间初始分配量*/
#defineSTACKINCREMENT5/*存储空间分配增量*/
/*定义元素的类型*/
typedefstruct{
ElemType*base;
ElemType*top;
intstacksize;
/*当前已分配的存储空间*/
}SqStack;
intInitStack(SqStack*S);
/*构造空栈*/
intpush(SqStack*S,ElemTypee);
/*入栈*/
intPop(SqStack*S,ElemType*e);
/*出栈*/
intCreateStack(SqStack*S);
/*创建栈*/
voidPrintStack(SqStack*S);
/*出栈并输出栈中元素*/
intInitStack(SqStack*S){
S->
base=(ElemType*)malloc(STACK_INT_SIZE*sizeof(ElemType));
S->
base)returnERROR;
top=S->
base;
stacksize=STACK_INT_SIZE;
}/*InitStack*/
intPush(SqStack*S,ElemTypee){
}/*Push*/
intPop(SqStack*S,ElemType*e){
}/*Pop*/
intCreateStack(SqStack*S){
inte;
if(InitStack(S))
InitSuccess!
else{
InitFail!
inputdata:
(Terminatedbyinputingacharacter)\n"
while(scanf("
e))
Push(S,e);
}/*CreateStack*/
voidPrintStack(SqStack*S){
while(Pop(S,&
%3d"
e);
}/*Pop_and_Print*/
SqStackss;
\n1-createStack\n"
CreateStack(&
ss);
\n2-Pop&
Print\n"
PrintStack(&
}
●算法分析:
输入元素序列12345,为什么输出序列为54321?
体现了栈的什么特性?
2、在第1题的程序中,编写一个十进制转换为二进制的数制转换算法函数(要求利用栈来实现),并验证其正确性。
●实现代码
●验证
3、阅读并运行程序,并分析程序功能。
string.h>
#defineM20
#defineelemtypechar
typedefstruct
{
elemtypestack[M];
inttop;
stacknode;
voidinit(stacknode*st);
voidpush(stacknode*st,elemtypex);
voidpop(stacknode*st);
voidinit(stacknode*st)
st->
top=0;
voidpush(stacknode*st,elemtypex)
if(st->
top==M)
thestackisoverflow!
{
top=st->
top+1;
stack[st->
top]=x;
voidpop(stacknode*st)
if(st->
top>
0)st->
top--;
elseprintf(“StackisEmpty!
intmain()
chars[M];
stacknode*sp;
createaemptystack!
sp=malloc(sizeof(stacknode));
init(sp);
inputaexpression:
gets(s);
strlen(s);
if(s[i]=='
('
)
push(sp,s[i]);
)'
pop(sp);
if(sp->
top==0)
'
match'
!
notmatch'
●输入:
2+((c-d)*6-(f-7)*a)/6
●运行结果:
a-((c-d)*6-(s/3-x)/2
●程序的基本功能:
4、设计算法,将一个表达式转换为后缀表达式,并按照后缀表达式进行计算,得出表达式得结果。
5、假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾结点(不设队头指针),试编写相应的置空队列、入队列、出队列的