数据结构课程的主要内容Word文档下载推荐.docx
- 文档编号:7936986
- 上传时间:2023-05-09
- 格式:DOCX
- 页数:29
- 大小:52.34KB
数据结构课程的主要内容Word文档下载推荐.docx
《数据结构课程的主要内容Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构课程的主要内容Word文档下载推荐.docx(29页珍藏版)》请在冰点文库上搜索。
❑线性表的顺序表示(顺序存储结构)是指用一组地址连续的存储单元依次存放线性表的数据元素。
LOC(ai)=LOC(a1)+(i-1)*ll为每个元素所占的空间
❑线性表的顺序存储结构(顺序表)具有逻辑上相邻的元素,物理位置上也相邻的特点。
❑顺序表是一种随机存取的存储结构
❑通常用数组描述顺序表
❑顺序表的表示
structsqlist{#defineLEN100#defineLEN100
int*elem;
structsqlist{inta[LEN];
intlength;
inta[LEN];
intlistsize;
};
❑顺序表的操作
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次。
插入O(n)
(1)查找插入点的前趋结点p
(2)生成新结点s
(3)s->
next=p->
next;
(4)p->
next=s;
删除O(n)
p->
next
v建立含头结点的单链表(动态生成)
head=(structnode*)malloc(sizeof(structnode));
head->
next=NULL;
q=(structnode*)malloc(sizeof(structnode));
(1)顺序——从表头至表尾
设p为指向链表当前最后一个结点的指针
next=q;
p=q;
(2)逆序——从表尾至表头
q->
next=head->
(3)有序——递增或递减
循环链表
❑最后一个结点的指针域指向头结点,形成一个环。
❑空表:
head->
next=head;
双向链表
❑结点含两个指针域,分别指向直接前趋和后继。
❑p->
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->
top-1]
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);
front->
链队列判空
rear;
元素入队列
新生成结点s;
rear->
rear=s;
元素出队列(非空队列)
p=q->
if(q->
rear==p)q->
rear=q->
front
循环队列——队列的顺序表示和实现
typedefstruct
{intdata[MAX]
intfront,rear;
}SEQQUEUE;
SEQQUEUE*q;
头指针始终指向队列头元素,尾指针始终指向队列尾元素的下一个位置。
由于存在假溢出(q->
rear=MAX),可将顺序队列臆造成一个环状空间,称为循环队列。
队空和队满的判别条件相同:
front==q->
rear
两种处理办法:
(1)增设标志位
(2)少用一元素空间。
队空:
队满:
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;
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<
jk=j*(j-1)/2+i-1
✷上、下三角矩阵
矩阵的下(上)三角(不包括对角线)中的元均为常数或零的n阶矩阵。
只需存储上(下)三角中的元,再外加一个存储常数c的存储空间。
下三角矩阵:
当i>
当i<
jk=n*(n+1)/2+1
✷对角矩阵
所有的非零元素都集中在以主对角线为中心的带状区域中。
即除了主对角线上和主对角线邻近的上、下方以外,其余元素均为零。
–稀疏矩阵
✷在矩阵A(m*n)中,s为非零元素的个数,t为零元素的个数,若s<
<
t,则A为稀疏矩阵。
稀疏因子=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>
对任何一棵二叉树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);
rchild);
}}
♣中序遍历二叉树的递归算法(inorder)
中序遍历左子树->
中序遍历右子树
♣后序遍历二叉树的递归算法(postorder)
后序遍历左子树->
后序遍历右子树->
访问根
♣表达式的前缀表示(波兰式)、中缀表示和后缀表示(逆波兰式)。
♣将表达式表示为二叉树,若表达式=xy,则根结点存放运算符,左子树表示x,右子树表示y。
a+b*(c-d)-e/f
波兰式:
表达式二叉树的前序
中缀表示:
中序
逆波兰式:
后序
♣从递归执行过程的角度先序、中序和后序是完全相同的。
✹线索二叉树
遍历二叉树实质上是对一个非线性结构进行线性化操作,使得每个结点有且仅有一个前趋和后继。
但以二叉链表作为存储结构时,只能找到结点的左右儿子信息,而没有前趋和后继的信息。
由于在n个结点的二叉链表中必定存在n+1个空链域,可以利用空链域存放结点的前趋和后继的信息。
二叉链表的指针域描述儿子或前趋后继信息的链表为线索链表;
指向前趋和后继的指针为线索;
加上线索的二叉树为线索二叉树。
对二叉树以某种次序遍历使其变为线索二叉树的过程为线索化。
Typedefstructbtnode
{chardata;
structbtnode*lchild,*rchild;
intltag,rtag;
}BTNODE;
ltag=0lchild指示结点的左儿子
ltag=1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程 主要内容