《计算机软件技术基础指导书》由会员分享，可在线阅读，更多相关《计算机软件技术基础指导书（19页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础实验指导书内 蒙 古 工 业 大 学 信 息 工 程 学 院 计 算 机 系2009 年 3 月 1 日赵俊生 编2计算机软件技术基础实验教学大纲 一、基本信息课程编码 020213050 课程学时 56课程类别 技术基础课 实验总学时 4 开出学期 第六学期开出单位 信息学院计算机系 适用专业 自动化、电子信息工程、通信工程二、实验安排序号 实 验 项 目实验学时每组人数实验类型开出要求1 线性表的建立与遍历 2 1 验证性 必做 二叉树的建立与遍历 2 1 验证性 必做三、实验目的、内容与要求实验一 线性表的建立与遍历（一） 实验目的进一步理解线性表的逻辑结构和存储结构，
2、掌握线性表的建立与遍历算法。（二） 实验内容1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。2、给定一个输入序列，建立线性链表，访问输出线性链表中各结点的内容。（三） 实验要求1、掌握线性表的建立与遍历算法的实现；2、根据实验内容，用 C 语言编程实现，上机调试运行得出实验结果；3、写出预习报告和实验报告。实验二 二叉树的建立与遍历（一） 实验目的进一步理解二叉树的逻辑结构和存储结构，掌握二叉树的建立与遍历算法。（二） 实验内容1、 用二叉链表创建二叉树输入根结点值；若左子树不空，则输入左子树，否则输入一个结束符；若右子树不空，则输入右子树，否则输入一个结束符。例如：FCA D
3、BEGHP 其中表示结束符2、遍历该二叉树(1) 前序遍历(DLR)若二叉树为空，则结束返回。否则：访问根结点；前序遍历左子树；前序遍历右子树。(2) 中序遍历(LDR)若二叉树为空，则结束返回。否则：中序遍历左子树；3访问根结点；中序遍历左子树。(3) 后序遍历(LRD)若二叉树为空，则结束返回。否则：后序遍历左子树；后序遍历左子树；访问根结点。（三） 实验要求1、掌握二叉树的建立与遍历算法的实现；2、根据实验内容，用 C 语言编程实现，上机调试运行得出实验结果；3、写出预习报告和实验报告。四、考核方式根据实验课考勤、课前预习情况、课上实验能力、原型系统效果验收与实验报告的完成情况确定最终的
4、实验成绩，实验成绩占课程总成绩的 10%。五、建议教材与教学参考书1、课程教材1 沈被娜等编.计算机软件技术基础 （第三版）.北京.清华大学出版社.20002、实验指导书1 计算机软件技术基础实验指导书. 赵俊生（自编）. 2009六、编制说明编制者：赵俊生 组长：赵俊生执笔人：赵俊生 编制时间：2009 年 3 月4实验一 线性表的建立与遍历一、实验目的进一步理解线性表的逻辑结构和存储结构，掌握线性表的建立与遍历算法二、实验题目线性表的建立与遍历三、实验类型验证性四、实验内容1、给定一个输入序列，建立顺序表，访问输出顺序表中各结点的内容。2、给定一个输入序列，建立线性链表，访问输出线性链表中
5、各结点的内容。五、实验要求根据实验内容，用 C 语言编程实现，上机调试运行得出实验结果，写出实验报告。六、实验提示1、线性结构中的所有结点按它们之间的关系可以排成一个线性序列：k1，k 2，k n其中 k1 是开始结点，k n 是终端结点，k i 是 ki+1 的前驱结点，而 ki+1 是 ki 的后继结点(i=1，2，n-1)。通常把上述线性序列称为“线性表” ，把线性结构中的结点称为元素或“表目” 。将一个线性表存放到计算机中，可以采用不同的方法，其中最简单而自然的就是顺序的方法，即把表目按其索引值从小到大一个接一个地存放在相邻的单元里。顺序方法存储的线性表简称“顺序表” ，顺序表是一种紧
6、凑结构。2、常用的链表有单链表和双链表。在单链表中分配给每个结点的存储单元可分为两个部分：一部分存放结点的数据，称为 data 域，另一部分存放指向结点后续结点的指针，称为 next 域，终端结点没有后继结点，其 next 域为 NULL，在计算机中可以表示成零或负数，另外还需要一个表头变量 head 指向链表的第一个结点。七、实验报告1、写出每个算法的思想。2、画出算法流程图。3、调试程序出现的问题及解决的方法。4、打印实验报告及程序清单。5、报告给出测试的结果并写出实验体会。6、报告按信息学院统一格式书写。八、范例参考1、顺序表 向量的建立向量的定义如下：typedef ElemType
7、vectorn0输入 n 个整数，产生一个存储这些整数的向量 A 的函数如下：void create(A,n)vector A;int n;5int i;for(i=1;in) printf(“i 值错误！n”);elsefor(j=n;j=i;j-) Aj+1=Aj; /*将第 i 个元素及其后的元素后移*/Ai=x;n+; /*向量长度增 1*/向量的删除在一个有 n 个元素的向量 A 中删除第 i 个元素的函数如下：void delete (A,n)vector A;int n;int j;if(in)printf(i 值错误！n);elsefor(j=i;jx)i+;if(idata=
8、x;p-next=s; p=s;else cycle=0;head=head-next; /*删除头结点*/p-next=NULL;查找某个结点在已建立好的单链表（表头指针为 head）中查找元素值为 x 的函数如下：void find(head,x)node *head;int x;node *p;p=head;while(p-data!=x&p!=NULL)p=p-next;if(p!=NULL)7printf(结点找到了！n);elseprintf(结点未找到！n);求单链表的长度计算一个已建立好的单链表（表头指针为 head）的结点个数的函数如下：int length(head)nod
9、e head;int n=0;node *p;p=head;while(p!=NULL)p=p-next;n+;return(n);在单链表中插入一个结点在单链表中第 i 个结点(i0)之后插入一个元素为 x 的结点的函数如下：void insert(head,i,x)node *head;int i,x;node *s,*p;int j;s=(node *)malloc(sizeof(node); /*建立一个待插入的结点 s*/s-data=x;if(i=0) /*如果 i=0,则将 s 所指结点插入到表头后返回*/s-next=head;head=s;elsep=head;j=1; /*
10、在单链表中查找第 i 个结点，由 p 所指向*/while(p!=NULL&jnext;if(p!=NULL) /*若查找成功，则把 s 插入到其后*/s-next=p-next;8p-next=s;elseprintf(未找到！n);从单链表中删除一个结点从单链表中删除一个其值等于给定值 x 的结点的函数如下：void delete(head,x)node *head;int x;node *p,*q;if(head=NULL)printf(链表下溢！n);/*如果单链表为空，则下溢处理*/if(head-data=x) /*如果表头结点值等于 x 值，则删除之*/p=head;head=h
11、ead-next;free(p);elseq=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); 建立、遍历单链表(方法二）int count_nohead(LINKLIST *head)/*不带头结点的单链表：输出单链表元素值并计数*/i
12、nt i = 0;LINKLIST *p;p = head;printf(输出单链表元素值 : );9while(p != NULL)printf( %c,p-data);i+;p = p-next;printf(n);return i;int count_head(LINKLIST *head)/*带头结点的单链表：输出单链表元素值并计数*/int i = 0;LINKLIST *p;p = head-next;printf(输出单链表元素值 : );while(p != NULL)printf( %c,p-data);i+;p = p-next;printf(n);return i;LIN
13、KLIST *creatlink_nohead_head(LINKLIST *head) /*用头插入法建立不带头结点的单链表*/LINKLIST *t;char ch;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) /*用头插入法建立带头结点的单链表*
14、/LINKLIST *t;char ch;t = (LINKLIST *)malloc(sizeof(LINKLIST);head = t;t-next = NULL;10printf(单链表元素值为单个字符, 连续输入，$为结束字符 : );while(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)/*用尾插入法
15、建立不带头结点的单链表*/LINKLIST *last, *t;char ch;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_rail(LINKLIST *head)/*用尾插入法建立带头结点的单链表*/LINKLIST *last, *t;char ch;t = (LINKLIST *)malloc(sizeof(LINKLIST);head = t; last = t;t-next = NULL;printf
