链表
单链表
-
单链表的建立/测长/打印
-
单链表的删除：找上一个节点指针
-
单链表的插入：找上一个节点指针
-
单链表的排序：冒泡/选择/快排
-
单链表的逆置：三指针四步法：pPrev指向上一个节点，pCurr指向当前节点，pNext保存下一个节点。
pNext = pCurr->next;
pCurr-> = pPrev;
pPrev = pCurr;
pCurr = pNext;
双链表
与单链表区别不大。多了一个指向前一节点的指针ListNode * pre。
循环链表
链表的尾元素的next指针指向队首元素。
队列 vs. 栈
队列：先进先出
栈：后进先出
用两个栈实现一个队列的功能
我们有两个栈stack1和stack2。
插入的时候都是直接用stack1.push(element)。
删除的时候：当stack2中不为空时，stack2中栈顶的元素就是最先进入队列的元素，可以弹出。如果stack2为空，我们就把stack1中的元素逐个弹出并压入stack2，因为先进入stack1的元素在栈底，经过弹出并压入之后处于stack2的栈顶，可以直接弹出。
树，图，哈希表
二叉树
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
二叉搜索树
对于树中的每个节点，它的左子树的所有节点的值都小于该节点值，它的右子树的所有节点的值都大于该节点的值。
每次插入的新节点都是新的叶子节点。
搜索，插入，删除的复杂度等于树高，O(log(n))。
平衡二叉树
它的左右两棵子树的高度差的绝对值不超过1.
Trie树
又称单词查找树，字典树，是一种哈希树的变种，是一种用于快速检索的多叉树结构。
典型应用是用于统计和排序大量的字符串，所以经常被搜索引擎系统用于文本词频统计。
排序算法
| 排序算法 | 最好情况 | 最差情况 | 平均情况 | 辅助空间 | 稳定性 | 类别 |
|---|---|---|---|---|---|---|
| 插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | 插入类 |
| 希尔排序 | O(n^1.3) | O(n^2) | O(nlog(n)) | O(1) | 不稳定 | 插入类 |
| 选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 | 选择类 |
| 堆排序 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(1) | 不稳定 | 选择类 |
| 冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 稳定 | 交换类 |
| 快速排序 | O(nlog(n)) | O(n^2) | O(nlog(n)) | O(logn) ~ O(n) | 不稳定 | 交换类 |
| 归并排序 | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(1) | 稳定 | 归并类 |
字符串
#include <cstring>
整数和字符串转化
-
itoa：加’0’，再逆序
-
atoi：减’0’，再乘10
都要考虑正负号
字符数组和strcpy
char * strcpy(char * strDest, const char * strSrc)
{
assert(strSrc != NULL);
char * address = strDest;
while(*strSrc != '\0')
*strDest++ = *strSrc++;
return address;
}
数组初始化和数组越界
字符数组的初始化要求最后一个字符必须是’\0’
C++ String类
class String
{
public:
String(const char *str = NULL);// 普通构造函数
String(const String &other);// 拷贝构造函数
~String(void);// 析构函数
String & operator = (const String &other);// 赋值函数
private:
char *m_data;// 用于保存字符串
};
下面是上面四个函数的具体实现
// 普通构造函数
String::String(const char *str)
{
if (str == NULL)
{
m_data = new char[1];// 得分点：对空字符串自动申请存放结束标志'\0'的，加分点：对m_data加NULL判断
*m_data = '\0';
}
else
{
int length = strlen(str);
m_data = new char[length + 1];// 若能加 NULL 判断则更好
strcpy(m_data, str);
}
}
// String的析构函数
String::~String(void)
{
delete[] m_data; // 或delete m_data;
}
// 拷贝构造函数
String::String(const String &other)// 得分点：输入参数为const型
{
int length = strlen(other.m_data);
m_data = new char[length + 1];//加分点：对m_data加NULL判断
strcpy(m_data, other.m_data);
}
// 重载+
String String::operator+(const String &str) const //重载+
{
String newString;
newString.length = length + str.size();
newString.data = new char[newString.length + 1];
strcpy(newString.data, data);
strcat(newString.data, str.data);
return newString;
}
// 赋值函数
String & String::operator = (const String &other) // 得分点：输入参数为const型
{
if (this == &other)//得分点：检查自赋值
return *this;
if (m_data)
delete[] m_data;//得分点：释放原有的内存资源
int length = strlen(other.m_data);
m_data = new char[length + 1];//加分点：对m_data加NULL判断
strcpy(m_data, other.m_data);
return *this;//得分点：返回本对象的引用
}