数据结构复习要点(整理版)

《数据结构复习要点(整理版)》由会员分享，可在线阅读，更多相关《数据结构复习要点(整理版)（13页珍藏版）》请在装配图网上搜索。

1、第一章 数据结构概述 基本概念与术语1数据:数据是对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中并被计算 机程序所处理的符号的总称.2. 数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点 顶点记录。(补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。)3数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集.(有时候也 叫做属性。)4数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。(1) 数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数 据结构.数据的逻辑结构是从数据元

2、素之间存在的逻辑关系上描述数据与数据的存储无关，是 独立于计算机的.依据数据元素之间的关系,可以把数据的逻辑结构分成以下几种：1. 集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。2. 线性结构:结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一 个元素之外,和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。3。树形结构:结构中的数据元素之间存在“一对多“的关系.若数据为非空集，则除了第一个 元素(根)之外，其它每个数据元素都只有一个直接前驱,以及多个或零个 直接后继.4。图状结构:结构中的数据元素存在“多对多”的关系.若结构为非空

3、集,折每个数据可有多 个(或零个)直接后继.(2) 数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据,就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射 为以下两种存储结构:1。顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元 素在存储器中的相对位置来表示数据之间的逻辑关系。2。链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素 物理位置上也相邻。5。时间复杂度分析：1.常量阶：算法的时间复杂度与问题规模n无关系T (n) =0 (1)2。线性阶:算法的时间复杂度与问题规模n成线性关系T (

4、n)=0 (n)3。平方阶和立方阶:一般为循环的嵌套，循环体最后条件为 i+ 时间复杂度的大小比较:O(1 ) O(log 2 n) O( n ) O(n log 2 n) O( n2) O( n3) O( 2 n ) O(n!)next=headnext; headnext=p;输出：printf (“d, pdata);删除:q=pnext；p-next = qnext ; free (q)；结点遍历： for(p=head;p;p=pnext)；补充内容:1、线性表中,第一个元素没有直接前驱,最后一个元素没有直接后驱.2、在一个单链表中，若p所指结点是q所指结点的前驱结点，则删除结点q的

5、操作语句为 P- next = qnext ； free（ q）；3、在长度为N的顺序表中,插入一个新元素平均需要移动表中N/2个元素栅9除一个元素平 均需要移动（N1） /2个元素。4、若线性表的主要操作是在最后一个元素之后插入一个元素或删除最后一个元素，则采用 顺序表存储结构最节省运算时间。5、已知顺序表中每个元素占用3个存储单元，第13个元素的存储地址为336,则顺序表的首 地址为300。（第n个元素的地址即首地址+ （n-1）*每个元素的存储空间，如a 12（第13 个元素）的地址=3 0 +12*3）6、设有一带头结点单链表L,请编写该单链表的初始化，插入、输出和删除函数。（函数名

6、自定义）结点定义：typedef int datatype； typedef struct node 结点数据类型,假设为int/结点结构datatype data; struct node *next;/双向链表还应加上* previous Lnode，* pointer ; 结点类型，结点指针类型typedef pointer lklist;/单链表类型，即头指针类型1。初始化:lklist initlist()pointer head；head=new node； 这是 C+做法 /head=( pointer)malloc(sizeof(Lnode) ;这是 C 语言做法head- n

7、ext=NULL；/循环链表则是 headnext=head;/双向链表应加上 head previos=NULL; return head;2。插入：(C语言中需要把head转化为全局变量才能实现此程序) int insert(lklist head,datatype x,int i) pointer q， s;q=get( head， i1 ) ;/找第 i-1 个点if(q=NULL)/无第 i1 点，即 in+1 时coutV”非法插入位置！ n”; 这是C+做法，即C语言中的printf (“非法插入位置!n”) ;return 0;s=new node;/生成新结点即 C 语言中的

8、 s= ( pointer)malloc (sizeof (Lnode)；s-data=x;snext=q-next; 新点的后继是原第i个点qnext=s；/原第 i1 个点的后继是新点return 1;/插入成功3。删除：(C语言中需要把head转化为全局变量才能实现此程序)int delete(lklist head,int i)pointer p,q；q=get(head，i1)；/找待删点的直接前趋if(q=NULL | q next=NULL)/即 inext=head D. head!=NULL3。 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点,则执行(B )

9、A。s next=p; p next=s； B。 s- next=p next； p-next=s；C。s- next=p-next； p=s； D. p-next=s; s next=p；4。在一个单链表中，若删除p所指结点的后续结点，则执行(A )A。p- next=pnext next;B。p=p next；p- next=p next next;C。pnext=p-nextD。p=p-next-next5。从一个具有n个结点的有序单链表中查找其值等于x结点时，在查找成功的情况下，需 平均比较(B )个结点。A。n Bo n/2 C. (n1)/2D。O (n log 2n)6。给定有n

10、个元素的向量，建立一个有序单链表的时间复杂度(B)A。 O(1) B.O(n)C。 O(n2)D.O(ng2n)7。在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是(B)A.O(1) B。 O(n)C.O(n2)D.O(ng 2n)8o在一个单链表中删除q所指结点时，应执行如下操作：q=p-next；p-next=( p- nextnext )；free(q)； /这种题目靠一根指针是没有办法完成的，必须要借助第二根指针.9. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行： s next=( p- next )pnext=(s)操作。10. 对于一个具有 n

11、个节点的单链表 ,在已知所指结点后插入一个新结点的时间复杂度是 (0(1)；在给定值为x的结点后插入一个新结点的时间复杂度是(O (n)。11. 问答题线性表可用顺序表或链表存储。试问:( 1 ) 两种存储表示各有哪些主要优缺点?顺序表的存储效率高,存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发 生改变,因此，不易扩充。同时,由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空 间,就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序, 只需要保

12、持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针，修改效率较高。 但存取表中的数据元素时,只能循链顺序访问，因此存取效率不高.(2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素， 这时，应采用哪种存储表示？为什么？ 应采用顺序存储表示.因为顺序存储表示的存取速度快，但修改效率低.若表的总数基本稳定, 且很少进行插入和删除，但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好。第三章 栈和队列1。栈(1) 栈的结构与定义定义:限定仅在表尾进行插入或删除操作的线性表。结构：typedef struct list int listsize;/栈的容量s

13、truct list head；/栈顶指针struct list *base;/栈底指针(2) 顺序栈操作算法：入栈、出栈、判断栈空等(这个是使用数组进行操作的，具体内 容参照书本 P4647)(3) 链栈的结构与定义2。队列(1) 队列的定义定义:只允许在表的一端进行插入，而在另一端删除元素。补充内容:1、一个栈的入栈序列为“ABCDE”，则以下不可能的出栈序列是(B)A。 BCDAEB。 EDACBC. BCADED. AEDCB2、栈的顺序表示中，用TOP表示栈顶元素，那么栈空的条件是（D）A。 TOP=STACKSIZEB. TOP=1C。 TOP=0D。 TOP=13、允许在一端插入

14、，在另一端删除的线性表称为队列。插入的一端为表头，删除的一端为表尾。4、栈的特点是先进后出，队列的特点是先进先出.5、对于栈和队列，无论他们采用顺序存储结构还是链式存储结构，进行插入和删除操作的 时间复杂度都是O （1）（即与已有元素N无关）。6、已知链栈Q,编写函数判断栈空，如果栈空则进行入栈操作，否则出栈并输出。（要求判 断栈空、出栈、入栈用函数实现）（详看考点 2）7、出队与取队头元素的区别：出队就是删除对头的数据元素，取队头元素是获取对头的数 据元素值，不需要删除。8、链栈与顺序栈相比，比较明显的优点是（D）A。插入操作比较容易B.删除操作比较容易C。不会出现栈空的情况D。不会出现栈满

15、的情况考点 1：队列的编程:结构：typedef struct QNode int date;struct QNode next； QNode, * QueuePtr；typedef structQueuePtr front；QueuePtr rear; LinkQueue；创建：LinkQueue InitQueue( LinkQueue Q)Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode) ; Q。 front-next=NULL； return ( Q) ;入队：LinkQueue EnQueue( LinkQueue Q,int e)Queu

16、ePtr p；p=( QueuePtr) malloc(sizeof(QNode)；pdate=e； pnext=NULL; Q.rearnext=p;Q。 rear=p； return (Q) ;出队:LinkQueue DeQueue(LinkQueue Q)int e；QueuePtr p；p=Q.frontnext; e=pdate; Q.front=pnext; printf(”d”，e);if (Q。rear=p) Q.rear=Q。front=NULL； free( p) ;return ( Q)；考点 2：栈的编程:创建：struct list *creat()struct l

17、ist *p； p=(struct list )malloc( LEN); pnext=NULL； return( p)；入栈：struct list *push(struct list *head，int a)struct list *p；p=( struct list *) malloc( LEN)； pnum=a;pnext=head； return(p) ;出栈：struct list pop( struct list head)struct list *p； p=headnext； free(head)； return( p);判断栈空：int listempty（struct li

18、st head）if（headnext）return 0；else return 1；第四章 串 （不是重点内容）1。串是由零个或多个字符组成的有限序列2。串的赋值：x=abc；或 x =abc；第五章 数组和广义表 （不是重点内容）1。多维数组中某数组元素的position求解。一般是给出数组元素的首元素地址和每个元素占 用的地址空间并组给出多维数组的维数,然后要求你求出该数组中的某个元素所在的位置。2。明确按行存储和按列存储的区别和联系，并能够按照这两种不同的存储方式求解1 中类 型的题.3。将特殊矩阵中的元素按相应的换算方式存入数组中.这些矩阵包括:对称矩阵，三角矩阵, 具有某种特点的稀

19、疏矩阵等。熟悉稀疏矩阵的三种不同存储方式：三元组，带辅助行向量的 二元组，十字链表存储。掌握将稀疏矩阵的三元组或二元组向十字链表进行转换的算法。补充内容:三元组:结构：typedef structint i,j；/元素行下标及列下标int e;/元素值Triple；typedef structint mu，nu，tu；/矩阵的行数、列数、非零元素个数Triple data MAXSIZE+1;矩阵包含的三元组表，data0未用 TSMatrix；十字链表：typedef struct OLNodeint i， j；/元素行下标及列下标int e；/元素值struct OLNode right,

20、down；/行的后继以及列的后继 OLNode,大 OLink；typedef structint mu,nu， tu；/矩阵的行数、列数、非零元素个数OLink rhead,chead；/行和列的表头指针组的首地址CrossList；CrossList Creat(CrossList M)int m，n,t； scanf(“ddd”,m，&n，&t);M。mu=m； M。nu=n;M.tu=t；M。 rhead=( OLink )malloc(m+1)*sizeof(OLink)；/开辟行表头指针组M。 chead=( OLink )malloc(n+1)sizeof(OLink);/开辟行

21、列头指针组M。 rhead=M。 chead=NULL；/初始化/接下来就是赋值和入链第六章 树和二叉树1 树(1) 树的概念及术语 树:n (n0)个结点的有限集合。当n=0时，称为空树；任意一棵非空树满足以下条件： 有且仅有一个特定的称为根的结点；当nl时，除根结点之外的其余结点被分成m(m)个互不相交的有限集合T1,T2,， Tm,其中每个集合又是一棵树,并称为这个根结点的子树.(2) 结点的度：结点所拥有的子树的个数.树的度：树中所有结点的度的最大值.(3) 叶子结点：度为0的结点，也称为终端结点。 分支结点：度不为0的结点，也称为非终端结点。(4) 孩子、双亲：树中某结点的子树的根结

22、点称为这个结点的孩子结点 ,这个结点称为它孩 子结点的双亲结点；兄弟：具有同一个双亲的孩子结点互称为兄弟.(5) 路径：如果树的结点序列nl, n2,nk有如下关系：结点ni是ni+1的双亲(1=ik),则把nl, n2,，nk称为一条由nl至nk的路径；路径上经过的边的个数称为路径长度.(6) 祖先、子孙：在树中，如果有一条路径从结点x到结点y,那么x就称为y的祖先，而 y称为x的子孙。(7) 结点所在层数：根结点的层数为1；对其余任何结点,若某结点在第k层，则其孩子结点 在第 k+1 层.树的深度：树中所有结点的最大层数，也称高度.(8) 层序编号:将树中结点按照从上层到下层、同层从左到右

23、的次序依次给他们编以从1 开 始的连续自然数。(9) 有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的,称这棵树为有序树； 反之，称为无序树.数据结构中讨论的一般都是有序树( 10)树通常有前序(根)遍历、后序(根)遍历和层序(次)遍历三种方式(树, 不是二叉树,没中序遍历。 )2 二叉树(1) 二叉树的定义：二叉树是n(nO)个结点的有限集合，该集合或者为空集(称为空二叉 树)，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在 同一层上。(满二叉树的特点：叶子只能出现在最下

24、一层；只有度为0和度为 2 的结点。)完全二叉树：对一棵具有n个结点的二叉树按层序编号，如果编号为i(lWiWn)的结点与 同样深度的满二叉树中编号为i的结点在二叉树中的位置完全相同。完全二叉树的特点：1。在满二叉树中，从最后一个结点开始，连续去掉任意个结点，即是一棵完全二叉树2。叶子结点只能出现在最下两层,且最下层的叶子结点都集中在二叉树的左部;3。完全二叉树中如果有度为1 的结点，只可能有一个，且该结点只有左孩子。4。深度为 k 的完全二叉树在 k1 层上一定是满二叉树。(3) 二叉树的性质:性质1： 二叉树的第i层上最多有2i-1个结点G21)。性质 2： 一棵深度为 k 的二叉树中，最

25、多有 2k1 个结点,最少有 k 个结点。深度为 k 且具有 2k1 个结点的二叉树一定是满二叉树性质3：在一棵二叉树中，如果叶子结点数为n0，度为2的结点数为n2,则有：n0=n2 1.(一个结点的度就是指它放出的射线)性质4：具有n个结点的完全二叉树的深度为log2n +1.性质5:对一棵具有n个结点的完全二叉树中从1开始按层序编号，则对于任意的序号 为i (1WiWn)的结点(简称为结点i)，有：(1)如果i1,则结点i的双亲结点的序号为i/2；如果i=1，则结点i是根结点，无双 亲结点。(2) 如果2iWn,则结点i的左孩子的序号为2i；如果2in，则结点i无左孩子。(3) 如果2i+

26、1Wn,则结点i的右孩子的序号为2i+1；如果2i+1n,则结点i无右孩子。3 二叉树的遍历(递归调用与访问的顺序不同而产生不同的遍历方法)( 1) 先序遍历void XianXu(BiTree T) if( T) printf(”%c， Tdata);/先访问XianXu(Tlchild)；/再继续遍历XianXu( T-rchild)；( 2) 中序遍历(3) 后序遍历4。森林与二叉树的转换(1) 同级以左为亲，即左一结点的右孩子是与它同级的右一结点(2) 只认最左路线为亲子路线，即结点的左孩子是它下一级结点的最左的元素5。哈夫曼树（1）哈夫曼树的基本概念： 哈夫曼树:给定一组具有确定权值

27、的叶子结点,带权路径长度最小的二叉树. （2）哈夫曼树的特点：1. 权值越大的叶子结点越靠近根结点，而权值越小的叶子结点越远离根结点.2。 只有度为0（叶子结点）和度为 2（分支结点）的结点，不存在度为1 的结点（3）哈夫曼树的构造算法思想及构造过程（森林与哈夫曼编码）就是求各权值和路径相乘之后叠加的最小值。1、已知一棵完全二叉树有47个结点，则该二叉树有（C）个叶子结点。A。6B。12 C。24 D。48解法如下： 1+2+4+8+16=31计算从第一层到 n1 层的结点个数47-31=16计算第 n 层的叶子结点个数1616/2=8计算第 n-1 层的叶子结点个数所以，叶子结点数=16+8

28、=24计算第 n 层和第 n-1 层的总叶子结点数2、已知遍历一棵二叉树的前序序列ABCDEFG和中序序列CBEDAFG那么是下面哪棵树 （C ）。C 图如下：A/ BF/ CDG/E4、完全二叉树必须满足的条件为：一棵具有n个结点的二叉树，它的结构与满二叉树的 前 n 个结点的的结构相同。5、哈夫曼树不存在度为 1 的结点。6、有 5 个带权结点,其权值分别为 2,5， 3， 7， 11,根据哈夫曼算法构建该树，并计算该树的 带权路径长度。（构建哈夫曼树，很简单，从小开始,计算相加，然后把所有叶子结点乘以等 级数字然后相加。也即是:带权路径长度=叶结点的权值路径长度）7。试找出分别满足下列条

29、件的所有二叉树： 前序序列和中序序列相同：只有右子树中序序列和后序序列相同:只有左子树前序序列和后序序列相同：只有根，空二叉树第七章图1. 图的基本概念：图的基本术语及推论 图的结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关 设图有n个顶点，则：有1/2 n(n 1)条边的无向图称为完全图有n (n1)条弧的有向图称为有向完全图 元素被多少条弧的箭头所指，它的入度就为多少；反之，出度. 第一个顶点和最后一个顶点相同的路径叫做回路或环 顶点不重复出现的路径叫简单路径若图中任意两个顶点之间存在路径(不一定是直接相连),则称作连通图2. 邻接矩阵：W . gVRi,ji j邻接矩阵的

30、定义： A.j=0即VR中不存在Vj，V/时寸3. 图的遍历(1)深度优先遍历步骤：1。从任意顶点开始访问。2。访问后把该元素对应的访问标志赋值为1表示已访问该数据元素3。寻找与其有关未被访问的所有邻接顶点，并从该顶点开始进行访问4。重复2、3步骤直到该连通图的所有顶点均已访问完毕2)广度优先遍历步骤：1。从任意顶点开始访问。2。访问后把该元素对应的访问标志赋值为1表示已访问该数据元素3。寻找与其有关未被访问的邻接顶点，并按顺序入列直到所有邻接顶点均 已访问完毕4。把最先入列的顶点出列，以它为顶点开始访问5。重复2、3、4步骤直到该连通图的所有顶点均已访问完毕第八九十章 查找表是由同一类型的数据元素(或记录)构成的集合 对查找表的操作有：(1) 查询某个“特定的”数据元素是否在查找表中(2) 检索某个“特定的”数据元素的各种属性3) 在查找表中插入一个数据元素4) 从查找表中删去某个特定元素 静态查找表只进行前两种“查找”操作的查找表为静态查找表动态查找表 若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某 个数据元素，则成为动态查找表排序 其功能是将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列.