- 博客(20)
- 问答 (1)
- 收藏
- 关注
RSS订阅原创 非线性表——图——关键路径/最短路径
9.7.2关键路径AOE网：顶点表示事件，弧表示活动，权表示活动持续时间。把工程计划表示为有向图，整个工程只有一个开始点(入度为零的点，源点)，一个完成点(出度为零的点，汇点)。路径长度：路径上各活动持续时间(边的权值)之和。完成工程的最短时间：源点到汇点的最长路径的长度。关键路径：路径长度最长的路径。关键活动：关键路径上的活动。事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径的长度。求ve(i)：从源点开始，按拓扑顺序向汇点递推。ve(1)
2022-05-29 09:15:00
2779
2
原创 非线性表——图——有向无环图之拓扑排序
7有向无环图DAG也是描述一项工程或系统的进行过程的有效工具，几乎所有工程都可分为若干个称作活动的子工程。9.7.1拓扑排序AOV网：用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网(不应该有环).方法：在有向图中选一个没有前驱的顶点且输出之 ，从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。拓扑序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C
2022-05-28 07:45:00
333
1
原创 非线性表——图——图的遍历/连通性/生成树
9.3图的遍历要避免同一顶点被访问多次，所以在遍历过程中，必须记下每个已访问过的顶点。可借助一辅助数组visited[0…n-1]；初始置为0，一旦访问了顶点vi，置visited[i]为1或访问时的次序号。9.3.1深度优先遍历void DFSTraverse( Graph G ){ int i, visited[M]; for( i=0; i<G.vexnum; i++ ) visited[i]=0; for( i=0; i<G.ve..
2022-05-27 08:15:00
535
原创 非线性表——图——基本概念/存储结构
9.1基本概念图G是由两个集合V(G)和E(G)组成的，记为G=(V,E)。其中： V(G)是顶点的有限集。 E(G)是边的有限集，边是顶点的无序对或有序对。如果图G(V,E)和图G’(V’,E’),满足： 则称G’为G的子图。有向图：E(G)是有向边（也称弧）的有限集，弧是顶点的有序对。记为<v,w>，v,w是顶点，v为弧尾，w为弧头。无向图：无向图G由两个集合V(G)和E(G)组成。其中： V(G)是顶点的有限集。 E(G)是边的有限集，边是顶点..
2022-05-26 15:53:39
1330
原创 非线性表——哈夫曼树
8.7哈夫曼树哈夫曼树（最优二叉树）：带权路径长度最小的二叉树。路径：从树中一个结点到另一个结点之间的分支。路径长度：路径上的分支数。结点的权：给树的每个结点赋予的实数。结点的带权路径长度：该结点到根结点之间的路径长度与结点上权的乘积。树的带权路径长度：8.7.1构造哈夫曼树（2）在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和；(3)在森林中删除这两棵树，同时将新的二叉树加入森林中；(4)重复上
2022-05-15 07:30:00
1767
原创 非线性表——树和森林
8.6树和森林8.6.1双亲表示法实现：定义结构体数组存放树的结点结点包含两个域：数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置特点：找双亲容易，找孩子难类型描述：#define MAXSIZE 100typedef struct PTNode { TElemType data; int parent;}PTNode;typedef struct { PTNode nodes[MAXSIZE]...
2022-05-14 09:30:00
362
原创 非线性表——线索二叉树
8.5线索二叉树8.5.1基本概念每个结点增加两个指针域，指示遍历时得到的前驱和后继。但是，存储密度大大降低。在n个结点的二叉链表中必定存在有n+1个空链域，利用空链域来存放结点的前驱、后继信息。同时结点增加两个标志域LTag，RTag： 若LTag=0，LChild域指向左孩子；若LTag=1，LChild域指向其前驱。 若RTag=0，RChild域指向右孩子； 若RTag=1，RChild域指向其后继。当二叉树以某种次序遍历使其变为线索二叉...
2022-05-13 08:00:00
527
原创 非线性表——遍历二叉树代码
8.4.2遍历代码无论按哪一种次序进行遍历，对含有n个结点的二叉树，其时间复杂度均为O(n)。非递归所需辅助空间为栈的最大容量，即树的深度，最坏情况下，空间复杂度为O(n)。以下都为递归算法实现8.4.2.1先序遍历void PreOrder( BiTree t ) { if( t ) { printf( t->data); PreOrder( t->lchild ); PreOrder( t->
2022-05-12 09:15:00
268
原创 非线性表——树/二叉树——基本性质特点
8.1树的基本概念8.1.1树的表示形式括号表示法凹入表示法8.1.2树的基本术语结点的度：结点的子树个数树的度：树内各结点的度的最大值叶子/终端结点：度为0的结点分支/非终端结点：度不为0的结点内部结点：除根结点之外的分支结点祖先：从根结点到该结点所经分支上的所有结点。子孙：以某结点为根的子树中的任一结点都称为该结点的子孙结点的层次：从根开始，根为第一层，根的孩子为第二层，…树的深度或高度：树中结点的最大层次数。堂
2022-05-11 20:18:09
987
原创 线性表——广义表
7广义表广义表是递归定义的线性表，广义表是一个多层次的线性结构ai 可以是单个元素(原子，用小写字母表示)，也可以是广义表(子表，用大写字母表示) A = ( ) F = (d, (e)) D = ((a,(b,c)), F) C = (A, D, F) B = (a, B) = (a, (a, (a, ... , ) ) )7.1结构特点广义表的长度定义为最外层包含元素个数;广义表的深度定义为所含括号的重数;一般用〇表示子表，用□表示原子...
2022-05-08 07:15:00
5527
1
原创 线性表——数组
6.二维数组矩阵A【m×n】可以看成是由n个列向量组成的线性表矩阵A【m×n】可以看成是由m个行向量组成的线性表二维数组可以看作是拓展的线性表6.1顺序存储一旦确定，不做插入删除操作6.1.1计算存储地址以行序为主序二维数组A【m*n】中任一元素a i, j 的存储位置LOC(i,j) = LOC(1,1) + (n×（i-1）＋（j-1）)×L三维数组A【r*m*n】中任一元素a i ,j ,k 的存储位置Loc[i,j,k]=Loc[1,1,1]+(.
2022-05-07 16:37:14
1524
原创 线性表——串——堆串/链串
5.2堆串为了解决定长顺序串的截断问题，引出不限定串长动态分配的堆串5.2.1类型构造typedef struct { char * ch; int len; // 串长度} HString;5.2.2串赋值//将字符串tval的值赋给串sStrAssign(HString * s ,char * tval) { if(s->ch!=NULL) free(s->ch); //将s置空 i=0; while(tval[i]
2022-05-06 09:15:00
434
原创 线性表——串——定长顺序串
长度为n的串的子串数目为n(n+1)/2+1长度为1的子串有n个，长度为2的子串有n-1个，长度为3的子串有n-2个，……，长度为n的子串有1个，+空串5.1定长顺序串超出预定长度，截断5.1.1类型构造#define MAXLEN 20typedef struct { char ch[MAXLEN]; int len;} SString; 5.1.2置空串StrClear( SString *s ){ s->len=
2022-05-05 10:00:00
450
原创 线性表——顺序栈
特点LIFO后进先出有顺序栈和链栈两种3.1顺序栈3.1.1类型说明typedef struct { ElemType elem[Stack_Size]; int top;//栈顶下标 }SeqStack;top==-1，表示栈空；top== stacksize-1，表示栈满；3.1.2初始化void InitStack ( SeqStack * s ){ S->top= -1;}3.1.3入栈in...
2022-05-04 09:00:00
211
1
原创 线性表——链表的应用
2.3链表的应用2.3.1一元多项式的存储2.3.1.1定义typedef struct Polynode { int coef;//系数 int exp;//指数 struct Polynode *next;//指针域}Polynode , * Polylist; 2.3.1.2尾插法建表Polylist polycreate( ) { rear=head=(Polynode *)malloc(sizeof(Polynode)); //分配头结点
2022-05-03 11:30:00
243
原创 线性表——循环链表/双向链表
2.2循环链表比单链表多了个尾指针，指向头结点2.2.1循环链表的合并LinkList merge(LinkList LA, LinkList LB) { p=LA; q=LB; while(p->next!=LA) p=p->next; /*找到表LA的表尾*/ while(q->next!=LB) q=q->next; //找到表LB的表尾 p->next=LB->next; //表LA的尾指针指向LB首元结点 q->
2022-05-02 11:15:00
304
2
原创 线性表——队列
4.1队列特点：FIFO4.2.1链队列的结点结构#define TRUE 1#define FALSE 0typedef struct QNode { ElemType data; struct QNode *next;}LinkQueueNode,*Queueptr;typedef struct{ Queueptr front; //头指针 Queueptr rear; //尾指针}LinkQueue;当Q.f
2022-05-02 09:31:45
128
原创 线性表——链栈
3.2链栈依然设置头结点top3.2.1结点类型typedef struct node{ ElemType data;//数据域 struct node *next;//指针域}LinkStackNode， *LinkStack;3.2.2入栈int Push(LinkStack top, ElemType x) { temp=(LinkStackNode *)malloc(sizeof(LinkStackNode)); temp->d
2022-05-01 16:42:24
320
原创 线性表——链表
2.1单链表设置头结点原因：无论是否为空表，都可以将首元结点当做其它结点一样操作2.1.1定义typedef struct Node{ ElemType data；//数据域 struct Node * next；//指针域}Node, * LinkList；Node *p;//Node是结点，类型为指针//Linklist为结构体名，类型为指针2.1.2头插法建表Linklist CreateFromHead( ){ LinkList L; Node *s;
2022-05-01 09:50:58
608
2
原创 线性表——顺序表篇
1.线性表——顺序表篇1.1特点1、顺序表是静态链表，地址连续1.2代码功能实现1、静态动态申请区别typedef struct{ ElemType elem[maxsize]；/*静态申请*/ int last；}SeqList；ps:last是下标，不是序号Elemtype是元素类型，就相当于 int ，float之类的elem是变量名typedef struct{ ElemType *elem；//动态申请
2022-04-30 21:15:46
160
空空如也
An exception occurred processing JSP page
2023-10-15
疑惑？蓝桥杯货物摆放真题
2022-04-04
TA创建的收藏夹 TA关注的收藏夹
TA关注的人