《软件技术基础课件》由会员分享，可在线阅读，更多相关《软件技术基础课件（112页珍藏版）》请在金锄头文库上搜索。
1、非线性结构1非线性结构n非线性结构：至少存在一个数据元素有两 个或两个以上的直接前驱（或直接后继）元 素的数据结构。n非线性结构主要有 u树(TREE)结构 u图(GRAPH)结构2树3树型结构n树形结构例：用于描述层次结构的关系，如：人 类的族谱、各种社会关系、各类分类编码；操作系 统的文件系统、编译程序的语法树；Internet中 的DNS（域名系统）n分等级的分类方案均可用层次结构来表示，即可 由此导出树形结构。4树的定义n树(Tree)是n(n0)个结点的有限集合T， 对于任意一棵非空树，它满足： u当n0时，称为空树； u当n0时，有且仅有一个特定的称为根(root) 的结点。 u当
2、n1时，其余结点可分为m(m0)个互不 相交的有限集T1，T2，.，Tm，其中每个集合 本身又是一棵树，称为根的子树。n树的定义是一个递归定义。5树的定义ABCDEFGHIJKn由11个结点集合T组成的树， T=A,B,C,D,E,F,G,H,I,J,K，其 中结点A是根结点，除结点A外，其 余结点分成3个互不相交的集合 T1=B,E,F,G，T2=C， T3=D,H,I,J,K，形成了以结点A 为树根的3棵子树T1、T2、T3。而这 三棵子树本身又是一棵树。BiTree *LChild,*RChild; ;39二叉链表的创建(p66)status CreateBiTree(BiTree *T
3、) scanf( if(ch = ) T = NULL; else T = (BiTree*)malloc(sizeof (BiTree); T - data = ch;CreateBiTree( T-LChild);CreateBiTree( T-RChild); return OK;ABCDEFG输入序列：ABCDEGF40二叉树的基本操作及实现 nInitiate(bt)：初始建立二叉树bt，并使bt指向 头结点。 int Initiate(BiTree *bt) /初始化建立二叉树*bt的头结点if(bt=(BiTNode*)malloc(sizeof(BiTNode)=NULL)re
4、turn 0;bt-lchild=NULL;bt-rchild=NULL;return 1; 41二叉树的基本操作及实现ncreate(x，lbt，rbt) nInsertL(bt，x，parent) nDeleteL(bt，parent) n见书p565742二叉树的遍历n所谓树的遍历，就是按某种次序访问树中的结 点，要求每个结点访问一次且仅访问一次。n设访问根结点记作D，遍历根的左子树记作L， 遍历根的右子树记作R。则可能的遍历次序有 DLR DRL / LDR RDL / LRD RLD n当限制左右子树的访问顺序时，有三种方式： u前序/先序遍历：DLR u中序遍历：LDR u后序遍历
5、：LRD43前序遍历n算法描述： u若二叉树为空，遍历结束； u否则 访问根结点； 按前序遍历左子树； 按前序遍历右子树；+/a*efbcdelse visit(T); if(T-Lchild!= NULL) preorder(T-LChild); if(T-Lchild!= NULL) preorder(T-LChild); 45前序遍历的过程访问-，访问+，/入栈，访问a，*入栈，*出栈，访问*访问b，-入栈，-出栈，访问-，访问c，d入栈，d出栈访问d，/出栈，访问/，访问e，f压栈，f出栈，访问f访问输出序列：- + a * b c d / e f+/a*efbcd/s为一栈 int
6、top = 0; p = root; while(p != NULL) | (top 0) ) while( p != NULL) visit(p); /访 问根结点 s+top = p; /当 前结点压栈 p = p-LChild;/走 向左子树尽头 p = stop-; p = p-Rchild; /转向右子树 48中序遍历n算法描述： u若二叉树为空，遍历结束； u否则 按中序遍历左子树； 访问根结点； 按中序遍历右子树；+/a*efbcdelse if(T-Lchild != NULL) preorder(T- LChild); visit(T); if(T-Lchild != NUL
7、L) preorder(T- LChild); 50中序遍历的非递归算法n中序遍历的递规算法中仍然有系统压栈出现，如 果我们将这个过程在程序中描述出来，就是中序遍 历的非递归算法。n中序遍历的非递归算法 u设立一数组为栈。 u从二叉树的根结点开始，沿左子树一直走到末端(左子 结点为空) 按顺序将结点压栈。 u若左子树为空，从栈顶退出某结点，访问退出的结点 ，将指针指向该结点的右子结点。 u如此重复，直到栈为空或指针为空。51中序遍历的非递归算法void inorder(BiTree *T) BiTree *p,*sMaxsize + 1; int top = 0; p = root; whil
8、e(p != NULL) | (top 0) while( p != NULL) /走到左子树尽头 s+top=p; p=p- LChild; p = stop-; visit(p); /访问根 结点 p = p-Rchild; /指 向右子树 52后序遍历n算法描述： u若二叉树为空，遍历结束； u否则 按后序遍历左子树； 按后序遍历右子树； 访问根结点； +/a*efbcdelse if(T-Lchild != NULL) preorder(T- LChild); if(T-Lchild != NULL) preorder(T- LChild); visit(T); 54三种遍历输出序列的
9、特点n前序：输出的第一个结点是树的根结点。n中序：根结点在输出序列中间的某个位置，在它 的左边的序列全部是左子树的结点，在它右边的序 列全部是右子树的结点。n后序：最后一个输出的结点是根结点。n推想：有了根结点再加上中序序列，就可以区分 左子树和右子树。55二叉树的其它常见运算在二叉树中查找具有给定值的结点BiTree findnode(BiTree *bt, elemtype x) if ( bt = NULL) return(NULL); else if ( bt-data = x) return(bt); else return( findnode(bt-LChild)| findnod
10、e(bt-RChild); 56二叉树的其它常见运算求二叉树的深度int treehigh(BiTree *boot) int h,h1,h2;BiTree *p p = boot; if(t = NULL) h=0; else h1=treehigh(t- lchild); h2=treehigh(t- rchild); if(h1=h2) h=h1+1; else h=h2+1； return h; 57由遍历序列重构二叉树n可重构二叉树的结点序列组合：u先序序列和中序序列u中序序列和后序序列n不可重构二叉树的结点序列组合：u先序序列和后序序列58由结点序列恢复二叉树n由先序序列和中序序列
11、恢复二叉树：u由先序序列得到二叉树的根结点；u由上述(1)的根结点把中序序列分为左子树的中 序序列和右子树的中序序列两个部分；u根据上述左子树的中序序列个数找到对应的左 子树先序序列和右子树的先序序列；u按上述(1)、(2)、(3)同样的方法依次类推，直 到所得左、右子树只含一个结点为止。59int arcsnn; graph;86建立无向图的邻接矩阵void CreateAdj(graph *g) int i,j,k; for(k=0;kvk); for(i=0;iarcsij = 0; for(k=0;karcsij = 1; g-arcsji = 1;87邻接矩阵的插入删除操作n插入 u
12、无向图 g-arcsij = g- arcsji = 1; u有向图 g-arcsij = 1;n删除 u无向图 g-arcsij = g- arcsji = 0; u有向图 g-arcsij = 0;88图的链式存储结构邻接表n图的一种链式存储结构。以任何一个顶点为头结 点，将它的所有邻接点用单链表来存放n每个结点的组成 u该顶点(Vi)的邻接点u权值 u指向Vi邻接点的指针n每个单链表设一个头结点 u存储顶点的信息 u指向该顶点的第一个邻接点的指针n所有的头结点组成一个一维数组89邻接表示例n无向图1243V1V4V2V32341213 34124131234顶点序号90邻接表示例132有
13、向图23123 32123顶点序号91邻接表的性质n无向图邻接表 u第i个链表中结点的数目为顶点i的度u所有链表中结点数目的一半为图的边数 u占用了存储单元数为n+2en有向图邻接表 u第i个链表中结点的数目为顶点i的出度 u第i个顶点的入度为该顶点在所有链表中出现的次数 u占用存储单元的数目为n+e92邻接表数据类型描述Const int n = MaxV Const int e = MaxE struct link elemtype adjvex; weighttype data; struct link *next; Struct headnode elemtype V; struct
14、link *next; ;93建立无向图的邻接表void CreateLink() int i,j,k; struct link *s; headnode an; for(i=0;iadjvex = j; s-next = ai.next; /头插法建表 ai.next = s;94建立无向图的邻接表(续)s = (struct link*)malloc(sizof(struct link); s-adjvex = j; s-next = ai.next; ai.next = s; 讨论： (1)怎样建立有向图的邻接表？ (2)用尾插法建立单链表的方法如何？95图的遍历n从已给的连通图中某一顶
15、点出发，沿着一些边访 遍图中所有的顶点，且使每个顶点仅被访问一次， 就叫做图的遍历(Graph Traversal)n图中可能存在回路，且图的任一顶点都可能与其 它顶点相通，在访问完某个顶点之后可能会沿着某 些边又回到了曾经访问过的顶点。n为了避免重复访问，可设置一个标志顶点是否被 访问过的辅助数组visited ，它的初始状态为0 ，在图的遍历过程中，一旦某一个顶点 i 被访问， 就立即让 visitedi为1，防止它被多次访问。96两种遍历方式n深度优先搜索(Depth_First Search)n广度优先搜索(Breadth_First Search)97深度优先搜索(DFS)n访问某给定的顶点i,并标识visitedi=1；n搜索与顶点i有边相连的下一个顶点j，若j未被访 问过，访问它，并标识visitedj=1，然后从j顶 点开始按照深度优先算法处理j；若j被访问过，再 看与i有边相连的其它顶点；n若与顶点i相连的顶点都被访问过，则退回到前 一个访问顶点并重复刚才的过程，直到图中所有的 顶点都被访问过。98例(邻接矩阵实现的图)
