数据结构课程设计

安徽农业大学·信息与计算机学院·《数据结构课程设计》

平衡二叉树的函数，其时间复杂度均与以上情况类似，等于O（n）。

（4）删除函数不采用递归手法，而是采用重新建立一颗不含要删结点的二插排序树。其时间复杂度＝O（n）。

6 心得和总结

这次课程设计作业我选择做数据结构是出于我对用高级语言编程的极大兴趣。通过这次实验我也着实又感受了一次编程的乐趣，从中也学到了不少知识。

虽然都说“程序＝数据结构＋算法”，但我在学习运用数据结构编程之前，并没能深刻体会到这一点，直到这次课设实践。

我感受最深的一点是：以前用C编程，只是注重如何编写函数能够完成所需要的功能，似乎没有明确的战术，只是凭单纯的意识和简单的语句来堆砌出一段程序。感觉有点像张飞打仗，有勇无谋，只要能完成任务就行。但现在编程感觉完全不同了。在编写一个程序之前，自己能够主动的综合考虑各种因素，首先选取自己需要的数据结构，是树还是图或是别的什么？然后选定一种或几种存储结构来具体的决定后面的函数的主要风格。最后在编写每一个函数之前，可以仔细斟酌比对，挑选出最适合当前状况的算法。这样，即使在完整的程序还没有写出来之前，自己心中已经有了明确的原图了。这样无形中就提高了自己编写的程序的质量。

另外，我还体会到深刻理解数据结构的重要性。只有真正理解这样定义数据类型的好处，才能用好这样一种数据结构。了解典型数据结构的性质是非常有用的，它往往是编写程序的关键。

我以前对递归算法一直很害怕，总是看不明白究竟这递归是怎么进行的。在这次实验中我终于克服了这一障碍，一次次单步执行书中递归函数的例子，并一遍遍在心中自己默默的走，终于弄明白了，真的是功夫不负有心人啊！同时我还根据自己的理解写出了类似的递归函数实现了新的功能，真是受益良多啊！

在这次实验中，我对参数的调用也进行了很多种尝试，已经能够相对准确的选择合适的参数形式来实现函数之间的数据传输交互了。

这次实验中我也出现过一些比较严重的错误。在用一维数组顺序表结构编写程序时我错误的运用静态链表来实现函数功能。这是我对基本概念理解的模糊不清造成的。我原以为只要采用一维数组作为存储结构它就一定也是顺序表结构，而实质上这根本是两个不相干的概念。后来在同学的指点下我意识到自己的错误。不过收获也很不少。至少我又练习了运用静态链表来实现同样的功能，同时我也发现两者在很多函数上是互通的，只需稍作修改即可移植。

总之，我会继续我的兴趣编写程序的，相信在越来越多的尝试之后，自己会不断进步不断提高的。

第 21 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

7 源程序清单

(1) 二插链表存储结构源程序清单： #include typedef struct Tnode{

int data; /*输入的数据*/ struct Tnode *lchild,*rchild;

/*结点的左右指针，分别指向结点的左右孩子*/ }*node,BSTnode;

searchBST(node t,int key,node f,node *p) /*查找函数*/ {

if(!t) {*p=f;return (0);} /*查找不成功*/ else if(key==t->data) {*p=t;return (1);} /*查找成功*/

else if(keydata) searchBST(t->lchild,key,t,p); /*在左子树中继续查找*/ else searchBST(t->rchild,key,t,p); /*在右子树中继续查找*/ }

insertBST(node *t,int key) /*插入函数*/ {

node p=NULL,s=NULL;

if(!searchBST(*t,key,NULL,&p)) /*查找不成功*/ {

s=(node)malloc(sizeof(BSTnode)); s->data=key;

s->lchild=s->rchild=NULL; if(!p) *t=s; /*被插结点*s为新的根结点*/

else if(keydata) p->lchild=s; /*被插结点*s为左孩子*/ else p->rchild=s; /*被插结点*s为右孩子*/ return (1); } else return (0); /*树中已有关键字相同的结点，不再插入*/ }

inorderTraverse(node *t) /*中序遍历函数*/ { if(*t){

if(inorderTraverse(&(*t)->lchild)) /*中序遍历根的左子树*/ {

printf(\\ /*输出根结点*/

if(inorderTraverse(&(*t)->rchild)); /*中序遍历根的右子树*/ }

第 22 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

}

else return(1); }

calculateASL(node *t,int *s,int *j,int i) /*计算平均查找长度*/ { if(*t){

i++; /*i记录当前结点的在当前树中的深度*/ *s=*s+i; /*s记录已遍历过的点的深度之和*/

if(calculateASL(&(*t)->lchild,s,j,i)) /*计算左子树的ASL*/ {

(*j)++; /*j记录树中结点的数目*/

if(calculateASL(&(*t)->rchild,s,j,i)) /*计算右子树的ASL*/ i--; return(1);} } }

else return(1); }

node Delete(node t,int key) /*删除函数*/ {

node p=t,q=NULL,s,f;

while(p!=NULL) /*查找要删除的点*/ {

if(p->data==key) break; q=p;

if(p->data>key) p=p->lchild; else p=p->rchild; }

if(p==NULL) return t; /*查找失败*/

if(p->lchild==NULL) /*p指向当前要删除的结点*/ {

if(q==NULL) t=p->rchild; /*q指向要删结点的父母*/

else if(q->lchild==p) q->lchild=p->rchild; /*p为q的左孩子*/ else q->rchild=p->rchild; /*p为q的右孩子*/ free(p); }

else{ /*p的左孩子不为空*/ f=p;

第 23 页 共 30 页

安徽农业大学·信息与计算机学院·《数据结构课程设计》

s=p->lchild;

while(s->rchild) /*左拐后向右走到底*/ { f=s; s=s->rchild; }

if(f==p) f->lchild=s->lchild; /*重接f的左子树*/ else f->rchild=s->lchild; /*重接f的右子树*/ p->data=s->data; free (s); } return t; }

int balanceBST(node t,int *i) /*判断是否为平衡二叉树的函数*/ {

int dep1,dep2; if(!t) return(0); else {

dep1=balanceBST(t->lchild,i); dep2=balanceBST(t->rchild,i); }

if((dep1-dep2)>1||(dep1-dep2)<-1) *i=dep1-dep2; /*用i值记录是否存在不平衡现象*/ if(dep1>dep2) return(dep1+1); else return(dep2+1); }

void main() {

node T=NULL; int num; int s=0,j=0,i=0; int ch=0; node p=NULL;

printf(\ do{

scanf(\

if(!num) printf(\ else insertBST(&T,num); }while(num);

第 24 页 共 30 页