数据结构1学习.pptx

2.1 数据结构的概念数据结构的概念数据结构是计算机科学与技术专业的专业基础课，所有的计算机系统软件和应用软件都要用到各种类型的数据结构。数据是一些可以被计算机接收和处理的描述客观事物的符号。这些符号可以是数字、字符、图形、声音及其他。数据元素是数据(集合)中的一个“个体”，是数据的基本单位。也可称为节点、记录。数据对象是具有相同性质的若干个数据元素的集合。第1页/共114页数据结构是指数据以及数据元素相互之间的联系。可以看作是相互之间存在着某种特定关系的数据元素的集合。因此,可时把数据结构看成是带结构的数据元素的集合。四类基本的结构：集合结构：数据元素间的关系是“属于同一个集合”。集合是元素关系极为松散的一种结构。线性结构：数据元素之间存在着一对一的关系。树型结构：数据元素之间存在着一对多的关系。图形结构：数据元素之间存在着多对多的关系，图形结构也称作网状结构。第2页/共114页数据结构的形式定义为：数据结构S是一个二元组 S=（D，R）其中D是一个数据元素非空的有限集合；R是定义在D 上的关系，是非空集合。（a）集合结构 （b）线性结构 （c）树型结构（d）图形结构图2-1 四类基本结构的示意图第3页/共114页数据结构包括如下3个方面：（1）数据元素之间的逻辑关系，即数据的逻辑结构。（2）数据元素及其关系在计算机存储器中的存储 方式，即数据的存储结构，也称为数据的物 理结构。（3）施加在该数据上的操作，即数据的运算。第4页/共114页2.1.1数据的逻辑结构数据的逻辑结构数据的逻辑结构也称数据结构，是数据元素之间关系的描述，是从具体问题抽象出来的数学模型，它与数据的存储无关。数据的逻辑结构有两种：线性结构：各数据元素之间的逻辑关系可用一个线性序列表示，如线性表，数据元素只按先后次序连接。非线性结构：不能用线性结构表达的结构，如树、图等；树中的数据元素是分层次的纵向连接，而图中的数据元素则是有各种各样的复杂连接。第5页/共114页2.1.2 数据的物理结构数据的物理结构数据的物理结构是数据的逻辑结构在计算机中的表示或称为映像；也称存储结构。研究的是数据结构在计算机中的实现方法。【实例2-1】有一个学生表如表2-1所示。表中的数据元素是学生记录,每个数据元素由四个数据项(即学号、姓别、性别和C语言)组成。张小明的C语言考试成绩为92分，92就是该同学的成绩数据。了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。第6页/共114页第7页/共114页1顺序存储结构数据元素按某种顺序依此存放在计算机存储器的连续存储单元中，它们之间的关系由存储单元的邻接关系来体现。其存储的地址由起始地址和元素所占的存储空间来决定。S是起始地址，H是每个元素所占的空间，则第i个元素的存储地址为：Loc(i)=Loc(1)+(i-1)*H=S+(i-1)*H第8页/共114页顺序存储结构的主要特点：（1）节点中只有自身信息域，没有连接信息域。因此存储密度大，利用率高；（2）计算确定数据结构中第i 个元素的位置，可以（直接）随机存取（3）插入和删除操作会引起大量的元素移动；（4）必须存储在一片地址连续的存储单元中；第9页/共114页2.链接存储结构在链接存储结构中，每个节点即数据元素由数据域Data和指针域Next两部分组成。数据域存放元素本身的数据，指针域存放与其相邻的元素地址。链接存储结构如图2-3所示。第10页/共114页链接存储结构的主要特点：（1）节点除有自身信息域外，还有表示连接信息的指针域。因此存储密度小，利用率低；（2）可使逻辑上相邻的节点在物理上不邻接，使用于复杂的逻辑结构；（3）插入和删除操作灵活方便；只要修改指针域的值即可；（4）可以存储在不连续的存储单元中；第11页/共114页3数据结构的运算数据结构的运算插入:在数据结构中的指定位置插入新的元素。删除:根据一定的条件，将某个节点从数据结构中删除。更新:更新数据结构中某个指定节点的值。检索:在给定的数据结构中，找出满足一定条件的节点，条件可以是一个或多个数据项的值。排序:根据某一给定的条件，将数据结构中所有的节点重新排列顺序。第12页/共114页2.2 线性表线性表线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为：(a1，a2，ai-1，ai，ai+1，an)其中n为表长，n0 时称为空表。相邻元素之间存在着顺序关系。将ai-1 称为 ai 的直接前趋，ai+1 称为 ai 的直接后继。对于ai，有且仅有一个直接后继 ai+1，而 a1是表中第一个元素没有前趋，an 是最后一个元素无后继。第13页/共114页2.2.1 线性表的存储结构线性表的存储结构具有顺序存储结构的线性表称为顺序表。线性表的顺序存储是指在内存中用地址连续的一块存储空间顺序存放线性表的各元素。因为内存中的地址空间是线性的，用物理上的相邻实现数据元素之间的逻辑相邻关系是简单，知道顺序表首地址和每个数据元素所占地址单元的个数就可求出第i个数据元素的地址，顺序表具有按数据元素的序号随机存取的特点。第14页/共114页从结构性上考虑，通常将data和last封装成一个结构作为顺序表的类型：typedef struct datatype dataMaxSize;int last;lnode,*SeqSeqList;SeqSeqList L;/定义一个顺序表L;第15页/共114页2.2.2 顺序表上基本运算的实现顺序表上基本运算的实现1.插入运算Insert_SeqList(L,i,x)(a1，a2，.，ai-1，ai，ai+1，.，an)插入后表长=原表长+1,成为表长为 n+1 表:(a1，a2，.，ai-1，x，ai，ai+1，.，an)顺序表上完成的步骤：(1)将aian 顺序向下移动，为新元素让出位置；(2)将 x 插入空出的第i个位置；(3)修改 last 指针，使之仍指向最后一个元素。第16页/共114页算法如下：Insert_SeqList(SeqSeqList L，int i，datatype x)int j;if(iL-last+1)printf(插入位置错);/*检查插入位置的正确性*/else for(j=L-last;j=i-1;j-)L-dataj=L-dataj-1;/*移动元素*/L-datai-1=x;/*插入新元素*/L-last+;/*last仍指向最后元素,表的长度1*/第17页/共114页插入算法的时间性能分析：时间主要消耗在了数据的移动上，在第i个位置上插入 x，从 ai 到 an 都要向下移动一个位置，共需要移动 ni1个元素，而 i 的取值范围为：1=i=n+1，即有 n1个位置可以插入。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：设：Pi=1/(n+1)，即为等概率情况，则：第18页/共114页第19页/共114页删除运算Delete_SeqList(L,i)线性表的删除运算是指将表中第 i 个元素从线性表中去掉，删除后表长原表长使原表长为 n 的线性表：(a1，a2，.，ai-1，ai，ai+1，.，an)成为为 n1 的线性表，：(a1，a2，.，ai-1，ai+1，.，an)。i 的取值范围为：1=i=n。如图2-7所示顺序表中的删除。第20页/共114页第21页/共114页算法步骤：(1)将将ai+1an 顺序向上移动。(2)修改last指针，使之仍指向最后一个元素。Delete_List(SeqSeqList L,int i)int j;if(iL-last+1)printf(不存在第i个元素);return(0);else/*检查空表及删除位置的合法性*/for(j=i;jlast;j+)L-dataj-1=L-dataj;/*移动元素*/L-last-;/*last仍指向最后元素,表的长度-1*/return(1);/*删除成功*/第22页/共114页删除算法的时间性能分析：与插入运算相同，时间主要消耗在移动表中元素上，删除第i个元素时，其后面的元素 ai+1an 都要向上移动一个位置，共移动 n-i 个元素，所以平均移动数据元素的次数：在等概率情况下，pi=1/n，则：第23页/共114页2.2.3 线性表的链式存储和运算实现线性表的链式存储和运算实现存储单元地址可连续，可不连续，不要求逻辑上相邻的两个数据元素物理上也相邻，通过“链”将数据元素之间的逻辑关系来，对线性表的插入、删除不需要移动数据元素。1.单链表的表示链表节点定义如下：typedef struct node datatype data;struct node*next;LNode，*LinkList；/LNode是节点的类型定义头指针变量：LinkList L；/LinkList是指向Lnode类型节点的指针类型第24页/共114页第25页/共114页2.单链表的建立，在单链表的尾部插入节点建立单链表算法思路：（1）初始状态：头指针L=NULL，尾指针 r=NULL;（2）按线性表中元素的顺序依次读入数据元素，不是结束标志时，申请节点。（3）将新节点插入到 r 所指节点的后面，然后 r 指向新节点（但第一个节点有所不同，读者注意下面算法中的有关部分）。在尾部插入建立单链L=NULL 或 r=NULL /*初始状态*/第26页/共114页第27页/共114页算法如下：LinkList Creat_LinkList()LinkList L=NULL;Lnode *s,*r=NULL;char flag=0;char x;/*设数据元素的类型为char*/scanf(%d,&x);while(x!=flag)s=(Lnode*)malloc(sizeof(Lnode);s-data=x;if (L=NULL)H=s;/*第一个节点的处理*/else r-next=s;/*其他节点的处理*/r=s;/*r 指向新的尾节点*/scanf(%d,&x);if(r!=NULL)r-next=NULL;/*对于非空表，最后节点的指针域放空指针*/return L;第28页/共114页第29页/共114页3.按序号查找 Get_Linklist(L,i)算法思路：(1)从链表的第一个元素节点起，判断当前节点是否是第i个节点;(2)若是第i个节点，则返回该节点的指针，否则继续后一个，表结束为止。(3)没有第个节点时返回空。第30页/共114页Lnode *Get_LinkList(LinkList L,char i);/*在单链表L中查找第i个元素节点*/Lnode *p=L;int j=0;while(p-next!=NULL&jnext;j+;if(j=i)return p;/*若是第i个节点，则返回该节点的指针*/else return NULL;/*没有第个节点时返回空*/第31页/共114页4.单链表的插入，后插节点：设p指向单链表中某节点，s指向待插入的值为x的新节点，将节点s插入到节点p的后面，插入示意图如图2-14。操作如下：s-next=p-next;p-next=s;第32页/共114页(2)插入运算 Insert_LinkList(L,i,x)算法思路：（1）查找第i-1个节点；如果找到，继续（2），否则结束；（2）申请、填装新节点；（3）将新节点插入，结束。第33页/共114页int Insert_LinkList(LinkList L,int i,char x)/*在单链表L的第i个位置上插入值为x的元素*/Lnode *p,*s;p=Get_LinkList(L,i-1);/*查找第i-1个节点*/if(p=NULL)printf(参数i错);return 0;/*第i-1个不存在不能插入*/else s=(Lnode*)malloc(sizeof(Lnode);/*申请、填装节点S*/s-data=x;s-next=p-next;/*插入在第i-1个节点的后面*/p-next=s；return 1;/*1表示插入成功*/第34页/共114页5.删除 删除节点p 删除节点：设p指向单链表中某节点，删除节点p。操作示意图如图2-15所示。操作如下：q-next=p-next;第35页/共114页(2)删除运算：Del_LinkList(L,i)算法思路：（1）查找到第i-1个节点；如果找到，继续（2），否则结束；（2）若存在第i个节点则继续（3），否则结束；（3）删除第i个节点，结束。第36页/共114页int Del_LinkList(LinkList L，int i)/*删除单链表L上的第i个数据节点*/LinkList p,s;p=Get_LinkList(L,i-1);/*查找第i-1个节点*/if(p=NULL)printf(第i-1个节点不存在);return 0;else if(p-next=NULL)printf(第i个节点不存在);return 0;else s=p-next;/*s指向第i个（P的后继）节点*/p-next=s-next;/*从链表中删除S节点*/free(s);/*释放*s*/return 1;/*删除成功*/第37页/共114页6.上机实验单链表上插入、删除，源程序名“2_2.c”第38页/共114页循环链表是最后一个节点的指针不为空，而指向第一个节点的链表，使得链表头尾节点相连，就构成了单循环链表。如图2-16所示。图2-16 带头节点的单循环链表(a)非空表a1Han(b)空表H第39页/共114页2.3栈和队列栈和队列2.3.1栈栈(Stack)是操作受限的线性表，它限定仅在表尾进行插入或删除操作。对栈采说，允许插入、删除的这一端称为栈顶，另一个固定端称为栈底。当表中没有元素时称为空栈。向栈里放入一个新元素，称为进栈(Push)，从栈中取出一个元素，称为出栈(Pop)。第40页/共114页 进栈顺序是a1、a2、a3，出栈时顺序a3、a2、a1，所以栈又称为后进先出的线性表（Last In First Out），简称 LIFO表。在日常生活中栈的例子，如子弹夹，火车调度进站出站等。第41页/共114页第42页/共114页栈的初始化：建立一个空栈，即说明一个数组和指针初值。int smax；top-1；进栈：在栈顶插入一个元素，即将栈顶指针加1，同时元素值x送人栈顶。int Push(int s,int x)if(top=max-1)return 0;/*栈满，不能入栈*/else top+;s top=x;return 1;/*元素进入，返回*/第43页/共114页出栈：在栈顶删除一个元素，同时栈顶指针减1。int Pop(int s,int*x)if (top=-1)return 0;/*栈空，不能出栈*/else *x=s top;s-top-;return 1;/*栈顶元素存入*x，返回*/第44页/共114页【实例2-2】栈的简单应用，数制转换问题：将十进制数N转换为r进制的数，其转换方法利用辗转相除法：以N=3456，r=8为例转换方法如下：N N/8（整除）N%8（求余）123 15 3 低 15 1 7 1 0 1 高 以：（123）10 =（173）8当当N0时重复（时重复（1），（），（2）若若 N0，则将，则将N%r 压入栈压入栈s中中，执行，执行2;若若N=0，将栈，将栈s的内容依次出栈，算法结束。的内容依次出栈，算法结束。用用N/r 代替代替 N第45页/共114页#define L 8 void conversion(int N，int r)int sL,top;/*定义一个顺序栈*/int x;top=-1;/*初始化栈*/while(N)s+top=N%r;/*余数入栈*/N=N/r;/*商作为被除数继续*/while(top!=-1)x=stop-;printf(“%d”,x);printf(n);第46页/共114页2.3.2队列队列栈是一种后进先出的数据结构，“先进先出”FIFO(First In First Out)的数据结构：即插入在表一端进行，而删除在表的另一端进行，我们将这种数据结构称为队或队列。把允许插入的一端叫队尾(rear)，把允许删除的一端叫队头(front)。第47页/共114页排队买东西，排头的买完后走掉，新来的排在队尾。在队列上进行的基本操作有：（1）初始化队列:initQueue(Q)（2）取队首元素之值：将队列Q的队头元素置于变量x中，队列不变。（3）入队：在队列Q的队尾插入一个元素x（4）出队：删除队列Q的队头元素。第48页/共114页1顺序存储的队列 采用顺序存储结构的队列称为顺序队列。假设用一维数组qm来存储队列中的数据元素，队列所允许的最大容量为m。由于插入和删除的原故，队头和队尾的位置会经常变动，所以要设置两个指针front和rear，并约定rear指向队尾元素所在的位置，front指向队头元素的前一个位置。qrear 指向队尾元素，qfront+1表示队头元素。当frontrear时，就表示空队列。第49页/共114页在图在图2-21中，中，(a)为空队列；为空队列；(b)为元素为元素a1，a2，a3相继进入队列后的情相继进入队列后的情况；况；(c)为元素为元素a1，a2，a3相继退出队，相继退出队，a6，a7，a8入队列；入队列；第50页/共114页因为rear+l已超出了最大容量MaxSize。但我们注意到队列中还有空间可利用，这种现象称为假溢出。解决假溢出时，可以将队列看成是头尾相连的环，称之为循环队列。第51页/共114页循环队列人队操作可描述如下：rear(rear+1)m；qrearx；循环队列出队操作可描述如下：front(frontd-1)m；xqfront；v在在循环队列循环队列如何如何判定判定队队满满和队和队空空。v因为此时无论队满或队空，都有因为此时无论队满或队空，都有frontfrontrearrear。v解决方案是少用一个元素空间，这样可用解决方案是少用一个元素空间，这样可用(rear+1)(rear+1)m mfrontfront作为队满的判别条件。作为队满的判别条件。第52页/共114页(1)入队In_SeQueue(int q,int x)if(rear+1)mfront)printf(队满);return 1;/*队满不能入队*/else rear=(rear+1)%MAX;q rear=x;num+;return 1;/*入队完成*/第53页/共114页（2）出队Out_SeQueue(int q)int x;if (front=rear)printf(队空)；return 1;/*队空不能出队*/else front=(front+1)%m;x=front;/*读出队头元素*/num-;return 1;/*出队完成*/第54页/共114页2链接存储的队列采用链接存储结构的队列称为链队列。一个链队列需要分别指向队头和队尾的两个指针才能惟一确定。第55页/共114页2.4串和数组串和数组2.4.1串1串的定义串(String)是由零个或多个字符组成的有限序列。一般记为：s=a1 a2 an(n0)其中，s是串的名字，在本书中，用双引号作为串的定界符，引号引起来的字符序列为串值，引号本身不属于串的内容；第56页/共114页.常用术语子串与主串：串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。子串的位置：子串的第一个字符在主串中的序号称为子串的位置。串相等：称两个串是相等的，是指两个串的长度相等且对应字符都相等。第57页/共114页2.4.2 数组数组1.数组数组可以看作线性表的推广。数组作为一种数据结构其特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型，比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推。第58页/共114页设有mn二维数组Amn，按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij 的物理地址可用一线性寻址函数计算：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l第59页/共114页2.稀疏矩阵设m*n矩阵中有t个非零元素且t0)个节点的有限集合T。在任意一棵树中：有且仅有一个称为根(Root)的节点；它只有直接后继，但没有直接前驱；除根节点之外，其余节点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树。并且称之为根的子树。每棵子树的根节点有且仅有一个直接前驱，但可以有0个或多个直接后继。第62页/共114页第63页/共114页2.5.2二叉树二叉树二叉树（Binary Tree）是个有限元素的集合，该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。1.二叉树的主要性质性质1 非空二叉树的第i层上最多有2i-1个节点 （i1）性质2 一棵深度为k的二叉树中，最多具有2k1 个节点第64页/共114页性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0n21。性质4 具有n个节点的完全二叉树的深度k为log2n+1。第65页/共114页性质5 对于具有n个节点的完全二叉树，如果按照从上至下和从左到右的顺序对二叉树中的所有节点从1开始顺序编号，则对于任意的序号为i的节点，有：（1）如果i1，则序号为i的节点是根节点，无双亲节点。（2）如果2in，则序号为i的节点无左孩子,否则其左孩是节点2i。（3）如果2i1n，则序号为i的节点无右孩子,否则其右孩是节点2i+1。第66页/共114页2.满二叉树和完全二叉树2i左孩子右孩子I，二叉树编号2i+1一棵深度为k且有2k-1个节点的二又树称为满二叉树。特点特点是在一棵二叉树中，是在一棵二叉树中，如果所有分支节点都存在如果所有分支节点都存在左子树左子树和和右子树右子树，并且所，并且所有有叶子节点叶子节点都在都在同一层同一层上，上，这样的一棵二叉树称作这样的一棵二叉树称作满满二叉树二叉树。第67页/共114页一棵深度为k的有n个节点的二叉树，对树中的节点按从上至下、从左到右的顺序进行编号，如果编号为i（1in）的节点与满二叉树中编号为i的节点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左部。如图2-28所示，（a）图就是一棵满二叉树，（b）图则不是满二叉树，因为其叶子未在同一层上，故不是满二叉树。第68页/共114页第69页/共114页3顺序存储结构顺序存储结构所谓二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的节点。一般是按照二叉树节点从上至下、从左到右的顺序存储。因此，依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中节点的序号可以唯一地反映出节点之间的逻辑关系 第70页/共114页第71页/共114页4链式存储结构二叉树的链式存储结构，用链表来表示一棵二叉树，通常用二叉链表存储形式。链表中每个节点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该节点左孩子和右孩子所在的链节点的存储地址。节点的存储的结构为：第72页/共114页第73页/共114页5.二叉树的遍历二叉树的遍历是指按照某种顺序访问二叉树中的每个节点，使每个节点被访问一次且仅被访问一次。通过一次完整的遍历，可使二叉树中节点信息由非线性排列变为某种意义上的线性序列。也就是说，遍历操作使非线性结构线性化。第74页/共114页一棵由根节点、根节点的左子树和根节点的右子树三部分组成。依次遍历这三部分，就可以遍历整个二叉树。若以D、L、R分别表示访问根节点、遍历根节点的左子树、遍历根节点的右子树，则二叉树的遍历方式有六种：DLR、LDR、LRD、DRL、RDL和RLD。限定先左后右，则只有前三种方式:DLR（称为先序遍历）、LDR（称为中序遍历）和LRD（称为后序遍历）。第75页/共114页（1）先序遍历（DLR）先序遍历的递归过程为：若二叉树为空，遍历结束。否则，访问根节点；先序遍历根节点的左子树；先序遍历根节点的右子树。void PreOrder（BiTree bt）/*先序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件*/Visite（bt-data);/*访问节点的数据域*/PreOrder（bt-lchild);/*先序递归遍历bt的左子树*/PreOrder（bt-rchild);/*先序递归遍历bt的右子树*/第76页/共114页（2）中序遍历（LDR）中序遍历的递归过程为：若二叉树为空，遍历结束。否则:中序遍历根节点的左子树；访问根节点；中序遍历根节点的右子树。void InOrder（BiTree bt）/*中序遍历二叉树中序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件递归调用的结束条件*/InOrder（bt-lchild）;/*中序递归遍历中序递归遍历bt的左子树的左子树*/Visite（bt-data）;/*访问节点的数据域访问节点的数据域*/InOrder（bt-rchild);/*中序递归遍历中序递归遍历bt的右子树的右子树*/第77页/共114页void InOrder（BiTree bt）/*中序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件*/InOrder（bt-lchild）;/*中序递归遍历bt的左子树*/Visite（bt-data）;/*访问节点的数据域*/InOrder（bt-rchild）;/*中序递归遍历bt的右子树*/第78页/共114页（3）后序遍历后序遍历的递归过程为：若二叉树为空，遍历结束。否则，后序遍历根节点的左子树；后序遍历根节点的右子树。访问根节点；（LRD）void PostOrder（BiTree bt）/*后序遍历二叉树后序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件递归调用的结束条件*/PostOrder（bt-lchild）;/*后序递归遍历后序递归遍历bt的左子树的左子树*/PostOrder（bt-rchild）;/*后序递归遍历后序递归遍历bt的右子树的右子树*/Visite（bt-data）;/*访问节点的数据域访问节点的数据域*/第79页/共114页void PostOrder（BiTree bt）/*后序遍历二叉树bt*/if(bt=NULL)return;/*递归调用的结束条件*/PostOrder（bt-lchild）;/*后序递归遍历bt的左子树*/PostOrder（bt-rchild）;/*后序递归遍历bt的右子树*/Visite（bt-data）;/*访问节点的数据域*/第80页/共114页2.5.3树的存储结构树的存储结构1.双亲表示法用一组连续空间，在存储节点信息的同时为每个节点附设一个指向其双亲的指针parent，如图2-32（a）所示的树，其双亲表示法如图2-32（b）所示。2.孩子兄弟表示法孩子兄弟表示法又叉链表表示法。在这种表示法中，节点的结构为：data存放节点的有关信息，firstchild指向该节点的第一个孩子，nextbrother指向下一个兄弟节点。图2-33就是树的孩子兄弟表示法。第81页/共114页第82页/共114页第83页/共114页2.5.4森林与二叉树的转换森林与二叉树的转换由于二叉树和树都可以用二叉链表作为存储结构，因此以二叉链表作为媒介可导出树与叉树之间的一一对应关系，任何树都可唯一地对应到一棵二叉树，所以树的问题可归结为二叉树问题来研究。第84页/共114页第85页/共114页第86页/共114页2.6 图图图状结构是一种非线性结构。在图状结构中，任意两个节点之间都可能相关，即节点之间的邻接关系可以是任意的。2.6.1 图的定义和基本概念图是由非空的顶点集合和一个描述顶点之间关系边（或者弧）的集合组成，其形式化定义为：G（V，E）。其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合，若顶点偶对是有序的，则这些有序偶对称为有向边，图G称为有向图。有向边亦称为弧。若顶点vi到顶点vj有一条弧，则记为，称vi是弧尾，vj是弧头。第87页/共114页若顶点偶对是无序的，则这些无序偶对称为无向边，简称边，图G称为无向图。若顶点vi到顶点vj有一条边，则该边也是顶点vj到顶点vi的边，记为(vi，vj)或(vj，vi)。对无向图G(V，E)，如果(vi，vj)是E中的一条边，则称顶点vi和顶点vj互为邻接点，即顶点vi和vj相关联。与顶点v相关联的边的数目称为顶点v的度。第88页/共114页图2-37 有向图和无向图在有向图中以顶点V为头的弧的数目称为V的入度，以顶点V为尾的弧的数目称为V的出度。如图2-37有向图和无向图。对于无向图，边的取值范围是0到n(n-1)/2,有n(n-1)/2条边的无向图称为完全图。对于有向图，边有取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。第89页/共114页第90页/共114页2.6.2 图的存储结构图的存储结构1.邻接矩阵邻接矩阵是用一维数组存储图中顶点的信息，用矩阵表示图中各顶点之间的邻接关系。假设图G（V，E）有n个确定的顶点，即Vv0,v1,vn-1,则表示G中各顶点相邻关系为一个nn的矩阵，图2-37中G1（a）和G2(b)的邻接矩阵表示法，矩阵的元素为：第91页/共114页 借助于邻接矩阵，可以很方便地求得顶点的度。在无向图中，每个顶点的度就等于邻接矩阵中与该顶点相应的行或列中非零元素的个数；在有向图中，每行的非零元素个数等于相应顶点的出度，每列的非零元素个数等于相应顶点的入度。第92页/共114页 2邻接表邻接表是图的一种顺序存储与链式存储结合的存储方法。就是对于图G中的每个顶点Vi，将所有邻接于Vi的顶点Vj链成一个单链表，这个单链表就称为顶点Vi的邻接表，再将所有点的邻接表表头放到数组中，就构成了图的邻接表。第93页/共114页一种是顶点表的节点结构，它由顶点域（vertex）和指向第一条邻接边的指针域（firstedge）构成，另一种是边表（即邻接表）节点，它由邻接点域(adjvex)和指向下一条邻接边的指针域(next)构成。第94页/共114页2.6.3深度优先搜索遍历深度优先搜索遍历图的遍历是指从图中的任一顶点出发，对图中的所有顶点访问一次且只访问一次。图的遍历通常有深度优先搜索和广度优先搜索两种方式。1.深度优先搜索遍历深度优先搜索遍历类似于树的先根遍历，是树的先根遍历的推广。从图中某个顶点发V出发，访问此顶点，然后依次从V的未被访问的邻接点出发深度优先遍历图，直至图中所有和V有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。第95页/共114页得到的顶点访问序列为：v1 v2 v4v8 v5 v3v6v7第96页/共114页2广度优先搜索谝历广度优先搜索遍历类似于树的按层次遍历的过程。假设从图中某顶点V出发，在访问了V之后依次访问V的各个未曾访问过和邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。得到的顶点访问序列为：v1v2 v3 v4 v5 v6 v7 v8第97页/共114页2.7查找查找查找就是数据结构中找出满足某种条件的数据元素。即按给定的某个值x，在查找表中查找关键字为给定值x的数据元素（记录）。若在数据结构中找到了这样的元素，则称查找成功。否则称查找失败。关键字是数据元素（记录）中某个项或组合项的值，用它可以标识一个数据元素（记录）。能唯一确定一个数据元素（记录）的关键码，称为主关键码；而不能唯一确定一个数据元素（记录）的关键码，称为次关键码。第98页/共114页2.7.1 线性表查找线性表查找1.顺序查找法其查找过程从表的第一个元素开始，将给定的值与表中各元素的关键字逐个进行比较，若某个记录的关键字和给定值比较相等，则查找成功；反之，查找不成功。第99页/共114页int Seqsr_char(int a，int n，int k)/顺序表查找 int i；i=0；while(ai!=k&in);i+;if(in)return(i);else return(-1)；第100页/共114页2.折半查找法有序表即是表中数据元素按关键码升序或降序排列。对以顺序方式存放的有序表的查找可采用对半查找方法。折半查找的思想为：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键码相等，则查找成功；若给定值小于中间元素的关键码，则在中间元素的左半区继续查找；若给定值大于中间元素的关键码，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。第101页/共114页图2-42 折半查找过程示意图第102页/共114页图2-42 折半查找过程示意图Binary_Search(int a,int n,int x)int mid，low=1；int high=n；/*设置初始区间*/While(low=high)/*表空测试*/mid=(low+high)/2；/*得到中点*/if(amid=k)return(mid)/*查找成功*/if(xamid)high=mid-1；/*调整到左半区*/else low=mid+1；/*调整到右半区*/return(-1)；第103页/共114页2.8排序排序排序又称分类，是数据结构中另一种十分重要的运算。其功能是对一个数据元素集合或序列重新排列成一个按数据元素某个项值有序的序列。作为排序依据的数据项称为“排序码”，也即数据元素的关键码。若对任意的数据元素序列，使用某个排序方法，对它按关键码进行排序：若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；而不能保持一致的排序方法则称为不稳定的。排序分为两类：内排序和外排序。第104页/共114页内排序：指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列。外排序：指排序过程中还需访问外存储器，足够大的元素序列，因不能完全放入内存，只能使用外排序。比如：一组数排序前是a1,a2,a3,a4,a5，其中a2=a4，经过某种排序后为a1,a2,a4,a3,a5，则我们说这种排序是稳定的，因为a2排序前在a4的前面，排序后它还是在a4的前面。假如变成a1,a4,a2,a3,a5就不是稳定的了。第105页/共114页2.8.1 直接插入排序直接插入排序第106页/共114页Insert_sort(int a,int n)int i,j,k;int temp;for(i=1;i=0&tempaj)aj+1=aj;/将关键字大于ai.key的记录后移j-;aj+1=temp;/在j+1处插入ai 第107页/共114页2.8.2交换排序交换排序交换排序主要是通过两两比较待排记录的关键码，若发生与排序要求相逆，则交换之。1.冒泡排序冒泡排序的基本思想是：通过对待排序关键字的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。第108页/共114页整个算法是从最下面的记录开始,对每两个相邻的关键字进行比较,且使关键字较小的记录换至关键字较大的记录之上,使得经过一趟冒泡排序后,关键字最小的记录到达最上端,接着,再在剩下的记录中找关键字次小的记录,并把它换在第二个位置上。依次类推,直到在某趟排序过程中没有进行过交换记录的操作为止。待排序的关键字为49，38，65，97，13，27，49，存放在分别存放在a0a7中，第109页/共114页第110页/共114页Bubble_Sort(int a,int n)int i