循环列表
- 约瑟夫环问题
已知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所指的地址优化为同一个地方
}
- 申请方式和申请效率
- 栈：系统自动分配。速度较快
- 堆：程序员自己申请，并指明大小。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
红黑树的性质
- 节点时红色或者黑色的
- 根节点是红色的
- Nil节点是黑色的
- 每个红节点的左子节点和右子节点必定是黑色的
- Nil节点在任意位置黑神东都相等
