数据结构基础知识要点

数据结构基础知识要点 ------------------------------------------------------------------------------------------------ 数据结构基础知识要点 第一章 数据结构 1(定义 数据结构是计算机存储、组织数据的方式。数据结构是抽象数据类型的物理实现。 2.数据结构包括如下几个方面: (1) 数据元素之间的逻辑关系,即数据的逻辑结构。 (2) 数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物理结构。 (3) 施加在该数据上的操作,即数据的运算。 2.逻辑结构类型 (1) 集合结构。交通工具的集合，动物的集合 (2) 线性结构。一对一，综合素质测评产生的学生排名 (3) 树形结构。一对多，单位的组织结构图，族谱 (4) 图形结构。多对多，生产、、网络建设图等 3.存储结构类型 (1) 顺序存储。数组 (2) 链式存储方法。链表 (3) 索引存储方法 (4) 散列存储方法 4.算法 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 通常把具体存储结构上的操作实现步骤或过程称为算法。 C语言里通常表现为解决问的步骤 程序 = 算法(加工数据) + 数据结构(数据的存储和组织) 5.算法的五个特征 (1) 有穷性:在有穷步之后结束。 (2) 确定性:无二义性。 (3) 可行性:可通过基本运算有限次执行来实现。 (4) 有输入:可有零个或多个。 (5) 有输出:至少有一个输出。 6.算法分析 (1)时间复杂度:(算法的工作量大小)通常把算法中包含基本运算次数的多少称为算法的时间复杂度,也就是说,一个算法的时间复杂度是指该算法的基本运算次数。 算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作: T(n)=O(f(n)) (2) 空间复杂度: 实现算法所需的存储单元多少 1.线性表的基本概念 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表示,n?0。 2.线性结构的基本特征为: (1) 集合中必存在唯一的一个“第一元素”; —————————————————————————————————————— ------------------------------------------------------------------------------------------------ (2) 集合中必存在唯一的一个“最后元素”; (3) 除最后一个元素之外，均有唯一的后继(后件); (4) 除第一个元素之外，均有唯一的前驱(前件)。 3.定义顺序表 typedefstruct { ElemType data[MAXCOUNT]; //定义存放顺序表元素的数组 int length; //length为存放线性表的实际长度 }SqList; //顺序表类型 4.顺序表上的运算及其实现 (1). 建立顺序表CreateList 创建一个空的顺序表，要完成线性表所需空间的分配和其他初始化设置。 (2) 求线性表的长度ListLength (3) 输出线性表DispList (4) 在线性表中的指定位置插入一个元素InsertElem (5) 根据键值查找指定元素FindElemByNum (6) 获取指定位置的元素信息GetElem (7) 删除指定位置的元素DelElem (8) 释放线性表DestroyList 5.线性表的链式存储——单链表(data域和指针域next) 由于顺序表中的每个元素至多只有一个前驱元素和一个后继元—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 素, 即数据元素之间是一对一的逻辑关系,所以当进行链式存储时,一 种最简单也最常用的方法是: 在每个结点中除包含有数据域外,只设置一个指针域,用以指向其 后继结点,这样构成的链接表称为线性单向链接表,简称单链表; 7.单链表的定义 LinkList类型的定义如下: typedefstructLNode /*定义单链表结点类型*/ { ElemType data; structLNode *next; /*指向后继结点*/ }LinkList; 第二章线性表 8.顺序表上的运算及其实现 1、创建单链表LinkList *CreateList(); 2、初始化单链表void InitList(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、采用头插法向单链表中插入一个元素 intInsertElem_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前 驱) 对于双链表,采用类似于单链表的类型定义,其DLinkList类型的定 义如下: typedefstructDNode /*定义双链表结点类型*/ { ElemType data; structDNode *prior; /*指向前驱结点*/ structDNode *next; /*指向后继结点*/ } DLinkList 在双链表中p所指的结点之后插入一个*s结点。 其操作语句描述为: s->next=p->next; /*将s插入到p之后*/ —————————————————————————————————————— ------------------------------------------------------------------------------------------------ p->next->prior=s; s->prior=p; p->next=s; 归纳起来,删除双链表L中*p结点的后续结点。其操作语句描述为: p->next=q->next; q->next->prior=p; 10.循环链表 循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空,而是指向表头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到链表中其他结 (a)循环单链表 (b)循环双链表 第三章栈和队列 1.栈的定义及基本运算 栈是限定只能在表尾进行插入和删除的线性表，并将表尾称为栈顶，表头称为栈底。 栈的基本运算如下: (1)判栈空IsEmpty(S). 若栈为空则返回“真“，否则返回”假“; (2)入栈操作(压栈)Push(S,x) 将新元素压入栈中，使其成为栈顶元素; (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(Stack 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) { top->next=NULL; } 调用此函数之前，在主调函数中(例如main( ))说明一个指针变量后，先为它申请分配一个结点，然后调用初始化函数。 2(入栈操作 链栈入栈操作的含义是:将一个元素推入指定的链栈中。对该操作应设置两个参数，即在参数中指定一个链栈及入栈的元素。假设指定的链栈top，入栈元素x其类型为 ElemType，入栈操作取名为push，则该操作可表示为: viod Push(Lsnode *top，ElemType x) 操作的功能为在由top指向的链栈中插入元素x，使x成为栈顶元素。 3. 出栈操作 链栈出栈操作的含义是:从链栈中弹出栈顶结点并返回该结点中—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 的元素值。对该操作应设置一个参数，即在参数中指定一个链栈。假设指定的链栈top,出栈操作取名为pop，则该操作可表示为: ElemTypePop(Lsnode *top) 操作的功能为从由top指向的链栈中弹出栈顶结点并返回该结点中的元素值。 4.队列的基本操作 进队算法: 根据队列的结构，若队尾指针不在队的最大长度上，则首先队尾指针加,，元素进队，否则就是队满，无法进队。 ADDQUEUE(queue，r，f，in) /* 在queue队列中进一个元素in，f和r分别是队首和队尾的标志 */ { if(r==n) { printf("队满"); } else { r++; queue[r]=in; } —————————————————————————————————————— ------------------------------------------------------------------------------------------------ } 出队算法: 出队首先要判断队列中是否有元素，即R是否等于F，R=F可能出现在初态，也可能出现在出队、进队的动态变化中。 DELQUEUE(queue，r，f，out) /* 在queue队列中退出一个元素到out，f和r分别是队首和队尾的标志 */ { if(f==r) { printf("队空"); } else out=queue[++f]; } 5.链队的存储结构及其运算 当队空时，Front=NULL;Rear=NULL;所谓队满，是指在可利用的空间表中，所有的结点被取完，即AV=NULL时，才表示队满。根据队列的操作特点，进队和退队分别在表的两端进行，具体表现为“先进先出”。从链队的结构可看出，进队的基本操作步骤为(设进队结点的地址为x): Rear->next=x; —————————————————————————————————————— ------------------------------------------------------------------------------------------------ x->next=NULL; Rear=x; 第四章串 1.串的基本概念 串结构的形式化定义为:String=(D，R) 其中，D={ ai,ai?character，i=1，2„n，n?0}，R={< a i-1 ai> ,a i-1，ai?D，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):把串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)串的联接 (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.串的块链存储表示 顺序串上的插入和删除操作运算需要移动大量的字符。因此，可以采用单链表方式来存储串值，串的这种链式存储结构简称为链串。但在利用链表存储串值时，每个结点既可以存放一个字符，也可以存放多个字符，即存在一个“结点大小”的问题。结点的大小是指结点的数据域可存放字符的个数。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 第六章树和二叉树 1.树的表示 (1)树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象 (2)文氏图表示法。使用集合以及集合的包含关系描述树结构。 文氏图表示法 (3)凹入表示法。使用线段的伸缩描述树结构。 (4)括号表示法。将树的根结点写在括号的左边, 除根结点之外的其余结点写在括号中并用逗号 间隔来描述树结构。 2.树的基本术语 1. 结点的度与树的度: 凹入表示法 树中某个结点的子树的个数称为该结点的度。 树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。 2. 分支结点与叶结点: 度不为零的结点称为非终端结点,又叫分支结点。 度为零的结点称为终端结点或叶结点。 在分支结点中,每个结点的分支数就是该结点的度。 3. 路径与路径长度: 如果一棵树中的一串结点n1,n2,„,nk,有如下关系:结点ni是ni+1的父结点(1?i<k) ,就把n1,n2,„,nk称为一条由n1至nk的路径，这条路径的长度是k-1。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 4. 孩子结点、双亲结点和兄弟结点: 在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。 相应地,该结点被称作孩子结点的双亲结点(或父母结点)。 具有同一双亲的孩子结点互为兄弟结点。 进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点 5.结点的层次和树的高度: 树中的每个结点都处在一定的层次上。结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。 树中结点的最大层次称为树的高度(或树的深度)。 6.有序树和无序树: 若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则 称为有序树,否则称为无序树。 7.森林:n(n,0)个互不相交的树的集合称为森林。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给n棵独立的树加上一个结点,并把这n棵树作为该结点的子树,则森林就变成了树。 3.树的性质 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 性质1 树中的结点数等于所有结点的度数加1。 性质2 度为m的树中第i层上至多有mi-1个结点,这里应有i?1。 性质3 高度为h的m次树至多有个结点。 性质4 具有n个结点的m次树的最小高度为?logm(n(m-1)+1)?。 4.树的特点: ?树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 ?树中所有结点可以有零个或多个后继结点。 5.树的基本运算 树的运算主要分为三大类: 第一类,寻找满足某种特定关系的结点,如寻找当前结点的双亲结点等; 第二类,插入或删除某个结点,如在树的当前结点上插入一个新结点或删除当前结点的第i个孩子结点等; 第三类,遍历树中每个结点,这里着重介绍。 树的遍历运算是指按某种方式访问树中的每一个结点且每一个结点只被访问一次。树的遍历运算的算法主要有先根遍历和后根遍历两种。注意,下面的先根遍历和后根遍历算法都是递归的。 1. 先根遍历 先根遍历过程为: (1)访问根结点; (2)按照从左到右的次序先根遍历根结点的每一棵子树。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 2. 后根遍历 后根遍历过程为: (1) 按照从左到右的次序后根遍历根结点的每一棵子树; (2) 访问根结点。 6.二叉树的定义 二叉树(Binary Tree)是n(n?0)个结点的有限集合。它或为空树(n,0)，或为非空树;对于非空树有: (1) 有一个特定的称之为根的结点; (2) 根结点以外的其余结点分别由两棵互不相交的称之为左子树和右子树的二叉树组成。 这个递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成的。由于左、右子树也是二叉树，则由二叉树的定义，它们也可以为空。由此，二叉树可以有五种基本形态 7.二叉树的重要性质 性质1 二叉树第i(i?1)层上至多有2i-1个结点。 性质2 深度为k(k?1)的二叉树至多有2k,1个结点。 性质3 在任意二叉树中，若叶子结点(即度为零的结点)个数为n0，度为1的结点个数n1，度为2的结点个数为n2，那么n0=n2+1。 性质4 具有n个(n,0)结点的完全二叉树的高度为?log2n+1?或?log2n?+1。 性质5 若对有n(1?i?n)个结点的完全二叉树进行顺序编号，那么，对于编号为i(i?1)的结点: 当i=1时，该结点为根，它无双亲—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 结点; 当i,1时，该结点的双亲结点编号为?i/2 ?; 若2i?n，则有编号为2i的左孩子，否则没有左孩子; 若2i+1?n，则有编号为2i+1的右孩子，否则没有右孩子。 满二叉树:深度为k且含有2k,1个结点的二叉树为满二叉树，这种树的特点是每层上的结点数都是最大结点数 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。如图所示，(a)图就是一棵满二叉树，(b)图则不是满二叉树，因为，虽然其所有结点要么是含有左右子树的分支结点，要么是叶子结点，但由于其叶子未在同一层上，故不是满二叉树 完全二叉树:深度为k，含有n个结点的二叉树，当且仅当每个结点的编号与相应满二叉树结点顺序号从1到n相对应时，则称此二叉树为完全二叉树 显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。如图所示(a)为一棵完全二叉树，(b)不是完全二叉树。 8.二叉树的顺序存储结构 二叉树的顺序存储结构中结点的存放次序是:对该树中每个结点进行编号,其编号从小到大的顺序就是结点存放在连续存储单元的先后次序。若把二叉树存储到一维数组中,则该编号就是下标值加1(注意,C/C++语言中数组的起始下标为0)。树中各结点的编号与等高度的完全二叉树中对应位置上结点的编号相同 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 9.二叉树的链式存储结构 data表示值域,用于存储对应的数据元素,lchild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点(即左、右子树的根结点)的存储位置 下图(a)给出一棵二叉树的二叉链表存储表示。二叉链表也可以带头结点的方式存放，如图(b)所示。 二叉链表存储表示可描述为: typedefstructbitnode { datatype data; structbitnode *lchild;*rchild;/*左右孩子指针域*/ }BiTNode, *BiTree; 定义指针变量，用来存放根结点地址，通常用该指针标识一个二叉树: BiTree t; 10.二叉树遍历的概念 二叉树的遍历是指按照一定次序访问树中所有结点,并且每个结点仅被访问一次的过程。它是最基本的运算,是二叉树中所有其他运算的基础。 1.先序遍历(DLR) 先序遍历二叉树的过程是: (1) 访问根结点; —————————————————————————————————————— ------------------------------------------------------------------------------------------------ (2) 先序遍历左子树; (3) 先序遍历右子树。 voidPreOrder(BiTreebt) { if (bt==NULL) return; /*递归调用的结束条件 */ Visit(bt) ; /*访问根结点*/ PreOrder(bt?>lchild); /*先序递归遍历bt的左子树*/ PreOrder(bt?>rchild);/*先序递归遍历bt的右子树*/ } 2.中序遍历(LDR) 中序遍历二叉树的过程是: (1) 中序遍历左子树; (2) 访问根结点; (3) 中序遍历右子树。 voidInOrder(BiTreebt) { if (bt==NULL) return; /*递归调用的结束条件*/ InOrder(bt?>lchild); /*中序递归遍历bt的左子树*/ Visit(bt); /*访问根结点*/ InOrder(bt?>rchild); /*中序递归遍历bt的右子树*/ } —————————————————————————————————————— ------------------------------------------------------------------------------------------------ 3.后序遍历(LRD) 后序遍历二叉树的过程是: (1) 后序遍历左子树; (2) 后序遍历右子树; (3) 访问根结点。 voidPostOrder(BiTreebt) { if (bt==NULL) return; /*递归调用的结束条件*/ PostOrder(bt?>lchild);/*后序递归遍历bt的左子树*/ PostOrder(bt?>rchild);/*后序递归遍历bt的右子树*/ Visite(bt); /*访问根结点*/ } 4.层次遍历 其过程是: 若二叉树非空(假设其高度为h)，则: (1)访问根结点(第1层); (2)从左到右访问第2层的所有结点; (3)从左到右访问第3层的所有结点、„、第h层的所有结点。 11.二叉树基本运算概述 (1)创建二叉树CreateBTNode(*b,*str):根据二叉树括号表示法的字符串*str生成对应的链式 存储结构。 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ ** Initiate(bt):建立一棵空的二叉树bt，并返回bt。 二叉树带不带头结点，可根据具体需要而定。 建立一棵空的带头结点的二叉树 BiTree Initiate ()/*建立一棵空的带头结点的二叉树*/ { BiTNode *bt; bt=(BiTNode *)malloc(sizeof(BiTNode)); bt?>lchild=NULL bt?>rchild=NULL; returnbt; } 建立一棵空的不带头结点的二叉树 BiTree Initiate() /*初始建立一棵空的不带头结点的二叉树*/ { BiTNode *bt; bt=NULL; returnbt; } 在主函数中，可以通过如下方式调用Initiate函数: main ( ) { —————————————————————————————————————— ------------------------------------------------------------------------------------------------ BiTree t ; /*定义根结点指针变量*/ t =Initiate(); „„ voidDispBiTNode(BiTree T) } { ** void DispBTree(*bt) if (T != NULL) 算法:对于非空二叉树bt: { 先输出其元素值 printf("%c", T->data); 当其有左孩子或右孩子时 if (T->lchild != NULL || 输出( T->rchild != NULL) 递归输出左子树 { 输出， printf("("); 递归输出右子树 DispBiTNode(T->lchild); 输出) printf(","); DispBiTNode(T->rchild); (2)查找结点FindNode(*b,x):在二叉树b中寻找data域值为x的结点,并返回指向该结点的 printf(")"); 指针。 } (3)找孩子结点LchildNode(p)和RchildNode(p):分别求二叉树中结点*p的左孩子结点和右 孩子结点 (4)求高度BTNodeDepth(*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，试恢复该二叉树。 13.哈夫曼树的概念 设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。记为: WPL,Wk?Lk 其中Wk为第k个叶结点的权值，Lk为第k个叶结点的路径长度。 具有最小带权路径长度的二叉树称为哈夫曼树。 14.构造哈夫曼树 根据哈夫曼树的定义,一棵二叉树要使其WPL值最小,必须使权值越大的叶子结点越靠近根结点,而权值越小的叶子结点越远离根结点。那么如何构造一棵哈夫曼树呢?其方法如下: (1)由给定的n个权值{W1,W2,...,Wn}构造n棵只有一个叶子结点的二叉树,从而得到一个二叉树的集合F={T1,T2,...,Tn}; (2)在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树,这棵新的二叉树根结点的权值为其左、右子树根结点权值之和; (3)在集合F中删除作为左、右子树的两棵二叉树,并将新建立的二叉树加入到集合F中; (4)重复(2)、(3)两步,当F中只剩下一棵二叉树时, 给定权值w=(1,3,5,7) 来构造一棵哈夫曼树 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ (b) (d) (a) (c) 给定一组叶结点权值，所构造的哈夫曼树树的形状可能不同，但带权路径长度值是相同的， 一定是最小的。 15.哈夫曼编码 编码方法 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长， 所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。 具体构造方法如下: 设需要编码的字符集合为{d1,d2,„,dn},各个字符在电文中出现的次数集合为 {w1,w2,„,wn},以d1,d2,„,dn作为叶结点,以w1,w2,„,wn作为各根结点到每个叶结点的权值构造一棵二叉树,规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。 上面构造的哈夫曼树对应的哈夫曼编码如下: 1:000 3:001 5:01 7:1 第八章查找 1.顺序表的查找 顺序查找:是一种最简单的查找方法。它的查找过程是从表的一—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 端开始,顺序扫描线性表,依次将扫描到的关键字和给定值k相比较,若当前扫描到的关键字与k相等,则查找成功;若扫描结束后,仍未找到关键字等于k的记录,则查找失败。 顺序查找的算法描述如下(在顺序表R[0..n-1]中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1): intSeqSearch(SeqListR,intn,KeyType k) { int i=0; while (i<n && R[i].key!=k) i++; /*从表头往后找*/ if (i>=n) return -1; else return i; } 2.有序表的查找 以有序表表示静态查找表时，Search函数可用折半查找来实现。折半查找也成为二分查找。 定义 折半查找(Binary Search)的查找过程是:要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 找到满足条件的结点或者该线性表中没有这样的结点。 其算法如下(在有序表R[0..n-1]中进行二分查找,成功时返回记录的位置,失败时返回-1): ? intBinSearch(SeqListR,intn,KeyType k) ? { ? int low=0,high=n-1,mid; ? while (low<=high) ? { mid=(low+high)/2; ? if (R[mid].key==k) /*查找成功返回*/ ? return mid; ? if (R[mid].key>k) /*继续在R[low..mid-1]中查找*/ ? high=mid-1; ? else ? low=mid+1; /*继续在R[mid+1..high]中查找*/ ? } ? return -1; } 3.哈希函数的构造方法 构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址上,同时使计算过程尽可能简单以达到尽可能高—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 的时间效率。 构造方法: 1.直接定址法 ? 直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。 直接定址法的哈希函数h(k)为: ? h(k)=k+c (c?0) 这种哈希函数计算简单,并且不可能有冲突发生。当关键字的分布基本连续时,可用直接定址法的哈希函数;否则,若关键字分布不连续将造成内存单元的大量浪费 2.除留余数法 除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为: h(k)=k mod p (mod为求余运算,p?m) p最好取小于m的质数(素数)。 3.数字分析法 该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。例如，有学生的生日数据如下: 76.07.12 75.04.21 76.02.15 —————————————————————————————————————— ------------------------------------------------------------------------------------------------ ... 经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。 第九章排序 1.直接插入排序 插入排序的基本思想是把一个记录插入到一个有序的文件中，在插入后使该文件仍然是有序的。设有一个包含n个记录{R(1), R(2), „, R(n)}的源文件。假设有一个子文件，它是由源 文件的第一个记录R(1)构成的，显然，这个只有一个记录的源文件是有序的。然后，把源文件的第二个记录R(2)按记录关键值的有序性插入到只包含一个记录R(1)的子文件中。 直接插入排序的算法 INSORT(R) { Inta[n]; int i, j, temp; for (i=1; i<=n-1; i++) // 从外层处理n-1次循环 { temp = a[i];//把当前待排序的首元素保存起来 for (j=i-1; j>=0;j--)//内层每次插入的过程 a[i]~a[0~i-1] { if(a[j]>temp) { —————————————————————————————————————— ------------------------------------------------------------------------------------------------ a[j+1]=a[j]; } else { Break; } } a[j+1] = temp; } } 2.冒泡排序过程 冒泡排序是一种简单常用的排序方法。其排序思想是:通过相邻记录关键字间的比较和交换，使关键字最小的记录像气泡一样逐渐上浮。 比较可以采用不同的方法，本算法是从最下面的记录开始，对两个相邻的关键字进行比较并且使关键字较小的记录换至关键字较大的记录之上，使得经过一次冒泡后，关键字最小的记录到达最上端，接着，再在剩下的记录中找关键字最小的记录，把它换到第二个位置上。依次类推，一直到所有记录都有序为止。 一般情况下，记录数为n，需要做n,1次冒泡。 冒泡排序算法 Bibblesort(R) —————————————————————————————————————— ------------------------------------------------------------------------------------------------ { Inta[n]; int i, j, temp; for (i=1; i<=n-1; i++) // 从外层处理n-1次循环 { for (j=n-1; j>=i;j--) if(a[j]<a[j-1]) { temp=a[j]; a[j]=a[j-1]; a[j-1]=temp; } } } 3..简单选择排序过程 冒泡算法中每次通过若干次交换把待排序序列中最小的数据放在已排序序列的最后，简单选择排序主要是减少排序过程中的交换次数，只是简单的记录下当前待排序序列中最小数据的位置，最后通过1次交换来完成当次排序。具体步骤是: (1) 在未排序的文件中找出关键字值最小的记录，然后把这个记录与第一个位置上的记录对换，使得关键字值最小的记录定位; (2) 在余下的记录中找出关键字值最小的记录，并把它与第二个—————————————————————————————————————— ------------------------------------------------------------------------------------------------ 位置上的记录进行对调，使关键字值次小的记录在已排序的序列中定位; (3) 依次类推，一直到所有的记录逐个在排序的序列中定位 简单选择排序算法 Bibblesort(R) { Int a[n]; int i, j,k,min; for (i=1; i<=n-1; i++) { k=i-1;min=a[k]; for (j=k+1; j<n;j++) if(a[j]<a[k]) { K=j; } } if(a[k]!=a[i-1]) { a[k]=a[i-1]; } } —————————————————————————————————————— ------------------------------------------------------------------------------------------------ ——————————————————————————————————————