数据结构 折半查找

1、插入操作原理】. 10 【删除操作原理】. 10 【NO.2 代码】11 【运行截图演示】. 20 三、顺序栈的操作 25 【数值转换原理】. 25 【NO.3 代码】. 26 【运行截图演示】. 30 四、查找算法 32 【顺序查找原理】. 32 【折半查找原理】. 32 【NO.4 代码】. 33 【运行截图演示】. 38 五、排序算法 40 【直接插入排序原理】 40 【快速排序原理】. 40 【NO.5 代码】. 41 【运行截图演示】. 46 数据结构与算法分析课程设计 2 一、一、顺序表的操作顺序表的操作 （1）插入元素操作：将新元素 x 插入到顺序表 a 中第 i 个位置； （2）删除元素操作：删除顺序表 a 中第 i 个元素。
【插入操作原理】【插入操作原理】 线性表的插入操作是指在线性表的第i-1个数据元素和第i个数 据元素之间插入一个新的数据元素，就是要是长度为 n 的线性表： 11 , iin aaaa 变成长度为 n+1 的线性表： 11 , iin aab aa 数据元素 1i a 和i 。

2、顺序查找；折半查找;时间复杂度。
1 1 引引 言言 “数据结构”在计算机科学中是一门综合性的专业基础课，“数据结构”的研究不 仅涉及到计算机硬件的研究范围，而且和计算机软件的研究有着密切的关系无论是编译 程序还是操作系统，都涉及到数据元素在存储器中的分配问题。
在研究信息检索时也必 须考虑如何组织数据，一遍查找和存取数据元素更为方便。
因此，可以认为“数据结构” 是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。
课程设计是我们专业课程知识综合应用的实践训练，是实践性教学的一个重要环 节。
而数据结构的课程设计，更要求学生在数据结构的逻辑特性和物理表示、数据结构 的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。
同时，在程 序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。
在日常生活中，人们几乎每天都要进行“查找”工作。
例如，在电话号码薄中查阅 “某单位”或“某人”的电话号码；在字典中查阅“某个词”的读音和含义等等。
而同 样地，在各种系统软件和应用软件中，也存在“查找” ：如编译程序中符号表、信息处 理表中相关信息的查找。
所以， “查找。

3、个其关键字与给定值相同的数据元素，并返 回该数据元素在列表中的位置。
查找的方法分为比较式查找法和计算式查找法， 其中比较式查找法可分为基于线性表的查找法和基于树的查找法； 而计算式查找 法也称为 Hash(哈希)查找法。
基于线性表的查找法是将集合的数据对象组织成 为线性表形式进行查找，即用给定的关键字与线性表中各元素的关键字逐个比 较，直到成功或失败。
线性表的存储结构通常是顺序存储结构，也可使用链式存 储结构。
查找时可在表的一端设置一个“监视哨” ，存放要查找元素的关键字，从表 的另一端开始查找，若在“监视哨”找到要查找元素的关键字，返回失败信息， 否则返回关键字的位序。
基于线性表的查找技术有着非常广泛的应用。
2.基于线性表的排序法概述 排序是计算机程序设计中的一种重要操作，在数值计算或数据处理过程中， 都会直接或间接用到数据的排序问题。
排序的功能是将一个数据元素 （或称记录） 的无序序列，按数据元素的关键字大小排列成一个递增或递减有序的记录序列。
由于待排序的记录数量不同，使得排序过程中涉及的存储器也不同，因此可 将排序方法分为内排序和外排序。
内排序包括插入、交换、选择和归并。

4、 月 19 日至 2010 年 9 月 3 日 算法与数据结构课程设计 2 一、 实验题目：汽车牌照的快速查找 二、 实验要求： 利用链式基数排序和折半查找对一批汽车牌照进行排序和查找 三、 问题分析： 想要完成题目要求，需要选择链表对汽车信息（包括汽车牌照、汽车颜色、 汽车商标、汽车的注册时间、汽车所有者等）进行存储，并在此基础上进行多关 键字排序，因为汽车牌号是汉字、字母和数字的组合。
考虑到对汉字进行排序是 一件不可能的事，因此对各省市的简称可以放到字符串数组中，也就可以通过数 组下标进行排序， 字母可以选择同汉字一样的处理方法， 数字却很容易进行排序。
因此，排好序的汽车牌照其实就是一组长整型数组，例如根据行政规划对各省市 的简称进行存储，如汽车牌照京 C0123，转换为长整型数组后为 00020123 如何对排好序的车辆信息进行折半查找呢？因为存储好的汽车信息其实就 是一组长整型数组，而所输入的信息就是一个长整型数据，然后再那个数组中进 行折半查找既可以实现。
四、 设计思路及流程： 为了完成所需的功能，需要的函数及其功能如下： main()：主函数模块 SetLis。

5、序清单五、详细程序清单 10 六、程序运行结果六、程序运行结果 24 七、心得体会七、心得体会 26 一、问题描述一、问题描述 1、顺序表的查找问题描述 顺序查找又称线性查找，它是一种最简单、最基本的查找方法。
它从顺序表 的一端开始，依次将每一个数据元素的关键字值与给定 Key进行比较，若某个 数据元素的关键字值等于给定值 Key，则表明查找成功；若直到所有数据元素都 比较完毕，仍找不到关键字值为 Key的数据元素，则表明查找失败。
2、有序表的查找问题描述 所谓“折半”也称为“二分” ，故二分查找又称为折半查找。
作为二分查找 对象的数据必须是顺序存储的有序表， 通常假定有序表是按关键字值从小到大排 列有序，即若关键字值为数值，则按数值有序，若关键字值为字符数据，则按对 应的 Unicode 码有序。
二分查找的基本思想是：首先取整个有序表的中间记录的 关键字值与给定值相比较，若相等，则查找成功；否则以位于中间位置的数据元 素为分界点，将查找表分成左、右两个子表，并判断待查找的关键字值 key是在 左子表还是在右子表，再在左或右子表中重复上述步骤，直到找待查找的关键字 值为 key的记录。

6、 章 概要设计 4 2.1 数据结构描述. 4 2.11 数据类型定义 4 2.2 模块设计 4 2.21 模块之间的关系 . 4 2.22 主程序流程图设计 . 5 第 3 章 程序设计 . 6 3.1 程序演示 6 二、拓扑排序. 10 2.1 问题描述 10 2.2 要求 . 10 2.3 问题分析 10 2.4 主要流程图 .11 2.5 代码设计 12 2.6 要实现的图 . 12 2.7 程序演示 13 三、排序查找数据 14 3.1 问题描述 14 3.2 要求 . 14 3.3 主要思路及代码 14 3.4 主要流程图设计 . 16 3.5 程序演示 17 总结. 18 数据结构课程设计 3 一、通讯录管理一、通讯录管理 第第 1 章章 需求分析需求分析 1.11.1 问题定义问题定义 随着信息社会的高速发展与进步，人们之间的交往越来越丰富多彩，人与人 之间的交往联系越来越频繁，通讯方式越来越多样化，如何保证与朋友、同学、 同事、领导、亲戚等之间的联系，并能方便快捷的查找、记录、修改其相关通讯 信息，越来越受到关注。
对通讯录进行必要的管理与更人性化的设计，对人们实 。

7、 设计要求： (1) 符合课题要求，实现相应功能； (2) 操作方便易行； (3) 注意程序的实用性、安全性； 二、需求分析：二、需求分析： 串的查找与替换要实现的功能是：打开一篇英文文章，在该文章中找出所有给定的 单词，然后对所有给定的单词替换为另外一个单词，再存盘。
首先实现程序比较简单的功能， 即： 输入要替换的单词和给定单词 gets(keyWords); gets(copyWords)。
然后实现程序打开文件的功能。
最后编写最核心的替换功能，首先用关键字来匹配要查找的单词，第一个单词匹配 上的话再判断这个关键字在不在单词的首字母上，否则不匹配，主要是要实现替换单词 的功能不替换其他单词中的字符串。
然后匹配第二个字母，这样一次类推的判断。
不匹 1 配的单词直接放入 strTwo 数组中，匹配的单词先替换然后再放入 strTwo 数组中。
三、概要设计三、概要设计和详细设计：和详细设计： 程序头设计 对程序作简单介绍以及输出程序制作人的基本信息。
main（） printf(“nnnttt 数据结构课程设计n“); printf(“nttt 。