软件技术基础实验报告-2

PAGEPAGE4 《计算机软件技术基础》实验报告专业_____________年级_____________学号_____________学生姓名_____________指导老师_____________南华大学计算机学院编

【实验报告】实验时间：实验地点：实验机号：具体实验内容

程序调试过程实习小结=1\*ROMANI实验要求1．每次实验中有若干习题，每个学生至少应该完成其中的两道习题。2．上机之前应作好充分的准备工作，预先编好程序，经过人工检查无误后，才能上机，以提高上机效率。3．独立上机输入和调试自己所编的程序，切忌抄袭、拷贝他人程序。4．上机结束后，应整理出实验报告。书写实验报告时，重点放在调试过程和小节部分，总结出本次实验中的得与失，以达到巩固课堂学习、提高动手能力的目的。实验一线性表【实验目的】1．熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。2．通过编程、上机调试，进一步理解线性表的基本概念,熟练运用C语言实现线性表基本操作。3．熟练掌握线性表的综合应用问题。【实验内容】必做：1．一个线性表有n个元素（n<MAXSIZE,MAXSIZE指线性表的最大长度），且递增有序。（1）现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。采用链式存储表示方法实现，设计程序实现（2）从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。要求：=1\*GB3①指定的值x由键盘输入；=2\*GB3②程序能处理空链表的情况。选做：3．设有头结点的单链表，编程对表中的作一值只保留一个结点，删除其余值相同的结点。要求：=1\*GB3①该算法用函数（非主函数）实现；=2\*GB3②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。4．已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。要求：=1\*GB3①该算法用函数Reverse(head,p)实现，其中head为表头指针，p指向要交换的结点；=2\*GB3②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。要求：=1\*GB3①建立一个结点中含有三个域的单链表；=2\*GB3②在主函数中调用此算法，构成双向循环链表；=3\*GB3③在主函数中利用正向和逆向两种方式输出链表中的数据，验证算法的正确性。实验二栈与队列【实验目的】1．学习如何使用C语言实现堆栈与队列。2．熟悉堆栈与队列的基本操作及应用。【实验内容】现有一循环顺序队列，其结构描述为：#definemaxsize10structsequeue{datatypedata[maxsize];intfront，rear;}; /*循环顺序队列的类型*/sequeue*sq要求：=1\*GB3①设计队列的几种几种操作：初始化、进队、出队、取队头元素和判断队列是否非空。=2\*GB3②编写一个主函数进行测试。2．顺序堆栈实验要求：=1\*GB3①设计堆栈的几种几种操作：初始化、入栈、出栈、取栈顶元素和判断堆栈是否非空。=2\*GB3②编写一个主函数进行测试。实验三队列与栈的应用必做：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>#definemaxsize6typedefcharqueue[maxsize]；intrear=0,len=0；intenqueue(queuequ,charx){if(len==maxsize)return0；else{rear=(rear+1)%maxsize；qu[rear]=x；len++；return1；}}intdequeue(queuequ,char*x){intfront；if(len==0)return0；else{front=(rear-len+1+maxsize)%maxsize；*x=qu[front]；len--；return1；}}voidmain(){charx；queuequ；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“malloc.h”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；blinkadd(blinkbt,charch){if(bt==NULL){bt=nalloc(sizeof(bnode))；bt->data=ch；bt->lchild=bt->rchild=NULL；}elseif(ch<bt->data)bt->lchild=add(bt->lchid,ch)；elsebt->rchild=add(bt->rchild,ch)；returnbt；}voidinorder(blinkbt){if(bt){inorder(bt->)；printf（“%c”,）；inorder(bt->)；}}main(){blinkroot=null；inti,n；charx；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”structnode{chardata；structnode*lchild,*rchild；}bnode；typedefstructnode*blink；intn=0,no=0；voidpreorder(blinkbt){if(bt){n++；if(bt->lchild==NULL&&bt->rchild==NULL)no++；preorder(bt->；)preorder(bt->；)}}blinkcreat(){blinkbt；charch；ch=getchar()；if(ch!=’#’){bt=nalloc(sizeof(bnode))；bt->data=ch；bt->lchild=()；bt->rchild=()；}elsebt=NULL；returnbt；}main(){blinkroot；root=creat()；preorder(root)；printf（“numberofnode：%dnumberofleaf：%d\n”,n,no)；}输入：ab##cd###输出：实验五查找与排序【实验目的】熟悉各种查找与排序的算法，并对各种算法的效率进行比较和测试。【实验内容】排序算法比较。要求：=1\*GB3①调用函数intrand(void)产生100000个待排序的数据；=2\*GB3②测试下列各排序函数的机器实际执行时间：a.直接插入排序；b.希尔排序c.选择排序d.冒泡排序e.快速排序f.归并排序实验六综合练习【实验目的】1．在掌握基本