求助!数据结构问题!
时间:2011-12-10
来源:互联网
麻烦高手补充下面有注释没有代码的部分!感谢!
#include <iostream.h>
#include <conio.h>
typedef
struct node
{ int data; // 表示一个整数
int next; // 指示下一个结点的指针(下标)
}sqlist_node; // 用于链式基数排序的静态链表的结点类型
void output(int L[]) // 输出数组中100个整数的函数
{ for(int i=0; i<100; i++)
{ if(L[i]<10) cout<<" ";
else if(L[i]<100) cout<<" ";
cout<<L[i];
if((i+1) % 10==0) cout<<endl; // 按每行10个输出
else cout<<", "; // 否则以逗号间隔
}
}
int partition(int L[],int j,int k) // 快速排序一趟分割函数,返回分割点位置(独立完成)
{ 选定L[]中一个整数作为分割点的元素,并暂存;
当前端位置指针j小于后端位置指针k
{ 自后端起向前顺序查找,找出第一个小于作为分割点的整数的位置k;
将L[k]移动到j;
自前端起向后顺序查找,找出第一个大于作为分割点的整数的位置j;
将L[j]移动到k;
}
将暂存的作为分割点的整数移动到k或j; // 此时j与k位置重叠
返回k或j;
}
void sort_quick(int L[],int s,int t) // 快速排序的递归算法
{ int m;
if(s<t)
{ m=partition(L,s,t);
sort_quick(L,s,m-1);
sort_quick(L,m+1,t);
}
}
void heap_sift(int L[],int s,int t) // 堆排序中,L[s]..L[t]范围内的堆的筛选(独立完成)
{
暂存根结点L[s];
令i为根结点的下标s;
令j为堆顶L[s]的左孩子的下标
当j小于或等于最后一个结点的位置t
{ 如果L[i]的右孩子存在且大于左孩子L[j], 则令j为右孩子的下标;
若已经是堆,则break;
键值较L[s]大的L[j]上升至i;
令i为j;
令j为L[i]的左孩子的下标;
}
将暂存的L[s]下降到i;
}
void sort_heap(int L[],int n) // 堆排序
{ int i;
for (i=n/2-1;i>=0;i--) heap_sift(L,i,n-1); // 反复筛选,建初始堆
for (i=n-1;i>0;i--)
{ swap(L[0],L[i]); // 将最大元素(堆顶)L[0]与最后一个元素L[i]交换
heap_sift(L,0,i-1); // 重新调整和筛选0..i-1范围内的堆
}
}
void distribute(sqlist_node R[],int p,int i,int f[],int e[]) // 按第i位关键字的分配算法(独立完成)
{ // 参数p已指向静态链表的第1个记录
令所有队头指针f[j]为-1(空);
while(p非空) // 遍历静态链表
{ 取记录R[p]的第i位关键字; 令j为其键值(0..9之间的一位数)
若f[j]为空 令f[j]指向p;
否则,另队尾记录的next指向p;
队尾指针指向当前记录;
P指向下一个记录;
}
}
void collect(sqlist_node R[],int &p,int i,int f[],int e[]) // 完成一趟收集过程的算法
{ int j=0, t;
while(f[j]==-1) j++; // 找第1个非空队列
p=f[j]; // 表头指针指向第1个非空队列的第1个结点
t=e[j]; // t初始化为指向第1个非空队列的队尾
while(j<9)
{ j++;
while((j<9)&&(f[j]==-1)) j++; // 找下一个非空队列(子表)
if(f[j]!=-1)
{ R[t].next=f[j]; // 指向下一个非空队列的队头记录
t=e[j]; // 取下一个队尾
}
}
R[t].next=-1; // 修正最后一个记录的后继指针
}
void radixsort(sqlist_node R[],int &p) // 链式基数排序
{ int j;
int f[10],e[10]; // 队头、队尾指针向量
for(j=0; j<100; j++) R[j].next=j+1; // 初始化静态链表
R[99].next=-1; // 最后一个元素没有后继
p=0; // 初始化首元素指针
for(j=3; j>0; j--) // 从第3位关键字开始
{ distribute(R,p,j,f,e); // 分配操作
collect(R,p,j,f,e); // 收集操作
}
}
void output_sqlist(sqlist_node *R,int p) // 遍历静态链表,输出100个整数的函数
{ int m=0;
while(p!=-1)
{ if(R[p].data<10) cout<<" ";
else if(R[p].data<100) cout<<" ";
cout<<R[p].data;
if((m+1)%10==0) cout<<endl;
else cout<<", ";
m++;
p=R[p].next;
}
}
void main() // 主函数
{ int a[100],ks[100],dui[100];
sqlist_node sqlist[100];
int head;
randomize();
for(int i=0; i<100; i++)
{ a[i]=random(1000); // 产生0到999之间的随机数
ks[i]=a[i];
dui[i]=a[i];
sqlist[i].data=a[i];
};
cout<<"100个0到999之间的随机整数:\n";
output(a);
cout<<"快速排序后的100个整数序列:\n";
sort_quick(ks,0,99);
output(ks);
cout<<"堆排序后的100个整数序列:\n";
sort_heap(dui,100);
output(dui);
cout<<"链式基数排序后的100个整数序列:\n";
radixsort(sqlist,head);
output_sqlist(sqlist,head);
return;
}
#include <iostream.h>
#include <conio.h>
typedef
struct node
{ int data; // 表示一个整数
int next; // 指示下一个结点的指针(下标)
}sqlist_node; // 用于链式基数排序的静态链表的结点类型
void output(int L[]) // 输出数组中100个整数的函数
{ for(int i=0; i<100; i++)
{ if(L[i]<10) cout<<" ";
else if(L[i]<100) cout<<" ";
cout<<L[i];
if((i+1) % 10==0) cout<<endl; // 按每行10个输出
else cout<<", "; // 否则以逗号间隔
}
}
int partition(int L[],int j,int k) // 快速排序一趟分割函数,返回分割点位置(独立完成)
{ 选定L[]中一个整数作为分割点的元素,并暂存;
当前端位置指针j小于后端位置指针k
{ 自后端起向前顺序查找,找出第一个小于作为分割点的整数的位置k;
将L[k]移动到j;
自前端起向后顺序查找,找出第一个大于作为分割点的整数的位置j;
将L[j]移动到k;
}
将暂存的作为分割点的整数移动到k或j; // 此时j与k位置重叠
返回k或j;
}
void sort_quick(int L[],int s,int t) // 快速排序的递归算法
{ int m;
if(s<t)
{ m=partition(L,s,t);
sort_quick(L,s,m-1);
sort_quick(L,m+1,t);
}
}
void heap_sift(int L[],int s,int t) // 堆排序中,L[s]..L[t]范围内的堆的筛选(独立完成)
{
暂存根结点L[s];
令i为根结点的下标s;
令j为堆顶L[s]的左孩子的下标
当j小于或等于最后一个结点的位置t
{ 如果L[i]的右孩子存在且大于左孩子L[j], 则令j为右孩子的下标;
若已经是堆,则break;
键值较L[s]大的L[j]上升至i;
令i为j;
令j为L[i]的左孩子的下标;
}
将暂存的L[s]下降到i;
}
void sort_heap(int L[],int n) // 堆排序
{ int i;
for (i=n/2-1;i>=0;i--) heap_sift(L,i,n-1); // 反复筛选,建初始堆
for (i=n-1;i>0;i--)
{ swap(L[0],L[i]); // 将最大元素(堆顶)L[0]与最后一个元素L[i]交换
heap_sift(L,0,i-1); // 重新调整和筛选0..i-1范围内的堆
}
}
void distribute(sqlist_node R[],int p,int i,int f[],int e[]) // 按第i位关键字的分配算法(独立完成)
{ // 参数p已指向静态链表的第1个记录
令所有队头指针f[j]为-1(空);
while(p非空) // 遍历静态链表
{ 取记录R[p]的第i位关键字; 令j为其键值(0..9之间的一位数)
若f[j]为空 令f[j]指向p;
否则,另队尾记录的next指向p;
队尾指针指向当前记录;
P指向下一个记录;
}
}
void collect(sqlist_node R[],int &p,int i,int f[],int e[]) // 完成一趟收集过程的算法
{ int j=0, t;
while(f[j]==-1) j++; // 找第1个非空队列
p=f[j]; // 表头指针指向第1个非空队列的第1个结点
t=e[j]; // t初始化为指向第1个非空队列的队尾
while(j<9)
{ j++;
while((j<9)&&(f[j]==-1)) j++; // 找下一个非空队列(子表)
if(f[j]!=-1)
{ R[t].next=f[j]; // 指向下一个非空队列的队头记录
t=e[j]; // 取下一个队尾
}
}
R[t].next=-1; // 修正最后一个记录的后继指针
}
void radixsort(sqlist_node R[],int &p) // 链式基数排序
{ int j;
int f[10],e[10]; // 队头、队尾指针向量
for(j=0; j<100; j++) R[j].next=j+1; // 初始化静态链表
R[99].next=-1; // 最后一个元素没有后继
p=0; // 初始化首元素指针
for(j=3; j>0; j--) // 从第3位关键字开始
{ distribute(R,p,j,f,e); // 分配操作
collect(R,p,j,f,e); // 收集操作
}
}
void output_sqlist(sqlist_node *R,int p) // 遍历静态链表,输出100个整数的函数
{ int m=0;
while(p!=-1)
{ if(R[p].data<10) cout<<" ";
else if(R[p].data<100) cout<<" ";
cout<<R[p].data;
if((m+1)%10==0) cout<<endl;
else cout<<", ";
m++;
p=R[p].next;
}
}
void main() // 主函数
{ int a[100],ks[100],dui[100];
sqlist_node sqlist[100];
int head;
randomize();
for(int i=0; i<100; i++)
{ a[i]=random(1000); // 产生0到999之间的随机数
ks[i]=a[i];
dui[i]=a[i];
sqlist[i].data=a[i];
};
cout<<"100个0到999之间的随机整数:\n";
output(a);
cout<<"快速排序后的100个整数序列:\n";
sort_quick(ks,0,99);
output(ks);
cout<<"堆排序后的100个整数序列:\n";
sort_heap(dui,100);
output(dui);
cout<<"链式基数排序后的100个整数序列:\n";
radixsort(sqlist,head);
output_sqlist(sqlist,head);
return;
}
作者: livedk 发布时间: 2011-12-10
这些最好能自己独立完成吧,你可以参考下我博客里关于排序的总结。
作者: a81895898 发布时间: 2011-12-12
相关阅读 更多
热门阅读
-
office 2019专业增强版最新2021版激活秘钥/序列号/激活码推荐 附激活工具
阅读:74
-
如何安装mysql8.0
阅读:31
-
Word快速设置标题样式步骤详解
阅读:28
-
20+道必知必会的Vue面试题(附答案解析)
阅读:37
-
HTML如何制作表单
阅读:22
-
百词斩可以改天数吗?当然可以,4个步骤轻松修改天数!
阅读:31
-
ET文件格式和XLS格式文件之间如何转化?
阅读:24
-
react和vue的区别及优缺点是什么
阅读:121
-
支付宝人脸识别如何关闭?
阅读:21
-
腾讯微云怎么修改照片或视频备份路径?
阅读:28