软件实验_软件实验平台

软件实验由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“软件实验平台”。

《软件技术基础》实验报告

实验一：

顺序表的操作

班 级

0801210 学 号

2012212982 姓 名

蒲米

栈，然后编写进栈和出栈的操作，读取栈顶元素。这里栈有顺序栈和链式栈两种，顺序栈是利用一种动态存储的数组定义，而链式栈是一个无头节点，只是在头部插入和删除元素的单链表。使用顺序栈要先为存储元素的数组申请一个空间，然后编写进栈和出栈取栈顶元素的操作。#include #define n 5 struct stack { int st[n];int top;};void push(struct stack *pst,int x){ if(pst->top==n-1)

printf(“此栈表已满”);pst->top++;pst->st[pst->top]=x;} void pop(struct stack *pt,int *p){ if(pt->top==-1)

printf(“此栈表为空”);*p=pt->st[pt->top];pt->top--;} void main(){ struct stack T;struct stack *t=&T;int a[n];int i;printf(“请输入数组的值:”);for(i=0;i

scanf(“%d”,&a[i]);} T.top=-1;for(i=0;i

push(t,a[i]);for(i=0;i

pop(t,&a[i]);

printf(“%dn”,a[i]);

}

}

四、算法。

顺序栈的算法：

1、顺序栈的初始化。

2、进栈操作

3、出栈操作

4、取栈顶元素。链式栈的算法：

1、进栈操作

若栈不满，则在栈顶插入元素x作为新的栈顶。

2、出栈操作

若栈不空，则删除栈顶的元素，用e返回其值。

五、实验心得体会：

通过本次实验我学习了栈这种特殊形式的线性表，就是只能从一端进行操作，逻辑和一般的线性表相同，只是元素的操作方式不同。

实验五：

队列的操作

一、实验目的：

掌握队列的定义及其运算，了解队列的应用。

二、实验内容：

1、掌握队列的特点及常见算法。

2、队列测试和应用。要求：

设计一个主函数对循环队列代码进行测试。测试方法为：依次把数据元 素2,4,6,8,10入队，然后出队中的数据元素并在屏幕上显示。

三、实验思路：

使用队列的时候要创建一个空队列，这里队列可以分为两种存储方式，顺序存储和链式存储，顺序存储顾名思义它的存储数据方式是连续存储的，而链式存储则是不连续的，队头和队尾定义两个指针，通过指针来操作队列。先创建一个含有头结点的空的链队列，建立头结点，在队尾插入结点后建立好队尾指针，判断队列是否为空，然后编写出队列的功能函数。

#include #define n 5 struct nobe { int data[n];int front;int rear;int len;};void ent(struct nobe *rst,int x)

{ if(rst->len==n)

printf(“此队列已满”);else {

rst->rear=(rst->rear+1)%n;

rst->data[rst->rear]=x;} } int out(struct nobe *rst){ int x;if(rst->len==0)

printf(“此队列为空”);else {

rst->front=(rst->front+1)%n;

x=rst->data[rst->front];} return x;}

首先建立一个结构体包含数据域与指针域，然后编写队列的入队与出队操作，最后编写主函数，在主函数调用入队与出队操作，实现程序的编程。

四、算法。队列的算法：

1、入队操作。

若队列不满，则在队尾插入元素x作为新的队尾。

2、出队操作。

3、若队列不空，则删除队头元素的值。链队列的算法

1、链队列初始化

建立一个含有头结点的空的链队列。

2、求队列的长度

返回队列的元素个数，即队列的长度。

3、入队列操作

插入元素x作为队列新的队尾元素。

4、出队列操作

若队列不空，则删除队头元素，用e返回其值。

五、实验心得体会：

队列和栈一样是一种特殊形式的线性表，队列不同与栈的是它可以在一端插入，另一端删除。

实验六： 二叉树的生成与遍历

一、实验目的：

1、熟悉二叉树节点的定义和生成方式；

2、熟悉二叉树链式结构的生成方式；

3、掌握二叉树遍历算法的实现。

二、实验内容：

1．设计实现二叉树的建立及遍历算法，要求：

（1）编写创建二叉链式存储结构的二叉树程序并输出。

（2）编写递归实现二叉树的先序、中序、后序遍历算法。（3）编写主函数测试以上二叉树的创建和遍历函数。

2.假设二叉树采用链式存储结构进行存储，编写程序实现二叉树的所有叶子

结点的统计并输出统计个数。

三、实验思路：

首先建立一个结构体包含数据域，左右子树的指针三个数据元素，这里左子树和右子树分别为某一结点指向其左子树和右子树的指针。对于叶子结点或者新生成的结点，它的左子树和右子树的指针都是空值。定义二叉树结构体变量，然后编写二叉树的输入和先序、中序、后序遍历算法，最后编写主函数，在主函数中初始化二叉树长度为零，输入二叉树的各个元素，再调用二叉树的先序、中序、后序遍历操作，输出二叉树，实现程序的编程。

四、算法。

1.二叉树的建立：

二叉树的遍历算法需要先建立二叉树，二叉树的建立需要建立栈和数组

栈和数组的建立：

typedef struct node

/*结点定义*/ {

char

data;

struct node * lchild, * rchild;} BinTreeNode;

typedef struct{ //栈的定义

BinTreeNode * ptr;int tag;}StackNode;

二叉树的建立：

BinTreeNode * CreateBinTree(BinTreeNode * Tree)/*,按先序序列建立二叉树，输入并建立一棵二叉树Tree*/ {

char c;scanf(“%c”,&c);if(c=='&')Tree = NULL;else {

Tree=(BinTreeNode *)malloc(sizeof(BinTreeNode));

Tree->data=c;

Tree->lchild= CreateBinTree(Tree->lchild);

Tree->rchild= CreateBinTree(Tree->rchild);

}

return(Tree);}

2.先序遍历

先序遍历的递归算法：

/*二叉树的先序遍历*/ void PreOrder(BinTreeNode *T){ if(T!= NULL)

{

printf(“%c”,T->data);

PreOrder(T->lchild);

PreOrder(T->rchild);

} } 先序遍历的非递归算法：

/*二叉树的先序遍历的非递归算法*/ void PreOrderTwo(BinTreeNode *T){

BinTreeNode *p,*S[Max];

int top=-1;

p=T;

/*初始化*/

do

{

while(p!= NULL)

{

printf(“%c”,p->data);

top++;S[top]=p;

p=p->lchild;

}

if(top >-1)/*栈非空*/

{

p=S[top];top--;/*取栈顶元素，出栈*/

p = p->rchild;

}

}while((p!= NULL)||(top>-1));

}

3、中序遍历：

void InOrder(BinTreeNode*t){

if(t){

InOrder(t—>leftchild);

Visit(t);

InOrder(t—>rightchild);

} }

4、后序遍历：

void PostOrder(BinTreeNode*t){

if(t){

PostOrder(t—>leftchild);

PostOrder(t—>rightchild);

visit(t);

} }

五、实验心得体会：

二叉树是一种非线性的数据存储结构，描述的是结点一对多的关系，这种结构最常用，最适合的描述方法是用链表的形式。每个结点都包含一个数据域和两个指针域。

实验七： 查找算法的实现

一、实验目的：

掌握各种查找算法的特点，测试并验证查找常见算法。

二、实验内容：

1.建立有序表，采用折半查找实现某一已知的关键字的查找。

2．利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。

三、实验思路：

#include

int search(int x,int data[],int n){ int low,high,mid;low=0;high=n-1;while(low

mid=(low+high)/2;

if(data[mid]=x)

return(mid+1);

else

if(data[mid]>x)

high=mid-1;

else

low=mid+1;} return 0;}折半查找法首先定义一个一维数组表示有序表，查找的思路是将给定的数据与有序表中间位置的元素做比较，若两者相等则查找成功，若前者小于后者，则在中间位置左边的元素中继续查找；若前者大于后者，则在中间位置右边的元素中继续查找。重复这个步骤直到查找成功。然后编写折半查找法的算法和利用折半查找法插入元素的算法，最后编写主函数，在主函数中输入有序表的元素，再调用折半查找法的查找和插入操作，保持有序表的有序性并输出，实现程序的编程。

四、算法。

1、设置查找区间初值，设下界low=0,设上界high=length—1。

2、若low

3、若key

若key>data[mid],则设low=mid+1并继续执行步骤2；

若key=data[mid]则查找成功，返回目标元素位置mid+1(位置从1计数)。

4、若当low=high时，key!=data[mid]则查找失败，返回0.四、实验心得体会：

折半查找法是对一个有序表进行折中查找，首先对表进行排序，则查找起来就会事半功倍。这种查找的算法直观，形象，便于使用。

实验八： 排序综合实验

一、实验目的：

参照各种排序算法程序样例，验证给出的排序常见算法。

二、实验内容：

输入一组关键字序列分别实现下列排序，并将上述几种排序的算法编写成菜

单，根据输入的数字不同执行对应的排序算法(任选两种排序方法实现)。

1、直接插入排序。

2、冒泡排序。

3、直接选择排序。

4、快速排序。

三、实验思路：

首先编写直接插入排序法和冒泡排序法，然后编写主函数，在主函数中定义一个一维数组用来记录数据，再编写一个菜单用来选择排序方法，最后调用直接插入排序法和冒泡排序法等操作，使用循环结构实现程序的反复执行直到退出为止。

四、算法。

直接插入排序算法void insort(int p[],int n){ int i,j,temp;for(i=1;i

temp=p[i];

j=i;

while(j>0&&temp

{

p[j]=p[j-1];

j--;

}

p[j]=temp;} }

冒泡排序算法void bublesort(int v[],int n){ int i,j,temp;for(i=1;i

for(j=0;j

{

if(v[j]>v[j+1])

{

temp=v[j];

v[j]=v[j+1];

v[j+1]=temp;

}

} } }

简单选择排序法void Select_Sort（datatype R[ ],intn){ /*对排序表R[1].....R[n]进行冒泡排法，n是记录个数*/ for(i=1;i

快速排序法int Partition(SeqList &L,int low,int high){

L.data[0] = L.data[low];

DataType key = L.data[low];

while(low

{

while(low=key)

high--;

L.data[low] = L.data[high];

while(low

low++;

L.data[high] = L.data[low];}

五、实验心得体会：

通过本次实验，我们对常用的排序方法（直接插入排序，简单选择排序快速排序和冒泡排序）进行了使用，排序对于我们今后处理无序的数据提供了一个快捷的方法。