哈尔滨工业大学计算机软件基础试验报告

1、实验一顺序存储的线性表维护子系统的实现实验报告姓名:吕静学号：6080510228日期：2010.4.21、实验程序/*顺序存储的线性表维护，插入，删除，修改，查找*/#include<stdio.h>#include<stdlib.h>intlast;/*查找函数*/intfind(intx,intnode)inti=0,findi=0;intflag=0;while(i<=last-1)&&(!flag)if(nodei=x)findi=i;flag=1;break;elsei=i+1;if(!flag)findi=-1;return(find

2、i);/*插入函数*/voidinsert(intp,intx,intnode)inti;if(last=40)printf("listisfull");else(for(i=last-1;i>=p;i-)nodei+1=nodei;nodep=x;last=last+1;/*修改函数*/voidchange(intp,intx,intnode)(nodep=x;/*删除函数*/voiddelete(intp,intnode)(inti=0;if(p>last-1|(p<0)printf("positioniswrong");else(

3、for(i=p+1;i<=last-1;i+)nodei-1=nodei;last=last-1;intmain()(/*线性表白生成*/intnode40;inti=0;intx=0;intp=0;/*插入的位置*/intxinsert=0;/*插入的数据*/intpchange=0;/*更改的位置*/intxchange=0;/*更改成德数据*/intpdelete=0;/*删除的位置*/charanswer=0;/*用户选项*/printf("pleaseenterthenumber:");/*到last-1个元素*/一共节点的个数，包括线性表的从0scanf(

4、"%d",&last);printf("pleasureenterthedatas,endingwithentern");for(i=0;i<last;i+)scanf("%d",&nodei);while(1)system("cls");printf("menun1.findn2.insertn3.changen4.deleten5.exit");answer=getchar();switch(answer)case'1':/*查找*/printf(&qu

5、ot;pleaserenterthenumberyouwanttofind");scanf("%d",&x);i=find(x,node);printf("find%d",i+1);/*包括第0个在内的第i个数据，即第i+1个*/getchar();getchar();break;case'2':/*插入*/printf("npleaseenterthepositionyouwanttoinsertbeforewhichpoint?n");/*/插在第几个数据之前？scanf("%d&quo

6、t;,&p);printf("pleasererterthedatayouwanttoinsertn");scanf("%d",&xinsert);insert(p-1,xinsert,node);/*读入第p个，是包括零在内的p-1号节点*/*显示新表*/printf("newlistn");for(i=0;i<last;i+)printf("%dn",nodei);getchar();getchar();break;case'3':/*更改*/printf("wh

7、ichdoyouwanttochange?");/*想更改第几个节点*/scanf("%d",&pchange);printf("changetowhat?");/*改成什么数据*/scanf("%d",&xchange);change(pchange-1,xchange,node);/*读入第p个，是包括零在内的p-1号节点*/*显示新表*/printf("newlistn");for(i=0;i<last;i+)printf("%dn",nodei);getc

8、har();getchar();break;case'4':/*删除*/printf("whichdoyouwanttodelete?");/*想删除第几个节点*/scanf("%d",&pdelete);delete(pdelete-1,node);/*显示新表*/printf("newlistn");for(i=0;i<last;i+)printf("%dn",nodei);getchar();getchar();break;case'5':return0;二、实验

9、过程先键入last的数值6键入6个数值，显示如下I:xhnxingbrnDebugJfianxing.exepleaseenterthenumber：6bleasureenterthedatasendingrwithenterI显示菜单:选才11查找键入要查找的数据4显示4位于线性表的第4位置选才i2插入键入插入位置插入数值后显示新表pleaseentethepoitionyouuanttoinsertbeforevhichpoint?pieaserei*terthedatayouwanttoinsert345neulist12345选才i3更改键入更改的数据位置，改为的数据后显示新表doyo

10、uvanttochange?3:lian9etowhat?234wwlist34选才i4删除键入删除的位置显示新表whichdoyou町anttodelete?3newlist±2345选择5退出程序三、实验分析1,scanf读入数据容错性不好读入数据如果不是合法的，比如用户输入了字母而非数字，该字母将会留在缓冲区中，直到程序结束，每次调用scanf都会试图读入该字母，读入失败后程序继续进行直到结束。即如果用户输入不正确程序即运行失常。为解决这个问题，先用自定义函数，替代scanf/*函数功能：读入整型数，如果非法，提示错误并给出重输的机会直到合法为止能识别各种数字字母混排的非法数据

11、，比检测函数返回值应用广泛，并能识别+-号等，合法符号，充分利用了scanf自带功能。函数参数：无.函数返回值：读入的合法的整型数.*/intgetint(void)(intn=0;intflag=1;charm='0'do(flag=1;scanf("%d",&n);m=getchar();if(m!='n')/*如果为合法输入，留在缓冲区中的一定是回车符，否则是第一个非法字符而不是回车*/(printf("输入有误请重新输入：")；fflush(stdin);/*清除缓冲区存储*/flag=0;while(fl

12、ag=0);returnn;2,请用户输入数组长度时，可能会输入比40(预设数组长度)大的数，导致程序错误，应该予以改进。doif(last>40)printf("toobig,enteragain");scanf("%d,last);while(last>40);循环输入直到合法为止3,如果插入位置不在数组中，删除位置不在数组中，修改元素位置不在数组中查找的元素不存在等都应该予以处理，处理方式与问题2类似，都是判断是否合法，如果不合法，打印信息，提示重新输入，再次读取输入，循环直到合法为止。4,实验时应该注意数组中所谓的元素编号，是从第0个开始，与平

13、时习惯的从一开始不同，即编程算法时的计数与printf输出的信息计数应该是差1的关系，如果不能确定，应该多次试验，如查找结果是i=4应该答应printf:"该数位于第五位”。四、实验结论线性表具有以下特性(1)线性表中所有数据元素，其性质是相同的，即数据类型是一致的。(2)数据元素之间的相对位置是线性的。线性表的线性存储结构能方便的进行，查找和修改操作，但插入和删除需要整个大块元素的搬移，工作量较大，不方便效率低，相对于链式存储具有一定的劣势，但考虑到其仅有数据域不含指针域，能有效节省存储空间，此方面优越于链式存储的线性表，综合以上，选择存储结构时应根据需要选择合适的存储结构。线性表

14、的插入算法示意图：0。35二35二O*3354167小67367.*88却88-2-8次3108。-"33.100,4/125p4。108小4.108.5。140。5心125/加12562氏6/140金14007q7小215第7.215,甑即*山4*务山10口1010.线性表的删除算法示意图:实验二二叉树的前序遍历程序的实现实验报告姓名：吕静学号：6080510228日期:2010.5.28一、实验程序#include<stdio.h>#include<stdlib.h>#definemax30/*函数功能：读入整型数，如果非法，提示错误并给出重输的机会直到合

15、法为止能识别各种数字字母混排的非法数据，比检测函数返回值应用广泛，并能识别+-号等，合法符号，充分利用了scanf自带功能。函数参数：无.函数返回值：读入的合法的整型数.*/intgetint(void)intn=0;intflag=1;charm='0'doflag=1;scanf("%d",&n);m=getchar();if(m!='n')/*如果为合法输入，留在缓冲区中的一定是回车符，否则是第一个非法字符而不是回车*/printf("输入有误请重新输入：")；fflush(stdin);/*清除缓冲区存储*

16、/flag=0;while(flag=0);returnn;/*二叉树的前序遍历*/structtree/*树的结构声明*/(intdata;/*节点数据structtree*left;/*structtree*right;/*)；typedefstructtreetreenode;/*typedeftreenode*btree;/*/指向左子树的指标*/指向右子树的指标*/树的结构型态*/宣告树节点指标型态*/*插入二叉树的节点*/btreeinsertnode(btreeroot,intvalue)(btreenewnode;btreecurrent;btreeback;/*建立新节点记忆

17、体*/newnode=(btree)malloc(sizeof(treenode);newnode->data=value;newnode->left=NULL;newnode->right=NULL;if(root=NULL)(returnnewnode;)else(current=root;/*保留*/while(current!=NULL)back=current;/*if(current->data>value)/*current=current->left;/*elsecurrent=current->right;/*if(back->

18、data>value)back->left=newnode;/*elseback->right=newnode;/*保留父节点指标*/比较*/左子树*/右子树*/左子树*/右子树*/returnroot;/*建立二叉树*/btreecreatebtree(int*data,intlen)(btreeroot=NULL;/*树根指标*/inti;for(i=0;i<len;i+)/*用回路建立树状结构*/root=insertnode(root,datai);returnroot;/*二叉树前序遍历*/voidpreorder(structtree*root)(struc

19、ttree*p;structtree*smax;inttop;top=-1;p=root;do(while(p!=NULL)(printf("%d",p->data);if(p->right!=NULL)(top=top+1;stop=p->right;p=p->left;if(top!=-1)(p=stop;top=top-1;while(p!=NULL)|(top!=-1);/*主程序*/intmain()(btreeroot=NULL;/*树根指标*/intn=0,i=0;/*二叉树节点数据*/intdatamax=0;printf("

20、;请输入你要插入的树的节点的个数n:");n=getint();while(n>30)(printf("输入有误，请重新输入");n=getint();)printf("请输入保存在节点的数据值n");for(i=0;i<n;i+)(datai=getint();)root=createbtree(data,n);printf("前序遍历法得到的树的节点内容n");preorder(root);return0;)二、实验过程首先输入树节点的个数：输入9,即要建立的二叉树有9各节点。然后输入保存在节点中的数值输入后

21、，程序按照建立二叉排序树的方法，存储这九个数到一个二叉树中，小于节点数值的,存储到左子数中，大于节点数值的存储于又子数中存储顺序：4/35/17/0689然后程序对已建立的二叉树进行前序遍历，若二叉树为空，则退出，否则：(1)访问根结点；(2)遍历左子树；(3)遍历右子树；(4)返回。输出结果：431057689。如图：请输入你要插入的树的节点的个数=9请输入保存在节点的数据值前序谪历法得到的树的节点内容31057689>ocessreturned0(0x0>executiontinte:22.384sressanykieytncontinue.三、实验分析故有算法的基础上增加了非

22、法字符处理函数getint该函数充分利用了scanf的自带功能能读入合法的整形数，对于非法输入，则根据缓冲区留下的字符不是“n”进行判断，然后清楚缓冲存储，循环输入，直到用户输入的为合法字符为止。函数getint()的加入增加了程序的稳定性。程序开始时先定义二叉树每个节点的结构体形式，由三部分构成，数据域，左指针，右指针。然后建立二叉树，反复调用插入节点的算法，直至把数据完全存储，按定二叉排序树里每个结点的左子树中结点的码值都小于该结点的码值，而右子树中结点的码值都大于此结点的码值。而后按照前序遍历的方法，逐个访问节点并打印。四、实验结论前序遍历方法简单，高效。本实验有效地完成了二叉树的建立，

23、前序遍历的任务，掌握了建立二叉排序树，对二叉树进行前序遍历的方法。实验三二叉排序树维护子系统实现实验报告姓名：吕静学号：6080510228日期：2010.5.5、实验程序#include<stdio.h>#include<stdlib.h>#definemax30/*函数功能：读入整型数，如果非法，提示错误并给出重输的机会直到合法为止能识别各种数字字母混排的非法数据，比检测函数返回值应用广泛，并能识别+-号等，合法符号，充分利用了scanf自带功能。函数参数：无.函数返回值：读入的合法的整型数.*/intgetint(void)intn=0;intflag=1;cha

24、rm='0'doflag=1;scanf("%d",&n);m=getchar();if(m!='n')/*如果为合法输入，留在缓冲区中的一定是回车符，否则是第一个非法字符而不是回车*/printf("输入有误请重新输入：")；fflush(stdin);/*清除缓冲区存储*/flag=0;while(flag=0);returnn;*/*/指向左子树的指标*/指向右子树的指标*/树的结构型态*/宣告树节点指标型态*/structtree/*树的结构声明(intdata;/*节点数据structtree*left;

25、/*structtree*right;/*)；typedefstructtreetreenode;/*typedeftreenode*btree;/*/*插入二叉树的节点*/btreeinsertnode(btreeroot,intvalue)(btreenewnode;btreecurrent;btreeback;/*建立新节点记忆体*/newnode=(btree)malloc(sizeof(treenode);newnode->data=value;newnode->left=NULL;newnode->right=NULL;if(root=NULL)(returnne

26、wnode;)else(current=root;/*保留*/while(current!=NULL)(back=current;/*保留父节点指标*/if(current->data>value)/*比较*/current=current->left;/*左子树*/elsecurrent=current->right;/*右子树*/if(back->data>value)back->left=newnode;/*左子树*/elseback->right=newnode;/*右子树*/returnroot;/*建立二叉树*/btreecreate

27、btree(int*data,intlen)(btreeroot=NULL;/*树根指标*/inti;*/for(i=0;i<len;i+)/*用回路建立树状结构root=insertnode(root,datai);returnroot;/*二叉树前序遍历*/voidpreorder(structtree*root)(structtree*p;structtree*smax;inttop;top=-1;p=root;do(while(p!=NULL)(printf("%d",p->data);if(p->right!=NULL)(top=top+1;st

28、op=p->right;p=p->left;if(top!=-1)(p=stop;top=top-1;while(p!=NULL)|(top!=-1);/*二叉树查找算法*/structtree*find(structtree*btree,intx)(intf;structtree*p,*q;p=btree;f=0;while(!f)&&(p!=NULL)(if(p->data=x)f=1;else(if(x<p->data)p=p->left;elsep=p->right;)if(f)q=p;elseq=NULL;return(q);

29、)/*二叉树插入算法*/voidinsertree(structtree*btree,intx)structtree*p;structtree*q;if(btree=NULL)p=(structtree*)malloc(sizeof(structtree);p->data=x;p->right=NULL;p->left=NULL;btree=p;)elsep=btree;while(p!=NULL)q=p;if(x<p->data)p=p->left;elsep=p->right;)p=(structtree*)malloc(sizeof(struct

30、tree);p->data=x;p->right=NULL;p->left=NULL;if(x<q->data)q->left=p;elseq->right=p;/*二叉树查找父节点算法*/structtree*findp(structtree*btree,intx)intf;structtree*p,*q;p=btree;f=0;while(!f)&&(p!=NULL)if(p->data=x)f=1;elseq=p;if(x<p->data)p=p->left;elsep=p->right;return

31、(q);voidDelete(structtree*t,structtree*f,structtree*p)structtree*q,*s;intbool;bool=0;if(p->left=NULL)|(p->right=NULL)(if(p->left=NULL)(if(p=t)t=p->right;else(s=p->right;bool=1;else(if(p=t)t=p->left;else(s=p->left;bool=1;else(q=p;s=q->right;while(s->left!=NULL)(q=s;s=s->

32、left;s->left=p->left;if(q!=p)(q->left=s->right;s->right=p->right;)if(P=t)t=s;elsebool=1;)if(bool=1)(if(p=f->left)f->left=s;elsef->right=s;)free(p);)/*主程序*/intmain()(btreeroot=NULL;/*树根指标*/intn=0,i=0;intx;/*查找目标*/intinsert1=0;intdele1=0;structtree*find1;structtree*parent;st

33、ructtree*p;charanswer;/*二叉树节点数据*/intdatamax=0;printf("请输入你要插入的树的节点的个数n:");n=getint();printf("请输入保存在节点的数据值n");for(i=0;i<n;i+)(datai=getint();)root=createbtree(data,n);printf("前序遍历法得到的树的节点内容n");preorder(root);getchar();while(1)(system("cls");printf("menu

34、n1.findn2.insertn3.changen4.deleten5.exit");answer=getchar();switch(answer)(case'1':/*查找*/printf("pleaserenterthenumberyouwanttofind");scanf("%d",&x);find1=find(root,x);if(find1!=NULL)(printf("找到n");)elseprintf("没有找到n");getchar();getchar();bre

35、ak;case'2':/*插入*/printf("插入什么内容？n");insert1=getint();insertree(root,insertl);/*显示新表*/printf("前序遍历法得到的树的节点内容n");preorder(root);getchar();getchar();break;case'3':/*更改*/printf("您想要更改哪个数？n");x=getint();find1=find(root,x);if(find1!=NULL)printf("找到您想要更改它为

36、什么数值：");parent=findp(root,dele1);p=find(root,dele1);Delete(root,parent,p);x=getint();insertree(root,x);elseprintf("没有找到n");printf("前序遍历法得到的树的节点内容n");preorder(root);getchar();getchar();break;case'4':/*删除*/printf("n删除节点：");dele1=getint();parent=findp(root,del

37、e1);p=find(root,dele1);Delete(root,parent,p);printf("前序遍历法得到的树的节点内容！n");preorder(root);getchar();getchar();break;case'5':return0;、实验过程输入插入节点个数8和节点数据4,3,6,8,0,1,2,5程序读入节点值，建立二叉排序树然后前序遍历显示节点内容得到如下结果:然后进入菜单选项，选择1查找，程序询问查找的内容，输入数字6程序按照大小比较的方法查找，找到了该数，返回地址不为空，显示“找到”ienu1-Find2+inserti.c

38、hange4 -delete5 .exit!aserentei1thenumberyouwarn；tofind6戋至u如果查找对象是12即树中不存在的数字，程序按照比较大小的方法查找，返回指针为空,显示“没有找到”menul.find1.1 nsert1 .change2 .delets3 .exit1pleaserenterthenumheryou.wanttofind12沿有找到循环执行程序，返回菜单，选则2进行插入操作，输入插入的数字7,程序在数中合适的位置插入一个节点7,然后进行前序遍历menu,find.insert.change.delete.exit2插入什么内容？前序遍历法得到的树的节点内容43012658?此