数据结构经典算法总复习（下卷）

第五章:树和二叉树

先序遍历二叉树的非递归算法。

void PreOrderTraverse(BiTree T, void (*Visit)(TElemType)) {//表示用于查找的函数的指针
  Stack S; BiTree p = T;
  InitStack(S);//S模拟工作栈
  while (p || !StackEmpty(S)) {//S为空且下一个结点为空，意味着结束遍历
    if (p) {//p有值，则Push进栈为一个工作进程
      Visit(p->data); Push(S, p); p = p->lchild;//先序遍历，先Visit
    } else {
//p为空，则它的上级被Pop出去，成为新的p，再取右孩子。在下一个循环中如果它的上级没右孩子，则说明它的上级是叶子结点（或两端已经工作栈弹出了），则再Pop出它的上级的上级（此时它的上级已经无用，工作栈弹出），取它上级的兄弟结点
      Pop(S, p); p = p->rchild;
    }
  }
}

利用工作栈的思想，过程十分复杂，多多复习，巩固加深！

层序遍历二叉树

void LayerTraverse(BiTree T, void (*Visit)(TElemType)) {
  Queue Q; BiTree p;
  InitQueue(Q);
  EnQueue(Q, T);
  while (!QueueEmpty(Q)) {
    DeQueue(Q, p);
//每有一个父母结点出队列，就把它的左右孩子放到队尾排队，确保一层一层遍历
    if (p) {
      Visit(p->data);
      EnQueue(Q, p->lchild); EnQueue(Q, p->rchild);
    }
  }
}

计算二叉树中每个结点的层次

void LevelRecur(BiTree T, int lev) {
  if (T) {
    ++lev;//准备遍历下一层
    cout << T->data << ' ' << lev << endl;
    LevelRecur(T->lchild, lev);
    LevelRecur(T->rchild, lev);//下一层启动
  }
}
void Level(BiTree T) {
  LevelRecur(T, 0);
}

输出二叉树根结点到所有叶子结点的路径

void OutPath(BiTree T, Stack &S) {//使用一个栈存储路径，起到回溯的作用
  if (T) {
    Push(S, T);
    if (!T->lchild && !T->rchild)
      PrintStack(S);//S栈中元素依次输出，不取出
    OutPath(T->lchild, S);
    OutPath(T->rchild, S);
    Pop(S, T);//该节点左右孩子搜索完，则出栈，不再计入路径中
  }
}

由扩展的先序序列，即波兰式，建立二叉树

void CreateBiTree(BiTree &T) {
  // 读入扩展的先序序列，假定数据元素为字符型，#表示NULL
  char ch; scanf("%c", &ch);
  if (ch == '#') T = NULL;
  else {
    T = new BiTNode; T->data = ch;
    CreateBiTree(T->lchild);//依次建立二叉树
    CreateBiTree(T->rchild);
  }
}

先根遍历树，孩子链表实现

void PreOrderRecur(CTree T, int loc, void (*Visit)(TElemType)) {
  if (loc == -1) return;
  Visit(T.nodes[loc].data);//先查询根结点
  ChildPtr p;
  for (p = T.nodes[loc].firstchild; p; p = p->next) {
    PreOrderRecur(T, p->child, Visit);//取出下个孩子，并查询
  }
}
void PreOrderTree(CTree T, void (*Visit)(TElemType)) {
  PreOrderRecur(T, T.root, Visit);
}

计算树的深度，孩子兄弟链表实现

int TreeDepth(CSTree T) {
  if (!T) return 0;//最简单情况，遍历结束条件
  CSTree p; int maxh = 0;//maxh为全局变量
  for (p = T->firstchild; p; p = p->nextsibling) {//到T的下一个孩子，并且遍历其孩子的兄弟
    int h = TreeDepth(p);//当前遍历结点的深度
    if (h > maxh) maxh = h;
  }
  return maxh + 1;
}

构造huffman树

typedef unsigned int WeightType;
typedef struct {
  TElemType data;
  WeightType weight; // 叶子权值的类型
  int parent, lchild, rchild; // 三叉静态链表
} HTNode, *HuffmanTree;
void CreateHuffmanTree(HuffmanTree &HT, int n) {
  int m = 2*n-1; // 最终将得到2n-1个结点
  HT = new HTNode[m];
  for (i=0; i<n; ++i) {
    cin >> HT[i].data >> HT[i].weight;
    HT[i].lchild = HT[i].rchild = HT[i].parent = -1;//-1即示意为为null
  }//输入结点值
  for (i=n; i<m; ++i) {
    Select(HT, i-1, s1, s2); HT[s1].parent=HT[s2].parent=i;
    HT[i].weight = HT[s1].weight + HT[s2].weight;//两个结点的父母的权值为它们加和
    HT[i].lchild=s1; HT[i].rchild=s2; HT[i].parent = -1;
  }
}

const unsigned int MAX_WEIGHT = UINT_MAX;
void Select(HuffmanTree HT, int s, int &l, int &r) {
  // 本函数的作用是从HT[0..s]中找到权值最小的两个结点
  WeightType WL = MAX_WEIGHT, WR = MAX_WEIGHT;
  for (i=0; i<=s; ++i) {
    if (HT[i].parent == -1) {
      if (HT[i].weight < WL) {
        WR = WL; WL = HT[i].weight; r=l; l=i;
      } else if (HT[i].weight < WR) {
        WR = HT[i].weight; r=i;
      }
    }
  }
}

第六章：图

深度优先遍历DFS

bool visited[MAX_VERTEX_NUM];
void DFS(Graph G, int v) {//类似于先根遍历
  Visit(v); visited[v] = true;
  for (int w=AdjVex(G, v); w != -1; w=AdjVex(G, v, w)) {
    if (!visited[w])
      DFS(G, w);
  }
}
void DFSTraverse(Graph G) {
  for (int v=0; v<G.vexnum; ++v)
    visited[v] = false;//初始化visited表
  for (int v=0; v<G.vexnum; ++v)
    if (!visited[v])
      DFS(G, v);//如果没有查找到没遍历过的，则弹出工作栈，返回上一级
}
int AdjVex(MGraph G, int v, int w=-1) {//邻接矩阵
  for (int j=w+1; j<G.vexnum; ++j)
    if (G.arcs[v][j] != INFINITY) return j;//找找它可能的出路
  return -1;
}

int AdjVex(ALGraph G, int v, int w=-1) {//邻接表
  ArcNode *p = G.vertices[v].firstarc;
  if (w != -1) {
    while (p && p->adjvex != w) p = p->nextarc;
    if (p) p = p->nextarc;
  }
  return p ? p->adjvex : -1;
}

广度优先搜索BFS

bool visited[MAX_VERTEX_NUM];
void BFS(Graph G, int v) {//类似于层序遍历
  Visit(v); visited[v] = true;
  Queue Q; InitQueue(Q); EnQueue(Q, v);
  while (!QueueEmpty(Q)) {
    DeQueue(Q, v);
    for (int w=AdjVex(G, v); w != -1; w=AdjVex(G, v, w)) {
      if (!visited[w]) {
        Visit(w); visited[w] = true; EnQueue(Q, w);
      }
    }
  }
}
void BFSTraverse(Graph G) {
  for (int v=0; v<G.vexnum; ++v)
    visited[v] = false;//初始化
  for (int v=0; v<G.vexnum; ++v)
    if (!visited[v])
      BFS(G, v);
}

利用DFS求简单路径

bool visited[MAX_VERTEX_NUM];
bool DFS_SimplePathRecur(Graph G, int vi, int vj, Stack &S) {
  Push(S, vi); visited[vi] = true;//S存储过往路径
  if (vi == vj) {
    Print(S); return true;
  }
  for (int w=AdjVex(G, vi); w != -1; w=AdjVex(G, vi, w)) {
    if (!visited[w]) {
      if (DFS_SimplePathRecur(G, w, vj, S))
        return true;
    }
  }
  Pop(S, vi); visited[vi] = false; return false;
}
void DFS_SimplePath(Graph G, int vi, int vj) {
  Stack S; InitStack(S);
  for (int v=0; v<G.vexnum; ++v)
    visited[v] = false;
  if (DFS_SimplePathRecur(G, vi, vj, S))
    cout << "Found a path" << endl;
}

使用Prim算法，得出最小生成树

void Prim(MGraph G, int v0) {
  // 用于存储F集合的两个数组：邻接顶点和最小边
  int adjvex[MAX_VERTEX_NUM], lowcost[MAX_VERTEX_NUM];
  for (int j=0; j<G.vexnum; ++j) {
    if (j!=v0) {
      adjvex[j] = v0;
      lowcost[j] = G.arcs[v0][j];}
  }
  lowcost[v0] = INFINITY;
  for (int i=0; i<G.vexnum-1; ++i) { // 循环n-1次
    int k = MinEdge(lowcost, G.vexnum);//该顶点的连接的最小边
    printf("(%d, %d): %d\n", k, adjvex[k], lowcost[k]);
    lowcost[k] = INFINITY;
    for (int j=0; j<G.vexnum; ++j) {
      if (G.arcs[k][j] < lowcost[j]) {
        adjvex[j] = k;
        lowcost[j] = G.arcs[k][j];}
    }
  }
}

得出拓扑排序

void TopologicalSort(ALGraph G) {//思路找头结点，并删除它和它连接的路径，继续下一个
  int InDegree[MAX_VERTEX_NUM];
  FindInDegree(G, InDegree);
  Stack S; InitStack(S);
  for (int i=0; i<G.vexnum; ++i)
    if (!InDegree[i]) Push(S, i);
  int count = 0; // 统计输出顶点的个数
  while (!StackEmpty(S)) {
    int i; Pop(S, i); ++count;
    cout << G.vertices[i].data << endl; 
    ArcNode *p;
    for (p=G.vertices[i].firstarc; p; p=p->nextarc) {
      k = p->adjvex;
      if (!(--InDegree[k])) Push(S, k);
    }
  }
  if (count<G.vexnum)
    cout << "The graph has loop" << endl;
}

void FindInDegree(ALGraph G, int *InDegree) {
  for (int i=0; i<G.vexnum; ++i) InDegree[i] = 0;
  for (int i=0; i<G.vexnum; ++i) {
    for (ArcNode *p=G.vertices[i].firstarc; p; p=p->nextarc) {
      InDegree[p->adjvex]++;
    }
  }
}

第七章：查找表

二分查找（折半查找）静态表

int Search_Bin(StaticSearchTable ST, KeyType key) {//其中ST为从小到大的顺序表
  int low=1, high=ST.length;
  while (low <= high) {
    mid = (low + high) / 2;
    if (key == ST.data[mid].key) return mid;
    else if (key < ST.data[mid].key) high = mid - 1;//取前一半
    else low = mid + 1;//取后一半
  }
  return 0;
}

二叉查找树的查找方法（递归算法）

BiTree Search_BST(BiTree T, KeyType key) {//题外话：对二叉查找树进行中序遍历可得到有序数列
  if (!T || key == T->data.key)
    return T;
  else if (key < T->data.key)//此时的左右孩子被赋予了更多意义
    return Search_BST(T->lchild, key);
  else
    return Search_BST(T->rchild, key);
}

二叉查找树的查找方法（非递归算法）

bool SearchBST(BiTree T, KeyType key, BiTree &p, BiTree &f) {
  // 若查找到key，则返回true，此时p指向等于key的
  // 结点，f是p的双亲（若p等于根结点，则f为NULL）
  // 若查找不到key，则返回false，此时p为NULL，f
  // 指向查找过程中最后一个比较的结点
  f = NULL; p = T;
  while (p && key != p->data.key) {
    f = p;//保存f，则允许了回溯到父母结点的操作
    if (key < p->data.key) p = p->lchild;//向左走呢，还是向右走呢？
    else p = p->rchild;
  }
  if (!p) return false;
  else return true;
}

二叉查找树的插入

bool InsertBST(BiTree &T, KeyType key) {
  BiTree p, f;
  bool found = SearchBST(T, key, p, f);
  if (found) return false;//查找成功，则不插入；
//反之，在查找失败的查找路径上最后一个结点的左或右插入
  BiTree t = new BiTNode;
  t->data.key = key; t->lchild = t->rchild = NULL;
  if (!f) T = t;//如果二叉树为空，则插入第一条数据
  else if (key < f->data.key) f->lchild = t;
  else f->rchild = t;
  return true;
}

二叉查找树的删除

bool DeleteBST(BiTree &T, KeyType key) {
  BiTree p, f;
  bool found = SearchBST(T, key, p, f);
  if (!found) return false;
  if (p->lchild && p->rchild) {//有左右孩子的条件
    BiTree q = p, t = p->rchild;//将结点替代为右子树上最小的结点（也可为左子树上最大的结点）
    while (t->lchild) { q = t; t = t->lchild; }//一直向左子树查找，找到“最左”的t，即最小
    p->data = t->data;//替代
    if (q != p) q->lchild = t->rchild;//q为t的双亲，由于t无左子树，则只需要将t的右子树接到q上即可完成交接t的转移。
    else q->rchild = t->rchild; delete t;//如果p是t的双亲，则直接插上
  } else {
    BiTree q = p->lchild ? p->lchild : p->rchild;
    if (!f) T = q;
    else if (p == f->lchild) f->lchild = q;
    else f->rchild = q; delete p;
  }
  return true;
}

写出判别一颗二叉树是否为二叉排序树的算法，设二叉排序树中不存在关键字值相同的结点。

elemType arr[MAXN]; // 存放中序遍历结果
int k=0; // 记录访问过的结点数
void Inorder_Traversal (TreeNode∗ T){
    if (!T) return;
    Inorder_Traversal (T−>left);
    arr [k] = T−>val; // 记录结点值
    k++;
    Inorder_Traversal (T−>right, arr);
}

bool Is_Binary_Sort_Tree(TreeNode∗ T){
    Inorder_Traversal (T); // 先中序遍历
    for (int i=1; i<k; i++)
        if (arr [ i ] <= arr[i−1]) // 判断是否递增
            return false ;
    return true;
}

第八章：排序

简单排序

void SelectSort(SqTable &L) {
  for (int i=1; i<L.len; ++i) {
    int j=i;
    for (int k=L.len; k>i; --k)
      if (L.r[k].key < L.r[j].key) j=k;
    if (i!=j) {
      // 这里我们将L.r[i]和L.r[j]交换
      // 另一种做法是将L.r[i..j-1]各个后移一位，然后令L.r[i]=L.r[j]
      RcdType tmp = L.r[i]; L.r[i] = L.r[j]; L.r[j] = tmp;
    }
  }
}

冒泡排序

void BubbleSort(SqTable &L) {
  bool change = true;
  for (int i=n; i>=2 && change; --i) {
    // 这里我们设置一个标记，如果j从1到i-1循环中没有发生元素的互换
    // 说明整个序列已经是有序的了，无需考虑更小的i
    change = false;
    for (int j=1; j<=i-1; ++j) {
      if (L.r[j].key > L.r[j+1].key) {
        RcdType tmp = L.r[j]; L.r[j] = L.r[j+1]; L.r[j+1] = tmp;
        change = true;
      }
    }
  }
}

插入排序

void InsertSortSub(SqTable &L, int low, int high) {
  // 这个子函数对L.r[low..high]做简单插入排序
  for (int i=low+1; i<=high; ++i)
    if (L.r[i].key < L.r[i-1].key) {
      RcdType tmp = L.r[i];
      for (int j=i-1; tmp.key < L.r[j].key && j>=low; --j)
        L.r[j+1] = L.r[j]; // 元素后移
      L.r[j+1] = tmp;      // 插入到合适位置
    }
}
void InsertSort(SqTable &L) {
  InsertSortSub(L, 1, L.len);
}

希尔排序

void ShellSortSub(SqTable &L, int dk) {
  // 一趟增量为dk的插入排序
  for (int i=dk+1; i<=L.len; ++i) {
    if (L.r[i].key < L.r[i-dk].key) {
      RcdType tmp = L.r[i];
      for (int j=i-dk; tmp.key < L.r[j].key && j>=1; j-=dk)
        L.r[j+dk] = L.r[j];
      L.r[j+dk] = tmp;
    }
  }
}
void ShellSort(SqTable &L, int delta[], int k) {
  // delta是每趟排序的增量值
  for (int i=0; i<k; ++i)
    ShellSortSub(L, delta[i]);
}

快速排序

void QSort(SqTable &L, int low, int high) {
  // 对L[low..high]进行快速排序
  if (low < high) {
    int pivotloc = Partition(L, low, high);
    QSort(L, low, pivotloc-1);
    QSort(L, pivotloc+1, high);
  }
}
void QuickSort(SqTable &L) {
  QSort(L, 1, L.len);
}
int Partition(SqTable &L, int low, int high) {
  // 选择一个枢轴，将L.r[low..high]分为两部分
  // 返回枢轴最后所在的位置，以便进一步划分
  // 划分以后，在枢轴之前（之后）的元素都小于（大于）或等于枢轴
  int pivotloc = low; // 枢轴可以任意选取，例如取第一个位置
  RcdType tmp = L.r[pivotloc];
  KeyType pivotkey = tmp.key;
  while (low<high) {
    while (low<high && L.r[high].key>=pivotkey) --high;
    L.r[low] = L.r[high];
    while (low<high && L.r[low].key<=pivotkey) ++low;
    L.r[high] = L.r[low];
  }
  L.r[low] = tmp;
  return low;
}

堆排序

void HeapAdjust(SqTable &L, int s, int m) {
  // 已知L.r[s..m]中除了L.r[s]以外，都满足大顶堆的定义
  // 本函数通过调整，使得L.r[s..m]成为一个大顶堆
  RcdType tmp = L.r[s];
  for (int i=2*s; i<=m; i*=2) { // 每次向下一层
    if (i<m && L.r[i].key<L.r[i+1].key) ++i;
    if (tmp.key >= L.r[i].key) break; // 已经找到合适的位置
    L.r[s] = L.r[i]; s = i; // 与孩子换位
  }
  L.r[s] = tmp;
}
void HeapSort(SqTable &L) {
  int i; RcdType tmp;
  for (i=L.len/2; i>0; --i)
    HeapAdjust(L, i, L.len); // 构造初始大顶堆
  for (i=L.length; i>1; --i) {
    tmp = L.r[i];
    L.r[i] = L.r[1];
    L.r[1] = tmp; // 将最大的关键字放到L.r[i]
    HeapAdjust(L, 1, i-1); // 对L.r[1..i-1]调用筛选法重新调整为堆
  }
}

归并排序

void Merge(RcdType* Rs, RcdType* Rt, int s, int m, int t) {
  // 已知Rs[s..m]和Rs[m+1..t]都是有序表，将它们归并存储到Rt[s..t]
  int i,j,k;
  for (i=s, j=m+1, k=s; i<=m && j<=t; ++k) {//两表的排序在此处
    if (Rs[i].key <= Rs[j].key) Rt[k] = Rs[i++];
    else Rt[k] = Rs[j++];
  }
  for (; i<=m; ++i, ++k) Rt[k] = Rs[i];//当一个有序表取完时，剩下直接安进去
  for (; j<=t; ++j, ++k) Rt[k] = Rs[j];
}
void MSort(RcdType* Rs, RcdType* Rt, int low, int high) {//递归算法
  if (low < high) {//low=high时，无需归并
    int mid = (low+high)/2;
    MSort(Rs, Rt, low, mid); MSort(Rs, Rt, mid+1, high);
    Merge(Rs, Rt, low, mid, high);
    for (int i=low; i<=high; ++i) Rs[i] = Rt[i];//将Rt复制到Rs上
  }
}
void MergeSort(SqTable &L) {
  RcdType* tmp = new RcdType[L.len+1];
  MSort(L.r, tmp, 1, L.len);
  delete []tmp;
}

基数排序

const int RADIX = 128; // 每个“基本关键字”的取值范围，称为基数
const int KEY_LENGTH = 5; // 共有5个“基本关键字”
typedef char KeyType[KEY_LENGTH]; // 关键字类型为长度为5的字符串
void RadixPass(RcdType *R, RcdType *T, int n, int k) {
  int j; int count[RADIX];
  for (j=0; j<RADIX; ++j) count[j] = 0;
  for (j=1; j<=n; ++j) count[R[j].key[k]]++;
  for (j=1; j<RADIX; ++j) count[j] = count[j-1] + count[j];
  for (j=n; j>0; --j) {
    int p = R[j].key[k]; T[count[p]] = R[j]; count[p]--;
  }
  for (j=1; j<=n; ++j) R[j] = T[j];
}
void RadixSort(SqTable &L) {
  RcdType *tmp = new RcdType[L.len+1];
  for (int k = KEY_LENGTH-1; k>=0; --k)
    RadixPass(L.r, tmp, L.len, k);
  delete []tmp;
}