《数据结构基础知识要点.pdf》由会员分享，可在线阅读，更多相关《数据结构基础知识要点.pdf（17页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一章 数据结构 1定义 数据结构是计算机存储、组织数据的方式.数据结构是抽象数据类型的物理实现.2.数据结构包括如下几个方面:(1）数据元素之间的逻辑关系，即数据的逻辑结构。(2)数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。（3)施加在该数据上的操作,即数据的运算。2。逻辑结构类型(1）集合结构。交通工具的集合，动物的集合(2)线性结构。一对一，综合素质测评产生的学生排名(3）树形结构。一对多，单位的组织结构图，族谱（4）图形结构.多对多,生产流程、施工计划、网络建设图等 3.存储结构类型(1)顺序存储方法。数组(2)链式存储方法。链表（3)索引存储方
2、法(4)散列存储方法 4.算法 通常把具体存储结构上的操作实现步骤或过程称为算法。C 语言里通常表现为解决问题的步骤 程序=算法（加工数据）+数据结构(数据的存储和组织）5.算法的五个特征（1)有穷性:在有穷步之后结束。(2）确定性:无二义性.（3）可行性：可通过基本运算有限次执行来实现。（4）有输入：可有零个或多个.(5）有输出:至少有一个输出。6.算法分析(1)时间复杂度：（算法的工作量大小）通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数.算法中基本运算次数 T（n）是问题规模 n 的某个函数 f（n）,记作：T(n）=O(f
3、(n)（2)空间复杂度：实现算法所需的存储单元多少 第二章线性表 1.线性表的基本概念 线性表是具有相同特性的数据元素的一个有限序列.该序列中所含元素的个数叫做线性表的长度,用 n 表示，n0。2。线性结构的基本特征为:(1）集合中必存在唯一的一个“第一元素；(2）集合中必存在唯一的一个“最后元素”;（3）除最后一个元素之外，均有唯一的后继（后件）；（4）除第一个元素之外，均有唯一的前驱（前件)。3。定义顺序表 线性表逻辑结构 顺序表存储结构 typedefstruct ElemType dataMAXCOUNT；/定义存放顺序表元素的数组 int length；/length 为存放线性表的
4、实际长度 SqList；/顺序表类型 4.顺序表上的运算及其实现(1).建立顺序表 CreateList 创建一个空的顺序表,要完成线性表所需空间的分配和其他初始化设置。(2）求线性表的长度 ListLength(3）输出线性表 DispList(4）在线性表中的指定位置插入一个元素 InsertElem(5)根据键值查找指定元素 FindElemByNum(6)获取指定位置的元素信息 GetElem(7）删除指定位置的元素 DelElem(8）释放线性表 DestroyList 5。线性表的链式存储单链表(data 域和指针域 next)由于顺序表中的每个元素至多只有一个前驱元素和一个后继元
5、素，即数据元素之间是一对一的逻辑关系，所以当进行链式存储时，一种最简单也最常用的方法是：在每个结点中除包含有数据域外,只设置一个指针域，用以指向其后继结点,这样构成的链接表称为线性单向链接表,简称单链表；7.单链表的定义 LinkList 类型的定义如下:typedefstructLNode /定义单链表结点类型*/ElemType data；structLNode next;/*指向后继结点/LinkList；a1 an a2 head 头结点 开始结点 终端结点 8.顺序表上的运算及其实现 1、创建单链表 LinkList*CreateList(）；2、初始化单链表 void InitLi
6、st（LinkList*list）;3、释放单链表 void DestroyList（LinkList*list）;4、获取单链表中元素的数量 intListLength(LinkList list）;5、输出单链表中的所有数据 void DispList（LinkList list）;6、获取单链表中指定位置的元素 intGetElem(LinkList list，intloc,ElemType*pElem)；7、根据键值查找指定元素 intFindElemByNum（LinkList*list，char keyCh,ElemType*pElem)；8、采用头插法向单链表中插入一个元素 in
7、tInsertElem_Head（LinkList list，ElemTypemyElem）;9、采用尾插法向单链表中插入一个元素 intInsertElem_Foot（LinkList list,ElemTypemyElem）；10、向单链表中的指定位置插入一个元素 ntInsertElem_Loc(LinkList*list，intloc，ElemTypemyElem）；11、删除指定位置的元素 intDelElem(LinkList*list，intloc，ElemType pElem)；9.线性表的链式存储双链表（data 域指针域 next 和 pre 前驱）对于双链表,采用类似于单
8、链表的类型定义，其 DLinkList 类型的定义如下:typedefstructDNode /定义双链表结点类型*/ElemType data;structDNode prior；/指向前驱结点/structDNode*next;/指向后继结点/DLinkList 在双链表中 p 所指的结点之后插入一个*s 结点.其操作语句描述为:s-next=pnext;/*将 s 插入到 p 之后*/pnext-prior=s;s-prior=p；pnext=s；归纳起来，删除双链表 L 中p 结点的后续结点。其操作语句描述为:p-next=qnext;qnext-prior=p;10。循环链表 循环链
9、表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空，而是指向表头结点，整个链表形成一个环。由此,从表中任一结点出发均可找到链表中其他结点。带头结点的单向循环链表和双向循环链表如下图 a1 a1 a2 head dhead a1 a2 an 头结点 开始结点 终端结点 头结点 开始结点 终端结点(a)循环单链表(b)循环双链表 第三章栈和队列 1.栈的定义及基本运算 栈是限定只能在表尾进行插入和删除的线性表，并将表尾称为栈顶，表头称为栈底。栈的基本运算如下：（1)判栈空 IsEmpty(S)。若栈为空则返回“真“,否则返回”假“；（2)入栈操作（压栈）Push（S，x）将新
10、元素压入栈中,使其成为栈顶元素；（3)出栈操作(弹栈）Pop（S,x）若栈不空则返回栈顶元素，并从栈中删除栈顶元素，否则返回 NULL；（4）取栈顶元素 GetTop（s，x）若栈不空则返回栈顶元素,否则返回 NULL；（5）置空栈 Clear（s）将当前栈设定为空栈；2。顺序栈的存储结构及算法实现 1顺序栈 顺序栈利用一组连续的存储单元存放从栈底到栈顶的诸元素。typedefstruct int data；int capacity;int top;Stack;2顺序栈的基本运算的实现(1)入栈操作 int Push（Stack S，Datatype x);(2)出栈操作 int Pop(St
11、ack s，Datatype x);(3)取栈顶操作 intGetTop（Stack S，Datatype x）；3。栈的链表存储结构 1栈可以用单链表作为存储结构,链表的结点结构描述如下：typedef char ElemType;typedefstructLsnode ElemType data;structLsnode next；Lsnode；/结点的类型标识符 Lsnode top;2栈的相关术语 1初始化空栈 voidIniStack(Lsnode*top）topnext=NULL;调用此函数之前，在主调函数中(例如 main（）)说明一个指针变量后，先为它申请分配一个结点，然后调用
12、初始化函数。2入栈操作 链栈入栈操作的含义是：将一个元素推入指定的链栈中。对该操作应设置两个参数，即在参数中指定一个链栈及入栈的元素.假设指定的链栈 top，入栈元素 x 其类型为ElemType,入栈操作取名为 push，则该操作可表示为：viod Push（Lsnode top,ElemType x）操作的功能为在由 top 指向的链栈中插入元素 x，使 x 成为栈顶元素.3。出栈操作 链栈出栈操作的含义是：从链栈中弹出栈顶结点并返回该结点中的元素值。对该操作应设置一个参数，即在参数中指定一个链栈。假设指定的链栈 top，出栈操作取名为 pop,则该操作可表示为：ElemTypePop(L
13、snode*top)操作的功能为从由 top 指向的链栈中弹出栈顶结点并返回该结点中的元素值。4。队列的基本操作 进队算法:根据队列的结构,若队尾指针不在队的最大长度上，则首先队尾指针加，元素进队，否则就是队满，无法进队。ADDQUEUE（queue,r，f，in)/*在 queue 队列中进一个元素 in，f 和 r 分别是队首和队尾的标志*/if(r=n）printf(”队满”)；else r+;queuer=in；出队算法:出队首先要判断队列中是否有元素,即 R 是否等于 F，R=F 可能出现在初态，也可能出现在出队、进队的动态变化中.DELQUEUE(queue,r,f，out)/在
14、queue 队列中退出一个元素到 out，f 和 r 分别是队首和队尾的标志*/if(f=r)printf（队空”）;else out=queue+f;5.链队的存储结构及其运算 当队空时，Front=NULL；Rear=NULL;所谓队满，是指在可利用的空间表中，所有的结点被取完，即 AV=NULL 时,才表示队满。根据队列的操作特点,进队和退队分别在表的两端进行，具体表现为“先进先出”。从链队的结构可看出，进队的基本操作步骤为（设进队结点的地址为 x）：Rearnext=x；xnext=NULL;Rear=x；第四章串 1。串的基本概念 串结构的形式化定义为：String=（D，R)其中,
15、D=aiaicharacter，i=1，2n，n0,R=a i-1 ai a i-1,aiD，i=1，2，n 串的基本运算有：(1)初始化 ClearString(s）:初始化串 s.（2)StrAssign（s，ch）:串赋值.（3)StrCopy(s，t):串复制。（4）StrConcat(t，s1，s2）:串联接。（5)求串长 StrLen(s）:返回 s 串的元素个数，即 s 串的长度。（6)串比较 StrCom（s，t)（7）求子串 SubStr（t，s，pos,len）：返回 s 串的第 pos 个字符起始的长度为 len 的子串.(8）插入运算 StrInsert（s，pos，t
16、）：把串 t 的值插入到串 s 的第 pos 个字符之后。（9)删除运算 StrDel(s，pos，len）：将串 s 中从第 pos 字符起始的长度为 len 的子串删除。（10）子串定位 StrIndex（s，t,pos）：从主串 s 的第 pos 个字符起定位串 s 中是否存在和串 t值相等的子串，若存在，则返回子串 t 在主串 s 中第一次出现的位置,否则,返回函数值 0。（11）置换运算 StrReplace（s，pos，len，t）:用 t 串置换 s 串中第 pos 字符开始的连续的 len个字符。2.串的定长顺序存储及运算实现 1定长顺序串的基本运算实现（1）求串长（2）串的联
17、接（3）求子串（4）子串的插入（5）子串的删除(6）串的置换 2在堆式动态存储分配下的串的几种常见运算的实现.（1）串赋值 StrAssign(t，chars)（2）串联接 StrConcat（t，s1,s2）(3）求子串 SubString(t,s,pos,len)(4）插入函数 StrInsert(s,pos，t)(5）删除函数 StrDelete(s,pos,t)3。串的块链存储表示 顺序串上的插入和删除操作运算需要移动大量的字符。因此，可以采用单链表方式来存储串值，串的这种链式存储结构简称为链串。但在利用链表存储串值时，每个结点既可以存放一个字符，也可以存放多个字符，即存在一个“结点大
18、小的问题。结点的大小是指结点的数据域可存放字符的个数。第六章树和二叉树 1。树的表示（1)树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构，非常直观和形象 （2）文氏图表示法。使用集合以及集合的包含关系描述树结构。(3)凹入表示法。使用线段的伸缩描述树结构。（4）括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号 间隔来描述树结构。2。树的基本术语 1.结点的度与树的度:树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为 m 的树称为 m 次树。2。分支结点与叶结点：度不为零的结点称为非终端结点，又叫分支结点。度为零的
19、结点称为终端结点或叶结点.在分支结点中,每个结点的分支数就是该结点的度.3。路径与路径长度:如果一棵树中的一串结点 n1，n2，,nk,有如下关系：结点 ni 是 ni+1 的父结点(1ik）,就把 n1,n2,，nk 称为一条由 n1 至 nk 的路径，这条路径的长度是 k1。4。孩子结点、双亲结点和兄弟结点:在一棵树中，每个结点的后继，被称作该结点的孩子结点(或子女结点）。相应地,该结点被称作孩子结点的双亲结点（或父母结点).具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系，可以把每个结点的所有子树中的结点称为该结点的子孙结点，从树根结点到达该结点的路径上经过的所有结点被称作该结点的
20、祖先结点 5。结点的层次和树的高度:树中的每个结点都处在一定的层次上.结点的层次从树根开始定义，根结点为第 1 层,它的孩子结点为第 2 层，以此类推,一个结点所在的层次为其双亲结点所在的层次加 1。树中结点的最大层次称为树的高度(或树的深度）.6。有序树和无序树:若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树。7。森林：n（n0）个互不相交的树的集合称为森林。森林的概念与树的概念十分相近，A C G J B E D F I H M K L H L D K I M C G J E B F 文氏图表示法 A F C A B D E G
21、J H I K L M 凹入表示法 因为只要把树的根结点删去就成了森林.反之，只要给 n 棵独立的树加上一个结点，并把这 n 棵树作为该结点的子树，则森林就变成了树。3。树的性质 性质 1 树中的结点数等于所有结点的度数加 1。性质 2 度为 m 的树中第 i 层上至多有 mi1 个结点，这里应有 i1。性质 3 高度为 h 的 m 次树至多有个结点。性质 4 具有 n 个结点的 m 次树的最小高度为logm（n(m1）+1).4。树的特点：树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。树中所有结点可以有零个或多个后继结点.5。树的基本运算 树的运算主要分为三大类：第一类
22、,寻找满足某种特定关系的结点，如寻找当前结点的双亲结点等；第二类，插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第 i个孩子结点等;第三类，遍历树中每个结点，这里着重介绍.树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历运算的算法主要有先根遍历和后根遍历两种。注意,下面的先根遍历和后根遍历算法都是递归的.1.先根遍历 先根遍历过程为：(1)访问根结点；（2）按照从左到右的次序先根遍历根结点的每一棵子树。2.后根遍历 后根遍历过程为：(1)按照从左到右的次序后根遍历根结点的每一棵子树；（2）访问根结点。6.二叉树的定义 二叉树（Binary
23、Tree）是 n(n0）个结点的有限集合.它或为空树（n0),或为非空树；对于非空树有:（1)有一个特定的称之为根的结点；(2）根结点以外的其余结点分别由两棵互不相交的称之为左子树和右子树的二叉树组成。这个递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成的。由于左、右子树也是二叉树，则由二叉树的定义,它们也可以为空。由此，二叉树可以有五种基本形态 7。二叉树的重要性质 性质 1 二叉树第 i（i1）层上至多有 2i-1 个结点。性质 2 深度为 k(k1）的二叉树至多有 2k1 个结点。性质 3 在任意二叉树中，若叶子结点(即度为零的结点)个数为
24、n0，度为 1 的结点个数 n1，度为 2 的结点个数为 n2,那么 n0=n2+1。性质 4 具有 n 个(n0）结点的完全二叉树的高度为log2n+1或log2n+1。性质 5 若对有 n（1in)个结点的完全二叉树进行顺序编号，那么,对于编号为 i(i1）的结点:当 i=1 时，该结点为根，它无双亲结点；当 i1 时,该结点的双亲结点编号为i/2;若 2in，则有编号为 2i 的左孩子，否则没有左孩子；若 2i+1n，则有编号为 2i+1 的右孩子，否则没有右孩子。满二叉树:深度为 k 且含有 2k1 个结点的二叉树为满二叉树，这种树的特点是每层上的结点数都是最大结点数 在一棵二叉树中,
25、如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上,这样的一棵二叉树称作满二叉树。如图所示，（a）图就是一棵满二叉树，（b）图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树 完全二叉树：深度为 k，含有 n 个结点的二叉树,当且仅当每个结点的编号与相应满二叉树结点顺序号从 1 到 n 相对应时，则称此二叉树为完全二叉树 显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图所示（a)为一棵完全二叉树,(b）不是完全二叉树。8.二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是
26、：对该树中每个结点进行编号，其编号从小到大的顺序就是结点存放在连续存储单元的先后次序.若把二叉树存储到一维数组中,则该编号就是下标值加 1(注意,C/C+语言中数组的起始下标为 0)。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同 9。二叉树的链式存储结构 data 表示值域,用于存储对应的数据元素,lchild 和 rchild 分别表示左指针域和右指针域，用于分别存储左孩子结点和右孩子结点（即左、右子树的根结点)的存储位置 下图（a)给出一棵二叉树的二叉链表存储表示。二叉链表也可以带头结点的方式存放，如图(b)所示。二叉链表存储表示可描述为：typedefstructbit
27、node datatype data；structbitnode lchild;rchild;/*左右孩子指针域/BiTNode,BiTree;定义指针变量，用来存放根结点地址,通常用该指针标识一个二叉树：BiTree t；10。二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。它是最基本的运算，是二叉树中所有其他运算的基础。1.先序遍历（DLR)先序遍历二叉树的过程是：(1)访问根结点；（2）先序遍历左子树；(3)先序遍历右子树。voidPreOrder（BiTreebt）if(bt=NULL)return；/*递归调用的结束条件*/Visit(
28、bt)；/*访问根结点*/PreOrder(btlchild);/*先序递归遍历 bt 的左子树/PreOrder(btrchild);/*先序递归遍历 bt 的右子树*/2.中序遍历（LDR)中序遍历二叉树的过程是：（1)中序遍历左子树;（2)访问根结点；（3）中序遍历右子树.voidInOrder（BiTreebt)if（bt=NULL）return；/递归调用的结束条件*/InOrder(btlchild)；/中序递归遍历 bt 的左子树*/Visit(bt);/*访问根结点/InOrder(btrchild);/*中序递归遍历 bt 的右子树*/3。后序遍历（LRD）后序遍历二叉树的过
29、程是：(1）后序遍历左子树；（2)后序遍历右子树；(3）访问根结点.voidPostOrder（BiTreebt）if（bt=NULL）return;/递归调用的结束条件*/PostOrder（btlchild）;/*后序递归遍历 bt 的左子树*/PostOrder(btrchild);/*后序递归遍历 bt 的右子树*/Visite(bt）;/*访问根结点/4.层次遍历 其过程是：若二叉树非空（假设其高度为 h），则:（1）访问根结点（第 1 层)；（2)从左到右访问第 2 层的所有结点；（3）从左到右访问第 3 层的所有结点、第 h 层的所有结点。11。二叉树基本运算概述（1)创建二叉树
30、 CreateBTNode(*b,str)：根据二叉树括号表示法的字符串str 生成对应的链式存储结构。Initiate（bt)：建立一棵空的二叉树 bt，并返回 bt。二叉树带不带头结点，可根据具体需要而定.建立一棵空的带头结点的二叉树 BiTree Initiate(）/*建立一棵空的带头结点的二叉树*/BiTNode bt；bt=（BiTNode*）malloc(sizeof(BiTNode）；btlchild=NULL btrchild=NULL；returnbt；建立一棵空的不带头结点的二叉树 BiTree Initiate（）/初始建立一棵空的不带头结点的二叉树*/BiTNode
31、bt；bt=NULL;returnbt；在主函数中，可以通过如下方式调用 Initiate 函数:main()BiTree t;/定义根结点指针变量*/t=Initiate(）;*void DispBTree(bt)算法:对于非空二叉树 bt：先输出其元素值 当其有左孩子或右孩子时 输出（递归输出左子树 输出，递归输出右子树 输出）（2）查找结点 FindNode(b，x）:在二叉树 b 中寻找 data 域值为 x 的结点，并返回指向该结点的指针。(3）找孩子结点 LchildNode（p)和 RchildNode(p）：分别求二叉树中结点p 的左孩子结点和右孩子结点(4）求高度 BTNod
32、eDepth（*b)：求二叉树 b 的高度。若二叉树为空，则其高度为 0；否则,其高度等于左子树与右子树中的最大高度加 l.（5）输出二叉树 DispBTNode（*b）：以括号表示法输出一棵二叉树。12.由遍历序列恢复二叉树(递归思想）1、依据遍历定义：由二叉树的先序序列和中序序列可唯一地确定该二叉树.由二叉树的后序序列和中序序列也可唯一地确定该二叉树。由二叉树的先序序列和后序序列不能唯一地确定该二叉树。2、分隔过程：已知一棵二叉树的先序序列与中序序列分别为：A B C D E F G H I，B C A E D G H F I,试恢复该二叉树。voidDispBiTNode(BiTree
33、T)if(T!=NULL)printf(%c,T-data);if(T-lchild!=NULL|T-rchild!=NULL)13。哈夫曼树的概念 设二叉树具有 n 个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。记为：WPLWkLk 其中 Wk为第 k 个叶结点的权值，Lk为第 k 个叶结点的路径长度。具有最小带权路径长度的二叉树称为哈夫曼树.14。构造哈夫曼树 根据哈夫曼树的定义，一棵二叉树要使其 WPL 值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。那么如何构造一棵哈夫曼树呢？其方法如下：(1)由给
34、定的 n 个权值W1，W2，.。.，Wn构造 n 棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合 F=T1，T2,.。，Tn;(2)在 F 中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；(3)在集合 F 中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合 F 中；(4)重复（2)、（3)两步,当 F 中只剩下一棵二叉树时,这棵二叉树便是所要建立的哈夫曼树。给定权值 w=（1，3,5,7)来构造一棵哈夫曼树 给定一组叶结点权值，所构造的哈夫曼树树的形状可能不同，但带权路径长度值是相同的，一定是最
35、小的.15.哈夫曼编码 编码方法 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。具体构造方法如下：设需要编码的字符集合为d1,d2,，dn，各个字符在电文中出现的次数集合为 w1,w2，wn,以 d1,d2,dn 作为叶结点,以 w1,w2，,wn 作为各根结点到每个叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为 0，右分支为 1，则从根结点到每个叶结点所经过的分支对应的 0 和 1 组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。上面构造的哈夫曼树对应
36、的哈夫曼编码如下：1：000 3:001 5：01 7：1 9 4 1 7 5 3 16 9 4 1 7 5 3(c)(d)1 3 5 7 4 5 7 1 3(a)(b)第八章查找 1。顺序表的查找 顺序查找：是一种最简单的查找方法。它的查找过程是从表的一端开始,顺序扫描线性表,依次将扫描到的关键字和给定值 k 相比较，若当前扫描到的关键字与 k 相等，则查找成功；若扫描结束后，仍未找到关键字等于 k 的记录,则查找失败。顺序查找的算法描述如下(在顺序表 R0。.n-1中查找关键字为 k 的记录，成功时返回找到的记录位置,失败时返回1）:intSeqSearch(SeqListR,intn,K
37、eyType k）int i=0；while（ik)/*继续在 Rlow.。mid1中查找*/high=mid-1；else low=mid+1；/*继续在 Rmid+1.。high中查找/return 1;3。哈希函数的构造方法 构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在 n 个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。构造方法：1。直接定址法 直接定址法是以关键字 k 本身或关键字加上某个数值常量 c 作为哈希地址的方法。直接定址法的哈希函数 h（k)为:h（k）=k+c (c0）这种哈希函数计算简单,并且不可能有冲突发生。当关键字的分布基本连续时，
38、可用直接定址法的哈希函数;否则,若关键字分布不连续将造成内存单元的大量浪费 2。除留余数法 除留余数法是用关键字 k 除以某个不大于哈希表长度 m 的数 p 所得的余数作为哈希地址的方法.除留余数法的哈希函数 h(k)为：h（k）=k mod p (mod 为求余运算,pm）p 最好取小于 m 的质数（素数）。3.数字分析法 该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。例如,有学生的生日数据如下：76.07.12 75.04.21 76。02。15 .。.经分析，第一位，第二位，第三位重复的可能性大，
39、取这三位造成冲突的机会增加,所以尽量不取前三位，取后三位比较好。第九章排序 1.直接插入排序 插入排序的基本思想是把一个记录插入到一个有序的文件中，在插入后使该文件仍然是有序的。设有一个包含 n 个记录R(1)，R(2)，,R(n）的源文件。假设有一个子文件,它是由源文件的第一个记录 R（1）构成的，显然,这个只有一个记录的源文件是有序的。然后，把源文件的第二个记录 R（2)按记录关键值的有序性插入到只包含一个记录 R(1)的子文件中.直接插入排序的算法 INSORT(R）Intan；int i,j,temp;for（i=1;i=n-1;i+)/从外层处理 n-1 次循环 temp=ai;/把
40、当前待排序的首元素保存起来 for(j=i1；j=0；j-)/内层每次插入的过程 aia0i-1 if(ajtemp）aj+1=aj；else Break;aj+1=temp;2。冒泡排序过程 冒泡排序是一种简单常用的排序方法。其排序思想是:通过相邻记录关键字间的比较和交换，使关键字最小的记录像气泡一样逐渐上浮。比较可以采用不同的方法,本算法是从最下面的记录开始，对两个相邻的关键字进行比较并且使关键字较小的记录换至关键字较大的记录之上,使得经过一次冒泡后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字最小的记录,把它换到第二个位置上.依次类推,一直到所有记录都有序为止.一般情况下,
41、记录数为 n，需要做 n1 次冒泡。冒泡排序算法 Bibblesort（R)Intan;int i,j,temp;for(i=1；i=n1；i+)/从外层处理 n-1 次循环 for(j=n1;j=i；j-)if(ajaj1）temp=aj;aj=aj1;aj1=temp；3。.简单选择排序过程 冒泡算法中每次通过若干次交换把待排序序列中最小的数据放在已排序序列的最后,简单选择排序主要是减少排序过程中的交换次数，只是简单的记录下当前待排序序列中最小数据的位置，最后通过 1 次交换来完成当次排序.具体步骤是:（1）在未排序的文件中找出关键字值最小的记录，然后把这个记录与第一个位置上的记录对换,使得关键字值最小的记录定位；（2)在余下的记录中找出关键字值最小的记录,并把它与第二个位置上的记录进行对调，使关键字值次小的记录在已排序的序列中定位;（3）依次类推，一直到所有的记录逐个在排序的序列中定位 简单选择排序算法 Bibblesort（R)Int an；int i,j,k,min；for（i=1;i=n1；i+）k=i1;min=ak;for(j=k+1;jn；j+）if（ajak）K=j;if(ak！=ai-1)ak=ai-1；