114130168 宋国俊 数据结构.docx
- 文档编号:14249002
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:17
- 大小:184.15KB
114130168 宋国俊 数据结构.docx
《114130168 宋国俊 数据结构.docx》由会员分享,可在线阅读,更多相关《114130168 宋国俊 数据结构.docx(17页珍藏版)》请在冰点文库上搜索。
114130168宋国俊数据结构
本科学生实验报告
姓名宋国俊学号114130168
专业_地理信息系统班级地信11
实验课程名称数据结构
实验名称数据结构
指导教师及职称何礼平
开课学期2013至2014学年上学期
云南师范大学旅游与地理科学学院编印
实验名称:
1.线性表
2.二叉树的遍历
3.最短路径
4.栈的运用
5.排序与查找
实验时间:
2013年12月
1、实验目的和要求:
能够熟练应用计算机来操作,和对数据结构的熟悉
2、实验材料及相关设备:
Turboc计算机
3、实验过程;
1,线性表
程序设计如下
#include
typedefstruct
{
int*elem;
intlength;
intlistsize;
}SqList;
InitL(SqList*L)
{
L->elem=(int*)malloc(100*sizeof(int));
if(!
L->elem)exit(-2);
L->length=0;
L->listsize=100;
return1;
}
DataIn(SqList*L)
{
inti=0,x;
scanf("%d",&x);
while(x!
=-999)
{
L->elem[i]=x;
i++;
scanf("%d",&x);
}
L->length=i;
}
DataOut(SqList*L)
{
inti;
printf("\n");
for(i=0;i
printf("%4d",L->elem[i]);
}
ListIns(SqList*L,inti,inte)
{
int*q,*p;
if(i<0||i>L->length)return0;
q=&(L->elem[i]);
for(p=&(L->elem[L->length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
++L->length;
}
ListD(SqList*L,inti,int*e)
{
int*q,*p;
if(i<0||i>L->length)return0;
p=&(L->elem[i]);
*e=*p;
q=L->elem+L->length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L->length;
return1;
}
main()
{
inte;
SqListL;
InitL(&L);
DataIn(&L);
DataOut(&L);
ListIns(&L,2,333);
DataOut(&L);
ListD(&L,4,&e);
DataOut(&L);
printf("\n%d",e);
}
运行后的结果为
2.二叉树的遍历
程序如下
#include
#defineM40
typedefstructbtnode{
chardata;
structbtnode*lchild,*rchild;
}BtNode;
BtNode*p[M+1];
BtNode*Creat_Bt(void){/*建立二叉树*/
inti,j;charch;
BtNode*s,*t;
scanf("%d%c",&i,&ch);
while(i!
=0&&ch!
='#')
{
s=(BtNode*)malloc(sizeof(BtNode));
s->data=ch;
s->lchild=s->rchild=NULL;
p[i]=s;
if(i==1)t=s;
else{
j=i/2;
if(i%2==0)p[j]->lchild=s;
elsep[j]->rchild=s;
}
scanf("%d%c",&i,&ch);
}
returnt;
}
voidPreorder(BtNode*bt)/*先根遍历*/
{
if(bt!
=0)
{
printf("%c",bt->data);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
voidInorder(BtNode*bt)/*中根遍历*/
{
if(bt!
=0)
{
Inorder(bt->lchild);
printf("%c",bt->data);
Inorder(bt->rchild);
}
}
voidPostorder(BtNode*bt)/*后根遍历*/
{
if(bt!
=0)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
printf("%c",bt->data);
}
}
main()
{
BtNode*bt;
bt=Creat_Bt();
Preorder(bt);
printf("\n");
Inorder(bt);
printf("\n");
Postorder(bt);
}
3,最短路径
程序设计如下
#include
#include
#defineM7
#defineTRUE1
#defineFALSE0
#defineINFINITY999
voiddatain(inta[M][M]);
voiddataout(inta[M][M]);
voidDIJ(intarcs[M][M],intv0,intP[M][M],intD[M]);
main()
{
inta[M][M],P[M][M],D[M],i;
datain(a);
dataout(a);
printf("\n\n");
DIJ(a,0,P,D);
dataout(P);
printf("\n\n");
for(i=0;i printf("%6d",D[i]); } voidDIJ(intarcs[M][M],intv0,intP[M][M],intD[M]) { intv,w,i,j,min; intfinal[M]; for(v=0;v { final[v]=FALSE;D[v]=arcs[v0][v]; for(w=0;w if(D[v] } D[v0]=0;final[v0]=TRUE; for(i=1;i { min=INFINITY; for(w=0;w if(! final[w]) if(D[w] final[v]=TRUE; for(w=0;w if(! final[w]&&(min+arcs[v][w] { D[w]=min+arcs[v][w]; for(j=0;j } } } voiddatain(inta[M][M]) { FILE*fp; inti,j; fp=fopen("lujing.txt","r"); for(i=0;i for(j=0;j fscanf(fp,"%d",&a[i][j]); fclose(fp); } voiddataout(inta[M][M]) { inti,j; for(i=0;i { printf("\n"); for(j=0;j printf("%6d",a[i][j]); } }_ 4.栈的运用 程序设计如下 #defineM100 typedefstruct { intelem[M]; inttop; }SqStack; voidinit(SqStack*s) { s->top=0; } intempty(SqStack*s) {return(s->top);} intpush(SqStack*s,intx) { if(s->top==M)return0; s->elem[s->top]=x; s->top++; return1; } intpop(SqStack*s,int*y) { if(s->top==0)return0; --s->top;*y=s->elem[s->top]; return1; } main() { intx,h,*y; SqStack*a; init(a); scanf("%d%d",&x,&h); while(x! =0) { push(a,x%h); x=x/h; } printf("\n"); while(empty(a)! =0) { pop(a,y); if(*y<10) printf("%d",*y); else printf("%c",*y-10+97); } } #include #include typedefstruct{ char*elem; inttop; }stack; voidinit(stack*s){ s->elem=(char*)malloc(100*sizeof(char)); s->top=0; } voidpush(stack*s,charc){ s->elem[s->top++]=c; } voidpop(stack*s,char*c){ *c=s->elem[--s->top]; } chargettop(stack*s){ returns->elem[s->top-1]; } intcmp(chara,charb){ if((a=='(')&&(b==')'))return1; if((a=='[')&&(b==']'))return1; if((a=='{')&&(b=='}'))return1; return0; } intempty(stack*s){ returns->top; } main(){ stack*s; char*string,c; inti=0; scanf("%s",string); init(s); push(s,string[i]); do{ i++; if(cmp(gettop(s),string[i])) pop(s,&c); else push(s,string[i]); }while(string[i+1]); if(empty(s)==0) printf("ok"); else printf("no"); }_ 运行结果为 ∙本程序的运行怀镜为WindowsXp/2000操作系统,执行文件名为: 栈的应用(表达式求值).exe。 ∙ 进入演示程序后即显示文本方式的用户界面: ∙进入主函数命令后,即提示键入您欲进行运算的表达式(以#作为表达式的结束标志),总的结束符为回车。 5排序与查找 程序设计为 #defineEQ(a,b)((a)==(b)) #defineLT(a,b)((a)<(b)) #defineLQ(a,b)((a)<=(b)) #include #include typedefstruct{ intkey; intn; }SType;/*turboc2中标识符名称不能超8个字符*/ typedefstruct{ STypeelem[10]; intlength; }SSTable; voidcreatD(SSTable*ST)/*参数ST应设为指针*/ { inti,x; ST->length=10; for(i=0;i<10;i++) { scanf("%d",&ST->elem[i].key);/*ST为指针,所以用指针运算符*/ } } intS_Bin(SSTable*ST,intkey){ intlow=0,mid; inthigh=ST->length-1;/*下标从0开始,所以最大下标为length-1*/ while(low<=high){ mid=(low+high)/2; if(EQ(key,ST->elem[mid].key)) returnmid; elseif(LT(key,ST->elem[mid].key)) high=mid-1; elselow=mid+1; } return0; } voidoutD(SSTable*ST)/*输出表*/ { inti; for(i=0;i printf("%6d",ST->elem[i].key); } main() { SSTableST; creatD(&ST); outD(&ST); printf("\n%d",S_Bin(&ST,55));/*输出查找结果*/ }_ 指导教师评语和实验得分: 实验得分: 签名: 年月日
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 114130168 宋国俊 数据结构