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

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

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

姓名：

学号：

班级：

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

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

源程序如下：
#include
using namespace std;
template
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
sq_LList::sq_LList(int m)
{
mm=m;
v=new T[mm];
nn=0;
return;
}

template
void sq_LList::prt_sq_LList()
{
int i;
cout<<"nn="<
int sq_LList<T>::flag_sq_LList()
{
if(nn==mm)
return(-1);
if(nn==0)
return(0);
return(1);
}

template
void sq_LList::ins_sq_LList(int i,T b)
{
int k;
if(nn==mm)
{
cout<<"overflow"<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
void sq_LList::del_sq_LList(int i)
{
int k;
if(nn==0)
{
cout<<"underflow!"<nn))
{
cout<<"Not this element in the list!"<nn=nn-1;
return;
}

template
int sq_LList::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)<x)
j=k-1;
else i=k+1;
}
return(0);
}

int main()
{
int y;
sq_LListouble> a(100);
cout<<"第一次输出顺序表对象a:"<ndl;
a.prt_sq_LList();
cout<<"请输入要查找的数:"<>y;
cout<
（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

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;itaskno=-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;
queuenode *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<)
myqueue.enqueue(i+1);
cout<<"链队入队完成，按回车键继续……";getchar();
for(;myqueue.dequeue(i);)
cout<eue.dequeue(i);)
cout<验内容：
1. 建立有序表，采用折半查找实现某一已知的关键字的查找。
2．利用折半查找算法在一个有序表中插入一个元素，并保持表的有序性。

源程序如下：
#include
using namespace std;
template
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
sL_List::sL_List(int m)
{
mm=m;
v=new T[mm];
nn=0;
return;
}

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

template ss T>
void sL_List::prt_sL_List()
{
int i;
for(i=0;is(20);
for(k=0;k<8;k++)
s.insert_sL_List(k+1,a[k]);
cout<<"输出有序对象s:"<ut<<"请输入要查找的数:"<>t;
cout<>q;
cout<试验，我知道了一些查找的基本方法，并且了解了折半查找的典型方法及技巧。
2. 并且我掌握了利用折半法插入一个元素的方法。
3. 常见问题在于在插入位置时，易混淆位置与数值的关系，以及c++中的一些基本定义方法易忘记。

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

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

源程序如下：
#include
using namespace std;
//实现简单插入排序
template
void insort(T p[],int n)
{
int j,k;
T t;

for(j=1;j=0)&&(p[k]>t))
{
p[k+1]=p[k];
k=k-1;
}
p[k+1]=t;
}
return;
}
//实现冒泡排序
template
void bub(T p[],int n)
{
int m,k,j,i;
T d;
k=0;
m=n-1;
while(kp[i1])
{
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
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
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=t))
j=j-1;
if(i
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
static sift(T p[],int i,int n)
{
int j;
T t;
t=p[i];
j=2*(i+1)-1;
while(j<=n)
{
ifj
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<<"排列前的序列为:"<ut<<"冒泡排序后的序列为:"<