北京工业大学耿丹学院
《软件技术基础》课程实验报告
注:本表格可直接采用计算机输入填写,但承诺人签字必须手写。
实验一 C++程序的结构及线性表的顺序存储结构
实验目的:
1、熟知C++程序的结构特征及运行特点。
2、参考书中例题实现线性表的顺序存储结构的相关算法
3、理解相关算法并对算法做简单的改动。
实验要求:
1、在上机实践的过程中,调试程序时会碰到一些错误,请将错误信息写实验报告程序右边相应的位置,如果是英文,将其翻译成中文,并简单记录错误修改的过程。
2、记录实验过程中学会的、要关注的知识点的解题方法,如果程序是打印的,这些记录的内容需要手写。
3、用文字表述书中27页至29页的sq_LList类中各算法。
实验内容:
1、在C-Free中编辑书中27页至29页的sq_LList类,并以sq_LList.h为文件名保存在某个目录中。
2、编辑书中例2.9中的程序,并以L2_3.cpp为文件名保存在sq_LList.h所在的目录。编译检查程序中的错误,运行后分析运行结果。
3、仿照例2.9中的程序编写一个新程序,实现依次插入表示学生成绩的线性表{98,73,67,87,56}中的元素,然后再删除其中的98、67、56三个元素。在插入和删除操作过程中使用输出方法prt_sq_LList()查看操作是否正确。
实验过程:
《软件开发技术基础》
实验报告
学院: 自动化学院
班级: 0831004班
学号: 2010213157
姓名: 彭威威
目录
n 《软件开发技术基础》 1
n 实验报告 1
n 实验一 线性表的操作(2学时) 3
n 实验二 栈的操作(3学时) 7
n 实验三 队列的操作(3学时) 11
n 实验四 树和二叉树的操作(3学时) 18
n 实验五 查找算法实现(2学时) 22
n 实验六 排序综合实验(3学时) 26
班级 0831004 学号 2010213157 姓名 彭威威
第 4 周 星期四1 、 2 节 成绩
实验类型:验证性
实验要求:必修
实验学时: 2学时
一、实验目的:
参照给定的线性表顺序表类和链表类的程序样例,验证给出的线性表的常见算法。
二、实验要求:
1、掌握线性表顺序表类和链表类的特点。掌握线性表的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:
设计一个静态数组存储结构的顺序表类,要求编程实现如下任务:
1)建立一个线性表,首先依次输人整数数据元素(个数根据自己的需要键盘给定)
2)删除指定位置的数据元素(指定元素位置通过键盘输入)再依次显示删除后的线性表中的数据元素。
3)查找指定数据的数据元素(指定数据的大小通过键盘输入),若找到则显示位置,若没有找到就显示0。
四、要求:
1)采用顺序表实现,假设该顺序表的数据元素个数在最坏情况下不会超过50个。
2)写出完整的程序并能调试通过即可
五、实验原理:
(1)线性表在顺序存储下的插入运算
①首先处理以下3种异常情况:
当存储空间已满(n=m)时为“上溢”错误,不能进行插入,算法解释。
当i>n时认为在最后一个元素之后(第n+1个元素之前)插入。
当i<1时认为在第一个元素之前插入。
②从最后一个元素开始,直到第i个元素,其中每一个元素均往后一点一个位置。
③最后将新元素插入到第i个位置,并将线性表的长度增加1。
(2)线性表在顺序存储下的删除运算
①首先出来以下2种异常情况:
当线性表为空(n=0)时为“上溢”错误,不能进行插入,算法结束。
当i<1或i>n时,认为在最后一个元素之后(第n+1个元素之前)插入。
②从第i+1个元素开始,直到最后一个元素,其中每一个元素均一次往前移动一个 位置。
③最后将线性表的长度减小1。
(3)线性表在顺序存储下的查找运算
将所要查找的数与线性表里面的数比较,当找到时输出其所在位置,否则输出0
#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();
void ins_sq_LList(int,T);
int search_sq_LList(T);
void del_sq_LList(int);
};
//建立空顺序表
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>
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>
int sq_LList<T>::search_sq_LList(T b)
{ int i;
for(i=0;i<nn;i++)
if(v[i]==b)
return i+1;
return 0;
}
//在顺序表中删除指定未指定的元素
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;
}
int main()
{
int i,k,temp1,temp2,temp3;
sq_LList<int>s1(100);
cout<<"=========================="<<endl;
cout<<"输入数据的个数k:"<<endl;
cin>>k;
cout<<"=========================="<<endl;
cout<<"输入k个整型数据元素:"<<endl;
for(i=1;i<=k;i++)
{
cin>>temp1;
s1.ins_sq_LList(i,temp1);
}
cout<<"=========================="<<endl;
cout<<"输出顺序表对象s1:"<<endl;
s1.prt_sq_LList();
cout<<"=========================="<<endl;
cout<<"指定删除元素的位置:"<<endl;
cin>>temp2;
s1.del_sq_LList(temp2);
cout<<"再次输出顺序表对象s1:"<<endl;
s1.prt_sq_LList();
cout<<"=========================="<<endl;
cout<<"输入要查找的数据:"<<endl;
cin>>temp3;
cout<<"该数的位置为:"<<s1.search_sq_LList(temp3)<<endl;
return 0;
}
班级 0831004 学号 2010213157 姓名 彭威威
第 8 周 星期五7 、 8 节 成绩
实验类型:验证性
实验要求:必修
实验学时: 3学时
一、实验目的:
参照给定的栈类的程序样例,验证给出的栈的常见算法。
二、实验要求:
1、掌握栈的特点。掌握特殊线性表的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:
堆栈类测试和应用问题。要求:
(1)设计一个主函数实现对顺序堆栈类和链式堆栈类代码进行测试。测试方法为:依次把数据元素1,2,3,4,5入栈,然后出栈堆栈中的数据元素并在屏幕上显示。
(2)定义数据元素的数据类型为如下形式的结构体:
typedef struct
{ char taskname[10];//任务名
int taskno; //任务号
}DataType;
设计一个包含5个数据元素的测试数据,并设计一个主函数实现依次把5个数据元素入栈,然后出栈堆栈中的数据元素并在屏幕上显示。
四、要求
1)栈的长度都由自己定;
2)写出完整的程序并能调试通过即可。
3)重点理解栈的算法思想,能够根据实际情况选择合适的存储结构。
五、实验原理:
链式堆栈类
①栈的初始化,即建立一个空栈的顺序存储空间
②入栈运算,是指在栈顶位置插入一个新元素
③退栈运算,即取出栈顶元素赋给一个指定的变量
④读栈顶元素,是指将栈顶元素赋给一个指定的变量
链栈:
#include<iostream>
using namespace std;
template<class T>
struct node
{
T d;
node *next;
};
template<class T>
class linked_Stack
{
private:
node<T> *top;
public:
linked_Stack();
void prt_linked_Stack();
void ins_linked_Stack(T);
int flag_linked_Stack();
T del_linked_Stack();
T read_linked_Stack();
};
//链栈初始化
template<class T>
linked_Stack<T>::linked_Stack()
{
top=NULL;
return;
}
//检测链栈的状态
template<class T>
int linked_Stack<T>::flag_linked_Stack()
{
if(top==0)
return(0);
return(1);
}
//顺序输出栈中的元素
template<class T>
void linked_Stack<T>::prt_linked_Stack()
{
node<T> *p;
p=top;
if(p==NULL)
{
cout<<"Stack empty!"<<endl;
return;
}
do{
cout<<p->d<<endl;
p=p->next;
}while(p!=NULL);
return;
}
//入栈
template<class T>
void linked_Stack<T>::ins_linked_Stack(T x)
{ node<T> *p;
p=new node<T>;
p->d=x;
p->next=top;
top=p;
return;
}
//退栈
template<class T>
T linked_Stack<T>::del_linked_Stack()
{ T y;
node<T> *q;
if(top==NULL)
{
cout<<"Stack empty!"<<endl;
return(0);
}
q=top;
y=q->d;
top=top->next;
delete q;
return(y);
}
//读取栈顶元素
template<class T>
T linked_Stack<T>::read_linked_Stack()
{
if(top==NULL)
{
cout<<"Stack empty!"<<endl;
return(0);
}
return(top->d);
}
int main()
{
linked_Stack<int>s;
s.ins_linked_Stack(1);
s.ins_linked_Stack(2);
s.ins_linked_Stack(3);
s.ins_linked_Stack(4);
s.ins_linked_Stack(5);
cout<<"=========================="<<endl;
cout<<"输出栈中的元素:"<<endl;
s.prt_linked_Stack();
cout<<"=========================="<<endl;
if(s.flag_linked_Stack())
cout<<"栈顶元素:"<<s.read_linked_Stack()<<endl;
if(s.flag_linked_Stack())
cout<<"退栈元素:"<<s.del_linked_Stack()<<endl;
if(s.flag_linked_Stack())
cout<<"退栈元素:"<<s.del_linked_Stack()<<endl;
if(s.flag_linked_Stack())
cout<<"退栈元素:"<<s.del_linked_Stack()<<endl;
cout<<"=========================="<<endl;
cout<<"再次输出栈中的元素:"<<endl;
s.prt_linked_Stack();
return 0;
}
班级 0831004 学号 2010213157 姓名 彭威威
第 9 周 星期四9-11 节 成绩
实验类型:验证性
实验要求:必修
实验学时: 3学时
一、实验目的:
参照给定的队列类的程序样例,验证给出的队列的常见算法,并结合线性表类实现有关串的操作。
二、实验要求:
1、掌握队列、串的特点。掌握特殊线性表的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:
队列类测试和应用问题。要求:
设计一个主函数对循环队列类和链式队列类代码进行测试.测试方法为:依次把数据元素1,2,3,4,5入队,然后出队中的数据元素并在屏幕上显示。
四、要求:
1)队列的长度都由自己定;
2)写出完整的程序并能调试通过即可。
3)重点理解队列和串的算法思想,能够根据实际情况选择合适的存储结构。
4)栈、队列的算法是后续实验的基础(树、图、查找、排序等)。
五、实验原理:
(1)、循环队列类
①入队运算
首先判断循环队列是否满,当循环队列非空(算)且队尾指针等于排头指针时,说明循 环队列已满,不能进行入队运算。这种情况称为“上溢”,此时算法结束
然后敬爱那个队尾指针进一(rear=rear+1),并且置循环队列非空标志
最后将新元素插入到队尾指针指向的位置,并且置循环队列非空标志
②退队运算
首先判断循环队列是否为空,当循环队列为空(s=0)时,不能进行腿肚运算。这种情况称为“下溢”,此时算法结束
然后将排头指针进一(front=front+1),并当front=m+1时置front=1
再将排头指针指向元素赋给指定的变量
最后判断退队后循环队列是否为空。当front=rear时置循环队列空标志(s=0)
(2)、带链队列
①队列的初始化,建立一个空队列的顺序存储空间
②入队运算,指在循环队列的队尾加入一个新元素
③退队运算,在循环队列的派头位置退出一个元素并赋给指定的变量
循环队列类:
#include<iostream>
using namespace std;
template<class T>
class sq_Queue
{
private:
int mm;
int front;
int real;
int s;
T *q;
public:
sq_Queue(int);
void prt_sq_Queue();
void ins_sq_Queue(T);
T del_sq_Queue();
};
//建立空队列
template<class T>
sq_Queue<T>::sq_Queue(int m)
{
mm=m;
q=new T[mm];
front=mm;
real=mm;
s=0;
return;
}
//输出排头与队尾指针以及队中的元素
template<class T>
void sq_Queue<T>::prt_sq_Queue()
{
int i;
cout<<"front="<<front<<endl;
cout<<"real="<<real<<endl;
if(s==0)
{
cout<<"Queue empty"<<endl;
return;
}
i=front;
do{
i=i+1;
if(i==mm+1)
i=1;
cout<<q[i-1]<<endl;
}while(i!=real);
return;
}
//入队
template<class T>
void sq_Queue<T>::ins_sq_Queue(T x)
{
if((s==1)&&(real==front))
{
cout<<"Queue overflow!"<<endl;
return;
}
real=real+1;
if(real==mm+1)
real=1;
q[real-1]=x;
s=1;
return;
}
//退队
template<class T>
T sq_Queue<T>::del_sq_Queue()
{
T y;
if(s==0)
{
cout<<"Queue underflow!"<<endl;
return(0);
}
front=front+1;
if(front==mm+1)
front=1;
y=q[front-1];
if(front==real)
s=1;
return(y);
}
int main()
{
sq_Queue<int>q(5);
cout<<"==============================="<<endl;
cout<<"输出排头与队尾指针以及队中的元素:"<<endl;
q.prt_sq_Queue();
q.ins_sq_Queue(1);
q.ins_sq_Queue(2);
q.ins_sq_Queue(3);
q.ins_sq_Queue(4);
q.ins_sq_Queue(5);
cout<<"==============================="<<endl;
cout<<"输出排头与队尾指针以及队中的元素:"<<endl;
q.prt_sq_Queue();
cout<<"==============================="<<endl;
cout<<"输出退队元素:"<<endl;
cout<<q.del_sq_Queue()<<endl;
cout<<q.del_sq_Queue()<<endl;
cout<<q.del_sq_Queue()<<endl;
cout<<"==============================="<<endl;
cout<<"再次输出排头与队尾指针以及队中的元素:"<<endl;
q.prt_sq_Queue();
return 0;
}
链式队列:
#include<iostream>
using namespace std;
template<class T>
struct node
{ T d;
node *n;
};
template<class T>
class Q
{ private:
node<T>*a;
node<T>*b;
public:
Q();
void prt();
int flag();
void in(T);
T del();
};
//链队的初始化
#include<iostream>
using namespace std;
template<class T>
struct node
{ T d;
node *n;
};
template<class T>
class Q
{ private:
node<T>*a;
node<T>*b;
public:
Q();
void prt();
int flag();
void in(T);
T del();
};
//链队的初始化
template<class T>
Q<T>::Q()
{ a=NULL;
b=NULL;
return;
}
//顺序输出队列中的元素
template<class T>
void Q<T>::prt()
{ node<T>*p;
p=a;
if(p==NULL)
{ cout<<"empty!"<<endl;
return;
}
do{
cout<<p->d<<endl;
p=p->n;
}while(p!=NULL);
return;
}
//检测链队的状态
template<class T>
int Q<T>::flag()
{ if(a==NULL)
return(0);
return(1);
}
//入队
template<class T>
void Q<T>::in(T x)
{ node<T>*p;
p=new node<T>;
p->d=x;
p->n=NULL;
if(b==NULL) a=p;
else b->n=p;
b=p;
return;
}
//退队
template<class T>
T Q<T>::del()
{ T y;
node<T>*q;
if(a==NULL)
{
cout<<"empty!"<<endl;
return(0);
}
y=a->d;
q=a;
a=q->n;
delete q;
if(a==NULL)
b=NULL;
return(y);
}
int main()
{
Q<int>q;
q.in(1);q.in(2);q.in(3);q.in(4);q.in(5);
cout<<"============================"<<endl;
cout<<"输出带链队列中的元素:"<<endl;
q.prt();
cout<<"============================"<<endl;
if(q.flag())
cout<<"输出退队元素:"<<q.del()<<endl;
if(q.flag())
cout<<"输出退队元素:"<<q.del()<<endl;
if(q.flag())
cout<<"输出退队元素:"<<q.del()<<endl;
cout<<"============================"<<endl;
cout<<"再次输出带链队列中的元素:"<<endl;
q.prt();
return 0;
}
班级 0831004 学号 2010213157 姓名 彭威威
第 10 周 星期日5-7 节 成绩
实验类型:验证性
实验要求:必修
实验学时: 2学时
一、实验目的:
参照给定的二叉树类的程序样例,验证给出的有关二叉树的常见算法,并实现有关的操作。
二、实验要求:
1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:
1.设计实现二叉树类,要求:
(1)编写一个程序,首先建立不带头结点的二叉链式存储结构的二叉树,然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息,最后再测试查找函数和撤销函数的正确性。
(2)实现二叉树层次遍历的非递归算法。
(3)编写一主函数来验证算法实现。
2. 假设二叉树采用链式存储结构进行存储,编写一个算法,输出一个二叉树的所有叶子结点,并统计叶子结点个数。
四、实验原理:
(1)建立链式存储结构,输入给定二叉树及左右子树中的个结点值应按如下顺序:
①输入根结点值。
②若左子树不空,则输入左子树,否则输入一个结束符。
③若右子树不空,则输入右子树,否则输入一个结束符。
(2)前序遍历是指:先访问根结点,然后遍历左子树,最后遍历右子树;
中序遍历是指:先遍历左子树,然后访问根结点,最后遍历右子树;
后序遍历是指:先遍历左子树,然后遍历右子树,最后访问根结点。
(3)二叉树的前序遍历简单描述为:
①访问根结点;
②前序遍历左子树;
③前序遍历右子树;
(4)二叉树的中序遍历简单描述为:
①中序遍历左子树;
②访问根结点;
③中序遍历遍历右子树;
(5)二叉树的后序遍历的简单描述为:
①后序遍历左子树
②访问根结点;
③后序遍历右子树;
#include<iostream>
using namespace std;
int i=0;
template<class T>
struct B
{ T d;
B *l;
B *r;
};
template<class T>
class Tr
{ private:
B<T> *BT;
public:
Tr(){BT=NULL;return;}
void cr(T);
void in1();
void in2();
};
//生成二叉树
template<class T>
void Tr<T>::cr(T end)
{ B<T> *p;
T x;
cin>>x;
if(x==end) return;
p=new B<T>;
p->d=x;
p->l=NULL;
p->r=NULL;
BT=p;
Cr(p,1,end);
Cr(p,2,end);
return;
}
template<class T>
static Cr(B<T> *p,int k,T end)
{ B<T>*q;
T x;
cin>>x;
if(x!=end)
{
q=new B<T>;
q->d=x;
q->l=NULL;
q->r=NULL;
if(k==1) p->l=q;
if(k==2) p->r=q;
Cr(q,1,end);
Cr(q,2,end);
}
return 0;
}
//中序遍历
template<class T>
void Tr<T>::in1()
{ B<T>*p;
p=BT;
In1(p);
cout<<endl;
return;
}
template <class T>
static In1(B<T>*p)
{ if(p!=NULL)
{
In1(p->l);
cout<<p->d<<" ";
In1(p->r);
}
return 0;
}
//中序遍历输出叶子
template<class T>
void Tr<T>::in2()
{
B<T>*p;
p=BT;
In2(p);
cout<<endl;
return;
}
template <class T>
static In2(B<T>*p)
{
if(p!=NULL)
{
In2(p->l);
In2(p->r);
if((p->l==NULL)&&(p->r==NULL))
{
cout<<p->d<<" ";
i++;
}
}
return 0;
}
int main()
{ Tr<int>b;
cout<<"========================"<<endl;
cout<<"输入各节点值(-1结束符):"<<endl;
b.cr(-1);
cout<<"========================"<<endl;
cout<<"中序序列:"<<endl;
b.in1();
cout<<"========================"<<endl;
cout<<"中序序列叶子:"<<endl;
b.in2();
cout<<"========================"<<endl;
cout<<"叶子数为:"<<i<<endl;
return 0;
}
班级 0831004 学号 2010213157 姓名 彭威威
第 11 周 星期三7 、 8 节 成绩
实验类型:验证性
实验要求:必修
实验学时: 2学时
一、实验目的:
参照各种查找算法程序样例,验证给出的查找常见算法。
二、实验要求:
1、掌握各种查找算法的特点,测试并验证查找的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:
1. 建立有序表,采用折半查找实现某一已知的关键字的查找。
2.利用折半查找算法在一个有序表中插入一个元素,并保持表的有序性。
#include<iostream>
using namespace std;
template<class T>
class s
{
private:
int a;
int b;
T *v;
public:
s(){a=0;b=0;return};
s(int);
int se(T);
int in(T);
void prt();
};
//顺序表初始化
template<class T>
s<T>::s(int c)
{
a=c;
v=new T[a];
b=0;
return;
}
//查找指定的元素
template<class T>
int s<T>::se(T x)
{
int i,j,k;
i=1;
j=b;
while(i<=j)
{
k=(i+j)/2;
if(v[k-1]==x)
return k-1;
if(v[k-1]>x)
i=k+1;
else
j=k-1;
}
return(-1);
}
//插入元素
template<class T>
int s<T>::in(T x)
{
int k;
if(a==b)
{
cout<<"overflow!"<<endl;
return(-1);
}
k=b;
while((v[k]<x)&&(k>=0))
{
v[k+1]=v[k];
k=k-1;
}
v[k+1]=x;
b=b+1;
return(1);
}
//顺序输出元素
template<class T>
void s<T>::prt()
{
int i;
for(i=0;i<b;i++)
cout<<v[i]<<endl;
return;
}
int main()
{
int i,n,m,p;
s<int>s1(10);
cout<<"=============================="<<endl;
cout<<"顺序表s1从大到小输入7到1:"<<endl;
for(i=1;i<=7;i++)
{ cin>>n;
s1.in(n);
}
cout<<"=============================="<<endl;
cout<<"第1次输出顺序表对象s1:"<<endl;
s1.prt();
cout<<"=============================="<<endl;
cout<<"输入要查找的数:"<<endl;
cin>>m;
cout<<"数的位置是:"<<s1.se(m)<<endl;
cout<<"=============================="<<endl;
cout<<"插入一个数:"<<endl;
cin>>p;
s1.in(p);
cout<<"=============================="<<endl;
cout<<"第2次输出顺序表对象s1:"<<endl;
s1.prt();
return 0;
}
班级 0831004 学号 2010213157 姓名 彭威威
第 12 周 星期五7 、 8 节 成绩
实验类型:综合性
实验要求:必修
实验学时: 3学时
一、实验目的:
参照各种排序算法程序样例,验证给出的排序常见算法。
二、实验要求:
1、掌握各种排序算法的特点,测试并验证排序的常见算法。
2、提交实验报告,报告内容包括:目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。
三、实验内容:
输入一组关键字序列分别实现下列排序:
1.实现简单选择排序、直接插入排序和冒泡排序。
2.实现希尔排序算法。
3.实现快速排序算法(取第一个记录或中间记录作为基准记录)。
4.快速排序的非递归算法。
把上述几种排序的算法编写成菜单,根据输入的数字不同执行对应的排序算法。
#include<iostream>
#include<iomanip>
using namespace std;
//冒泡排序
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 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 shel(T p[],int n)
{ int i,j,k;
T t;
k=n/2;
while(k>0)
{
for(j=k;j<=n-1;j++)
{
t=p[j];
i=j-k;
while((i>=0)&&(p[i]>t))
{
p[i+k]=p[i];
i=i-k;
}
p[i+k]=t;
}
k=k/2;
}
return;
}
//简单选择排序
template<class T>
void select(T p[],int n)
{ int i,j,k;
T d;
for(i=0;i<n-1;i++)
{ k=i;
for(j=i+1;j<n;j++)
if(p[j]<p[k])
k=j;
if(k!=j)
{
d=p[i];
p[i]=p[k];
p[k]=d;
}
}
return;
}
int main()
{ int i,j;
double p[50],r=1.0;
for(i=0;i<50;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<50;i++)
p[i]=100.0+200.0*p[i];
cout<<"=================================================="<<endl;
cout<<"排序前的序列:"<<endl;
for(i=0;i<10;i++)
{ for(j=0;j<5;j++)
cout<<setw(10)<<p[5*i+j];
cout<<endl;
}
cout<<"=================================================="<<endl;
bub(p,10);
qck(p+10,10);
insort(p+20,10);
shel(p+30,10);
select(p+40,10);
cout<<"排序后的序列:"<<endl;
for(i=0;i<10;i++)
{
for(j=0;j<5;j++)
cout<<setw(10)<<p[5*i+j];
cout<<endl;
}
return 0;
}
计算机软件技术基础实验报告姓名班级0801105学号日期20xx125班级0801105学号姓名第5周星期三910节成绩一实验目的…
山东建筑大学实验报告学院信电学院班级姓名课程计算机软件技术基础实验日期20xx年11月22日成绩实验八数据库应用系统开发一实验目的…
计算机软件基础实验报告实验一一元多项式的相加一实验的目的与要求1熟悉单链表的一些操作2掌握采用链表结构实现一元多项式的相加的算法二…
计算机软件技术基础实验报告专业年级学号学生姓名指导老师南华大学计算机学院编I实验要求1每次实验中有若干习题每个学生至少应该完成其中…
石家庄铁道大学实验报告课程名称计算机软件基础建筑与艺术学院系11021班试验者姓名学号实验日期年月日评分教师签名123456789…
大学计算机基础课程实验报告手册学院年级专业姓名学号2220xx319xx20xx任课教师上机地点以上由学生填写实验教师签字西南大学…
太原理工大学现代科技学院计算机软件技术基础课程实验报告专业班级学号姓名指导教师太原理工大学现代科技学院实验报告装订线实验名称顺序表…
上海建桥学院本科实验报告课程名称学号姓名专业班级计算机应用基础1222534单国原物流管理B121指导教师朱凯伦课内实验目录及成绩…
计算机软件基础实践报告题目C语言程序上机操作专业学生姓名准考证号指导教师20xx年5月1一单链表实验内容单链表的定义创建插入和删除…
软件开发技术基础实验报告姓名XXXXX学号XXXXXXXx班级XXXXXXX指导教师实验名称实验一线性表的操作班级学号姓名第周星期…
计算机软件技术基础实验报告实验一代码编写于VC60环境下includequotiostreamquotincludeltconio…