-*
数据结构课程的主要内容
数据结构的基本概念
基本概念和术语
算法和算法分析（典型算法）
线性表
线性表的概念定义和特点
线性表的实现——顺序表示和链式表示（特点、定义）
线性表的基本操作——建立（正序、逆序、有序）、查找、插入、删除、输出
线性表的应用——合并、时间复杂度
循环链表和双向链表
栈和队列
栈和队列的定义
栈的表示、实现和操作（出栈、入栈）
队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列）
串（串的基本概念和基本操作）
数组
数组的定义
数组的地址计算（一维、二维、三维）
特殊矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏）
树和二叉树
树的定义和基本术语
二叉树
○ 二叉树的性质
○ 二叉树的存储结构
○ 二叉树的遍历
树和森林
○ 树的存储结构
○ 树、森林与二叉树的转换
○ 树和森林的遍历
哈夫曼树及其应用
图
图的定义和术语
图的存储结构
图的遍历
查找
查找的基本概念
静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析
动态查找表（二叉排序树和平衡二叉树）
哈希表
排序（直接插入、冒泡、选择、快速和归并）
第一章 数据结构课程的主要内容（二）
线性表
线性表的类型定义
q 线性表是n个（n0)数据元素的有限序列。数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。
q 在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最后一个元素，除次之外，每个元素有唯一的前驱和唯一的后继。
q 线性表（a1,…,ai-1,ai,ai+1, …,an）
n为线性表的长度，i为元素在线性表中的位序。
q 线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用）
线性表的顺序表示和实现——顺序表
q 线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单元依次存放线性表的数据元素。
LOC(ai)=LOC(a1)+(i-1)*l l为每个元素所占的空间
q 线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素， 物理位置上也相邻的特点。
q 顺序表是一种随机存取的存储结构
q 通常用数组描述顺序表
q 顺序表的表示
struct sqlist{ #define LEN 100 #define LEN 100
int *elem; struct sqlist{ int a[LEN];
int length; int a[LEN]; int length;
int listsize; int length;
}; };
q 顺序表的操作
v 顺序表初始化
v 顺序表的插入
v 顺序表的删除 移动大量元素
v 顺序表的查找
v 线性表的插入(n+1)
a1,a2,…ai-1, ai, ai+1,…an 插入位置的判断(n+1) (q) (p) 元素移动的顺序和位置
a1,a2,…ai-1,b,ai,ai+1,…an 表长的变化
v 线性表的删除(n-1)
a1,a2,…ai-1,ai,ai+1,…an 删除位置的判断
(p) (q) 元素移动的顺序和位置
a1,a2,…ai-1, ai+1,…an 表长的变化
v 时间复杂度
求表长 O(1)
查找第i个元素、前趋、后继 O(1)
查找值为x的元素的位序 O(n)
插入元素 O(n)
(0+1+……+n)/(n+1)=n/2
删除元素 O(n)
(0+1+……+n-1)/n=(n-1)/2
v 顺序表适用于不常进行插入、删除运算，表中元素相对稳定的场合。
线性表的链式表示和实现——线性链表
q 线性表的链式存储结构是用一组任意的（可连续、也可不连续）存储单元存储线性表的数据元素。
q 为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其直接后继的信息。即指针为数据元素之间逻辑关系的映象。
……
h
q 结点包括两个域：数据域和指针域（链），n个结点链接成一个（单）链表。指示链表中第一个结点地址的指针称为头指针，最后一个结点的指针为空(NULL)。单链表可由头指针唯一确定。
q 链表的表示
#define NULL 0
struct node{
int data;
struct node *next;
};
struct node *head; /*head为头指针/
若head=NULL，则表示空表。
head
p->next
p
……
q 为处理方便，在单链表的第一个结点前附设一个结点，称为头结点。此时，head->next 指向第一个结点。
q p指向第i个结点，则p->data=ai; p->next->data=a i+1;
q 单链表是一种非随机（顺序）存储结构。
q 单链表的操作
v 查找第i个元素 O(n)
指针p从指向第一个结点的位置（head->next）向后移动（p=p->next）i-1次。
p->next
s
p
v 插入O(n)
（1）查找插入点的前趋结点p （2）生成新结点s
（3）s->next=p->next; （4）p->next=s;
p->next->next
p->next
p
删除O(n)
p->next=p->next->next
v 建立含头结点的单链表（动态生成）
head=(struct node *) malloc (sizeof(struct node));
head->next=NULL;
q=(struct node *) malloc (sizeof(struct node));
（1）顺序——从表头至表尾
设p为指向链表当前最后一个结点的指针
p->next=q; p=q;
（2）逆序——从表尾至表头
q->next =head->next; head->next=q;
（3）有序——递增或递减
循环链表
q 最后一个结点的指针域指向头结点，形成一个环。
q 空表：head->next=head;
双向链表
q 结点含两个指针域，分别指向直接前趋和后继。
q p->next->priou=p->priou->next=p
q 双向循环链表
链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存储结构。
栈和队列
栈和队列是两种重要的线性结构。从数据结构角度看，它们是操作受限的线性表。
栈——后进先出的线性表（LIFO）
抽象数据类型的定义
栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。
基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除） a1 a2 …… an-1 an
栈底 栈顶
栈的表示和实现
顺序栈——栈的顺序存储结构
利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置。
typedef struct {
int *base;
int *top;
}sqstack;
#define MAX 100
Typedef struct
{int stack[MAX]
int top;
}SEQSTACK;
SEQSTACK *s;
构造空栈
s.top = s.base s->top = 0
返回栈顶元素
e=*(s.top-1) e=s.stack[s.top-1]
入栈
*s.top++=e s->stack[s->top]=e
s->top=s->top+1
出栈
e=*--s.top e=s->stack[s->top-1]
s->top=s->top-1
栈满
s.top-s.base=MAX s->top=MAX
链栈——栈的链式表示
栈顶指针为top
栈空 top=NULL;
入栈
生成新结点s
s->link=top; top=s;
出栈
输出top->data;
top=top->link;
栈的应用举例 int check(SEQSTACK *s)
数制转换 {int bool; char ch;
括号匹配的检验 push(s,’#’); bool=1;
行编辑程序 ch=getchar();
表达式求值 while (ch!=‘\n’&&bool)
栈与递归 {if (ch==‘(‘) push(s,ch);
if (ch==‘)’)
if (gettop(s)==‘#’) bool=0; else pop(s);
ch=getchar(); }
if (gettop(s)!=‘#’) bool=0; /*’(’多于‘)’*/
if (bool) printf(“rigth”);
else rintf(“error”);}
队列——先进先出的线性表（FIFO）
抽象数据类型队列的定义
队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进行删除操作的线性表。
基本操作：入队列（插入） 和出队列（删除）
出队列 a1 a2 …… an-1 an 入队列
队头 队尾
链队列——队列的链式表示和实现
typedef struct qnode
{int data;
struct qnode *next;
}QNODE
typedef struct {
QNODE *front, *rear;
}LINKQUEUE;
LINKQUEUE *q;
链队列初始化
q->front=q->rear=(QNODE*)malloc(QNODE);
q->front->next=NULL;
链队列判空
q->front=q->rear;
元素入队列
新生成结点s; s->next=NULL;
q->rear->next=s; q->rear=s;
元素出队列（非空队列）
p=q->front->next; q->front->next=p->next
if (q->rear==p) q->rear=q->front
循环队列——队列的顺序表示和实现
typedef struct
{int data[MAX]
int front,rear;
}SEQQUEUE;
SEQQUEUE *q;
头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。
由于存在假溢出(q->rear=MAX)，可将顺序队列臆造成一个环状空间，称为循环队列。
队空 和队满的判别条件相同：
q->front==q->rear
两种处理办法:
(1)增设标志位
(2)少用一元素空间。
队空： q->front==q->rear
队满： q->front==(q->rear+1)%MAX
串
串类型的定义
串（String）（或字符串）是由零个或多个字符组成的有限序列。记为：s=’a1a2…an’(n0)
S为串名，单引号括起来的字符序列是串的值，n为串的长度。
子串——主串中任意个连续字符组成的子序列。
位置——字符在序列中的序号为该字符在串中的位置。子串在 主串中的位置以子串的第一个字符在主串中位置来表示。
串相等——两个串的长度相等，且每个对应位置的字符都相等。
空串——零个字符的串为空串，长度为0，用表示。
空格串——由一个或多个空格组成的串为空格串。长度为空格字符的个数。
串的基本操作：通常以“串的整体”为操作对象。
串赋值 串复制
求子串 判空串
串连接 子串定位
串比较 串替换
求串长 串插入
串清空 串删除
串的表示和实现
定长顺序存储表示
为每个串变量分配一个固定长度地址连续的存储区。
#define MAX 255
unsigned char sstring[MAX+1];
0号单元存放串的长度。
堆分配存储表示
在程序执行过程中，为每个串变量动态分配（malloc) 一个地址连续的存储区。
串的块链存储表示
#define CSIZE 80 //块的大小
typedef struct Chunk {
char ch[CSIZE];
struct Chunk *next;
}Chunk;
typedef struct {
Chunk *head,*tail; //头尾指针
int curlen; //串长度
}Lstring;
数 组
数组的定义
– 数组的性质
数组元素数目固定，一旦定义，维数和维界就不再改变。
数组元素具有相同的类型。
数据元素的下标关系具有上下界的约束并且下标有序。
– 数组的描述
ji=0，…，bi-1, i=1,2,…,n, bi是数组第i维的长度
D={aj1j2…jn|n(>0)为数组的维数，ji是数组元素的第i维下标}
n=1表示一维数组，是线性表。
n=2表示二维数组，以矩阵形式表示，它也可以看成是线性表，其中每个数据元素本身又是一个线性表。
– 数组的基本操作
初始化数组
销毁数组
取元素——给定一组下标，返回相应的数组元素值。
修改元素值（赋值）——给定一组下标，修改相应的数组元素的值。
数组的顺序表示和实现
– 数组运算通常是随机访问与修改，一般不作插入或删除，故一旦建立数组，数据元素的个数与元素之间的关系就不再发生变动，所以数组采用顺序存储结构表示。
– 存储单元是一维结构，而数组是多维结构，用一组地址连续的存储单元存放数组元素有次序约定的问题。
– 对于数组，一旦规定了它的维数和各维的长度（下标的界限），就可分配空间，并根据给定的一组下标求得相应数组元素的存储位置。
– 一维数组 LOC(ai)=LOC(a0)+i*L
– 二维数组(m*n)
行序为主序
（a00,a01,…,a0,n-1,a10,a11,……am-1,n-1)
LOC(i,j)=LOC(0,0)+(i*n+j)*L
列序为主序
（a00,a10,…,am-1,0),a01,a11,……am-1,n-1)
LOC(i,j)=LOC(0,0)+(j*m+i)*L
– 三维数组(m*n*p)
左下标（行）为主序
（a000,a001,…a00,p-1,a010,……am-1,n-1,p-1)
LOC(i,j,k)=LOC(0,0,0)+(i*n*p+j*p+k)*L
右下标（列）为主序
– 多维数组（b1*b2*…*bn)
LOC(j1,j2…,jn)=LOC(0,0,…,0)+
(j1*b2*…*bn+j2*b3*…*bn+jn-1*bn+jn)*L
– 若确定了数组的各维长度，则bl*…*bn为常数，数组元素的存储位置是其下标的线性函数，由于存取数组中任一元素的时间相等，故此结构为随机存储结构。
矩阵的压缩存储
– 若矩阵阶数很高，且矩阵中有许多值相同的元素或者零元素，为节省存储空间，对矩阵进行压缩存储，即为多个值相同的元只分配一个存储空间，对零元不分配空间
– 假若值相同的元素或者零元素在矩阵中的分布有一定的规律，这类矩阵为特殊矩阵，否则为稀疏矩阵。特殊矩阵可将非零元压缩存储到一维数组中，并找到每个非零元在一维数组中的对应关系。
– 特殊矩阵
N阶对称矩阵—元素关于主对角线对称
aij=aji 0<=i,j<=n-1
只需存储上三角或下三角元素。
存储元素总个数为
（1+2+…+n)=n*(n+1)/2
假设以行序为主序存储下三角中的元
当i>=j k=i*(i-1)/2+j-1
当i
=j k=i*(i-1)/2+j-1
当i=0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根(root)的结点；（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2……Tm，其中每一个集合本身又是一棵树，称为根的子树。
树的基本操作
建树 求孩子结点
求根结点 求兄弟结点
求双亲结点 结点的插入、删除
树的表示形式
树形表示
嵌套集合表示
广义表表示
凹入表表示
基本术语
树的结点——指一个数据元素及若干指向其子树的分支。通常以结构体来描述。
结点的度——结点拥有的子树数。度为0的结点称为叶子或终端结点；度不为0的结点称为非终端结点或分支结点。
树的度——树内各结点度的最大值。
孩子和双亲——结点的子树的根为该结点的孩子，该结点为孩子的双亲。
结点的层次——根为第一层，依次类推。
兄弟和堂兄弟——双亲相同的结点为兄弟，双亲在同一层次的结点为堂兄弟。
祖先和子孙——从根到该结点所经分支上的所有结点为该结点的祖先；以某结点为根的子树中的任一结点都称为该结点的子孙。
树的深度(高度)——树中结点的最大层次。
有序树和无序树——如果将树中结点的各子树看成从左到右是有次序的（即不能交换），则称该树为有序树，否则为无序树。
森林——是m（m>=0)个棵互不相交的树的集合。
二叉树
二叉树的定义
二叉树的每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。
二叉树的基本操作
建树（空树、非空树）
求根结点、双亲、孩子、兄弟结点
二叉树的遍历
插入、删除
二叉树的五种基本形态
空二叉树
仅有根结点的二叉树
左子树为空的二叉树
右子树为空的二叉树
左、右子树均非空的二叉树
二叉树的性质
在二叉树的第i层上至多有2i-1个结点（i>=1)
深度为k的二叉树至多有2k-1个结点（k>=1)
对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1
一棵深度为k且有2k-1个结点的二叉树称为满二叉树，其每一层上的结点数都是最大结点数。可以对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。深度为k的，有n个结点的二叉树，当且仅当其每个结点都与深度为k的满二叉树中编号从1至n结点一一对应时，称之为完全二叉树。
具有n个结点的完全二叉树的深度为 k=[log2n]+1
如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i（i<=1<=n)
(1)i=1，结点i为二叉树的根；若i>1，则双亲结点是[i/2]
(2)如果2i>n，则结点无左孩子；否则其左孩子是结点2i。
(3)如果2i+1>n，则结点无右孩子；否则其右孩子是结点2i+1。
二叉树的存储结构
顺序存储结构
用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即完全二叉树上编号为i的结点存储在一维数组中下标为i-1的分量中。对一般二叉树，顺序存储结构必须能反映结点之间的逻辑关系（父子关系），故将其每个结点与完全二叉树相 对照进行存储。
这种顺序存储结构仅适用于完全二叉树。最坏情况下，k个结点、深度为k的二叉树需要2k-1个结点的存储空间。
链式存储结构——头指针指向根结点。
二叉链表——存储结点的一个数据元素和分别指向其左、右子树的两个指针。
三叉链表——增加一个指向双亲结点的指针域。
typedef struct tnode
{int data;
struct tnode *lchild, *rchild;
}TNODE;
TNODE *root;
在n个结点的二叉链表中有n+1个空链域。
建立二叉树
遍历二叉树和线索二叉树
遍历二叉树
遍历二叉树是指如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。(即将二叉树的结点排成一个线性队列)
一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，依次遍历这三部分，便能遍历整个二叉树。若限定先左（L）后右（R），则遍历方法有先序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）三种。
先序遍历二叉树的递归算法
访问根->先序遍历左子树->先序遍历右子树
void preorder(TNODE *bt)
{ if (bt!=NULL)
{printf(“%d ”,bt->data);
preorder(bt->lchild);
preorder(bt->rchild);}}
中序遍历二叉树的递归算法（inorder)
中序遍历左子树->访问根->中序遍历右子树
后序遍历二叉树的递归算法(postorder)
后序遍历左子树->后序遍历右子树->访问根
表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。
将表达式表示为二叉树，若表达式=xqy，则根结点存放运算符，左子树表示x，右子树表示y。
a+b*(c-d)-e/f
波兰式：表达式二叉树的前序
中缀表示：中序
逆波兰式：后序
从递归执行过程的角度先序、中序和后序是完全相同的。
线索二叉树
遍历二叉树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。但以二叉链表作为存储结构时，只能找到结点的左右儿子信息，而没有前趋和后继的信息。由于在n个结点的二叉链表中必定存在n+1个空链域，可以利用空链域存放结点的前趋和后继的信息。
二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索；加上线索的二叉树为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。
Typedef struct btnode
{char data;
struct btnode *lchild, *rchild;
int ltag, rtag;
}BTNODE;
ltag=0 lchild指示结点的左儿子
ltag=1 lchild指示结点的前趋
rtag=0 lchild指示结点的右儿子
rtag=1 lchild指示结点的后继
树和森林
树的存储结构
双亲表示法
用一组地址连续的空间存放树中的结点，每个结点存放本身的信息和双亲结点所在的位置序号。
孩子表示法
多重链表——每个结点有多个指针域，分别指向其每个子树。同构或不同构。
孩子链表 ——每个结点有一个孩子链表，n个结点链表的头指针顺序存储。
孩子双亲表示法——双亲表示和孩子链表表示法结合起来。
孩子兄弟表示法——二叉链表表示法*****
二叉链表作为树的存储结构，链表中的两个指针域分别指向该结点的第一个孩子和该结点的下一个兄弟。
树、森林与二叉树的转换
以二叉链表作为转换的依据。
树转化成二叉树后，二叉树根一定没有右子树。
森林的第二棵树树根看成是第一棵树树根的兄弟。
树与森林的遍历
树的先序遍历是指先访问树的根结点，然后依次先序遍历根的各子树。等价于先序遍历该树对应的二叉树。
树的后序遍历是指先依次后序遍历树的根结点的各子树，然后访问根结点。等价于中序遍历该树对应的二叉树。
先序遍历森林是指从左到右依次按先序遍历森林中的每一棵树，相当于先序遍历该森林对应的二叉树。
后序遍历森林是指从左到右依次按后序遍历森林中的每一棵树，相当于中序遍历该森林对应的二叉树。
赫夫曼树及其应用
最优二叉树——赫夫曼树
从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，记作WPL。
假设有n个权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。
赫夫曼算法——构造赫夫曼树
根据给定的n个权值构成n棵二叉树的集合F，每棵二叉树Ti只有一个带权为wi的根结点。
在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新二叉树，其根结点的权值为左右子树根结点的权值之和。
在F中删除这两棵树，将新二叉树加入F
重复构造，直到 F中只含一棵树为止，这棵树就是赫夫曼树。
赫夫曼编码——电报码
电文的总长尽可能短——出现次数多的字符采用尽可能短的编码。
任一个字符的编码都不是另一个字符编码的前缀——前缀编码。
设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题。
约定赫夫曼树的左分支表示字符‘0’，右分支表示字符‘1’，从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点字符的编码。
图
图是复杂的非线性结构，结点之间的关系是任意的，任何两个数据元素都可能相关。图的应用极为广泛。
l 图的定义和术语
l 图是两个集合的二元组，G=（V，E），V表示顶点的有穷非空集合，E是顶点之间关系的有穷集合。
l 若图中的每条边都是有方向的，顶点之间的关系表示从v到w的一条弧，v为弧尾或初始点，w为弧头或终端点，该图为有向图。
l 若图中的每条边无方向，有必有，顶点之间的关系以无序对表示，表示从v到w的一条边，该图为无向图。
l n表示图中顶点数目，e表示边或弧的数目，若不考虑顶点自身的边或弧，无向图e的取值范围是0~n(n-1)/2，具有n(n-1)/2条边的无向图为完全图；有向图e的取值范围是0~n(n-1)，具有n(n-1) 条边的有向图为有向完全图。有很少条边或弧(e
展开阅读全文
相关搜索