软件开发技术基础的实验报告.doc

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

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

姓名：

学号：

班级：

实验一 线性表的操作（2学时）
实验类型：验证性
实验要求：必修
实验学时： 2学时
一、实验目的：
参照给定的线性表顺序表类和链表类的程序样例，验证给出的线性表的常见算法。
二、实验要求：
1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
设计一个静态数组存储结构的顺序表类，要求编程实现如下任务：
1）建立一个线性表，首先依次输人整数数据元素（个数根据自己的需要键盘给定）
2）删除指定位置的数据元素（指定元素位置通过键盘输入）再依次显示删除后的线性表中的数据元素。
3）查找指定数据的数据元素（指定数据的大小通过键盘输入），若找到则显示位置，若没有找到就显示0。

四、要求
1）采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过50个。
2）写出完整的程序并能调试通过即可

源程序如下：
#include <iostream>
using namespace std;
template <class T>
class sq_LList
{
private:
int mm;
int nn;
T *v;
public:
sq_LList(){mm=0;nn=0;return;}
sq_LList(int);
void prt_sq_LList();
int flag_sq_LList();
void ins_sq_LList(int,T);
void del_sq_LList(int);
int search_sq_LList(T x);
};

template <class T>
sq_LList<T>::sq_LList(int m)
{
mm=m;
v=new T[mm];
nn=0;
return;
}

template <class T>
void sq_LList<T>::prt_sq_LList()
{
int i;
cout<<"nn="<<nn<<endl;
for(i=0;i<nn;i++)
cout<<v[i]<<endl;
return;
}

template <class T>
int sq_LList<T>::flag_sq_LList()
{
if(nn==mm)
return(-1);
if(nn==0)
return(0);
return(1);
}

template <class T>
void sq_LList<T>::ins_sq_LList(int i,T b)
{
int k;
if(nn==mm)
{
cout<<"overflow"<<endl;
return;
}
if(i>nn)
i=nn+1;
if(i<1)
i=1;
for(k=nn;k>=i;k--)
v[k]=v[k-1];
v[i-1]=b;
nn=nn+1;
return;
}

template <class T>
void sq_LList<T>::del_sq_LList(int i)
{
int k;
if(nn==0)
{
cout<<"underflow!"<<endl;
return;
}
if((i<1)||(i>nn))
{
cout<<"Not this element in the list!"<<endl;
return;
}
for(k=i;k<nn;k++)
v[k-1]=v[k];
nn=nn-1;
return;
}

template <class T>
int sq_LList<T>::search_sq_LList(T x)
{
int i,j,k;
i=1;j=nn;
while(i<=j)
{
k=(i+j)/2;
if(v[k-1]==x)
cout<<"你要查找的数现在的位置为:"<<(k-1)<<endl;
if(v[k-1]>x)
j=k-1;
else i=k+1;
}
return(0);
}

int main()
{
int y;
sq_LList<double> a(100);
cout<<"第一次输出顺序表对象a:"<<endl;
a.prt_sq_LList();
a.ins_sq_LList(1,1);
a.ins_sq_LList(2,3);
a.ins_sq_LList(3,5);
a.ins_sq_LList(4,7);
a.ins_sq_LList(5,9);
a.ins_sq_LList(6,11);
cout<<"第二次输出顺序表对象a:"<<endl;
a.prt_sq_LList();
a.del_sq_LList(2);
cout<<"第三次输出顺序表对象a:"<<endl;
a.prt_sq_LList();
cout<<"请输入要查找的数:"<<endl;
cin>>y;
cout<<endl;
a.search_sq_LList(y);
cout<<"第四次输出顺序表对象a:"<<endl;
a.prt_sq_LList();
return 0;
}

运行结果如下：

心得体会：
1. 通过本次试验，我掌握了线性表的基本概念。
2.通过本次试验，我懂得了如何建立一个顺序表，并能对顺序表进行基本的建立、插入、检测、删除以及查找的操作。
3.本次试验我知道了线性表的顺序存储结构具有如下两个特点：
（1） 线性表中所有元素所占的存储空间是连续的。
（2） 线性表中各元素在存储空间中是按逻辑顺序依次存放的。

实验二 栈、队列的操作
实验目的：
参照给定的栈类和队列类的程序样例，验证给出的栈和队列的常见算法，并结合线性表类实现有关串的操作。
实验内容：

实验要求：
1． 掌握栈、队列、串的特点。掌握特殊线性表的常见算法。
2． 提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
3. 栈和队列的长度都由自己定；
4. 写出完整的程序并能调试通过即可。
5． 重点理解栈、队列和串的算法思想，能够根据实际情况选择合适的存储结构。
6 栈、队列的算法是后续实验的基础（树、图、查找、排序等）。

实验原理：
1. 堆栈类测试和应用问题。要求：
定义数据元素的数据类型为如下形式的结构体：
typedef struct
{ char taskname[10];//任务名
int taskno;　　　　//任务号
｝DataType；
设计一个包含5个数据元素的测试数据，并设计一个主函数实现依次把5个数据元素入栈，然后出栈堆栈中的数据元素并在屏幕上显示。
2. 队列类测试和应用问题。要求：
设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为：依次把数据元素1,2,3,4,5入队，然后出队中的数据元素并在屏幕上显示。

#include<iostream>

using namespace std;
//stack--------------------------------------------begin
#define stacksize 5

typedef struct
{ char taskname[10]; //任务名
int taskno; //任务号
}DataType;

class stack
{
private:
int top;
DataType task[stacksize];
public:
bool init();
bool empty();
bool push(DataType d);
bool pop(DataType &d);

};

bool stack::init()
{
top=0;
int i;
for(i=0;i<stacksize;i++)
{
strcpy(task[i].taskname,"");
task[i].taskno=-1;
}
return true;
}

bool stack::empty()
{
return top>0?false:true;

}

bool stack::push(DataType d)
{
if(top>=stacksize) return false;
strcpy(task[top].taskname,d.taskname);
task[top].taskno=d.taskno;
top++;
return true;
}

bool stack::pop(DataType &d)
{
if(top<=0) return false;
strcpy(d.taskname,task[top-1].taskname);
d.taskno=task[top-1].taskno;
top--;
return true;
}

//stack--------------------------------------------end

//queue--------------------------------------------begin

class queue_node
{
public:
int data;
queue_node *next;

queue_node()
{
data=0;
next=NULL;
}
queue_node(int d)
{
data=d;
next=NULL;
}
};

class queue
{
private:
queue_node *front,*rear;
public:
bool init();
bool empty();
bool enqueue(int d);
bool dequeue(int &d);

};

bool queue::init()
{
front=rear=new queue_node;
return true;
}

bool queue::empty()
{
if(front==rear) return true;
else return false;
}

bool queue::enqueue(int d)
{
rear->next=new queue_node(d);
rear=rear->next;
return true;
}

bool queue::dequeue(int &d)
{
if(front==rear) return false;

queue_node *p=front->next;

d=p->data;
front->next=p->next;

if(p==rear)rear=front;
delete p;
return true;
}

//queue--------------------------------------------end

#define queuesize 10
class sqqueue
{
private:
int * base;
int front;
int rear;
public:
bool init();
bool enqueue(int d);
bool dequeue(int &d);

};

bool sqqueue::init()
{
base=(int *)malloc(queuesize*sizeof(int));
if(!base) return false;
front=rear=0;
return true;
}

bool sqqueue::enqueue(int d)
{
if((rear+1)%queuesize==front) return false;
base[rear]=d;
rear=(rear+1)%queuesize;
return true;
}

bool sqqueue::dequeue(int &d)
{
if(front==rear) return false;
d=base[front];
front=(front+1)%queuesize;
return true;
}

void main()
{

DataType dd[5],tt;

char tn[]="任务a";
int i;
for(i=0;i<5;i++)
{
strcpy(dd[i].taskname,tn);
tn[4]++;
dd[i].taskno=i+1;
}
stack mystack;
mystack.init();
for(i=0;i<5;i++)
{
mystack.push(dd[i]);
}
cout<<"入栈完成，按回车键继续……";getchar();

while(mystack.pop(tt))
cout<<tt.taskname<<" "<<tt.taskno<<endl;
cout<<"出栈完成，按回车键继续……";getchar();

queue myqueue;
myqueue.init();
for(i=0;i<5;i++)
myqueue.enqueue(i+1);
cout<<"链队入队完成，按回车键继续……";getchar();
for(;myqueue.dequeue(i);)
cout<<i<<endl;
cout<<"链队出队完成，按回车键继续……";getchar();

sqqueue mysqqueue;
mysqqueue.init();
for(i=0;i<5;i++)
{
mysqqueue.enqueue(i+1);
}
cout<<"循环队列入队完成，按回车键继续……";getchar();
for(;mysqqueue.dequeue(i);)
cout<<i<<endl;
cout<<"循环队列出队完成，按回车键退出……";getchar();

}

实验步骤：
实验结果：

实验三 查找算法实现（2学时）
实验类型：验证性
实验要求：必修
实验学时： 2学时
一、实验目的：
参照各种查找算法程序样例，验证给出的查找常见算法。
二、实验要求：
1、掌握各种查找算法的特点，测试并验证查找的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
1. 建立有序表，采用折半查找实现某一已知的关键字的查找。
2．利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。

源程序如下：
#include <iostream>
using namespace std;
template <class T>
class sL_List
{
private:
int mm;
int nn;
T *v;
public:
sL_List(){mm=0;nn=0;return;}
sL_List(int);
int search_sL_List(T);
int insert_sL_List(int,T);
void prt_sL_List();
};

template <class T>
sL_List<T>::sL_List(int m)
{
mm=m;
v=new T[mm];
nn=0;
return;
}

template <class T>
int sL_List<T>::search_sL_List(T x)
{
int i,j,k;
i=1;j=nn;
while(i<=j)
{
k=(i+j)/2;
if(v[k-1]==x)
return(k-1);
if(v[k-1]>x)
j=k-1;
else i=k+1;
}
return(-1);
}

template <class T>
int sL_List<T>::insert_sL_List(int p,T x)
{
if(nn==mm)
{
cout<<"溢出！"<<endl;
return(-1);
}
p=nn-1;
while(v[p]>x)
{
v[p+1]=v[p];
p=p-1;
}
v[p+1]=x;
nn=nn+1;
return(1);
}

template <class T>
void sL_List<T>::prt_sL_List()
{
int i;
for(i=0;i<nn;i++)
cout<<v[i]<<endl;
return;
}

int main()
{
int k,t,q,result;
int a[20]={10,20,30,40,50,60,70,80};
sL_List<int>s(20);
for(k=0;k<8;k++)
s.insert_sL_List(k+1,a[k]);
cout<<"输出有序对象s:"<<endl;
s.prt_sL_List();
cout<<"请输入要查找的数:"<<endl;
cin>>t;
cout<<endl;
cout<<"你要查找的数在数组中的位置为:"<<endl;
result=s.search_sL_List(t);
cout<<result<<endl;
cout<<"请插入一个元素:"<<endl;
cin>>q;
cout<<endl;
s.insert_sL_List(k+1,q);
cout<<"插入后有序表变为:"<<endl;
s.prt_sL_List();
return 0;
}

实验结果如下：

心得体会：
1. 通过这次试验，我知道了一些查找的基本方法，并且了解了折半查找的典型方法及技巧。
2. 并且我掌握了利用折半法插入一个元素的方法。
3. 常见问题在于在插入位置时，易混淆位置与数值的关系，以及c++中的一些基本定义方法易忘记。

实验四 排序综合实验（3学时）
实验类型：综合性
实验要求：必修
实验学时： 3学时
一、实验目的：
参照各种排序算法程序样例，验证给出的排序常见算法。
二、实验要求：
1、掌握各种排序算法的特点，测试并验证排序的常见算法。
2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容：
输入一组关键字序列分别实现下列排序:
1.实现直接插入排序；
2.实现冒泡排序算法；
3.实现快速排序算法（取第一个记录或中间记录作为基准记录）；
4.快速排序的非递归算法；
5. 堆排序。

把上述几种排序的算法编写成菜单，根据输入的数字不同执行对应的排序算法。

源程序如下：
#include <iostream>
using namespace std;
//实现简单插入排序
template <class T>
void insort(T p[],int n)
{
int j,k;
T t;
for(j=1;j<n;j++)
{
t=p[j];
k=j-1;
while((k>=0)&&(p[k]>t))
{
p[k+1]=p[k];
k=k-1;
}
p[k+1]=t;
}
return;
}
//实现冒泡排序
template <class T>
void bub(T p[],int n)
{
int m,k,j,i;
T d;
k=0;
m=n-1;
while(k<m)
{
j=m-1;m=0;
for(i=k;i<=j;i++)
if(p[i]>p[i+1])
{
d=p[i];
p[i]=p[i+1];
p[i+1]=d;
m=i;
}
j=k+1;k=0;
for(i=m;i>=j;i--)
if(p[i-1]>p[i])
{
d=p[i];
p[i]=p[i-1];
p[i-1]=d;
k=i;
}
}
return;
}
//实现快速排序
template <class T>
void qck(T p[],int n)
{
int m,i;
T *s;
if(n>10)
{
i=split(p,n);
qck(p,i);
s=p+(i+1);
m=n-(i+1);
qck(s,m);
}
else
bub(p,n);
return;
}

template <class T>
static int split(T p[],int n)
{
int i,j,k,l;
T t;
i=0;j=n-1;
k=(i+j)/2;
if((p[i]>=p[j])&&(p[j]>=p[k]))
l=j;
else if((p[i]>=p[k])&&(p[k]>=p[j]))
l=k;
else
l=i;
t=p[l];
p[l]=p[i];
while(i!=j)
{
while((i<j)&&(p[j]>=t))
j=j-1;
if(i<j)
{
p[i]=p[j];
i=i+1;
while((i<j)&&(p[i]<=t))
i=i+1;
if(i<j)
{
p[j]=p[i];
j=j-1;
}
}
}
p[i]=t;
return(i);
}
//实现堆排序
template <class T>
void hap(T p[],int n)
{
int i,mm;
T t;
mm=n/2;
for(i=mm-1;i>=0;i--)
sift(p,i,n-1);
for(i=n-1;i>=1;i--)
{
t=p[0];p[0]=p[i];p[i]=t;
sift(p,0,i-1);
}
return;
}

template <class T>
static sift(T p[],int i,int n)
{
int j;
T t;
t=p[i];
j=2*(i+1)-1;
while(j<=n)
{
if((j<n)&&(p[j]<p[j+1]))
j=j+1;
if(t<p[j])
{
p[i]=p[j];
i=j;
j=2*(i+1)-1;
}
else
j=n+1;
}
p[i]=t;
return(0);
}
//主函数如下
#include <iomanip>
int main()
{
int i,j;
double p[30],r=1.0;
for(i=0;i<30;i++)
{
r=2053.0*r+13849.0;
j=r/65536.0;
r=r-j*65536.0;
p[i]=r/65536.0;
}
for(i=0;i<10;i++)
p[i]=100.0+200.0*p[i];
cout<<"排列前的序列为:"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<p[i];
cout<<endl;
}
insort(p,10);
cout<<"简单插入排序后的序列为:"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<p[i];
cout<<endl;
}
bub(p,10);
cout<<"冒泡排序后的序列为:"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<p[i];
cout<<endl;
}
qck(p,10);
cout<<"快速排序后的序列为:"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<p[i];
cout<<endl;
}
hap(p,10);
cout<<"堆排序后的序列为:"<<endl;
for(i=0;i<10;i++)
{
cout<<setw(10)<<p[i];
cout<<endl;
}
return 0;
}

运行结果如下：

心得体会：
1. 通过本次试验，我掌握了简单插入排序、冒泡法排序、快速排序以及堆排序的基本方法。
2. 在本次试验中，我用类比c语言常见的排序方法来实现了这一基本的排序技术。
3. 出现的问题在于快速排序中表的分割方法，以及堆排序中调整建堆的概念不是很清楚。

- 23 -