北京工业大学耿丹学院
《软件技术基础》课程实验报告
注：本表格可直接采用计算机输入填写，但承诺人签字必须手写。
实验一 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
实验一 线性表的操作（2学时）
班级 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;
}
实验二 栈的操作（3学时）
班级 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;
}
实验三 队列的操作（3学时）
班级 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;
}
实验四 树和二叉树的操作（3学时）
班级 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;
}
实验五 查找算法实现（2学时）
班级 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;
}
实验六 排序综合实验（3学时）
班级 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;
}
