数据结构与算法知识梳理

经典题：如何用两个栈实现队列的功能？
二叉树的遍历

（1）前序遍历：根节点 -> 左子树所有节点 -> 右子树所有节点。（子树同样采用前序遍历）

（2）中序遍历：左子树所有节点 -> 根节点 -> 右子树所有节点。（子树同样采用中序遍历）

（3）后序遍历：左子树所有节点 -> 右子树所有节点 -> 根节点。（子树同样采用后序遍历）
排序二叉树（二叉查找树）

特点：

（1）左子树节点全部小于根节点的值，右子树节点全部大于根节点的值；

（2）没有键值相等的节点；

（3）子树也是排序二叉树。
平衡二叉树：节点左子树的高度与右子树的高度相差不超过 1

插入新数据可能导致二叉树不平衡，无法得到比链表更高的效率，因此需要平衡算法。当树很大的时候平衡算法很复杂。
排序算法：冒泡排序、选择排序、快速排序等
查找算法：二分查找、哈希查找等

二分算法查找效率很高 log2(n)，但必须保证整个数据在内存空间是连续的，当删除一个数据时，需要把后面的数据都往前挪一个位置，当数据多的时候比较消耗CPU。所以，二分算法适合那些不需要经常增删改的数据，比如全国行政区划列表。而哈希算法适合那些经常增删改的数据，对哈希表操作类似于对链表进行操作，虽然其效率比二分差，但总体来说还是不错的。
异或操作交换两个变量的数据：
```
a[i] = a[i] ^ a[i+1];
a[i+1] = a[i] ^ a[i+1];
a[i] = a[i] ^ a[i+1];
```
但要注意，如果两个变量值相等则不能使用此方法，因为异或会得到0.

当然，交换变量值也可以用以下代码实现：
```
a = a + b;
b = a - b;
a = a - b;
```
但是，这种做法有个致命缺陷，就是越界问题。软件工程师在使用加减乘除时要时刻注意是否存在越界问题。
用<<,>>,|,&实现一个 WORD(2 个字节)的高低位交换。

(w >> 8) | (w << 8), 要求w是无符号的。
请定义一个宏，比较两个数a、b的大小，不能使用大于、小于、if语句。

＃define max(a,b) ((((a)-(b))&&(1<<31))?(b):(a))

参考文章
字节对齐
```
typedef struct employee{
    char sex;
    int length;
    char name[10];
} em_st;
```
请问sizeof(em_st)的值是多少？很多人会回答15，其实并不是。

在定义的数据结构中，如果出现了三种基本的数据类型 char, short int , int ,我们就以占用内存最大的那个作为字节对齐的方式。比如只有char、short int时，就以2字节对齐。只有char，就以1字节对齐。

结构成员变量中的位

有时候为了节省空间，结构体中的成员变量是按位操作的，比如

typedef struct test{
    char a:5;   // 第一字节的前5位
    char b:3;   // 第一字节的后3位
    char c:8;   // 第二字节的前8位
    char d:2;   // 第三字节的前2位
    char e:6;
    char f:7;
    char g:1;
} test_em;

IP地址就可以采用这种形式来定义，比字符串更省空间。

数据库(Database)是按照数据结构来组织、存储和管理数据的仓库，它产生于距今六十多年前，随着信息技术和市场的发展，特别是二十世纪九十年代以后，数据管理不再仅仅是存储和管理数据，而转变成用户所需要的各种数据管理的方式。
索引的类型:

(1) 唯一索引

(2) 非唯一索引

(3) 主键索引

(4) 聚集索引
主键与索引的区别:

(1) 主键一般在创建表的时候指定，而索引可以在任何时候创建；

(2) 一个表只能有一个主键，但可以有多个索引；

(3) 主键也是一种索引，但索引不是主键;

(4) 索引可以创建也可以删除。

参考资料：MySql索引详解大全、C语言操作MySql库函数

反转链表

可理解为在head左右有分别以pre和next为头节点的两个子链表。

#include<stdio.h>
struct ListNode * reverseList(struct ListNode *head)
{
        struct ListNode* pre=NULL;
        struct ListNode* next=NULL;
        while(head!=NULL){
            next=head->next;
            head->next=pre;
            pre=head;
            head=next;
        }
        return pre;
}

链表的宏遍历
假设现有一个单向的链表,但是只知道只有一个指向该节点的指针 p,并且假设这个节点不是尾节点,试编程实现删除此节点。

O(1)的办法:用 p 指向的节点的下一节点的值替换 p 指向的节点的值,然后删除 p 指向的节点的下一节点。
KMP算法中next表的构造（看前缀集合和后缀集合的交集的字符数）
Huffman树的构造
Hamming Weight的算法分析

面试数据结构算法