数据结构,清华大学出版社,严蔚敏吴伟民编著

第一章 绪论1、 数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。2、 程序设计= 算法 +数据结构3、 解决问题方法的效率：l 跟数据的组织方式有关l 跟空间的利用效率有关l 跟算法的巧妙程度有关4、 数据：所有能输入到计算机中,且被计算机处理的符号的集合， 是计算机操作对象的总称； 是计算机处理的信息的某种特定的符号表示形式。 5、 数据元素：数据中的一个“个体”,数据结构中讨论的基本单位。 相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。6、 数据项: 相当于记录的“域”, 是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。7、 数据对象：性质相同的数据元素的集合. 例如: 所有运动员的记录集合8、 数据结构：是相互间存在某种关系的数据元素集合。9、 数据结构是带结构的数据元素的集合。10、 不同的关系构成不同的结构。11、 次序关系： |i=1,2,3,4,5,612、 对每种数据结构，主要讨论如下两方面的问题： 1） 数据的逻辑结构，数据结构的基本操作； 2） 数据的存储结构，数据结构基本操作的实现；13、 数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：指对数据结构的加工处理。14、 数据的存储结构 (物理结构)： 数据结构在计算机内存中的表示。数据结构基本操作的实现：基本操作在计算机上的实现（方法)。15、 数据结构的有关概念16、数据元素的4类的基本结构：集合； 线性结构：结构中数据元素之间存在一对一的关系； 树形结构：结构中数据元素之间存在一对多的关系； 图状结构或网状结构：结构中数据元素之间存在多对多的关系。17、 C语言的优点：C语言可以直接操作内存。18、 每个节点都由两部分组成：数据域和指针域。19、 链接存储结构特点：l 比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。l 逻辑上相邻的节点物理上不必相邻。l 插入、删除灵活(不必移动节点，只要改变节点中的指针)。20、 数据类型 是一个值的集合和定义在此集合上的一组操作的总称。21、 ADT 有两个重要特征:数据抽象和数据封装。22、 抽象数据类型 (Abstract Data Type 简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。23、 抽象数据类型有： 数据对象数据对象的定义、数据关系数据关系的定义、 基本操作基本操作的定义。24、 数据类型的定义和含义。定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。含义：将数据按一定次序与形式存放的结构。 24、算法空间复杂度S(n) 算法的存储量包括： 输入数据所占的空间； 程序本身所占的空间； 辅助变量所占的空间。25、 算法具有有穷性、确定性、可行性、输入和输出五大特性。26、 抽象数据类型具有数据抽象、数据封装的特点。27、 数据的储存结构分为：顺序存储结构和链式存储结构。第二章 线性表1、线性结构的特点：在数据元素中的非空有限集中。（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，集合中的每一个数据元素均只有一个前驱；（4）除最后一个外，集合中的每一个数据元素均只有一个后继。2、线性表(Linear List) ：一个线性表是n个数据元素的有限序列。3、线性表的顺序存储实现：typedef struct ElementType DataMAXSIZE; int Last; List; List L, *PtrL;4、初始化（建立空的顺序表）List *MakeEmpty( ) List *PtrL; PtrL = (List *)malloc( sizeof(List) ); PtrL-Last = -1; return PtrL;5、查找int Find( ElementType X, List *PtrL ) int i = 0; while( i Last & PtrL-Datai!= X ) i+; if (i PtrL-Last) return -1; /* 如果没找到，返回-1 */ else return i; /* 找到后返回的是存储位置 */6、插入算法void Insert( ElementType X, int i, List *PtrL ) int j; if ( PtrL-Last = MAXSIZE-1 ) /* 表空间已满，不能插入*/ printf(表满); return; if ( i PtrL-Last+2) /*检查插入位置的合法性*/ printf(位置不合法); return; for ( j = PtrL-Last; j = i-1; j- ) PtrL-Dataj+1 = PtrL-Dataj; /*将 ai an倒序向后移动*/ PtrL-Datai-1 = X; /*新元素插入*/ PtrL-Last+; /*Last仍指向最后元素*/ return; 7、删除算法void Delete( int i, List *PtrL ) int j; if( i PtrL-Last+1 ) /*检查空表及删除位置的合法性*/ printf (“不存在第%d个元素”, i ); return ; for ( j = i; j Last; j+ ) PtrL-Dataj-1 = PtrL-Dataj; /*将 ai+1 an顺序向前移动*/ PtrL-Last-; /*Last仍指向最后元素*/ return; 8、求表长int Length ( List *PtrL ) List *p = PtrL; /* p指向表的第一个结点*/ int j = 0; while ( p ) p = p-Next; j+; /* 当前p指向的是第 j 个结点*/ return j;9、查找（1）按序号查找: FindKth; List *FindKth( int K, List *PtrL ) List *p = PtrL; int i = 1; while (p !=NULL & i Next; i+; if ( i = K ) return p; /* 找到第K个，返回指针 */ else return NULL; /* 否则返回空 */（2）按值查找: FindList *Find( ElementType X, List *PtrL ) List *p = PtrL; while ( p!=NULL & p-Data != X ) p = p-Next; return p;10、插入（在链表的第 i-1(1in+1)个结点后插入一个值为X的新结点)List *Insert( ElementType X, int i, List *PtrL ) List *p, *s; if ( i = 1 ) /* 新结点插入在表头 */ s = (List *)malloc(sizeof(List); /*申请、填装结点*/ s-Data = X; s-Next = PtrL; return s; /*返回新表头指针*/ p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */ if ( p = NULL ) /* 第i-1个不存在，不能插入 */ printf(参数i错); return NULL; else s = (List *)malloc(sizeof(List); /*申请、填装结点*/ s-Data = X; s-Next = p-Next; /*新结点插入在第i-1个结点的后面*/ p-Next = s; return PtrL; 11、删除（删除链表的第 i (1in)个位置上的结点)List *Delete( int i, List *PtrL ) List *p, *s; if ( i = 1 ) /* 若要删除的是表的第一个结点 */ s = PtrL; /*s指向第1个结点*/ PtrL = PtrL-Next; /*从链表中删除*/ free(s); /*释放被删除结点 */ return PtrL; p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/ if ( p = NULL ) printf(“第%d个结点不存在”, i-1); return NULL; else if ( p-Next = NULL ) printf(“第%d个结点不存在”, i); return NULL; else s = p-Next; /*s指向第i个结点*/ p-Next = s-Next; /*从链表中删除*/ free(s); /*释放被删除结点 */ return PtrL; 12、链表不具备的特点是 1 。 可随机访问任一节点 插入删除不须要移动元素 不必事先估计存储空间 所需空间与其长度成正比13、带头结点的单链表head为空的判定条件是 2 。 head=NULL head-next=NULLhead-next=head head!=NULL14、如果最常用的操作是取第i个结点及其前驱，则采用 4 存储方式最节省时间。 单链表 双链表 单循环链表 顺序表第三章 Chapter 3 栈(stacks)和队列（queues）1、 栈是限定仅能在表尾一端进行插入、删除操作的线性表。2、 栈的特点是“后进栈的元素先出栈”（last in, first out），故栈又称为后进先出表（LIFO）。3、 一个栈是一些元素的线形列表，其中元素的插入和删除均在表的同一端进行。插入和删除发生的一端称为栈顶（the top of the stack）。4、 第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。5、 连续栈(Contiguous Stack)的类型定义#define MaxStack 50Typedef struct datatype stackMaxStack; int top;Seqstack;Seqstack *s;6、 判断栈是否已满？viod Push(Seqstack *s, datatype x ) if (s-top=MaxStack-1) printf(“ overflow” ); else s- top+; s-stacks-top=x; 7、 判断栈是否为空？datatype pop(Seqstack *s ) if (s-topstacks-top); s-top-; 8、 返回栈顶元素的值，栈不发生变化。datatype top(Seqstack *s ) if (s-topstacks-top);9、 链栈（Linked Stack)的类型定义栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedef struct stacknode datatype datastruct stacknode *nextstacknode10、 链式栈的特点：链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操作。11、栈是限定仅能在表的一端进行插入、 删除操作的线性表。12、栈的元素具有后进先出的特点。13、栈顶元素的位置由栈顶指针的指示, 进栈、出栈操作要修改栈顶指针。14、抽象数据类型队列的定义：队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。15、队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。16、双端队列：就是限定插入和删除操作在表的两端进行的线性表。17、链队列结点定义：typedef struct Qnode QElemType data;struct QNode *next; QNode,*QueuPtr;18、 队列的顺序存储结构称为顺序队列，在队列的顺序存储结构中，除了用一组地址连续的储存单元依次存放从队头到队尾的元素之外，尚需要附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。19、 在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。20、栈的特点是 先进后出 ，队列的特点是 先进后出 。21、栈和队列的共同特点是只允许在端点处插入和删除元素 。22、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。（A）edcba （B）decba （C）dceab （D）abcde23、若已知一个栈的进栈序列是p1，p2，p3， ，pn 。其输出序列为1，2，3，n ，若p3=1，则p1为 C 。（A）可能是2（B）一定是2（C）不可能是2 （D）不可能是324、设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是 3 ，栈顶指针是 8 。5、4、3、2、1 2、1 2、3 3、4 1002H 1004H 1005H 1003H24、一个队列的入队序列是若1，2，3，4，则队列的输出序列是 B 。（A）4，3，2，1 （B）1，2，3，4（C）1，4，3，2 （D）3，2，4，125、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 B 。（A）1和5 （B）2和4 （C）4和2 （D）5和126、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？C、D、B、A、E C、D、E、B、A C、D、B、E、A第六章 树和二叉树1、树型结构是一类重要的非线性结构。2、树的定义：树是n(n=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：（1）有且仅有一个特定的称为根的结点；（2）当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，T3Tm，其中每个子集又是一棵树，并称其为根的子树。3、基本术语结点表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点叫该结点的兄弟(sibling)同一双亲的孩子树的度一棵树中最大的结点度数结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层深度(depth)树中结点的最大层次数森林(forest)m(m0)棵互不相交的树的集合 例题:4、二叉树是由n(n=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。二叉树可以是空集合，根可以有空的左子树或空的右子树。性质1: 在二叉树的第i层上至多有2i-1个结点(i=1)。性质2：深度为k的二叉树至多有2k1个结点（k=1)。性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0n21。性质4：具有n个结点的完全二叉树的深度为log2n1。性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n +1层，每层从左到右)，则对任一结点i（1=i1，则其双亲是结点i/2 。（2）如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。（3）如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。一棵深度为k且有2k-1个结点的二叉树称为满二叉树。如：5、二叉树的存储结构l 顺序存储结构define MAX-TREE-SIZE 100Typedef TelemType SqBiTree MAX-TREE-SIZE;SqBitree bt;缺点是有可能对存储空间造成极大的浪费。l 链式存储结构二叉链式存储结构typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild;BiTNode,*BiTree;三叉链表typedef struct node datatype data;struct node *lchild, *rchild, *parent;JD;6、遍历二叉树二叉树是由三个基本单元组成：根结点、左子树和右子树。若限定先左后右，则只有前三种情况，分别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历。（1）先序遍历算法若二叉树为空树，则空操作；否则，l 访问根结点；l 先序遍历左子树；l 先序遍历右子树。void PreOrder（BiTree bt）/*先序遍历二叉树bt*/if (bt=NULL) return; /*递归调用的结束条件*/ Visite（bt-data）; /*(1)访问结点的数据域*/ PreOrder（bt-lchild）; /*(2)先序递归遍历bt的左子树*/ PreOrder（bt-rchild）;/*(3)先序递归遍历bt的右子树*/例题：先序遍历序列：A B D Cvoid preorder(JD *bt) if(bt!=NULL) printf(%dt,bt-data); preorder(bt-lchild); preorder(bt-rchild); （2）中序遍历算法若二叉树为空树，则空操作；否则，l 先序遍历左子树；l 访问根结点；l 先序遍历右子树。void InOrder（BiTree bt）/*先序遍历二叉树bt*/if (bt=NULL) return; /*递归调用的结束条件*/ InOrder（bt-lchild）; /*(2)先序递归遍历bt的左子树*/ Visite（bt-data）; /*(1)访问结点的数据域*/ InOrder（bt-rchild）;/*(3)先序递归遍历bt的右子树*/例题：中序遍历序列：B D A C（3）后序遍历算法若二叉树为空树，则空操作；否则，l 先序遍历左子树；l 先序遍历右子树；l 访问根结点。void PostOrder（BiTree bt）/*后序遍历二叉树bt*/if (bt=NULL) return; /*递归调用的结束条件*/PostOrder（bt-lchild）;/*(1)后序递归遍历bt的左子树*/PostOrder（bt-rchild）; /*(2)后序递归遍历bt的右子树Visite（bt-data）; /*(3)访问结点的数据域*/例题：后序遍历序列： D B C A（4）层次遍历所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。层次遍历序列:1 2 3 4 5 67、例题：1、先序序列：A B C D E F G H K中序序列：B D C A E H G K F后序序列：D C B H K G F E K层次序列：A B E C F D G H K2、若先序遍历此二叉树，按访问结点的先后次序将结点排列起来，其先序序列为：-+a*b-cd/ef 按中序遍历，其中序序列为：a+b*c-d-e/f按后序遍历，其后序序列为：abcd-*+ef/ -8、（1）查询二叉树中某个结点Status Preorder (BiTree T, ElemType x, BiTree &p) / 若二叉树中存在和 x 相同的元素，则 p 指向该结点并/返回 OK,/ 否则返回 FALSEif (T) if (T-data= =x) p = T; return OK, else if (Preorder(T-lchild, x, p)） return OK; else (Preorder(T-rchild, x, p) return OK; /else/if else return FALSE;（2）计算二叉树中叶子结点的个数int CountLeaf (BiTree T)/返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0; if (!T-lchild & !T-rchild) return 1; else m = CountLeaf( T-lchild); n = CountLeaf( T-rchild); return (m+n); /else / CountLeaf（3）求二叉树的深度(后序遍历)int Depth (BiTree T ) / 返回二叉树的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval;（4）按先序遍历序列建立二叉树Status CreateBiTree (BiTree &T ) /按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T scanf (&ch); if ( ch= ) T=NULL; else if(!T=(BiTNode *)malloc(sizeof(BiTNode) exit (OVERFLOW); T-data=ch; /生成根结点CreateBiTree(T-lchild);/构造左子树 CreateBiTree(T-rchild);/构造右子树Return OK; /CreateBiTree9、遍历二叉树的非递归算法（1）先序遍历二叉树的非递归算法void inorder(JD *r)/先序遍历二叉树非递归算法/ int i=0; JD *p,*sM; p=r; do while(p!=NULL) printf(%dt,p-data); if (p-rc!=NULL) si+=p-rc; p=p-lc; if ( i 0) p=s-i;while( i0 | p!=NULL); （2）中序遍历二叉树的非递归算法void inorder(JD *r)/先序遍历二叉树非递归算法/ int i=0; JD *p,*sM; p=r; do while(p!=NULL) si+=p; p=p-lc; if (i0) p=s-i; printf(%dt,p-data); p=p-lc; if ( i 0) p=s-i;while( i0 | p!=NULL); （3）后序遍历二叉树的非递归算法void inorder(JD *r)/先序遍历二叉树非递归算法/ int s2M,b,i=0; JD *p,*s1M; p=r; do while(p!=NULL) s1i-1=p;s2i+=0;p=p-lc; while (i0 & (s2i-1=1) p=s1-i; printf(“%dt”,p-data ); if (i0) p=s-i; printf(%dt,p-data); p=p-lc; if ( i 0) s2i-1=1; p=s1i-1; p=p-rc; while( i0); 11、 线索二叉树：以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能在结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域;lchildLtag dataRtagrchildLtag=0 ，lchild 域指示结点的左孩子；Ltag=1， lchild 域指示结点的前驱。Rtag=0，rchild 域指示结点的右孩子；Rtag=1，rchild 域指示结点的后驱。以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索，加上线索的二叉树称之为线索二叉树。（1）先序线索二叉树（2）中序线索二叉树（3）后序线索二叉树12、 树的存储结构双亲表示法#define MAX_TREE_SIZE 100typedef struct PTNode /结点结构ElemType data;int parent; / 双亲位置域 PTNode; typedef struct /树结构PTNode nodesMAX_TREE_SIZE;int r, n; / 根结点的位置和结点个数 PTree;孩子表示法带双亲的孩子链表孩子兄弟表示法链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。typedef struct node datatype data; struct node *fch, *nsib;JD;13、树和森林与二叉树的转换加线：在兄弟之间加一连线 。抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系，旋转：以树的根结点为轴心，将整树顺时针转45。13、 将二叉树转换成树l 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来.l 抹线：抹掉原二叉树中双亲与右孩子之间的连线l 调整：将结点按层次排列，形成树结构14、森林转换二叉树（1）将各棵树分别转换成二叉树.（2）将每棵树的根结点用线相连.（3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构14、 二叉树转换成森林抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树.还原：将孤立的二叉树还原成15、 树和森林的遍历树的遍历两种次序遍历树的方法：一种是先根（次序）遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。森林的遍历先序遍历：A B C D E F G H I J中序遍历：B C D A F E H J I G16、 赫夫曼树及其应用例题： w=5, 29, 7, 8, 14, 23, 3, 11习题：1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B 。 （A）正确 （B）错误2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 D 。（A）空或只有一个结点 （B） 完全二叉树（C）二叉排序树 （D） 高度等于其节点数3、 深度为5的二叉树至多有C 个结点。（A）16 （B）32 （C）31 （D）104、根据使用频率为5个字符设计的赫夫曼编码不可能是C .（A）111，110，10，01，00（B）000，001，010，011，1（C）100，11，10，1，0（D）001，000，01，11，105、树和二叉树的主要差别是（1） 树的结点个数至少为1，而二叉树的结点个数可以为 0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分。6、深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号 。7、一棵二叉树的第i(i1)层最多有 个结点；一棵有n（n0）个结点的满二叉树共有 个叶子结点和 个非叶子结点。8、已知二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。l 先序序列是：*BC*FGl 中序序列是：CB*EAG*l 后序序列是：*EDB*FA9、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍