C语言与数据结构实验指导(编辑版.).doc

Harbin Institute of TechnologyC 语言与数据结构实验指导书刘梅 索莹 田文龙哈工大电子与信息工程学院电子工程系实验实验 1 实验平台实验平台一、实验目的1.掌握 Microsoft Visual C+ 6.0 集成环境的使用方法。2.掌握 C 程序在 Microsoft Visual C+ 6.0 开发环境中的编辑、编译、链接和运行全过程二、实验内容1）启动 Microsoft Visual C+ 6.0 开发环境双击桌面应用程序图标或云兄“开始”菜单程序组中的 Microsoft Visual C+ 6.0 应用程序，启动 VC+，如图所示图 1.1 VC+初始界面2）建立 C 源程序文件方法 1：单机工具栏的“新建文本文件”按钮，打开文本文件编辑界面如下图所示图 1.2 文本文件编辑界面方法 2：执行“文件”->“新建”命令，在“文件”选项卡下选择 C+ Source File 文件类型，然后输入 C 源程序文件名和保存文职，如图 所示，然后单击“确定”按钮，打开源程序文件编辑界面，如图 1.4 所示。注意：注意：输入 C 源程序文件名时必须带上扩展“.c” ，否则默认创建的是扩展名为“.cpp”的 C+文件。3）编辑源文件方法 1：在如图 1.2 所示的文本文件编辑界面中输入源程序代码，如图 1.5 所示。方法 2：在如图 1.4 所示的 C 源程序文件编辑界面中编辑源程序代码，如图 1.6所示。图 1.3 新建文件图 1.4 C 源程序文件编辑界面图 1.5 文本文件编辑界面编辑源文件图 1.6 C 源程序编辑界面编辑源文件4）保存源文件源文件编辑结束后，执行“文件”->“保存”命令保存文件，文本文件编辑界面中编辑的源文件保存时必须在文件名后加上扩展名“.c”，否则保存的是扩展名为txt 的文本文件，不能编译运行。5）组件文件执行“组建”->“组建”命令或直接按 F7 功能键或单机工具栏 Build 按钮，可以对源文件进行编译、链接而不运行改程序。当然也可以先执行“组建”->“编译”（快捷键 Ctrl+F7）命令编译文件，再执行“组建”->“组建”（快捷键 F7）命令链接文件。由于 VC+有工作区的要求，所以组建时，系统提示需要建立工作区，如图1.7 所示。单机“是”按钮，系统会自动建立工作区，组建后的结果如图 1.8 所示。图 1.7 提示建立工作区图 1.8 组建源程序结果注意：注意：图 1.8 下方的“组建”信息窗口中的内容说明了组建的结果，必须保证错误（error(s)）数为 0 才能运行程序。6）运行文件执行“组建”->“执行”命令或直接按 Ctrl+F5 键或单机工具栏 BuildExecute 按钮，可以运行程序， 结果显示在用户输出窗口中，如图 1.9 所示。图 1.9 用户输出窗口注意：注意：如果要编辑下一个 C 源程序，由于新建的文件不会自动加入工作区，因此需要先关闭当前工作区。方法是执行“文件”->“关闭工作空间”命令，或者关闭后重新启动 VC+，再按照上述方法建立、编辑新的 C 源文件，让 VC+自动建立工作区。7）运行“加法”程序在 VC+环境中建立并编辑实现加法运算的源程序，然后组建该文件，结果如图 1.10 所示。运行该文件，并按要求输入数据，得到运行结果。图 1.10 VC+环境下组建“加法”程序后的界面实验实验 2 顺序结构程序设计顺序结构程序设计一、实验目的1.掌握上机运行 C 程序的全过程。2.掌握各种格式说明符的使用方法。3.掌握格式输入输出函数 scanf()和 printf()的用法。4.熟悉字符输入输出函数 getchar()和 putchar()的用法。二、实验内容1.格式说明符的使用。创建并编辑输入输出各个类型数据的程序，分析各个格式说明符的作用。2.编写“输入输出字符”程序，功能如下：使用 getchar()函数接收一个字符，用 printf()函数显示；使用 scanf()函数接收一个字符，用 putchar()函数显示。3.编写“求三角形面积”程序，功能如下：输入三角形三边长，求三角形的面积。已知三角形的三边长 a、b、c，则该三角形的面积公式为：09okm 其中，。() / 2sabc4.编写“圆柱体”程序，功能如下：设圆柱体的半径 r=2.5，圆柱高 h=5.0，求出该圆柱体的表面积和体积。要求：用 scanf()函数输入数据，输出时要求有文字说明，取小数点后两位数字。三、实验指导1.格式说明符的使用(参考教材)2. “输入输出字符”程序1）编程分析(1)需要定义字符型变量存放输入的数据；(2)用 scanf()函数输入字符时，要注意不要接收缓冲区中已有的字符。2）参考程序#include “stdio.h“main()char a,b,c;printf(“1.Input a character:n“);a=getchar();c=getchar();printf(“The character is:%cnn“,a);printf(“2.Input a character:n“);scanf(“%c“,printf(“The character is:“);putchar(b);putchar('n');3. “求三角形面积”程序1）编程分析(1)该问题的解决过程如下：定义变量输入三角形三边边长计算面积输出结果(2)需要定义实型（float 或 double）变量存放相应的数据；(3)计算面积需要用到开平方函数 sqrt()，该函数原型包含在头文件 math.h 中，因此需要在程序开始将头文件包含进来；(4)根据实际情况确定各个变量在输出时的宽度和小数位数。2）参考程序#include “stdio.h”#include “math.h”main()float a,b,c,s,area;printf(“Input a,b,c:n”);scanf(“%f ,%f,%f”,s=(a+b+c)/2;area=sqrt(s*s(s-a)*(s-b)*(s-c);printf(“a=%7.2f,b=%7.2f,c=%7.2fn”,a,b,c);printf(“area=%9.2fn”,area);3. “圆柱体”程序1）编程分析(1)该问题的解决过程如下：定义变量输入半径和高计算表面积和体积输出结果(2)需要定义实型（float 或 double）变量存放相应的数据；(3)计算过程中需要用到常数，为使用方便，在程序开始用宏定义命令 define将常数 3.14159（即）用 PI 表示；(4)输出数据时根据要求确定各个变量的宽度和小数位数（本例采用 10.2） 。2）参考程序#include “stdio.h”#define PI 3.14159main()float r,h;double s,v;printf(“Input the value of r and h:n”);scanf(“%f ,%f”,s=2*PI*r*r+2*PI*r*h;v=PI*r*r*h;printf(“The value of s is:%10.2fn”,s);printf(“The value of v is:%10.2fn”,v);实验实验 3 选择结构程序设计选择结构程序设计一、实验目的1.学会使用逻辑表达式表示条件的方法。2.掌握 switch 语句的用法。二、实验内容1.switch 语句的应用编写计算器程序。要求从键盘任意输入两个数值，然后输入一个四则运算符，自动完成运算后输出结果。三、实验指导1.switch 语句的应用1）编程分析(1)四则运算共有加（+） 、减（-） 、乘（*） 、除（/）4 种运算，要做出判断需使用 switch 语句。(2)当输入符号为四则运算之外的符号时，不进行任何运算，但应给出相应的提示信息。当使用提示信息时，switch 语句应含有 default 子句。2）参考程序#include “stdio.h”void main()float x,y;char p;scanf(“%f,%f”,p=getchar();switch(p)case +:printf(“%f+%f=%fn”,x,y,x+y);break;case -:printf(“%f-%f=%fn”,x,y,x-y);break;case *:printf(“%f*%f=%fn”,x,y,x*y);break;case /:printf(“%f/%f=%fn”,x,y,x/y);break;default:printf(“Input is error!n”);3）程序调试调试程序时，+、-、*、/及非四则运算符的情况都应予以调试。实验实验 4 循环结构程序设计循环结构程序设计一、实验目的1.通过本实验，加深对循环控制结构有关概念的理解。2.掌握二重循环结构程序的设计方法。二、实验内容1.阶乘累加问题。编写程序，求 1！+2！+3！+n!的值。2.取彩球问题。有 12 个彩球：3 个白色，5 个红色，4 个黄色，从中任意取 n个球，求出所有不同的取法。12（2n）三、实验指导1.阶乘累加问题1）编程分析(1)本实验内容为求解阶乘问题。(2)求 n!用一个循环即可实现。(3)求 1！+2！+3！+n!的值，需要在求阶乘程序之外增加一个外重循环。2）参考程序#include “stdio.h”void main()long int s=1,t;int i,j,n;printf(“n=”);scanf(“%d”,for(i=2;i=1for(j=0;j=p;q-)/*元素后移*/*(q+1)=*q;*p=n;/*插入数据*/printf(“n 插入数据后的数列：n”);for(p=a,i=0;i=t;q-)/*元素后移*/*(q+1)=*q;*t=x;/*插入数据*/实验实验 8 线性表的顺序存储系统维护线性表的顺序存储系统维护一、实验目的1.掌握线性表的顺序存储的定义和基本使用方法。2.掌握线性表的顺序存储存储单元的排列特点。3.掌握线性表的顺序存储系统的建立、查找 、修改、插入、删除操作，学会相关的函数定义和调用。二、实验内容1.建立一个顺序表。 2.能够对建立的顺序表进行查找、修改、插入、删除等操作。当输入指令错误 时，能够提示错误信息。主函数中可以选择由 switch case 语句构成主菜单，再 根据提示进行相应操作。 3.使用 C 语言程序编写。 三、实验指导1）编程分析(1)在线性表的建立时，可直接用数组赋初值；(2)在查找功能中要实现的功能为：当能找到时该值时返回该值所在节点，找不到时返回-1；(3)修改功能是在查找的基础上，将找到的值加以修改；(4)在插入功能中要实现的功能为：在找到指定节点后，当线性表满时，提示不能插入，当线性表不满时，插入数据；(5)删除功能主要实现：当线性表为空或者删除位置超出线性表长度时，都显示位置错误，其他情形进行删除操作。2）参考程序#include #define max 20int last=20;int nodemax=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19;int find(int find_num);void insert(int insert_pot,int insert_num);void delet(int delete_pot);void modify(int renew_pot,int renew_num);void list_printf();int main()printf(“please enter number:n1,查找n2,删除n3,修改n4,插入n5,退出系统n“);int flag=0;int find_num,delete_pot;int renew_pot,renew_num;int insert_pot,insert_num;int findresult;int choice;doscanf(“%d“,switch(choice)case 1:printf(“please enter the find_numn“);scanf(“%d“,findresult =find(find_num);printf(“findresult=%dn“, findresult);break;case 2:printf(“please enter the delete_pot n“);scanf(“%d“,list_printf();printf(“n“);delet(delete_pot);printf(“after deleten“);list_printf();break;case 3:printf(“please enter the renew_pot and renew_num n“);scanf(“%d %d“,printf(“before modifyn“);list_printf();modify(renew_pot, renew_num);printf(“after modifyn“);list_printf();break;case 4:printf(“please enter the insert_pot and insert_num n“);scanf(“%d %d“,printf(“before insertn“);list_printf();insert(insert_pot, insert_num);printf(“after insertn“);list_printf();break;case 5:flag=1;break;default:printf(“input errorn“);break;while(!flag);return(0);int find(int find_num) /*查找值为 find_num 的节点*/int k=0,findi;int flag=0;findi=0;while(klast-1| delete_pot = insert_pot-1;i-)nodei+1=nodei;nodep-1= insert_num;last=last+1;void list_printf()/*输出表的内容*/int i;for(i=0;i#includestruct Nodeint data;struct Node *next;void Build(struct Node * L) /*建立一个带头结点的单链表*/int n;struct Node *p,*q;p=L;printf(“请输入 n 和 n 个数据元素:n“);scanf(“%d“,while(n-)q=( struct Node *)malloc(sizeof(struct Node);scanf(“%d“,q->next=NULL;p->next=q;p=q;void Print(struct Node * L)/*计算单链表的长度，然后遍历输出单链表*/int num=0;struct Node * p;p=L->next;while(p)num+;printf(“%d “,p->data);p=p->next;printf(“n 长度为%d:n“,num);void Tips()/*选择函数*/printf(“按数字键选择相应操作n“);printf(“ 输出单链表及其长度:n“);printf(“ 查找值为 x 的前驱结点:n“);printf(“ 删除值为 x 的结点:n“);printf(“ 在值为 y 的结点后插入值为 x 的结点:n“);printf(“ 退出:n“);void Find(struct Node * L,int x)/*查找值为 x 的直接前驱结点 p*/struct Node * p;p=L;while( p->next if(p->next)printf(“%d 的前驱结点为:%dn“,x,p->data);elseprintf(“没找到!n“);void Delete(struct Node * L,int x)/*删除值为 x 的结点*/struct Node * p,*q;p=L;while( p->next if(p->next)if(p->next->next)q=p->next;p->next=q->next;free(q);elseq=p->next;p->next=NULL;free(q);printf(“删除成功!n“);elseprintf(“链表中没有%dn“,x);void Insert(struct Node *L, struct Node *x,int y) /*在值为 y 的结点后插入值为 x 的结点*/struct Node *p;p=L;while(p->next!=NULLif(p->data!=y)printf(“No Find Y !“);elsex->next= p->next;p->next=x;printf(“插入成功!n“);int main()int choice,x,y,flag;struct Node * L,*p;L=(struct Node *)malloc(sizeof(struct Node);L->next=NULL;L->data=-1;Build(L);/*建立一个带头结点的单链表*/Tips();/*选择函数*/scanf(“%d“,while(choice)switch(choice)case 1:Print(L); /*计算单链表的长度，然后遍历输出单链表*/break;case 2:printf(“请输入要查找的元素 X:n“);scanf(“%d“,Find(L,x); /*查找*/break;case 3:printf(“请输入要删除的元素 X:n“);scanf(“%d“,Delete(L,x); /*删除*/break;case 4:printf(“请输入要插入的元素 X 及其前结点 Y: (X,Y)n“);scanf(“%d,%d“,p=(struct Node *)malloc(sizeof(struct Node);p->data=x;Insert(L,p,y); /*插入*/break;default:break;Tips();scanf(“%d“, /*下一步操作选择*/return 0;实验实验 10 二叉树的遍历二叉树的遍历一、实验目的1.理解二叉树的原理，掌握二叉树的存储方法。2.掌握二叉树前、中、后序顺序遍历的过程。3.掌握前、中、后序遍历二叉树程序的编写，并用递归与非递归方法分别实现。二、实验内容1.输入数据建立一棵二叉树。 2.输出其前、中、后序遍历的结果，分别用递归与非递归方法实现。 3.使用 C 语言程序编写。 三、实验指导1）编程分析(1)在二叉树的建立时，先用递归算法建立一颗二叉树，以所输入的字母为其数据项，当输入为#时，所对应的节点为空；(2)分别以前、中、后序遍历二叉树，打印相应的节点值。2）参考程序(1)前序非递归遍历二叉树#include#include#define MAX 100struct nodeint data;struct node *llink;struct node *rlink;*shutree=NULL;void preorder(struct node *t);int main()struct node *createtree(struct node *tree);shutree=createtree(shutree);preorder(shutree);return(0);void preorder(struct node *tree)struct node*p;struct node*sMAX;int top;top=-1;p=tree;dowhile(p!=NULL)printf(“ %c“,p->data);if(p->rlink!=NULL)top=top+1;stop=p->rlink;p=p->llink;if(top!=-1)p=stop;top=top-1;while(p!=NULL | top!=-1);struct node *createtree(struct node *tree)char ch;scanf(“%c“,if(ch='=')tree=NULL;elsetree=(struct node *)malloc(sizeof(struct node);tree->data=ch;createtree(tree->llink);createtree(tree->rlink);return(tree);(2)前序递归遍历二叉树void PreOrder(struct node *tree) struct node *p;p=tree;if(p!=NULL) printf(“%c “, root->data); PreOrder(p->lchild); PreOrder(p->rchild); (3)中序非递归遍历二叉树void Inorder(struct node *tree)struct node*p;struct node*sMAX;int top;top=-1;p=tree;dowhile(p!=NULL)if(p->rlink!=NULL)top=top+1;stop=p;p=p->llink;if(top!=-1)p=stop;printf(“ %c“,p->data);top=top-1;p=p->rlink;while(p!=NULL | top!=-1); (4)中序递归遍历二叉树void InOrder(struct node *tree) struct node *p;p=tree;if(p!=NULL) InOder(p->lchild); printf(“%c “, root->data); InOrder(p->rchild); (5)后序非递归遍历二叉树void postorder(struct node *tree)struct node*p;struct node*q=NULL;struct node*sMAX;int top;top=-1;p=tree;dowhile(p!=NULL)if(p->rlink!=NULL)top=top+1;stop=p->rlink;p=p->llink;p= stop;top=top-1;if(p->rlink=NULL| p->rlink=q)printf(“ %c“,p->data);q=p;p=NULL;elsep=p->rlink;while(p!=NULL | top!=-1);(6)后序递归遍历二叉树void PostOrder(struct node *tree) struct node *p;p=tree;if(p!=NULL) PostOrder(p->lchild); PostOrder(p->rchild); printf(“%c “, root->data); 实验实验 11 二叉排序树系统维护二叉排序树系统维护一、实验目的1.掌握二叉排序树定义和基本使用方法。2.掌握二叉排序树存储数据的排列特点。3.掌握二叉排序树系统的建立、插入、查找 、替换、删除操作，学会相关的函数定义和调用。二、实验内容1.输入数据自行建立一棵二叉排序树。 2.能够对建立的二叉排序树进行查找、插入、替换、删除等操作。当输入指令 错误时，能够提示错误信息。主函数中可以选择由 switch case 语句构成主菜单， 再根据提示进行相应操作。 3.使用 C 语言程序编写。 三、实验指导1）编程分析(1)在建立一棵二叉排序树时，可以采用反复调用插入函数直到整个二叉排序树建立完成；(2)查找功能主要实现：若找到返回该节点指针并打印“找到了” ，否则返回空并打印“没找到” ；(3)在删除时，要充分考虑到被删除节点的各种情况：是否有左子女，是否有右子女，是否有双亲；(4)替换功能的实质是将一个节点删除，然后再插入一个新节点。2）参考程序#include #include #include#define MAX 9int aMAX;struct nodeint data;struct node *llink;struct node *rlink;*shutree=NULL,*f,*fp;int main()int n,i,k,x,y;int flag1=0;struct node *find(struct node *tree,int x); /*查找*/struct node *findparents(struct node *tree,int x);/*查找双亲*/struct node *insertree(struct node *tree,int x);/*插入*/struct node *detree(struct node *t,struct node *f,struct node *p); /*删除*/void preorder(struct node *tree);/*前序遍历*/printf(“input datan“);for(i=0;idata=x)f=1;elseif(xdata)p=p->llink;elsep=p->rlink;if(f)q=p;elseq=NULL;return(q);struct node *findparents(struct node *tree,int x)int f;struct node *p,*q;p=tree;q=NULL;f=0;while(!f)elseq=p;if(xdata)p=p->llink;elsep=p->rlink;return(q);struct node *insertree(struct node *tree,int x)struct node *p,*q;if(tree=NULL)p=(struct node *)malloc(sizeof(struct node);p->data=x;p->rlink=NULL;p->llink=NULL;tree=p;elsep=tree;while(p!=NULL)q=p;if(xdata)p=p->llink;elsep=p->rlink;p=(struct node *)malloc(sizeof(struct node);p->data=x;p->rlink=NULL;p->llink=NULL;if(xdata)q->llink=p;elseq->rlink=p;return(tree);struct node *detree(struct node *t,struct node *f,struct node *p)struct node*q,*s;int bol;bol=0;if(p->llink=NULL)|(p->rlink=NULL)if(p->llink=NULL)if(p=t)t=p->rlink;elses=p->rlink;bol=1;elseif(p=t)t=p->llink;elses=p->llink;bol=1;elseq=p;s=q->rlink;while(s->llink!=NULL)q=s;s=s->llink;s->llink=p->llink;if(q!=p)q->llink=s->rlink;s->rlink=p->rlink;if(p=t)t=s;elsebol=1;if(bol=1)if(p=f->llink)f->llink=s;elsef->rlink=s;free(p);return(t);void preorder(struct node*tree)struct node*p;struct node*sMAX;int top;top=-1;p=tree;dowhile(p!=NULL)printf(“ %d“,p->data);if(p->rlink!=NULL)top=top+1;stop=p->rlink;p=p->llink;if(top!=-1)p=stop;top=top-1;while(p!=NULL | top!=-1);printf(“n“);