下载文档原格式
二分法查找1、二分查找(Binary Search)二分查找又称折半查找，它是一种效率较高的查找方法。
二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。
不妨设有序表是递增有序的。
2、二分查找的基本思想二分查找的基本思想是：（设R[low..high]是当前的查找区间）（1）首先确定该区间的中点位置：（2）然后将待查的K值与R[mid].key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下：①若R[mid].key>K，则由表的有序性可知R[mid..n].keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R[1..mid-1]中，故新的查找区间是左子表R[1..mid-1]。
②类似地，若R[mid].key<K，则要查找的K必在mid的右子表R[mid+1..n]中，即新的查找区间是右子表R[mid+1..n]。
下一次查找是针对新的查找区间进行的。
因此，从初始的查找区间R[1..n]开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。
这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。
3、二分查找算法int BinSearch(SeqList R，KeyType K){ //在有序表R[1..n]中进行二分查找，成功时返回结点的位置，失败时返回零int low=1，high=n，mid；//置当前查找区间上、下界的初值while(low<=high){ //当前查找区间R[low..high]非空mid=(low+high)/2；if(R[mid].key==K) return mid；//查找成功返回if(R[mid].kdy>K)high=mid-1; //继续在R[low..mid-1]中查找elselow=mid+1；//继续在R[mid+1..high]中查找}return 0；//当low>high时表示查找区间为空，查找失败} //BinSeareh二分查找算法亦很容易给出其递归程序【参见练习】4、二分查找算法的执行过程设算法的输入实例中有序的关键字序列为(05，13，19，21，37，56，64，75，80，88，92)要查找的关键字K分别是21和85。
![全国计算机等级考试二级公共基础知识要点汇总[规整]](https://img.taocdn.com/s1/m/5a409e56842458fb770bf78a6529647d272834fd.png)
全国计算机等级考试二级公共基础知识要点汇总第一章数据结构与算法1.1 算法算法：是指解题方案的准确而完整的描述。
算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。
算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。
特征包括：（1）可行性；（2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性；（3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义；（4）拥有足够的情报。
算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。
指令系统：一个计算机系统能执行的所有指令的集合。
基本运算包括：算术运算、逻辑运算、关系运算、数据传输。
算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。
算法复杂度：算法时间复杂度和算法空间复杂度。
算法时间复杂度是指执行算法所需要的计算工作量。
算法空间复杂度是指执行这个算法所需要的内存空间。
1.2 数据结构的基本概念数据结构研究的三个方面：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。
数据结构是指相互有关联的数据元素的集合。
数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。
数据的存储结构有顺序、链接、索引等。
线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。
非线性结构：不满足线性结构条件的数据结构。
1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。
大纲一、考试性质本考试是为在计算机专科生中招收本科生而实施的具有选拔功能的水平考试，其指导思想是既要有利于国家对高层次人材的选拔，又要有利于促进高等学校各类课程教学质量的提高，考试对象为2003年参加专升本考试的考生。
二、考试的基本要求要求学生比较系统地理解数据结构的基本概念和基本知识，掌握表、栈、队列、树和图等数据结构的基本特征和在计算机上实现的方法，要求考生具有抽象思维能力、逻辑推理能力、综合运用所学的知识分析问题和解决问题的能力，以及软件设计和编程能力。
三、考试方法和考试时间考试方法为闭卷笔试，考试时间为120分钟。
四、考试内容和要求1、绪论考试内容:数据结构基本概念和术语，算法、算法的描述和算法分析。
考试要求（1）了解非数值问题的数学模型不是数学方程，而是表、树和图之类的数据结构。
（2）理解数据、数据元素、数据对象、数据结构和数据类型等的定义。
（3）掌握数据的逻辑结构和存储结构及其种类；算法的重要特征等。
（4）会根据语句的最大频度计算算法的时间复杂度的方法。
2、线性表考试内容:线性表的定义、线性表的逻辑结构、线性表的顺序存储结构和链式存储结构，单向链表、循环链表和双向链表，一元多项式的表示及相加。
考试要求（1）了解线性表的定义和线性结构的特点。
（2）理解线性表的顺序存储和链式存储，理解数组与单链表表示表的优缺点。
（3）掌握线性顺序表中数据元素的存储位置的计算，顺序表、单向链表、循环链表和双向链表的插入、删除等有关操作。
（4）会用单链表编写插入、删除等有关算法。
（5）能够从时间和空间复杂度的角度综合比较两存储结构的特点及适用场合。
3、栈和队列考试内容:栈的定义、栈的表示和实现；队列的定义、队列的表示和实现，链队列、循环队列。
考试要求（1）了解栈和队列的定义。
（2）理解线性表、栈和队列特点及区别，栈对实现递归过程的作用。
（3）掌握顺序栈、链栈的入栈和出栈操作，顺序队列、链队列的入队和出队操作，循环队列的队空和队满的判断。
数据结构课程设计–宾馆客房管理系统概述本次课程设计旨在设计一个宾馆客房管理系统，该系统可以对宾馆的客房进行管理，统计客房的使用情况，方便客房的预定和安排，为客户提供更好的服务。
功能描述该系统主要包括以下功能： 1. 客房信息管理：包括客房的编号、类型、价格、状态等信息的录入和修改； 2. 顾客信息管理：包括顾客的基本信息、预订信息等的管理； 3. 客房预订：客户可以根据需要进行客房的预订，系统会自动判断客房的可用情况； 4. 入住管理：客户入住时需要进行登记，同时系统会自动更改客房的状态信息； 5. 结账管理：客户结账需要进行登记，同时系统会自动更改客房的状态信息； 6. 统计报表：包括客房的使用情况、收入情况等的统计报表。
数据结构为了在实现上述功能的同时保证系统的高效性和正确性，应当使用合适的数据结构来存储和管理数据。
在本系统中，可以采用以下数据结构： - 顺序表：可用于存储客房信息、顾客信息等数据，方便进行查询和修改操作。
- 栈：可用于实现入住管理和结账管理功能。
- 队列：可用于客房预订时的管理，按照先来先服务的原则对客户进行排队。
- 二叉树：可用于客房使用情况的统计和查询，以方便管理员对客房的管理。
算法设计为了实现上述功能并保证高效性和正确性，需要采用合适的算法进行设计。
在本系统中，可以使用以下算法： - 顺序查找：用于在顺序表中查询指定的客房信息或顾客信息； - 插入排序：用于对顺序表中的客房信息或顾客信息按照指定的属性进行排序； - 二分法查找：用于在二叉树中进行快速查询客房信息； - 栈和队列的基本操作：用于管理客户的入住和结账。
程序流程1.初始化程序，加载客房信息和顾客信息，初始化相关变量和数据结构；2.进入系统主菜单，提供相应的功能选项，并根据用户的选择执行相应的操作；3.可根据指定条件查询客房和顾客信息，并进行修改、删除等操作；4.客户进行预订时，将其信息添加到队列中等待处理；5.管理员根据客房的可用情况，接受或拒绝客房预订；6.客户到达宾馆入住时进行登记，系统将其信息添加到栈中存储；7.客户结账时进行结账登记，系统将其信息从栈中移除，并修改客房的状态信息；8.根据需要生成统计报表，方便管理员进行相关的管理操作；9.系统退出时，将数据保存到文件中以便下次使用。
必考点（其它的知识点也需要记忆，这只是必考点和经常考）数据源：只要提到数据源，不管是建立什么的数据源都是：数据库表、自由表、视图（查询不能作为查询的数据来源，但是可以作为报表的数据来源）扩展名：第一章：表文件（自由表、数据库表）：.DBF备注文件：.FPT一个表文件不管有多少个备注型和通用型字段，均只有一个备注型文件，该备注型文件的主文件名与表文件的主文件名同名。
第四章：数据排序独立索引文件：.IDX复合索引结构复合索引文件：.CDX非结构复合索引文件：.CDX第七章程序设计程序文件（命令文件）：.PRG第九章项目管理器项目文件：.PJX项目备注文件的扩展名是：.PJT。
第十章数据库数据库文件：.DBC数据库备注文件：.DCT 数据库索引文件：.DCX 第十一章查询和视图查询文件：.QPR第十二章表单表单文件：.SCX表单备注文件：.SCT第十三章菜单菜单格式文件：.MNX 菜单备注文件：.MNT 菜单程序文件：.MPR 第十四章报表报表文件：.FRX报表备注文件：.FRT第十五章项目连编应用程序: .app可执行文件： .exe动态链接文件：.dll 其他文本文件：.TXT标签文件：.LBX第七章程序设计Do while循环带参模块的调用（参数的传递：按值传递和按引用传递）变量的作用范围(域)1、公共(全局)变量建立命令：public 变量名或者在命令窗口中直接赋值的变量也称为公共(全局)变量作用域：在所有模块中均有效2、局部变量建立命令：local 变量名作用域：只能在建立它的模块中使用，不能在上层或下层模块中使用。
3、私有变量：不用命令建立，直接使用的变量，即在程序中直接赋值的变量（在程序中不需要用public等命令明确声明和建立，可直接使用的内存变量是私有变量）作用域：建立它的模块及其下属的各层模块。
4、隐藏变量命令：private 变量名功能：该命令不是建立变量命令，它的作用是隐藏指定的在上层模块中可能已经存在的内存变量，使得这些变量在当前模块程序中暂时无效。
一、举例说明二分查找的基本思想，并用类C语言设计算法实现二分查找(折半查找)。
解：二分法查找的过程是：首先确定待查记录的范围，然后逐步缩小范围到直到找到或找不到该记录为止。
例如：已知11个数据元素的有序表，（关键字为数据元素的值）：（05，13，19，21，37，56，64，75，80，88，92），现在查找关键字为21的数据元素。
设指针low指向下界，high指向上界，mid=（low+high）」/2指向中间区域。
所以此例种设low=1，则high=11，mid=6。
首先取mid所指元素ST.elem[mid].key与给定值k ey=21比较，因为56>21，说明所查key=21一定在56的左侧，则令high=mid-1，所以所查元素在[low，mid-1]之间即[1，5]范围，求出mid=（low+high）」/2=3，取mid所指元素19再与k e y的值21比较，因为19<21，所以所查元素必在21的右侧，则令low=mid+1，所以所查元素在[mid+1，high]之间即[4，5]范围，求mid=（low+high）」/2=4，取mid所指元素21再与k ey 的值21比较，相等，查找成功，所查元素在表中序号为mid的值是4。
按照以上方法若所查元素在表中不存在，则会出现low>high的情况，因此当low>high说明查找不成功。
算法如下：Int Search_Bin(SSTable ST, KeyType key){//在有序表ST中查找值为ke y的元素，若找到，则函数值为该元素在表中的位置，否则为0 low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2; //找中间位置if(EQ(key,ST.elem[mid].key) returnmid; //找到返回元素在表中的位置else if (LT(key, ST.elem[mid].key)) high=mid-1; //继续在前半区间找else low=mid+1; //继续在后半区间找}Return0; //顺序表中不存在待查元素} //二分法查找算法二、将两个有序单链表合并为一个有序单链表通过比较不断后移指针合并链表。
数据结构与算法基础作为计算机科学中最基础的核心理论学科之一，数据结构与算法几乎涵盖了所有计算机科学的领域。
随着科技的不断发展和计算机的越来越普及，数据结构与算法的重要性也越来越被人们所认识并广泛应用于各个领域。
因此，作为一名计算机专业学生，在数据结构与算法这门学科的学习中必须掌握其基本概念和算法实现，并且应该在学习过程中注重理解算法的精髓和内涵。
一、数据结构数据结构，指数据之间的关系，包括数据的存储和组织方式。
对于计算机程序员来说数据结构是非常重要的，因为理解数据结构的本质意义，创造出合适的数据结构来满足实际应用需求并可以提高程序执行效率，而这点又可以极大地影响整个计算机的工作效率。
常见的数据结构有线性结构、树形结构、图形结构等。
这里主要介绍一些常见的数据结构：1. 线性结构：常见的有数组、链表、队列、栈等。
- 数组：数组是由相同类型的元素所组成的一组连续内存储单元，并按序号索引组成的，称为线性结构。
在数组中，查找元素的效率较高，但其插入和删除的效率非常低。
- 链表：由若干个结点组成，每个结点包含具有相同数据类型的数据元素和指向下一结点的指针（或称链），最后一个节点不指向任何结构称为空结点。
单向链表仅有一个指向下一结点的指针。
双向链表每个结点都有两个指针，均指向前后两个结点。
链表的时间效率优于数组，在插入和删除操作中，链表可以很快的完成。
- 队列：队列是一种操作受限的线性结构，它具有先进先出（FIFO）的特点。
队列有两个指针，即队首指针和队尾指针。
从队首插入和删除一个元素，从队尾删除一个元素。
插入恒等于入队操作，删除等于出队操作。
- 栈：栈是一种操作受限的线性结构，它具有先进后出（LIFO）的特点。
栈有两个主要操作：压入和弹出。
压入元素即入栈操作，弹出元素即出栈操作。
栈的应用非常广泛，比如从栈中打印寻址路径和存储路径，栈在很多算法的实现中被广泛地应用。
2. 树形结构：由结点和连接结点的边组成。
- 二叉树：二叉树是一个树形结构，它满足每个节点最多有两个子节点。
计算机专业基础综合（查找）-试卷1(总分：94.00，做题时间：90分钟)一、单项选择题(总题数：25，分数：50.00)1.单项选择题1-40小题。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
__________________________________________________________________________________________ 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。
A.(n—1)／2B.n／2C.(n+1)／2 √D.n此题考查的知识点是顺序查找长度ASL的计算。
假设表长度为n，那么查找第i个数据元素需进行n一i+1次比较，即C i =n一i+l。
又假设查找每个数据元素的概率相等，即P i =1／n，则顺序查找算法的平均查找长度为：所以应选C。
3.顺序查找法适用于查找顺序存储或链式存储的线性表二分法查找只适用于查找顺序存储的有序表，平均比较次数为( )。
在此假定N为线性表中结点数，且每次查拔都是成功的。
A.N+1B.2log 2 NC.log 2 N √D.N／2此题考查的知识点是各类查找算法的比较次数计算。
顺序查找法用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败，其ASL=(n+1)／2，即查找成功时的平均比较次数约为表长的一半。
应选C。
4.顺序查找法适用于查找顺序存储或链式存储的线性表，平均比较次数为( )在此假定N为线性表中结点数，且每次查拔都是成功的。
A.N+1B.2log 2 NC.log 2 ND.N／2 √二分法查找过程可用一个称为判定树的二叉树描述，由于判定树的叶子结点所在层次之差最多为1，故n个结点的判定树的深度与n个结点的完全二叉树的深度相等，均为[log 2 n]+1。
这样，折半查找成功时，关键字比较次数最多不超过[log 2 n]+1。
2022年江苏理工学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A.60B.66C.18000D.332、若需在O（nlog2n）的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。
A.快速排序B.堆排序C.归并排序D.直接插入排序3、链表不具有的特点是（）。
A.插入、删除不需要移动元素B.可随机访问任一元素C.不必事先估计存储空间D.所需空间与线性长度成正比4、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。
A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)5、动态存储管理系统中，通常可有（）种不同的分配策略。
A.1B.2C.3D.46、下列选项中，不能构成折半查找中关键字比较序列的是（）。
A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。
A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。
A.107B.108C.214D.2159、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（）。
A.其中任意一个结点均无左孩子B.其中任意一个结点均无右孩子C.其中只有一个叶结点D.其中度为2的结点最多为一个10、分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（）。
A.（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，20，110，130）D.（100，80，60，90，120，130，110）二、填空题11、在有n个顶点的有向图中，每个顶点的度最大可达______。
二叉树查找-二分法查找二叉树二分法查找二叉树方法：左大右小，找不到的时候就分支限定的查找#include <cstdlib>#include <iostream>using namespace std;struct tree{ // 声明树的结构struct tree *left;int data;struct tree *right;};typedef struct tree treenode;//声明新类型的树的结构typedef treenode *b_tree;//声明二叉树的链表/*递归建立二叉树*/b_tree creat_btree(int *nodelist,int position)//看好了某些定义b_tree {b_tree newnode;//声明树根指针if(nodelist[position]==0||position>15){//cout <<"d";return NULL;}else{newnode = (b_tree) malloc(sizeof(treenode));//申请空间newnode->data=nodelist[position];//建立节点内容//cout << " newnode=" << newnode->data;newnode->left=creat_btree(nodelist,2*position); //递归建立左子树newnode->right=creat_btree(nodelist,2*position+1);//递归建立右子树return newnode;}}//建立二叉树//二叉树遍历方式查找b_tree btree_travesal_search(b_tree point,int findnode){b_tree point1,point2;//声名往左和往右查询的指针if(point!=NULL){if(point->data==findnode)return point;else//找左子树point1=btree_travesal_search(point->left,findnode);//找右子树point2=btree_travesal_search(point->right,findnode);if(point1 != NULL)return point1;else if(point2!=NULL)return point2;else return NULL;}elsereturn NULL;}//二叉树二分查找法b_tree btree_travesal_search1(b_tree point, int findnode){while(point!=NULL){if(point->data==findnode)//找到了数据return point;//返回找到节点的指针elseif(point->data>findnode){point=point->left;}//向左子树找else {point=point->right;}//向右子树找}return NULL;}void inoder(b_tree point){if(point!=NULL){inoder(point->left);cout << point->data<<" ";inoder(point->right);}};int main(int argc, char *argv[]){b_tree root = NULL;//树根指针b_tree point = NULL;int findnode;int i;int nodelist[16]={0,5,2,9,0,4,7,0,0,0,3,0,6,8,0,0};//---------------建立树状结构-----------//root = creat_btree(nodelist,1); //建立printf("\n The node content of arrary_structure is:\n");printf("\nPlease input the node value(1...9) you want search:");scanf("%d",&findnode);//进行遍历查找point=btree_travesal_search(root,findnode);if(point!=NULL){cout << "\n=Travesal search result: \n";printf(" The finding node value is [%d]\n",point->data); }elseprintf("\nTravesal search result: NOT found!!\n");//二分查找point = btree_travesal_search1(root,findnode);if(point!=NULL){cout << "\n=Binary search result: \n";printf(" The finding node value is [%d]\n",point->data); }else cout << "\nBinary search not found!!\n";inoder(root);/*for(i=1;i<16;i++)cout << nodelist[i] <<" ";cout <<endl;//打印树状结构连表的内容//cout <<"\nThe postoder travesal result is";inoder(root);*/system("PAUSE");return EXIT_SUCCESS;}#include <cstdlib>#include <iostream>using namespace std;struct tree{ // 声明树的结构struct tree *left;int data;struct tree *right;};typedef struct tree treenode;//声明新类型的树的结构typedef treenode *b_tree;//声明二叉树的链表b_tree creat_btree(int *nodelist,int position)//看好了某些定义b_tree {b_tree newnode;//声明树根指针if(nodelist[position]==0||position>15){cout <<"d";return NULL;}else{newnode = (b_tree) malloc(sizeof(treenode));//申请空间newnode->data=nodelist[position];//建立节点内容newnode->left=creat_btree(nodelist,2*position); //递归建立左子树newnode->right=creat_btree(nodelist,2*position+1);//递归建立右子树return newnode;}}//建立二叉树void inoder(b_tree point){if(point!=NULL){inoder(point->left);cout << point->data<<" ";inoder(point->right);}}int main(int argc, char *argv[]){b_tree root = NULL;//树根指针int i;int nodelist[16]={0,5,9,2,1,4,7,0,0,0,3,0,6,8,0,0};//---------------建立树状结构-----------//root = creat_btree(nodelist,1);printf("\n The node content of arrary_structure is:\n");for(i=1;i<16;i++)cout << nodelist[i] <<" ";cout <<endl;//打印树状结构连表的内容//cout <<"\nThe postoder travesal result is";inoder(root);system("PAUSE");return EXIT_SUCCESS;}注：递归的构建二叉树只是单独的递归调用构造函数，并没有按照一定的大小比较规则进行排序。
二叉树后序遍历的思想：从根节点开始，沿左子树一直走到没有左孩子的节点为止，并将所经[节点]的地址第一次进栈；当找到没有左孩子的节点时，此节点的左子树已访问完毕；从栈顶退出该节点，判断该节点是否为第一次进栈，如是，再将所经[节点]的地址第二次进栈，并沿该节点的右子树一直走到没有右孩子的节点为止，如否，则访问该节点；此时，该节点的左、右子树都已完全遍历，且令指针p = NULL;如此重复到栈空为止。
例如有如上图所示二叉树，则后序遍历的顺序是：O J / I * H + G A 实现程序如下：#include <cstdlib>#include <iostream>using namespace std;struct tree{ // 声明树的结构struct tree *left;int data;struct tree *right;};typedef struct tree treenode;//声明新类型的树的结构typedef treenode *b_tree;//声明二叉树的链表b_tree insert_node(b_tree root,int node)//看好了某些定义b_tree {b_tree newnode;//声明树根指针b_tree currentnode;//声明目前节点指针b_tree parentnode;//声明父亲接点指针//建立新节点的内存空间newnode = (b_tree) malloc(sizeof(treenode));//建立新节点的内存空间newnode->data=node;//存入节点的内容newnode->right=NULL;//设置右指针的初值newnode->left=NULL;//设置左指针的初值if(root == NULL) return newnode;else{currentnode = root;while(currentnode!=NULL){parentnode = currentnode;if(node < currentnode->data)//比较节点的数值大小{currentnode = currentnode->left;}//坐子树else currentnode =currentnode->right;//右子树}//寻找空的节点便插入if(parentnode->data > node){parentnode->left = newnode;}else parentnode->right = newnode;//插入了哈哈}return root;}//建立二叉树b_tree creat_btree(int *data,int len){b_tree root = NULL;//根节点指针int i;for(i=0;i<len;i++)//建立树状结构{ root=insert_node(root,data[i]);}return root;}//打印二叉树/*void print_btree(b_tree root){b_tree pointer;pointer = root->left;printf("Print left_subtree node of root:\n"); while(pointer!=NULL){printf("[%2d]\n",pointer->data);pointer = pointer->left;//指向左节点}pointer = root->right;printf("Print right_subtree node of root:\n"); while(pointer!=NULL){printf("[%2d]\n",pointer->data);//打印节点的内容pointer = pointer->right;//指向右节点}}*/void postoder(b_tree point){if(point!=NULL){postoder(point->left);//左--右--根postoder(point->right);cout << point->data<<" ";}}int main(int argc, char *argv[]){b_tree root = NULL;int i,index;int value;int nodelist[20];printf("\n Please input the elsements of binary tree (Exit for 0):\n"); index = 0;scanf("%d",&value);while (value!= 0){nodelist[index]=value;index++;scanf("%d",&value);}root= creat_btree(nodelist,index);//建立二叉树// print_btree(root);//打印二叉树节点的内容cout <<"\nThe postoder travesal result is";postoder(root);system("PAUSE");return EXIT_SUCCESS;}#include <string.h>#include <ctype.h>#include <malloc.h>#include <stdio.h>#include <stdlib.h>#include <conio.h>#include <mem.h>#include <alloc.h>#define OK 1#define ERROR 0#define MAXSIZE 100#define MAXRC 20 typedef int Status;typedef int ElemType; typedef struct{int i,j;ElemType e;}Triple;typedef struct{Triple data[MAXSIZE+1]; int rpos[MAXRC+1];int mu,nu,tu;}RLSMatrix;typedef struct OLNode{int i,j;ElemType e;struct OLNode *right,*down; }OLNode,*OLink;typedef struct{OLink *rhead,*chead;}CrossList;Status CreateSMatrix(RLSMatrix *M);void DestroySMatrix(RLSMatrix *M);void PrintSMatrix(RLSMatrix M);Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q);Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T);int menu_select();Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C);Status Exchange(RLSMatrix M,CrossList *N);Status Show(CrossList N);Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M); Status DestoryCrossList(CrossList *M);void About();main(){RLSMatrix A,B,C;CrossList N;clrscr();About();for(;;){switch(menu_select()){case 1:clrscr();printf("\n\n\n\t-------------Create Sparse Matrix A-----------------"); CreateSMatrix(&A); break;printf("\n\n\n\t-------------Create Sparse Matrix B-----------------"); CreateSMatrix(&B); break;case 3:Operate(A,B,&C);break;case 4:Change(A,B,C,&N); break;case 5:About();break;case 6:DestroySMatrix(&A);DestroySMatrix(&B);DestroySMatrix(&C);DestoryCrossList(&N);exit(0);}}}int menu_select(){char *menu[]={"","",""," +--------------MENU--------------+"," | |"," | 1.Create Sparse Matrix A |"," | 2.Create Sparse Matrix B |"," | 3.Operate |"," | 4.Change into CrossList |"," | 5.About... |"," | 6.Quit |"," | |"," | |"," +-----------------------------------+"," By Teacher"," 10/10/07",};char s[3];int c,i;gotoxy(1,25);printf("Any key to enter menu......\n"); getch();clrscr();for(i=0;i<16;i++){ gotoxy(10,i+1);cprintf("%s",menu[i]);}window(1,1,80,25);gotoxy(10,21);do{printf("\n Enter your choice(1~6):"); scanf("%s",s);c=atoi(s);}while(c<1||c>6);return c;}Status CreateSMatrix(RLSMatrix *M) {int i;Triple T;int flag=0,mis;printf("\nPlease input the row,col,and nonzero element number of the Sparse Matrix."); printf("\nForm:row num,col num,nonzero element num\n");scanf("%d,%d,%d",&(*M).mu,&(*M).nu,&(*M).tu);(*M).data[0].i=0;for(i=1;i<=(*M).tu;i++){ mis=0;do{if(flag){printf("ERROR INPUT!\n");flag=0;mis++;}if(mis==3){printf("Fail Create !");return OK;}printf("Please input the row,col and value of the %dth nonzero element:",i);scanf("%d,%d,%d",&T.i,&T.j,&T.e);if(T.i<1||T.i>(*M).mu||T.j<1||T.j>(*M).nu)flag=1;if(T.i<(*M).data[i-1].i||T.i==(*M).data[i-1].i&&T.j<=(*M).data[i-1].j)flag=1;}while(flag);(*M).data[i]=T;}for(i=1;i<=(*M).tu;i++)for(T.i=0;T.i<(*M).data[i].i-(*M).data[i-1].i;T.i++)(*M).rpos[(*M).data[i].i-T.i]=i;for(i=(*M).data[(*M).tu].i+1;i<=(*M).mu;i++)(*M).rpos[i]=(*M).tu+1;PrintSMatrix(*M);return OK;}void PrintSMatrix(RLSMatrix M){int i,j,k;printf("\n ");for(i=1,k=1;i<=M.mu;i++){for(j=1;j<=M.nu;j++){if(M.data[k].i==i&&M.data[k].j==j){printf("%d\t",M.data[k].e); k++;}else printf("0\t");while(j==M.nu){printf("\n ");break;}}}}Status ADD(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) {int k,p,q;if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;(*Q).mu=M.mu;(*Q).nu=M.nu;(*Q).tu=0;M.rpos[M.mu+1]=M.tu+1;N.rpos[N.mu+1]=N.tu+1;for(k=1;k<=M.mu;++k){(*Q).rpos[k]=(*Q).tu+1;p=M.rpos[k];q=N.rpos[k];while(p<M.rpos[k+1]&&q<N.rpos[k+1]){if(M.data[p].j==N.data[q].j){(*Q).data[(*Q).tu+1].e=M.data[p].e+N.data[q].e; if((*Q).data[(*Q).tu+1].e!=0){++(*Q).tu;(*Q).data[(*Q).tu].i=k;(*Q).data[(*Q).tu].j=M.data[p].j;}++p;++q;}else if(M.data[p].j<N.data[q].j){++(*Q).tu;(*Q).data[(*Q).tu].e=M.data[p].e;(*Q).data[(*Q).tu].i=k;(*Q).data[(*Q).tu].j=M.data[p].j;++p;}else{++(*Q).tu;(*Q).data[(*Q).tu].e=N.data[q].e;(*Q).data[(*Q).tu].i=k;(*Q).data[(*Q).tu].j=N.data[q].j;++q;}}while(p<M.rpos[k+1]){++(*Q).tu;(*Q).data[(*Q).tu].e=M.data[p].e;(*Q).data[(*Q).tu].i=k;(*Q).data[(*Q).tu].j=M.data[p].j;++p;}while(q<N.rpos[k+1]){++(*Q).tu;(*Q).data[(*Q).tu].e=N.data[q].e;(*Q).data[(*Q).tu].i=k;(*Q).data[(*Q).tu].j=N.data[q].j;++q;}}return OK;}Status SubtS(RLSMatrix M,RLSMatrix N,RLSMatrix *Q){int i;if(M.mu!=N.mu||M.nu!=N.nu) return ERROR;for(i=1;i<=N.tu;++i)N.data[i].e*=-1;ADD(M,N,Q);return OK;}Status Mult(RLSMatrix M,RLSMatrix N,RLSMatrix *Q) {int arow,brow,p,q,ccol,ctemp[MAXRC+1];if(M.nu!=N.mu) return ERROR;(*Q).mu=M.mu;(*Q).nu=N.nu;(*Q).tu=0;M.rpos[M.mu+1]=M.tu+1;N.rpos[N.mu+1]=N.tu+1;if(M.tu*N.tu!=0){for(arow=1;arow<=M.mu;++arow){for(ccol=1;ccol<=(*Q).nu;++ccol)ctemp[ccol]=0;(*Q).rpos[arow]=(*Q).tu+1;for(p=M.rpos[arow];p<M.rpos[arow+1];++p){brow=M.data[p].j;for(q=N.rpos[brow];q<N.rpos[brow+1];++q){ccol=N.data[q].j;ctemp[ccol]+=M.data[p].e*N.data[q].e;}}for(ccol=1;ccol<=(*Q).nu;++ccol)if(ctemp[ccol]){if(++(*Q).tu>MAXSIZE) return ERROR;(*Q).data[(*Q).tu].i=arow;(*Q).data[(*Q).tu].j=ccol;(*Q).data[(*Q).tu].e=ctemp[ccol];}}}return OK;}Status FastTransposeSMatrix(RLSMatrix M,RLSMatrix *T) {int col,p,q,t,num[MAXRC+1],cpot[MAXRC+1];(*T).mu=M.nu;(*T).nu=M.mu;(*T).tu=M.tu;if((*T).tu){for(col=1;col<=M.nu;++col) num[col]=0;for(t=1;t<=M.tu;++t) ++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col) cpot[col]=cpot[col-1]+num[col-1]; for(p=1;p<=M.tu;++p){col=M.data[p].j; q=cpot[col];(*T).data[q].i=M.data[p].j;(*T).data[q].j=M.data[p].i;(*T).data[q].e=M.data[p].e;++cpot[col];}}PrintSMatrix(M);printf("\nTranspose:\n");PrintSMatrix(*T);return OK;}Status Operate(RLSMatrix A,RLSMatrix B,RLSMatrix *C){int c;char t;do{clrscr();printf("\nInput your choice:\n(ADD--1,SUB--2,MUL--3,Transpose A--4,Transpose B--5,QUIT--any except 1~5)\n");scanf("%d",&c);switch(c){case 1:if(A.mu!=B.mu||A.nu!=B.nu){printf("Can't,condition misfit!\n");break;}ADD(A,B,C);PrintSMatrix(A);printf("\n\t(+)\n");PrintSMatrix(B);printf("\n\t(=)\n");PrintSMatrix(*C);break;case 2:if(A.mu!=B.mu||A.nu!=B.nu) {printf("Can't,condition misfit!\n"); break;}SubtS(A,B,C);PrintSMatrix(A);printf("\n\t(-)\n");PrintSMatrix(B);printf("\n\t(=)\n");PrintSMatrix(*C);break;case 3:if(A.nu!=B.mu){printf("Can't,condition misfit\n"); break;}Mult(A,B,C);PrintSMatrix(A);printf("\n\t(*)\n");PrintSMatrix(B);printf("\n\t(=)\n");PrintSMatrix(*C);break;case 4:FastTransposeSMatrix(A,C);break;case 5:FastTransposeSMatrix(B,C);break;default: return OK;}/* switch */printf("Want to continue? (y/n)?");t=getch();}while(t=='y');return OK;}void DestroySMatrix(RLSMatrix *M){(*M).mu=0;(*M).nu=0;(*M).tu=0;}Status Exchange(RLSMatrix M,CrossList *N){int i;OLNode *p,*Q;(*N).mu=M.mu;(*N).nu=M.nu;(*N).tu=M.tu;(*N).rhead=(OLink*)malloc((MAXRC+1)*sizeof(OLink)); (*N).chead=(OLink*)malloc((MAXRC+1)*sizeof(OLink));for(i=1;i<=10;i++) {(*N).rhead[i]=NULL;(*N).chead[i]=NULL;} for(i=1;i<=M.tu;i++){Q=(OLNode*)malloc(sizeof(OLNode));Q->i=M.data[i].i;Q->j=M.data[i].j;Q->e=M.data[i].e;if(!(*N).rhead[M.data[i].i]){(*N).rhead[M.data[i].i]=Q;Q->right=NULL;}else{for(p=(*N).rhead[M.data[i].i];p->right;p=p->right); p->right=Q;Q->right=NULL;}if(!(*N).chead[M.data[i].j]){(*N).chead[M.data[i].j]=Q;Q->down=NULL;}else{for(p=(*N).rhead[M.data[i].j];p->down;p=p->down); p->down=Q;Q->down=NULL;}}return OK;}Status Show(CrossList N){int i,j,sub;int x,y;OLNode *q;printf("\n\n ");for(i=1;i<=N.nu;i++) printf(" --- ");printf("N.chead\n\nN.rhead\n");for(i=1;i<=N.mu;i++){if(N.rhead[i]){q=N.rhead[i];printf(" |");for(j=0;q;j=q->j,q=q->right){sub=q->j-j;while(sub>1){printf("-----------");sub--;}printf("--->|%d|%d|%d|",q->i,q->j,q->e);x=wherex();y=wherey();gotoxy(x-4,y-1);printf("V",x);gotoxy(x-4,y-2);printf("|");gotoxy(x,y);}printf("\n\n\n");}else printf(" |^\n\n");;}return OK;}Status Change(RLSMatrix A,RLSMatrix B,RLSMatrix C,CrossList *M) {int cho;clrscr();printf("\n\n\nChoose the RLSMatrix you want to change into CrossList\n"); printf("(1--A,2--B,3--C,any but 123 back) :");scanf("%d",&cho);switch(cho){case 1:Exchange(A,M);Show(*M);break;case 2:Exchange(B,M);Show(*M);break;case 3:Exchange(C,M);Show(*M);break;}return OK;}Status DestoryCrossList(CrossList *M){free((*M).rhead);free((*M).chead);(*M).chead=(*M).rhead=NULL;return OK;}void About(){clrscr();gotoxy(20,10);printf("Made By: \n\n\t\t\t");printf("\ The College of Information Engineering \n\n\t\t\t");printf(" in AnHui University Of Finance & Economics "); }#include <stdio.h>void swap(int *a, int *b){int temp = *a;*a = *b;*b = temp;}int partition(int *array, int low, int high){int middle = (low + high)/2;for(int i=low,j=high; i<j; ) {while(array[i] < array[middle]) ++i;if(i < j && i != middle) {swap(&array[i], &array[middle]);middle = i;}while(array[j] > array[middle]) --j;if(i < j && j != middle) {swap(&array[j], &array[middle]);middle = j;}}return middle;}int quicksort(int *array, int low, int high){int piovt_pos;if(low < high) {piovt_pos = partition(array, low, high);quicksort(array, low, piovt_pos - 1);quicksort(array, piovt_pos + 1, high);}}struct barrel {int a[10];int count;};int main(){int data[] = {23, 12, 3, 54, 1, 98, 24, 34};int min = data[0];int max = data[0];for(int i=1; i<sizeof(data)/sizeof(int); ++i) {min = min < data[i] ? min : data[i];max = max > data[i] ? max : data[i];}int num = (max - min + 1)/10 + 1;barrel *pBarrel = new barrel[num];for(int i=0; i<sizeof(data)/sizeof(int); ++i) {int j = (pBarrel+((data[i]-min+1)/10))->count; (pBarrel+((data[i]-min+1)/10))->a[j] = data[i]; (pBarrel+((data[i]-min+1)/10))->count++;}static int pos = 0;for(int i=0; i<num; ++i) {quicksort((pBarrel+i)->a, 0, (pBarrel+i)->count-1);for(int j=0; j<(pBarrel+i)->count; ++j) {data[pos++] = (pBarrel+i)->a[j];}}for(int i=0; i<8; ++i) {printf("%d ", data[i]);}return 0;}简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。
