排序实验报告.doc

《数据结构》课程实验报告
题目:
专业:
班级:
学号:
姓名:
实验目的与要求
理解二叉树排序树、AVL树的查找、插入、删除、建立算法的思想及程序的实现
掌握散列存储结构的思想,能选择合适散列函数,实现不同冲突处理方法的散列表的查找,建立。
运用折半查找、分块查找、二叉排序树、散列表等查找算法解决实际的问题。
理解各种排序方法的特点。
应用各种排序的算法解决实际的问题。
实验内容(问题描述)
设计一个算法、利用折半查找算法在一个有序表中插入一个元素x,并保持表的有序性。
编写一个算法,实现快速排序。
存储结构及其C/C++语言描述
typedef struct{
RedType r[MAXSIZE+1];
int length;
}SqList;
利用折半查找算法在一个有序表中插入一个元素x,并保持表的有序性。
typedef struct {
KeyType key;
}ElemType,TElemType;
快速排序
typedef struct{
KeyType key;
InfoType otherinfo;
}RedType;
typedef struct{
ElemType *elem;
int length;
}SSTable;
算法的基本思想

,并保持表的有序性。

首先,运用折半查找法将表中间位置记录的关键字与查找关键字比较,如果中间位置记录的关键字大于查找的关键字,则进一步查找前一个子表,否则进一步查找后一个子表;直到关键字小于查找的关键字x,然后把x插入表中关键字的后面。

通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一不部分的所有数据都要小,然后再按次方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
算法描述
利用折半查找算法在一个有序表中插入一个元素x,并保持表的有序性。
++high;
for(int i= ;i>=high;i--)
{
[i+1].key= [i].key;
}
[high].key=key;
++ ;
return OK;
}
Status Insert(SSTable &ST,KeyType key)
{
int low,high,mid;
low=1;
high= ;
while(low<=high)
{
mid=(low+high)/2;
if(key== [mid].key)
{
cout<<"数据已存在,插入失
败"<<endl;
exit(OVERFLOW);
}
else if(key< [mid].key)
high=mid-1;
else
low=mid+1;
}

{
[i+1].key= [i].key;
}
[high].key=key;