数据结构：面向对象语言描述Bppt.ppt

1、1,版权所有, 1997 (c) Dale Carnegie n0; ei AtomSet或ei GList 结构关系： R1= | ei-1 , ei D, 2in 基本操作： 对广义表可执行以下的基本操作。 InitGList(L) 初始化。创建一个空的广义表L。 CopyGList(L,L0) 复制。由广义表L0复制得到一个广义表L。 GListDepth(L) 求深度。求广义表L的深度。 GListLength(L) 求长度。求广义表L的长度，即元素个数。 GlistEmpty(L) 判空表。判广义表L是否为空。 GetHead(L) 取头。取广义表L的头。 GetTail(L) 取尾

2、。取广义表L的尾。 InsertFirst(L,e) 插入元素。插入元素e作为广义表L的第一元素。,9,广义表与其他数据结构的关系,1 与线性表的关系 当限定广义表的每一项只能是基本元素而非子表时，广义表就退化为线性表：(a1,a2,an)； 2 与二维数组的关系 当将数组的每行（或每列）看作为子表时，数组即为一个广义表： (a11,a12,a1n),(a21,a22,a2n),(an1,an2,ann) 3 与树的关系 树也可以用广义表来表示，例如图7.1所表示的树可以用如下的广义表来表示： (a,(b,c,d),e,(f,g) 4. 在LISP语言中，使用函数嵌套的形式来构造程序。例如：（

3、 op（op A B）（op C D） 在这种情形下，程序本身就是一个广义表。,10,存储方式：头尾表示法,二类节点 表节点 元素节点 typedef char Tatom ; struct GListNode int tag; union Tatom data; GListNode *hp; ; GListNode *tp; ;,11,存储方式：头尾表示法,C=(a,(b,c,d) (b,c,d),(b,c,d),(c,d),(d),12,存储方式：儿子兄弟表示法,二类节点 有儿子 无儿子 类型定义与头尾表示法的类型定义是一致的，只不过各字域所代表的含义有所不同。,13,存储方式：儿子兄弟表

4、示法,C=(a,(b,c,d) 最高层结点的tp域必为nil,(b,c,d),14,互动环节： G=(a,b),(c,d)的存储结构 使用头尾表示法画出G=(a,b),(c,d)的存储结构,15,互动环节： G=(a,b),(c,d)的存储结构,C=(a,b),(c,d) (c,d),(c,d),(d),(a,b),(b),16,广义表的类定义,class GList GListNode *ls; public: GList(GListNode *ls0=NULL) copyls0(ls,ls0); GList(String,17,取头、取尾操作,取头操作成员函数 GListNode* hea

5、d() 功能:返回指向当前广义表头的指针，程序代码如下： GListNode* GList:head() if (ls-tag=1) return ls-hp; else return NULL; ; 取尾操作成员函数 GListNode* tail() 功能:返回指向当前广义表尾的指针，程序代码如下： GListNode* GList:tail() if (ls-tag=1) return ls-tp; else return NULL; ;,18,插入、删除操作,void insertFirst(GList,19,广义表递归算法,递归定义递归算法递归函数 递归函数：直接或间接地调用自己 递

6、归算法特点 结构清晰、程序简练易读、其正确性也容易证明， 但递归过程的执行效率较低 递归定义由基本项和归纳项两部分组成。 基本项描述递归过程的终结状态，终结状态是指不需要继续递归而可直接求解的状态。 归纳项描述了如何实现从当前状态到终结状态的转化。,20,广义表的相等比较,bool equal(GListNode* ls1,GListNode* ls2) 功能：对广义表ls1与ls2进行比较。若相等则返回函数值true，否则返回函数值false。 分析: (1)若两者都为NIL，则返回true (2)若一方NIL而另一方不为NIL或两者tag不相等则返回false。 (3)若tag相等且为0，

7、则可比较结点中的data; (4)若tag相等且为1，则可比较表头与表尾是否都相同，并返回一个相应的函数值。 处理过程： (1)对一些特殊情形作处理：若两者都为NULL，则返回true,若一方NULL而另一方不为NULL或两者tag不相等则返回false。 (2) 若tag相等且为0，则比较结点中的data是否相同并返回值; 若tag相等且为1，则通过递归调用比较表头与表尾是否都相同，并返回一个相应的函数值。,21,相等比较 程序代码,bool GList:equal(GListNode* ls1,GListNode* ls2) bool b1,b2; if (ls1=NULL ,22,相等比

8、较 实例函数,上述equal函数是静态成员函数，它不涉及当前对象，而equal函数的另一种形式是实例函数，涉及到当前对象，其形式如下： bool equal(GList ,23,成员判别,bool member(GListNode* ls1,GListNode* ls2) 功能：判别ls2是否为ls1的成员，若是则返回函数值true，否则返回函数值false。 其处理过程为： (1)若ls1为NULL或但元素则返回false,否则： (2)调用equal判别ls1的第一个成员是否与ls2相等，调用本递归函数判别ls1的其它成员中是否含有与ls2相等的成员，并将这两者的结果逻辑加后作为最后返回的

9、函数值。 bool GList:member(GListNode* ls1,GListNode* ls2) bool b1,b2; if ( ls1=NULL | ls1-tag=0 ) return(false); else b1=equal(ls1-hp, ls2); b2=member(ls1-tp, ls2); return(b1 | b2); ,24,成员判别实例函数,上述member函数是静态成员函数，它不涉及当前对象，而member函数的另一种形式是实例函数，涉及到当前对象，其形式如下： bool member(GList ,25,求广义表的深度,定义： 对于广义表 ls=(a1

10、,a2, ai ,an) 当ls为单元素时，depth(ls)=0； 当ls为空表时， depth(ls)=1； 否则， depth(ls)= max(1=i=n) depth(ai) + 1； 可以作简单的理解： 广义表的深度定义为广义表中括号的层数 例如： depth()=1; depth(a)=0; depth(a,(b,c,d)=2; depth( (x,(x,(x,x),(x,x) ) = 3;,26,求广义表的深度,int depth( GListNode *ls ) 其中参数ls表示指定的广义表的结点指针，该函数的功能为：求由结点指针ls 所指向的广义表的深度，并作为函数值返回之

11、。 对于广义表ls，若为单元素时其深度为0，若为空表时其深度为1，否则可分别求出其头的深度h及尾的深度t，当h小于t时其深度为t，否则其深度为h+1，按这种分析可知其处理过程为： (1) 若ls指向单元素或空表则分别返回函数值为0或1,否则： (2) 调用本递归函数分别求出其头的深度存入h及尾的深度存入t； (3) 若ht则返回t，否则返回h+1。,27,求广义表的深度,int GList:depth(GListNode *ls) int h,t; if (ls=NULL ) return(1); else if (ls-tag=0 ) return(0); else h=depth(ls-h

12、p); t=depth(ls-tp); if (ht ) return(t); else return(h+1); 实例函数 int GList:depth() return(depth(ls); ,28,广义表递归算法互动环节：广义表复制,设计一个拷贝构造函数，其功能为按一个指定的广义表来创建一个新的广义表。 void copyls(GListNode* 并输出该广义表的第一个成员。 (2) 输出一个，与广义表的下一个成员。 (3)重复过程(2)的处理，直至所有的成员都处理完，最后再输出一个)。,32,打印广义表程序代码,void GList:prnt(GListNode *ls) GLis

13、tNode *p; if (ls = NULL ) couttag=1) couthp); p=ls-tp; while (p!=NULL) couthp); p=p-tp; ; coutdata; ; 实例函数 void GList:prnt() prnt(ls); coutendl; ;,33,广义表类功能测试,编写一个测试程序测试广义表类Glist的构造函数、拷贝构造函数、插入第一元素、删除第一元素、求深度等项功能。 void main( ) String st1=(a,(b,c),st2=(x,y,(z); GList gyb1(st1); gyb1.prnt(); GList gyb

14、2(st2); gyb2.prnt(); GList gyb3(gyb1); gyb3.prnt(); gyb2.insertFirst(gyb1);gyb2.prnt(); gyb2.deleteFirst(); gyb2.prnt(); coutdep=gyb2.depth()endl; 程序的运行结果如下： (a,(b,c) (x,y,(z) (a,(b,c) (a,(b,c)，x,y,(z) (x,y,(z) dep=3,34,后记,结束,35,版权所有, 1997 (c) Dale Carnegie BTreeNode *lchild, *rchild; ； 三叉链表： struct

15、 BTreeNode T data; BTreeNode *parent, *lchild, *rchild; ；,A,B,C,D,E,51,二叉树结点类的定义,template class BTree; template class BSTree; template class BTreeNode friend class BTree ; friend class BSTree ; T data; BTreeNode *lchild,*rchild; public: BTreeNode():lchild(NULL),rchild(NULL); BTreeNode(T d, BTreeNode

16、 *l=NULL, BTreeNode *r=NULL) :data(d),lchild(l),rchild(r); T getdata()return data; BTreeNode *getleft()return lchild; BTreeNode *getright()return rchild; ;,52,二叉树类的定义,template class BTree T *a; int n; BTreeNode *build0(int i); protected: BTreeNode *root; public: BTree(BTreeNode *p=NULL) copybt(root,

17、p); BTree(T a,int n); int num(); static int num(BTreeNode *p); int dep(); static int dep(BTreeNode *p); bool equal(BTree,53,建立二叉链表,D,H,I,A,B,C,F,G,54,建立二叉链表 构造函数,template BTree: BTree(T a,int n) this-a=a; this-n=n; root=build0(1); BTreeNode * build0(int i) 功能为：以数组a中的第i个元素（下标为i-1）为根结点，递归地创建二叉链表，并返回指向

18、该链表的指针。其处理过程为： (1)若序号为i的数组元素存在，即i小于等于数组的长度且数组的第i个元素非空，则创建一个结点作为根结点，在其数据域中存放数组的第i个元素。 (2)以2*i为参数，调用build0创建左子树，并挂在该结点的左支上。 (3)以2*i+1为参数，调用build0创建右子树，并挂在该结点的右支上。,55,建立二叉链表 递归函数的程序代码,template BTreeNode * BTree:build0(int i) BTreeNode *p; int l,r; if (i ; p-data=ai-1; l=2*i; r=2*i+1; p-lchild=build0(l)

19、; p-rchild=build0(r); return(p); else return(NULL); ,56,计算二叉树结点个数,int num(BTreeNode *p) 其功能为返回p所指向的二叉树的结点个数，其处理过程为： (1)若p为NULL则返回0；否则 (2)通过递归调用求出左、右子树的结点个数，并返回两者之和加1 template int BTree:num(BTreeNode *p) if(p=NULL)return(0); else return(num(p-lchild)+num(p-rchild)+1); 实例函数，求当前对象中的结点个数： template int B

20、Tree:num() return(num(root); ,57,互动环节:计算二叉树的高度,int dep(BTreeNode *p) 功能:返回p所指向的二叉树的高度，其处理过程为： (1)若p为NULL则返回0，否则； (2)求出左、右子树的高度l1、l2并返回max(l1+ l2)+1。,58,互动环节:计算二叉树的高度,template int BTree:dep(BTreeNode *p) int max; if(p=NULL)return(0); else max=dep(p-lchild); if (dep(p-rchild)max) max=dep(p-rchild); re

21、turn(max+1); 实例函数求当前对象中的高度： template int BTree:dep() return(dep(root); ,59,树(二)判断两个二叉树相等,bool equal(BTreeNode *p, BTreeNode *q) 其功能为判断p、q所指向的两棵二叉树是否相等，若相等则返回true否则返回false，其处理过程为： (1) 若p、q均为空，则返回true；否则， (2) 若p、q中有一个为空，则返回false；否则（处理p、q均非空的情形）， (3) 若结点数据和左右子树均相等，则返回true否则返回false。 template bool BTree:

22、equal(BTreeNode *p,BTreeNode *q) bool b; if(p=NULL ,60,判断两个二叉树相等,equal函数的另一种形式是实例函数： bool equal(BTree ,61,复制二叉树：拷贝函数,void copybt(BTree ,62,复制二叉树：递归函数,void copybt(BTreeNode * 要注意的是参数p是结点指针类型，其值会有所改变，因此必修加上引用符号 cout void BTree:inorder(BTreeNode *p, void visit(BTreeNode *p) if (p!=NULL ) inorder(p-lchi

23、ld,visit); visit(p); inorder(p-rchild,visit); 先序、后序遍历的递归函数也与之类似,67,中序遍历递归函数的执行过程,执行过程：,In(-),In(C),显示(-),In(*),显示(a),显示(*),显示(b),显示(C),In(b),In(a),-,*,C,a,b,68,表达式的逆波兰表示,（a+b）*（c-d） 先序遍历 先序序列 中序遍历 中序序列 后序遍历 后序序列（逆波兰表示）ab+cd-*,*,+,-,a,b,c,d,69,中序遍历的非递归函数,void inorder1(void visit(BTreeNode *p) 其功能为对当前

24、二叉树进行非递归的中序遍历，执行visit函数的操作，其处理过程为： (1)栈初始化，根结点进栈。 (2)若栈非空，则栈顶结点的左儿子相继进栈，直至NULL退栈；访问栈顶结点（执行visit函数的操作）并使栈顶结点的右儿子成为栈顶结点。 (3)重复执行步骤(2)直至栈为空。,70,中序遍历的非递归函数,template void BTree:inorder1(void visit(BTreeNode *p) BTreeNode *stack10,*p; int top; s=; top=0;stacktop=root; while(top=0) while(stacktop!=NULL) p=

25、 stacktop-lchild; stack+top=p; top-; if (top=0) p=stacktop; visit(p); stacktop=p-rchild ; coutendl; ,71,互动环节：二叉树显示,为二叉树类增设一个打印二叉树的成员函数，按二叉树的凹入表示法打印二叉树，其输出的形式相当于把二叉树逆时针旋转90度。 设计思想：该算法的设计思想与中序遍历二叉树相类似。由于把二叉树逆时针旋转90度后显示在上方的右子树，然后是根节点，最后是左子树，所以该算法是一种特殊的中序遍历算法。为了使不同层次中的结点显示在不同的位置上，在递归函数中设置一个表示递归调用深度的参数。递

26、归打印函数的程序代码如下：,72,互动环节：二叉树显示,template void BTree:prnt(BTreeNode *p, int l) if (p!=NULL ) prnt(p-rchild,l+1); for (int i=0;idatalchild,l+1); void prnt()prnt(root,1);,73,互动环节：重置函数及其测试,template void BTree:setroot(BTreeNode *p) dest(root); copybt(root,p); void main( ) char *str2=abcd f; BTreebt2(str2,6);

27、 bt2.prnt(); BTreeNode *p1=new BTreeNode(x,NULL,NULL); BTreeNode *p2=new BTreeNode(y,NULL,NULL); BTreeNode *p3=new BTreeNode(z,p1,p2); bt2.setroot(p3); bt2.prnt(); c f a b d y z x,74,排序二叉树的定义,排序二叉树或为空树或为满足具有以下特点的二叉树： （1）所有结点的（数据）值均不相同； （2）若左子树为非空，则左子树中所有结点的值均小于根结点的值； （3）若右子树为非空，则右子树中所有结点的值均大于根结点的值；

28、（4）左子树和右子树均是排序二叉树。,75,排序二叉树的动态生成过程,32,16,43,14,25,57,18,52,61,32,57,43,18,61,52,16,25,14,P=nil,32,16,32,43,16,25,14,32,76,排序二叉树类的定义,template class BSTree : public BTree public: BSTree(BTreeNode *p=NULL)root=p; T minv(); T maxv(); BTreeNode *sear(T el); /查找实例函数 BTreeNode *sear1(T el); /非递归查找函数 static

29、 BTreeNode *sear(T el, BTreeNode *bst);/递归查找函数 void inst(T el); /插入实例函数 void inst1(T el); /非递归插入函数 static void inst(BTreeNode *p, BTreeNode *,77,求排序二叉树的最值,T minv() 其功能为返回当前排序二叉树中结点关键码的最小值。其处理过程为： 使p=root，若p为空，则显示相应的信息，否则 (1)若p所指结点有左儿子，则令p指向该结点； (2)重复(1)，直至p所指结点的左儿子链为空； (3)返回p所指结点的关键码。 程序代码为： templat

30、e T BSTree:minv() BTreeNode *p=root; if (p=NULL) coutlchild!=NULL) p=p-lchild; return p-data; ,78,树与森林,森林 森林是m(m0)棵互不相交的树的集合。 树 当节点个数 n0 时由根节点与M棵子树构成的森林所构成。,7,3,6,2,5,4,1,79,树的存储结构：儿子双亲表示法,把树中每个结点的儿子节点排列起来，用单链表来存储；而每个单链表的头指针又组成一个线性表，同时在线性表的元素中又增加父节点的序号，构成儿子双亲表示法,7,3,6,2,5,4,1,80,树的存储结构：儿子兄弟表示法,依据：从最

31、先的祖先开始，只要能确定家属中每个人的儿子与兄弟，即可找到家属中的每个人。,e,d,a,c,b,81,树、森林转换成二叉树,树转换成二叉树 转换方法：用儿子兄弟表示法表示一棵树，并将儿子链看作为左子树，将兄弟链看作为右子树。,e,d,a,c,b,e,d,a,c,b,82,树、森林转换成二叉树,森林转换成二叉树，转换方法： 将第一棵树转换成二叉树， 将第二棵树转换成二叉树，并掛在第一棵二叉树的右子树上， 将第三棵树转换成二叉树，并掛在第二棵二叉树的右子树上 （互动环节 ）,e,d,a,c,b,e,d,a,c,b,f,g,f,g,83,树的应用：哈 夫 曼 树,哈夫曼树的定义 节点的路径长度：从树

32、中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度 树的路径长度：从树根到每一结点的路径长度之和 树的带权路径长度：被定义为从各叶结点到树根之间的路径长度与结点上权的乘积和。,84,树的应用：哈 夫 曼 树,(a)WPL = 9262523246 (b)WPL = 6132935354 (c)WPL = 9162533345,b,5,3,c,6,d,a,9,a,6,5,b,9,c,d,3,a,5,6,c,9,b,d,3,85,哈夫曼树的定义,具有n个带权叶节点的二叉树中WPL最小的二叉树称为哈夫曼树 意义：用于编码设计 编码长度路径长度 使用频率权值 报文总

33、长WPL 报文总长最短WPL最小,86,各类编码,87,哈夫曼树的构造,设给定叶结点的个数n及权值集合 w1 , w2 , wn 为使二叉树的带权路径长度达到最小，权值越大的叶结点应越靠近根结点，而权值越小的叶结点则离根结点越远。构造方法如下： (互动环节),a,6,5,b,9,c,d,3,a,5,6,c,9,b,d,3,a,6,b,9,c,d,a,9,5,6,c,b,d,3,88,哈夫曼树的建树过程,89,哈夫曼树的建树过程,2,6,5,3,3,6,2,2,1,7,4,1,8,4,12,10,8,9,11,13,90,哈夫曼编码的确定,由已形成的哈夫曼树求哈夫曼编码。对每个叶结点都进行如下的

34、处理： 扫描由叶结点到根结点的各条分支， 若分支中的当前结点与双亲结点是左支关系，则生成编码0， 若分支中的当前结点与双亲结点是右支关系，则生成编码1， 由此生成的二进制码的序列即为该结点的哈夫曼编码。,91,树的应用：哈夫曼编码生成程序,在程序中要使用到两种结构类型，一种是哈夫曼树的结点类型，另一种是哈夫曼编码的结构类型。 struct HaffNode int weight; int parent; int lchild; int rchild; ; struct HaffCode int bitmaxlen; int start; int weight; ;,92,树的应用：哈夫曼编码生

35、成程序,void Haffman(int w,int n,HaffNode ht,HaffCode hc) int i,j,m1,m2,x1,x2; /m1、m2分别表示最小、次小的权值 /x1、x2分别表示当前分支结点的左右儿子 /步骤1 构造哈夫曼树 for(i=0;i2*n-1;i+) /哈夫曼树初始化 if(in)hti.weight=wi;else hti.weight=0; hti.parent=0; hti.lchild=-1; hti.rchild=-1; ; 在构造某一个分支结点时使用了一个循环for(j=0;jn+i;j+)表示从根结点到当前已生成的分支结点中找出两个权值最

36、小的结点。当然应该在还没有确定父结点的结点中进行查找。,93,树的应用：哈夫曼编码生成程序,for(i=0;in-1;i+) /构造哈夫曼树的n-1个分支结点 m1=m2=1000; x1=x2=0; for(j=0;jn+i;j+) if( htj.weightm1 ,94,树的应用：哈夫曼编码生成程序,/步骤2 由哈夫曼树生成哈夫曼编码 HaffCode cd; int child,parent; for(i=0;in;i+) /由哈夫曼树生成哈夫曼编码 cd.start=n-1; cd.weight=hti.weight; child=i; parent=htchild.parent;

37、while (parent!=0) if( htparent.lchild=child) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; child=parent; parent=htchild.parent; ; for(j=cd.start+1;jn;j+) hci.bitj=cd.bitj; hci.start=cd.start; hci.weight=cd.weight; ;,95,哈夫曼编码生成程序：执行实例,设有字符集A、B、C、D、E、F、G，各字符对应的权值分别为4,2,6,8,3,2,1，设计各字符的哈夫曼编码。程序代码

38、如下： void main( ) int w =4,2,6,8,3,2,1; int n=7,i,j; HaffNode *ht = new HaffNode 2*n-1; HaffCode *hc = new HaffCode n; Haffman(w,n,ht,hc); for(i=0;in;i+) coutweight= hci.weight code=; for(j=hci.start+1;jn;j+) couthci.bitj; coutendl; ; weight=4 code=101 weight=2 code=1001 weight=6 code=01 weight=8 cod

39、e=11 weight=3 code=001 weight=2 code=100 weight=1 code=1000,96,后记,结束,97,版权所有, 1997 (c) Dale Carnegie E(G1) = (1,2), (1,3), (2,3), (2,4), (2,5), (3,5), (4,5);,4,1,5,3,2,图与树的比较： 树：一对多，树中的每一个节点最多只有一个父节点。 图：多对多，顶点间的关系是任意的。,100,图有关的基本术语,图中的每一个数据元素vi 称为顶点(vertex)； 无向图中点的连线( vi , vj )称为边；vi、 vj为此边的两个端点，并称它

40、们互为邻接点(adjacent)， 而有向图中点的连线则称为弧，并称顶点vi为弧头（始点），顶点vj为弧尾（终点）；并称此边是顶点vi的一条出弧，顶点vj的一条入弧。,101,图有关的基本术语,顶点的度、入度、出度 无向图中顶点v的度(degree)定义为以该顶点为一个端点的边的数目，简单地说，就是该顶点的边的数目，记为d(v)。如图G1中顶点1的度为2，顶点2的度为4。 有向图中顶点的度有入度和出度之分：入度是该顶点的入边的数目；出度是该顶点的出边的数目，顶点v的度等于它的入度和出度之和。,102,图有关的基本术语,路径和回路 若存在顶点的序列（v1,v2,vm）, 其中（vi,vj）E（i

41、=1,2,m-1）,则称v1到vm存在一条路径，路径长度即为边或弧的数目。 特别地当v1vm时，则称次路径为回路或环,103,图有关的基本术语,子图 设有两个图G = (V, E)和G= (V, E)，若V是V的子集，且E是E的子集，则称G是G的子图。直观地看，子图就是将原来的图中的部分点和边去掉后所得到的图。,4,1,5,3,2,4,1,3,2,104,图有关的基本术语,权和网 在一个图中，每条边可以标上具有某种含义的数值，此数值称为该边的权(weight)。例如，用权值来标记距离或花费等。 边上带有权的图称作带权图，也常称作网。,4,1,3,2,2,4,1,3,2,5,3,4,3,3,3,

42、4,4,5,5,2,105,存储方式：邻接矩阵,对于有向图：若图G = (V, E)是一个有n个顶点的图，则G的邻接矩阵A是一个nn的二维数组，且,4,1,5,3,2,106,存储方式：邻接矩阵,对于无向图：邻接矩阵A是一个对称矩阵，即： Ai,j=aj,i,4,1,5,3,2,107,存储方式：邻接矩阵,对于带权图（网），我们也可以用邻接矩阵来表示：,4,1,5,3,2,3,1,7,4,2,5,2,108,存储方式：邻接链表,const int max=100; /n为图中允许的最大顶点数 struct ArcNode /弧结点类型定义 int adjvex; ArcNode *nextar

43、c; ; struct VexNode /顶点结点类型定义 int vexdata; ArcNode *firstarc; ; VexNode adjlistmax; /邻接表adjlist的定义,4,1,5,3,2,109,存储方式：邻接链表,有向图 邻接链表 对于出弧建立弧节点,4,1,5,3,2,110,存储方式：邻接链表,有向图 逆邻接链表 对于入弧建立弧节点,4,1,5,3,2,111,存储方式：邻接链表,对于无向图 每一条边生成二个边节点，分别挂在对方节点的链上,4,1,5,3,2,112,存储方式：邻接链表,对于有向网 在弧节点中增设权值域,4,1,5,3,2,3,1,7,4,2

44、,5,2,113,互动环节：画出以下有向图的(1)连接矩阵、邻接链表、逆邻接链表(2)深度及广度优先序列,4,1,5,3,2,6,114,图的遍历,概述 含义：从指定的某个顶点（称为初始点）出发，按照一定的搜索方法访问对图中的所有顶点且每个节点只访问一次 复杂性：因为存在着多条路径，可能被多次访问。因而要设置标记向量visited1.n 种类：一种是深度优先搜索遍历，另一种是广度优先搜索遍历。,115,边结点、顶点结点的类型定义,struct ArcNode int adjvex; ArcNode *nextarc; ; struct VexNode int vexdata; int ox,o

45、y; ArcNode *firstarc; ;,116,邻接链表图类Graph,class Graph private: static String str; bool *visited; VexNode *adjlist; int n; void dfs0(int v0,void visit(int,117,邻接链表图类的构造函数,构造函数Graph(VexNode adjl,int l) 功能是构造一个由adj1表示的顶点个数为l的邻接链表对象，实际上是将参数中指定的邻接链表复制到当前对象中。 构造函数Graph(int vex,int arc, int n) 功能是按参数中给出的顶点数据

46、和邻接矩阵生成邻接链表的存储结构。 其中参数vex给出各顶点中的数据元素值，arc是邻接矩阵的一维排列，n是顶点的个数。,118,深度优先遍历,从确定的某一顶点v0开始，按先纵向后横向的次序访问与v0有路径相通的所有的顶点。 直观理解： 连长 1排长 1班长2班长3班长 2排长 4班长5班长6班长 3排长 7班长8班长9班长,119,深度优先遍历 接口函数,String dfs(int v0,void visit(int ,120,深度优先遍历 递归函数,void dfs0(int v0,void visit(int VexNode *adjlist; 层次队列 int q 100 ,fron

47、t,rear; 作用：记录已被访问但其下一层尚未访问的顶点，以便实现逐层访问。 使用方法： 访问后进队列； 出队列时依次访问各邻接点，访问后进队列。,124,广度优先遍历 接口函数,String bfs(int v0,void visit(int ,125,广度优先遍历函数,void bfs0(int v0, void visit(int 若未访问过则进行处理,127,图的应用 拓扑排序,有向无环图：不存在回的有向图 这是拓扑排序的前提 AOV网：是一个有向图，其顶点表示活动、 弧表示活动间先后关系。,3,2,5,4,1,128,图的应用 拓扑排序,拓扑排序的含义：偏序全序 即将图之所有的顶点

48、排成一个线性序列，并使各顶点间的先后关系都得到满足，例如：在下图中，顶点表示课程，有向边表示课程之间的先后关系。拓扑排序要确定所有课程的安排为： 1 2 3 4 5 或 1 2 4 3 5,3,2,5,4,1,129,拓扑排序的方法,(l)在AOV网中选一个没有直接前驱（入度为0）的顶点，并访问； (2) 从图中删去该顶点，同时删去它所发出的所有弧。 (3) 重复(1)、(2)，直到图中不存在入度为0的点。,C,B,D,E,F,C,B,D,E,A,F,C,B,D,F,130,拓扑排序的实现,顶点的存储形式 在顶点节点中增加一个入度域表示入弧的个数 struct ArcNode int adjv

49、ex; ArcNode *nextarc; ; struct VexNode int vexdata; int indegree; ArcNode *firstarc; ; VexNode adjlistmax;,131,拓扑排序的实现,顶点的存储形式 顶点节点 弧节点,C,B,D,E,A,F,132,拓扑排序的实现,利用入度域将入度为0的顶点作成一个链栈 （1）顶点i入栈： adjlisti.indegree=top; top= i; （2）栈顶元素出栈： j = top; top = adjlisttop.indegree;,top,top,133,拓扑排序的实现,void tpsort0

50、() 功能：对adjlist所表示的有向图进行拓扑排序，输出相应的拓扑序列（结果在字符串变量str中）。 处理过程： (1)搜索邻接表顶点结点的入度域，将入度为0的顶点链接成栈，并用top来指示栈顶元素。 (2)从栈中弹出栈顶元素，对其所指顶点进行访问。 (3)将该顶点邻接点的入度减1，若变为0，则将对应顶点入栈。 (4)重复执行(2)、(3)，直至栈空（top为 -1）。,134,拓扑排序的实现,void Graph:tpsort0() int top,m,i,j; ArcNode *p; top= -1;/栈顶指针初始化 for (i=0; in; i+ )/搜索入度域,将入度为0的顶点联

51、接成栈 if (adjlisti.indegree = 0 ) adjlisti.indegree=top; top= i; ,135,拓扑排序的实现,m= 0; /m用来统计已经访问的顶点个数 while (top != -1 ) /处理栈顶元素，直至栈成为空栈 m=m+1; str=str+IntToStr(adjlisttop.vexdata)+ ; /访问栈顶元素所指顶点 p = adjlisttop.firstarc; /p指向该顶点的第一个邻接点 top= adjlisttop.indegree; / 修改栈顶指针 while (p != NULL ) j=p-adjvex; /取

52、邻接点序号 adjlistj.indegree-; /入度减1 if (adjlistj.indegree = 0 ) /若入度为0 adjlistj.indegree= top; top = j; ; p= p-nextarc; /p指向下一个弧结点 ; ; /如果循环结束时，还有未访问顶点 则显示出错 if (m != n ) ShowMessage(loop exists, error +IntToStr(m)+ +IntToStr(n)+ ); ;,136,拓扑排序的实现,执行实例 3 1 5 2 6 4,初态,C,B,D,E,A,F,访D后,访E后6号减1,访A后2，5减1 成0相继

53、进栈,访C后Top指向1 2，4，6减1,访B后6号 再减1成0进栈,访F后4号减1 成0进栈,137,最短路径 问题,问题说明 从一个带权的图中某一顶点到达另一顶点的最短路径（权值总和达到最小）。 v0v5 100 v0v4 v5 90 v0v4 v3 v5 60,3,5,4,0,2,1,100,10,60,30,20,10,50,138,最短路径 问题,Dijkstra算法可描述如下： (1)设置当前点集初态，列出V0到各点的距离； (2)从V0到当前点集中找出距离最短的点VJ及相应的路径，并将其余各点的已有路径与经过该路径的新路径比较，若新路径短则更新为新路径； (3)从当前点集中除去V

54、J，并重复过程2进行类似的处理，直至当前点集为空，即确定了从V0到所有各点中的最短距离。,139,最短路径 问题,执行过程 更新,3,5,4,0,2,1,100,10,60,30,20,10,50,140,最短路径 算法的实现要点,（1）设置数组distn ，每个分量disti 存放V0到Vi的当前最短路径长度，其初始值为：如果从V0到Vi有一条路径，则为权值否则为无穷大。 （2）设置集合型数组pathn ，每个分量pathi 存放与disti 对应的最短路径的点集，其初始值为：如果从V0到Vi有一条路径，则为V0,Vi否则为空集。 （3）设置集合型变量S ，存放当前已确定了最短路径的那些点的

55、点集，其初始值为 V0。显然，在确定下一个最短路径的点时，应除去S中的那些点。 （4）此外，还设置cost为带权有向图的邻接矩阵，存放权值，V为指定的起始顶点。 具体处理过程： (1)对每一个顶点i，设置disti ，pathi，及Si的初态。 (2)确定一个最短路径的顶点及相应的路径，将这个顶点划进S，并以这条路径与其它各点的已有路径作比较，若通过这条路径的路径可使达到某一点的距离减少，则更新该点的已有路径。 (3)重复执行过程(2)，直至S中包含n个顶点。,141,最短路径 变量定义,struct VexNode int ox,oy; const int numv=10; /表示最多顶点数

56、 const int max=1000; /在邻接矩阵中表示无穷大 VexNode adjlistnumv;/顶点数组，记录顶点的位置 int costnumvnumv; /网的邻接矩阵，对称矩阵 int distnumv; /disti存放从v到顶点i的最短路径 int pathnumv; /pathi存放在最短路径上从顶点i到前一点的顶点号 /该数组的作用是将各点到指定始点的路径链成一条仿真链 int snumv; /si=1表示顶点i的最短路径已经求出，si=0表示未求出 int ii,iis,iie; / ii顶点计数器,iis边的起始点号,iie边的终结点号 bool id; /画边

57、时表示点击的是起点还是终点,142,最短路径,void shotpath(const int v) int i, j, k ,wm; for(i=0;inumv;i+) /按网的邻接矩阵确定各顶点最短路径的初值 disti= costvi; if (i!=v ,143,后记,结束,top,144,top,0,1,2,3,4,5,145,版权所有, 1997 (c) Dale Carnegie ; ; Rec rn+1; 说明：为了使逻辑序号与存储下标一致，定义rn+1记录存放在r1至 rn,查找过程,无监视所,设置监视所,150,无监视所的查找函数,int srch(Rec r, int n,

58、 Key k); 其中，参数r表示查找表，其长度为n+1，参数k表示指定的关键字。 功能：若存在关键字等于k的记录，则返回该记录在顺序表中的序号，否则返回值为0。 其处理过程为：从表中第一个记录开始，逐个进行记录的关键字与给定值的比较，若某个记录的关键字与给定值的相等，则查找成功返回该记录的序号，反之，若直至最后一个记录，其关键字与给定值都不等，则查找不成功返回0。 程序代码为： int srch(Rec r, int n, Key k) int i=1; while (ri.key!=k),151,算法改进：设置监视所,为了避免在查找过程中每一步都要检验整个表是否查找完毕。可在查找之前先对r

59、0的关键字赋值k，在此r0起到了监视哨的作用。 经改进后二个控制条件只要使用一个，条件语句也可以去掉。,1,2,n,0,1,n,K,152,设置监视所查找函数,int srch1(Rec r, int n, Key k) int i=n; r0.key=k; while (ri.key!=k) i-; return(i); ;,153,静态查找表 平均查找长度,其中，Pi ,Ci分别为查找第i个记录的频率及次数， 显然，Ci依赖于所用的查找方法，在顺序查找中，Ci取决于元素在表中的位置。例如查找rn时仅需比较一次，而查找r1时需要比较n次，一般情况下，Ci=n-i+1。假设每个记录的查找概率相

60、等，即Pi=1/n，则在等概率的情况下，顺序查找的平均查找长度为： ASL(1/n) *(1+2+n)= (1/n) *(n*(n+1)/2)= (n+1)/2。,154,互动环节：顺序查找函数测试程序,Rec r=0,34,53,22,71,36,48,15,82; int srch(Rec r, int n, Key k); int srch1(Rec r, int n, Key k) ; 在主函数中调用查找函数进行查找，程序代码如下： void main( ) int i=srch(r,8,22); int j=srch1(r,8,48); couti=i j=jendl; if(src