数据结构总结课件

封面1.什么是数据结构

2.数据结构研究什么内容

3.数据结构处理软件开发过程中的什么问题

4.《数据结构与算法》在软件技术专业课程体系中占有什么地位本学期的任务1学习图状结构及其应用2学习集合结构及其应用3学习常用算法，并选用常用算法解决问题穷举法分治法动态规划贪心法回溯法分枝限界法线性表例2人机对奕问题树……..……..…...…...…...…...竞赛项目的时间安排问题图数据结构定义:数据的集合，以一定的逻辑关系组织在一起，以某种方式存储在计算机的存储器中，并在这些数据上定义了某些相应运算。这种结构成为数据结构数据的逻辑结构—只抽象反映数据元素的逻辑关系数据的存储（物理）结构—数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关 算法设计 逻辑结构 算法实现 存储结构 存储结构分为：顺序存储结构——借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构——借助指示元素存储地址的指针表示数据元素间的逻辑关系1536元素21400元素11346元素3∧元素41345h存储地址

存储内容

指针1345

元素1

14001346

元素4∧

…….

……..

…….

1400

元素21536

…….

……..

…….1536

元素31346

链式存储

h数据类型—高级语言中指数据的取值范围及其上可进行的操作的总称例C语言中，提供int,char,float,double等基本数据类型，数组、结构体、共用体、枚举等构造数据类型，还有指针、空(void)类型等。用户也可用typedef自己定义数据类型typedefstruct{intnum;charname[20];floatscore;}STUDENT;STUDENTstu1,stu2,*p;算法描述算法的时间复杂度:以算法中基本操作重复执行的次数作为算法的时间度量。例:(a)x=x+1; O(1)(b)for(i=0;i<n;i++)x=x+1; O(n)(c)for(i=1;i<n;i++)for(j=1;j<i;j++)x=x+1; O(n2)1.2线性表和数组

1.2.1线性表及其顺序存储结构一、线性表的逻辑结构线性表由n(n≥0)个数据元素a1,a2,...,an构成的有限序列记作:L＝(a1,a2,...,an)其中，a1称为首元素，an称为尾元素。表的长度(表长)

线性表中数据元素的数目。空表

不含数据元素的线性表(n=0)。一、线性表的逻辑结构线性表(a1,a2,...,an)的特征:直接前驱

ai－1在ai之前，称ai－1是ai的直接前驱(1＜i≤n)直接后继

ai＋1在ai之后，称ai＋1是ai的直接后继(1≤i＜n)a1没有前驱an没有后继。ai(1＜i＜n)有且仅有一个直接前驱和一个直接后继一、线性表的逻辑结构线性表L＝(a1,a2,...,an)的运算1)initiate(L)初始化L为空表2)length(L)求长度3)get(L,i)取元素ai4)prior(L,elm)求前驱函数5）next(L,elm)求后继函数6）locate(L,x)定位函数7）insert(L,i,x)在元素ai之前插入新元素ｘ8)delete(L,i)删除第i个数据元素9)empty(L)判空表函数10)clear(L)表置空函数二、线性表的顺序存储结构插入一个元素┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4│17│20│25│35│40│││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789||

插入8n┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4││17│20│25│35│40││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789||

插入8n┌─┬─┬─┬─┬─┬─┬─┬─┬─┐│2│4│8│17│20│25│35│40││└─┴─┴─┴─┴─┴─┴─┴─┴─┘123456789||

插入8之后n二、线性表的顺序存储结构算法分析假设在线性表的第ｊ个位置插入一个元素的概率为Pj，ｎ是线性表的长度,1≤ｊ≤n,那么每插入一个元素所需移动元素数目的期望值(平均数目)是：

其中，n-j+1表示在第ｊ个元素之前插入一个新元素必须移动n-j+1个元素。假定在表的任意位置ｊ(1≤j≤n)插入元素的概率相等,即Ｐｊ＝1/n,那么移动元素的期望值为：二、线性表的顺序存储结构顺序存储结构的评价(1)优点

a)存取结构简单，存取任意元素的时间是一个常数，存取速度快

b)不使用指针，存储密度大。(2)缺点

a)需请求分配一个连续存储块；

b)插入可能发生溢出；

c)为了防止溢出，需保留一个较大的连续存储块，造成浪费；

d)插入和删除需移动大量数据元素。1.2.2线性表的链式存储结构

一、单链表单链表的结点结构

data结点类型说明:

structnode{element；

structnode*next;}1.2.2线性表的链式存储结构

一、单链表思考：若删除尾结点C情况如何？1.2.2线性表的链式存储结构

一、单链表1.2.2线性表的链式存储结构

一、单链表1.2.2线性表的链式存储结构

一、单链表带表头结点的单链表的一般形式

若head->next≠NULL，则为非空单链表；

若head->next＝NULL，则为空单链表。

1.2.2线性表的链式存储结构

一、单链表带表头结点的循环单链表的一般形式若head->next≠head，则为非空循环单链表；

若head->next＝head，则为空循环单链表。

二、双向链表双向链表的结点结构

结点类型说明:

structnodedou{elementdata；

structnodedou*llink;structnodedou*rlink;}二、双向链表带表头结点的双向链表

(1)非空表(首结点的左指针为空，尾结点的右指针为空)

h┌──────────────────────────┐┌──┐┌┼┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐││─┼→┤│││─┼→┤∧│a1│─┼→....→┤│an│∧├←┘│││││││││├←←┼─│││└──┘└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘

头指针表头结点首结点尾结点

(2)空表

h┌──┐┌─┬─┬─┐│─┼→┤∧││∧│││││││└──┘└─┴─┴─┘

头指针表头结点1.2.3数组及其顺序存储

一、组和数组的运算对数组的运算:

(1)给定一个有定义的下标组，访问与其对应的数组元素。(2)给定一个有定义的下标组，存取或修改与其对应的数组元素。

1.2.3数组及其顺序存储

一、组和数组的运算

例二维数组:┌┐│ａ11ａ12││ａ21ａ22││ａ31ａ32││ａ41ａ42│└┘(1)以行序为主序的顺序存储方式:┌──┬──┬──┬──┬──┬──┬──┬──┐│ａ11│ａ12│ａ21│ａ22│ａ31│ａ32│ａ41│ａ42│└──┴──┴──┴──┴──┴──┴──┴──┘

序号:12345678(2)以列序为主序的顺序存储方式:┌──┬──┬──┬──┬──┬──┬──┬──┐│ａ11│ａ21│ａ31│ａ41│ａ12│ａ22│ａ32│ａ42│└──┴──┴──┴──┴──┴──┴──┴──┘

序号:123456781.3栈和队列

1.3.1栈定义和术语(1)栈(stack):只允许在表的一端插入和删除元素的线性表。(2)栈顶(top):线性表中允许进行插入和删除的一端。(3)栈底(bottom):线性表中不允许进行插入和删除的一端。(4)栈顶元素:位于栈顶的元素。(5)栈底元素:位于栈底的元素。(6)空栈:不含元素的栈。(7)进栈(push,下推,压入):插入一个新元素到栈中。(8)退栈(POP,弹出):删除栈顶元素。(9)栈中元素的进出原则:后进先出(LastInFirstOut)。(10)栈的别名:“后进先出表”或“LIFO”表

<───┐┌───

退栈│↑↓│进栈││├──┤││4├──┤top→│Ｃ│3栈顶元素Ｃ├──┤│Ｂ│2├──┤bottom│Ａ│1栈底元素Ａ└──┘栈的图示1.3.1栈

一、栈的定义栈的基本操作(1)init(s)初始化，将栈ｓ设置为空栈(2)empty(s)判断栈ｓ是否为空栈(3)push(s,x)将元素ｘ压入栈ｓ中(4)pop(s)弹出栈ｓ的顶元素(5)gettop(s)读取栈顶元素(6)clear(s)栈置空操作(7)length(s)求当前栈中元素的个数

一、栈的定义例由输入(A,B,C),得输出(C,B,A)的操作

A,B,CC,B,A<───┐┌───<───┐┌───<───┐┌───

退栈│↑↓│进栈│↑↓││↑↓│├──┤├──┤├──┤

3││top→3│C│3││├──┤├──┤├──┤2││2│B│2││├──┤├──┤├──┤1││1│A│1││└──┘└──┘└──┘top→0top→0

空栈A,B,C进栈后C,B,A退栈后

push(s,A);pop(s);push(s,B);pop(s);push(s,C);pop(s);二、栈的存储结构s[1..n]s[1..n]s[1..n]┌──┐┌──┐┌──┐n││n││top→n│an│├──┤├──┤├──┤n-1││n-1││n-1││.├──┤.├──┤.├──┤.││.││.││.├──┤.├──┤.├──┤3││3││3│a3│├──┤├──┤├──┤2││top→2│a2│2│a2│├──┤├──┤├──┤1││1│a1│1│a1│└──┘└──┘└──┘top→0空栈0非空栈满栈（下溢）（上溢）二、栈的存储结构链式栈设链式栈的栈顶指针为top，指向位于栈顶的结点：

datanext┌─┬─┐top─→│B│││栈顶└─┴┼┘

datanext↓┌─┬─┐┌─┬─┐top＝NULLtop─→│A│∧│栈顶│A│∧│栈底└─┴─┘(栈底)└─┴─┘

(1)置为空栈(2)压入元素A之后(3)压入元素B之后

1.3.2队列

一、定义和术语(1)队列:只允许在表的一端删除元素，在另一端插入元素的线性表(2)空队列:不含元素的队列(3)队首:队列中只允许进行删除元素的一端(4)队尾:队列中只允许进行插入的一端(5)队首元素:处于队首的元素(6)队尾元素:处于队尾的元素(7)进队:插入一个元素(8)出队:删除一个元素(9)队列中元素的进出原则:先进先出(FirstInFirstOut)。(10)队列的别名:先进先出表，FIFO表

队列示例─┬─┬─┬─┬─┬─┬─││││││出队←││A│B│C││←进队││││││─┴─┴─┴─┴─┴─┴─↑↑

headtail(队首指针)(队尾指针)

1.3.2队列

一、定义和术语队列的的基本操作(1)init(q)初始化，将队列q设置为空队列(2)empty(q)判断队列q是否为空队列(3)insert(q,x)入队操作，将ｘ插入队列q尾部(4)delete(q)出队操作，取队列q首元素(5)gethead(q)读取队列q首元素(6)clear(q)队列q置空操作(7)length(q)求当前队列q中元素的个数二、链队列如果采用单向链，设两个指针

head指向队首

tail指向队尾空队列

head=tail=NULL;有一个元素的队列

datanext┌─┬─┐head→│A│∧│首(尾)结点

tail→└─┴─┘一般队列

datanext┌─┬─┐head─→│A│││首结点└─┴┼┘↓┌─┬─┐│B│││└─┴┼┘↓┌─┬─┐tail─→│C│∧│尾结点└─┴─┘二、链队列

head┌──┐│^│p─┐└──┘↓┌──┐┌─┬─┐│^││A│^│└──┘└─┴─┘tail

┌─┬─┐head─→│A│││首结点└─┴┼┘↓┌─┬─┐

tail─→│B│∧│尾结点└─┴─┘

┌─┬─┐

p─→│C││└─┴─┘

入队算法if(head==NULL){head=p;}else{tail->next=p;}tail=p;二、链队列

head┌──┐│┼───┐└──┘↓┌──┐┌─┬─┐│┼→│A│^│└──┘└─┴─┘tail

┌─┬─┐head─→│A│││首结点└─┴┼┘↓┌─┬─┐│B│││└─┴┼┘↓┌─┬─┐tail─→│C│∧│尾结点└─┴─┘

出队算法if(head==NULL){/*空队列*/}else{p=head;head=head->next;if(head==NULL)tail==NULL;}三、循环队列

如果采用数组q[6],设两个指针

head指向队首

tail指向队尾空队列head=tail┌-┬-┬-┬-┬-┬-┐←│││││││←└-┴-┴-┴-┴-┴-┘012345↑↑HT(带头结点链表？）

插入A,B,C,D,E之后┌-┬-┬-┬-┬-┬-┐←││A│B│C│D│E│←└-┴-┴-┴-┴-┴-┘012345↑↑HT删除A,B,C之后┌-┬-┬-┬-┬-┬-┐←│││││D│E│←└-┴-┴-┴-┴-┴-┘012345↑↑HT插入F发生假“溢出”.┌-┬-┬-┬-┬-┬-┐←│││││D│E│←F└-┴-┴-┴-┴-┴-┘012345↑↑HT三、循环队列

循环队列插入Ftail=(tail+1)%6↓↑┌-┬-┬-┬-┬-┬-┐│F││││D│E│└-┴-┴-┴-┴-┴-┘012345↑↑TH插入G,H,队列满(tail+1)%6=head↓↑┌-┬-┬-┬-┬-┬-┐│F│G│H││D│E│└-┴-┴-┴-┴-┴-┘012345↑↑THtail→0

5F1E

4D2

3←head0

5F1EG

4DH2←tail

3←head1.4树

1.4.1树及存储结构一、树的基本概念定义树是一个或多个结点的有穷集合T，其中有且仅有一个指定的称为树根(root)的结点，除树根之外的其余结点被分为m(m≥0)个互不相交的集合T1，T2，...，Tm，每一个Ti(i=1，2，...，m)又都是树，并且称为根的子树。

例1.一个结点的树

T＝{A}

1.4.1树及存储结构

一、树的基本概念例2.12个结点的树

1T＝{A,B,C,D,E,F,G,H,I,J,K,L}2T1＝{B,E,F,J}Ａ...........第1层

3T11＝{E}／│＼

4T12＝{F,J}／│＼

5T121＝{J}ＢＣＤ......第2层

6T2＝{C}／＼／│＼

7T3＝{D,G,H,I,K,L}／＼／│＼

8T31＝{G,K,L}ＥＦＧＨＩ...第3层

9T311＝{K}││＼

10T312＝{L}││＼

11T32＝{H}ＪＫＬ.......第4层

12T33＝{I}一棵树的图示

1.4.1树及存储结构

一、树的基本概念(1)结点的度：结点X的子树数称为结点X的度(degree)(2)树的度：树T中各结点的度的最大值称为树T的度。度为d的树称为d度树(3)叶子：树中度为0的结点称为叶子(leaf)或终端结点(4)分枝结点(非终端结点、非叶子)：树中度不为0的结点(5)双亲和孩子：若树中结点P的一棵子树的根是结点C，则称结点P是结点C的双亲或父母(parent)；反之，称结点C是结点P的孩子(child)(6)结点的层：规定树的根结点的层(level)为1，其余任一结点的层等于它的双亲的层加1(7)树的深度：树T中各结点的层的最大值称为树T的深度或高度(8)兄弟和堂兄弟：同一个双亲的孩子之间互称为兄弟(sibling)，其双亲在同一层的结点互为堂兄弟(9)祖先和子孙：一个结点的祖先是指从树的根到该结点所经分枝上的所有结点，一个结点的子树的所有结点称为该结点的子孙(10)有序树和无序树：如果树T中任一结点的各棵子树规定从左至右是有次序的，即不能互换位置，则称树T为有序树；否则树T为无序树(11)森林：n(n>=0)棵互不相交的树的集合称为森林1.4.1树及存储结构

一、树的基本概念

例3.有序树和无序树ＡＡＡＡ／＼／＼／＼／＼／＼／＼／＼／＼ＢＣＣＢＢＣＣＢ││││││││ＤＤＤＤ两棵不同的有序树两棵相同的无序树

例4.森林F＝{T1,T2,T3}

ＢＣＤ／＼／│＼／＼／│＼ＥＦＧＨＩ││＼││＼ＪＫＬ

T1T2T31.4.2二叉树及其存储结构

一、二叉树的基本概念二叉树的递归定义二叉树是有限个结点的集合，它或者为空集，或者是由一个根结点和两棵互不相交的且分别称为根的左子树和右子树的二叉树所组成。若二叉树为空集，则称之为空二叉树。

二叉树的5种基本形态

ΦＡＡＡＡ／＼／＼／＼／＼ＢＢＢＣ

(1)(2)(3)(4)(5)

空二叉树只有根结点有根结点有根结点有根结点左、右子树左子树非空左子树为空左子树非空为空二叉树右子树为空右子树非空右子树非空一、二叉树的基本概念二叉树和2度树的区别

(1)二叉树的度小于等于2；而2度树的度等于2。

(2)二叉树的左子树和右子树是有序的；而2度树可以不规定各子树之间的次序，即可以是有序树，也可以是无序树。

例.

ＡＡＡＡ／＼／＼／＼／≠＼／＼／＼ＢＢＢＣＣＢ

T1T2T4T5

T1、T2是两棵不同的二叉树，但不是2度树。

T4、T5是两棵不同的二叉树；是相同的无序2度树。一、二叉树的基本概念具有3个结点的不同形态的二叉树

○○○○○／＼／／＼＼／＼／／＼＼○○○○○○／＼／／＼／○○○

T1T2T3T4T5

一、二叉树的基本概念性质1：在任意二叉树的第ｉ层上，最多有２i-1个结点(ｉ≥1)。例.○.............第1层２1-1

＝1

／＼／＼／＼○○.........第2层２2-1

＝2

／＼／＼／＼／＼○○○○......第3层２3-1

＝4

／＼／＼／＼／＼○○○○○○○○.....第4层２4-1

＝8

二、二叉树的性质性质2：深度为k的二叉树最多有2k

－1(k≥1)个结点。由性质1知，深度为ｋ的二叉树的结点总数最多为：

kki－1∑(第ｉ层上结点的最多数目）＝∑2i=1i=1

例.T4T1T2T3○○○○／＼／＼／＼／＼／＼／＼／＼○○○○○○／＼／＼／＼／＼○○○○／＼／＼○○○○／＼／＼／＼／＼○○○○○○○○21－1＝122－1＝323－1＝724－1＝15二、二叉树的性质性质3：对于任一非空二叉树，如果它的叶子数目为ｎ0，度为2的结点数目为ｎ2，则有：ｎ0＝ｎ2＋１(2n2+1=n0+n2)

例

T1T2T3T4

○○○○

／／＼／＼／／＼／＼○○○○○＼／＼／＼／＼＼／＼／＼／＼○○○○○○○／＼／＼＼／＼／＼／＼＼／＼○○○○○○○

ｎ0＝1ｎ0＝2ｎ0＝4ｎ0＝5

ｎ2＝0ｎ2＝1ｎ2＝3ｎ2＝4三、特殊二叉树特殊二叉树满二叉树、完全二叉树(1)满二叉树:深度为k的具有2k

－1个结点的二叉树称为满二叉树(k≥1).

例：

T1T2T3T4○○○○／＼／＼／＼／＼／＼／＼／＼○○○○○○／＼／＼／＼／＼○○○○／＼／＼○○○○／＼／＼／＼／＼○○○○○○○○

k＝1k＝2k＝3k＝421

－1＝122

－1＝323

－1＝724

－1＝15三、特殊二叉树

顺序编号的满二叉树:从根结点开始，从上至下；同层的结点从左至右；n个结点的满二叉树，依次用1，2，…，n顺序编号。

例.顺序编号的满二叉树

T1T2T3①①①

／＼／＼／＼／＼②③②③／＼／＼／＼／＼④⑤⑥⑦

n＝1n＝3n＝7

满二叉树的结点个数与树的深度之间的关系：具有n个结点的满二叉树的深度为log2（n＋1）。依定义,一棵深度为k的满二叉树有2k

－1个结点），有：

2k

－1＝n三、特殊二叉树(2)完全二叉树若二叉树的任一结点深度为k,有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时

，则称该二叉树为完全二叉树。例.完全二叉树

T1