数据结构实验答案doc.docx
- 文档编号:14400586
- 上传时间:2023-06-23
- 格式:DOCX
- 页数:26
- 大小:32.73KB
数据结构实验答案doc.docx
《数据结构实验答案doc.docx》由会员分享,可在线阅读,更多相关《数据结构实验答案doc.docx(26页珍藏版)》请在冰点文库上搜索。
数据结构实验答案doc
《数据结构》实验大纲
实验一顺序表的创建及插入、删除算法
一、实验目的:
1.创建一个顺序表,并实现插入、删除算法
二、实验内容:
1.
(1)创建一个空的顺序表L
(2)依次插入a,b,c,d,e五个元素
(3)在第4个元素位置上插入元素f
(4)删除L的第3个元素
(5)输出顺序表L
#include
#include
#defineMaxSize50
typedefcharElemType;
typedefstruct
(
ElemTypeelem[MaxSize];
intlength;
JSqList;
SqList*InitList()
(
SqList*L;
L=(SqList*)malloc(sizeof(SqList));
L->length=0;
returnL;
}
voidDispList(SqList*L)
(
inti;
if(L->length==O)return;
for(i=0;i
printf(n%c",L->elem[i]);
printf(侦');
}
voidListInsert(SqList*L,inti,ElemTypee)
(,
intj;
if(i
return;
i—»
for(j=L->length;j>i;j—)
L->elem[j]=L->elem[j-1];
L->elem[i]=e;
L->length++;
}J
voidListDelete(SqList*L,inti)
intj;
if(i<1IIi>L->length)
return;
i--;
for(j=i;j
L->elem[j]=L->elem0+1];
L->length-;
}
main()
(
SqList*L;
L=InitList();
ListInsert(L,l,*a');
ListInsert(L,2,'b');
ListInsert(L,3/c');
ListInsert(L,4,'d');
ListInsert(L,5,'e');
ListInsert(L,4,'f);
ListDelete(L,3);
printf(”输出顺序表L:
");
DispList(L);
}
实验二单链表的创建及插入、删除算法
一、实验目的:
1.创建一个单链表,并实现插入、删除算法
二、实验内容:
1.
(1)创建一个空的单链表L
(2)依次插入a,b,c,d,e五个元素
(3)在第4个元素位置上插入元素f
(4)删除L的第3个元素
(5)输出单链表L
(6)销毁单链表L
#include
#include
typedefcharElemType;
typedefstructLNode
(
ElemTypedata;
structLNode*next;
JLinkList;
LinkList*InitList()
(
LinkList*L;
L=(LinkList*)malloc(sizeof(LinkList));
L->next=NULL;
returnL;
}
voidDestroyList(LinkList*L)
(
LinkList*p=L,*q=p->next;
while(q!
=NULL)
free(p);
p=q;
q=p->next;
}
free(p);
}
voidDispList(LinkList*L)
(
LinkList*p=L->next;
while(p!
=NULL)
(
printf(n%c",p->data);
p=p->next;
)
printfC'\nH);
}
voidListInsert(LinkList*L,inti,ElemTypee)
{,
intj=0;
LinkList*p=L,*s;
while(j =NULL) ( j++; p=p->next; } if(p==NULL) return; else ( s=(LinkList*)malloc(sizeof(LinkList)); s->data=e; s->next=p->next; p->next=s; } } voidListDelete(LinkList*L,inti) ( intj=0; LinkList*p=L,*q; while(j =NULL) ( j++; p=p->next; } if(p==NULL) return; else q=p->next; p->next=q->next; free(q); } main() { LinkList*L; L=InitList(); ListInsert(L,l,'a'); ListInsert(L,2,'b'); ListInsert(L,3,'c'); ListInsert(L,4,'d'); ListInsert(L,5,'e'); ListInsert(L,4,'f); ListDelete(L,3); printf(n输出单链表: , DispList(L); DestroyList(L); } 实验三实现二叉树各种基本算法 一、实验目的: 1.实现二叉树各种基本算法 二、实验内容: 1.编写一个程序,利用递归算法求出二叉树T的深度、结点个数及叶子结点个数。 提示: 创建二叉树的三叉链表算法如下: 设二叉树的字符串表示形式为"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。 #include #include #defineMaxSize100 typedefcharElemType; typedefstructBiTNode ( ElemTypedata; structBiTNode*lchild,*rchild; }BiTree; BiTree*CreateBiTree(char*str)//由str字符串创建二叉树的二叉链表 ( charch; BiTree*T; BiTree*stack[MaxSize],*p=NULL; inttop,k,j; top=-l; j=0; T=NULL; ch=str[j]; while(ch! ='\0') ( switch(ch) case'(': top++;stack[top]=p;k=l;break;〃为左结点 case')': top--;break; case*,': k=2;break;〃为右结点 default: p=(BiTree*)malloc(sizeof(BiTree)); p->data=ch;p->lchild=p->rchild=NULL; if(T==NULL) T=p; else ( switch(k) ( case1: stack[top]->lchild=p;break; case2: stack[top]->rchild=p;break; } } ) j++; ch=str[j]; } returnT; } intBiTreeDepth(BiTree*T) ( intlchild_depth,rchild_depth; if(T==NULL) return0; else ( lchild_depth=BiTreeDepth(T->lchild); rchild_depth=BiTreeDepth(T->rchild); if(lchild_depth>rchild_depth) return(lchild_depth+l); else return(rchild_depth+1); ) ) intNodes(BiTree*T) ( intnl,n2; if(T==NULL) return0; elseif(T->lchild==NULL&&T->rchild==NULL)return1; else ( nl=Nodes(T->lchild); n2=Nodes(T->rchild); return(nl+n2+l); } } intLeafNodes(BiTree*T) intnl,n2; if(T==NULL) return0; elseif(T->lchild==NULL&&T->rchild==NULL) return1; else ( n1=LeafNodes(T->lchild); n2=LeafNodes(T->rchild); return(nl+n2); } } main() ( BiTree*T; T=CreateBiTree("A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树T的深度: %d\n",BiTreeDepth(T)); printf("二叉树T的结点个数: %d\n".Nodes(T)); printf("二叉树T的叶子结点个数: %d\n",LeafNodes(T)); } 实验四二叉树的遍历 一、实验目的: 1.实现二叉树各种遍历算法 二、实验内容: 1.编写一个程序,实现二叉树的先序遍历、中序遍历、后序遍历以及层次遍历的算法,并输出每种算法的遍历序列。 提示: 创建二叉树的二叉链表算法与实验三相同。 设二叉树的字符串表示形式为"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”。 #include #include #defineMaxSize100 typedefcharTElemType; typedefstructBiTNode ( TElemTypedata; structBiTNode*lchild,*rchild; }BiTree; BiTree*CreateBiTree(char*str)〃由str字符串创建二叉树的二叉链表 ( charch; BiTree*T; BiTree*stack[MaxSize],*p=NULL; inttop,k,j; top=-1; j=0; T=NULL; ch=str[j]; while(ch! ='\0') switch(ch) ( case'(': top++;stack[top]=p;k=l;break;〃为左结点case')': top—;break; case',': k=2;break;〃为右结点 default: p=(BiTree*)malloc(sizeof(BiTree)); p->data=ch;p->lchild=p->rchild=NULL; if(T==NULL) T=P; else { switch(k) ( case1: stack[top]->lchild=p;break; case2: stack[top]->rchild=p;break; } } } j++; ch=str[j]; } returnT; ) voidPreOrder(BiTree*T) ( if(T! =NULL) ( printf("%c",T->data); PreOrder(T->lchild); PreOrder(T->rchild); } } voidInOrder(BiTree*T) ( if(T! =NULL) ( InOrder(T->lchild); printf("%c",T->data); InOrder(T->rchild); ) } voidPostOrder(BiTree*T) if(T! =NULL) PostOrder(T->lchild); PostOrder(T->rchild);printf(H%cn,T->data); } } voidLevelOrder(BiTree*T)/*层次遍历*/ ( BiTree*q[MaxSize]; intfront,rear; front=rear=0; if(T! =NULL) printf(n%cn,T->data); rear++; q[rear]=T; while(rear! =front) ( front=(front+l)%MaxSize; T=q[front]; if(T->lchild! =NULL) { printf("%c",T->lchild->data); rear=(rear+1)%MaxSize; q[rear]=T->lchild; } if(T->rchild! =NULL) ( printf("%c",T->rchild->data); rear=(rear+l)%MaxSize; q[rear]=T->rchild; } } printf("\n"); } main() ( BiTree*T; T=CreateBiTree(nA(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))n); printf("层次遍历序列: \n"); LevelOrder(T); printf(”先序遍历序歹! J: \nn); PreOrder(T); printf(侦'); printf(H中序遍历序列: \n"); InOrder(T); printf(侦'); printf(n后序遍历序列: \n"); PostOrder(T); printf(H\nH); 实验五图的遍历 一、实验目的: 1.实现图的深度优先遍历和广度优先遍历算法 二、实验内容: 1.编写一个程序,实现图的深度优先遍历和广度优先遍历算法,并输出图G从顶点1开始的深度优先遍历和广度优先遍历的遍历序列 #include"stdio.h" #include"malloc.hn #defineVNUM20typedefstruct( charvexs[VNUM+1]; intarcs[VNUM][VNUM];intvexnum,arcnum; )graph; typedefstructnode ( chardata; structnode*next; }node,*queueptr; typedefstruct { queueptrfront; queueptrrear; }linkqueue; voidCreatGraph(graph*g) inti,j,k; printf("PleaseinputthevertexesnumberandarcsnumberofUndigraphAn");printf("vexnum="); scanf(n%dn,&g->vexnum); printf("arcnum=n); scanf("%d",&g->arcnum); printf("PleaseinputTheNameofallvertexes: "); for(i=0;i {J printf("\nNO.%dvertex: n,i+l); g->vexs[i]=getch(); printf("%c",g->vexs[i]); }一 g->vexs[i]='\0'; for(i=0;i for(j=0;j g->arcs[i]0]=O; printf("\nPleaseinputthepositionofallexistarcs( \n"); printf("Everyarcinputonlyonce! \nH); printf(Hvivj: n); for(k=O;k {J scanf(”%d%d”,&i,&j); g->arcs[i-l][j-l]=l; g->arcs[j-l][i-l]=l; } } voidInitQueue(linkqueue*q) ( q->front=q->rear=(queueptr)malloc(sizeof(node)); q->front->next=NULL; } voidEnQueue(linkqueue*q,intx,graph*g) queueptrp; p=(queueptr)malloc(sizeof(node)); p->data=g->vexs[x]; p->next=NULL; q->rear->next=p; q->rear=p; } intDeQueue(linkqueue*q,graph*g) (、、 intk=0,u; queueptrp; p=q->front->next; while(g->vexs[k]! =p->data) k++; u=k; q->front->next=p->next; if(q->rear==p) q->rear=q->front; free(p); returnu; } intIsEmpty(linkqueue*q) if(q->front==q->rear) return1; else return0; } intFirstAdjvex(graph*g,intx) (「「 intk; for(k=O;k {J if(g->arcs[x][k]&&g->arcs[k][x]! =0)returnk; ) return-1; } intNextAdjvex(graph*g,intx,inty) (「「 intk; for(k=y+l;k if(g->arcs[x][k]&&g->arcs[k][x]! =0)returnk; return-1; } voidBFST(graph*g) {」」 intu,w; intv; intvisited[VNUM]; linkqueueq; InitQueue(&q); for(v=0;v visited[v]=O; v=0; printf("%c",g->vexs[v]); visited[v]=l; EnQueue(&q,v,g); while(! IsEmpty(&q)) ( u=DeQueue(&q,g); w=FirstAdjvex(g,u); while(w! =-l) ( if(! visited[w]) ( printf(n%cn,g->vexs[w]); visited[w]=l; EnQueue(&q,w,g); } w=NextAdjvex(g,u,w); }'「 } } intvisited[VNUM]; voidDFS(graph*g,intv); voidDFST(graph*g) intv; for(v=0;v visited[v]=O; for(v=0;v if(! visited[v]) DFS(g,v); } voidDFS(graph*g,intv) (「「 intw; visited[v]=l; printf(n%cn,g->vexs[v]); for(w=FirstAdjvex(g,v);w>=O;w=NextAdjvex(g,v,w)) (if(! visited[w])DFS(g,w);) }J main() ( graph*g; g=(graph*)malloc(sizeof(graph)); CreatGraph(g); printf(nDFSTraverseGraph: \nM); DFST(g); printf(侦'); printf("BFSTraverseGraph: \nH); BFST(g); printf(侦'); } 实验六实现折半查找算法 一、实验目的: 1.实现二分法查找(折半查找)的算法 二、实验内容: 1.输出在顺序表{1,2,3,4,5,6,7,8,9,10)中采用二分法查找(折半查找)关键字9的过程。 #include #defineN10 intBinSearch(intR[],intn,intk) ( intlow=0,high=n-l,mid,count=0; while(low<=high) ( mid=(low+high)/2; printf("M%d次查找: 在[%d,%d]中查找到元素%d\n”,++count,low,high,R[mid]); if(R[mid]==k) returnmid; elseif(R[mid]>k)high=mid-l; elselow=mid+l; } return-1; } main() inti,k=9; inta[N]; for(i=0;i a[i]=i+l; if((i=BinSearch(a,N,k))! =-l) printfC兀素%<1的位置是%d\n",k.i); else printf("元素%d不在表中\n",k); } 实验七实现起泡排序算法 一、实验目的: 1.实现起泡排序算法 二、实验内容: 1.编写一个程序实现起泡排序算法,并输出{9,8,7,6,5,4,3,2,1,0}的排序过程 #include voidBubbleSort(inta[],intn) ( inti,j,k,temp; for(i=0;i ( for(j=n-l;j>i;j-) if(aU] ( temp=a[j]; a[j]=a|j-l]; a[j-l]=temp; } printf(nM%d次排序: ",i+1); for(k=0;k printf(n%2d",a[k]); printf(侦
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 答案 doc