修心的小屋

栈(Stack)栈的基本概念定义  只允许在一端进行插入或删除操作的线性表。首先，栈是一种线性表，但限定这种线性表只能在某一段进行插入和删除操作。   栈顶（Top）：线性表允许进行插入和删除的一端。   栈底（Bottom）：固定的，不允许进行插入和删除的另一端。   空栈：不含任何元素。   如上图：a1为栈底元素，an为栈顶元素。由于栈只能在栈顶进行插入和删除操作，故进栈次序依次为a1，a2，… ,an 而出栈次序为an，…，a2，a1。栈的明显的操作特征为后进先出（Last In First Out，LIFO）,故又称 后进先出的线性表。 栈的基本操作  1）InitStack（&S）：初始化空栈S   2）StackEmpty（S）：判断一个栈是否为空   3）Push（&S，x）：进栈，若栈未满，则将x加入使之成为新栈顶   4）Pop（&S，&x）：出栈，若 ...

栈和队列的应用栈的应用验证括号的正确性  题目很简单就是输入一串字符，判断字符中的括号是否合法。直接上代码： #include <iostream>#include <string.h>using namespace std;typedef char ElemType;#define MAXSIZE 100typedef struct Stack{ ElemType data[MAXSIZE]; int top;}Stack;void InitStack(Stack& S) { S.top = -1;}bool StackEmpty(Stack S) { if (S.top == -1) { return true; } return false;}bool Push(Stack& S, ElemType x) { if (S.top == MAXSIZE - 1) { return false; } S.top+ ...

循环链表循环单链表  循环单链表和单链表的区别在于：循环单链表的最后一个结点的指针不是NULL，而改为指向头结点，从而整个链表形成一个环。   在循环单链表中，表尾结点tail的next指针指向头结点，所以表中没有指针域为NULL的结点，因此，循环单链表的判空条件不是头结点的指针是否为空，而是判断头结点的指针是否等于头指针，就是说是否指向自身。 初始化bool InitLinkList(LinkList& L){ LNode* L = (LNode*)malloc(sizeof(LNode)); if( L == NULL){ return false; } L->next = L; return true;} 判空bool IsEmpty(LinkList& L){ if( L->next == L){ return true; } return false;
...

线索二叉树基本概念  遍历二叉树以一定规则将二叉树中的结点排列成一个线性序列，得到二叉树结点的各种遍历序列，其实质是对一个非线性结构进行线性化操作，使这个访问序列中的每个结点（第一个和最后一个除外）都有一个直接前驱和直接后继。   引入线索二叉树是为了加快查找结点前驱和后继的速度。在有n的结点的二叉树中，有n+1个空指针。   在二叉树线索化时，通常规定：若无左子树，令lchild指向其前驱结点；若无右子树，令rchild指向后继结点。还需要增加两个标志域表明当前指针域所指对象是指向左（右）子结点还是指向直接前驱（后继）。   线索二叉树的存储结构描述如下： typedef struct ThreadNode{ ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag;}ThreadNode,*ThreadTree;   以这种结点构成的二叉链表作为二叉树的存储结构，称 ...

网络编程基本原理 Socket通信函数soketint socket( _In_ int af, //AF_INET _In_ int type, //socket类型，SOCK_STREAM(Tcp),SOCK_DGRAM(UDP) _In_ int protocol //协议 ); 返回：非负描述字──成功， -1──出错 参数family 这个参数指定一个协议簇，也往往被称为协议域。系统存在许多可以的协议簇，常见有AF_INET──指定为IPv4协议，AF_INET6──指定为IPv6，AF_LOCAL──指定为UNIX 协议域等等。它值都是系统预先定义的宏，系统支持哪些协议我们才可以使用，否则会调用失败。协议簇是网络层的协议。 参数type 这个参数指定一个套接口的类型，套接口可能的类型有：SOCK_STREAM、SOCK_DGRAM、SOCK_SEQPACKET、SOCK_RAW等等，它们分别表明字节流、数据报、有序分组、原始套接口。这实际上是指定内核为我们提供的服务抽象，比如我们要一个字节流。需要注意的 ...

特殊矩阵的压缩存储 数组的存储结构   一个数组中的所有元素在内存中占用一段连续的存储空间。   对于多维数组，有两种映射方法：按行优先，按列优先。以二维数组为例：按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。 矩阵的压缩存储   压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。目的是为了节省存储空间。   特殊矩阵：指具有许多相同矩阵的元素或零元素，并且这些相同矩阵沿元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有 对称矩阵，上（下）三角矩阵，对角矩阵。 对称矩阵      上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存储，则会浪费几乎一半的存储空间，所以我们存放在一个一维数组B[n(n+1)/2]中，即元素a(i,j) 存放在b(k)中。   元素a(i,j)在数组b中的下标k = 1 + 2 + … + (i - 1) + ( j - 1) = i (i-1) / 2 + j - 1 (数组下标从0 开始)。   因此，元素下标之间的对应关系为： k={i(i−1)/2+j−1i>= ...

顺序表  线性表的顺序存储又称顺序表。表中元素的逻辑顺序与其物理顺序相同。 定义静态定义：#define MAXSIZE 50; //定义线性表的最大长度typedef struct { ElemType data[MAXSIZE]; //顺序表的元素 int length; //顺序表的当前长度}Sqlist; //顺序表的类型定义   静态分配时，数据量小的话，会造成数组空间的浪费；而如果是数据量大的话，就会造成溢出，进而导致程序崩溃。所以我们采用下面更灵活的方式来 动态分配#define InitSize 100 //定义线性表的初始长度typedef struct { ElemType* data; //指示动态分配数组的指针 int MAXSIZE,length; //数组的最大容量和当前个数}Sqlist;   C的初始化分配语句为： L.data = (ElemType*)mal ...

双链表  单链表结点中只有一个只指向后继的指针，使得单链表只能从头结点开始一次顺序的先后遍历。要访问某个结点的前驱结点（插入删除操作时），只能从头开始遍历，访问后继节点的时间复杂度为O（1），访问前驱结点的时间复杂度为O（n）。   为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior 和 next，分别指向其前驱结点和后继结点。 定义  双链表中结点类型描述： typedef struct DNode{ ElemType data; struct DNode *prior, *next;}DNode,*DLinkList;   在双链表中，按位查找和按值查找的操作和单链表中的相同。但在插入和删除上有着较大的不同。因为双链表有prior指针，可以很方便地找到其前驱结点，因此插入，删除结点的时间复杂度为O（1）。 前插操作   将结点s 插入到指针p所指结点b之前： bool DLinkList_Insert(DLinkList& ...

树、森林树的存储结构  树的存储方式有很多种，既可采用顺序结构，又可采用链式存储结构，但无论采用何种存储方式，都要求能唯一的反映树中各结点之间的逻辑关系。下面是常见的存储结构： 双亲表示法  这种存储方式采用一组连续空间来存储每个结点，同时在每个结点中增设一个伪指针，指示其双亲结点在数组中的位置。   双亲表示法的存储结构描述: #define MAX_TREE_SIZE 100 //树中最多结点数typedef struct{ //树中的结点定义 ElemType data; //数据元素 int parent; //双亲位置}PTNode;typedef struct{ //树的类型定义 PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //结点数}PTTree;   该存储结构利用了每个结点（根结点除外）只有唯一双亲的性质，可以很快得到每个结 ...

区别顺序表和链表的比较 顺序表 单链表 存取方式 可顺序存取，可随机存取 只能从表头顺序存取 逻辑结构和物理结构 顺序存储，逻辑上相邻物理上也相邻 链式存储，逻辑上相邻物理上不一定相邻，通过指针链接 按值查找 按值查找：O（n）(无序)折半查找 O(log2n)(有序) O（n） 按序号查找 O（1） O（n） 插入 O（n），平均需要移动n/2个元素 只需修改相关结点 删除 O（n），平均需要移动n/2个元素 只需修改相关结点 空间分配 可能会出现存储空间大量闲置或空间不足溢出 动态申请空间，操作灵活、高效 怎样选取存储结构  1、基于存储的考虑     难以估计线性表的长度或存储规模时，不易采用顺序表；但链表的存储密度较低，链式存储结构的存储密度是小于1的。   2、基于运算的考虑     若经常做的运算是按序访问数据元素，则显然顺序表更优。     若经常做插入删除操作，则链式存 ...