计算机软件技术基础实验指导书06版

《计算机软件技术基础》实验指导书内蒙古工业大学信息工程学院计算机系2009年3月1日赵俊生编2《计算机软件技术基础》实验教学大纲一、基本信息课程编码020213050课程学时56课程类别技术基础课实验总学时4开出学期第六学期开出单位信息学院计算机系适用专业自动化、电子信息工程、通信工程二、实验安排序号实验项目实验学时每组人数实验类型开出要求1线性表的建立与遍历21验证性必做２二叉树的建立与遍历21验证性必做三、实验目的、内容与要求实验一线性表的建立与遍历（一）实验目的进一步理解线性表的逻辑结构和存储结构，掌握线性表的建立与遍历算法。（二）实验内容1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。2、给定一个输入序列，建立线性链表，访问输出线性链表中各结点的内容。（三）实验要求1、掌握线性表的建立与遍历算法的实现；2、根据实验内容，用C语言编程实现，上机调试运行得出实验结果；3、写出预习报告和实验报告。实验二二叉树的建立与遍历（一）实验目的进一步理解二叉树的逻辑结构和存储结构，掌握二叉树的建立与遍历算法。（二）实验内容1、用二叉链表创建二叉树①输入根结点值；②若左子树不空，则输入左子树，否则输入一个结束符；③若右子树不空，则输入右子树，否则输入一个结束符。例如：FCA▲▲DB▲▲▲E▲GH▲▲P▲▲其中▲表示结束符2、遍历该二叉树(1)前序遍历(DLR)若二叉树为空，则结束返回。否则：①访问根结点；②前序遍历左子树；③前序遍历右子树。(2)中序遍历(LDR)若二叉树为空，则结束返回。否则：①中序遍历左子树；3②访问根结点；③中序遍历左子树。(3)后序遍历(LRD)若二叉树为空，则结束返回。否则：①后序遍历左子树；②后序遍历左子树；③访问根结点。（三）实验要求1、掌握二叉树的建立与遍历算法的实现；2、根据实验内容，用C语言编程实现，上机调试运行得出实验结果；3、写出预习报告和实验报告。四、考核方式根据实验课考勤、课前预习情况、课上实验能力、原型系统效果验收与实验报告的完成情况确定最终的实验成绩，实验成绩占课程总成绩的10%。五、建议教材与教学参考书1、课程教材[1]沈被娜等编.《计算机软件技术基础》（第三版）.北京.清华大学出版社.20002、实验指导书[1]计算机软件技术基础实验指导书.赵俊生（自编）.2009六、编制说明编制者：赵俊生组长：赵俊生执笔人：赵俊生编制时间：2009年3月4实验一线性表的建立与遍历一、实验目的进一步理解线性表的逻辑结构和存储结构，掌握线性表的建立与遍历算法二、实验题目线性表的建立与遍历三、实验类型验证性四、实验内容1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。2、给定一个输入序列，建立线性链表，访问输出线性链表中各结点的内容。五、实验要求根据实验内容，用C语言编程实现，上机调试运行得出实验结果，写出实验报告。六、实验提示1、线性结构中的所有结点按它们之间的关系可以排成一个线性序列：k1，k2，…，kn其中k1是开始结点，kn是终端结点，ki是ki+1的前驱结点，而ki+1是ki的后继结点(i=1，2，…，n-1)。通常把上述线性序列称为“线性表”，把线性结构中的结点称为元素或“表目”。将一个线性表存放到计算机中，可以采用不同的方法，其中最简单而自然的就是顺序的方法，即把表目按其索引值从小到大一个接一个地存放在相邻的单元里。顺序方法存储的线性表简称“顺序表”，顺序表是一种紧凑结构。2、常用的链表有单链表和双链表。在单链表中分配给每个结点的存储单元可分为两个部分：一部分存放结点的数据，称为data域，另一部分存放指向结点后续结点的指针，称为next域，终端结点没有后继结点，其next域为NULL，在计算机中可以表示成零或负数，另外还需要一个表头变量head指向链表的第一个结点。七、实验报告1、写出每个算法的思想。2、画出算法流程图。3、调试程序出现的问题及解决的方法。4、打印实验报告及程序清单。5、报告给出测试的结果并写出实验体会。6、报告按信息学院统一格式书写。八、范例参考1、顺序表①向量的建立向量的定义如下：typedefElemTypevector[n0]输入n个整数，产生一个存储这些整数的向量A的函数如下：voidcreate(A,n)vectorA;intn;{5inti;for(i=1;i=n;i++)scanf(“%d”,A[i]);}②向量的插入在一个有n个元素的向量A中的第i个元素之前插入一个元素x的函数如下：voidinsert(A,n,x)vectorA;intn,x;{intj;if(i1||in)printf(“i值错误！\n”);else{for(j=n;j=i;j--)A[j+1]=A[j];/*将第i个元素及其后的元素后移*/A[i]=x;n++;/*向量长度增1*/}}③向量的删除在一个有n个元素的向量A中删除第i个元素的函数如下：voiddelete(A,n)vectorA;intn;{intj;if(i1||in)printf(i值错误！\n);else{for(j=i;j=n;j++)A[j]=A[j+1];/*将第i个元素之后的元素前移*/n--;}}④向量的查找在一个有n个元素的向量A中查找元素值为x的元素的函数如下：voidfind(A,n,x)vectorA;intn,x;{inti;i=1;while(i=n&&A[i]x)i++;if(i=n)printf(找到了！\n);6elseprintf(未找到！\n);}2、链表①建立一个单链表(方法一）单链表的结点类型node定义如下：typedefstructlinknode{ElemTypedata;structlinknode*next;}node;输入一系列整数，以0标志结束，将这些整数作为data域建立一个单链表的函数如下：voidcreat(){node*head,*p,*s;intx,cycle=1;/*cycle是循环控制变量*/head=(node*)malloc(sizeof(node));/*建立头结点，由head所指向*/p=head;while(cycle){scanf(%d,&x);if(x!=0){s=(node*)malloc(sizeof(node));/*建立下一个结点，由s所指向*/s-data=x;p-next=s;p=s;}elsecycle=0;}head=head-next;/*删除头结点*/p-next=NULL;}②查找某个结点在已建立好的单链表（表头指针为head）中查找元素值为x的函数如下：voidfind(head,x)node*head;intx;{node*p;p=head;while(p-data!=x&&p!=NULL)p=p-next;if(p!=NULL)printf(结点找到了！\n);7elseprintf(结点未找到！\n);}③求单链表的长度计算一个已建立好的单链表（表头指针为head）的结点个数的函数如下：intlength(head)nodehead;{intn=0;node*p;p=head;while(p!=NULL){p=p-next;n++;}return(n);}④在单链表中插入一个结点在单链表中第i个结点(i≥0)之后插入一个元素为x的结点的函数如下：voidinsert(head,i,x)node*head;inti,x;{node*s,*p;intj;s=(node*)malloc(sizeof(node));/*建立一个待插入的结点s*/s-data=x;if(i==0)/*如果i=0,则将s所指结点插入到表头后返回*/{s-next=head;head=s;}else{p=head;j=1;/*在单链表中查找第i个结点，由p所指向*/while(p!=NULL&&ji){j++;p=p-next;}if(p!=NULL)/*若查找成功，则把s插入到其后*/{s-next=p-next;p-next=s;8}elseprintf(未找到！\n);}}⑤从单链表中删除一个结点从单链表中删除一个其值等于给定值x的结点的函数如下：voiddelete(head,x)node*head;intx;{node*p,*q;if(head==NULL)printf(链表下溢！\n);/*如果单链表为空，则下溢处理*/if(head-data==x)/*如果表头结点值等于x值，则删除之*/{p=head;head=head-next;free(p);}else{q=head;p=head-next;/*从第二个结点开始查找其值为x的结点*/while(p!=NULL&&p-data!=x)if(p-data!=x)/*在查找时，p指向该结点，q指向其前一结点*/{q=p;p=p-next;}if(p!=NULL)/*若找到了该结点，则进行删除处理*/{q-next=p-next;free(p);}else/*未找到时，显示相应信息*/printf(未找到！\n);}}⑥建立、遍历单链表(方法二）intcount_nohead(LINKLIST*head){/*不带头结点的单链表：输出单链表元素值并计数*/inti=0;LINKLIST*p;p=head;printf(输出单链表元素值:);while(p!=NULL)9{printf(%c,p-data);i++;p=p-next;}printf(\n);returni;}intcount_head(LINKLIST*head){/*带头结点的单链表：输出单链表元素值并计数*/inti=0;LINKLIST*p;p=head-next;printf(输出单链表元素值:);while(p!=NULL){printf(%c,p-data);i++;p=p-next;}printf(\n);returni;}LINKLIST*creatlink_nohead_head(LINKLIST*head){/*用头插入法建立不带头结点的单链表*/LINKLIST*t;charch;printf(单链表元素值为单个字符,连续输入，$为结束字符:);while((ch=getchar())!='$'){t=(LINKLIST*)malloc(sizeof(LINKLIST));t-data=ch;t-next=head;head=t;}return(head);}LINKLIST*creatlink_head_head(LINKLIST*head){/*用头插入法建立带头结点的单链表*/LINKLIST*t;charch;t=(LINKLIST*)malloc(sizeof(LINKLIST));head=t;t-next=NULL;printf(单链表元素值为单个字符,连续输入，$为结束字符:);10while((ch=getchar())!='$'){t=(LINKLIST*)malloc(sizeof(LINKLIST));t-data=ch;t-next=head-next;head-next=t;}return(head);}LINKLIST*creatlink_nohead_rail(LINKLIST*head){/*用尾插入法建立不带头结点的单链表*/LINKLIST*last,*t;charch;last=head;printf(单链表元素值为单个字符,连续输入，$为结束字符:);while((ch=getchar())!='$'){t=(LINKLIST*)malloc(sizeof(LINKLIST));t-data=ch;t-next=NULL;if(head==NULL){head=t;last=t;}else{last-next=t;last=t;}}return(head);}LINKLIST*creatlink_head_