数据结构基础

循环列表

1. 约瑟夫环问题

已知n个人（以编号1，2，3，...，n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从k开始报数，数到m的那个人又出列；一词重复下去。直到圆桌的人全部出列。试用C++编程实现

核心步骤：

• 建立一个具有n个链节点、无头节点的循环链表
• 确定第一个报数人的位置
• 不断地从链表中删除链节点，直到链表为空

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#define ERROR 0
typedef struct LNode
{
    int data;
    struct LNode *link;
}Lnode, *LinkList;

void JOSEPHUS(int n, int k, int m)
{
    // p为当前节点，r为辅助节点，指向p的前区节点，list为头节点
    LinkList p, r, list, curr;

    // 构建循环链表
    p = (LinkList)malloc(sizeof(LNode));
    p->data = 0;
    p->link = p;
    curr = p;
    for (int i = 1; i<n; i++)
    {
        LinkList t = (LinkList)malloc(sizeof(LNode));
        t->data = i;
        t->link = curr->link;
        curr->link = t;
        curr = t;
    }

    // 把当前指针移动到第一个报数的人
    while(k--) r=p, p=p->link;
    while(n--)
    {
        for (int s=m-1;s--;r=p, p=p->link);
        r->link = p->link;
        printf("%d->", p->data);
        free(p);
        p = r->link;
    }
}

main()
{
    JOSEPHUS(13, 4, 4);
}

队列

编程实现队列的入队、出队操作

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
using namespace std;

typedef struct student
{
    int data;
    struct student *next;
}node;

typedef struct linkqueue
{
    node *first, *rear;
}queue;

//队列入队
queue *insert(queue *HQ, int x)
{
    node *s;
    s = (node *)malloc(sizeof(node));
    s->data = x;
    s->next = NULL;

    if(HQ->rear==NULL)
    {
        HQ->first = s;
        HQ->rear = s;
    }
    else
    {
        HQ->rear->next = s;
    }
    return HQ;
}

// 队列出队
queue *del(queue *HQ)
{
    int x;
    if (HQ->first==NULL)
    {
        printf("\n 溢出");
    }
    else
    {
        x = HQ->first->data;
        if(HQ->first==HQ->rear)
        {
            HQ->first = NULL;
            HQ->rear = NULL;
        }
        else
        {
            HQ->first = HQ->first->next;
        }
        return HQ;
    }
}

栈

编程实现栈的入栈和出栈操作

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
using namespace std;

typedef struct student
{
    int data;
    struct student *next;
}node;

typedef struct stackqueue
{
    node *bottom, *top;
}queue;

//入栈
queue *push(queue *HQ, int x)
{
    node *s;
    s = (node *)malloc(sizeof(node));
    s->data = x;
    s->next = NULL;

    if(HQ->top==NULL)
    {
        HQ->bottom = s;
        HQ->top = s;
    }
    else
    {
        HQ->top->next = s;
    }
    return HQ;
}

// 出栈
queue *pop(queue *HQ)
{
    node *p; int x;
    if (HQ->bottom==NULL)
    {
        printf("\n 溢出");
    }
    else
    {
        x = HQ->top->data;
        p = HQ->bottom;
        if(HQ->top==HQ->bottom)
        {
            HQ->top = NULL;
            HQ->bottom = NULL;
        }
        else
        {
            while(p->next != HQ->top)
            {
                p = p->next;
            }
            HQ->top = p;
            hQ->top->next = NULL;
        }
        return HQ;
    }
}

堆和栈的区别

在C、C++编程中，经常需要操作的内存可分为以下几个类别：

• 栈区（stack）：由编译器自动分配和释放，存放函数的参数值，局部变量的值等，其操作方式类似于数据结构中的栈。
• 堆区（heap）：一般由程序员分配和释放，若程序员不释放，程序结束时间可能由操作系统回收。和数据结构中的堆是两码事，分配方式类似链表
• 全局区（静态区，static）:全局变量和静态变量存储是放在一块的，初始化的全局变量和静态变量是在一块区域，未初始化的全局变量和未初始化的静态变量是在相邻的另一块。程序结束后由系统释放。
• 文字常量区：常量字符串就是放在这里。程序结束后由系统释放。
• 程序代码区：存放函数体的二进制代码。

//main.cpp
Int a= 0;       //全局初始化区
Char *p1;   //全局未初始化区
main ()
{
    int b;  //栈
    char s[] = “abc”;   //栈
    char *p2;       //栈
    char *p3 = “123456”;        //123456在常量区，p3在栈
    static int c = 0;   //全局静态初始化区

    p1 = (char *)malloc(10);
    p2 = (char *)malloc(20);    // 分配得来的10和20字节的区域就在堆区
    strcpy(p1, “123456”);       //123456放在常量区，编译器可能会将它与p3所指的地址优化为同一个地方
}

1. 申请方式和申请效率

• 栈：系统自动分配。速度较快
• 堆：程序员自己申请，并指明大小。C中用malloc函数，C++中用new（一般较慢，容易产生内存碎片，不过用起来方便）

2.申请后系统响应

• 栈：只要剩余空间大于申请空间，系统就给内存，否则报栈溢出
• 堆：略复杂，查链表，找第一个大于申请大小的空间，分配。多余的重新放入空闲链表

树

1. 二叉树

• 遍历原则：前序遍历是根左右， 中序遍历是左根右，后序遍历是左右根。

2.二叉搜索树

• 特点：对于树中的每个节点X，它的左子树中所有节点的值都小于X，右子树中所有节点的值都大于X。
• 遍历：采取二叉链表作 为二叉搜索树的存储结构。中序遍历可以得到一个有序序列。插入时，不必移动其他节点，只需改动某个节点的指针，由空变为非空即可。搜索、插入、删除的复杂度等于树高，即O(log(N))
• 查找优势：查询最小节点，只需一直向左找到终止节点即可；查找最大，向右找到终止节点。

3.平衡二叉树

• 特点：它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1。左右子树都是一颗平衡二叉树。

4. 判断树相等

两个树相等，当且仅当RootA->data == RootB->data，而且左右子树对应相等或者互换后相等

int CompTree(TreeNode *tree1, TreeNode *tree2)
{
    bool isTree1Null = (tree1 == NULL);
    bool isTree2Null = (tree2 == NULL);
    // 其中一个为NULL，而另一个不为NULL，肯定不相等
    if (isTree1Null != isTree2Null)
        return 0;
    // 两个都为NULL，一定相等
    if (isTree1Null && isTree2Null)
        return 1;
    // 两个都不为NULL，如果data不等，一定不等
    if(tree1->data != tree2->data)
        return 0;
    //递归
    return (CompTree(tree1->left, tree2->left) & CompTree(tree1->right & tree2->right)) |
        (CompTree(tree1->left, tree2->right) & CompTree(tree1->right, tree2->left))
}

5.拓扑排序

有向图拓扑排序算法的基本步骤如下：

• 从图中选择一个入度为0的顶点，输出该节点；
• 从图中删除该顶点及其相关联的弧，调整被删除弧的弧头节点的入度(入度减1)
• 重复执行1、2直到所有顶点均输出

6. Trie树

又称单词查找树、字典树，是一种哈希树的变种，是一种用于快速检索的多叉树结构。典型应用于统计和排序大量的字符串，所以经常被搜索引擎系统用于文本词频统计。

• 优点：最大限度的减少无谓的字符串比较，查询效率比哈希表高。
• 思想：空间换时间，利用字符串比较的公共前缀来降低查询时间的开销，以提高效率的目的。

7. 哈夫曼编码

8.四叉树

一个包含n个节点的四叉树，每一个节点都有4个指向孩子节点的指针，这个四叉树有多少个空指针？
解析：n个节点有n-1非空指针，其余皆为空指针。4*n-(n-1)=3*n+1

9. 红黑树

红黑树与AVL的比较？

• AVL是严格平衡树，因此在增加或删除节点时，根据不同的情况，旋转的次数要比红黑树多
• 红黑是用非严格的平衡换区增删节点时候的旋转次数的降低
• 如果搜索次数远大于插入和删除，那么选择AVL；如果搜索、插入、删除次数几乎差不多，应该选择RB

红黑树的性质

1. 节点时红色或者黑色的
2. 根节点是红色的
3. Nil节点是黑色的
4. 每个红节点的左子节点和右子节点必定是黑色的
5. Nil节点在任意位置黑神东都相等