《数据结构复习整理》由会员分享，可在线阅读，更多相关《数据结构复习整理（14页珍藏版）》请在金锄头文库上搜索。
1、功能：建立空的线性表 L;2 销毁操作 DetroyList (&L)功能：回收为线性表 L动态分配的存储空间；3 置空操作 ClearList (&L)功能：L中已存在，重新将其置成空表；4 判空操作 ListEmpty (L)功能：判断线性表 L是否为空表，若为空表返回TRUE否则返回FALSE5 求表长操作 ListLe ngth (L)功能：返回线性表 L的表长；6 取元素操作：GetElem ( L, i, &e)功能：将线性表L中第i个元素赋值给 e；7 查找操作 LocateElem ( L, e, compare。)功能：在线性表L中查找与元素e满足compare()的第1个元
2、素，返回该元素在表中的序号(或位置)，若表中不存在这样的元素，则返回 0 ;8 查找前驱 PriorElem ( L, cur_e, &pre_e )功能：若cur_e是L中的数据元素且不是第一个，则用pre_e返回它的前驱，否则失败，pre_e无定义。9 查找后继 NextElem ( L, cur_e, &n ext_e )功能：若cur_e是L中的数据元素且不是最后一个，则用 next_e返回它的后继，否 则失败，next_e无定义。10 插入操作 ListInsert ( &L, i, e )功能：在线性表L的第i个元素之前插入1个新元素e；11 删除操作 ListDelete ( &
3、 L, i, &e )功能：删除线性表 L的第i个元素，并用 e返回；12 遍历操作 ListTraverse ( L,visit()功能：依次对线性表L的每个元素调用函数 visit()。若visit()失败，则返回 ERROR否则返回OK;顺序存储 表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于 在插入或删除时，为保持原有次序(没有规定元素进栈顺序)，平均需要移动一半(或近一半)元素，修改效率不高。链接存储 表示的存储空间一般在程序的运行过程中动态分
4、配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时 不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。作为一般规律，当线性表中元素个数变化较大或者未知时，最好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 每个结点包括两个部分：一个是存
5、储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作。对线性表的基本操作栈是限定仅能在表尾一端进行插入、删除操作的线性表能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。1、栈是限定仅能在表尾一端进行插入、删除操作的线性表2、栈的元素具有后进先出的特点3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改 栈顶指针出栈機廳SO栈的特点后进先出第个进栈的元素在栈底 最后一个进栈的元素在栈顶 第一个出栈的元素为栈顶元素栈的示意图最后一个岀栈的元素为栈底兀素队列是限定仅能在
6、表头进行删除，表尾进行插入的线性表。 能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。队列的示意图第一个入队的元亲在队头最后一个入队的元素在臥尾孑?第一个出队的元素为队头元素一 F最后一个出队的元素为队尾元素三、队列的应用1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；3）离散事件的模拟一一模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示；4、入
7、队操作要修改队尾指针，出队操作要修改队头指针。数组的概念数量固定，数据类型相同的（变量）元素组合在一起。使用一个名称代表它。这个名称就是数组名。如果要访问其中某个元素（变量），可以使用元素的索引值 （下标）来访问它。在C语言中，数组元素的索引值从0开始。数组的存储两种形式：既可以是顺序存储，也可以采用链式结构。稀疏矩阵含有较多值相同元素或较多零元素，且值相同元素或者零元素分布没有一定规律的矩阵称为稀疏矩阵如何设计递归函数？一、分治法 （Divide and Conq uer）（又称分割求解法）二、后置递归法（Postponing the work）三、回溯法（Backtracking）递归函数
8、一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条 件：2.必须有一个终止条件。 树的表示1 ）图示表示2）二兀组表示3）文氏图表示4）广义表表示5）凹入表示法（类似书的目录）树的基本术语树的结点：包含一个数据元素的内容及若干指向子树的分支。孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如 B是E的双亲。兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。堂兄结点：同一层上结点；女口 G与E、F、H、I、J互为堂兄。祖先结点：某一结点的祖先是从根到该结点所 经分支上的所有结点；如 H的祖先为A、D。子孙
9、结点：以某结点为根的子树中的任一结点称为该结点的子孙；女口A的子孙为B、C D、E、F、G、H、I、J。结点的度：结点子树的个数；女口D的度为3。叶子结点：也叫终端结点，是度为0的结点；女口 E、F、G、H、I、Jo分枝结点：度不为 0的结点；如A、B、C Do结点：数据元素+若干指向子树的分支 结点的度：分支的个数树的度：树中所有结点的度的最大值 叶子结点：度为零的结点 分支结点：度大于零的结点结点的层次：假设根结点的层次为 1,第I层的结点的子树根结点的层次为1+1树的深度： 树中叶子结点所在的最大层次二叉树一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为
10、左子树和右子树的、互不相交的二叉树组成。满二叉树：指的是深度为k且含有2k-i个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点 对应遍历：按某种搜索路径访问二叉树中的每个结点，且每个结点仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。 遍历是各种数据结构最基本的操作，许多其它的操作可以在遍历基础上实现。遍历对线性结构来说很容易解决，但二叉树每个结点都可能有两棵子树，因而需要寻找一种规律，使得二叉树上的结点能线性排列。二叉树的遍历二叉树的遍历，就是按某种次序访问二叉树中的结点，要求每个结点访问一次且仅访问一次。二叉树由根、左子树
11、、右子树三部分组成。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树。令：L:遍历左子树D:访问根结点R:遍历右子树有六种遍历方法：基本：DLR LDR LRD镜象：DRL，RDL，RLD约定先左后右，有三种遍历方法：DLR LDR LRD,分别根据访问根结点的次序称为：先序遍历、中序遍历和后序遍历。J 11.例：先序遍历、中序遍历、后序遍历二叉树。TfJrTbifr先序遍历序列：-,+,a,*,b,-,c,d,/,e,f中序遍历序列：a,+,b,*,c,-,d,-,e,/,f后序遍历序列：a,b,c,d,-,*,+,e,f,/,-最优二叉树(赫夫曼树)哈夫曼树：假设有 n个权值(wi,
12、w2,，nW,构造有n个叶子结点的二叉树，每个叶子结 点有一个 Wj作为它的权值。则带权路径长度最小的二叉树称为哈夫曼树。图(Graph)图G是由两个集合 V(G)和E(G组成的，记为G=(V,E)其中：V(G)是顶点的非空有限集E(G)是边的有限集合，边是顶点的无序对或有序对。图的分类有向图无向图有向图一一有向图G是由两个集合 V(G)和E(G组成的。其中：V(G)是顶点的非空有限集。E(G)是有向边(也称弧)(的有限集合，弧是顶点的有序对，记为, v,w是顶点，v为弧尾，w为弧头。无向图一一无向图G是由两个集合 V(G)和E(G组成的。(v,w)或(w,v)，并且E(G)是边的有限集合，边
13、是顶点的无序对，记为(v,w)=(w,v)。? 图的基本术语1邻接点及关联边邻接点：边的两个顶点关联边：若边e= (v, u),则称顶点v、u关连边e 2顶点的度、入度、出度顶点V的度=与V相关联的边的数目在有向图中：顶点V的出度=以V为起点有向边数 顶点V的入度=以V为终点有向边数 顶点V的度=V的出度+V的入度设图G的顶点数为 n,边数为e图的所有顶点的度数和=2*e(每条边对图的所有顶点的度数和贡献”2度)O O|1、1、数据结构在计算机内存中的表示是指A.数据的存储结构B.数据元素的结构C.数据的逻辑结构D.数据元素之间的关系答案：A2、在数据结构中，与所使用的计算机无关的是A.数据的
14、存储结构C.数据的逻辑结构答案：C3、对于给定的n个元素，答案：集合 线性结构 树结构 图结构1、线性表的顺序存储结构是通过何种方式表示元素之间的关系 A.保存后继元素地址B.元素的存储顺序C.保存左、右孩子地址D.后继元素的数组下标B当对一个线性表经常进行的是读取操作，而很少进行插入和删除操作时，则采用 存储结构为宜，相反，当经常进行的是插入和删除操作时，则采用宜。顺序链式3、 若线性表最常用的操作是存取第i个元素及其前趋和后继元素的值，为节省时间应采用 的存储方式是 答案：顺序表4、在p所指向的结点后插入由A) p_n ext=q;B) q=p-n ext;C) q_n ext=p-n ext;B.逻辑和物理结构D.数据的物理结构可以构造出的逻辑结构有树结构q指向的新结点的语句序列是q_n ext=p-n ext;p_n ext=q;p_n ext=q; 四种。存储结构为D) p=p-n ext;q_n ext=p;答案：C5、
