《数据结构及其应用》PPT课件

1、软件开发技术基础,数据结构及其应用,什么是数据,指描述客观事物的信息符号的集合，这些信息符号能输入到计算机中存储起来，并能被计算机处理。,整数数据,整数集合的子集： -3 -2 -1 0 1 2 3 4 int j; -32768 至 +32767 unsigned int j; 0 至 +65535 long int j; -232 至 + 232 - 1 unsigned long int j;范围？,Struct student long num; char name9; char sex; float score; ,学生花名册数据,学号 姓名 性别 成绩 98031001 张三 男

2、88 98031002 李四 女 89.5 .,棋盘数据：围棋棋盘,如何描述？,棋盘数据：井字棋盘,O,O,*,*,O,O,O,O,O,O,*,*,O,O,O,O,*,*,*,*,*,*,*,*,O,O,O,O,O,Char chess9; 或 int chess9;,城市交通图数据,图像数据,像素存储 （行号，列号，颜色）,声音数据,时刻值，幅度值,数据元素-是数据这个集合中的一个个体，是数据的基本单位。,数据项-是具有独立含义，且不可再细分的最小标识单位。,数据结构-指相互之间存在一种或多种特定关系的数据元素集合,数据的逻辑结构-反映数据元素之间客观存在的逻辑关系。,数据的存储结构-将数据

3、的逻辑结构在计算机内存中存储的结构。 数据的物理结构,数据的运算-是定义在数据结构上的操作。 例如求某个数据结构中的最大元素等。,线性表、堆栈、队列、树、图,名词术语,什么是算法？ 算法-是解决问题方案的准确而完整的描述 算法的特性：有穷性、确定性、可行性、有输入、有输出 时间复杂度：依据算法编制成程序后，在计算机上运行所消耗时间 空间复杂度：依据算法编制成程序后，在计算机上运行所消耗空间 用数量级来度量和分析时间复杂度和空间复杂度。 #define n 1000000 sum=sum+1; O(1) for(I=0;In;I+) sum+; O(n) for(I=0;In;I+) for(j

4、=0;jn;j+) sum+; O(n2) float a; O(1) float an; O(n) float ann O(n2),算法,什么是线性表,日常生活中常见到表格形式的一类数据 列车时刻表 学生成绩表 周名缩写表,列车时刻表,学生成绩表,周名缩写表,1）表中每一行信息虽然组成的内容不同，但都代表某个明确独立的含义，将表中每一行信息称之为一个数据元素； 2）每个数据元素在表中的位置固定，除了第一个元素和最后一个元素外，其余元素都有唯一一个前驱元素和唯一一个后继元素； 3）表中数据元素的个数不相同，有长有短； 4）大多数表中数据元素会增加或减少，是动态变化的。但也有一些表是固定不变，

5、将这些表格形式的数据加以抽象，统称为线性表。,上述表格数据具有如下共同特点：,什么是线性表,试举出日常生活中线性表的例子？,指n(n0)个元素a1，a2，a3，an 的有限集合，集合中的元素除第一个与最后一个元素外，其它元素都只有一个直接前趋元素和一个直接后继元素。,对线性表有哪些处理（或操作）呢？,1）统计线性表里总共有多少个元素。简称求表长，记作 Length（L）， 2）获取线性表中某个数据元素的信息。简称取元素，记作 Get（L，i） 3）置换或修改线性表中某个数据元素的信息。简称置换元素， 记作Replace（L，i，x） 4）在线性表中某个位置上增加一个数据元素。简称插入元素， 记

6、作Insert（L，i，x） 5）删除线性表中某个位置上的一个数据元素。简称删除元素， 记作Delete（L，i） 6）查找某个数据元素是否在线性表中存在。简称查找元素， 记作Locate（L，x） 7）对线性表中的数据元素按某个数据项的值递增（或递减） 的顺序排列。简称排序，记作Sort(L)。,线性表的顺序存储结构-顺序表类 线性表的非顺序存储结构-链表类,线性表的两种存储结构,顺序表类,线性表的顺序存贮结构就是将线性表的每个数据元素按其逻辑次序依次存放在一组地址连续的存贮单元里,const int MAXSIZE=100; /顺序表最大允许长度 class SeqList public:

7、 ElemType dataMAXSIZE; / 存储数据的数组 int length; / 顺序表当前长度 SeqList() length=0; /构造函数 void ClearList() length=0; /将顺序表置为空表 bool IsListEmpty() return length=0; /判断是否为空表 /判断顺序表是否为满 bool IsListFull() return length=MAXSIZE; void ListDelete( int i ); /在表中删除第i个元素 /在表中第 i 个位置插入新元素x void ListInsert( int i, ElemT

8、ype x ); int Find( ElemType x ); /在表中查找元素 ;,由于不同的线性表，其数据元素类型不一样 例如学生花名册中每个元素有四个数据项 航班时刻表也有多个数据项。 从通用性出发，表中的元素为一个模板数据类型DataType。 Template,数据元素类型说明,插入前：（a 1，a 2，a i-1，a i，a n） 插入后：（a 1，a 2，a i-1，x ，a i，a n） 第1步: 判定表不满方可插入； 第2步: 判定插入位置i的合法性； 第3步: 将第n至第i个元素后移一个存储位置； 第4步: 将x存入到a i-1之后空间； 第5步: 线性表的长度加1。,插

9、入算法,void SeqList:ListInsert( int i, ElemType x ) if( ilength+1 | length=MAXSIZE ) cout=i-1;j- ) dataj+1 = dataj; / 元素依次向后移动 datai-1 = x; / 向第i个位置存入新元素 length+; / 表长度加1 ,在等概率的条件下,插入函数的时间复杂度:N/2 a1 a2 a3 a4 an-1 an 有N+1处可能插入,等概率值为1/(1+N),插入算法评价,删除前：（a 1，a 2，a i-1，a i，a i+1，a n） 删除后：（a 1，a 2，a i-1，a i+

10、1，a n） 第1步：判定表不空方可删除； 第2步：判定删除位置i值的合法性； 第3步：将第i+1至第n个元素依次向前移动一个存储位置； 第4步：将线性表的长度减1。,删除算法,void SeqList:Delete( int i ) if(iL-length ) cout表中没有第i个元素; else for ( int j=i; j=length-1; j+ ) dataj-1 = dataj; /元素依次向前移动 length-; ,删除函数的时间复杂度：（N-1）/2 在等概率条件下 插入和删除算法详见rjjcjg_1.cpp,删除算法评价,int SeqList:Find(ElemT

11、ype x ) for( int i = 0; ilength; i+ ) /查找成功，返回元素位置 if( datai=x ) return i+1; return 0;/查找失败，返回 0 ,在表中查找某个元素,下面是根据数据元素本身的值进行查询的算法，x为需要查找的元素，查找结果返回元素的实际位置。,顺序表应用举例,一元多项式P(x)可以表示为: (a0, 0), (a1, 1), , (a n, n) 用顺序表存放,例2-1】 利用顺序表表示多项式，实现两个一元多项式L1(x)和L2(x)相加，将结果存于多项式L3(x)中。并计算当L1(x)=3.5+4x2+2.5x4， L2(x)=

12、1.5x+2.6x2+1.6x3时， L3(x)的结果是什么？, 设定两个位置变量i和j指向顺序表L1和L2的第一个元素，设定位置变量k表示L3的插入位置，插入位置从1开始。本例中i、j和k初值均为1。 比较i和j两个位置数据元素的指数项，如果L1中第i项指数较小，则将此项数据元素复制到L3的位置k中，并将位置变量i和k后移；如果L2中第j项指数较小，则同样是将此项复制到L3中，并将位置变量j和k后移；如果两项指数项相等，则合并同类项后再将结果复制到L3中，并将位置变量i、j和k同时后移。 当L1或L2中的一个顺序表已经处理完毕，则将另一个顺序表的剩余部分复制到L3中。,演示运行2-1.cpp

13、,多项式相加算法可按照下列步骤实现,顺序表类的优缺点,1、存取元素非常快； 2、不用存关系集合； 3、插入删除元素要移动一半元素； 4、需要申请较大的空间，但往往只用一部分空间； 5、可扩充性差；,线性表的非顺序存储结构-单链表,设计新的存储结构，改进顺序表的结构思路： 1、线性表中有多少元素就开辟多少存储空间，不预留空间； 2、元素之间不需要紧挨着存放，元素可以散落在存储器中任何地方； 3、插入和删除都不需要移动大量元素；,链表类,线性表中每个元素的存储结构如下：,每个数据元素存储都由两部分组成： 存贮数据元素值的部分，简称数据域； 存贮直接后继元素存贮位置的部分，简称指针域。,数据元素值,

14、后继元素位置,struct LNode ElemType data; LNode *next; ,为了后面定义方便，一个数据元素定义如下：,Typedef struct LNode ElemType data; LNode *next; Lnode;,线性表的非顺序存储结构示意图如下：,A1,A2,A3,An,head,指针将线性表中每一个元素有机地连接在一起，指针像链条一样，所以线性表的非顺序存储结构又称链式结构，简称链表。,A1,A2,A3,22 38 86 94,存储地址 数据域 指针域,head,38,head,链表存储结构示意图如下：,Typedef struct Lnode Ele

15、mType data; LNode *next; Lnode; class LinkList public: LNode *head; /定义头指针 LinkList() /构造函数 head=new LNode; /建立头结点 head-next=NULL; /头结点的指针为空 int ListSize(); /求单链表长度 LNode* GetElemPointer(int pos); /返回表中指定序号结点的指针 void InsertList(int i, ElemType x); /向单链表第i个位置插入元素x LNode* LinkList:DeleteList( int i);

16、/从单链表中删除第i个结点 LNode* Find( ElemType x )； /在单链表中查找数据值为x的结点 ;,单链表类的完整定义如下：,指针操作,假如p为指向某一结点的指针 则该结点的数据域用p-data表示 该结点的指针域用p-next表示 它们都是变量，可以被赋值，也可向其他变量赋值。 例如: 假定data为整型变量,则 p-data=5; p-next=NULL; 将结点变为:,如果p为指向结点ai的指针，那么p-next就是指向ai后继结点ai+1的指针；若q为另一指针变量 p=q 指针p指向指针q所指的结点 p=q-next 指针p指向指针q所指结点的后继,指针操作,要确定

17、链表长度需要走遍表中所有结点才能算出。 为了保持头指针不变，使用了指针p在链表中移动。,求单链表的长度,int LinkList:ListSize() LNode *p=head-next; /p指向第一个元素所在结点 int len=0; while( p!=NULL ) /逐个检测p结点存在与否 len+; p=p-next; /指针后移 return len; ,LNode* LinkList:GetElemPointer(int pos) if(posnext;/p为首元结点指针 int k=1; while( p!=NULL /该位置不存在 ,返回单链表中指定序号的结点的指针,Lno

18、de* newnode=new LNode; newnode-data=x; newnode-next=previous-next; previous-next=newnode;,单链表类的插入算法,从表头开始 寻找插入位置 判定插入位置有错否 申请新结点 修改链表指针，将新结点插入链表中,void LinkList:InsertList( int i, ElemType x) LNode *p=head; p=GetElemPointer(i-1); /p最终将指向第i-1个结点 if(!p) coutdata = x; s-next=p-next;/定义结点s的指针域 p-next=s;/

19、修改结点p的指针域 ,Ai-1,Ai,X,p,s,p-next=s;,新结点链入表中示意图,s-next=p-next;,previous-next=current-next; delete current;,单链表类的删除算法,判定空表 寻找插入位置 确认插入有错否 修改链表指针 收回结点空间,LNode* LinkList:DeleteList( int i ) if(inext; k+; if(p=NULL) coutnext=p-next;/从链表中删除该结点 delete p;/释放结点p ,Ai-1,Ai,q-next=p-next; delete p;,Ai+1,q,p,删除Ai

20、结点示意图,X,X,可以按照数据元素本身的值进行查找，也可以按照数据元素的某个属性进行查找。这里仅给出按照数据元素本身的值进行查找的算法。,在单链表中查找数据值为x的结点,LNode* LinkList:Find( ElemType x ) LNode *p=head-next; /p指向第一个元素所在结点 while ( p!=NULL ,循环链表,head,A1,An,A2,head,空循环链表,非空循环链表,前驱指针域 prior,后继指针域 next,数据域 data,双向链表结点示意图,每个数据元素存储结构如下：,约瑟夫环问题可以解释为：将整数1至n围成一个圆圈，假定从某个整数开始顺

21、时针从1数到m时，令该位置整数出列；然后再从下一数开始，顺时针从1数到第m时再令其出列，如此下去，直到圆圈中无整数为止。请写出所有数字出列的顺序。,链表应用举例,演示【例2-2】2-2.cpp,堆栈stack,探讨货仓工作原理 假设只有一个门的货仓，先进去的货物后出来。 若线性表比照货仓，货物比照数据元素。 元素只能在线性表的一端插入删除。,堆栈的定义,堆栈指插入和删除元素操作只能在表的一端进行，这种线性表称为堆栈。,堆栈又称LIFO表或FILO表,插入 进栈,删除 出栈,栈顶,栈底,创建一个堆栈：setnull(stack) 判空栈： emptystack(stack) 元素进栈： push

22、(stack,data) 元素出栈： pop(stack) 取栈顶元素： gettop(stack),堆栈的基本操作,由于栈是一个特殊线性表，顺序栈类与顺序表基本相同。 类似于线性表的顺序存储结构，顺序栈类的C+描述如下： #define STACKSIZE 100 class SeqStack public: ElemType dataSTACKSIZE; /存储元素的数组 int top; SeqStack( )top=-1; /构造函数 BOOL stack_empty( ); /判栈空函数 BOOL push(ElemType x); /元素进栈函数 BOOL pop(ElemType

23、 ,顺序栈类定义,A1,A2,A3,A4,A5,A6,内存储器,top,5 栈顶,0 栈底,进栈,出栈,进栈的核心操作： top+; datatop=X; 出栈的核心操作： X=datatop; top-;,1,2,3,4,顺序栈类的进栈函数,第1步：判断栈是否已满，若栈满则元素不 能进栈，退出函数； 第2步：栈顶下标变量top增1，即top+； 第3步：在top所指向的当前位置存入元素x。,BOOL SeqStackpush ( ElemType x) if (top=STACKSIZE-1) cout栈满。又称栈溢出(上溢)n; return FALSE; else top+; datat

24、op=x; return TRUE; ,顺序栈类的出栈函数,第1步：判定栈是否为空栈，若为空则无元 素可以出栈，退出函数； 第2步：弹出（删除）栈顶元素； 第3步：栈顶下标变量top减1，即top-。,BOOL SeqStackpop(ElemType ,顺序栈类的取栈顶函数,第1步：判定栈是否为空栈，若为空则无元 素可以出栈，退出函数； 第2步：弹出（删除）栈顶元素；,BOOL SeqStackgettop(ElemType ,类似于单链表，链栈的C+描述如下： typedef struct node ElemType data; /数据域 struct node *next; / 指针域

25、SNode; class LinkStack public: SNode* top; /栈顶指针 LinkStack() top=NULL; /构造函数 void Push(ElemType x);/入栈操作 void Pop(ElemType ,链栈类定义,A2,A3,A4,A5,A6,A1,top,进栈的核心操作： newnode=new SNode; newnode data=X; newnode link=top; top=newnode; 出栈的核心操作： cureent=top; X=top data; top=top link; delete current;,若栈不满，则在栈顶

26、插入元素x作为新的栈顶。 void LinkStack:Push(ElemType x) SNode *p=new SNode; if(p!=NULL) p-data=x; p-next=top; top=p; ,链栈进栈操作,若栈不空，则删除栈顶元素，用result返回其值。 void LinkStack:Pop(ElemType ,链栈出栈操作,三种不同的表示方法： 前缀表示法 OPS1S2 例如6+3写成+63 中缀表示法 S1OPS2 例如6+3写成6+3 后缀表示法 S1S2OP 例如6+3写成63+,假定表达式是由加减乘除和数字构成。最常见的表达式为下列形式： (操作数S1)(运算

27、符OP)(操作数S2),算术表达式表示,同时，任何表达式都可分解为下列形式： (子表达式E1)(运算符OP)(子表达式E2) 它的后缀表示法应写成： (E1的后缀表示)(E2的后缀表示)OP 只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式都可写成前缀式或后缀式。 例如： 2*(6+3) 2(6+3)* 263+*。 (注意：转化为后缀式后括号去掉),算术表达式表示,用后缀式求值的算法为： 首先设立一个堆栈，依此读取后缀式中的字符 若字符是数字，则进栈并继续读取 若字符是运算符，则连续出栈两次得到数字S1和S2 计算表达式S1OPS2,并将结果入栈， 继续读

28、取后缀式。当读到结束符时停止读操作 这时堆栈中只应该有一个数据，即结果数据。,后缀表达式求值,人们习惯于中缀式的计算，但计算机在求值的时候往往利用前缀式或后缀式。,例如后缀式263+*的计算过程为2、6、3依次入栈，读+号则令3和6依次出栈，计算6+3后将结果9入栈，读*号则令9和2依次出栈，计算2*9后将结果18入栈。这时18就是最终结果。 【例2-3】假定表达式是由不超过四个实数进行四则运算构成的算式，要编写一个程序来求解该算式的结果。,运行2_3.cpp,举例计算后缀表达式,中缀式变成后缀式,转换规则是： 设立一个栈，存放运算符，首先栈为空 编译程序从左到右扫描中缀表达式 若遇到操作数，

29、直接输出，并输出一个空格作为两个操作数的分隔符 若遇到运算符，则必须与栈顶比较，运算符级别比栈顶级别高则进栈，否则退出栈顶元素并输出，然后输出一个空格作分隔符 若遇到左括号，进栈；若遇到右括号，则一直退栈输出，直到退到左括号止 当栈变成空时，输出的结果即为后缀表达式。,将中缀表达式(1+2)*(8-2)/(7-4)变成等价的后缀表达式。现在用栈来实现该运算，栈的变化及输出结果如下：,对头,队尾,队列类似日常生活中的排队原理 LILO表 FIFO表,分析进队顺序：A, B, C 则出队顺序有哪些？,进队,出队,队列也是特殊的线性表。它只允许在线性表的一个端 点进行插入，而在线性表的另一个端点进行

30、删除操作,setnull（QUEUE） 创建一个空队列QUEUE。 empty_gueue（QUEUE） 判定队列是否为空。 addqueue（QUEUE，x） 入列操作。 delqueue（QUEUE） 出列操作。 frontqueue(QUEUE） 读取队列的队头元素。,队列的五种基本运算,类似于顺序表类的定义，C+描述如下： const int QUEUESIZE=200; class SeqQueue public: ElemType dataQUEUESIZE; int front,rear; SeqQueue()front=rear = 1; /创建空队列 BOOL queue_e

31、mpty(); /判队列空 BOOL addqueue( ElemType x); /元素进队 BOOL delqueue(ElemType ,顺序队列类定义,入列操作： rear+; datarear=X; 出列操作： front+; X = datafront; 分析：队列空的条件 front = rear 队列满的条件 rear = QUEUESIZE-1,分析队列操作,队列假满的状态 front = rear = QUEUESIZE-1 或 front -1 datarear=X; 出列操作： front=(front+1)%QUEUESIZE; X = datafront;,循环队列

32、示意图,0 1,7 2,6 3,5 4,0 1 2 3 4 5 6 7,为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。 队空条件为:front=rear 队满条件为:(rear+1)%QUEUESIZE=front,(a)循环队列空 (b)非空循环队列 (c)循环队列满 循环队列示意图,/循环队列进队函数 bool SeqQueue:addqueue(ElemType x) if(rear+1)%MAXSIZE=front) printf(“队列已满，元素不能进队列！n”); return false; else real=(real+1)%MAXSIZE; datare

33、al=x; return true; ,/循环队列出队函数 bool SeqQueue:delqueue( ElemType ,链队列队列链式存储,链队列实质上就是只能在头部删除元素、只能在尾部插入元素的单链表。 队头指针front就是单链表的头指针，队尾指针rear则是指向单链表最后一个结点的指针。,struct QNode /类似于单链表的C+描述如下： ElemType data; struct QNode *next; ; class LinkQueue public: QNode *front;/ 队头指针 QNode *rear; / 队尾指针 LinkQueue() front

34、= new QNode;/建立头结点 front-next=NULL; rear = front;/尾指针也指向头结点 int Length(); /求队列长度 void EnQueue(ElemType x); /入队操作 void DeQueue (ElemType ,链队列,返回队列的元素个数，即队列的长度。 int LinkQueue:Length() QNode * p=front; int len=0; while(p!=rear) len+; p= p-next; return len; ,求队列的长度,链队列进队算法： 1、申请新结点 2、链入新结点 void LinkQueu

35、e:EnQueue(ElemType x) QNode *s=new QNode; /建立新结点s s-data = x; s-next =NULL; rear -next = s; /在队尾插入结点s rear = s; /修改队尾指针 ,链队列进队算法,链队列出队算法： 1、判断队列空否 2、队头元素出队 3、出队元素归还操作系统 void LinkQueue:DeQueue (ElemType 删除最后一个元素时，需要修改尾指针，使其指向头结点,上机练习一：求两个链表的交集,解决方法: 建立两个带头结点的单链表； 通过插入函数插入两个链表中的所有元素 创建第三个带头结点的单链表 从两个表

36、头开始循环比较，只有相等才能插入,上机练习二：求k阶斐波那切数列某一项,k阶斐波那切数列ai定义如下：,解决方法: 建立一个容量为k的循环队列，将前k个元素依次入队。然后计算第k+1个元素，它等于队列中全部元素之和。而后将对头元素出队，将第k+1个元素入队。重复上述过程，就可求得任意指定项元素的值。,【例2-4】利用循环队列求k阶斐波那切数列 某一式的值。,前面所学的数据结构都是线性关系结构，即每个数据元素都只有唯一的前驱元素和唯一的后继元素。 但是在客观世界中数据元素之间的关系不一定是线性关系，即不一定是唯一的前驱和唯一的后继，称为非线性关系结构。 例如分析任何一个企事业单位的组织机构，会发

37、现任何一个部门机构，它只隶属于一个部门机构，而下辖一个以上部门机构。假如把部门机构看成数据元素，那么可以说任何一个数据元素有唯一的前驱元素，但有多个后继元素。 又例如日常生活中对事物的分类水果的分类。,非线性数据结构：树和图,西安交通大学,管理学院,电信学院,医学院,信控系,计算机系,电子系,组织机构示意,水果,芒果,苹果,梨,香蕉,红富士,黄元帅,秦冠,巴拿马,芝麻,水果分类示意,R,A,E,G,D,C,B,X,F,Z,Y,K,J,I,H,M,L,N,P,O,Q,V,U,T,S,*,+,%,将上述分层结构抽象成如下所示的结构倒置树,树是包含n个数据元素的有限集合T（n1），并且满足： （1）

38、T中有一个称为根的结点root； （2）T中除根以外的其余结点被分成m（nm0）个互不相交的集合T1、T2、Tm，且每一个集合又符合上述两条，即它 们本身又是一棵树，这些树称为root的子树。,树的递归定义,T1,T2,TN,T3,T4,结点表示树中的数据元素； 树枝表示树中的数据元素与数据元素之间的关系； 叶子结点表示没有后继的结点称为叶子（或终端结点）； 分支结点表示非叶子结点称为分支结点（或非终端结点）； 结点的度意指一个结点的子树数目就称为该结点的度； 树的度意指一棵树上所有结点的度的最大值就是这棵树的度； 结点的层次确定根结点的层数为1，其它任何结点的层数等于 它的父结点的层数加1；

39、,有关树的基本术语,树的深度意指一棵树中，结点的最大层次值就是树的深度； 孩子结点代表某结点的子树的根称为该结点的孩子结点； 双亲结点相对于某结点的前驱结点，称该结点为双亲结点； 兄妹意指同属于一个双亲的孩子结点之间互称为兄弟； 堂兄妹意指其双亲在同一层的结点之间互称为兄弟； 有序树如果一棵树中结点的各子树看成是从左至右依次有序排 列且不能交换，则该树就称为有序树； 无序树如果一棵树中结点的各子树可以互换排列次序，则该树 称为无序树； 森林森林是n棵互不相交的树的集合（n0）；,建空树 记作setnull(T)，置T为空树。 求根结点 记作root(x)，求x所在树的根结点。 求双亲结点 记作

40、parent(T，x)，在树T中取出结点x的双亲。 求孩子结点 记作child(T,x,i)，在树T中取出结点x的第i个孩子。 插入结点 记作ins_child(T,y,i,x)，将x作为树T中y结点的第i个孩子。 删除子树 记作del_child(T,x,I)，即删除树T中x结点的第i棵子树。 遍历树 记作TRAVERSE(T)，即从根结点出发，按某种次序，依次访问树 中每个结点，且每个结点只访问一次的操作。,树的基本运算,二叉树的定义,二叉树是n（n0）个结点的有限集合，且满足以下两条: (1)或者为空二叉树，即n=0； (2)或者由一个根结点和两棵互不相交的被称为根的左子树和右子树所组成

41、，左子树和右子树分别又是一棵二叉树。,问题：1、二叉树可以定义为度不大于2的树？ 2、三个结点的二叉树有几种形态？,探讨结构较为简单的一类树，二叉树,创建空二叉树 记作setnull(BT)，置BT为空二叉树。 求二叉树的根 记作root(x)，求结点x所在二叉树的根。 求双亲结点 记作parent(BT,x)，在二叉树中求结点x的双亲。 求左孩子结点 记作lchild(BT,x),在二叉树BT中求结点x的左孩子。 求右孩子结点 记作rchild(BT,x),在二叉树BT中求结点x的右孩子。 插入左孩子结点 记作ins_lchild(BT,x,y),将结点y置为结点x的左孩子。 插入右孩子结点

42、 记作ins_rchild(BT,x,y),将结点y置为结点x的右孩子。 删除左孩子 记作del_lchild(BT,x),在二叉树BT中，删除结点x的左子树。 删除左孩子 记作del_rchild(BT,x),在二叉树BT中，删除结点x的右子树。 遍历二叉树 记作TRAVERSE(BT),即从根结点出发，按某种次序，依次访问 二叉树中每个结点，且每个结点只访问一次。,二叉树的基本操作,左指针域,数据域,右指针域,二叉树的非顺序存储结构,根据二叉树的特性：任何一个结点最多有左、右两个子树，这样可以为树中每个数据元素设计三个存储区域（或称变量）。 一个域用来存放数据元素值，两个域用来存放指向左右

43、子树根的指针。也就是说对于二叉树中任意一个数据元素可以设计成如下存储结构。俗称结点。,二叉树的二叉链表存储结构示意图,A,B,C,F,E,G,D,A,B,C,D,E,G,F,V,V,V,V,V,V,V,V,struct BinTreeNode /结点的定义 ElemType data; struct BinTreeNode *leftChild, *rightChild; ; class BinTree /二叉链表类的定义 public: BinTreeNode *root; /定义根结点指针 BinTree() root=NULL; /构造函数，创建空树 bool IsEmpty() ret

44、urn root=NULL; /判空二叉树 void Ins_lchild(BinTreeNode *p,BinTreeNode *q) p-leftChild=q; /在叶子结点p下插入左子树q void Ins_rchild(BinTreeNode *p,BinTreeNode *q) p-rightChild=q; /在叶子结点p下插入右子树q /删除结点p的左子树 void Del_lchild(BinTreeNode *p) p-leftChild=NULL; /删除结点p的右子树 void Del_rchild(BinTreeNode *p) p-rightChild=NULL;

45、void PreOrder(BinTreeNode *t); /先序遍历 void InOrder(BinTreeNode *t); /中序遍历 void PostOrder(BinTreeNode *t); /后序遍历 ;,注意：上述性质都可以通过归纳方法进行证明。,二叉树的性质,性质一：二叉树的第i层上至多有2i-1（i1）个结点。,性质二：深度为h的二叉树上最多含有2h-1个结点。,性质三：包含n个结点的二叉树必有n-1条树枝(分枝)。,性质四：任何一棵二叉树，若含有n0个叶子结点、n2个 度为2的结点，则必存在关系式n0=n2+1 。,若一棵二叉树的深度为h，且含有2h-1个结点，则称

46、该二叉树为满二叉树。,A,A,B,C,A,B,C,D,E,G,F,深度为1 深度为2 深度为5,满二叉树,深度为4的满二叉树,编号规则： 设满二叉树的深度是h，根结点的编号为1，其余结点的编号次 序是从上层到下层，每层从左到右。 推论： 1）若1i2h-1-1，则结点i的左子树根的编号为2*i，结点i的右子树根的编号为2*i+1； 2）若1i2h-1，则结点i的父结点的编号为(int)(i/2)；,1,2,4,5,8,9,10,11,3,6,7,12,13,14,15,设一个深度为h的二叉树，每层结点数目如果满足： 1）第i层（1ih-1）上的结点个数均为2i-1； 2）第h层从右边起连续缺若

47、干个结点。 这样的二叉树称为完全二叉树。,A,B,C,D,E,G,F,H,完全二叉树,A,B,C,D,E,从满二叉树叶子所在的层次中，自右向左连续删除若干叶子所得到的二叉树被称为完全二叉树。,首先将任何一棵二叉树转变为相同深度的完全二叉树，即通过编号顺序，在每一层加上一些空结点，以便保证第i层上有2i-1个结点。其次将实结点和空结点依次存入一维数组中。,A,B,C,D,E,F,G,H,A,B,C,D,E,F,G,H,0 1 2 3 4 5 6 7 8 9 10 1112,A,B,C,D,E,F,G,H,任何一棵二叉树都可用一维数组来储存的方法,ABCDEFG 二叉树的逻辑形态？ ABCDEFG

48、H 二叉树的逻辑形态？,A,B,C,D,E,G,F,A,B,C,D,E,G,F,H,问题,二叉树的遍历,根据一定的规律访问二叉树中的每一个结点，且每个结点只能访问一次的过程。,注意：定义中所提到的访问，对于不同应用问题有不同的操作意义。例如读取二叉树中的每一个结点的值，进行统计计算。又比如修改二叉树中的每一个结点的值等等。,由于二叉树中每个结点最多有两棵子树，也就是说一个结点可能有两个后继，所以，二叉树的遍历方法会有好几种。可以将二叉树看成如下图所示的三个基本组成部分。,这样一来对二叉树的访问顺序就有六种 DLR 先根遍历 LDR 中根遍历 LRD 后根遍历 DRL RDL RLD,先序遍历a

49、.访问根结点； b.先序遍历左子树； c.先序遍历右子树； 中序遍历a.中序遍历左子树； b.访问根结点； c.中序遍历右子树； 后序遍历a.后序遍历左子树； b.后序遍历右子树； c.访问根结点；,二叉树的三种遍历方式,A,B,C,D,E,G,F,A,B,C,D,E,G,F,H,讨论下列两棵二叉树的遍历,先根遍历结果： 中根遍历结果： 后根遍历结果：,/假设二叉树存储以二叉链表结构 void BinTree:PreOrder(BinTreeNode *t) if (t) Visit( t ); /访问根结点 PreOrder( t-leftChild ); /遍历左子树 PreOrder(

50、t-rightChild ); /遍历右子树 ,先序遍历二叉树的递归算法,/中序遍历算法 void BinTree:InOrder(BinTreeNode *t) if(t) InOrder( t-leftChild );/ 遍历左子树 Visit( t ); / 访问根节点 InOrder( t-rightChild ); / 遍历右子树 ,/后序遍历算法 void BinTree:PostOrder(BinTreeNode *t) if(t) PostOrder( t-leftChild ); /遍历左子树 PostOrder( t-rightChild ); /遍历右子树 Visit(

51、t ); /访问根节点 ,非线性数据结构：图,图是中一种重要的、比树更复杂的非线性数据结构。 在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系，而同一层的结点之间没有任何横向联系。 在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。 图的应用范围非常广泛，诸如电网络分析、交通、管道线路、集成电路布图、工程进度安排图等实际问题的处理都可以归纳为图的问题,图的定义,图是由数据元素集合及数据元素间的关系集合组成的一种数据结构。一般记作Graph( V, E )。其中V是数据元素的非空有限集合；E是数据元素之间关系的有限集合。,边和弧的含义,图的符号表示,邻接点

52、：对于无向图，如果边（v，u）E，则v和u互为邻接点，亦即u是v的邻接点，v也是u的邻接点；对于有向图，如果弧E，则u是v的邻接点。 顶点的度：在无向图中，顶点的度就是以该顶点为一个端点的边 的条数。在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度；以某顶点为弧尾的弧的数目，称为此顶点的出度。该顶点的度则是此顶点的入度与出度之和。 路径：在图G中，从顶点v至顶点u的一条路径是指存在这样的顶点的序列（v，v1，v2，vi，u），并且有，,，都属于边（弧）集合。 长度：路径上弧的数目称为该路径的长度。 环（回路）：第一个顶点和最后一个顶点相同的路径称为回路或环,有关图的术语,连通图：在无向图

53、中，若每一对顶点之间都有路径，此图为连通图 强连通图：在有向图中，若每一对顶点u和v之间都在从v到u及从u到v的路径，则称此图为强连通图。 网：如果图G（V，E）中每条边（弧）都赋有反映这条边的某种特性的数据，则称此图是一个网。 权：与边（弧）相关的数据称为该边的权。 通常我们用n表示图中顶点数目，e表示图中边或弧的数目，并且下 面的讨论不涉及顶点到自身的边或弧，因此,对于有n个顶点的有向 图来说,其弧的数目有0en（n-1）。 完全有向图：在n个顶点的有向图中，具有n（n-1）条弧的有向图 称为完全有向图。 完全图：在n个顶点的无向图中，具有n(n-1）/2条边的无向图 子图：设有图G=(V

54、,E)和图G=（V，E)，若V包含在V中，且 E包含在E中，则称G是G的子图。,有关图的术语,术语提问？,由于一个图是由顶点集合V和顶点之间的关系集合E(即顶点偶对集合)。因此，设计一个图的存储结构只要分别解决集合V和集合E的存贮结构表示即可。 显然可以用一个一维数组表示集合V中的所有顶点；用一个二维数组来表示集合E。此二维数组被称为邻接矩阵。 对于n个顶点的有向图，则其邻接矩阵中所有元素按如下公式来确定：,对于n个顶点的无向图，则其邻接矩阵中所有元素按如下公式 来确定：,图的存储结构:邻接矩阵,.对于无向图，邻接矩阵第i行（或第i列）的元素之和则 是顶点Vi的度； .对于有向图，邻接矩阵第i

55、行的元素之和为顶点Vi的出 度；邻接矩阵第i列的元素之和为顶点Vi的入度。,1,2,3,5,4,2,1,4,3,5,6,无向图G1 有向图G2,#define MAX_NUM 100 / 最大顶点个数 typedef struct VertexType vexsMAX_NUM; /顶点数组 ArcType MatrixMAX_NUMMAX_NUM; /邻接矩阵 int vexnum; /图的实际顶点数 int arcnum; /图的实际弧(边)数 int kind; /图的种类标志, 1有向图, /2有向网,3无向图,4无向网 MGraph; 其中ArcType是顶点关系的数据类型。Verte

56、xType是顶点的数据类型。MAX_NUM表示最多可存的顶点数。,(a)无向图邻接矩阵 (b)有向图邻接矩阵 (c)网络邻接矩阵,邻接矩阵反映出图中顶点之间的联系，值得注意的是当一个图为稀疏图时，其邻接矩阵为稀疏矩阵。如果将邻接矩阵看成是顺序存储结构，那么，另一种结构就是链式存贮结构，把一个顶点的所有邻接顶点都链接在同一个单链表上。 邻接表存储形式是一种链表与数组结合的存储形式。在邻接表中，图中每个顶点数据存储为数组，某个顶点的所有邻接点建立一个单链表，n个顶点就建立n个单链表。 邻接表中由下列三个结点组成，如下图所示：,图的存储结构:邻接表,数组元素（头结点）： 无权图中的单链表结点： 网中的