struct BiTree {char data; struct BiTree *lchild; struct BiTree *rchild; }; struct BiTree* CreatBiTree() { char x; struct BiTree* p; scanf(\"%c\if(x!='.') {p=(struct BiTree*)malloc(sizeof(struct BiTree)); p->data=x; p->lchild=CreatBiTree(); p->rchild=CreatBiTree(); } else p=NULL; return p; } int LeafNum(struct BiTree *T) {if(!T)return 0; else if(!T->lchild&&!T->rchild)return 1;else return LeafNum(T->lchild)+LeafNum(T->rchild); } int main() {int num; struct BiTree* T; printf(\"请输入树:\\n\"); T=CreatBiTree(); while(T==NULL) { printf(\"empoty,again:\\n\"); T=CreatBiTree();} num=LeafNum(T); printf(\"\\n这颗树的叶子节点是:%d\\n\return 0; } 五、实验数据记录和处理 六、实验结果与分析 该程序时间复杂度为log(n)，比较理想，空间复杂度也比较小。程序简单易行，便于理解与执行。 七、讨论、心得 构建树的时候没有纠错机制，可以加入，如果输入错误可以重新输入或者撤销输入
图结构 一、实验目的和要求 熟悉图的存储结构，掌握有关算法的实现，了解图在计算机科学及其他工程技术中的应用。 二、实验内容和原理 简述题目要解决的问题是什么，并说明输入和输出数据的形式。 采用邻接表存储结构，编写一个求无向图的连通分量个数的算法。 首先按照邻接表的存储方法，构建起图。图构建完成后从键盘输入两个数字进行判断， 如果在由邻接表构建起来的无向图中这两个顶点不相连，则输出不存在从i到j的路径， 否则输出 存在从i到j路径 三、主要仪器设备 使用的计算机：硬件配置：计算机、软件环境：VC++6.0 四、操作方法与实验步骤 列出调试通过的源程序。 #include \"stdio.h\" #include \"malloc.h\" #include \"conio.h\" typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; int in; }ArcNode; typedef struct VNode{ int data; ArcNode *firstarc; }VNode,AdjList[20]; typedef struct ALGraph{ AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; int n,i,j; int m=0; int s=1; ALGraph *graph; void read(ArcNode *firstarc){ int x;
char y; scanf(\"%c\while(y==' ') scanf(\"%c\firstarc->nextarc=NULL; if(y=='\\n'){ return; } else{ x=(int)y-48; ArcNode *t; t=new ArcNode; t->nextarc=NULL; t->in=0; t->adjvex=x; firstarc->nextarc=t; read(firstarc->nextarc); } } void mkgraph(ALGraph *graph){ char rub; ArcNode *t; VNode *list; scanf(\"%c\for(;s<=n;s++){ printf(\"%d =new ArcNode; graph->vertices[s].firstarc=t; read(graph->vertices[s].firstarc); } } void run(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); } int main(){ graph=new ALGraph; printf(\"图中有几个顶点:\"); scanf(\"%d\printf(\"请以邻接表方式依次输入各顶点的关系以回车作为结束标志:\\n\"); mkgraph(graph); printf(\"已为您生成图.\\n\\n请输入您要寻找路径的起点i和终点j(i!=j):\"); scanf(\"%d%d\while(i==j||i<=0||i>n||j<=0||j>n){ printf(\"对不起,您输入的数据有误,请重新输入:\"); scanf(\"%d%d\} run(graph->vertices[i].firstarc->nextarc); if(m==1) printf(\"存在从%d到%d的路径.\else printf(\"不存在从%d到%d的路径.\getch(); } 五、实验数据记录和处理 六、实验结果与分析 此程序对于任何两条边，判断是否连同的时候要遍历此节点的所有的边，时间负责度为o（n）。空间复杂度为0 七、讨论、心得
单链表构建图的思想使得关于图的程序被简化了，没有那么生涩难懂了。
查找 一、实验目的和要求 通过本次实验，掌握查找表上的有关查找方法，并分析时间复杂度。 二、实验内容和原理 试将折半查找的算法改写成递归算法。 按照递增顺序输入一串数字，按照递归折半查找查找要查的数字，如果存在，则输出此位置，否则则输出此数字不存在 三、主要仪器设备 使用的计算机：硬件配置：计算机、软件环境：VC++6.0 四、操作方法与实验步骤 #include\"stdio.h\" typedef struct { int a[30]; int length; } sqtable; sqtable st; int b=0; void createst(int k) { int i; printf(\"请输入:\"); st.a[0]=-100; for (i=1;(!b&&(i<=k));i++) { scanf(\"%d\ if (st.a[i]} } int stfind(sqtable st,int l,int h,int y) { int m; while (l<=h) { m=(l+h)/2; if (y==st.a[m]) return m; else if (y五、实验数据记录和处理 六、实验结果与分析 该程序结构算法简单，易于理解，时间复杂度为o（n^2）,空间复杂度比较低。 七、讨论、心得 折半查找可以节省更多的效率，更快的找到要找的元素内排序 一、实验目的和要求 通过本次实验，掌握线性表的排序方法，并分析时间复杂度。 二、实验内容和原理 设计一个用链表表示的直接选择排序算法，并用程序实现。 已知待排序初始序列用单链表存贮，头指针head指向第一个结点，从这个待排序列中找出最小结点，插入head之后，用r来指示。r以前为已排序序列，r以后为未排序序列。再从未排序序列中找出最小结点插入r的后面，让r指向这个结点。反复执行这个过程，直到排好序。 三、主要仪器设备 使用的计算机：硬件配置：计算机、软件环境：VC++6.0 #include #include #include typedef struct node{ int x; struct node *next; }NODE; void read(NODE *head,int n){ if(n==0) return; int x; NODE *p; p=(NODE*)malloc(sizeof(NODE)); head->next=p; scanf(\"%d\p->x=x; read(p,n-1); } void write(NODE *head,int n){ NODE *p; if(n==0) return; p=head->next; printf(\"%d \write(p,n-1); } void px(NODE *head,int n){ if(n==0) return; int min; int i,s=0; NODE *p; NODE *r; NODE *t; p=head->next; r=head->next; t=head; min=p->x; for(i=0;ip->x){ min=p->x; r=p; s=i; } p=p->next; } for(i=0;inext; t->next=r->next; r->next=head->next; head->next=r; px(head->next,n-1); } void main(){ int n; NODE *head; head=(NODE *)malloc(sizeof(NODE)); printf(\"输入个数n:\"); scanf(\"%d\printf(\"输入%d个数据:\\n\read(head,n); printf(\"您输入的数据为:\\n\"); write(head,n); printf(\"\\n排序后的数据为:\\n\"); px(head,n); write(head,n); getch(); }五、实验数据记录和处理 六、实验结果与分析 该程序比较长，但是算法还比较清晰，时间复杂度为O（n），比较理想。空间复杂度犹豫额外空间不多，所以也不高。第二题的算法较短，时间复杂度为O（n），也比较理想。 七、讨论、心得 该程序比较困难，尤其是用两个指针变量作为首排序和末排序，理解比较困难。
