华仔数据结构实验报告

1、本科实验报告课程名称：数据结构实验项目：线性结构、树形结构、图结构、查找、排 序实验地点：专业班级：_学号：学生姓名：指导教师：2011年 12 月 24 日实验目的和要求熟练掌握线性结构的基本操作在顺序表和链式表上的实现。二、实验内容和原理设顺序表递增有序，编写一个程序，将 x插入，使之仍然有序。三、主要仪器设备使用的计算机：Nopated+四、操作方法与实验步骤#include<stdio.h>#define maxlen 50typedef int elemtype;typedef elemtype sqlistmaxlen;int creat(sqlist A)int i,

2、n;printf("Please input length:n");scanf("%d",&n);for(i=0;i<n;i+)printf("Please input %dth elementn",i+1); scanf("%d”,&Ai); return n;void disp(sqlist A,int n)int i;if(n=0)printf("The list is NULL:n");for(i=0;i<n;i+)printf("%4d",Ai);

3、 printf("n");int Insert(sqlist A,int n,int x)int i=0,j;if(x>=An-1)An=x; else while(Ai<x) i+；for(j=n;j>=i;j-) Aj+1=Aj；Ai=x； return n+1; void main() sqlist A; int x,n;n=creat(A);disp(A,n);printf("Please input you want to insert:n"); scanf("%d",&x);n=Insert(A,

4、n,x); disp(A,n);五、实验数据记录和处理inputlength：Please 1 Please 4 Pleaseinputinputinput1th2th3thPleaseinput4thelementelementelementelement4 6inputyouuant to insert：请按任意键继续.六、实验结果与分析这个程序为比较基础的程序七、讨论、心得该程序可以帮助我加深对线性表的理解，引发我对数据结构这门课的兴趣实验项目(树结构)一、实验目的和要求熟悉各种表示方法和便利方式，掌握有关算法，了解树在计算机科学中的应用。二、实验内容和原理编写递归算法，计算二叉树中的叶

5、子节点数目三、主要仪器设备使用的计算机：nopated+四、操作方法与实验步骤#include<stdio.h>#include<stdlib.h>#define max 10typedef struct nodechar data;node *lchild,*rchild;Bitree;Bitree *Bmax;Bitree *Creatree() /建立二叉树Bitree *T,*S;char ch;int front,rear,sign;sign=0;front=0;rear=-1;T=NULL;printf("建立二叉树：n");ch=get

6、char();while(ch!='#')if(ch!='') /输入结点不是虚结点S=(Bitree *)malloc(sizeof(Bitree);S->data=ch;S->lchild=S->rchild=NULL;rear+;Brear=S;if(rear=front)T=S;sign+;elseif(sign%2=1) /寻找父结点Bfront->lchild=S;if(sign%2=0) Bfront->rchild=S; front+; sign+;else /输入结点为虚结点if(sign%2=0)front+;s

7、ign+;ch=getchar();return T;int Searchleaf(Bitree *T) /计算叶子数if(T=NULL)return 0;else if(T->lchild=NULL&&T->rchild=NULL)return 1;else return(Searchleaf(T->lchild)+Searchleaf(T->rchild);void visit(Bitree *T)printf("%cn",T->data);void Inorder(Bitree *T) /中序遍历二叉树if(T!=NULL

8、)Inorder(T->lchild);visit(T);Inorder(T->rchild);void main()Bitree *T;T=Creatree();printf("中序遍历:n");Inorder(T);printf("叶子数 %dn",Searchleaf(T);五、实验数据记录和处理健立二叉树; nBCDEFGK 中序月历;社子数4Press dny knjr to continue六、实验结果与分析这个程序让我加深了对中序遍历二叉树的理解七、讨论、心得树是常用的数据结构 要加深理解掌握它实验项目（图结构）-、实验目的和要

9、求熟悉图的存储结构，掌握有关算法的实现，了解图在软件中的应用。二、实验内容和原理基于深度优先算法编写程序，判别该有向图中是否存在vi到vj的路径。三、主要仪器设备使用的计算机：nopated+四、操作方法与实验步骤#include<stdio.h>#include<malloc.h>int n;struct VNode 顶点int position;struct VNode* next;；struct ArcNode/ 弧int mark;struct VNode* first;void DFS(struct ArcNode* v,struct ArcNode* w)深

10、度优先搜索struct VNode* L;w->mark=1;L=w->first;while(L!=NULL)if(v+(L->position)->mark=0)/递归调用DFS(v,(v+L->position);L=L->next;int main()int i,j,k；int key1,key2;int num=0;struct ArcNode* p;struct VNode* temp;struct VNode* flag;printf("该有向图有多少个顶点：n");scanf("%d",&n);

11、while(n<1)printf("你输入的值不合理，请重新输入：n");scanf("%d",&n);p=(struct ArcNode*)malloc(n*sizeof(struct ArcNode);for(i=0;i<n;i+) 创建有向图printf("请输入以V%d为弧尾的所有弧，并以-1结束输入n",i+1);scanf("%d",&k);if(k=-1)pi.mark=0;pifirst=NULL;elsetemp=(struct VNode*)malloc(sizeof

12、(struct VNode);temp->position=k;temp->next=NULL;pi.first=temp;pi.mark=0;flag=temp;scanf("%d",&k);while(k!=-1)temp=(struct VNode*)malloc(sizeof(struct VNode);temp->position=k;temp->next=NULL;flag->next=temp;flag=temp;scanf("%d",&k);printf（"请输入要判断的两顶点的位置

13、：n"）;scanf("%d%d",&key1,&key2);/以下代码用来判断是否连通DFS(p,(p+key1);if(pkey2.mark=1)printf("V%d 和 V%d 是连通的！ n",key1+1,key2+1);elsepkey1.mark=0;DFS(p,(p+key2);if(pkey1.mark=1)printf("V%d 和 V%d 是连通的！n",key1+1,key2+1);else printf("V%d 和 V%d 不是连通的！n",key1+1,ke

14、y2+1);system("pause");return 0;五、实验数据记录和处理该有向图有多少个顶点.4请输入以Ui为瓠尾的所有瓠，并以T结束输入 2褊队以U2为瓠尾的所有瓠，并以T结束输入 4意输入以U3为瓠尾的所有弧，并以T结束输入 信输入以U4为弧尾的所有弧，并以1结束输入 3德输入要判断的两顶点的位置;2心和U4丕是连通的！请卷任煮遍缝一六、实验结果与分析在调试和运行中，发现了很多错误，经过反复修改，终于能运行。七、讨论、心得由于这个程序较为复杂， 程序代码也比较长，编写程序时遇到了不少的困难， 经过不懈努力, 对于图有了更深的认识。实验项目（查找）-、实验目的

15、和要求掌握查找表上的有关查找方法，并分析时间复杂度。二、实验内容和原理在二叉树中查找关键字为key的记录三、主要仪器设备使用的计算机：nopated+四、操作方法与实验步骤#include"stdio.h"#include"stdlib.h"#include"conio.h"struct nodeint data;struct node * Ichild,* rchild;；void MiddleOrder (struct node *q) if (q!=NULL)MiddleOrder(q->lchild);printf(&q

16、uot;%d ",q->data); MiddleOrder(q->rchild);void InsertNode(struct node *p,struct node * pn)if(pn->data<p->data)if (p->lchild=NULL) p->lchild=pn;elseInsertNode(p->lchild,pn);elseif (p->rchild=NULL) p->rchild=pn;elseInsertNode(p->rchild,pn);struct node * CreateBinS

17、ortTree()int x;struct node *t;struct node *s;t=NULL;printf("请输入有序表，输入-1时结束。n");scanf("%d",&x);while(x!=-1) s=(struct node *)malloc(sizeof(struct node);s->data=x;s->lchild=s->rchild=NULL;if (t=NULL)t=s;elseInsertNode(t,s); scanf("%d",&x);return (t);struc

18、t node * bstsearch(struct node * t, int x)while(t!=NULL)if(x=t->data) return t;else if(x<t->data) t=t->lchild; else t=t->rchild;return NULL;int main()int q;struct node * root;root= CreateBinSortTree();printf("请输入需要找的关键字")；scanf("%d",&q);MiddleOrder(root);if(bstsearch(root,q)!=NULL) printf("n 找到关键字 %dn",q);elseprintf("n没有找到关键字%d n",q);printf("n"