数据结构基础知识要点.doc

第1章 数据结构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表示,n0。2.线性结构的基本特征为: (1) 集合中必存在唯一的一个“第一元素”；(2) 集合中必存在唯一的一个“最后元素”；(3) 除最后一个元素之外，均有唯一的后继(后件)；(4) 除第一个元素之外，均有唯一的前驱(前件)。3.定义顺序表线性表逻辑结构顺序表存储结构typedefstructElemType dataMAXCOUNT; /定义存放顺序表元素的数组int length; /length为存放线性表的实际长度SqList; /顺序表类型4.顺序表上的运算及其实现(1). 建立顺序表CreateList创建一个空的顺序表，要完成线性表所需空间的分配和其他初始化设置。(2) 求线性表的长度ListLength(3) 输出线性表DispList(4) 在线性表中的指定位置插入一个元素InsertElem(5) 根据键值查找指定元素FindElemByNum(6) 获取指定位置的元素信息GetElem(7) 删除指定位置的元素DelElem(8) 释放线性表DestroyList5.线性表的链式存储单链表（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.循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是空,而是指向表头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到链表中其他结点。带头结点的单向循环链表和双向循环链表如下图第三章栈和队列1.栈的定义及基本运算栈是限定只能在表尾进行插入和删除的线性表，并将表尾称为栈顶，表头称为栈底。栈的基本运算如下：（1）判栈空IsEmpty(S). 若栈为空则返回“真“，否则返回”假“；（2）入栈操作（压栈）Push(S,x) 将新元素压入栈中，使其成为栈顶元素；（3）出栈操作（弹栈）Pop(S, x) 若栈不空则返回栈顶元素，并从栈中删除栈顶元素，否则返回NULL；（4）取栈顶元素GetTop(s,x) 若栈不空则返回栈顶元素，否则返回NULL；（5）置空栈Clear(s) 将当前栈设定为空栈；2.顺序栈的存储结构及算法实现1顺序栈顺序栈利用一组连续的存储单元存放从栈底到栈顶的诸元素。typedefstructint *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+;queuer=in; 出队算法:出队首先要判断队列中是否有元素，即R是否等于F，R=F可能出现在初态，也可能出现在出队、进队的动态变化中。DELQUEUE(queue，r，f，out)/* 在queue队列中退出一个元素到out，f和r分别是队首和队尾的标志 */ if(f=r) printf(队空); elseout=queue+f;5.链队的存储结构及其运算当队空时，Front=NULL；Rear=NULL；所谓队满，是指在可利用的空间表中，所有的结点被取完，即AV=NULL时，才表示队满。根据队列的操作特点，进队和退队分别在表的两端进行，具体表现为“先进先出”。从链队的结构可看出，进队的基本操作步骤为(设进队结点的地址为x)：Rear-next=x；x-next=NULL；Rear=x；第四章串1.串的基本概念串结构的形式化定义为：String=(D，R)其中，D= aiaicharacter，i=1，2n，n0，R=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）：把串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的父结点(1ilchild); /*先序递归遍历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=NULLbt-rchild=NULL;returnbt; 建立一棵空的不带头结点的二叉树BiTree Initiate() /*初始建立一棵空的不带头结点的二叉树*/ BiTNode *bt;bt=NULL;returnbt;在主函数中，可以通过如下方式调用Initiate函数：main ( )BiTree t ; /*定义根结点指针变量*/t =Initiate();voidDispBiTNode(BiTree T)if (T != NULL)printf(%c, T-data);if (T-lchild != NULL | T-rchild != NULL)printf();DispBiTNode(T-lchild);printf(,);DispBiTNode(T-rchild);printf();* void DispBTree(*bt)算法：对于非空二叉树bt：先输出其元素值当其有左孩子或右孩子时输出（递归输出左子树输出，递归输出右子树输出）(2)查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点的指针。(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个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度。记为： WPLWkLk其中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)来构造一棵哈夫曼树给定一组叶结点权值，所构造的哈夫曼树树的形状可能不同，但带权路径长度值是相同的，一定是最小的。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的记录,则查找失败。顺序查找的算法描述如下(在顺序表R0.n-1中查找关键字为k的记录,成功时返回找到的记录位置,失败时返回-1)：intSeqSearch(SeqListR,intn,KeyType k) int i=0;while (i=n) return -1;elsereturn i; 2.有序表的查找以有序表表示静态查找表时，Search函数可用折半查找来实现。折半查找也成为二分查找。定义折半查找（Binary Search）的查找过程是:要求线性表中的结点必须己按关键字值的递增或递减顺序排列。它首先用要查找的关键字k与中间位置的结点的关键字相比较,这个中间结点把线性表分成了两个子表,若比较结果相等则查找完成;若不相等,再根据k与该中间结点关键字的比较大小确定下一步查找哪个子表,这样递归进行下去,直到找到满足条件的结点或者该线性表中没有这样的结点。其算法如下(在有序表R0.n-1中进行二分查找,成功时返回记录的位置,失败时返回-1)： intBinSearch(SeqListR,intn,KeyType k) int low=0,high=n-1,mid; while (lowk) /*继续在Rlow.mid-1中查找*/ high=mid-1; else low=mid+1; /*继续在Rmid+1.high中查找*/ return -1; 3.哈希函数的构造方法构造哈希函数的目标是使得到的哈希地址尽可能均匀地分布在n个连续内存单元地址上,同时使计算过程尽可能简单以达到尽可能高的时间效率。构造方法： 1.直接定址法 直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。直接定址法的哈希函数h(k)为： h(k)=k+c (c0)这种哈希函数计算简单,并且不可能有冲突发生。当关键字的分布基本连续时,可用直接定址法的哈希函数；否则,若关键字分布不连续将造成内存单元的大量浪费2.除留余数法除留余数法是用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：h(k)=k mod p (mod为求余运算,pm) p最好取小于m的质数(素数)。3.数字分析法该方法是提取关键字中取值较均匀的数字位作为哈希地址的方法。它适合于所有关键字值都已知的情况,并需要对关键字中每一位的取值分布情况进行分析。例如，有学生的生日数据如下：76.07.1275.04.2176.02.15.经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增加，所以尽量不取前三位，取后三位比较好。第九章排序1.直接插入排