Ferry's blog

前言二叉树也有顺序存储结构和链式存储结构。由于二叉树是一种特殊的树，所以也可以通过顺序存储结构来实现。因为是顺序存储结构，所以要用数组来实现。 顺序存储结构 存放数据的区域（数组），而且数组的下标也要体现节点间的逻辑关系。 数组的大小要定义为完全二叉树的大小。当中某些节点有可能是为空的，所以顺序存储结构一般只用于完全二叉树，否则会造成空间的浪费。 链式存储结构既然顺序存储结构的适用性不强，所以将引入二叉链表。它一般被分为两个区域——数据区和指向左右孩子的指针区。然而它还可以在指针区增加一个指针来指向父母。 123456789typedef struct Node *PtrToNode;typedef PtrToNode Tree;typedef int ElementType;typedef struct Node{ ElementType e; PtrToNode lchild, rchild;}Node

||=== A||B 记忆如果当A与B都是false才false，其余都是true（只有1个假） 短路如果||的左侧表达式为真，则不会执行右侧表达式。 && A&&B 记忆如果当A与B都为true才true，其余都是false（只有1个真） 短路如果&&的左侧表达式为假，则不会执行右侧表达式。

前言链队列就是限制了只能在首端和尾端进行插入，删除操作的表。 链队列中需要头节点 实现它需要声明两个结构。QNode存储某一项的数据，和指向下一项的结构指针。ListQueue存储指向头节点和尾节点的结构指针。 12345678910typedef struct QNode{ ElementType data; struct QNode *next;}QNode, *QNodePtr;typedef struct ListQueue{ QNodePtr front, rear;}ListQueue, *ListQueuePtr; 空队列判断条件 front和rear同时指向头节点 操作插入12345678910111213void EnQueue(ListQueuePtr Q, ElementType e){ QNodePtr P = (QNodePtr)malloc(sizeof(QNode)); if(P == NULL) { ...

前言队列也是一种表。它把线性表限制了只能在第一项删除和最后一项添加数据。由此，它的结构– 指向头和尾的指针 每一项的数据 由于队列的删除和插入操作，需要移动数据而且时间复杂度为O(n)，但可以通过引入循环队列来使得时间复杂度变为O(1) 队列也同线性表类似，可以有两种存储结构。顺序存储结构 和 链式存储结构 顺序存储说明同样地，顺序存储结构用到数组来实现。结构中记录头和尾的指针其实是数组的下标(int)（front,rear)注意，rear是指队尾元素的下一个位置，front是队头（第一个元素） 空队列的判断。所以，当rear == front的时候，不是还剩一个元素，而是空队列。（一个元素都没有） 当我们用循环队列的时候，如果，元素把整个数组都占满的时候，那么rear == front着个等式不是也成立吗？那么我们怎么区分满队列和空队列呢？我们应该采取一种方法—永远不要让元素占满整个数组。应该留一个空位。 满队列的判断。因为要留下一个位置不能用，要用Q->rear + 1 ==...

前言栈是为了限制插入，删除只能在末端的一种表。栈通常的操作有Push和Pop。与同表类似，栈也有顺序存储结构和链式存储结构。 顺序栈第一种 顺序栈用数组实现。定义一个结构中有存放数据的数组（data[])，以及表明栈顶的数组下标（top）。 进行Push和Pop操作的时候，通过给top++；来表面栈在数组中增添位置。 空栈顺序栈以数组来实现，所以下标为0时为第一个元素。当S->top = -1即一个元素也没有。 满栈当数组下标top - 1时，数组被占满。 123456789101112131415#ifndef _STACK_H_/*顺序存储结构的栈*/#define MAXSIZE 20typedef int SElementType;typedef struct { SElementType data[MAXSIZE]; int top;} SqStack;void Push(SqStack *S, SElementType e);SElementType Pop(SqStack...

前言拥有头节点的链表 头节点的date区可以存放链表的整体数据（例如：长度） 实现接口遍历链表遍历链表一般使用while循环。相关操作有：GetElement() ListLength() Insert()很多很多都可以使用遍历链表来实现 虽然当我们的函数参数为（结构指针）的时候，在函数中改变指针的指向，不会影响到指针的指向。但是，如果我们传递结构指针的指针来改变指针的指向呢？（例如：malloc创建节点） 针对以上问题，我们可以在函数中再定义一个指针，让它指向第一个节点，由此循环链表。Position P = L->next 同时必须确定循环条件。i为要遍历第i个元素(从1开始对应节点)，所以也必须设置计数器count = 1。当P == NULL，证明它已经过了最后一个节点。 12345while(P != NULL && count < i){ P = P->next; count++; } 限制i的值不在元素之中的情况 一真全真12345if(P ==...

前言ADT（抽象数据类型），如果我们的程序需要使用类型，C中没有与之匹配的基本类型。那我们可以自己定义抽象数据类型。如果，我们要设计一个数据类型需要： 提供存储数据的方法。（定义一个结构） 描述操控该数据的方法 如何实现？ 对数据类型进行一个属性和操作的描述。 开发一个实现ADT的接口。（在.h头文件） 编写代码实现接口。（.c文件） 例如int类型给我们的属性是：它代表一个整数值。操作是：可以进行+ - * / % Anyway.ADT就是描述一些这个类型是属性和操作。如果要实现它，再通过接口(.h .c)来实现它。

前言线性表有一种物理结构叫顺序存储结构。它由一系列连续的存储单元组成，从而使得逻辑上相邻的两个元素也连续。 这样的结构可以使用一维数组来实现。数组的下标从0开始，但我们的元素是从1开始。所以，我们可以这样看：元素均对应，但标志不一样（只需在用[]时，-1即可） 12345#define MaxSize 50 // 定义线性表的最大长度typedef struct{ ElemType data [MaxSize] ; // 表的元素 int length; // 线性表的当前长度}SqList; // 表的类型定义 注意线性表长度和数组长度不同 操作Insert 如果线性表长度等于数组长度，退出 如果插入到线性表长度+1以外，退出 如果不是插到最后（length + 1），那么for，从最后一个元素到第i个，一个个往后退 Delete 如果线性表为空，退出 如果删除表以外的数据，退出 如果不是删除最后位置，for，从i+1到length一个个向前移 示例11234567891011121314151617#define TSIZE...

前言ADT是一些操作的集合。用ADT风格，它侧重于问题的解决思路来表达程序，而不是将代码的细节暴露出来，不是将解决的工具来表达程序。所以，ADT风格的可读性更高，而且是解决问题中最关心的问题。例如：表，集合，图都可以看作ADT。ADT需要拥有相关属性和操作。定义ADT需要确定如何存储数据，以及管理该数据的函数使用ADT应该用一般的语言来描述，不应该用某种特定的计算机语言来表示，且不应该具体的实现细节 定义ADT的步骤 定义接口（定义相关的函数原型） 实现接口（实现与函数原型相应的函数） 使用接口 如果要使用一个简单的链表程序组成: list.h(提供数据类型和接口的原型(general type definitions + function...

前言双链表和单链表的插入，删除，交换。可以想象成锁链，但是，前后的链不能断开联系 交换123456789101112void SwapWithNextAndLast(Position BeforeP){ Position P = BeforeP->next; Position AfterP = P->next; P->next = AfterP->next; BeforeP->next = AfterP; AfterP->next = P; P->next->last = P;//注意这行！不能用AfterP->last，因为P和AfterP的位置改变 P->last = AfterP; AfterP->last =...