文章目录
- 一、单链表的结构决定只能出栈，入栈
- 1.链表的结构
- 2.链表与数组的区别
- 3.单链表所有基本操作代码
- （1）链表的插入
- （2）链表的查找
- （3）链表的删除
- （3）遍历整个链表
- （4）销毁整个链表
- 4.习题
- 5.C++NULL指针
- 二、双向链表结构决定可以出队和入队
- 1.在上面的单项链表上改改，得到双向链表
- 2.改进双向链表：新增界定表头和表尾，不保存数据的两个节点
- 三、链表实现环形队列：把双向链表改改即可
- 四、静态链表
- 五、二叉树
- 1.二叉树的基本概念
- 2.二叉树的递归定义
- 3.二叉树的遍历方法：前序、中序、后序
- 4.依据前序和中序遍历结果构造二叉树
- 5.二叉树的递归定义
- 六、排序二叉树
- 七、哈希表
- 八、 各种数据结构的search、 insert和delete操作在平均情况下的时间复杂度比较
一、单链表的结构决定只能出栈，入栈
1.链表的结构
结构体的递归定义
stuct s{
char data[6];
struct s *next;
};下图示意了由几个 struct s 结构体组成的链表，这些结构体称为链表的节点（Node）
- head 指针是链表的头指针，指向第一个节点。
- 每个节点的 next 指针域指向下一个节点。
- 最后一个节点的 next 指针域为 NULL ，在图中用0表示。
2.链表与数组的区别
（1）每个链表有一个头指针，通过头指针可以找到第一个节点，每个节点都可以通过指针域找到它的后继，最后一个节点的指针域为 NULL ，表示没有后继。
（2）数组在内存中是连续存放的，而链表在内存中的布局是不规则的，我们知道访问某个数组元素 b[n] 时可以通过 基地址+n×每个元素的字节数 得到它地址，或者说数组支持随机访问。
而链表是不支持随机访问的，只能通过前一个元素的指针域得知后一个元素的地址，因此只能从头指针开始顺序访问各节点。
3.单链表所有基本操作代码
（a）注意链表的数据结构怎么定义的
/* linkedlist.h */
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
//注意链表结构的定义
typedef struct node *link;
struct node {
unsigned char item;
link next;
};
link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void delete(link p);
void traverse(void (*visit)(link));
void destroy(void);
void push(link p);
link pop(void);
#endif/* linkedlist.c */
#include <stdlib.h>
#include "linkedlist.h"
static link head = NULL;//在初始化时把头指针 head 初始化为 NULL ，表示空链表
link make_node(unsigned char item)
{
link p = malloc(sizeof *p);
p->item = item;
p->next = NULL;
return p;
}
void free_node(link p)
{
free(p);
}
link search(unsigned char key)
{
link p;
for (p = head; p; p = p->next) //for (p = head->next; p; p = p->next)我觉得更好
if (p->item == key)
return p;
return NULL;
}
void insert(link p)
{
p->next = head; //p->next=head->next;更好
head = p;//head->next=p;更好
}
void delete(link p)
{
link pre;
if (p == head) {
head = p->next;
return;
}
for (pre = head; pre; pre = pre->next) //for (pre = head->next; pre; pre = pre->next)
if (pre->next == p) {
pre->next = p->next;
return;
}
}
void traverse(void (*visit)(link))
{
link p;
for (p = head; p; p = p->next)//for (p = head->; p; p = p->next)更好
visit(p);
}
void destroy(void)
{
link q, p = head; //p=head->next更好，我觉得
head = NULL;
while (p) {
q = p;
p = p->next;
free_node(q);
}
}
void push(link p)
{
insert(p);
}
link pop(void)
{
if (head == NULL)
return NULL;
else {
link p = head;
head = head->next;
return p;
}
}/* main.c */
#include <stdio.h>
#include "linkedlist.h"
void print_item(link p)
{
printf("%d\n", p->item);
}
int main(void)
{
link p = make_node(10);
insert(p);
p = make_node(5);
insert(p);
p = make_node(90);
insert(p);
p = search(5);
delete(p);
free_node(p);
traverse(print_item);
destroy();
p = make_node(100);
push(p);
p = make_node(200);
push(p);
p = make_node(250);
push(p);
while (p = pop()) {
print_item(p);
free_node(p);
}
return 0;
}（1）链表的插入
（a）代码解释如下
在初始化时把头指针 head 初始化为 NULL ，表示空链表。
然后 main 函数调用 make_node 创建几个节点，分别调用 insert 插入到链表中。
void insert(link p)
{
p->next = head; //p->next=head->next;更好
head = p;//head->next=p;更好
}
//写法：指针=节点，因为后继指针指向下一个节点嘛,这样去写，这里的head指针为NULL，所以这样也可以（b）链表的操作图例
（2）链表的查找
main 函数调用 search 在链表中查找某个节点，如果找到就返回指向该节点的指针，找不到就返回 NULL 。
search 函数其实也隐含了对于空链表这种特殊情况的处理，如果是空链表则循环体一次都不执行，直接返回 NULL 。
link search(unsigned char key)
{
link p;
for (p = head; p; p = p->next) //for (p = head->next; p; p = p->next)我觉得更好
if (p->item == key)
return p;
return NULL;
}
//看到节点=新节点，表示：新下个节点赋值给上个节点（功能：遍历节点需要），注意与指针=节点的区别（功能：把节点连接起来）。ps：主要看左边被赋值的类型！！！
//p = p->next当成下个节点赋值给当前的节点。得到新节点。（3）链表的删除
（a）代码解释如下
main 函数调用 delete 从链表中摘除用 search 找到的节点，最后调用 free_node 释放它的存储空间。
void delete(link p)
{
link pre;
if (p == head) {
head = p->next;
return;
}
for (pre = head; pre; pre = pre->next) //for (pre = head->next; pre; pre = pre->next)更好
if (pre->next == p) {
pre->next = p->next;
return;
}
}
//head = p->next让p->next成为新的head（b）链表的删除操作图例
（c）但是，我感觉你将节点p删除后，前面的指针怎么指向后面的节点呢？？感觉写的有点问题（黄色标记处）
能不能把上面的特殊情况转化为一般情况呢？可以把 delete 函数改成这样：
（3）遍历整个链表
void traverse(void (*visit)(link))
{
link p;
for (p = head; p; p = p->next)//for (p = head->; p; p = p->next)更好
visit(p);
}（4）销毁整个链表
void destroy(void)
{
link q, p = head; //p=head->next更好，我觉得
head = NULL;
while (p) {
q = p;
p = p->next;
free_node(q);
}
//销毁的话，一定要新建一个节点，link q4.习题
（1）
- 使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
- 数据的存取往往要在不同的排列顺序中转换，而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。
（2）
（a）非递归方式
void reverse(void)
{
link p=head->next,q=p->next;
while (p)
{
p->next=head;//指针操作
p=q;//剩下的都是节点操作
q=q->next;
}
delete(head);
insert(m);
}5.C++NULL指针
参考：https://www.runoob.com/cplusplus/cpp-null-pointers.html
在变量声明的时候，如果没有确切的地址可以赋值，为指针变量赋一个 NULL 值是一个良好的编程习惯。赋为 NULL 值的指针被称为空指针。
NULL 指针是一个定义在标准库中的值为零的常量。请看下面的程序：
#include <iostream>
using namespace std;
int main ()
{
int *ptr = NULL;
cout << "ptr 的值是 " << ptr ;
return 0;
}当上面的代码被编译和执行时，它会产生下列结果：
ptr 的值是 0
在大多数的操作系统上，程序不允许访问地址为 0 的内存，因为该内存是操作系统保留的。然而，内存地址 0 有特别重要的意义，它表明该指针不指向一个可访问的内存位置。但按照惯例，如果指针包含空值（零值），则假定它不指向任何东西。
如需检查一个空指针，您可以使用 if 语句，如下所示：
if(ptr) /* 如果 ptr 非空，则完成 */
if(!ptr) /* 如果 ptr 为空，则完成 */因此，如果所有未使用的指针都被赋予空值，同时避免使用空指针，就可以防止误用一个未初始化的指针。很多时候，未初始化的变量存有一些垃圾值，导致程序难以调试。
二、双向链表结构决定可以出队和入队
1.在上面的单项链表上改改，得到双向链表
（1）在 linkedlist.h 中修改链表节点的结构体定义
struct node {
unsigned char item;
link prev, next;
};（2）在 linkedlist.c 中修改 insert 和 delete 函数
void insert(link p)
{
p->next = head;
if (head)
head->prev = p;
head = p;
p->prev = NULL;
//下面这样写更好
//p->next=head->next;
//head->next=p;
//head->next->pre=p;
//p->pre=head;
//其它，特殊情况再特殊对待
}
void delete(link p)
{
if (p->prev)
p->prev->next = p->next;
else
head = p->next;
if (p->next)
p->next->prev = p->prev;
//p->pre->next=p->next;
//p-next-pre=p->pre;
//其它，特殊情况，再特殊对待
}
2.改进双向链表：新增界定表头和表尾，不保存数据的两个节点
（1）改后的代码如下
/* doublylinkedlist.h */
#ifndef DOUBLYLINKEDLIST_H
#define DOUBLYLINKEDLIST_H
typedef struct node *link;
struct node {
unsigned char item;
link prev, next;
};
link make_node(unsigned char item);
void free_node(link p);
link search(unsigned char key);
void insert(link p);
void delete(link p);
void traverse(void (*visit)(link));
void destroy(void);
void enqueue(link p);
link dequeue(void);
#endif#include "doublylinkedlist.h"
struct node tailsentinel;
struct node headsentinel = {0, NULL, &tailsentinel};//新添加的两个点，与单链表不同
struct node tailsentinel = {0, &headsentinel, NULL};//新添加的两个点，与单链表不同
static link head = &headsentinel;
static link tail = &tailsentinel;
link make_node(unsigned char item)
{
link p = malloc(sizeof *p);
p->item = item;
p->prev = p->next = NULL;//与单链表不同
return p;
}
void free_node(link p)
{
free(p);
}
link search(unsigned char key)
{
link p;
for (p = head->next; p != tail; p = p->next)//不同点
if (p->item == key)
return p;
return NULL;
}
void insert(link p)
{
p->next = head->next;
head->next->prev = p;
head->next = p;
p->prev = head;
/*我是这么写的
p->next=head->next;（1）
head->next=p;（2）
head->next->pre=p;（3）
p->pre=head;（4）
*/
}
void delete(link p)
{
p->prev->next = p->next;//和我想的一样
p->next->prev = p->prev;//和我想的一样
}
void traverse(void (*visit)(link))
{
link p;
for (p = head->next; p != tail; p = p->next)//与单链表不同
visit(p);
}
void destroy(void)
{
link q, p = head->next;//与单链表不同
head->next = tail;//与单链表不同
tail->prev = head;//与单链表不同
while (p != tail) {//与单链表不同
q = p;
p = p->next;
free_node(q);
}
}
void enqueue(link p)//入队
{
insert(p);
}
link dequeue(void)//出队，所以从队尾tail出队
{
if (tail->prev == head)
return NULL;
else {
link p = tail->prev;
delete(p);
return p;
}
}/* main.c */
#include <stdio.h>
#include "doublylinkedlist.h"
void print_item(link p)
{
printf("%d\n", p->item);
}
int main(void)
{
link p = make_node(10);
insert(p);
p = make_node(5);
insert(p);
p = make_node(90);
insert(p);
p = search(5);
delete(p);
free_node(p);
traverse(print_item);
destroy();
p = make_node(100);
enqueue(p);
p = make_node(200);
enqueue(p);
p = make_node(250);
enqueue(p);
while (p = dequeue()) {
print_item(p);
free_node(p);
}
return 0；
}（2）带Sentinel的双向链表示意图如下
三、链表实现环形队列：把双向链表改改即可
（1）其实用链表实现环形队列是最自然的，以前基于数组实现环形队列，我们还需要“假想”它是首尾相接的，而如果基于链表实现环形队列，我们本来就可以用指针串成首尾相接的。
（2）把上面的程序改成环形链表（Circular Linked List） 也非常简单，只需要把 doublylinkedlist.c 中的
struct node tailsentinel;
struct node headsentinel = {0, NULL, &tailsentinel};
struct node tailsentinel = {0, &headsentinel, NULL};
static link head = &headsentinel;
static link tail = &tailsentinel;
改为
struct node sentinel = {0, &sentinel, &sentinel};
static link head = &sentinel;再把 doublylinkedlist.c 中所有的 tail 替换成 head 即可，相当于把 head 和 tail 合二为一了。
（4）示意图
四、静态链表
五、二叉树
1.二叉树的基本概念
（1）链表的每个节点可以有一个后继，而二叉树（Binary Tree） 的每个节点可以有两个后继
比如这样定义二叉树的节点：
typedef struct node *link;
struct node {
unsigned char item;
link l, r;
};（2）二叉树的定义和举例
2.二叉树的递归定义
3.二叉树的遍历方法：前序、中序、后序
4.依据前序和中序遍历结果构造二叉树
（1）前序和中序遍历的结果合在一起可以唯一确定二叉树的形态， 也就是说根据遍历结果可以构造出二叉树，过程如下图所示：
（2）想一想，根据中序和后序遍历结果能否构造二叉树？根据前序和后序遍历结果能否构造二叉树？
- 根据一棵树的先序遍历和中序遍历，或者后序遍历和中序遍历序列，都可以唯一地确定一棵树。
- 根据前序和后序遍历结果确定唯一的二叉树是有前提的，即：所有结点的度为0或者2
（3）补充：数据结构 – 树的度和结点数的关系 参考：先序遍历和后序遍历为什么不能唯一地确定一棵树？
数据结构 – 树的度和结点数的关系
http://blog.sina.com.cn/s/blog_52f6ead00101gve6.html
（a）： 二叉树叶子节点与度为二的节点有什么关系？
叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。
比如一棵完全二叉树有三层，叶子结点就是最下面那一层的结点数，没有孩子结点，就是4，度为二的结点有3个。
（b）与图论中的“度”不同，树的度是如下定义的：有根树T中，结点x的子女数目称为x的度。也就是：在树中，结点有几个分叉，度就是几。
一个有用的小公式：树中结点数 = 总分叉数 +1。(这里的分叉数就是所有结点的度之和)
（c）度的计算
（i）设树T的度为4，其中度为1，2，3，4的节点个数分别为4，2，1，1，则T中的叶子数为？
解：
叶子的度数为0；那么设叶子数为x，则此树的总分叉数为14+22+31+41=15；此树的节点个数为16（此处涉及到一个公式;节点 数=分叉数+1，由图形便可以观察出来）。又根据题目可以知道顶点数目还可以列出一个式子：4+2+1+1+x便可以得到等 式：4+2+1+1+x=16；x=8为叶子数。
因为此题是数据结构中的问题：一般情况下都是有向树，所以叶子节点的度数为0，要区分于离散数学中的无向树叶子节点度为一。在数据结构中一般常用的 公式为：二叉树：度为0的节点数=度为2的节点数+1（n0=n2+1）此公式可由上述计算思想推导（一般在二叉树那里的公式多一些，树中只要你明确定 义，画出图来，便可以根据图形寻找出规律来）
（ii）一棵无向树T有3个2度结点，2个3度结点，2个4度结点，其余为叶。则T共有多少个结点，多少片叶？
解答：一共是21个结点，叶子结点为14个，简单的方法是你随意照着条件画一个就行，要算也简单，叶子结点=32+23+2*4-3-2-2+1=14，也就是等于总度数-节点数+1
（d）树中的节点，分为度为0，1，2的结点。如果树中只有一个节点，那么可以唯一确定一棵树，即只有一个节点的树。
当树中结点个数大于等于2的情况，树中的叶子结点和它的父亲结点中，至少有一种存在如下的情况。（为方便起见，我们先从叶子节点入手）
case 1: case2: case 3:
A D F
/ \ / \
B C E G即，叶子结点的父亲有两个孩子，只有左孩子，只有右孩子的情况。我们只需要证明，如果树存在这三种结构中的哪一种，可以唯一确定一棵树，什么情况下又不能唯一确定一棵树呢?
（i）. case 1:
A
/ \
B C前序遍历： ABC， 后序遍历： BCA
现在，我们根据遍历序列，看看能否得到另一种树的结构？
由于在前序遍历中A第一个出现，则A为这棵树的根节点。（前： A BC 后： BC A）
接下来，我们看，BC可以只在A的左子树或者右子树中出现吗？
如果BC只出现在树的左子树或者右子树中，则根据前序遍历， B应为子树的树，C为B的孩子。则后序遍历时，C应在B的前面。但实际的后序遍历，C在B的后面。因此，BC不可能只出现在A的左子树或者右子树当中。因此，在这种情况下，可以唯一确定树的结构。
（ii）. case 2:
D
/
E前序遍历： DE, 后序遍历： ED
则下面树的结构也满足前序和后序遍历的序列。
D
\
E即这种情况，不能唯一确定一棵树。
（iii）. case 3:
同case 2情况相似，也不能唯一确定一棵树。
我们可以把叶子结点推广成一棵树的情况，即如果树中只存在度为0和度为2的节点，则根据它的前序遍历和后序遍历序列，可以重构树的结构。否则不能唯一重构树。那如果给你一个前序和后序遍历的序列，我们如何来判断，它是否可以唯一地构造一棵树呢？
即我们根据遍历序列，来看看树中，如果所有结点的度为0或者2，则可以唯一还原。
例： 前序： ABDFGEC 后序： FGDEBCA
第一步： 根结点为A
第二步： 根据前后序序列，B为A的左子树的根，根据后序序列 将整个序列分为两部分： FGDEB， C 即A有两个孩子。
第三步： 继续看以B为树的树，前序为 BDFGE, 后序： FGDEB 。 按照分析A的方法来分析 B，最后得知，这棵树可以唯一确定。
但是如果把上面序列中的结点C给去掉，即：前序： ABDFGE 后序： FGDEBA， 此时就不能唯一确定了。
5.二叉树的递归定义
（1）代码如下
/* binarytree.h */
#ifndef BINARYTREE_H
#define BINARYTREE_H
typedef struct node *link;
struct node {
unsigned char item;
link l, r;
};
link init(unsigned char VLR[], unsigned char LVR[], int n);
void pre_order(link t, void (*visit)(link));
void in_order(link t, void (*visit)(link));
void post_order(link t, void (*visit)(link));
int count(link t);
int depth(link t);
void destroy(link t);
#endif/* binarytree.c */
#include <stdlib.h>
#include "binarytree.h"
static link make_node(unsigned char item)
{
link p = malloc(sizeof *p);
p->item = item;
p->l = p->r = NULL;
return p;
}
static void free_node(link p)
{
free(p);
}
link init(unsigned char VLR[], unsigned char LVR[], int n)
{
link t;
int k;
if (n <= 0)
return NULL;
for (k = 0; VLR[0] != LVR[k]; k++);
t = make_node(VLR[0]);
t->l = init(VLR+1, LVR, k);
t->r = init(VLR+1+k, LVR+1+k, n-k-1);
return t;
}
void pre_order(link t, void (*visit)(link))
{
if (!t)
return;
visit(t);
pre_order(t->l, visit);
pre_order(t->r, visit);
}
void in_order(link t, void (*visit)(link))
{
if (!t)
return;
in_order(t->l, visit);
visit(t);
in_order(t->r, visit);
}
void post_order(link t, void (*visit)(link))
{
if (!t)
return;
post_order(t->l, visit);
post_order(t->r, visit);
visit(t);
}
int count(link t)
{
if (!t)
return 0;
return 1 + count(t->l) + count(t->r);
}
int depth(link t)
{
int dl, dr;
if (!t)
return 0;
dl = depth(t->l);
dr = depth(t->r);
return 1 + (dl > dr ? dl : dr);
}
void destroy(link t)
{
post_order(t, free_node);
}/* main.c */
#include <stdio.h>
#include "binarytree.h"
void print_item(link p)
{
printf("%d", p->item);
}
int main()
{
unsigned char pre_seq[] = { 4, 2, 1, 3, 6, 5, 7 };
unsigned char in_seq[] = { 1, 2, 3, 4, 5, 6, 7 };
link root = init(pre_seq, in_seq, 7);
pre_order(root, print_item);
putchar('\n');
in_order(root, print_item);
putchar('\n');
post_order(root, print_item);
putchar('\n');
printf("count=%d depth=%d\n", count(root), depth(root));
destroy(root);
return 0;
}六、排序二叉树
（1）定义
- 排序二叉树（ BST， Binary Search Tree） 具有这样的性质： 对于二叉树中的任意节点， 如果它有左子树或右子树， 则该节点的数据成员大于左子树所有节点的数据成员， 且小于右子树所有节点的数据成员。
- 排序二叉树的中序遍历结果是从小到大排列的。
（2）代码如下
/* bst.h */
#ifndef BST_H
#define BST_H
typedef struct node *link;
struct node {
unsigned char item;
link l, r;
};
link search(link t, unsigned char key);
link insert(link t, unsigned char key);
link delete(link t, unsigned char key);
void print_tree(link t);
#endif/* bst.c */
#include <stdlib.h>
#include <stdio.h>
#include "bst.h"
static link make_node(unsigned char item)
{
link p = malloc(sizeof *p);
p->item = item;
p->l = p->r = NULL;
return p;
}
static void free_node(link p)
{
free(p);
}
link search(link t, unsigned char key)
{
if (!t)
return NULL;
if (t->item > key)
return search(t->l, key);
if (t->item < key)
return search(t->r, key);
/* if (t->item == key) */
return t;
}
link insert(link t, unsigned char key)
{
if (!t)
return make_node(key);
if (t->item > key) /* insert to left subtree */
t->l = insert(t->l, key);
else /* if (t->item <= key), insert to right subtree */
t->r = insert(t->r, key);
return t;
}
link delete(link t, unsigned char key)
{
link p;
if (!t)
return NULL;
if (t->item > key) /* delete from left subtree */
t->l = delete(t->l, key);
else if (t->item < key) /* delete from right subtree */
t->r = delete(t->r, key);
else
{ /* if (t->item == key) */
if (t->l == NULL && t->r == NULL) { /* if t is leaf node */
free_node(t);
t = NULL;
}
else if (t->l)
{ /* if t has left subtree */
/* replace t with the rightmost node in left subtree */
for (p = t->l; p->r; p = p->r);
t->item = p->item;
t->l = delete(t->l, t->item);
}
else
{ /* if t has right subtree */
/* replace t with the leftmost node in right subtree */
for (p = t->r; p->l; p = p->l);
t->item = p->item;
t->r = delete(t->r, t->item);
}
}
return t;
}
void print_tree(link t)
{
if (t)
{
printf("(");
printf("%d", t->item);
print_tree(t->l);
print_tree(t->r);
printf(")");
}
else
printf("()");
}/
* main.c */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "bst.h"
#define RANGE 100
#define N 6
void print_item(link p)
{
printf("%d", p->item);
}
int main()
{
int i, key;
link root = NULL;
srand(time(NULL));
for (i = 0; i < N; i++)
root = insert(root, rand() % RANGE);
printf("\t\\tree");
print_tree(root);
printf("\n\n");
while (root)
{
key = rand() % RANGE;
if (search(root, key))
{
printf("delete %d in tree\n", key);
root = delete(root, key);
printf("\t\\tree");
print_tree(root);
printf("\n\n");
}
}
}结果：
七、哈希表
（1）下图示意了哈希表（ Hash Table） 这种数据结构
（2）
八、 各种数据结构的search、 insert和delete操作在平均情况下的时间复杂度比较
