大数据结构课程地主要内容.docx

大数据结构课程地主要内容.docx

《大数据结构课程地主要内容.docx》由会员分享，可在线阅读，更多相关《大数据结构课程地主要内容.docx（30页珍藏版）》请在冰点文库上搜索。

大数据结构课程地主要内容

数据结构课程的主要内容

✩数据结构的基本概念

Ø基本概念和术语

Ø算法和算法分析（典型算法）

✩线性表

Ø线性表的概念定义和特点

Ø线性表的实现——顺序表示和链式表示（特点、定义）

Ø线性表的基本操作——建立（正序、逆序、有序）、查找、插入、删除、输出

Ø线性表的应用——合并、时间复杂度

Ø循环链表和双向链表

✩栈和队列

Ø栈和队列的定义

Ø栈的表示、实现和操作（出栈、入栈）

Ø队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列）

✩串（串的基本概念和基本操作）

✩数组

Ø数组的定义

Ø数组的地址计算（一维、二维、三维）

Ø特殊矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏）

✩树和二叉树

Ø树的定义和基本术语

Ø二叉树

○二叉树的性质

○二叉树的存储结构

○二叉树的遍历

Ø树和森林

○树的存储结构

○树、森林与二叉树的转换

○树和森林的遍历

Ø哈夫曼树及其应用

✩图

Ø图的定义和术语

Ø图的存储结构

Ø图的遍历

✩查找

Ø查找的基本概念

Ø静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析

Ø动态查找表（二叉排序树和平衡二叉树）

Ø哈希表

✩排序（直接插入、冒泡、选择、快速和归并）

第一章数据结构课程的主要内容

（二）

线性表

Ø线性表的类型定义

❑线性表是n个（n0）数据元素的有限序列。

数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。

❑在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最后一个元素，除次之外，每个元素有唯一的前驱和唯一的后继。

❑线性表（a1,…,ai-1,ai,ai+1,…,an）

n为线性表的长度，i为元素在线性表中的位序。

❑线性表的操作：

建立空表、删除表、置空表、判空表、统计表长、查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用）

Ø线性表的顺序表示和实现——顺序表

❑线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单元依次存放线性表的数据元素。

LOC（ai）=LOC（a1）+（i-1）*ll为每个元素所占的空间

❑线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素，物理位置上也相邻的特点。

❑顺序表是一种随机存取的存储结构

❑通常用数组描述顺序表

❑顺序表的表示

structsqlist{#defineLEN100#defineLEN100

int*elem;structsqlist{inta[LEN];

intlength;inta[LEN];intlength;

intlistsize;intlength;

};};

❑顺序表的操作

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顺序表适用于不常进行插入、删除运算，表中元素相对稳定的场合。

Ø线性表的链式表示和实现——线性链表

❑线性表的链式存储结构是用一组任意的（可连续、也可不连续）存储单元存储线性表的数据元素。

❑为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其直接后继的信息。

即指针为数据元素之间逻辑关系的映象。

❑

结点包括两个域：

数据域和指针域（链），n个结点链接成一个（单）链表。

指示链表中第一个结点地址的指针称为头指针，最后一个结点的指针为空（NULL）。

单链表可由头指针唯一确定。

❑链表的表示

#defineNULL0

structnode{

intdata;

structnode*next;

};

structnode*head;/*head为头指针/

若head=NULL，则表示空表。

❑为处理方便，在单链表的第一个结点前附设一个结点，称为头结点。

此时，head->next指向第一个结点。

❑p指向第i个结点，则p->data=ai;p->next->data=ai+1;

❑单链表是一种非随机（顺序）存储结构。

❑单链表的操作

v查找第i个元素O（n）

指针p从指向第一个结点的位置（head->next）向后移动（p=p->next）i-1次。

v

插入O（n）

（1）查找插入点的前趋结点p

（2）生成新结点s

（3）s->next=p->next;（4）p->next=s;

删除O（n）

p->next=p->next->next

v建立含头结点的单链表（动态生成）

head=（structnode*）malloc（sizeof（structnode））;

head->next=NULL;

q=（structnode*）malloc（sizeof（structnode））;

（1）顺序——从表头至表尾

设p为指向链表当前最后一个结点的指针

p->next=q;p=q;

（2）逆序——从表尾至表头

q->next=head->next;head->next=q;

（3）有序——递增或递减

Ø循环链表

❑最后一个结点的指针域指向头结点，形成一个环。

❑空表：

head->next=head;

Ø双向链表

❑结点含两个指针域，分别指向直接前趋和后继。

❑p->next->priou=p->priou->next=p

❑双向循环链表

链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存储结构。

栈和队列

栈和队列是两种重要的线性结构。

从数据结构角度看，它们是操作受限的线性表。

Ø栈——后进先出的线性表（LIFO）

✧抽象数据类型的定义

栈是限定仅在表尾进行插入或删除操作的线性表。

表尾称为栈顶，表头称为栈底。

基本操作：

取栈顶元素（查找）、入栈（插入）和出栈（删除）a1a2……an-1an

栈底栈顶

✧栈的表示和实现

顺序栈——栈的顺序存储结构

利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置。

typedefstruct{

int*base;

int*top;

}sqstack;

#defineMAX100

Typedefstruct

{intstack[MAX]

inttop;

}SEQSTACK;

SEQSTACK*s;

构造空栈

s.top=s.bases->top=0

返回栈顶元素

e=*（s.top-1）e=s.stack[s.top-1]

入栈

*s.top++=es->stack[s->top]=e

s->top=s->top+1

出栈

e=*--s.tope=s->stack[s->top-1]

s->top=s->top-1

栈满

s.top-s.base=MAXs->top=MAX

链栈——栈的链式表示

栈顶指针为top

栈空top=NULL;

入栈

生成新结点s

s->link=top;top=s;

出栈

输出top->data;

top=top->link;

栈的应用举例intcheck（SEQSTACK*s）

数制转换{intbool;charch;

括号匹配的检验push（s,’#’）;bool=1;

行编辑程序ch=getchar（）;

表达式求值while（ch!

=‘\n’&&bool）

栈与递归{if（ch==‘（‘）push（s,ch）;

if（ch==‘）’）

if（gettop（s）==‘#’）bool=0;elsepop（s）;

ch=getchar（）;}

if（gettop（s）!

=‘#’）bool=0;/*’（’多于‘）’*/

if（bool）printf（“rigth”）;

elserintf（“error”）;}

Ø队列——先进先出的线性表（FIFO）

抽象数据类型队列的定义

队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进行删除操作的线性表。

基本操作：

入队列（插入）和出队列（删除）

出队列a1a2……an-1an入队列

队头队尾

链队列——队列的链式表示和实现

typedefstructqnode

{intdata;

structqnode*next;

}QNODE

typedefstruct{

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

循环队列——队列的顺序表示和实现

typedefstruct

{intdata[MAX]

intfront,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，用Ö表示。

Ø空格串——由一个或多个空格组成的串为空格串。

长度为空格字符的个数。

Ø串的基本操作：

通常以“串的整体”为操作对象。

Ø串赋值串复制

Ø求子串判空串

Ø串连接子串定位

Ø串比较串替换

Ø求串长串插入

Ø串清空串删除

Ó串的表示和实现

Ø定长顺序存储表示

为每个串变量分配一个固定长度地址连续的存储区。

#defineMAX255

unsignedcharsstring[MAX+1];

0号单元存放串的长度。

Ø堆分配存储表示

在程序执行过程中，为每个串变量动态分配（malloc）一个地址连续的存储区。

Ø串的块链存储表示

#defineCSIZE80//块的大小

typedefstructChunk{

charch[CSIZE];

structChunk*next;

}Chunk;

typedefstruct{

Chunk*head,*tail;//头尾指针

intcurlen;//串长度

}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=aji0<=i,j<=n-1

只需存储上三角或下三角元素。

存储元素总个数为

（1+2+…+n）=n*（n+1）/2

假设以行序为主序存储下三角中的元

当i>=jk=i*（i-1）/2+j-1

当i

✷上、下三角矩阵

矩阵的下（上）三角（不包括对角线）中的元均为常数或零的n阶矩阵。

只需存储上（下）三角中的元，再外加一个存储常数c的存储空间。

下三角矩阵：

当i>=jk=i*（i-1）/2+j-1

当i

✷对角矩阵

所有的非零元素都集中在以主对角线为中心的带状区域中。

即除了主对角线上和主对角线邻近的上、下方以外，其余元素均为零。

–稀疏矩阵

✷在矩阵A（m*n）中，s为非零元素的个数，t为零元素的个数，若s<

稀疏因子=t/（m*n）<=0.05。

✷由于稀疏矩阵的非零元素分布没有任何规律，压缩存储除了存储非零元素值外，还必须同时存储它的位置。

✷稀疏矩阵的每个非零元素由一个三元组（i，j，aij）唯一确定。

✷稀疏矩阵可由表示非零元的三元组及其矩阵的行列数唯一确定。

✷三元组的表示

–三元组顺序表

–行逻辑链接的顺序表

–十字链表

树和二叉树

♣树的定义和基本术语

♣树（tree）是n（n>=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个结点的存储空间。

♣链式存储结构——头指针指向根结点。

♣二叉链表——存储结点的一个数据元素和分别指向其左、右子树的两个指针。

♣三叉链表——增加一个指向双亲结点的指针域。

typedefstructtnode

{intdata;

structtnode*lchild,*rchild;

}TNODE;

TNODE*root;

在n个结点的二叉链表中有n+1个空链域。

♣建立二叉树

♣遍历二叉树和线索二叉树

遍历二叉树

♣遍历二叉树是指如何按某条搜索路径巡访树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。

（即将二叉树的结点排成一个线性队列）

♣一棵非空二叉树是由根结点、左子树和右子树三个基本部分组成，依次遍历这三部分，便能遍历整个二叉树。

若限定先左（L）后右（R），则遍历方法有先序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）三种。

♣先序遍历二叉树的递归算法

访问根->先序遍历左子树->先序遍历右子树

voidpreorder（TNODE*bt）

{if（bt!

=NULL）

{printf（“%d”,bt->data）;

preorder（bt->lchild）;

preorder（bt->rchild）;}}

♣中序遍历二叉树的递归算法（inorder）

中序遍历左子树->访问根->中序遍历右子树

♣后序遍历二叉树的递归算法（postorder）

后序遍历左子树->后序遍历右子树->访问根

♣表达式的前缀表示（波兰式）、中缀表示和后缀表示（逆波兰式）。

♣将表达式表示为二叉树，若表达式=xy，则根结点存放运算符，左子树表示x，右子树表示y。

a+b*（c-d）-e/f

波兰式：

表达式二叉树的前序

中缀表示：

中序

逆波兰式：

后序

♣从递归执行过程的角度先序、中序和后序是完全相同的。

✹线索二叉树

遍历二叉树实质上是对一个非线性结构进行线性化操作，使得每个结点有且仅有一个前趋和后继。

但以二叉链表作为存储结构时，只能找到结点的左右儿子信息，而没有前趋和后继的信息。

由于在n个结点的二叉链表中必定存在n+1个空链域，可以利用空链域存放结点的前趋和后继的信息。

二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表；指向前趋和后继的指针为线索；加上线索的二叉树为线索二叉树。

对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。

Typedefstructbtnode

{chardata;

structbtnode*lchild,*rchild;

intltag,rtag;

}BTNODE;

ltag