数据结构及其应用

《数据结构及其应用》由会员分享，可在线阅读，更多相关《数据结构及其应用（186页珍藏版）》请在装配图网上搜索。

1、软件开发技术基础软件开发技术基础 数据结构及其应用数据结构及其应用 什么是数据什么是数据指描述客观事物的信息符号的集指描述客观事物的信息符号的集合，这些信息符号能输入到计算合，这些信息符号能输入到计算机中存储起来，并能被计算机处机中存储起来，并能被计算机处理。理。整数数据整数数据整数集合的子集：整数集合的子集：-3 -2 -1 0 1 2 3 4-3 -2 -1 0 1 2 3 4 int j;-32768 int j;-32768 至至 +32767 +32767 unsigned int j;0 unsigned int j;0 至至 +65535+65535 long int j;-2

2、long int j;-232 32 至至 +2+23232-1-1 unsigned long int j;unsigned long int j;范围？范围？Struct student Struct student long num;long num;char name9;char name9;char sex;char sex;float score;float score;学生花名册数据学生花名册数据学号学号 姓名姓名 性别性别 成绩成绩 98031001 98031001 张三张三 男男 888898031002 98031002 李四李四 女女 89.589.5 .棋盘数据：围棋

3、棋盘棋盘数据：围棋棋盘如何描述？如何描述？棋盘数据：井字棋盘棋盘数据：井字棋盘OO*OOOOOO*OOOO*OOOOOChar chess9;或 int chess9;城市交通图数据城市交通图数据OOOOOOOOO咸阳咸阳西安西安长安县长安县临潼临潼兴平兴平礼泉礼泉渭南渭南大荔大荔图像数据图像数据 像素存储像素存储 （行号，列号，颜色）（行号，列号，颜色）声音数据声音数据时刻值，幅度值时刻值，幅度值数据元素数据元素-是数据这个集合中的一个个体，是数据的基本单位。是数据这个集合中的一个个体，是数据的基本单位。数据项数据项-是具有独立含义，且不可再细分的最小标识单位。是具有独立含义，且不可再细分的

4、最小标识单位。数据结构数据结构-指相互之间存在一种或多种特定关系的数据元素集合指相互之间存在一种或多种特定关系的数据元素集合数据的逻辑结构数据的逻辑结构-反映数据元素之间客观存在的逻辑关系。反映数据元素之间客观存在的逻辑关系。数据的存储结构数据的存储结构-将数据的逻辑结构在计算机内存中存储的结构。将数据的逻辑结构在计算机内存中存储的结构。数据的物理结构数据的物理结构数据的运算数据的运算-是定义在数据结构上的操作。是定义在数据结构上的操作。例如求某个数据结构中的最大元素等。例如求某个数据结构中的最大元素等。线性表、堆栈、队列、树、图线性表、堆栈、队列、树、图名词术语名词术语什么是算法？什么是算法

5、？算法算法-是解决问题方案的准确而完整的描述是解决问题方案的准确而完整的描述算法的特性：有穷性、确定性、可行性、有输入、有输出算法的特性：有穷性、确定性、可行性、有输入、有输出时间复杂度：依据算法编制成程序后，在计算机上运行所消耗时间时间复杂度：依据算法编制成程序后，在计算机上运行所消耗时间空间复杂度：依据算法编制成程序后，在计算机上运行所消耗空间空间复杂度：依据算法编制成程序后，在计算机上运行所消耗空间用数量级来度量和分析时间复杂度和空间复杂度。用数量级来度量和分析时间复杂度和空间复杂度。#define n 1000000#define n 1000000 sum=sum+1;sum=sum

6、+1;O(1)O(1)for(I=0;In;I+)sum+;for(I=0;In;I+)sum+;O(n)O(n)for(I=0;In;I+)for(j=0;jn;j+)sum+;for(I=0;In;I+)for(j=0;jn;j+)sum+;O(nO(n2 2)float a;float a;O(1)O(1)float an;float an;O(n)O(n)float ann float ann O(nO(n2 2)算法算法什么是线性表什么是线性表日常生活中常见到表格形式的一类数据日常生活中常见到表格形式的一类数据 列车时刻表列车时刻表 学生成绩表学生成绩表 周名缩写表周名缩写表 车次车

7、次火车种类火车种类始发站始发站终点站终点站始发时间始发时间到达时间到达时间140140特快特快西安西安上海上海2020：30301919：45454242特快特快西安西安北京北京1717：30307 7：4545361361普快普快西安西安铜川铜川9 9：45451313：1010列车时刻表列车时刻表学号学号姓名姓名性别性别分数分数9901100199011001周敏周敏女女86869901100299011002苏伊诗苏伊诗女女92929901100399011003王苏朋王苏朋男男7676学生成绩表学生成绩表Sun.Mon.Tue.Wen.Thu.Fri.Sat.周名缩写表周名缩写表1 1

8、）表中每一行信息虽然组成的内容不同，但都代表某个明确独）表中每一行信息虽然组成的内容不同，但都代表某个明确独立的含义，将表中每一行信息称之为一个数据元素；立的含义，将表中每一行信息称之为一个数据元素；2 2）每个数据元素在表中的位置固定，除了第一个元素和最后一）每个数据元素在表中的位置固定，除了第一个元素和最后一个元素外，其余元素都有唯一一个前驱元素和唯一一个后继元素；个元素外，其余元素都有唯一一个前驱元素和唯一一个后继元素；3 3）表中数据元素的个数不相同，有长有短；）表中数据元素的个数不相同，有长有短；4 4）大多数表中数据元素会增加或减少，是动态变化的。但也有）大多数表中数据元素会增加或

9、减少，是动态变化的。但也有一些表是固定不变，一些表是固定不变，将这些表格形式的数据加以抽象，统称为线性表。将这些表格形式的数据加以抽象，统称为线性表。上述表格数据具有如下共同特点：上述表格数据具有如下共同特点：什么是线性表什么是线性表试举出日常生活中线性表的例子？试举出日常生活中线性表的例子？指指n(n0)n(n0)个元素个元素a a1 1，a a2 2，a a3 3，a an n 的的有限集合，集合中的元素除第一个与最有限集合，集合中的元素除第一个与最后一个元素外，其它元素都只有一个直后一个元素外，其它元素都只有一个直接前趋元素和一个直接后继元素。接前趋元素和一个直接后继元素。对线性表有哪些

10、处理（或操作）呢？对线性表有哪些处理（或操作）呢？1 1）统计线性表里总共有多少个元素。简称）统计线性表里总共有多少个元素。简称求表长求表长，记作，记作 LengthLength（L L），），2 2）获取线性表中某个数据元素的信息。简称）获取线性表中某个数据元素的信息。简称取元素取元素，记作，记作 GetGet（L L，i i）3 3）置换或修改线性表中某个数据元素的信息。简称）置换或修改线性表中某个数据元素的信息。简称置换元素置换元素，记作记作ReplaceReplace（L L，i i，x x）4 4）在线性表中某个位置上增加一个数据元素。简称）在线性表中某个位置上增加一个数据元素。简称

11、插入元素插入元素，记作记作InsertInsert（L L，i i，x x）5 5）删除线性表中某个位置上的一个数据元素。简称）删除线性表中某个位置上的一个数据元素。简称删除元素删除元素，记作记作DeleteDelete（L L，i i）6 6）查找某个数据元素是否在线性表中存在。简称）查找某个数据元素是否在线性表中存在。简称查找元素查找元素，记作记作LocateLocate（L L，x x）7 7）对线性表中的数据元素按某个数据项的值递增（或递减）对线性表中的数据元素按某个数据项的值递增（或递减）的顺序排列。简称的顺序排列。简称排序排序，记作，记作Sort(L)Sort(L)。线性表的顺序存

12、储结构线性表的顺序存储结构-顺序表类顺序表类线性表的非顺序存储结构线性表的非顺序存储结构-链表类链表类线性表的两种存储结构线性表的两种存储结构顺序表类线性表的顺序存贮结构就是将线性表的每个数据元素线性表的顺序存贮结构就是将线性表的每个数据元素按其逻辑次序依次存放在一组地址连续的存贮单元里按其逻辑次序依次存放在一组地址连续的存贮单元里Loc(1)Loc(1)+CLoc(1)+C*(j-1)存储地址内存状态数据元素符号i const int MAXSIZE=100;const int MAXSIZE=100;/顺序表最大允许长度顺序表最大允许长度class SeqListclass SeqList

13、public:public:ElemType dataMAXSIZE;/ElemType dataMAXSIZE;/存储数据的数组存储数据的数组 int length;int length;/顺序表当前长度顺序表当前长度 SeqList()length=0;/SeqList()length=0;/构造函数构造函数 void ClearList()length=0;/void ClearList()length=0;/将顺序表置为空表将顺序表置为空表 bool IsListEmpty()return length=0;bool IsListEmpty()return length=0;/判断是否

14、为空表判断是否为空表 /判断顺序表是否为满判断顺序表是否为满 bool IsListFull()return length=MAXSIZE;bool IsListFull()return length=MAXSIZE;void ListDelete(int i);/void ListDelete(int i);/在表中删除第在表中删除第i i个元素个元素 /在表中第在表中第 i i 个位置插入新元素个位置插入新元素x x void ListInsert(int i,ElemType x);void ListInsert(int i,ElemType x);int Find(ElemType x

15、);int Find(ElemType x);/在表中查找元素在表中查找元素;由于不同的线性表，其数据元素类型不一样由于不同的线性表，其数据元素类型不一样例如学生花名册中每个元素有四个数据项例如学生花名册中每个元素有四个数据项航班时刻表也有多个数据项。航班时刻表也有多个数据项。从通用性出发，表中的元素为一个模板数据类型从通用性出发，表中的元素为一个模板数据类型DataTypeDataType。TemplateTemplate数据元素类型说明插入前：（插入前：（a a 1 1，a a 2 2，a a i-1 i-1，a a i i，a a n n）插入后：（插入后：（a a 1 1，a a 2

16、2，a a i-1 i-1，x x ，a a i i，a a n n）第第1 1步步:判定表不满方可插入；判定表不满方可插入；第第2 2步步:判定插入位置判定插入位置i i的合法性；的合法性；第第3 3步步:将第将第n n至第至第i i个元素后移一个存储位置；个元素后移一个存储位置；第第4 4步步:将将x x存入到存入到a a i-1 i-1之后空间；之后空间；第第5 5步步:线性表的长度加线性表的长度加1 1。插入算法 0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 x ai an-1 an 0 1 2 i-2 i-1 i n maxsize a1 a2 a3

17、 ai-1 ai ai+1 an 序序号号 内内容容 序序号号 内内容容 插插入入前前 插插入入后后 顺顺序序表表中中插插入入元元素素前前后后状状态态 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:N/2 a a1 1 a a2 2

18、 a a3 3 a a4 4 a an-1n-1 a an n 有有N+1N+1处可能插入处可能插入,等概率值为等概率值为1/(1+N)1/(1+N)插入算法评价删除前：（删除前：（a a 1 1，a a 2 2，a a i-1 i-1，a a i i，a a i+1 i+1，a a n n）删除后：（删除后：（a a 1 1，a a 2 2，a a i-1 i-1，a a i+1 i+1，a a n n）第第1 1步：判定表不空方可删除；步：判定表不空方可删除；第第2 2步：判定删除位置步：判定删除位置i i值的合法性；值的合法性；第第3 3步：将第步：将第i+1i+1至第至第n n个元素依

19、次向前移动一个存储位置；个元素依次向前移动一个存储位置；第第4 4步：将线性表的长度减步：将线性表的长度减1 1。删除算法 0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 ai+1 an 0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 ai ai+1 an 序序号号 内内容容 序序号号 内内容容 删删除除前前 删删除除后后 顺顺序序表表中中删删除除元元素素前前后后状状态态 void SeqList:Delete(int i)if(iL-length)cout表中没有第表中没有第i个元素个元素;else for(int j=i;j=

20、length-1;j+)dataj-1=dataj;/元素依次向前移动元素依次向前移动 length-;删除函数的时间复杂度：（删除函数的时间复杂度：（N-1N-1）/2 /2 在等概率条件下在等概率条件下插入和删除算法详见插入和删除算法详见rjjcjg_1.cpprjjcjg_1.cpp删除算法评价int SeqList:Find(ElemType x)for(int i=0;inext=NULL;/头结点的指针为空头结点的指针为空 int ListSize();/求单链表长度求单链表长度 LNode*GetElemPointer(int pos);/返回表中指定序号结点的指针返回表中指定序

21、号结点的指针 void InsertList(int i,ElemType x);/向单链表第向单链表第i个位置插入元素个位置插入元素x LNode*LinkList:DeleteList(int i);/从单链表中删除第从单链表中删除第i个结点个结点 LNode*Find(ElemType x)；/在单链表中查找数据值为在单链表中查找数据值为x的结点的结点;单链表类的完整定义如下：指针操作指针操作假如假如p p为指向某一结点的指针为指向某一结点的指针则该结点的数据域用则该结点的数据域用p-datap-data表示表示 该结点的指针域用该结点的指针域用p-nextp-next表示表示它们都是变

22、量，可以被赋值，也可向其他变量赋值。它们都是变量，可以被赋值，也可向其他变量赋值。例如例如:假定假定datadata为整型变量为整型变量,则则p-data=5;p-next=NULL;将将结点变为结点变为:5 NULL next aiai-1ai-1aiai-1ai+1qqpp 如果如果p为指向结点为指向结点ai的指针，那么的指针，那么p-next就是指向就是指向ai后继结点后继结点ai+1的指针；若的指针；若q为另一指针变量为另一指针变量 p=q 指针指针p指向指针指向指针q所指的结点所指的结点 p=q-next 指针指针p指向指针指向指针q所指结点的后继所指结点的后继指针操作指针操作要确定

23、链表长度需要走遍表中所有结点才能算出。要确定链表长度需要走遍表中所有结点才能算出。为了保持头指针不变，使用了指针为了保持头指针不变，使用了指针p p在链表中移动。在链表中移动。求单链表的长度求单链表的长度int LinkList:ListSize()int LinkList:ListSize()LNode LNode*p=head-next;/pp=head-next;/p指向第一个元素所在结点指向第一个元素所在结点 int len=0;int len=0;while(p!=NULL)while(p!=NULL)/逐个检测逐个检测p p结点存在与否结点存在与否 len+;len+;p=p-ne

24、xt;p=p-next;/指针后移指针后移 return len;return len;LNode*LinkList:GetElemPointer(int pos)if(posnext;/p为首元结点指针为首元结点指针 int k=1;while(p!=NULL&knext;k+;if(k=pos&p!=NULL)return p;/返回第返回第pos个结点指针个结点指针 else return NULL;/该位置不存在该位置不存在 返回单链表中指定序号的结点的指针返回单链表中指定序号的结点的指针a 1ai-1aia nheada 1ai-1aia nheaddatapreviouscurre

25、ntnew nodeLnode*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)cout

26、 idata=x;s-next=p-next;/定义结点定义结点s的指针域的指针域 p-next=s;/修改结点修改结点p的指针域的指针域 Ai-1AiXpsp-next=s;新结点链入表中示意图s-next=p-next;a 1ai-1ai+1a nheadaia 1ai-1ai+1a nheadpreviouscurrentaiprevious-next=current-next;delete current;单链表类的删除算法判定空表判定空表寻找插入位置寻找插入位置确认插入有错否确认插入有错否修改链表指针修改链表指针收回结点空间收回结点空间LNode*LinkList:DeleteLis

27、t(int i)if(i1)cout”不存在第不存在第”i”个元素个元素”;else LNode*p=head;/p指向头结点指向头结点(第第0个结点个结点)LNode*q;/q和和p最终分别指向第最终分别指向第i-1和第和第i个结点个结点 int k=0;while(p!=NULL&knext;k+;if(p=NULL)cout inext=p-next;/从链表中删除该结点从链表中删除该结点delete p;/释放结点释放结点p Ai-1Aiq-next=p-next;delete p;Ai+1qp删除Ai结点示意图XX可以按照数据元素本身的值进行查找，也可以按照可以按照数据元素本身的值进

28、行查找，也可以按照数据元素的某个属性进行查找。这里仅给出按照数据元素的某个属性进行查找。这里仅给出按照数据元素本身的值进行查找的算法。数据元素本身的值进行查找的算法。在单链表中查找数据值为在单链表中查找数据值为x x的结点的结点LNode*LinkList:Find(ElemType x)LNode*p=head-next;/p指向第一个元素所在结点指向第一个元素所在结点 while(p!=NULL&p-data!=x)p=p-next;return p;循环链表headA1AnA2head空循环链表空循环链表非空循环链表非空循环链表前驱指针域前驱指针域 prior后继指针域后继指针域 nex

29、t数据域数据域 data双向链表结点示意图双向链表结点示意图每个数据元素存储结构如下：每个数据元素存储结构如下：head.ana2a1 约瑟夫环问题可以解释为：将整数约瑟夫环问题可以解释为：将整数1 1至至n n围围成一个圆圈，假定从某个整数开始顺时针成一个圆圈，假定从某个整数开始顺时针从从1 1数到数到m m时，令该位置整数出列；然后再时，令该位置整数出列；然后再从下一数开始，顺时针从从下一数开始，顺时针从1 1数到第数到第m m时再令时再令其出列，如此下去，直到圆圈中无整数为其出列，如此下去，直到圆圈中无整数为止。请写出所有数字出列的顺序。止。请写出所有数字出列的顺序。链表应用举例链表应用

30、举例 演示【演示【例例2-2】2-2.cpp2-2.cpp堆栈堆栈stack探讨货仓工作原理探讨货仓工作原理假设只有一个门的货仓，先进去的货物后出来。假设只有一个门的货仓，先进去的货物后出来。若线性表比照货仓，货物比照数据元素。若线性表比照货仓，货物比照数据元素。元素只能在线性表的一端插入删除。元素只能在线性表的一端插入删除。堆栈的定义堆栈的定义堆栈堆栈指插入和删除元素操作只能在表指插入和删除元素操作只能在表的一端进行，这种线性表称为堆栈。的一端进行，这种线性表称为堆栈。堆栈又称堆栈又称LIFOLIFO表或表或FILOFILO表表DCBA插入插入进栈进栈删除删除出栈出栈栈顶栈顶栈底栈底创建一个

31、堆栈：创建一个堆栈：setnull(stack)setnull(stack)判空栈：判空栈：emptystack(stack)emptystack(stack)元素进栈：元素进栈：push(stack,data)push(stack,data)元素出栈：元素出栈：pop(stack)pop(stack)取栈顶元素：取栈顶元素：gettop(stack)gettop(stack)堆栈的基本操作由于栈是一个特殊线性表，顺序栈类与顺序表基本相同。由于栈是一个特殊线性表，顺序栈类与顺序表基本相同。类似于线性表的顺序存储结构，顺序栈类的类似于线性表的顺序存储结构，顺序栈类的C+C+描述如下：描述如下：#

32、define STACKSIZE 100 class SeqStack public:ElemType dataSTACKSIZE;/存储元素的数组存储元素的数组 int top;SeqStack()top=-1;/构造函数构造函数 BOOL stack_empty();/判栈空函数判栈空函数 BOOL push(ElemType x);/元素进栈函数元素进栈函数 BOOL pop(ElemType&result);/元素出栈函数元素出栈函数 BOOL gettop(ElemType&result);/取栈顶元素取栈顶元素 stack();顺序栈类定义A1A1A2A2A3A3A4A4A5A5A

33、6A6内存储器内存储器toptop5 5 栈顶栈顶0 0 栈底栈底进栈进栈出栈出栈进栈的核心操作：进栈的核心操作：top+;top+;datatop=X;datatop=X;出栈的核心操作：出栈的核心操作：X=datatop;X=datatop;top-;top-;1 12 23 34 4顺序栈类的进栈函数第第1步：判断栈是否已满，若栈满则元素不步：判断栈是否已满，若栈满则元素不 能进栈，退出函数；能进栈，退出函数；第第2步：栈顶下标变量步：栈顶下标变量top增增1，即，即top+；第第3 3步：在步：在toptop所指向的当前位置存入元素所指向的当前位置存入元素x x。BOOL SeqSta

34、ck push(ElemType x)if(top=STACKSIZE-1)cout栈满。又称栈溢出栈满。又称栈溢出(上溢上溢)n;return FALSE;else top+;datatop=x;return TRUE;顺序栈类的出栈函数第第1步：判定栈是否为空栈，若为空则无元步：判定栈是否为空栈，若为空则无元 素可以出栈，退出函数；素可以出栈，退出函数；第第2步：弹出（删除）栈顶元素；步：弹出（删除）栈顶元素；第第3 3步：栈顶下标变量步：栈顶下标变量toptop减减1 1，即，即top-top-。BOOL SeqStack pop(ElemType&result)if(top=1)cou

35、t栈空栈空.又称栈溢出又称栈溢出(下溢下溢)n;return false;else result=datatop;top-;return true;顺序栈类的取栈顶函数第第1步：判定栈是否为空栈，若为空则无元步：判定栈是否为空栈，若为空则无元 素可以出栈，退出函数；素可以出栈，退出函数；第第2步：弹出（删除）栈顶元素；步：弹出（删除）栈顶元素；BOOL SeqStack gettop(ElemType&result)if(top=1)coutdata=x;p-next=top;top=p;链栈进栈操作若栈不空，则删除栈顶元素，用若栈不空，则删除栈顶元素，用result返回其值。返回其值。voi

36、d LinkStack:Pop(ElemType&result);SNode*p;if(top!=NULL)result=top-data;p=top;top=top-next;delete p;链栈出栈操作三种不同的表示方法：三种不同的表示方法：前缀表示法前缀表示法 OPOPS S1 1S S2 2 例如例如6+36+3写成写成+63+63中缀表示法中缀表示法 S S1 1OPOPS S2 2 例如例如6+36+3写成写成6+36+3后缀表示法后缀表示法 S S1 1S S2 2OPOP 例如例如6+36+3写成写成63+63+假定表达式是由加减乘除和数字构成。最常见的表假定表达式是由加减乘

37、除和数字构成。最常见的表达式为下列形式：达式为下列形式：(操作数操作数S S1 1)()(运算符运算符OPOP)()(操作数操作数S S2 2)算术表达式表示算术表达式表示同时，任何表达式都可分解为下列形式：同时，任何表达式都可分解为下列形式：(子表达式子表达式E E1 1)()(运算符运算符OPOP)()(子表达式子表达式E E2 2)它的后缀表示法应写成：它的后缀表示法应写成：(E(E1 1的后缀表示的后缀表示)(E)(E2 2的后缀表示的后缀表示)OPOP只要不断对子表达式进一步分解，总能将子表只要不断对子表达式进一步分解，总能将子表达式分解为最简单形式，因此任何四则运算表达式分解为最简

38、单形式，因此任何四则运算表达式都可写成前缀式或后缀式。达式都可写成前缀式或后缀式。例如：例如：2 2*(6+3)(6+3)2 2(6+3)(6+3)*2 263+63+*。(注意：转化为后缀式后括号去掉注意：转化为后缀式后括号去掉)算术表达式表示算术表达式表示用后缀式求值的算法为：用后缀式求值的算法为：后缀表达式求值后缀表达式求值人们习惯于中缀式的计算，但计算机在人们习惯于中缀式的计算，但计算机在求值的时候往往利用前缀式或后缀式。求值的时候往往利用前缀式或后缀式。例如后缀式例如后缀式263+263+*的计算过程为的计算过程为2 2、6 6、3 3依依次入栈，读次入栈，读+号则令号则令3 3和和

39、6 6依次出栈，计算依次出栈，计算6+36+3后后将结果将结果9 9入栈，读入栈，读*号则令号则令9 9和和2 2依次出栈，计算依次出栈，计算2 2*9 9后将结果后将结果1818入栈。这时入栈。这时1818就是最终结果。就是最终结果。【例【例2-32-3】假定表达式是由不超过四个实数进行】假定表达式是由不超过四个实数进行四则运算构成的算式，要编写一个程序来求解四则运算构成的算式，要编写一个程序来求解该算式的结果。该算式的结果。运行运行2_3.cpp2_3.cpp举例计算后缀表达式举例计算后缀表达式中缀式变成后缀式中缀式变成后缀式转换规则是：转换规则是：步骤步骤栈中元素栈中元素 输出结果输出结

40、果 说明说明1(（进栈（进栈2(1输出输出13(+1+进栈进栈4(+1 2输出输出25 1 2 +退栈输出，退栈退栈输出，退栈到（止到（止6*1 2 +*进栈进栈7*(1 2 +（进栈（进栈8*(1 2 +（进栈（进栈9*(1 2 +8输出输出810*(-1 2 +8 -进栈进栈将中缀表达式将中缀表达式(1+2)(1+2)*(8-2)/(7-4)(8-2)/(7-4)变成等价的后缀表达变成等价的后缀表达式。式。现在用栈来实现该运算，栈的变化及输出结果如下：现在用栈来实现该运算，栈的变化及输出结果如下：11*(-1 2 +8 2输出输出212*(1 2 +8 2 -退栈输出，退退栈输出，退栈到（

41、止栈到（止13*(/1 2 +8 2 -/进栈进栈14*(/(1 2 +8 2 -（进栈进栈15*(/(1 2 +8 2 -7输出输出716*(/(-1 2 +8 2 -7-进栈进栈17*(/(-1 2 +8 2 -7 4输出输出418*(/1 2 +8 2 -7 4 -退栈输出，退退栈输出，退栈到（止栈到（止19*1 2 +8 2 -7 4 -/退栈输出，退退栈输出，退栈到（止栈到（止20 1 2 +8 2 -7 4 -/*退栈并输出退栈并输出对头对头队尾队尾队列类似日常生活中的排队原理队列类似日常生活中的排队原理 LILO表表 FIFO表表分析进队顺序：分析进队顺序：A,B,C 则出队顺序

42、有哪些？则出队顺序有哪些？进队进队出队出队队列队列也是特殊的线性表。它只允许在线性表的一个端也是特殊的线性表。它只允许在线性表的一个端点进行插入，而在线性表的另一个端点进行删除操作点进行插入，而在线性表的另一个端点进行删除操作ABCD EFG setnull（QUEUE）创建一个空队列创建一个空队列QUEUE。empty_gueue（QUEUE）判定队列是否为空。判定队列是否为空。addqueue（QUEUE，x）入列操作。入列操作。delqueue（QUEUE）出列操作。出列操作。frontqueue(QUEUE）读取队列的队头元素。读取队列的队头元素。队列的五种基本运算队列的五种基本运算类

43、似于顺序表类的定义，类似于顺序表类的定义，C+描述如下：描述如下：const int QUEUESIZE=200;class SeqQueue public:ElemType dataQUEUESIZE;int front,rear;SeqQueue()front=rear=1;/创建空队列创建空队列 BOOL queue_empty();/判队列空判队列空 BOOL addqueue(ElemType x);/元素进队元素进队 BOOL delqueue(ElemType&element);/元素出队元素出队 BOOL frontgueue(ElemType&element);/取队头取队头

44、 queue();顺序队列类定义入列操作：入列操作：rear+;rear+;datarear=X;datarear=X;出列操作：出列操作：front+;front+;X=datafront;X=datafront;分析：队列空的条件分析：队列空的条件 front=rearfront=rear 队列满的条件队列满的条件 rear=QUEUESIZE-1rear=QUEUESIZE-1 分析队列操作分析队列操作队列假满的状态队列假满的状态 front=rear=QUEUESIZE-1 或或 front -1&rear=QUEUESIZE-1 假设假设MAXSIZE为为8rear front E

45、F G H front rear解决假满的两种方法：解决假满的两种方法：1、整个队列中的元素左移、整个队列中的元素左移 2、构造循环队列、构造循环队列入列操作：入列操作：rear=(rear+1)%QUEUESIZE;datarear=X;出列操作：出列操作：front=(front+1)%QUEUESIZE;X=datafront;循环队列示意图循环队列示意图0 17 26 35 40 1 2 3 4 5 6 7为了将队空和对满的条件加以区分，一般不使用为了将队空和对满的条件加以区分，一般不使用front指针所指的位置。指针所指的位置。队空条件为队空条件为:front=rear队满条件为队满

46、条件为:(rear+1)%QUEUESIZE=front30124567frontrearABCD30124567frontrear30124567frontrearABCDFGE (a)(a)循环队列空循环队列空 (b)(b)非空循环队列非空循环队列 (c)(c)循环队列满循环队列满 循环队列示意图循环队列示意图/循环队列进队函数循环队列进队函数bool SeqQueue:addqueue(ElemType x)if(rear+1)%MAXSIZE=front)printf(“队列已满，元素不能进队列！队列已满，元素不能进队列！n”);return false;else real=(real

47、+1)%MAXSIZE;datareal=x;return true;/循环队列出队函数循环队列出队函数bool SeqQueue:delqueue(ElemType&x)if(front=rear)printf(“队列已空，无法删除元素队列已空，无法删除元素n”n”);return false;else front=(front+1)%QUEUESIZE;x=datafront;return true;链队列链队列队列链式存储队列链式存储 Qa1anfrontrear非空链队列非空链队列 struct QNode /类似于单链表的类似于单链表的C+描述如下：描述如下：ElemType dat

48、a;struct QNode*next;class LinkQueue public:QNode*front;/队头指针队头指针QNode*rear;/队尾指针队尾指针 LinkQueue()front=new QNode;/建立头结点建立头结点 front-next=NULL;rear=front;/尾指针也指向头结点尾指针也指向头结点 int Length();/求队列长度求队列长度void EnQueue(ElemType x);/入队操作入队操作void DeQueue(ElemType&e);/出队操作出队操作void GetHead(ElemType&e);/求队头元素求队头元素;

49、链队列返回队列的元素个数，即队列的长度。返回队列的元素个数，即队列的长度。int LinkQueue:Length()QNode*p=front;int len=0;while(p!=rear)len+;p=p-next;return len;求队列的长度求队列的长度链队列进队算法：链队列进队算法：1、申请新结点、申请新结点 2、链入新结点、链入新结点 void LinkQueue:EnQueue(ElemType x)QNode*s=new QNode;/建立新结点建立新结点s s-data=x;s-next=NULL;rear-next=s;/在队尾插入结点在队尾插入结点s rear=s;

50、/修改队尾指针修改队尾指针链队列进队算法链队列出队算法：链队列出队算法：1、判断队列空否、判断队列空否 2、队头元素出队、队头元素出队 3、出队元素归还操作系统、出队元素归还操作系统void LinkQueue:DeQueue(ElemType&e)QNode*p;if(front=rear)coutnext;e=p-data;front-next=p-next;if(rear=p)rear=front;delete p;删除最后一个元素时，需要修改尾指针，使其指向头结点删除最后一个元素时，需要修改尾指针，使其指向头结点上机练习一：求两个链表的交集上机练习一：求两个链表的交集建立两个带头结点的

51、单链表；建立两个带头结点的单链表；通过插入函数插入两个链表中的所有元素通过插入函数插入两个链表中的所有元素 创建第三个带头结点的单带头结点的单链表 从两个表头开始循环比较，只有相等才能插入上机练习二：求上机练习二：求k阶斐波那切数列某一项阶斐波那切数列某一项k阶斐波那切数列阶斐波那切数列ai定义如下：定义如下：建立一个容量为建立一个容量为k k的循环队列，将前的循环队列，将前k k个个元素依次入队。然后计算第元素依次入队。然后计算第k+1k+1个元素，它等于队个元素，它等于队列中全部元素之和。而后将对头元素出队，将第列中全部元素之和。而后将对头元素出队，将第k+1k+1个元素入队。重复上述过程

52、，就可求得任意指个元素入队。重复上述过程，就可求得任意指定项元素的值定项元素的值。【例例2-4】利用循环队列求】利用循环队列求k阶斐波那切数列阶斐波那切数列 某一式的值。某一式的值。前面所学的数据结构都是线性关系结构，即每个数前面所学的数据结构都是线性关系结构，即每个数据元素都只有唯一的前驱元素和唯一的后继元素。据元素都只有唯一的前驱元素和唯一的后继元素。但是在客观世界中数据元素之间的关系不一定是线但是在客观世界中数据元素之间的关系不一定是线性关系，即不一定是唯一的前驱和唯一的后继，称为非性关系，即不一定是唯一的前驱和唯一的后继，称为非线性关系结构。线性关系结构。例如分析任何一个企事业单位的组

53、织机构，会发现例如分析任何一个企事业单位的组织机构，会发现任何一个部门机构，它只隶属于一个部门机构，而下辖任何一个部门机构，它只隶属于一个部门机构，而下辖一个以上部门机构。假如把部门机构看成数据元素，那一个以上部门机构。假如把部门机构看成数据元素，那么可以说任何一个数据元素有唯一的前驱元素，但有多么可以说任何一个数据元素有唯一的前驱元素，但有多个后继元素。个后继元素。又例如日常生活中对事物的分类又例如日常生活中对事物的分类水果的分类。水果的分类。非线性数据结构：树和图 西安交通大学管理学院电信学院医学院信控系计算机系电子系组织机构示意水果芒果苹果梨香蕉红富士黄元帅秦冠巴拿马芝麻水果分类示意RA

54、EGDCBXFZYKJIHMLNPOQVUTS*+%将上述分层结构抽象成如下所示的结构倒置树 树是包含树是包含n n个数据元素的有限集合个数据元素的有限集合T T（n1n1），并且满足：），并且满足：（1 1）T T中有一个称为根的结点中有一个称为根的结点rootroot；（2 2）T T中除根以外的其余结点被分成中除根以外的其余结点被分成m m（nm0nm0）个互不相交）个互不相交的集合的集合T T1 1、T T2 2、T Tm m，且每一个集合又符合上述两条，即它，且每一个集合又符合上述两条，即它们本身又是一棵树，这些树称为们本身又是一棵树，这些树称为rootroot的子树。的子树。树的递

55、归定义T1T2TNT3T4GACFDEB结点结点表示树中的数据元素；表示树中的数据元素；树枝树枝表示树中的数据元素与数据元素之间的关系；表示树中的数据元素与数据元素之间的关系；叶子结点叶子结点表示没有后继的结点称为叶子（或终端结点）；表示没有后继的结点称为叶子（或终端结点）；分支结点分支结点表示非叶子结点称为分支结点（或非终端结点）；表示非叶子结点称为分支结点（或非终端结点）；结点的度结点的度意指一个结点的子树数目就称为该结点的度；意指一个结点的子树数目就称为该结点的度；树的度树的度意指一棵树上所有结点的度的最大值就是这棵树的度；意指一棵树上所有结点的度的最大值就是这棵树的度；结点的层次结点的

56、层次确定根结点的层数为确定根结点的层数为1 1，其它任何结点的层数等于，其它任何结点的层数等于 它的父结点的层数加它的父结点的层数加1 1；有关树的基本术语树的深度树的深度意指一棵树中，结点的最大层次值就是树的深度；意指一棵树中，结点的最大层次值就是树的深度；孩子结点孩子结点代表某结点的子树的根称为该结点的孩子结点；代表某结点的子树的根称为该结点的孩子结点；双亲结点双亲结点相对于某结点的前驱结点，称该结点为双亲结点；相对于某结点的前驱结点，称该结点为双亲结点；兄妹兄妹意指同属于一个双亲的孩子结点之间互称为兄弟；意指同属于一个双亲的孩子结点之间互称为兄弟；堂兄妹堂兄妹意指其双亲在同一层的结点之间

57、互称为兄弟；意指其双亲在同一层的结点之间互称为兄弟；有序树有序树如果一棵树中结点的各子树看成是从左至右依次有序排如果一棵树中结点的各子树看成是从左至右依次有序排 列且不能交换，则该树就称为有序树；列且不能交换，则该树就称为有序树；无序树无序树如果一棵树中结点的各子树可以互换排列次序，则该树如果一棵树中结点的各子树可以互换排列次序，则该树 称为无序树；称为无序树；森林森林森林是森林是n n棵互不相交的树的集合（棵互不相交的树的集合（n0n0）；）；建空树建空树 记作记作setnull(T)setnull(T)，置，置T T为空树。为空树。求根结点求根结点 记作记作root(x)root(x)，求

58、，求x x所在树的根结点。所在树的根结点。求双亲结点求双亲结点 记作记作parent(Tparent(T，x)x)，在树，在树T T中取出结点中取出结点x x的双亲。的双亲。求孩子结点求孩子结点 记作记作child(T,x,i)child(T,x,i)，在树，在树T T中取出结点中取出结点x x的第的第i i个孩子。个孩子。插入结点插入结点 记作记作ins_child(T,y,i,x)ins_child(T,y,i,x)，将，将x x作为树作为树T T中中y y结点的第结点的第i i个孩子。个孩子。删除子树删除子树 记作记作del_child(T,x,I)del_child(T,x,I)，即删

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

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

61、arent(BT,x)，在二叉树中求结点，在二叉树中求结点x x的双亲。的双亲。求左孩子结点求左孩子结点 记作记作lchild(BT,x),lchild(BT,x),在二叉树在二叉树BTBT中求结点中求结点x x的左孩子。的左孩子。求右孩子结点求右孩子结点 记作记作rchild(BT,x),rchild(BT,x),在二叉树在二叉树BTBT中求结点中求结点x x的右孩子。的右孩子。插入左孩子结点插入左孩子结点 记作记作ins_lchild(BT,x,y),ins_lchild(BT,x,y),将结点将结点y y置为结点置为结点x x的左孩子。的左孩子。插入右孩子结点插入右孩子结点 记作记作in

62、s_rchild(BT,x,y),ins_rchild(BT,x,y),将结点将结点y y置为结点置为结点x x的右孩子。的右孩子。删除左孩子删除左孩子 记作记作del_lchild(BT,x),del_lchild(BT,x),在二叉树在二叉树BTBT中，删除结点中，删除结点x x的左子树。的左子树。删除左孩子删除左孩子 记作记作del_rchild(BT,x),del_rchild(BT,x),在二叉树在二叉树BTBT中，删除结点中，删除结点x x的右子树。的右子树。遍历二叉树遍历二叉树 记作记作TRAVERSE(BT),TRAVERSE(BT),即从根结点出发，按某种次序，依次访问即从根

63、结点出发，按某种次序，依次访问 二叉树中每个结点，且每个结点只访问一次。二叉树中每个结点，且每个结点只访问一次。二叉树的基本操作左指针域左指针域 数据域数据域 右指针域右指针域二叉树的非顺序存储结构 根据二叉树的特性：任何一个结点最多有左、根据二叉树的特性：任何一个结点最多有左、右两个子树，这样可以为树中每个数据元素设计右两个子树，这样可以为树中每个数据元素设计三个存储区域（或称变量）。三个存储区域（或称变量）。一个域用来存放数据元素值，两个域用来存一个域用来存放数据元素值，两个域用来存放指向左右子树根的指针。也就是说对于二叉树放指向左右子树根的指针。也就是说对于二叉树中任意一个数据元素可以设

64、计成如下存储结构。中任意一个数据元素可以设计成如下存储结构。俗称结点。俗称结点。二叉树的二叉链表存储结构示意图ABCFEGDABCDEGFVVVVVVVVstruct BinTreeNode/结点的定义结点的定义ElemType data;struct BinTreeNode*leftChild,*rightChild;class BinTree /二叉链表类的定义二叉链表类的定义 public:BinTreeNode*root;/定义根结点指针定义根结点指针BinTree()root=NULL;/构造函数，创建空树构造函数，创建空树bool IsEmpty()return root=NULL

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

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