第1章绪论 1.数据结构的定义 数据一>数据元素一>数据项 数据结构是指数据以及相互之间的联系。包括 (1)数据的逻辑结构 (2)数据的存储结构(物理结构) (3)施加在该数据上的运算 数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。 数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象),它是依赖于计算机语言的。 数据的运算是定义在数据的逻辑结构上的,每种逻辑结构都有一组相应的运算。但运算的实现与数据的存 储结构有关。 逻辑结构主要有两大类 (1)线性结构 (2)非线性结构: 1)树形结构 2)图形结构 存储结构分为如下四种 (1)顺序存储方法 (2)链式存储方法 (3)索引存储方法 (4)散列存储方法 2.抽象数据类型 抽象数据类型( Abstract Data Type简写为ADT)指的是用户进行软件系统设计时从问题的数学模型中抽 象出来的逻辑数据结枃和逻辑数据结构上的运算,而不考虑计算机的具体存储结构和运算的具体实现算法。 3.什么是算法 算法是对特定问题求解步骤的一种描述,它是指令的有限序列 算法的五个重要的特性: (1)有穷性(2)确定性(3)可行性(4)有输入(5)有输 4.算法分析 (1)算法的时间复杂度:是指其基本运算在算法中重复执行的次数 算法中基本运算次数T(n)是问题规模n的某个函数f(n),记作 T(n)=0(f(n) 己号“o”读作“大o”,它表示随问题规模n的增大算法执行时间的增长率和f(n)的增长率相同 (2)算法空间复杂度:是对一个算法在运行过程中临时占用的存储空间大小的量度。 对于空间复杂度为o(1)的算法称为原地工作或就地工作算法 第2章线性表 1.线性表的定义 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度,用n表 n≥0。当n=0时,表示线性表是一个空表,即表中不包含任何元素 1.线性表的顺序存储结构一顺序表 typedef struct ElemType elem[ Maxsize];/*存放顺序表元素* nt length /*存放顺序表的长度*/ 1 SqList 顺序表基本运算的实现 插入数据元素算法:元素移动的次数不仅与表长n有关:插入一个元素时所需移动元素的平均次数n/2 平均时间复杂度为0(n)。 删除数据元素算法:元素移动的次数也与表长n有关。删除一个元素时所需移动元素的平均次数为 (n-1)/2。删除算法的平均时间复杂度为0(n) 【例2.1】设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构)的适当位置上, 并保持线性表的有序性。 void Insert(SqList &A, ElemType x) I int i=0, j
第 1 章 绪论 1.数据结构的定义 数据－＞数据元素 －＞数据项 数据结构是指数据以及相互之间的联系。包括： （1）数据的逻辑结构。 （2）数据的存储结构（物理结构）。 （3）施加在该数据上的运算。 数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 数据的存储结构是逻辑结构用计算机语言的实现（亦称为映象），它是依赖于计算机语言的。 数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组相应的运算。但运算的实现与数据的存 储结构有关。 逻辑结构主要有两大类： （1）线性结构 （2）非线性结构： 1）树形结构 2）图形结构 存储结构分为如下四种： （1）顺序存储方法 （2）链式存储方法 （3）索引存储方法 （4）散列存储方法 2.抽象数据类型 抽象数据类型（Abstract Data Type 简写为 ADT）指的是用户进行软件系统设计时从问题的数学模型中抽 象出来的逻辑数据结构和逻辑数据结构上的运算，而不考虑计算机的具体存储结构和运算的具体实现算法。 3.什么是算法 算法是对特定问题求解步骤的一种描述，它是指令的有限序列 。 算法的五个重要的特性 ： （1）有穷性 （2）确定性 （3）可行性 （4）有输入 （5）有输出 4.算法分析 (1)算法的时间复杂度：是指其基本运算在算法中重复执行的次数。 算法中基本运算次数 T(n)是问题规模 n 的某个函数 f(n)，记作： T(n)=O(f(n)) 记号“O”读作“大 O”，它表示随问题规模 n 的增大算法执行时间的增长率和 f(n)的增长率相同。 (2)算法空间复杂度：是对一个算法在运行过程中临时占用的存储空间大小的量度 。 对于空间复杂度为 O(1)的算法称为原地工作或就地工作算法。 第 2 章 线性表 1.线性表的定义 线性表是具有相同特性的数据元素的一个有限序列。该序列中所含元素的个数叫做线性表的长度，用 n 表 示，n≥0。当 n=0 时，表示线性表是一个空表，即表中不包含任何元素。 1.线性表的顺序存储结构—顺序表 typedef struct { ElemType elem[MaxSize]; /*存放顺序表元素*/ int length; /*存放顺序表的长度*/ } SqList; 顺序表基本运算的实现 插入数据元素算法：元素移动的次数不仅与表长 n 有关 ；插入一个元素时所需移动元素的平均次数 n／2。 平均时间复杂度为 O(n)。 删除数据元素算法:元素移动的次数也与表长 n 有关 。删除一个元素时所需移动元素的平均次数为 (n-1)/2。删除算法的平均时间复杂度为 O(n)。 【例 2.1】 设计一个算法，将 x 插入到一个有序（从小到大排序）的线性表（顺序存储结构）的适当位置上， 并保持线性表的有序性。 void Insert(SqList &A,ElemType x) { int i=0,j;
hile(i<A length && AS elem[i]<x)i++ for (j=A length-l: j>=i; j- A. elem[j+1]=A. elemLj] Alength++ F 2.线性表的链式存储结构一链表 定义单链表结点类型 ElemType data typedef struct lnoc struct LNode * next /*指向后继结点* 1 LinkList 定义双链表结点类型 typedef struct DNode i ElemType data truct DNode *prior *指向前驱结点*/ struct DNode * next /*指向后继结点* I DLinkList (1)单链表基本运算的实现 重点:头插法建表和尾插法建表算法,它是很多算法设计的基础。 【例2.1】设C={a1,b1,a2,b2,…,an,bn}为一线性表,采用带头结点的hc单链表存放,编写一个就地算法 将其拆分为两个线性表,使得:A={a1,a2,…,an},C={b1,b2,…,bn void fun(LinkList *hc, LinkList *&ha, LinkList *&hb) I LinkList *p=hc->next, *ra, *rb ha=hc /*ha的头结点利用hc的头结点* /*ra始终指向ha的末尾结点*/ hb=( Linklist*) malloc( sizeof( Linklist);/*创建hb头结点* b=hb;/*rb始终指向hb的末尾结点*/ while (p!=NULL I ra>nextp: ra=p: /*将*链到ha单链表未尾*/ p=p->next if (p!=NULL) rb->next=p; rb=p /*将*p链到hb单链表未尾* ra=rb=NULL; /*两个尾结点的next域置空* 整个算法实际上是采用尾插法建表 (2)双链表基本运算的实现 重点:插入和删除结点的算法 (3)循环链表基本运算的实 重点:判断最后一个结点 第3章栈和队列 3.1栈 1.栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的 另一端称为栈底。当栈中没有数据元素时,称为空栈。栈的插入操作通常称为进栈或入栈,栈的删除操作通常 称为退栈或出栈。 2.栈的顺序存储结构及其基本运算实现 typedef struct ElemType elem[MaxSize] int top;/*栈指针*/ I SqStack 栈空条件:s-top=1 栈满条件:s->top== MaxSize-1 3.栈的链式存储结构及其基本运算的实现
while (i<A.length && AS.elem[i]<x) i++; for (j=A.length-1;j>=i;j--) A.elem[j+1]=A.elem[j]; A.elem[i]=x; A.length++; } 2.线性表的链式存储结构—链表 定义单链表结点类型: typedef struct LNode { ElemType data; struct LNode *next; /*指向后继结点*/ } LinkList; 定义双链表结点类型: typedef struct DNode { ElemType data; struct DNode *prior; /*指向前驱结点*/ struct DNode *next; /*指向后继结点*/ } DLinkList; （1）单链表基本运算的实现 重点：头插法建表和尾插法建表算法，它是很多算法设计的基础。 【例 2.1】 设 C={a1 ,b1 ,a2 ,b2 ,…,an ,bn }为一线性表，采用带头结点的 hc 单链表存放，编写一个就地算法， 将其拆分为两个线性表，使得： A={a1 ,a2 ,…,an }，C={b1 ,b2 ,…,bn } void fun(LinkList *hc, LinkList *&ha,LinkList *&hb) { LinkList *p=hc->next,*ra,*rb; ha=hc; /*ha 的头结点利用 hc 的头结点*/ ra=ha; /*ra 始终指向 ha 的末尾结点*/ hb=(LinkList *)malloc(sizeof(LinkList)); /*创建 hb 头结点*/ rb=hb; /*rb 始终指向 hb 的末尾结点*/ while (p!=NULL) { ra->next=p;ra=p; /*将*p 链到 ha 单链表未尾*/ p=p->next; if (p!=NULL) { rb->next=p;rb=p; /*将*p 链到 hb 单链表未尾*/ p=p->next; } } ra=rb=NULL; } /*两个尾结点的 next 域置空*/ 整个算法实际上是采用尾插法建表。 （2）双链表基本运算的实现 重点：插入和删除结点的算法。 （3）循环链表基本运算的实现 重点：判断最后一个结点。 第 3 章 栈和队列 3.1 栈 1.栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。表的 另一端称为栈底。当栈中没有数据元素时，称为空栈。栈的插入操作通常称为进栈或入栈，栈的删除操作通常 称为退栈或出栈。 2.栈的顺序存储结构及其基本运算实现 typedef struct { ElemType elem[MaxSize]; int top; /*栈指针*/ } SqStack; 栈空条件:s->top==-1 栈满条件:s->top==MaxSize-1 3.栈的链式存储结构及其基本运算的实现
typedef struct linknode ElemType data;/*数据域* struct linknode*next;/*指针域*/ t LiStack 带头结点的单链表来实现(也可不带头结点) head 头结点栈顶结点 栈空条件:s->next=NULL 栈满条件:? 3.2队列 1.队列的定义 队列简称队,它也是一种运算受限的线性表,其限制仅允许在表的一端进行插入,而在表的另一端进行 删除。进行插入的一端称做队尾(rear),进行删除的一端称做队首( front)。 2.队列的顺序存储结构及其基本运算的实现 ypedef struct ElemType elem[MaxSize] nt front,rear;/*队首和队尾指针* 把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循 环队列 循环队列首尾相连,当队首指针 front= Maxsize-1后,再前进一个位置就自动到0,这可以利用除法 取余的运算(%来实现 队首指针进1: front=( front+1)% Maxsiz 队尾指针进1:rear=(rear+1)% Maxsize 队空条件: g->rear==q) front 队满条件:( g->rear+1)% MaxSize=q- front 3.队列的链式存储结构及其基本运算的实现 struct gnode i Elem Type data )n. struct gnode *next typedef struct I QNode *front QNode *rear 第4章串 1.串的定义 串(或字符串),是由零个或多个字符组成的有穷序列。含零个字符的串称为空串,用中表示。串中所含字 符的个数称为该串的长度(或串长) 2.串的顺序存储结构一顺序串 3.串的链式存储结构一链串 KP算法不作要求 第5章数组和稀疏矩阵 1.数组的定义 数组是n(n>1)个相同类型数据元素 构成的有限序列,且该有限序列存储在一块地址连续的内存单元中 2.数组的顺序存储结构
typedef struct linknode { ElemType data; /*数据域*/ struct linknode *next; /*指针域*/ } LiStack; 带头结点的单链表来实现(也可不带头结点) 栈空条件:s->next==NULL 栈满条件:? 3.2 队列 1.队列的定义 队列简称队，它也是一种运算受限的线性表，其限制仅允许在表的一端进行插入，而在表的另一端进行 删除。进行插入的一端称做队尾（rear），进行删除的一端称做队首（front）。 2.队列的顺序存储结构及其基本运算的实现 typedef struct { ElemType elem[MaxSize]； int front,rear；/*队首和队尾指针*/ } SqQueue； 把数组的前端和后端连接起来，形成一个环形的顺序表，即把存储队列元素的表从逻辑上看成一个环，称为循 环队列。 循环队列首尾相连，当队首指针 front=MaxSize-1 后，再前进一个位置就自动到 0，这可以利用除法 取余的运算(％)来实现： 队首指针进 1：front=(front+1)％MaxSize 队尾指针进 1：rear=(rear+1)％MaxSize 队空条件：q->rear==q->front 队满条件：(q->rear+1) % MaxSize==q->front 3.队列的链式存储结构及其基本运算的实现 struct qnode { ElemType data; struct qnode *next; } QNode; typedef struct { QNode *front; QNode *rear; } LiQueue; 第 4 章 串 1.串的定义 串（或字符串)，是由零个或多个字符组成的有穷序列。含零个字符的串称为空串，用Ф表示。串中所含字 符的个数称为该串的长度（或串长）。 2.串的顺序存储结构－顺序串 3.串的链式存储结构－链串 KMP 算法不作要求。 第 5 章 数组和稀疏矩阵 1. 数组的定义 数组是 n（n＞1）个相同类型数据元素 a1，a2，…，an 构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。 2.数组的顺序存储结构 … lhead a1 a2 an ∧ 头结点 栈顶结点 栈底结点
对于数组A[c1…d1,c2..d2], 以行序为主序 L0C(a,j)=LOC(acl,ce2)+[(i-c1)*(d2-c2+1)+(-c2)】*k 以列序为主序 L0Ca,j)=L0(acl,c2)+[(j-c2)*(d1-c1+1)+(1-c1)]喇 3.特殊矩阵的压缩存储 (1)对称矩阵 若一个n阶方阵Amm中的元素满足ai,j=aj,i(0≤i,j≤n1),则称其为n阶对称矩阵。 A[O.n-1][0..n-1]-B[0..n(an+1)/2] i(i+1)/2+j 当i≥j时 j(j+1)/2+i 当i<j时 (2)三角矩阵 采用类似的压缩方法 4.稀疏矩阵 (1)三元组表示 (2)十字链表表示 各种表示的基本思路 则1oc(A[2][2])为多少? 答:Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=10m长度为2, 【例5.1】二维数组A[4][4](即A[0..3][0..3])的元素起始地址是1oc(A[O][0])=1000,元素的长度为2, 第6章树和二叉树 6.1树 1.树的定义 树是由n(n≥0)个结点组成的有限集合(记为T)。其中, 如果n=0,它是一棵空树,这是树的特例; 如果n>0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分 为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根 root的子树 2.树的表示法(逻辑表示方法 (1)树形表示法 (2)文氏图表示法 (3)凹入表示法 (4)括号表示法 3.树的遍历 先根遍历算法为 (1)访问根结点 (2)按照从左到右的次序先根遍历根结点的每一棵子树 后根遍历算法为 (1)按照从左到右的次序后根遍历根结点的每一棵子树 (2)访问根结点 4.树(森林)与二叉树之间的相互转换 6.2二叉树 1.二叉树的定义 叉树也称为二次树或二分树,它是有限的结点集合,这个集合或者是空,或者由一个根结点和两棵互不 相交的称为左子树和右子树的二叉树组成。 完全二叉树,满二叉树的定义 2.二叉树性质 性质1非空二叉树上叶结点数等于双分支结点数加1。即n0=n2+1 性质2非空二叉树上第i层上至多有21-1个结点(i≥1) 质3高度为h的二叉树至多有2-1个结点(h≥1) 性质4完全二叉树的性质 性质5具有n个(n>0)结点的完全二叉树的高度为1og2n+1或 loggn+1 【例6.1】将一棵有100个结点的完全二叉树从根这一层开始,每一层从左到右依次对结点进行编号,根结点 的编号为1,则编号为49的结点的左孩子编号为
对于数组 A[c1 ..d1 ,c2 ..d2 ] , 以行序为主序 : LOC(ai,j)=LOC(ac1,c2)+[(i-c1 )*(d2 -c2 +1)+(j-c2 )]*k 以列序为主序 LOC(ai,j)=LOC(ac1,c2)+[(j-c2 )*(d1 -c1 +1)+(i-c1 )]*k 3.特殊矩阵的压缩存储 (1) 对称矩阵 若一个 n 阶方阵 A[n][n]中的元素满足 ai,j=aj,i（0≤i，j≤n-1），则称其为 n 阶对称矩阵。 A[0..n-1][0..n-1]->B[0..n(n+1)/2] i(i+1)/2 +j 当 i≥j 时 k= j(j+1)/2 +i 当 i＜j 时 (2)三角矩阵 采用类似的压缩方法. 4.稀疏矩阵 (1) 三元组表示 (2) 十字链表表示 各种表示的基本思路。 【 例 5.1】 二维数组 A[4][4]（即 A[0..3][0..3]）的元素起始地址是 loc(A[0][0])=1000，元素的长度为 2， 则 loc(A[2][2])为多少？ 答：Loc(A[2][2])=Loc(A[0][0])+[(2-0)*(3-0+1)+(2-0)]*2=1020。 第 6 章 树和二叉树 6.1 树 1.树的定义 树是由 n（n≥0）个结点组成的有限集合（记为 T）。其中， 如果 n=0，它是一棵空树，这是树的特例； 如果 n>0，这 n 个结点中存在（有仅存在）一个结点作为树的根结点，简称为根（root），其余结点可分 为 m （m>0）个互不相交的有限集 T1 ,，T2，…，Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根 root 的子树。 2.树的表示法 (逻辑表示方法) (1) 树形表示法 (2) 文氏图表示法 (3) 凹入表示法 (4) 括号表示法 3.树的遍历 先根遍历算法为： （1）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。 后根遍历算法为： （1）按照从左到右的次序后根遍历根结点的每一棵子树； （2）访问根结点。 4.树(森林)与二叉树之间的相互转换 6.2 二叉树 1.二叉树的定义 二叉树也称为二次树或二分树，它是有限的结点集合，这个集合或者是空，或者由一个根结点和两棵互不 相交的称为左子树和右子树的二叉树组成。 完全二叉树,满二叉树的定义 2.二叉树性质 性质 1 非空二叉树上叶结点数等于双分支结点数加 1。即 n0=n2+1. 性质 2 非空二叉树上第 i 层上至多有 2 i-1 个结点（i≥1）。 性质 3 高度为 h 的二叉树至多有 2 h-1 个结点（h≥1） 。 性质 4 完全二叉树的性质 。 性质 5 具有 n 个（n＞0）结点的完全二叉树的高度为 log2 n+1 或 log2 n+1。 【例 6.1】将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点 的编号为 1，则编号为 49 的结点的左孩子编号为
A.98B.99C.50D.48 答:A 【例6.2】深度为5的二叉树至多有个结点。 16B.32C.31D.10 容:相同满度时满二叉树结点最多,h=5的满二叉树结点个数=25-1=31。本题答案应为C。 3.二叉树存储结构 1)二叉树的顺序存储结构 (2)二叉链存储结构 typedef struct /*数据元素*/ struct node *k *指向左孩子*/ struct node* rchild:/指向右孩子*/ BTNode 4二叉树的遍历 1)先序遍历 void preorder (BTNode *t) printf(“%d”,t->data) preorder(t->child) (2)中序遍历 oid inorder btnode *t) I inorder(t->lchild) printf(“%d”,t->data) inorder(t->rchild):I (3)后序遍历 void postorder(BTNode t) i postorder(t->lchild) postorder(t->rchild printf(“%d”,t->data);} 注意:重点掌握基于遍历的递归算法设计 5.二叉树的构造 任何n(n≥0)个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定 任何n(n≥0)个不同结点的二又树,都可由它的中序序列和后序序列惟一地确定 掌握它们的构造方法。 6.线索二叉树 (1)线索二叉树的概念 对于具有n个结点的二叉树,采用二叉链存储结构时,每个结点有两个指针域,总共有2n个指针域,又 由于只有n-1个结点被有效指针所指向(树根结点没有被有效指针域所指向),则共有2n-(n-1)=n+1个空链域 遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这样 的指向该线性序列中的“前驱”和“后继”的指针,称作线索。 对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行线索化。 (2)二叉树进行线索化的过程 不要求掌握算法。 6.3哈夫曼树 1.哈夫曼树的定义 在n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树称为哈夫曼树(或最优二叉树) 2.哈夫曼树的构造过程 3.哈夫曼编码的构造过程 第7章广义表 一个广义表中所含元素的个数称为它的长度 个广义表中括号嵌套的最大次数为它的深度
A.98 B.99 C.50 D.48 答：A 【例 6.2】 深度为 5 的二叉树至多有 个结点。 A.16 B.32 C.31 D.10 答：相同满度时满二叉树结点最多，h=5 的满二叉树结点个数=25-1=31。本题答案应为 C。 3.二叉树存储结构 （1）二叉树的顺序存储结构 （2）二叉链存储结构 typedef struct node { ElemType data; /*数据元素*/ struct node *lchild; /*指向左孩子*/ struct node *rchild; /*指向右孩子*/ } BTNode; 4.二叉树的遍历 （1） 先序遍历 void preorder（BTNode ＊t） { printf(“%d”,t->data); preorder(t->lchild); preorder(t->rchild); } （2） 中序遍历 void inorder（BTNode ＊t） { inorder(t->lchild); printf(“%d”,t->data); inorder(t->rchild); } （3）后序遍历 void postorder（BTNode ＊t） { postorder(t->lchild); postorder(t->rchild); printf(“%d”,t->data); } 注意：重点掌握基于遍历的递归算法设计。 5.二叉树的构造 任何 n（n≥0）个不同结点的二又树，都可由它的中序序列和先序序列惟一地确定。 任何 n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列惟一地确定。 掌握它们的构造方法。 6.线索二叉树 (1)线索二叉树的概念 对于具有 n 个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有 2n 个指针域，又 由于只有 n-1 个结点被有效指针所指向（树根结点没有被有效指针域所指向），则共有 2n-(n-1)=n+1 个空链域。 遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这样 的指向该线性序列中的“前驱”和“后继”的指针，称作线索。 对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行线索化。 (2) 二叉树进行线索化的过程 不要求掌握算法。 6.3 哈夫曼树 1.哈夫曼树的定义 在 n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树称为哈夫曼树（或最优二叉树） 。 2.哈夫曼树的构造过程 3.哈夫曼编码的构造过程 第 7 章 广义表 相关概念: 一个广义表中所含元素的个数称为它的长度. 一个广义表中括号嵌套的最大次数为它的深度