数据结构之算法浅谈

算法：

1.确定性，有穷性，可行性，输入和输出性

2.设计范式

贪心法，分治法，动态规划法，线性规划法，搜索和枚举法。

3：实现方法

顺序执行，并行执行(包括分布式计算),递归算法和迭代算法

顺序执行

求数组当中元素最大值：

关于循环：

优美的递归：二叉排序树的搜索

尾递归是尾调用的一种特殊情况，也是递归结构的一种特殊形式。

编译器一般都可以对尾递归进行优化(尾调用消除技术)

直接利用当前函数的栈帧，将尾调用处理成循环的形式

尾调用：是指一个函数里的最后一个动作是调用一个函数的情形，这个函数调用的返回值直接被当前函数作为返回值

递归结构使用的函数递归调用，会增加任务的栈空间使用，用递归方法解决问题的规模受系统栈空间的约束，

除此之外函数调用时的参数入栈和出栈也会降低算法的效率

分支和跳转

闰年： 

过长的多分支结构常被视为软件当中的不良结构。违背了OCP原则(开放，封闭原则)

环形队列demo:一致性处理，包括函数表

对队尾指针移动的处理：rear = (rear+1) % N

如果不采取对N取模，则每次指针移动时都要做是否已经达到表尾的判断处理

算法实现与数据结构

逻辑结构：

线性结构，关联结构（集合，映射）,树形结构，图形结构

线性表：

数组，链表，栈，队列是四种最常见的线性表

数组：

访问方式：下标访问

查找无开销，插入和删除需要大量移动元素。

查找元素：O(n) if 数组有序  二分查找 O(logn)

链表：

适用于线性表的长度不确定的场合。

两个域构成：数据域 and 指针域

易于插入和删除，查找困难。

优势：链表长度可以动态增长，比数组具有很大的优势

表头结点的好处：

1：无论链表是否为空表，始终有一个能标识链表的头节点，可以用一致性处理空链表和非空链表

2：对链表进行插入，删除和遍历操作时，不需要对数据元素的首节点和中间节点做差异化处理，对每个结点的操作可以做到一致性