问题：设计一个顺序表类。
顺序表是一种常用的数据结构，它有点类似于 C++ 语言中的数组，即表中的各表项（数据）被存放在一块连续的内存中。与数组不同的是，顺序表中的各表项必须是相邻的，即各数据之间不得留有空白。若表未满，所有的空白必须留在表的尾部。
顺序表的基本操作主要有：
1,建立一个空表
2,销毁一个顺序表
3,清空顺序表
4,测试顺序表是否为空表
5,测试顺序表是否已满
6,获得顺序表的最大长度
7,获得表中实际元素个数
8,取得表中指定位置上元素的值
9,在表中查找指定的数据元素
10,在指定位置插入一个数据元素
11,删除表中指定位置上的数据元素
12,遍历顺序表，主要用于测试顺序表设计思想：
1,通常情况下，一个具体的数据结构仅能存放某一种特定的数据元素。为方便起见，本例所设计的顺序表中仅能存放 int
型数据。
2,考虑到通用性，顺序表的大小应能由用户任意指定。因此，
该类应当拥有一个 int* 型数据成员，根据用户的要求，利用
new 运算符为该数据成员申请一块动态指定大小的内存。
3,该类必须拥有一个 int 型数据成员来记录顺序表的大小；还须有一个 int 型数据成员来记录表中当前存放的数据元素的个数。注意：回顾顺序表与普通数组的区别可以发现，后者同时还指出了当前表中第一个空白位置。
4,顺序表的创建与销毁分别由构造函数和析构函数来完成。
// QLIST.H
#if !defined _QLIST_H_ // 防止重复嵌放
#define _QLIST_H_
#include <iostream.h>
class QList {
protected:
int *pData; // 指向动态数组的指针
int nNumElem; // 当前元素个数
int nSize; // 顺序表的大小
public:
QList(int = 10);
~QList() { delete []pData; }
void Clear() { nNumElem = 0; }
int IsEmpty() { return nNumElem == 0; }
int IsFull { return nNumElem >= nSize; }
int Length() { return nSize; }
int NumberOfElemts() { return nNumElem; }
int Append(int);
int Insert(int,int);
int Delete(int,int&);
int Find(int);
void Traverse();
};
#endif
// End of QLIST.H
// LIST.CPP
#include "qlist.h"
QList::QList(int n) // 构造函数
{
if(n != 0)
pData = new int[n];
else
pData = 0;
nSize = n;
nNumElem = 0;
}
int QList::Append(int nNewElem) // 添加数据元素
{
if(IsFull())
return 0;
pData[nNumElem ++] = nNewElem;
return 1;
}
int QList::Insert(int nIndex,int nNewElem) // 插入数据元素
{
if(IsFull() || nIndex > nNumElem || nNumElem >= nSize)
return 0; // 返回出错信息
for(int i = nNumElem; i > nIndex; i --)
pData[i] = pData[i - 1]; // 移动
pData[nIndex] = nNewElem; // 插入
nNumElem ++; // 当前元素个数加一
return 1; // 操作正常
}
int QList::Delete(int nIndex,int& rElem) // 删除数据元素
{
if(IsEmpty() || nIndex >= nNumElem || nNumElem == 0)
return 0;
rElem = pData[nIndex]; // 保存被删元素值
for(int i = nIndex; i < nNumElem; i ++) // 移动
pData[i] = pData[i + 1]; // 填补被删位置
nNumElem --; // 当前元素个数减一
return 1;
}
int QList::Find(int nElem) // 查找指定元素
{
for(int i = 0; i < nNumElem; i ++)
if(pData[i] == nElem)
return i; // 查找成功
return -1; // 查找失败
}
void QList::Traverse() // 遍历顺序表
{
for(int i = 0; i < nNumElem; i ++)
cout << pData[i] << endl;
}
// End of LIST.CPP
下面给出一个使用 QList 类的例子。该例调用了 QList 类的部分成员函数。作为一个习题，请同学们对该例子程序进行补充，以将 QList 类中所有的成员函数都测试到。
// TESTLIST.CPP
#include "qlist.h"
#include <stdlib.h>
void main()
{
QList Lst(20);
int nElem;
for(int i = 0; i < 15; i ++) {
nElem = rand() % 100;
Lst.Append(nElem);
}
Lst.Traverse();
cout << Lst.Length() << '\t' << Lst.NumberOfElemts() << endl;
if(Lst.Delete(10,nElem))
cout << endl << nElem << endl << endl;
Lst.Traverse();
cout << Lst.Length() << '\t' << Lst.NumberOfElemts() << endl;
}
// End of TESTLIST.CPP
问题：设计一个排序顺序表类。
QList 类的对象中所存放的数据是无序的，这在许多应用中将显得很不方便。比如，类中的成员函数 Find() 在查找一个给定元素时效率就不高，特别是当被查找的元素位于顺序表的尾部时。
通常，高效的查找算法都是建立在有序表上的。因此，设计一个有序的顺序表其意义十分重大。
当使用面向过程的程序语言进行程序设计时，一旦数据结构发生变化，程序代码一般都需要重新编写，重复工作量相当大。而利用面向对象的程序语言编程时，则可以通过继承重用已有的代码，这就大大地提高了编码效率。
排序顺序表是一个顺序表，因此 SortList 类只需从 QList 类公有派生即可。事实上,QList 类中的数据成员被说明成保护有，其目的就是为此作准备的。
// SORTLIST.H
#if !defined _SORTLIST_H_
#define _SORTLIST_H_
#include "qlist.h"
class SortList,public QList {
private:
void Swap(int&,int&);
public:
SortList(int n = 10),QList(n) {}
~SortList() {}
void Sort();
int Search(int,int,int);
};
#endif
// End of SORTLIST.H
在 SortList 类中，除必要的构造函数和析构函数外，实际上只说明了 3 个成员函数。然而，由于该类自 QList 类派生而来，它实际上还拥有 QList 中所有的成员函数。
注意：在 SortList 类中说明了一个私有的成员函数 Swap()，
该函数仅供本类中的成员函数调用。
// SORTLIST.CPP
#include "sortlist.h"
void SortList::Swap(int &d1,int &d2) // 交换两数据的值
{
int nTemp = d1;
d1 = d2;
d2 = nTemp;
}
冒泡排序算法冒泡排序（ Bubble Sort）的具体作法是（以非递减为例）：
1,令 i = 1，比较 Ri 和 Ri+1 的关键字，若前者大于后者，则交换两者的位置；否则什么都不做。
2,将 i 加 1；若 i = n，则结束；否则转向 1。
以上的操作叫做一趟冒泡。在一趟冒泡后，序列中关键字最大的元素就被交换到序列的尾部，就好象水中的气泡由于重量轻而冒到水面一样。
经过一趟冒泡后，序列的尾部就构成了有序序列，接着对余下的 n – 1 个元素进行冒泡排序，直至序列的长度为 1 为止。
以序列 15,64,33,5,7,89,6,24 为例，说明冒泡排序的过程。
第一趟冒泡
15 64 33 5 7 89 6 24
15 33 64 5 7 89 6 24
15 33 5 64 7 89 6 24
15 33 5 7 64 89 6 24
15 33 5 7 64 89 6 24
15 33 5 7 64 6 89 24
15 33 5 7 64 6 24 [89]
第二趟冒泡后：
15 5 7 33 6 24 [64 89]
第三趟冒泡后：
5 7 15 6 24 [33 64 89]
第四趟冒泡后：
5 7 6 15 [24 33 64 89]
第五趟冒泡后：
5 6 7 [15 24 33 64 89]
第六趟冒泡后：
5 6 [7 15 24 33 64 89]
第七趟冒泡后：
5 [6 7 15 24 33 64 89]
排序完成。
由以上的排序过程可以看出，若某一趟冒泡过程中没有发生一次交换，则序列就已经是完全有序的了。比如，上述过程中的第七趟冒泡就没有必要。事实上，若某次冒泡过程中仅仅在序列的第一个位置处发生了一次交换，也说明序列已经有序。
void SortList::Sort() // 冒泡排序
{
int i,j,nDown;
for(i = nNumElem - 2; i > 0; i --){
nDown = 0;
for(j = 0; j < i; j ++)
if(pData[j] > pData[j + 1]) {
Swap(pData[j],pData[j + 1]);
nDown = j;
}
if(nDown == 0)
break;
}
}
二分法查找算法二分查找（ Binary Searching）也称折半查找，是一种高效的查找算法。但是该算法要求查找表必须是有序的。不失一般性，这里假定查找表是一个不降的顺序表。
二分查找的基本思想为：先确定待查记录所在的范围（区间），然后在缩小了的范围中进行二分查找，直到找到或缩小后的范围中已无记录为止。
设置 3 个变量,Low,High 和 Mid，分别用来标识待查范围的下界、上界和中点位置，即,Low 的值为待查范围的最小下标值,High 的值为待查范围的最大下标值，而中点位置
Mid =?(Low + High) / 2? 。在进行二分查找时，每次将给定值与 Mid 所标识记录的关键字进行比较，若匹配，则查找成功。否则，若给定值大于 Mid 所标识记录的关键字，则待查找记录只可能出现在 Low 至 Mid? 1 的范围内，这时，下一步的查找范围应为
Low = Low,High = Mid – 1；
否则，下一步的查找范围应为
Low = Mid + 1,High = High。
int SortList::Search(int nLow,int nHi,int nKey) // 二分查找
{
int nMid = (nLow + nHi) / 2;
if(nHi < nLow)
return -1;
if(nKey == pData[nMid])
return nMid;
if(nKey < pData[nMid])
return Search(nLow,nMid - 1,nKey);
else
return Search(nMid + 1,nHi,nKey);
}
习题：
上机实现 QList 和 SortList 类，并编写测试程序将类中的所有成员函数均测试到。
顺序表是一种常用的数据结构，它有点类似于 C++ 语言中的数组，即表中的各表项（数据）被存放在一块连续的内存中。与数组不同的是，顺序表中的各表项必须是相邻的，即各数据之间不得留有空白。若表未满，所有的空白必须留在表的尾部。
顺序表的基本操作主要有：
1,建立一个空表
2,销毁一个顺序表
3,清空顺序表
4,测试顺序表是否为空表
5,测试顺序表是否已满
6,获得顺序表的最大长度
7,获得表中实际元素个数
8,取得表中指定位置上元素的值
9,在表中查找指定的数据元素
10,在指定位置插入一个数据元素
11,删除表中指定位置上的数据元素
12,遍历顺序表，主要用于测试顺序表设计思想：
1,通常情况下，一个具体的数据结构仅能存放某一种特定的数据元素。为方便起见，本例所设计的顺序表中仅能存放 int
型数据。
2,考虑到通用性，顺序表的大小应能由用户任意指定。因此，
该类应当拥有一个 int* 型数据成员，根据用户的要求，利用
new 运算符为该数据成员申请一块动态指定大小的内存。
3,该类必须拥有一个 int 型数据成员来记录顺序表的大小；还须有一个 int 型数据成员来记录表中当前存放的数据元素的个数。注意：回顾顺序表与普通数组的区别可以发现，后者同时还指出了当前表中第一个空白位置。
4,顺序表的创建与销毁分别由构造函数和析构函数来完成。
// QLIST.H
#if !defined _QLIST_H_ // 防止重复嵌放
#define _QLIST_H_
#include <iostream.h>
class QList {
protected:
int *pData; // 指向动态数组的指针
int nNumElem; // 当前元素个数
int nSize; // 顺序表的大小
public:
QList(int = 10);
~QList() { delete []pData; }
void Clear() { nNumElem = 0; }
int IsEmpty() { return nNumElem == 0; }
int IsFull { return nNumElem >= nSize; }
int Length() { return nSize; }
int NumberOfElemts() { return nNumElem; }
int Append(int);
int Insert(int,int);
int Delete(int,int&);
int Find(int);
void Traverse();
};
#endif
// End of QLIST.H
// LIST.CPP
#include "qlist.h"
QList::QList(int n) // 构造函数
{
if(n != 0)
pData = new int[n];
else
pData = 0;
nSize = n;
nNumElem = 0;
}
int QList::Append(int nNewElem) // 添加数据元素
{
if(IsFull())
return 0;
pData[nNumElem ++] = nNewElem;
return 1;
}
int QList::Insert(int nIndex,int nNewElem) // 插入数据元素
{
if(IsFull() || nIndex > nNumElem || nNumElem >= nSize)
return 0; // 返回出错信息
for(int i = nNumElem; i > nIndex; i --)
pData[i] = pData[i - 1]; // 移动
pData[nIndex] = nNewElem; // 插入
nNumElem ++; // 当前元素个数加一
return 1; // 操作正常
}
int QList::Delete(int nIndex,int& rElem) // 删除数据元素
{
if(IsEmpty() || nIndex >= nNumElem || nNumElem == 0)
return 0;
rElem = pData[nIndex]; // 保存被删元素值
for(int i = nIndex; i < nNumElem; i ++) // 移动
pData[i] = pData[i + 1]; // 填补被删位置
nNumElem --; // 当前元素个数减一
return 1;
}
int QList::Find(int nElem) // 查找指定元素
{
for(int i = 0; i < nNumElem; i ++)
if(pData[i] == nElem)
return i; // 查找成功
return -1; // 查找失败
}
void QList::Traverse() // 遍历顺序表
{
for(int i = 0; i < nNumElem; i ++)
cout << pData[i] << endl;
}
// End of LIST.CPP
下面给出一个使用 QList 类的例子。该例调用了 QList 类的部分成员函数。作为一个习题，请同学们对该例子程序进行补充，以将 QList 类中所有的成员函数都测试到。
// TESTLIST.CPP
#include "qlist.h"
#include <stdlib.h>
void main()
{
QList Lst(20);
int nElem;
for(int i = 0; i < 15; i ++) {
nElem = rand() % 100;
Lst.Append(nElem);
}
Lst.Traverse();
cout << Lst.Length() << '\t' << Lst.NumberOfElemts() << endl;
if(Lst.Delete(10,nElem))
cout << endl << nElem << endl << endl;
Lst.Traverse();
cout << Lst.Length() << '\t' << Lst.NumberOfElemts() << endl;
}
// End of TESTLIST.CPP
问题：设计一个排序顺序表类。
QList 类的对象中所存放的数据是无序的，这在许多应用中将显得很不方便。比如，类中的成员函数 Find() 在查找一个给定元素时效率就不高，特别是当被查找的元素位于顺序表的尾部时。
通常，高效的查找算法都是建立在有序表上的。因此，设计一个有序的顺序表其意义十分重大。
当使用面向过程的程序语言进行程序设计时，一旦数据结构发生变化，程序代码一般都需要重新编写，重复工作量相当大。而利用面向对象的程序语言编程时，则可以通过继承重用已有的代码，这就大大地提高了编码效率。
排序顺序表是一个顺序表，因此 SortList 类只需从 QList 类公有派生即可。事实上,QList 类中的数据成员被说明成保护有，其目的就是为此作准备的。
// SORTLIST.H
#if !defined _SORTLIST_H_
#define _SORTLIST_H_
#include "qlist.h"
class SortList,public QList {
private:
void Swap(int&,int&);
public:
SortList(int n = 10),QList(n) {}
~SortList() {}
void Sort();
int Search(int,int,int);
};
#endif
// End of SORTLIST.H
在 SortList 类中，除必要的构造函数和析构函数外，实际上只说明了 3 个成员函数。然而，由于该类自 QList 类派生而来，它实际上还拥有 QList 中所有的成员函数。
注意：在 SortList 类中说明了一个私有的成员函数 Swap()，
该函数仅供本类中的成员函数调用。
// SORTLIST.CPP
#include "sortlist.h"
void SortList::Swap(int &d1,int &d2) // 交换两数据的值
{
int nTemp = d1;
d1 = d2;
d2 = nTemp;
}
冒泡排序算法冒泡排序（ Bubble Sort）的具体作法是（以非递减为例）：
1,令 i = 1，比较 Ri 和 Ri+1 的关键字，若前者大于后者，则交换两者的位置；否则什么都不做。
2,将 i 加 1；若 i = n，则结束；否则转向 1。
以上的操作叫做一趟冒泡。在一趟冒泡后，序列中关键字最大的元素就被交换到序列的尾部，就好象水中的气泡由于重量轻而冒到水面一样。
经过一趟冒泡后，序列的尾部就构成了有序序列，接着对余下的 n – 1 个元素进行冒泡排序，直至序列的长度为 1 为止。
以序列 15,64,33,5,7,89,6,24 为例，说明冒泡排序的过程。
第一趟冒泡
15 64 33 5 7 89 6 24
15 33 64 5 7 89 6 24
15 33 5 64 7 89 6 24
15 33 5 7 64 89 6 24
15 33 5 7 64 89 6 24
15 33 5 7 64 6 89 24
15 33 5 7 64 6 24 [89]
第二趟冒泡后：
15 5 7 33 6 24 [64 89]
第三趟冒泡后：
5 7 15 6 24 [33 64 89]
第四趟冒泡后：
5 7 6 15 [24 33 64 89]
第五趟冒泡后：
5 6 7 [15 24 33 64 89]
第六趟冒泡后：
5 6 [7 15 24 33 64 89]
第七趟冒泡后：
5 [6 7 15 24 33 64 89]
排序完成。
由以上的排序过程可以看出，若某一趟冒泡过程中没有发生一次交换，则序列就已经是完全有序的了。比如，上述过程中的第七趟冒泡就没有必要。事实上，若某次冒泡过程中仅仅在序列的第一个位置处发生了一次交换，也说明序列已经有序。
void SortList::Sort() // 冒泡排序
{
int i,j,nDown;
for(i = nNumElem - 2; i > 0; i --){
nDown = 0;
for(j = 0; j < i; j ++)
if(pData[j] > pData[j + 1]) {
Swap(pData[j],pData[j + 1]);
nDown = j;
}
if(nDown == 0)
break;
}
}
二分法查找算法二分查找（ Binary Searching）也称折半查找，是一种高效的查找算法。但是该算法要求查找表必须是有序的。不失一般性，这里假定查找表是一个不降的顺序表。
二分查找的基本思想为：先确定待查记录所在的范围（区间），然后在缩小了的范围中进行二分查找，直到找到或缩小后的范围中已无记录为止。
设置 3 个变量,Low,High 和 Mid，分别用来标识待查范围的下界、上界和中点位置，即,Low 的值为待查范围的最小下标值,High 的值为待查范围的最大下标值，而中点位置
Mid =?(Low + High) / 2? 。在进行二分查找时，每次将给定值与 Mid 所标识记录的关键字进行比较，若匹配，则查找成功。否则，若给定值大于 Mid 所标识记录的关键字，则待查找记录只可能出现在 Low 至 Mid? 1 的范围内，这时，下一步的查找范围应为
Low = Low,High = Mid – 1；
否则，下一步的查找范围应为
Low = Mid + 1,High = High。
int SortList::Search(int nLow,int nHi,int nKey) // 二分查找
{
int nMid = (nLow + nHi) / 2;
if(nHi < nLow)
return -1;
if(nKey == pData[nMid])
return nMid;
if(nKey < pData[nMid])
return Search(nLow,nMid - 1,nKey);
else
return Search(nMid + 1,nHi,nKey);
}
习题：
上机实现 QList 和 SortList 类，并编写测试程序将类中的所有成员函数均测试到。
