LsWorld

图的基本概念图的定义 图G（Graph）由顶点集V（Vertex）和边集E（Edge）组成，记为$$G=(V,E)$$，其中V(G)表示图G中顶点的有限非空集：E（G）表示图G中顶点之间的关系（边）集合，如图1-1。 注： 线性表可以是空表，树可以是空树，但图不能是空图。图可以没有边，但不能没有顶点。 有向图有向图就是点与点之间相互有方向之间的关系，若设v,w为顶点，而<v,w>为从顶点v到顶点w，则有向图中$$<v,w>\neq<w,v>$$。 无向图在无向图中，若设v,w为顶点，而<v,w>为从顶点v到顶点w，则有$$<v,w>=<w,v>$$。 简单图、多重图简单图就是满足以下条件的图： 不存在重复边。 不存在顶点到自身的边 多重图就是图中某两个结点的边数多余一条，又允许顶点通过同一条边和自己关联，则G为多重图。 顶点的度、入度、出度对于无向图：顶点v的度是指依附于该顶点的边的条数，记为TD（v）。 在具有n个顶点、e条边的无向图中，无向图的全部顶点度的和等于边数的2...

树的定义和基本术语 树的定义：树是一种递归定义的数据结构，它包含一个根结点和若干个子树。当树的结点数为0时，称为空树；当树的结点数大于0时，除了一个特定的根结点外，其余的结点被分成m个互不相交的有限集合T1, T2,…, Tm，其中每个集合本身又是一棵树，并且称为根结点的子树。 非空树的特性： 有且仅有一个根节点。 没有后继的结点称为“叶子结点”（或终端结点）。 有后继的结点称为“分支结点”（或非终端结点）。 除了根结点外，任何一个结点都有且仅有一个前驱结点。 每个结点可以有0个或多个后继结点。 树结点之间的关系描述 根据1-2图可以得出结点之间的关系描述： 祖先结点：对于”你”结点到”爷爷”结点都是祖先结点，即结点的所有前驱结点为祖先结点。 子孙结点：对于”爷爷”结点，所有后继结点都是子孙结点，即对于一个结点所有后继结点都是子孙结点。 双亲节点（父结点）：对于”你”结点，”父亲”结点即为父结点，即对于一个结点的直接前驱结点为父结点。 孩子结点：对于”父亲”结点来说，”你“结点与”F”结点都是”父亲”结点的孩子结点，即对于一个结点的直接后继结点。 兄弟结点：对于”你...

串的实现在C语言中所使用的字符串就是串的数据类型的一种。 串的存储结构定长顺序存储表示类似于线性表的顺序存储结构，用一组连续的存储单元存储串值的字符序列。 #define MAXLEN 255 //预定义最大串长为255 typedef struct SString { char ch[MAXLEN]; //每个分量存储一个字符 int length; //串的实际长度 }SString; 串的实际长度只能小于或等于MAXLEN，超过预定义长度的串值会被社区，称为截断。串长的表示由两种方法：一种是通过length存放串的长度；二是在串值后面加一个不计入串长的结束标记字符'\0'（C语言种字符串就是采用这种方法），此时串就根据'\0'来算长度。 堆分配存储表示堆分配存储表示仍然以一组地址连续的存储单元存放串，但存储空间是动态分配获得。 typedef struct{ char *ch; //按串长分配存储区，ch指向串的首地址 int length; //串的长度 }HStr...

数制 数制的概念就不过多赘述，这里主要描述十进制，二进制，八进制以及十六机制间的相互转换。 十-二-八-十六进制之间的转换二进制转十进制按位权进行展开再求和。 例：$$(101110.011)2 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 + 0\times 2^{-1} + 1 \times 2^{-2} + 1 \times 2^{-3} = (46.375){10}$$ 十进制转二进制十进制通过除2即可将再将每次除过后的余数保存下来并倒序即可获得相应的二进制数。整数部分采用“除基取余，小鼠部分采用“乘基取整法” 例：$$(26.375)_{10}$$ 整数部分（%代表取余）：26%2 = 0 ，后再将 13 % 2 = 1 （13是通过26/2算出），后 6 % 2 = 0，再 3 % 2 = 1，最后 1%2 = 1，一直除到商为0为止。将取到的余倒序，...

栈在表达式求值中的应用 表达式求值是程序设计语言中最基本的问题，在中缀表达式中不仅依赖运算符的优先级，而且还要处理括号。后缀表达式的运算符在操作数后面，在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符，更符合CPU的运算与处理。 中缀表达式转后缀表达式（手算）中缀表达式A + B * (C - D) - E / F化为后缀表达式采用左优先的原则（没有运算符更高级的一律从左往右进行匹配，保证算法的唯一性）。 在这表达式中先进行( )中进行运算，并将运算符放在操作数后面，得CD-。 此时CD-为一个整体并根据运算符优先级与B*进行运算得BCD-*。 再与A+进行运算，得ABCD-*+，剩下就是- E / F部分，先进行除运算得EF/，再ABCD-*+与EF/进行减运算，得最终结果ABCD-*+EF/-。 中缀表达式转后缀表达式（机算）初始化一个栈，用于保存展示还不能确定运算顺序的运算符。 从左到右处理各个元素，直到末尾。可能遇到三种情况。 遇到操作数。直接加入后缀表达式。 遇到界限符。遇到"("直接入栈：遇到")"则依次弹...

电路和电路模型 电路是由电路零件、器件经导线连接而成的电通路装置。 电路零件常称为电路部件（例如电阻器、开关、蓄电池等）； 电路器件则是由电路部件组成且具有某种功能的产品（如晶体管、集成电路等）； 在电路中所产生的电压、电流是在电源的作用下产生的，因此电源又称为激励源或激励；由激励在电路中产生的电压、电流等称为响应。 电路模型电路模型 图片中左侧为简单的实际电路，由若干个干电池和小灯泡组成，右侧为电路模型，反映了将嗲能转换为热能和光能的物理现象；用理想电路元件或它们的组合模拟实际器件就是建立其模型，简称建模。 电流和电压的参考方向 电路理论中将电流（I）、电压（U）、电荷（Q）和磁通（Φ）来进行表示。磁通链用ψ进行表示。电功率和电能量分别用P和W。 在电路分析中，需指定电流或电压的参考方向后才能开始进行分析和计算。 在上图中规定了A到B电流i的方向为A->B，若实际电流方向和参考方向一致，则电流为正值，即i>0；若参考方向和实际方向不一致，即i<0。这样在指定的电流参考方向下，电流值的正负就可以反映除电流的实际方向，如下图所示。 同理，对电路两点...

题目1：删除最小值 题目： 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。 具体实现// 删除顺序表中最小值的元素 bool SqListDeleteMinimun(SqList *L,ElemType *e) { //判断顺序表是否为空 if (L->length == 0) { return false; } // 用于存放最小值 ElemType minValue = *(L->data + 0); // 用于存放最小值的索引 int index = 0; for (size_t i = 0; i < L->length - 1; i++) { if(*(L->data + i) > *(L->data + i + 1)){ minValue = *(L->data + i + 1); index = i+1; } &...

线性表的定义 注：线性表是一个逻辑结构！并不是真正物理意义上的地址相邻，而是在抽象层面的相邻，不要和顺序表搞混！ 线性表是具有相同数据类型的n个数据元素的有限序列。除了第一个元素意外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。 例：$$设有一个线性表 L=(a_1,a_2,…,a_i,a_{i+1},…,a_n)(a_1到a_n皆为int类型)\此时a_2的直接前驱为a_1,直接后继为a_3,以此类推。$$ 由此，可以得出以下特点： 表中元素的个数有限 表中元素具有逻辑上的顺序性 表中元素的数据类型相同，所占存储空间大小相同 元素都是数据元素，每个元素都是单个元素 线性表是逻辑结构，顺序表和链表指的是存储结构，两者概念不相同。 顺序表的定义与实现顺序表的定义 顺序表是用一组地址连续的存储单元依次存储线性表中的数据元素，使每个元素即在逻辑上相邻也在物理位置上相邻。 顺序表的第一个元素表示顺序表的起始位置，接下来的元素地理位置都是在第一个元素之后，所以可得顺序表的特点是元素的逻辑顺序（即线性表）和物理顺序相同。 例： ...

动态内存函数为解决动态的开辟内存空间的需求，C语言提供了一个动态内存开辟的函数： void *malloc( size_t size); 这个函数向内存申请一块连续可用的空间，并返回指向这块空间的指针。 开辟成功后会返回指向这片空间的指针。 若失败则会返回NULL指针。 并且提供了void free(void *ptr)来释放不再使用的动态内存空间。 //向内存申请10个整形的空间 int* p = (int*)malloc(10*sizeof(int)); //向内存申请失败打印错误原因 if(p ==NULL){ printf("%s\n",strerror(errno)); } //当动态申请空间不再使用则释放 free(p); p = NULL; 开辟动态数组void *calloc(size_t num,size_t size)会在内存中开辟一个初始全为0的数组。 // 向内存申请10个整形的空间 int *p = (int *)calloc(10, sizeof(int)); // 当动态申请空间不再使用则释放 free(p)...

使用以下所有函数需要引入头文件#include <string.h> strlen()函数size_t strlen(const char *string)传入字符串返回字符串长度，这里size_t == unsigned int所以这里要是直接进行比较将会以无符号数进行比较。 例： // strlen("abc") == 3 strlen("abcef") == 5 (strlen("abc") - strlen("abcef")) == 2 无符号数加减符号位默认为正 if (strlen("abc") - strlen("abcef") > 0) { printf("unsigned");//这条语句将会打印 } else { printf("signed"); } 递归实现strlen()函数int Strlen(const char *str) { //当查询到为\0时结束递归 if (*str == '\0') { return 0; } ...

根据qsort函数来实现冒泡排序版本，实现后时间复杂度为O(n^3)，仅供练习使用，实际运用效率过于低下。 qsort 函数定义于<stdlib.h>头文件中，主要接收参数： void qsort( void *ptr, [size_t] count, [size_t] size,int (*comp)(const void *, const void *) ); ptr为传入的数组 count为数组的长度 size为类型所占字节大小 comp为一个比较函数，若前一个元素大于后面的元素则返回大于0的数，反之返回小于0的数，相等则返回0。 了解qsort基本参数后就可将要实现的排序通过这些参数为标准来进行设计。 //主要排序函数实现 // base:要排序的数组 sz:数组长度 width:类型所占字节大小 cmp:排序所要传的函数(通过正负来判断大小) void bubble_sort(void *base, int sz, int width, int (*cmp)(void *e1, void *e2)) { for (size_t i =...

指针类型的意义： 1.指针类型决定了指针解引用操作符能访问几个字节： char* p能访问1个字节， int* p 能访问4个字节 2.指针类型决定了指针+1，-1，加的或者减的时几个字节：char* p；p+1，跳过一个字节。int* p; p+1，跳过四个字节。 int a = 0x11223344; char* cp = (char*)&a; int* ip = &a; printf("%p\n",*cp);//00 00 00 44 printf("%p\n",*ip);//11 22 33 44 字符指针在指针类型中将char*称为字符指针。 char a[] = "abcdef"; char* p = a; printf("%s\n",a); //abcdef printf("%s\n",p); //abcdef const char* p1 = "abcdef"; const char* p2 = "abcdef"; if (p1==p2) { printf("相同");//会进行打印，说明p1和p2指向同一块内存空间 &...