数据结构(c语言版)复习知识点

精品

第四章 串、数组和广义表

4.1串相关术语

串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 串长：串中字符个数（n≥0）.n=0时称为空串空白串：由一个或多个空格符组成的串。

子串：串s中任意个连续的字符序列叫s的子串;s叫主串。 子串位置：子串的第一个字符的序号。 字符位置：字符在串中的序号

串相等：串长度相等，且对应位置上字符相等。

串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集；串的基本操作和线性表有很大差别。在线性表的基本操作中，大多以“单个元素”作为操作对象；在串的基本操作中，通常以“串的整体”作为操作对象。

。

4.2串的基本操作

熟悉以下操作的意义： StrAssign(&T,chars) StrCopy(&T,S) DestroyString(&S) StrEmpty(S) StrCompare(S,T) StrLength(S) Concat(&T,S1,S2)

SubString(&Sub,S,pos,len) Index(S,T,pos) Replace(&S,T,V) StrInsert(&S,pos,T) StrDelete(&S,pos,len) ClearString(&S)

4.3数组

感谢下载载

精品

1.二维数组的顺序存储结构及地址计算方式。

设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0。L：单个元素长度 则行优先存储时的地址公式为：

LOC(aij)=LOC(c1，c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L 二维数组列优先存储的通式为：

LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+(i-c1)]*L

2.对称矩阵的压缩存储：在对称矩阵中，只需存储对称矩阵的下半部分。 所需空间数为：n×（n+1）/2。

设一般的二维数组是A[c1..d1,c2..d2]，这里c1,c2不一定是0，对应一维存储空间SA的起始 值是C3。

则行优先存储时的地址公式为：

3.三角矩阵：若n阶方阵中下(上)三角(不包括对角线)中的元均为常量c或0，则称为上(下) 三角矩阵；下三角矩阵：主队角线以上均为同一个常数；上三角矩阵，主队角线以下均为同一个常数。与对称矩阵类似，不同之处在于存完下三角中的元素之后，紧接着存储对角线上方的常量，因为是同一个常数，所以存一个即可，这样一共存储了n*(n+1)/2+1个元素，设存入数组：SA[n*(n+1)/2+1]中，这种的存储方式可节约n*(n-1)/2个存储单元。 4.理解下、上三角矩阵：SAk与ai,j的对应关系。

感谢下载载

精品

5.稀疏矩阵：将每个非零元素用一个三元组（i,j,aij）来表示，将三元组按行优先的顺序，同一行中列号从小到大的规律排列成一个线性表，称为三元组表，每个稀疏矩阵可用一个三元组表来表示。

4.4广义表

1.广义表是递归定义的线性结构，是线性表的推广，也称为列表(lists) 记为：LS=(1,2,...,n)。

2.广义表与线性表的区别和联系:广义表中元素既可以是原子类型，也可以是列表；当每个元素都为原子且类型相同时，就是线性表。 3.广义表LS=(

1,

2,…,n)的的性质:

1)广义表中的数据元素有相对次序;

2)广义表的长度定义为最外层包含元素个数; 3)广义表的深度定义为所含括弧的最大重数; 注意:“原子”的深度为0;“空表”的深度为1

4)广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，…。

5)广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。

6)广义表可以为其他表所共享。

7) 任何一个非空广义表LS=( 1, 2,…, n)

均可分解为:表头 Head(LS)=1和表尾Tail(LS)=( 2,…, n) 两部分. 任何一个非空表，表头可能是原子，也可能是列表；但表尾一定是列表

感谢下载载

精品

4.广义表的基本运算:广义表有两个重要的基本操作，即取头操作（Head）和取尾操作（Tail）。要熟悉这个两个操作，正确给出一个广义表的这两个操作的结果。

第五章 树及二叉树

5.1树结构及基本概念

1.树具有下面两个特点：

树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。 树中所有结点可以有零个或多个后继结点。 2.基本术语：

结点(node): 表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree):结点拥有的子树数称为~ 叶子(leaf):度为0的结点

孩子(child): 结点子树的根称为该结点的孩子 双亲(parents):

孩子结点的上层结点

兄弟(sibling): 同一双亲的孩子 树的度: 一棵树中最大的结点度数

结点的层次(level): 从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth): 树中结点的最大层次数 森林(forest): m(m

0)棵互不相交的树的集合

5.2二叉树结构

1.定义:二叉树是n(n

0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别

称为左子树和右子树的互不相交的二叉树构成

2.特点：每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且 其次序不能任意颠倒 3.基本形态:五种

感谢下载载

精品

4.二叉树的性质

性质1:在二叉树的第i层上至多有2i-1个结点。 性质2:深度为k的二叉树，至多有2k-1个结点。

性质3:对任意二叉树BT，若叶结点数为n0，度为2的结点数为n2，则：n0=n2+1 性质4:具有n个结点的完全二叉树的深度为

log2n

1

in)，

性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1有：

1) 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点2) 如果2i>n，则结点i无左孩子；如果2i

n，则其左孩子是结点2i

i/2

3) 如果2i+1>n，则结点i无右孩子；如果2i+1

5.几种特殊形式的二叉树： 满二叉树：一棵深度为k且有2k

1个结点的二叉树称为~

n，则其右孩子是结点2i+1

特点：每一层上的结点数都是最大结点数

完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉 树中编号从1至n的结点一一对应时，称为~

特点：叶子结点只可能在层次最大的两层上出现；对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l或l+1

5.3二叉树存储

1.二叉树的顺序存储结构：按满二叉树的结点层次编号，依次存放二叉树中的数据元素 特点：结点间关系蕴含在其存储位置中；浪费空间，适于存满二叉树和完全二叉树 2.二叉树的链式存储结构（二叉链表）：在n个结点的二叉链表中，有n+1个空指针域 3.二叉树的链式存储结构（三叉链表）

感谢下载载