数据结构实验报告四

学生实验报告

开课学院及实验室：年月日
学院年级、专业、班姓名学号
实验课程名称数据结构成绩
实验项目名称查找和算法>排序算法实现指导老师
评语:
一、实验目的
1、各种算法>排序算法的实现
2、各种查找算法实现
二、使用仪器、器材
微机一台
编程软件：C++
三、实验内容及原理
<简要描述具体任务；填写程序设计中使用的数据结构及算法（算法思路和程序框架）>
1、各种算法>排序算法的实现
用随机函数生成16个2位正整数（10~99），实现插入排序、选择排序、冒泡排序、双向冒泡、快速排序、二路归并排序等多种算法>排序算法，输出排序中间过程、统计关键字的比较次数和记录的移动次数。
2、各种查找算法实现
（1）顺序查找：使用数组或链表结构。用随机函数生成16个不重复的字母（’a’~’z’），键盘输入待查找的字母，返回查找成功与否，若成功则返回该字母所在的位置（序号），并计算比较次数。
（2）折半查找：用数组实现，查找前元素先排序。计算比较次数。分别用查找成功、不成功进行测试。
（3）二叉查找树：手工输入10个字母，生成一棵二叉查找树，用递归算法打印树结构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次数。分别用查找成功、不成功进行测试。
四、实验过程原始数据记录
<代码/程序执行结果/操作结果>
1、各种算法>排序算法的实现
用随机函数生成16个2位正整数（10~99），实现插入排序、选择排序、冒泡排序、双向冒泡、快速排序、二路归并排序等多种算法>排序算法，输出排序中间过程、统计关键字的比较次数和记录的移动次数。
源代码：
#include
using namespace std;
#define MAXSIZE 20
typedef struct
{
int key;
}Int;
typedef struct
{
Int r[MAXSIZE + 1];//存储空间基地址
int length;//顺序表长度
}SqList;
int count_compare;
int count_move;
void Create_SqList(SqList& L)//随机生成顺序表二位数
{
count_compare = 0;//初始化比较次数
count_move = 0;//初始化移动次数
cout << “Randomly generate 10 double digits” << endl;
for (int i = 1; i <= L.length; i++)
{
L.r[i].key = rand() % 90 + 10;
cout << L.r[i].key << " ";
}
cout << endl;
}
void Printf(SqList L)
{
for (int i = 1; i <= L.length; i++)
{
cout << L.r[i].key << " ";
}
cout << endl;
}
void InsertSort(SqList& L)//直接插入排序
{
cout << “Possessing of Direct Insertion Sort:” << endl;
for (int i = 2; i <= L.length; i++)
{
if (L.r[i].key < L.r[i - 1].key)//若小于，需将r[i]插入有序子表
{
int j;
L.r[0] = L.r[i];//将待插入的记录暂存到监视岗
L.r[i] = L.r[i - 1];//r[i-1]后移
for (j = i - 2; L.r[0].key < L.r[j].key; --j)//从后向前寻找插入位置
{
L.r[j + 1] = L.r[j];//记录逐个后移，直到找到插入位置
}
L.r[j + 1] = L.r[0];//将r[0],插入到正确位置
count_move++;
}
Printf(L);
}
cout << “Result of Direct Insertion Sort:” << endl;
Printf(L);
count_compare = L.length - 1;
cout << "Comparison times of direct insertion sort: " << count_compare << endl;
cout << "The number of moves for direct insertion sort: " << count_move << endl;
cout << endl;
}
void SelectSort(SqList& L)//选择排序
{
cout << “Possessing of Select Sort:” << endl;
Create_SqList(L);
for (int i = 1; i < L.length; ++i)
{
int k = i;
int j;
for (j = i + 1; j <= L.length; ++j)
{
if (L.r[j].key < L.r[k].key)
{
k = j;
}
}
if (k != j)
{
Int t = L.r[i];
L.r[i] = L.r[k];
L.r[k] = t;
count_move++;
}
Printf(L);
}
cout << “Result of Selecting Sort:” << endl;
Printf(L);
count_compare = ((L.length - 1) * L.length) / 2;
cout << "Comparison times of selecting sort: " << count_compare << endl;
cout << "The number of moves for selecting sort: " << count_move << endl;
cout << endl;
}
void BubbleSort(SqList& L)//冒泡排序
{
cout << “Possessing of Bubble Sort:” << endl;
Create_SqList(L);
int m = L.length - 1;
int flag = 1;
while ((m > 0) && (flag == 1))
{
flag = 0;//flag置为0，如果本趟排序没有发生变换，则不会执行下一趟排序
for (int j = 1; j <= m; j++)
{
if (L.r[j].key > L.r[j + 1].key)
{
flag = 1;//flag置为1，表示本趟排序发生了变化
Int t = L.r[j];
L.r[j] = L.r[j + 1];
L.r[j + 1] = t;
count_move++;
Printf(L);
}
count_compare++;
}
–m;
}
cout << “Result of Bubble Sort:” << endl;
Printf(L);
cout << "Comparison times of Bubble sort: " << count_compare << endl;
cout << "The number of moves for Bubble sort: " << count_move << endl;
cout << endl;
}
void swap(int& x, int& y)
{
int temp;
temp = x;
x = y;
y = temp;
count_move++;
}
void TwoBubbleSort(SqList& L)//双向冒泡排序
{
cout << “Bidirectional Bubble Sort” << endl;
Create_SqList(L);
cout << “Possessing of Bidirectional Bubble Sort:” << endl;
int left = 0;
int right = L.length - 1;
int shift = 1;//shift为记录左右两端已排序的元素位置
while (left < right)
{
//往右排序
count_compare++;
for (int i = left; i <= right; i++)
{
if (L.r[i].key > L.r[i + 1].key)
{
//第一个数比第二个数大，交换
swap(L.r[i].key, L.r[i + 1].key);
shift = i;
}
}
right = shift;
for (int i = right - 1; i >= left; i–)
{
//向左排序
if (L.r[i].key > L.r[i + 1].key)
{
//第一个数比第二个数大，交换
swap(L.r[i].key, L.r[i + 1].key);
shift = i + 1;
}
}
Printf(L);
left = shift;
}
cout << “Result of Bidirectional Bubble Sort:” << endl;
Printf(L);
cout << "Comparison times of Bidirectional Bubble Sort: " << count_compare << endl;
cout << "The number of moves for Bidirectional Bubble Sort: " << count_move << endl;
cout << endl;
}
int Partition(SqList& L, int low, int high)//快速排序
{
L.r[0] = L.r[low];//用子表的第一个记录做枢轴记录
int pivotkey = L.r[low].key;//枢轴记录关键字保存在pivotkey中
while (low < high)
{
while ((low < high) && (L.r[high].key >= pivotkey))
{
–high;
count_compare++;
}
if (low < high)
{
L.r[low] = L.r[high];
count_move++;
count_compare++;
Printf(L);
}
while (low < high && L.r[low].key <= pivotkey)
{
++low;
count_compare++;
}
if (low < high)
{
L.r[low] = L.r[0];
count_move++;
count_compare++;
Printf(L);
}
}
L.r[low] = L.r[0];
count_move++;
return low;
}
void QSort(SqList& L, int low, int high)
{
if (low < high)//长度大于1
{
int pivotloc = Partition(L, low, high);
//将L.r[low…high]一分为二，povotloc是枢轴位置
QSort(L, low, pivotloc - 1);//对左子表递归排序
QSort(L, pivotloc + 1, high);//对右子表递归排序
}
}
void QuickSort(SqList& L)//快速排序
{
cout << “Quickly Sorting:” << endl;
Create_SqList(L);
cout << “Possessing of quickly sorting:” << endl;
QSort(L, 1, L.length);
cout << “Result of Quickly Sort:” << endl;
Printf(L);
cout << "Comparison times of Quickly Sort: " << count_compare << endl;
cout << "The number of moves for Quickly Sort: " << count_move << endl;
cout << endl;
}
void Merge(Int R[], Int T[], int low, int mid, int high, SqList& L)//二路归并排序
{
int i = low;
int j = mid + 1;
int k = low;
while (i <= mid && j <= high)
{
count_compare++;//将R中记录由小到大并入T中
if (R[i].key <= R[j].key)
{
T[k++] = R[i++];
count_move++;
}
else
{
T[k++] = R[j++];
count_move++;
}
}
while (i <= mid)
{
T[k++] = R[i++];
count_move++;
}
while (j <= high)
{
T[k++] = R[j++];
count_move++;
}
Printf(L);
}
void MSort(Int R[], Int T[], int low, int high, SqList& L)
{
int mid;
Int S[MAXSIZE];
if (low == high)
{
T[low] = R[low];
}
else
{
mid = (low + high) / 2;
MSort(R, S, low, mid, L);
MSort(R, S, mid + 1, high, L);
Merge(S, T, low, mid, high, L);
}
}
void MergeSort(SqList& L)
{
cout << “Merge sort:” << endl;
Create_SqList(L);
cout << “Possessing of Merge Sort:” << endl;
MSort(L.r, L.r, 1, L.length, L);
cout << “Result of Merge Sort” << endl;
Printf(L);
cout << "Comparison times of Merge Sort: " << count_compare << endl;
cout << "The number of moves for Merge Sort: " << count_move << endl;
cout << endl;
}
int main()
{
SqList L;
L.length = 10;
//Create_SqList(L);
//InsertSort(L);
//SelectSort(L);
//BubbleSort(L);
//TwoBubbleSort(L);
//QuickSort(L);
MergeSort(L);
}
直接插入排序：
程序运行结果：

选择排序：
程序运行结果：

冒泡排序：
程序运行结果：

双向冒泡排序：
程序运行结果：

快速排序：
程序运行结果：

二路归并排序：
程序运行结果：

2.各种查找算法实现
（1）顺序查找：使用数组或链表结构。用随机函数生成16个不重复的字母（’a’~’z’），键盘输入待查找的字母，返回查找成功与否，若成功则返回该字母所在的位置（序号），并计算比较次数。
源代码：
#include
#include
#define MAXSIZE 100
using namespace std;
typedef struct
{
char key;//关键字域
char *otherinfo;//其它域
}ElemType;
typedef struct
{
ElemType R[MAXSIZE+1];//存储空间基地址
int length;//当前长度
}SSTable;
void Printf(SSTable L)
{
for (int i = 1; i <= L.length; i++)
{
cout << L.R[i].key << " ";
}
}
void CreateList(SSTable &L)
{
cout << “Generate 16 random letters:” << endl;
time_t t;
srand((unsigned)time(&t));
for (int i = 1; i <= L.length; i++)
{
L.R[i].key = rand() % 26 + ‘a’;
for (int j = 1; j < i; j++)
{
if (L.R[i].key == L.R[j].key)
{
–i;
}
}
}
}
int Search_Seq(SSTable& L)
{
//在顺序表L中查找其关键字为key的数据元素
//若找到，输出位置，若找不到，返回0
int count = 0;//比较次数
char key;//查找的字母
cout << “Please Input Letters to be found , Letter:”;
cin >> key;
int i;
for (i = L.length; i >= 1; --i)
{
count++;
if (L.R[i].key == key)
{
cout << “This Letter locate in " << i << " position” << endl;
break;
}
}
if (i > 0)//若查找到该元素，即i大于0时，输出比较次数
{
cout << “Comparison times is:” << count << endl;
}
else//若查不到该元素，即i=0，无法输出查询
{
cout << “This letter don’t exist!” << endl;
}
return 0;
}

int main()
{
SSTable L;
L.length = 16;
CreateList(L);
Printf(L);
cout << endl;
Search_Seq(L);
}
程序运行结果：
若能找到字母：

若不能找到字母：

（2）折半查找：用数组实现，查找前元素先排序。计算比较次数。分别用查找成功、不成功进行测试。
源代码：
#include
#include
#define MAXSIZE 100
using namespace std;
typedef struct
{
char key;//关键字域
char *otherinfo;//其它域
}ElemType;
typedef struct
{
ElemType R[MAXSIZE+1];//存储空间基地址
int length;//当前长度
}SSTable;
void Printf(SSTable L)
{
for (int i = 0; i < L.length; i++)
{
cout << L.R[i].key << " ";
}
cout << ‘\n’;
}
void CreateList(SSTable &L)
{
cout << “Generate 16 random letters:” << endl;
time_t t;
srand((unsigned)time(&t));
for (int i = 0; i < L.length; i++)
{
L.R[i].key = rand() % 26 + ‘a’;
for (int j = 0; j < i; j++)
{
if (L.R[i].key == L.R[j].key)
{
–i;
}
}
}
}
void BubbleSort(SSTable& L)
{
int m = L.length;
for (int j = 1; j < m; j++)
{
for (int i = 0; i < m - j; i++)
{
if (L.R[i].key > L.R[i + 1].key)
{
ElemType t = L.R[i];
L.R[i] = L.R[i + 1];
L.R[i + 1] = t;
}
}
}
}
void Search_Bin(SSTable L)
{
char key;
int compare_count = 0;
int low = 0;
int high = L.length - 1;
int mid, flag = 0;
cout << “Please Input Letters to be found , Letter:”;
cin >> key;
cout << endl;
while (low <= high)
{
compare_count++;
mid = (high + low) / 2;
if (key == L.R[mid].key)
{
flag = 1;
cout << “This Letter locate in " << mid+1 << " position” << endl;
break;
}
else if(L.R[mid].key>key)//继续在签字子表进行查询
{
high = mid - 1;
}
Else //继续在后一子表进行查询
{
low = mid + 1;
}
}
if (flag == 1)
{
cout << endl;
cout << “Comparison times is:” << compare_count << endl;
}
else
{
cout << endl;
cout << “This letter don’t exist!” << endl;
}
}
int main()
{
SSTable L;
L.length = 16;
CreateList(L);
Printf(L);
cout << “After sorting:”;
BubbleSort(L);
cout << endl;
Printf(L);
cout << endl;
Search_Bin(L);
//Search_Seq(L);
}
程序运行结果：
若能找到字母：

若不能找到字母：

（3）二叉查找树：手工输入10个字母，生成一棵二叉查找树，用递归算法打印树结构或分别输出先序和中序遍历序列以确认其结构。键盘输入待查找的字母，计算比较次数。分别用查找成功、不成功进行测试。
源代码：
#include
using namespace std;
typedef struct BSTNode
{
char data;
struct BSTNode* lchild, * rchild;
}BSTNode,BSTree;
void InsertBST(BSTree& T, char e)
{
if (!T)
{
BSTree S;//生成新节点S
S = new BSTNode;
S->data = e;//新结点S的数据为e
S->lchild = S->rchild = NULL;//新结点S作为叶子结点
T = S;
}
else if (e < T->data)
{
InsertBST(T->lchild, e);//将S插入左子树
}
else if (e > T->data)
{
InsertBST(T->rchild, e);//将S插入右子树
}
}
void CreateBST(BSTree& T)
{
T = NULL;
char e;
cout << “Please Input 10 letters:” << endl;
for (int i = 0; i < 10; i++)
{
cin >> e;
InsertBST(T, e);
}
}
void PreOrder_Traversal(BSTree T)
{
if (T)
{
cout << T->data << " ";
PreOrder_Traversal(T->lchild);
PreOrder_Traversal(T->rchild);
}
}
void MiddleOrder_Traversal(BSTree T)
{
if (T)
{
MiddleOrder_Traversal(T->lchild);
cout << T->data << " ";
MiddleOrder_Traversal(T->rchild);
}
}
BSTree SearchBST(BSTree T, char key, int& count_compare)
{
count_compare++;
if (!T || key == T->data)//查找结束的标志
{
return T;
}
else if (key < T->data)//在左子树继续查找
{
return SearchBST(T->lchild, key, count_compare);
}
Else //在右子树接续查找
{
return SearchBST(T->rchild, key, count_compare);
}
}
void Search(BSTree T)
{
char key;
int count_compare = 0;
cout << “Please Input Letters to be found , Letter:”;
cin >> key;
BSTree S = SearchBST(T, key, count_compare);
if (S)
{
cout << “The letter is:” << key << endl;
cout << “Comparison times is:” << count_compare << endl;
}
else
{
cout << “This letter don’t exist!” << endl;
}
}
int main()
{
BSTree T;
CreateBST(T);
cout << “PreOrder_Traversal:” << endl;
PreOrder_Traversal(T);
cout << endl;
cout << “MiddleOrder_Traversal:” << endl;
MiddleOrder_Traversal(T);
cout << endl;
Search(T);
}
程序执行结果：
若能找到字母：

若不能找到字母：

五、实验结果及分析
<逐条列出代码编写过程中出现的错误，及改正的方案>
问题一：
用随机函数生成16个不重复的字母（’a’~’z’）时，出现了以下状况；

代码如下：
for (int i = 0; i < n; i++)
{
LinkList p = new LNode;
for (int j = 0; j < 26; j++)
{
char c = ‘a’;
c = (char)(c + j);
p->data = c;
}
p->next = L->next;
L->next = p;
}
很明显是循环的问题，当内层循环执行完毕后，p->data=’z’;所以输出的全是j，后来我想既然是生成的是0-25转为char类型后，再加上’a’,那么就用随机函数生成j(0-25)不就可以了么。
于是便改成了这样：
void CreateList(LinkList& L, int n)
{
L = new LNode;
L->next = NULL;
time_t t;
srand((unsigned)time(&t));
for (int i = 0; i < n; i++)
{
LinkList p = new LNode;
int j = rand() % 26;
char c = ‘a’;
c = (char)(c + j);
p->data = c;
p->next = L->next;
L->next = p;
}
}
后来发现有多个重复的