数据结构实验.docx
- 文档编号:9154469
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:40
- 大小:374.10KB
数据结构实验.docx
《数据结构实验.docx》由会员分享,可在线阅读,更多相关《数据结构实验.docx(40页珍藏版)》请在冰点文库上搜索。
数据结构实验
数据结构实验
计科0902
200900
实验一——线性表
例题:
#defineNULL0
typedefstructnode{
chara;
structnode*link;
}node,*nodelink;
voidreadlink(nodelinkhead){
nodelinkp,q;
charc;
p=head;printf(“Inputalinktable(astring):
”);
scanf(“%c”,&c);
if(c==’\n’)printf(“Thisstringisempty.”);
while(c!
=’\n’){
q=(nodelink)malloc(sizeof(node));
q->a=c;
p->link=q;
p=q;
scanf(“%c”,&c);
}
p->link=NULL;
}
voildwritelink(nodelinkhead){
nodelinkq;
if(head->link==NULL)printf(“Thislinkisempty.\n”);
for(q=head->link;q;q=q->link)
printf(“%c”,q->a);
printf(“\n”);
}
Intinsert(nodelinkhead,chark1,chark2){
nodelinkp,q;
p=head->link;
while(p->a!
=k1&&p)
p=p->link;
if(p){
q=(nodelink)malloc(sizeof(node));
q->a=k2;
q->link=p->link;
p->link=q;
return1;
}
else{
printf(“Thereisno%c\n”,k1);
return0;
}
}
intdelete(nodelinkhead,chark){
nodelinkp,q;
q=head;
p=head->link;
while(((p->a)&&p){
q=q->link;
p=p->link;
}
If(p){
q=>link=p->link;
return1;
}
else{
printf(“Thereisno%c\n”,k);
return0;
}
}
voidopside(nodelinkhead){
nodelinkp,q;
p=head->link;
while(p->link){
q=p->link;
p->link=q->link;
q->link=head->link;
head->link=q;
}
}
main()
{
chark1,k2,k3;
nodelinkhead;
head=(nodelink)malloc(sizeof(node));
head->link=NULL;
readlink(head);
if(head->link!
=NULL){
printf(“Buildlinkis:
”);
writelink(head);}
if(head->link!
=NULL){
printf(“Pleaseinputacharyouwanttoinsertafter:
”);
k1=getch();
printf(“%c\n”,k1);
printf(“Pleaseinputacharyouwanttoinsert:
”);
k2=get();
printf(“%c\n”,k2);
if(insert(head,k1,k2)){
printf(“After%cinsert%c,linkis:
”,k1,k2);
writelink(head);
}
printf(“Pleaseinputacharyouwanttodelete:
”);
k3=getch();
printf(“%c\n”,k3);
if(delete(head,k3))
{
printf(“afterdelete%c,linkis:
”,k3);
writelink(head);
}
If(head->link!
=NULL){
printf(“Opsiteresultis:
”);
opsite(head);
writelink(head);
free(head);
}
}
}
习题1:
#include"stdio.h"
#include"malloc.h"
#include"conio.h"
typedefstructnode
{
chara;
structnode*link;
}node,*nodelink;
voidreadlink(nodelinkhead)
{
nodelinkp,q;
charc;
p=head;
printf("请输入顺序表中的递增有序元素:
");
scanf("%c",&c);
if(c=='\n')
printf("顺序表为空\n\n");
while(c!
='\n')
{
q=(nodelink)malloc(sizeof(node));
q->a=c;
p->link=q;
p=q;
scanf("%c",&c);
}
p->link=0;
}
intadd(nodelinkhead)
{
nodelinkp;
p=head;
if(p->link==0)
return0;
while(p->link!
=0)
{
if(p->a>p->link->a)
{
printf("输入有误请重新输入\n\n");
return0;
}
p=p->link;
}
return1;
}
voidinsert(nodelinkhead,charx)
{
nodelinkp,q,m;
inti=0;
p=head;
q=(nodelink)malloc(sizeof(node));
q->a=x;
m=p;
while(p->link!
=0)
{
if(p->a>=x)
{
q->link=m->link;
m->link=q;i=1;
break;
}
m=p;
p=p->link;
}
if(i==0)
{
p->link=q;
q->link=0;
}
}
intmain()
{loop:
nodelinkhead;
nodelinkp;
charx,z;
head=(nodelink)malloc(sizeof(node));
head->link=0;
readlink(head);
while(add(head)==0)
readlink(head);
printf("您输入的顺序表为:
");
for(p=head->link;p!
=0;p=p->link)
printf("%c",p->a);
printf("\n请输入您要插入的字符:
");
x=getchar();
insert(head,x);
printf("插入%c后的顺序表为:
",x);
for(p=head->link;p!
=0;p=p->link)
printf("%c",p->a);
printf("\n\n");
scanf("%c",&z);
gotoloop;
}
习题3:
#include
#include
typedefstructnodenode;
typedefstructnode*p_node;
structnode
{
intelement;
p_nodenext;
};
voidInitial(intn,p_nodeT);
p_nodeSearch(intm,p_nodepos);
voidMainBody(intm,ints,p_nodeT);
main()
{
intn,m,s;
charc;
p_nodeT=(p_node)malloc(sizeof(node));
printf("请输入n,m,s:
");
scanf("%d%d%d",&n,&m,&s);
if(s==1&&m==1)
{
for(inti=1;i<=n;i++)
{
printf("%d",i);
}
}
else
{
Initial(n,T);
MainBody(m,s,T);
}
printf("\n");
free(T);
getchar();
getchar();
}
voidInitial(intn,p_nodeT)
{
p_nodep=T;
for(inti=1;i<=n;i++)
{
p_nodeq=(p_node)malloc(sizeof(node));
q->element=i;
p->next=q;
p=q;
}
p->next=T->next;
}
voidMainBody(intm,ints,p_nodeT)
{
p_nodehead=T;
head=Search(s,head);
while(head!
=head->next)
{
p_nodep;
head=Search(m,head);
p=head->next;
head->next=p->next;
printf("%d",p->element);
free(p);
}
printf("%d",head->element);
free(head);
}
p_nodeSearch(intm,p_nodepos)
{
for(inti=1;i { pos=pos->next; } returnpos; } 实验二——树 例题: #include #include structnode{ charinfo; structnode*llink,*rlink; }; typedefstructnodeNODE; NODE*creat(){ charx; NODE*p; scanf("%c",&x); printf("%c",x); if(x! ='.'){ p=(NODE*)malloc(sizeof(NODE)); p->info=x; p->llink=creat(); p->rlink=creat(); } else p=NULL; returnp; } voidrun(NODE*t){ if(t){ run(t->llink); run(t->rlink); printf("%c",t->info); } } main() { NODE*T; printf("Pleaseinputatree: \n"); T=creat(); printf("\n"); if(! T) printf("Thisisaemptybinarytree."); else {printf("Theresultofposttraveseis: \n"); run(T); } printf("\n"); } 课后题1: #defineNULL0 #include #include #include typedefstructBiNode{ chardata; structBiNode*lchild,*rchild; }BiNode,*BiTree; intcreateBiTree(BiTree&T) {charch; scanf("%c",&ch); if(ch=='.')T=NULL; else{T=(BiTree)malloc(sizeof(BiNode)); T->data=ch; createBiTree(T->lchild); createBiTree(T->rchild); } return (1); } intleafcount(BiTree&T) {if(! T)return(0); elseif(! T->lchild&&! T->rchild)return (1); elsereturn(leafcount(T->lchild)+leafcount(T->rchild)); } main() {printf("BuildatreeasRLDplainsequence\n: "); BiTreeT; T=(BiTree)malloc(sizeof(BiNode)); if(createBiTree(T)) {inta; a=leafcount(T);printf("\nTheamountofleafis%d。 ",a);} system("pause"); } 课后题2: #defineNULL0 #include #include #include typedefstructBiNode{ chardata; structBiNode*lchild,*rchild; }BiNode,*BiTree; intc,k; intcreateBiTree(BiTree&T) {charch; scanf("%c",&ch); if(ch=='.')T=NULL; else{T=(BiTree)malloc(sizeof(BiNode)); T->data=ch; createBiTree(T->lchild); createBiTree(T->rchild); } return (1); } voidgetnode(BiTree&T) {if(T) {c++; if(c==k){printf("\nnodeis%c\n",T->data);} else{getnode(T->lchild); getnode(T->rchild); } } } main() {printf("BuildatreeasRLDplainsequence\n: "); BiTreeT; T=(BiTree)malloc(sizeof(BiNode)); createBiTree(T);c=0; printf("pleaseinputanumber: "); scanf("%d",&k); printf("\nGettheRLDplainsequence%dthnode。 ",k); getnode(T); system("pause"); } 实验三——图 例题: #include intnumber; typedefstruct{ intq[20];intf,r; }queue; intnodelist[20][20]; queueQ; intz[20];inta,b,n,i,j,x,y;intfinished; voidenq(queue*Q,intx){ Q->q[Q->r]=x; if(Q->r==19)Q->r=0; elseQ->r++; if(Q->r==Q->f) printf("Overflow! \n"); } front(queue*Q){ if(Q->r==Q->f)printf("Underflow! \n"); elsereturn(Q->q[Q->f]); } voiddeq(queue*Q){ if(Q->r==Q->f) printf("Underflow! \n"); else{ if(Q->f==19) Q->f=0; else Q->f++; } } intqempty(queueQ){ if(Q.f==Q.r)return1; elsereturn0; } voidreadgraph(){ printf("\nPleaseinputn: "); scanf("%d",&n); printf("Pleaseinputnodelist[i][j]: \n"); for(i=1;i<-n;i++){ for(j=1;j<=n;j++) scanf("%d",&nodelist[i][j]); } printf("\n"); printf("List-linkisbulit\n"); for(i=1;i<=n;i++){ for(j=1;j<=n;j++) printf("%3d",nodelist[i][j]); printf("\n"); } } voidshortest(inta,intb){ if(a==b)nodelist[a][a]=2; else{ enq(&Q,a); nodelist[a][a]=2; finished=0; while(! qempty(Q)&&! finished){ a=front(&Q); deq(&Q); j=1; while((j<=n)&&! finished){ if((nodelist[a][j]==1)&&(nodelist[j][j]! =2)){ enq(&Q,j); nodelist[j][j]=2; z[j]=a; if(j==b)finished=1; } if(! finished)j++; } } if(! finished)printf("Thereisnopath."); } } voidwritepath(inta,intb){ i=b; while(i! =a){ printf("%d<-",i); i=z[i]; } printf("%d",a); } main() { readgraph(); printf("Pleaseinputa: "); scanf("%d",&a); printf("Pleaseinputb: "); scanf("%d",&b); Q.f=0;Q.r=0; shortest(a,b); if(finished) writepath(a,b); } 课后题2: #include"stdio.h" #include"malloc.h" #include"conio.h" typedefstructArcNode{ intadjvex; structArcNode*nextarc; intin; }ArcNode; typedefstructVNode{ intdata; ArcNode*firstarc; }VNode,AdjList[20]; typedefstructALGraph{ AdjListvertices; intvexnum,arcnum; intkind; }ALGraph; intn,i,j; intm=0; ints=1; ALGraph*graph; voidread(ArcNode*firstarc){ intx; chary; scanf("%c",&y); while(y=='') scanf("%c",&y); firstarc->nextarc=NULL; if(y=='\n'){ return; } else{ x=(int)y-48; ArcNode*t; t=newArcNode; t->nextarc=NULL; t->in=0; t->adjvex=x; firstarc->nextarc=t; read(firstarc->nextarc); } } voidmkgraph(ALGraph*graph){ charrub; ArcNode*t; VNode*list; scanf("%c",&rub); for(;s<=n;s++){ printf("%d",s); t=newArcNode; graph->vertices[s].firstarc=t; read(graph->vertices[s].firstarc); } } voidrun(ArcNode*firstarc){ ArcNode*t; t=firstarc; if(t->adjvex==j){ m=1; return; } if(t->in==0&&m==0&&t->adjvex>0&&t->adjvex<=n&&graph->vertices[t->adjvex].firstarc->nextarc! =NULL){ t->in=1; run(graph->vertices[t->adjvex].firstarc->nextarc); } if(m==0&&t->nextarc! =NULL) run(t->nextarc); } intmain(){ graph=newALGraph; printf("顶点树: "); scanf("%d",&n); printf("以邻接表方式依次输入各顶点的关系: \n"); mkgraph(graph); printf("已生成图.\n\n请输入要寻找路径的起点i和终点j(i! =j): "); scanf("%d%d",&i,&j); while(i==j||i<=0||i>n||j<=0||j>n){ printf("对不起,输入有误,请重新输入: "); scanf("%d%d",&i,&j); } run(graph->vertices[i].firstarc->nextarc); if(m==1) printf
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验