数据库结构上机指导.docx
《数据库结构上机指导.docx》由会员分享,可在线阅读,更多相关《数据库结构上机指导.docx(21页珍藏版)》请在冰点文库上搜索。
数据库结构上机指导
数据结构实验指导书
实验一
一、实验目的
1、掌握使用TurboC2.0上机调试线性表的基本方法;
2、掌握线性表的基本操作:
插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。
二、实验要求
1、认真阅读和掌握本实验的程序。
2、上机运行本程序。
3、保存和打印出程序的运行结果,并结合程序进行分析。
4、按照你对线性表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果
三、注意事项:
在磁盘上创建一个目录,专门用于存储数据结构实验的程序。
四、实验内容
程序1:
线性表基本操作的实现
这个程序中演示了顺序表的创建、插入、删除和查找,请修改并完成。
程序如下:
#include
#include
/*顺序表的定义:
*/
#defineListSize100
typedefstruct
{intdata[ListSize];/*向量data用于存放表结点*/
intlength;/*当前的表长度*/
}SeqList;
voidmain()
{voidCreateList(SeqList*L,intn);
voidPrintList(SeqList*L,intn);
intLocateList(SeqList*L,intx);
voidInsertList(SeqList*L,intx,inti);
voidDeleteList(SeqList*L,inti);
SeqListL;
inti,x;
intn=10;/*THELENGTHOFLIST*/
L.length=0;
clrscr();
CreateList(&L,n);/*CREATTHELIST*/
PrintList(&L,n);/*PRINTTHELIST*/
printf("INPUTTHERESEARCHELEMENT");
scanf("%d",&x);
i=LocateList(&L,x);
printf("theresearchpositionis%d\n",i);/*顺序表查找*/
printf("inputthepositionofinsert:
\n");
scanf("%d",&i);
printf("inputthevalueofinsert\n");
scanf("%d",&x);
InsertList(&L,x,i);/*顺序表插入*/
PrintList(&L,n);/*打印顺序表*/
printf("inputthepositionofdelete\n");
scanf("%d",&i);
DeleteList(&L,i);/*顺序表删除*/
PrintList(&L,n);
getch();/*打印顺序表*/
}
/*顺序表的建立:
*/
voidCreateList(SeqList*L,intn)
{inti;
printf("pleaseinputnnumbers\n");
for(i=1;i<=n;i++)
{scanf("%d",&L->data[i]);
}
L->length=n;
}
/*顺序表的打印:
*/
voidPrintList(SeqList*L,intn)
{inti;
printf("thesqlistis\n");
for(i=1;i<=n;i++)
printf("%d",L->data[i]);
}
/*顺序表的查找:
*/
intLocateList(SeqList*L,intx)
{inti;
for(i=1;i<=10;i++)
if((L->data[i])==x)return(i);
elsereturn(0);
}
/*顺序表的插入:
*/
voidInsertList(SeqList*L,intx,inti)
{intj;
for(j=L->length;j>=i;j--)
L->data[j+1]=L->data[j];
L->data[i]=x;
L->length++;
}
/*顺序表的删除:
*/
voidDeleteList(SeqList*L,inti)
{intj;
for(j=i;j<=(L->length)-1;j++)
L->data[j]=L->data[j+1];
}
实验二单链表操作
一、实验目的
1.掌握握单链表的基本操作:
插入、删除、查找等运算。
二、实验要求
1.认真阅读和掌握本实验的程序。
2.上机运行本程序。
3.保存和打印出程序的运行结果,并结合程序进行分析。
4.按照你对单链表的操作需要,重新改写主程序并运行,打印出文件清单和运行结果
三、实验内容
程序1:
单链表基本操作的实现
这个程序中演示了单链表的创建、插入、删除和查找。
程序如下:
#include
typedefstructnode{
intdata;
structnode*next;
}NODE;
/******************************************/
NODE*Create(){
NODE*p,*head;
intx;
head=(NODE*)malloc(sizeof(NODE));
head->next=NULL;
printf("Inputdata,-1toEnd!
\n");
scanf("%d",&x);
while(x!
=-1){
p=(NODE*)malloc(sizeof(NODE));
p->data=x;
p->next=head->next;
head->next=p;
scanf("%d",&x);
}
return(head);
}
/******************************************/
voidOutput(NODE*head){
NODE*p;
p=head;
printf("BegintodumptheLinkList...\n");
while(p->next!
=NULL){
printf("->%d",p->next->data);
p=p->next;
}
printf("\nTheLinkListended!
\n");
}
/******************************************/
intListlen(NODE*head){
inti=0;
NODE*p=head;
while(p->next!
=NULL){
i++;
p=p->next;
}
return(i);
}
/******************************************/
intGet(NODE*head,inti){
intj=0;
NODE*p=head;
while(p->next&&j
j++;
p=p->next;
}
if(!
p->next||j>i)return(0);
elsereturn(p->data);
}
/******************************************/
voidDel(NODE*head,inti){
NODE*p=head;
intj=0;
while(p->next&&jj++;
p=p->next;
}
if(!
p->next||j>i-1)printf("thepositioniswrong\n");
else
p->next=p->next->next;
}
/******************************************/
voidIns(NODE*head,inti,inte){
NODE*p=head,*q;
intj=0;
while(p->next&&jj++;
p=p->next;
}
if(!
p->next&&j>i-1)printf("Wrongposition\n");
else{
q=(NODE*)malloc(sizeof(NODE));
q->data=e;
q->next=p->next;
p->next=q;
}
}
/******************************************/
main(){
NODE*head;
intlength;
inti,element;
clrscr();
head=Create();
Output(head);
length=Listlen(head);
printf("thelengthofthelinkis%d\n",length);
printf("inputtheorder:
\n");
scanf("%d",&i);
element=Get(head,i);
printf("theelementoftheorderis%d\n",element);
printf("inputthedelposition\n");
scanf("%d",&i);
Del(head,i);
Output(head);
printf("Inputtheinsertposionandelement:
\n");
scanf("%d%d",&i,&element);
Ins(head,i,element);
Output(head);
getch();
}_
} 实验三栈的基本操作
一、实验目的
掌握栈的基本操作:
初始化栈、判栈为空、出栈、入栈等运算。
二、实验要求
1.认真阅读和掌握本实验的算法。
2.上机将本算法实现。
3.保存和打印出程序的运行结果,并结合程序进行分析。
三、实验内容
利用栈的基本操作实现将任意一个十进制整数转化为R进制整数
算法为:
1、定义栈的顺序存取结构
2、分别定义栈的基本操作(初始化栈、判栈为空、出栈、入栈等)
3、定义一个函数用来实现上面问题:
十进制整数X和R作为形参
初始化栈
只要X不为0重复做下列动作
将X%R入栈
X=X/R
只要栈不为空重复做下列动作
栈顶出栈
输出栈顶元素
参考程序:
#defineMAXSIZE100
#include
structstack{
intdata[MAXSIZE];
inttop;
};
voidinit(structstack*s){
s->top=-1;
}
intempty(structstack*s){
if(s->top==-1)
return1;
else
return0;
}
voidpush(structstack*s,inti){
if(s->top==MAXSIZE-1){
printf("Stackisfull\n");
return;
}
s->top++;
s->data[s->top]=i;
}
intpop(structstack*s){
if(empty(s)){
printf("stackisempty");
return-1;
}
return(s->data[s->top--]);
}
voidtrans(intnum){
structstacks;
intk;
init(&s);
while(num){
k=num%16;
push(&s,k);
num=num/16;
}
while(!
empty(&s)){
k=pop(&s);
if(k<10)
printf("%d",k);
else
printf("%c",k+55);
}
printf("\n");
}
main(){
intnum;
clrscr();
printf("Inputanum,-1toquit:
\n");
scanf("%d",&num);
while(num!
=-1){
trans(num);
scanf("%d",&num);
}
}
_
实验四队列的基本操作
一、实验目的
掌握队列的基本操作:
初始化队列、判队列为空、出队列、入队列等运算。
二、实验要求
1.认真阅读和掌握本实验的算法。
2.上机将本算法实现。
3.保存和打印出程序的运行结果,并结合程序进行分析。
三、实验内容
利用队列的基本操作实现杨辉三角的输出
算法如下:
voidout_number(intn);
{init_queue(Q);
printf
(1);
en_queue(Q,s1+s2);
for(I=2;I<=n;I++)
{s1=0;for(j=1;j<=I-1;j++)
{s2=out_queue(Q);
printf(s2);
en_queue(q,s1+s2);
s1=s2;
}
printf
(1);
en_queue(Q,1+s2);
}
参考程序如下
typedefstruct
{int*data;
intfront;
intrear;
}
sqqueue;
main()
{
inti,j,m,s1=0,s2=1;
sqqueueq;
clrscr();
q.data=(int*)malloc(100*sizeof(int));
q.rear=q.front=0;
q.data[q.rear]=s2;
q.rear++;
printf("%40d",s2);
for(i=2;i<=8;i++)
{s1=0;
for(m=1;m<=40-i;m++)
printf("%c",'');
for(j=1;j<=i-1;j++)
{s2=q.data[q.front];
q.front++;
printf("%d",s2);
q.data[q.rear]=s1+s2;
q.rear++;
s1=s2;
}
printf("%d\n",1);
q.data[q.rear]=1+s2;
q.rear++;
}
}_
实验五数组的基本操作
一、实验目的
回顾c语言中数组的定义和基本应用
二、实验要求
1.认真阅读和掌握本实验的程序。
2.上机运行本程序。
3.保存和打印出程序的运行结果,并结合程序进行分析。
三、实验内容
有M个学生,学习N门课程,已知所有学生的各科成绩,
编程:
分别求每个学生的平均成绩和每门课程的平均成绩
参考程序:
#defineM5
#defineN4
#include"stdio.h"
main()
{inti,j;
staticfloatscore[M+1][N+1]={{78,85,83,65},{88,91,89,93},{72,65,54,75},{86,88,75,60},{69,60,50,72}};
for(i=0;i{for(j=0;j{score[i][N]+=score[i][j];
score[M][j]+=score[i][j];
}
score[i][N]/=N;
}
for(j=0;jscore[M][j]/=M;
clrscr();
printf("学生编号课程1课程2课程3课程4个人平均\n");
for(i=0;i{printf("学生%d\t",i+1);
for(j=0;jprintf("%6.1f\t",score[i][j]);
printf("\n");
}
for(j=0;j<8*(N+2);j++)
printf("-");
printf("\n课程平均");
for(j=0;jprintf("%6.1f\t",score[M][j]);
printf("\n");
getch();
}
实验六二叉树操作
一、实验目的
1.进一步掌握指针变量的含义。
2.掌握二叉树的结构特征,以及各种存储结构的特点及使用范围。
3.掌握用指针类型描述、访问和处理二叉树的运算。
二、实验要求
1.认真阅读和掌握本实验的程序。
2.上机运行本程序。
3.保存和打印出程序的运行结果,并结合程序进行分析。
4.按照你二叉树的操作需要,重新改写主程序并运行,打印出文件清单和运行结果
三、实验内容
程序1:
按先序次序输入二叉树中结点的值(一个字符),`0`表示空树,生成二叉树的二叉链表存储结构,a为指向根结点的指针。
然后按中序顺序遍历二叉树。
算法思想:
先访问左子树,再访问根结点,最后访问右子树
参考程序如下:
#defineNULL0
typedefstructstu{
chardata;
structstu*left,*right;
}sn;
sn*Create(sn*a)
{charch;
scanf("%c",&ch);
if(ch=='')a=NULL;
else{a=(sn*)malloc(sizeof(sn));
if(!
a)printf("yuguyuy");
a->data=ch;
a->left=Create(a->left);
a->right=Create(a->right);
}
return(a);
}
voidinc(sn*b)
{if(b){inc(b->left);
printf("%c",b->data);
inc(b->right);}
}
main()
{
sn*t,*q;
q=NULL;
t=Create(q);
inc(t);
printf("\n");
getch();
}实验数据:
abc00de0g00f000(0表示空格)
实验七图的操作
一.实验目的
1.掌握图的基本存储方法。
2.掌握有关图的操作算法并用高级语言编程实现;
3.熟练掌握图的两种搜索路径的遍历方法。
二.实验要求
1.认真阅读和掌握本实验的算法。
2.上机将本算法实现。
3.保存和打印出程序的运行结果,并结合程序进行分析。
4.按照你对图的操作需要,重新改写主程序并运行,打印出文件清单和运行结果
三.实验内容
以邻接矩阵和邻接表的方式存储连通图。
然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。
算法如下:
深度优先遍历的递归算法
(1)深度优先遍历算法
intvisited[MaxVertexNum];//访问标志向量是全局量
voidDFSTraverse(ALGraph*G)
{//深度优先遍历以邻接表表示的图G,而以邻接矩阵表示G时,算法完全与此相同
inti;
for(i=0;in;i++)
visited[i]=FALSE;//标志向量初始化
for(i=0;in;i++)
if(!
visited[i])//vi未访问过
DFS(G,i);//以vi为源点开始DFS搜索
}//DFSTraverse
(2)邻接表表示的深度优先搜索算法
voidDFS(ALGraph*G,inti){
//以vi为出发点对邻接表表示的图G进行深度优先搜索
EdgeNode*p;
printf("visitvertex:
%c",G->adjlist[i].vertex);//访问顶点vi
visited[i]=TRUE;//标记vi已访问
p=G->adjlist[i].firstedge;//取vi边表的头指针
while(p){//依次搜索vi的邻接点vj,这里j=p->adjvex
if(!
visited[p->adjvex])//若vi尚未被访问
DFS(G,p->adjvex);//则以Vj为出发点向纵深搜索
p=p->next;//找vi的下一邻接点
}
}//DFS
#defineMaxVertexNum5
#definem5
#defineNULL0
typedefstructnode
{intadjvex;
structnode*next;
}JD;
typedefstructtnode
{intvexdata;
JD*firstarc;
}TD;
typedefstruct
{
TDag[m];
intn;
}ALGRAPH;
voidDFS(ALGRAPH*G,inti);
voidcreat(ALGRAPH*G)
{inti,m1,j;
JD*p,*p1;
printf("pleaseinputthenumberofgraph\n");
scanf("%d",&G->n);
for(i=0;in;i++)
{printf("pleaseinputtheinfoofnode%d",i);
scanf("%d",&G->ag[i].vexdata);
printf("pleaseinputthenumberofarcswhichadjto%d",i);
scanf("%d",&m1);
printf("pleaseinputtheadjvexpositionofthefirstarc\n");
p=(JD*)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
G->ag[i].firstarc=p;
p1=p;
for(j=2;j<=m1;j++)
{printf("pleaseinputthepositionofthenextarcvexdata\n");
p=(JD*)malloc(sizeof(JD));
scanf("%d",&p->adjvex);
p->next=NULL;
p1->next=p;
p1=p;}
}
}
intvisited[MaxVertexNum];
voidDFSTraverse(ALGRAPH*G)
{
inti;
fo