发表于 | 分类于 ，

循环语句

循环类型 描述
while 循环 当给定条件为真时，重复语句或语句组。它会在执行循环主体之前测试条件。
for 循环 多次执行一个语句序列，简化管理循环变量的代码。
do…while 循环 除了它是在循环主体结尾测试条件外，其他与 while 语句类似。
嵌套循环 您可以在 while、for 或 do..while 循环内使用一个或多个循环。
阅读全文 »

发表于 | 分类于 ，
运算符 描述 实例
+ 把两个操作数相加 A + B 将得到 30
- 从第一个操作数中减去第二个操作数 A - B 将得到 -10
* 把两个操作数相乘 A * B 将得到 200
/ 分子除以分母 B / A 将得到 2
% 取模运算符，整除后的余数 B % A 将得到 0
++ 自增运算符，整数值增加 1 A++ 将得到 11
— 自减运算符，整数值减少 1 A— 将得到 9
== 检查两个操作数的值是否相等，如果相等则条件为真。 (A == B) 不为真。
!= 检查两个操作数的值是否相等，如果不相等则条件为真。 (A != B) 为真。
> 检查左操作数的值是否大于右操作数的值，如果是则条件为真。 (A > B) 不为真。
< 检查左操作数的值是否小于右操作数的值，如果是则条件为真。 (A < B) 为真。
>= 检查左操作数的值是否大于或等于右操作数的值，如果是则条件为真。 (A >= B) 不为真。
<= 检查左操作数的值是否小于或等于右操作数的值，如果是则条件为真。 (A <= B) 为真。
&& 称为逻辑与运算符。如果两个操作数都非零，则条件为真。 (A && B) 为假。
|| 称为逻辑或运算符。如果两个操作数中有任意一个非零，则条件为真。 (A || B) 为真。
! 称为逻辑非运算符。用来逆转操作数的逻辑状态。如果条件为真则逻辑非运算符将使其为假。 !(A && B) 为真。
& 如果同时存在于两个操作数中，二进制 AND 运算符复制一位到结果中。 (A & B) 将得到 12，即为 0000 1100
| 如果存在于任一操作数中，二进制 OR 运算符复制一位到结果中。 (A | B) 将得到 61，即为 0011 1101
^ 如果存在于其中一个操作数中但不同时存在于两个操作数中，二进制异或运算符复制一位到结果中。 (A ^ B) 将得到 49，即为 0011 0001
~ 二进制补码运算符是一元运算符，具有”翻转”位效果，即0变成1，1变成0。 (~A ) 将得到 -61，即为 1100 0011，一个有符号二进制数的补码形式。
<< 二进制左移运算符。左操作数的值向左移动右操作数指定的位数。 A << 2 将得到 240，即为 1111 0000
>> 二进制右移运算符。左操作数的值向右移动右操作数指定的位数。 A >> 2 将得到 15，即为 0000 1111
= 简单的赋值运算符，把右边操作数的值赋给左边操作数 C = A + B 将把 A + B 的值赋给 C
+= 加且赋值运算符，把右边操作数加上左边操作数的结果赋值给左边操作数 C += A 相当于 C = C + A
-= 减且赋值运算符，把左边操作数减去右边操作数的结果赋值给左边操作数 C -= A 相当于 C = C - A
*= 乘且赋值运算符，把右边操作数乘以左边操作数的结果赋值给左边操作数 C = A 相当于 C = C A
/= 除且赋值运算符，把左边操作数除以右边操作数的结果赋值给左边操作数 C /= A 相当于 C = C / A
%= 求模且赋值运算符，求两个操作数的模赋值给左边操作数 C %= A 相当于 C = C % A
<<= 左移且赋值运算符 C <<= 2 等同于 C = C << 2
>>= 右移且赋值运算符 C >>= 2 等同于 C = C >> 2
&= 按位与且赋值运算符 C &= 2 等同于 C = C & 2
^= 按位异或且赋值运算符 C ^= 2 等同于 C = C ^ 2
|= 按位或且赋值运算符 C |= 2 等同于 C = C | 2
阅读全文 »

发表于 | 分类于 ，

关键字

asm else new this
auto enum operator throw
bool explicit private true
break export protected try
case extern public typedef
catch false register typeid
char float reinterpret_cast typename
class for return union
const friend short unsigned
const_cast goto signed using
continue if sizeof virtual
default inline static void
delete int static_cast volatile
do long struct wchar_t
double mutable switch while
dynamic_cast namespace template
阅读全文 »

发表于 | 分类于 ，

使用 Visual Studio (Graphical Interface) 编译

1、下载及安装 Visual Studio Community 2015。
2、打开 Visual Studio Community
3、点击 File -> New -> Project

阅读全文 »

发表于 | 分类于

定义

将单链表中终端结点的指针端有空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表成为单循环链表，简称单链表(circle linked list)

但是循环链表进过改造，不用头指针，而是用指向终端结点的尾指针来表示循环链表，这样查找开始结点和终端结点都很方便。


阅读全文 »

发表于 | 分类于

定义

数据域：存储数据元素信息的域，指针域：存储直接后继位置的域。指针域中存储的信息成为指针或链。这两部分信息组成数据元素成为存储映像，成为结点(Node)。
数据域|指针域
-|-
data|next

头结点与头指针

  • 头结点
    头结点是加在单链表之前附设的一个头结点。头结点的数据域一般不存储任何信息，也可以存放一些关于线性表的长度的附加信息。
    -头指针
    头指针是指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
阅读全文 »

发表于 | 分类于

定义

顺序存储结构是指用一段地址连续的存储单元依次存储线性表的数据元素。通常都用数组来描述数据结构中的顺序存储结构。

阅读全文 »

发表于 | 分类于

一、绪论

二、抽象数据类型ADT

1
2
3
4
5
ADT 抽象数据类型名称{
      数据对象(Data):<数据对象的定义>
      数据关系      :<数据关系的定义>
      基本操作(Operation):<基本操作的定义>
}ADT抽象数据类型名称

线性表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
ADT 线性表（List）

Data
    线性表的数据对象集合为{a1,a2,…,an}，每个元素的类型均为DataType。
    其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素an外，每一个元素有且只有一个直接后继元素。
    数据元素之间的关系是一对一的关系。

Operation
    InitList(): 初始化操作，建立一个空的线性表L。
    DestroyList():线性表已经存在，释放该线性表所占用的存储空间
    ClearList(): 线性表已经存在，重置线性表为空表，将线性表清空。
    ListLength(): 线性表已经存在返回线性表L的元素个数。
    GetElem(): 求线性表L中的第i个位置元素值。
        初始条件：线性表已存在
        输入参数：元素序号i，1<=i<=ListLength(L)
        实现功能：取线性表中序号为i的元素值
        输出数据：如果序号不合理，则给出错误信息；否则返回序号为i的元素序号值
        操作结果：线性表不变
    LocateElem(): 在线性表L中查找与给定值x相等的元素，如果查找成功，返回线性表中第1个值等于x的元素序号;否则返回0。
        初始条件：线性表已存在
        输入参数：元素x
        实现功能：查找线性表中第1个值等于x的元素
        输出数据：如果查找成功，返回线性表中第1个值等于x的元素序号；否则返回0
        操作结果：线性表不变
    ListInsert(): 在线性表L中第i个位置插入新元素e。
        初始条件：线性表已存在
        输入参数：插入位置i,1<=i<=ListLength(L)+1,ListLength(L)表示插入前的表长;待插入元素x
        实现功能：插入x到线性表的第i个位置上
        输出数据：如果插入不成功，则给出错误信息
        操作结果：当插入成功时，线性表中增加了一个元素x，且表长增1
    ListDelete(): 删除线性表L中第i个位置元素，并用e返回其值。
        初始条件：线性表已存在
        输入参数：删除位置i,1<=i<=ListLength(L)+1,ListLength(L)表示插入前的表长
        实现功能：删除线性表中的第i个元素
        输出数据：如果删除不成功，则给出错误信息。否则返回第i个元素值
        操作结果：当删除成功时，线性表中减少了一个元素，且表长减1
endADT

顺序表
单链表
静态链表.md 没有审核代码
循环链表
双向链表.md 没有审核代码

特殊线性表-栈、队列和串

栈：后进先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ADT Stack{
    Data：
        栈中元素具有相同类型及后进先出特性，相邻元素具有前驱和后继关系
    Operation：
        InitStack()：初始化栈，构造一个空栈
        DestroyStack()：销毁栈，释放栈所占用的存储空间
        StackLength()：求栈的长度
        GetTop()：
              实现功能：读取当前栈顶元素
              输出数据：如果栈空，则给出错误信息；否则返回当前栈顶元素值
        Push()：
              输入参数：待插入元素
              实现功能：插入元素到栈顶
              输出数据：如果插入不成功，则给出错误信息
              操作结果：当插入成功时，栈顶增加了一个元素
        Pop()：
              输入参数：无
              实现功能：删除栈顶元素
              输出数据：如果栈为空，则给出错误信息；否则返回栈顶元素
              操作结果：当删除成功时，栈顶减少了一个元素
}

栈的顺序储结构栈.md
栈的链式存储结构.md

队列：先进先出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ADT Queue{
    Data：
        队列中元素具有相同类型及先进先出特性，相邻元素具有前驱和后继关系
    Operation：
        InitQueue()：初始化队列，构造一个空队列
        DestroyQueue()：销毁队列，释放队列所占用的存储空间
        QueueLength()：求队列的长度
        GetHead()：
              实现功能：读取当前队列头元素
              输出数据：如果队列空，则给出错误信息；否则返回当前队列头元素值
       EnQueue()：
              输入参数：待插入元素
              实现功能：插入元素到队列尾
              输出数据：如果插入不成功，则给出错误信息
              操作结果：当插入成功时，队列尾增加了一个元素
       DeQueue()：
              输入参数：无
              实现功能：删除队列头元素
              输出数据：如果队列为空，则给出错误信息；否则返回队列头元素
              操作结果：当删除成功时，队列尾减少了一个元素
}

队列的顺序存储结构.md
队列链式存储结构.md

串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ADT 串(string)
{
    Data
        串中元素仅由一个字符组成,相邻元素具有前驱和后继关系.

    Operation
        StrAssign(T,*chars):生成一个其值等于字符常量chars的串T.
        StrCopy(T,S):串S存在,由S复制得到T.
        ClearString(S):串S存在,将串清空.
        StringEmpty(S):  若串为空,返回true,否则返回false.
        StrLentgth(S) :返回串S的元素个数,即串的长度.
        StrCompare(S,L):比较S和T,若S>T,返回>0,S==T返回0, S<T返回<0
        SubString(Sub, S, pos, len): 串S存在,1<=pos<=StrLentgth(S),且 0<=len<=StrLentgth(S)-pos+1,用Sub返回串S的第pos个起,长度为len的子串.
        Index(S,T,pos)
        Replace(S,T,V)串S,T,V存在,T是非空串,用V替换S中出现的所有与T相等的不重叠的子串.
        StrInsert(S,T,pos): 在串S的第pos个字符之前插入串T.
        StrDelete(S,pos,len):从串S中删除第pos个字符起的长度为len的子串.
}endADT

串的顺序存储结构.md

数组和广义表

数组：由一组类型相同、下标不同的变量构成。

根据数组中存储的数据元素之间的逻辑关系，可以将数组分为 : 一维数组、二维数组、…、n维数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ADT Array {

Data:

    相同类型元素有序集合，每个元素受n(n>=1)个线性关系的约束并由一组下标唯一标识

Operation:

    InitArray():  //构造一个空数组,数组的维数和各维的长度

    DestroyArray()：//销毁数组,释放数组所占用的存储空间

    GetValue(A,&e,index1,…,indexn) //求值函数,求某个下标元素的值

        初始条件:A是维数组,e为元素变量,随后是n个下标值.

        操作结果:若各下标不超界,则e赋值为所指定的A的元素值,并返回OK.

    Assign(&A,e,index1,…,indexn)//赋值函数,给下具体的下标的元素赋值

        初始条件:A是n维数组,e为元素变量,随后是n个下标值.

        操作结果:若下标不超界,则将e的值赋给所指定的A的元素,并返回OK.

}ADT Array

树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ADT Tree{
    Data:
        树
    Operation：
        InitTree(&T):构造空树
        DestroyTree(&T)：销毁树
        CreateTree(&T,dfinition):
            初始条件:defination给出树T的定义
            操作结果：按defination构造树T
        ClearTree(&T):将树清为空树
        TreeEmpty(T):若树为空树，则返回TRUE,否则FALSE
        TreeDepth(T)：返回树的深度
        Root(T):返回T的根
        Value(T,node):树T存在，node是T中的某一个结点，返回node的值
        Assign(T,node,value):树T存在，node是T中的某一个结点，结点node赋值为value
        Parent(T,node):若node是T的非根结点,返回它的双亲，否则函数值为空
        LeftChild(T,node):若node是T的非叶子结点,返回它的最左孩子，否则函数值为空
        RightSiblingChild(T,node):若node右兄弟,返回它的右兄弟，否则函数值为空
        InsertChild(&T,&p,i,c):树T存在，p指向是T中某一个结点，插入c为T中p所指节点的第i颗子树
        DeleteChild(&T,&p,i,c):树T存在，p指向是T中某一个结点，删除T中p所指节点的第i颗子树
        TraveseTree():遍历树
}ADT Tree

树与森林.md
树的存储结构.md java版
二叉树.md
线索二叉树.md
哈赫夫曼树.md

图

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
ADT 图(Graph)
Data
    顶点的有穷非空集合和边的集合。
Operation
    CreateGraph(*G, V, VR): 按照顶点集V和边弧集VR的定义构造图G。
    DestroyGraph(*G):      图G存在则销毁。
    LocateVex(G, u):        若图G中存在顶点u，则返回图中的位置。
    GetVex(G, v):          返回图G中顶点v的值。
    PutVex(G, v, value):    将图G中顶点v赋值value。
    FirstAdjVex(G, *v):    返回顶点v的一个邻接顶点，若顶点在G中无邻接顶点返回空。
    NextAdjVex(G, v, *w):  返回顶点v相对于顶点w的下一个邻接顶点，
                            若w是v的最后一个邻接点则返回“空”。
    InsertVex(*G, v):      在图G中增添新顶点v。
    DeleteVex(*G, v):      删除图G中顶点v及其相关的弧。
    InsertArc(*G, v, w):    在图G中增添弧<v,w>，若G是无向图，还需要增添对称弧<w,v>。
    DeleteArc(*G, v, w):    在图G中删除弧<v,w>，若G是无向图，则还删除对称弧<w,v>。
    DFSTraverse(G):        对图G中进行深度优先遍历，在遍历过程对每个顶点调用。
    HFSTraverse(G):        对图G中进行广度优先遍历，在遍历过程对每个顶点调用。
endADT

图的术语与定义.md
图的抽象结构与存储结构.md(无向图采用多重邻接表，有向图采用十字链表)
图的遍历.md
最小生成树.md
最短路径问题.md
拓扑排序.md
关键路径.md

区别.md

查找

  • 静态查找(Static Search Table)：只作查找操作的查找表。主要操作有：
    • 查询某个“特定的”数据元素是否在查找表中。
    • 检索某个“特定的”数据元素和各种属性。
      线性表的查找.md
  • 动态查找表(Dynamic Search Table)：在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个特定的数据元素。主要操作有两个：
    • 查找时插入数据元素；
    • 查找时删除数据元素。
      查找树.md
      平衡二叉树.md
      2-3树.md
      B树
      红黑树
  • 哈希表
    散列查找.md

排序

  • 排序基础代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    #include <stdio.h>
    #include <stdlib.h>

    #define MAXSIZE 100
    #define TRUE 1
    #define FALSE 0

    typedef struct {

        int r[MAXSIZE + 1]; // 用于存储要排序的数组， r[0]用作哨兵或者临时变量
        int length;  // 用于记录顺序表的长度
    }SqList;

    /**
    * 交换数组r中下标i和j的值
    */
    void swap(SqList *L, int i, int j){
        int temp = L->r[i];
        L->r[i] = L->r[j];
        L->r[j] = temp;
    }

插入排序.md (直接插入排序，希尔排序。希尔排序根据直接插入排序而来)
选择排序.md
交换排序.md
归并排序.md(从0开始)

排序代码集合(从0开始).md

性能比较

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
简单选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 稳定
直接插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
希尔排序 $O(nlogn)~O(n^2)$ $O(n^{1.3})$ $O(n^2)$ $O(1)$ 不稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ 不稳定
归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ 稳定
快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(nlogn)~O(n)$ 不稳定

附录

图-邻接矩阵代码.md
邻接表代码.md
邻接矩阵与邻接表深度遍历.md
邻接矩阵与邻接表的广度优先遍历算法.md
普里姆（Prim）算法代码.md
克鲁斯卡尔（Kruskal）算法代码.md
迪杰斯特拉（Dijkstra）算法代码.md