没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构作业:查找与排序算法分析
数据结构作业:查找与排序算法分析
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
![](https://csdnimg.cn/release/wenkucmsfe/public/img/star.98a08eaa.png)
"这是西南交通大学数据结构课程的一份第5次作业,涵盖了查找和排序两个主题。作业包括理论问题、算法设计以及编程实践。学生需要完成对分查找算法的编写,构建并判断平衡二叉排序树,以及实现链式基数排序。" 在查找部分,作业涉及了对分查找算法。对分查找是一种在有序数组中查找特定元素的有效方法。它通过不断将查找区间减半来快速定位目标值。给定一个n元顺序表,已按照关键字递增有序存储,学生需要编写算法找到满足ai-1<key且ai≥key的下标i。对分查找的效率很高,其时间复杂度为O(log n)。 排序部分则包含内部排序的习题和编程题目。习题集中的问题可能涉及各种排序算法的分析,如计算平均查找长度(ASL)。而编程题目要求学生实现链式基数排序,这是一种非比较型整数排序算法,特别适用于处理大量无符号整数。对于C语言的32位无符号整数,可以按16进制位进行8次分配和收集,从而实现排序。链式基数排序的时间复杂度为O(kn),其中k是数字的最大位数,n是数字的数量。 此外,作业还涉及到平衡二叉排序树的构建和分析。平衡二叉排序树,如AVL树或红黑树,确保了树的高度保持平衡,从而保证了查找、插入和删除操作的平均时间复杂度为O(log n)。学生需要输入n个两两互不相等的整数,建立这样的树,并判断其是否平衡,同时输出中序遍历的结果,中序遍历可以得到排序后的序列。 这份作业考察了学生对数据结构基础概念的理解,包括查找算法、排序算法以及平衡二叉树的实现和分析。完成这些任务需要扎实的算法基础和编程能力。
资源详情
资源推荐
![](https://csdnimg.cn/release/download_crawler_static/75287139/bg4.jpg)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
3. (1)
#include <stdio.h>
#include <stdlib.h>
typedef struct AVLTNode
{
int key; //
数据
int bf; //
平衡因子,正为
L,
负为
R
int num; //
输入序号
struct AVLTNode *lchild;
struct AVLTNode *rchild;
} AVLTNode, *AVLTree;
/*
根据输入的
arr
数组,按数组中元素的顺序构建一棵平衡二叉排序树
*/
void InsertAVLTree(AVLTree &bt, int k, int i) //
树,结点数据,第几个结点(
arr
数组)
{
AVLTree S; //
新结点
AVLTree a, fa, p, fp, b, c;
//
将
k
(结点数据)先插入到新节点
S,
同时使
s
的左右子树为
NULL
S = new AVLTNode();
S->key = k;
S->num = i + 1;
S->lchild = NULL;
S->rchild = NULL;
S->bf = 0; //
平衡因子
if (bt == NULL) //
如果平衡树为空,那么
s
直接插入
bt = S;
else
{
/*
首先查找
S
的插入位置
fp
,同时记录距
S
的插入位置最近且
平衡因子不等于
0
(等于
-1
或
1
)的结点
a
,
a
为可能的失衡结点
*/
a = bt;
fa = NULL;
p = bt;
fp = NULL;
while (p)
{
if (p->bf != 0)
{
4 / 16
剩余15页未读,继续阅读
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![whl](https://img-home.csdnimg.cn/images/20210720083646.png)
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://profile-avatar.csdnimg.cn/baed4cf2581e450691f7ed18175631f4_qq_52046937.jpg!1)
码龄零年_921
- 粉丝: 303
- 资源: 49
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-2.8b825a4e.png)
电子书特权
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![](https://csdnimg.cn/release/wenkucmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![](https://csdnimg.cn/release/wenkucmsfe/public/img/voice.245cc511.png)
最新资源
- Vue实现iOS原生Picker组件:详细解析与实现思路
- Arduino蓝牙小车:参数调试与功能控制
- 百度Java面试精华:200页精选资源涵盖核心知识点
- Swift使用CoreData填坑指南:CoreData在Swift 3.0的变化
- 微距离无线充电器创新设计及其实验探索
- MTK Android平台开发全攻略:44步详解流程
- RecyclerView全面解析:替代ListView的新选择
- Android开发:自动适配中英文键盘解决方案
- Android调用WebService接口教程
- Android开发:BitmapUtil图片处理全解析与实例
- Android多线程断点续传实现详解
- PCA算法在人脸识别会议签到系统中的应用
- EventBus 3.0:Android事件总线详解与实战应用
- Android FileUtil:全面解析文件操作实用技巧与实例
- RecyclerView添加头部和尾部实战教程
- Android实现微博滑动固定顶部栏实战与优化
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035711.png)
![](https://img-home.csdnimg.cn/images/20220527035111.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![](https://csdnimg.cn/release/wenkucmsfe/public/img/green-success.6a4acb44.png)