void insert(const node *head, node *p) { node *x, *y; y=head; do { x=y; y=x->next; } while ((y!=NULL) && (y->value < p->value); x->next=p; p->next=y; }
二.栈
(1) 栈的实现!
操作规则:先进后出,先出后进。
int stack[N], top=0; // top表示栈顶位置。
入栈:inline void push(int a) { stack[top++]=a; }
出栈:inline int pop() { return stack[--top];
栈空的条件:inline bool empty() { return top<0; }
如果两个栈有相反的需求,可以用这种方法节省空间:用一个数组表示两个栈。分别用top1、top2表示栈顶的位置,令top1从0开始,top2从N-1开始。
(2) DFS和栈
递归其实也用到了栈。每调用一次函数,都相当于入栈(当然这步操作“隐藏在幕后”)。函数调用完成,相当于出栈。
一般情况下,调用栈的空间大小为16MB。也就是说,如果递归次数太多,很容易因为栈溢出导致程序崩溃,即“爆栈”。
为了防止“爆栈”,可以将递归用栈显式实现。如果可行,也可以改成迭代、递推等方法。
使用栈模拟递归时,注意入栈的顺序——逆序入栈,后递归的要先入栈,先递归的要后入栈。
下面是非递归版本的DFS模板:
stack <int> s; // 存储状态 void DFS(int v, …) { s.push(v); // 初始状态入栈 while (!s.empty()) { int x = s.top(); s.pop(); // 获取状态 // 处理结点 if (x达到某种条件) { // 输出、解的数量加1、更新目前搜索到的最优值等 … return; } // 寻找下一状态。当然,不是所有的搜索都要这样寻找状态。 // 注意,这里寻找状态的顺序要与递归版本的顺序相反,即逆序入栈。 for (i=n-1;i>=0;i--) { s.push(… /*i对应的状态*/); } } // 无解 cout<<"No Solution."; }
三.队列
(1) 顺序队列
操作规则:先进先出,后进后出。
定义:int queue[N], front=0, rear=0;
front指向队列首个元素,rear指向队列尾部元素的右侧。
入队:inline void push(int a) { queue[rear++]=a; }
出队:inline int pop() { return queue[front++]; }
队空的条件:inline bool empty() { return front==rear; }
(2) 循环队列
循环队列——把链状的队列变成了一个环状队列。与上面的链状队列相比,可以节省很大空间。
定义:int queue[N], front=0, rear=0;
front指向队列首个元素,rear指向队列尾部元素的右侧。
入队:inline void push(int a) { queue[rear]=a; rear=(rear+1)%N; }
出队:inline int pop() { int t=queue[front]; front=(front+1)%N; return t; }
队满或队空的条件:inline bool empty() { return front==rear; }
队满和队空都符合上述条件。怎么把它们区分开呢?
第一种方法:令队列的大小是N+1,然后只使用N个元素。这样队满和队空的条件就不一样了。
第二种方法:在入队和出队同时记录队列元素个数。这样,直接检查元素个数就能知道队列是空还是满。
(3) BFS和队列
BFS要借助队列来完成,并且,将队列改成堆栈,BFS就变成了DFS。BFS的具体实现见42页“3.7 代码模板”。
四.二叉树
(1) 二叉树的链表存储法
struct node { int value; node *leftchild, *rightchild; //int id; // 结点编号。 //node *parent; // 指向父亲结点。 } arr[N]; int top=-1; node * head = NULL; #define NEW(p) p=&arr[++top]; p->leftchild=NULL; \ p->rightchild=NULL; p->value=0
(2) 完全二叉树的一维数组存储法
如果一个二叉树的结点严格按照从上到下、从左到右的顺序填充,就可以用一个一维数组保存。
下面假设这个树有n个结点,待操作的结点是r(0≤r<n)。
(3) 二叉树的遍历
1. 前序遍历
void preorder(node *p) { if (p==NULL) return; // 处理结点p cout<<p->value<<' '; preorder(p->leftchild); preorder(p->rightchild); }
2. 中序遍历
void inorder(node *p) { if (p==NULL) return; inorder(p->leftchild); // 处理结点p cout<<p->value<<' '; inorder(p->rightchild); }
3. 后序遍历
void postorder(node *p) { if (p==NULL) return; postorder(p->leftchild); postorder(p->rightchild); // 处理结点p cout<<p->value<<' '; }
假如二叉树是通过动态内存分配建立起来的,在释放内存空间时应该使用后序遍历。
4. 宽度优先遍历(BFS)
首先访问根结点,然后逐个访问第一层的结点,接下来逐个访问第二层的结点……
node *q[N]; void BFS(node *p) { if (p==NULL) return; int front=1,rear=2; q[1]=p; while (front<rear) { node *t = q[front++]; // 处理结点t cout<<t->value<<' '; if (t->leftchild!=NULL) q[rear++]=t->leftchild; if (t->rightchild!=NULL) q[rear++]=t->rightchild; } }
对于完全二叉树,可以直接遍历:
for (int i=0; i<n; i++) cout<<a[i]<<' ';
(4) 二叉树重建
【问题描述】二叉树的遍历方式有三种:前序遍历、中序遍历和后序遍历。现在给出其中两种遍历的结果,请输出第三种遍历的结果。
【分析】
前序遍历的第一个元素是根,后序遍历的最后一个元素也是根。所以处理时需要到中序遍历中找根,然后递归求出树。
注意!输出之前须保证字符串的最后一个字符是'\0'。
1. 中序+后序→前序
void preorder(int n, char *pre, char *in, char *post) { if (n<=0) return; int p=strchr(in, post[n-1])-in; pre[0]=post[n-1]; preorder(p, pre+1, in, post); preorder(n-p-1, pre+p+1, in+p+1, post+p); }
2. 前序+中序→后序
void postorder(int n, char *pre, char *in, char *post) { if (n<=0) return; int p=strchr(in, pre[0])-in; postorder(p, pre+1, in, post); postorder(n-p-1, pre+p+1, in+p+1, post+p); post[n-1]=pre[0]; }
3. 前序+后序→中序
“中+前”和“中+后”都能产生唯一解,但是“前+后”有多组解。下面输出其中一种。
bool check(int n, char *pre, char *post) // 判断pre、post是否属于同一棵二叉树 { bool b; for (int i=0; i<n; i++) { b=false; for (int j=0; j<n; j++) if (pre[i]==post[j]) { b=true; break; } if (!b) return false; } return true; } void inorder(int n, char *pre, char *in, char *post) { if (n<=0) return; int p=1; while (check(p, pre+1, post)==false && p<n) p++; if (p>=n) p=n-1; // 此时,如果再往inorder里传p,pre已经不含有效字符了。 inorder(p, pre+1, in, post); in[p]=pre[0]; inorder(n-p-1, pre+p+1, in+p+1, post+p); }
(5) 求二叉树的直径*
从任意一点出发,搜索距离它最远的点,则这个最远点必定在树的直径上。再搜索这个最远点的最远点,这两个最远点的距离即为二叉树的直径。
求树、图(连通图)的直径的思想是相同的。
// 结点编号从1开始,共n个结点。 struct node { int v; node *parent, *leftchild, *rightchild; } a[1001], *p; int maxd; bool T[1003]; #define t(x) T[((x)==NULL)?0:((x)-a+1)] node *p; void DFS(node * x, int l) { if (l>maxd) maxd=l, p=x; if (x==NULL) return; t(x)=false; if (t(x->parent)) DFS(x->parent, l+1); if (t(x->leftchild)) DFS(x->leftchild, l+1); if (t(x->rightchild)) DFS(x->rightchild, l+1); } int distance(node *tree) // tree已经事先读好 { maxd=0; memset(T, 0, sizeof(T)); for (int i=1; i<=n; i++) T[i]=true; DFS(tree,0); maxd=0; memset(T, 0, sizeof(T)); for (int i=1; i<=n; i++) T[i]=true; DFS(p,0); return maxd; }
五.并查集
并查集最擅长做的事情——将两个元素合并到同一集合、判断两个元素是否在同一集合中。
并查集用到了树的父结点表示法。在并查集中,每个元素都保存自己的父亲结点的编号,如果自己就是根结点,那么父亲结点就是自己。这样就可以用树形结构把在同一集合的点连接到一起了。
并查集的实现:
struct node { int parent; // 表示父亲结点。当编号i==parent时为根结点。 int count; // 当且仅当为根结点时有意义:表示自己及子树元素的个数 int value; // 结点的值 } set[N]; int Find(int x) // 查找算法的递归版本(建议不用这个) { return (set[x].parent==x) ? x : (set[x].parent = Find(set[x].parent)); } int Find(int x) // 查找算法的非递归版本 { int y=x; while (set[y].parent != y) // 寻找父亲结点 y = set[y].parent; while (x!=y) // 路径压缩,即把途中经过的结点的父亲全部改成y。 { int temp = set[x].parent; set[x].parent = y; x = temp; } return y; } void Union(int x, int y) // 小写的union是关键字。 { x=Find(x); y=Find(y); // 寻找各自的根结点 if (x==y) return; // 如果不在同一个集合,合并 if (set[x].count > set[y].count) // 启发式合并,使树的高度尽量小一些 { set[y].parent = x; set[x].count += set[y].count; } else { set[x].parent = y; set[y].count += set[x].count; } } void Init(int cnt) // 初始化并查集,cnt是元素个数 { for (int i=1; i<=cnt; i++) { set[i].parent=i; set[i].count=1; set[i].value=0; } } void compress(int cnt) // 合并结束,再进行一次路径压缩 { for (int i=1; i<=cnt; i++) Find(i); }
说明:
使用之前调用Init()!
Union(x,y):把x和y进行启发式合并,即让节点数比较多的那棵树作为“树根”,以降低层次。
Find(x):寻找x所在树的根结点。Find的时候,顺便进行了路径压缩。
上面的Find有两个版本,一个是递归的,另一个是非递归的。
判断x和y是否在同一集合:if (Find(x)==Find(y)) ……
在所有的合并操作结束后,应该执行compress()。
并查集的效率很高,执行m次查找的时间约为O(5m)。
六.总结
数据结构是计算机科学的重要分支。选择合适的数据结构,可以简化问题,减少时间的浪费。
1. 线性表
线性表有两种存储方式,一种是顺序存储,另一种是链式存储。前者只需用一维数组实现,而后者既可以用数组实现,又可以用指针实现。
顺序表的特点是占用空间较小,查找和定位的速度很快,但是插入和删除元素的速度很慢(在尾部速度快);链表和顺序表正好相反,它的元素插入和删除速度很快,但是查找和定位的速度很慢(同样,在首尾速度快)。
2. 栈和队列
栈和队列以线性表为基础。它们的共同点是添加、删除元素都有固定顺序,不同点是删除元素的顺序。队列从表头删除元素,而栈从表尾删除元素,所以说队列是先进先出表,堆栈是先进后出表。
栈和队列在搜索中有非常重要的应用。栈可以用来模拟深度优先搜索,而广度优先搜索必须用队列实现。
有时为了节省空间,栈的两头都会被利用,而队列会被改造成循环队列。
3. 二叉树
上面几种数据结构都是线性结构。而二叉树是一种很有用的非线性结构。二叉树可以采用以下的递归定义:二叉树要么为空,要么由根结点、左子树和右子树组成。左子树和右子树分别是一棵二叉树。
计算机中的树和现实生活不同——计算机里的树是倒置的,根在上,叶子在下。
完全二叉树:一个完全二叉树的结点是从上到下、从左到右地填充的。如果高度为h,那么0~h-1层一定已经填满,而第h层一定是从左到右连续填充的。
通常情况下,二叉树用指针实现。对于完全二叉树,可以用一维数组实现(事先从0开始编号)。
访问二叉树的所有结点的过程叫做二叉树的遍历。常用的遍历方式有前序遍历、中序遍历、后序遍历,它们都是递归完成的。
4. 树
树也可以采用递归定义:树要么为空,要么由根结点和n(n≥0)棵子树组成。
森林由m(m≥0)棵树组成。
二叉树不是树的一种,因为二叉树的子树中有严格的左右之分,而树没有。这样,树可以用父结点表示法来表示(当然,森林也可以)。并查集的合并、查询速度很快,它就是用父结点表示法实现的。
不过父结点表示法的遍历比较困难,所以常用“左儿子右兄弟”表示法把树转化成二叉树。
树的遍历和二叉树的遍历类似,不过不用中序遍历。它们都是递归结构,所以可以在上面实施动态规划。
树作为一种特殊的图,在图论中也有广泛应用。
树的表示方法有很多种。
第一种是父节点表示法,它适合并查算法,但不便遍历。
第二种是子节点表表示法。
第三种是“左儿子右兄弟”表示法。