《计算机软件技术基础》实验报告专业_____________年级_____________学号_____________学生姓名_____________指导老师_____________南华大学计算机学院编I 实验要求1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。
2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。
3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。
4．上机结束后，应整理出实验报告。
书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。
实验一线性表【实验目的】1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。
2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。
3．熟练掌握线性表的综合应用问题。
【实验内容】必做：1．一个线性表有n个元素（n<MAXSIZE, MAXSIZE指线性表的最大长度），且递增有序。
（1）现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。
采用链式存储表示方法实现，设计程序实现（2）从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。
要求：①指定的值x由键盘输入；②程序能处理空链表的情况。
选做：3．设有头结点的单链表，编程对表中的作一值只保留一个结点，删除其余值相同的结点。
要求：①该算法用函数（非主函数）实现；②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。
4．已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。
要求：①该算法用函数Reverse(head,p)实现，其中head为表头指针，p指向要交换的结点；②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。
要求：①建立一个结点中含有三个域的单链表；②在主函数中调用此算法，构成双向循环链表；③在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。
【实验报告】实习时间：实习地点：实习机号：实验二堆栈与队列【实验目的】1．学习如何使用C语言实现堆栈与队列。
2．熟悉堆栈与队列的基本操作及应用。
【实验内容】1．现有一顺序队列，其结构描述为：# define MAX 100typedef struct{ ElemType queue[MaxQueueSize];int front; // 队头指针int count; // 计数器}QueueType;要求：①设计队列的几种几种操作：初始化、进队、出队、取队头元素和判断队列是否非空。
②编写一个主函数进行测试。
2．顺序堆栈实验要求：①设计堆栈的几种几种操作：初始化、入栈、出栈、取栈顶元素和判断堆栈是否非空。
②编写一个主函数进行测试。
【实验报告】实验三队列与栈的应用必做：1、设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个算法判断其中的括号是否匹配。
提示：本题使用一个运算符栈st，当遇到的‘（’、‘[’、或‘{’时进栈，当遇到‘}’、‘]’、‘）’时判断栈顶是否为相应的括号，若是退栈继续执行；否则算法结束。
选做：2、假设以数组sequ[0..MaxSize-1]存放环形队列的元素，同时设变量rear和len分别指示环形队列中队尾元素的位置和内含元素的个数。
试写出此环形队列队满的条件，并设计相应入队和出队的算法。
（根据题目填空完善程序）提示：该环形队列对满的条件为：len= =MaxSize，队空的条件为：len= =0。
由rear,len求队列头指针front的过程为：front=rear-len+1；if (front<0) front=front+MaxSize；即front=(rear-len+1+MaxSize)%MaxSize# include <stdio.h># define maxsize 6typedef char queue [maxsize]；int rear=0, len=0；int enqueue (queue qu, char x){if (len= =maxsize)return 0；else{rear=(rear+1) %maxsize；qu[rear]=x；len++；return 1；}}int dequeue (queue qu, char *x){int front；if (len= =0)return 0；else{front=(rear-len+1+maxsize) %maxsize；*x=qu[front]；len--；return 1；}}void main(){char x；queue qu；printf( “a入队\n”）；enqueue (qu, …a‟)；printf( “b入队\n”）；enqueue (qu, …b‟)；printf( “c入队\n”）；enqueue (qu, …c‟)；printf( “出队一次：”）；dequeue (qu, &x)；printf( “%c\n”,x)；printf( “d入队\n”）；enqueue (qu, …d‟)；printf( “e入队\n”）；enqueue (qu, …e‟)；printf( “出队一次：”）；dequeue (qu, &x)；printf（“%c\n”,x)；printf( “f入队\n”）；enqueue (qu, …f‟)；printf( “g入队\n”）；enqueue (qu, …g‟)；printf( “出队一次：”）；dequeue (qu, &x)；printf（“%c\n”,x)；printf（“余下元素出列：”）；while (len>0){dequeue (qu, &x)；printf（“%c\n”,x)；}printf（“\n”）；}输出：. 入队. 入队出队一次：. 入队. 入队出队一次：. 入队. 入队出队一次：余下元素出列：【实验报告】实习时间：实习地点：实习机号：实验四树一、实验目的1.掌握二叉树，二叉树排序数的概念及存储方法。
2.掌握二叉树的遍历算法。
3.熟练掌握编写实现树的各种运算的算法。
一、实验内容树的基本运算：创建树；输出树；遍历树；求二叉树的深度；创建二叉排序树；二叉排序树的查找；二叉排序树的删除；创造哈夫曼树；输出哈夫曼树；1、建立一棵二叉树并中序遍历。
（填空）#include “ stdio.h”#include “m alloc.h”struct node{char data；struct node *lchild , *rchild；} bnode；typedef struct node * blink；blink add(blink bt,char ch){if(bt==NULL){bt=nalloc(sizeof(bnode))；bt->data = ch；bt->lchild = bt->rchild =NULL；}else if ( ch < bt->data)bt->lchild = add(bt->lchild ,ch)；elsebt->rchild = add(bt->rchild,ch)；return bt；}void inorder(blink bt){if(bt){ inorder(bt->lchild)；printf（“%c”,bt->data）；inorder(bt->rchild)；}}main(){blink root = null；int i,n；char x；scanf（“%c”,&n)；for(i=1；i<=n；i++){x=getchar()；root=add(root,x)；}inorder(root)；printf（“\n”）；}输入：ephqsbma输出：2、求二叉树的结点数和叶子数(填空)#include “stdio.h”#include “alloc.h”struct node{char data；struct node *lchild , *rchild；} bnode；typedef struct node *blink；int n=0,no=0；void preorder(blink bt){if(bt){ n++；if(bt->lchild ==NULL&&bt->rchild==NULL) no++；preorder(bt->lchild；)preorder(bt->rchild；)}}blink creat(){blink bt；char ch；ch = getchar()；if (ch!=‟#‟){bt= nalloc(sizeof(bnode))；bt->data= ch；bt->lchild = creat( )；bt->rchild= creat( )；}elsebt=NULL；return bt；}main(){blink root；root = creat()；preorder(root)；printf（“number of node：%d number of leaf：%d \n” , n , no)；}输入：ab##cd###输出：【实验报告】实习时间：实习地点：实习机号：实验六查找与排序【实验目的】熟悉各种查找与排序的算法，并对各种算法的效率进行比较和测试。
【实验内容】1．排序算法比较。
要求：①调用函数int rand(void)产生100000个待排序的数据；②测试下列各排序函数的机器实际执行时间：a.直接插入排序；b.希尔排序c.选择排序d.冒泡排序e.快速排序f.归并排序【实验报告】实习时间：实习地点：实习机号：实验七综合练习【实验目的】1．在掌握基本概念的基础上，综合运用线性结构和树结构以及排序和查找算法进行复杂结构程序设计。
【实验内容】1．试将一棵普通树转换成二叉树，同时转换而成的二叉树按前序、中序、后序进行遍历，并输出遍历后结点的序列。
例如，下面左图是一棵普通树，用括号表示法表示为：A(BC(FG)DE)，右图是转换后的二叉树。
提示：从分析输入的树串形式可知，左括号后面的字符为左括号前面字符的左子树，括号内的字符关系是兄弟，则转化为二叉树后，后面字符为其前一字符的右子树。
所以，依据左右括号及字符间的关系，可以生成结点的左右子树。