template<class T> void merge(T* a, int n1, int n2){
//将数组 a 中下标分别从 0...n1-1 和 n1...n1+n2-1 的两个有序序列归并为一个有序序列
T* temp = new T(n1 + n2);
int i = 0, j1 = 0, j2 = 0;
while (j1<n1 & j2<n2)
temp[i++] = (a[j1] <= a[n1+j2] ? a[j1++] : a[n1+j2++]);
while (j1<n1)
temp[j++] = a[j1++];
while (j2<n2)
temp[j++] = a[n1+j2++];
for (int i=0; i<n1+n2; i++)
a[i] = temp[i];
delete[]temp;
}
template<class T> void sort(T* a, int n){
if (n>1){
int n1 = n / 2;
int n2 = n - n1;
sort(a, n1); // 递归使 a 中前 n1 个元素有序
sort(a+n1, n2); // 递归使 a 中后 n2 个元素有序
merge(a, n1, n2);
}
}
Dijkstra
算法void ShortestPath_DU(MGaph G, int v0, PathMatrix & P, ShortPathTable & D){
// 用 dijkstra 算法求有向图 G 的 v0 顶点到其余顶点 v 的最短路径 P[v] 及其带权长度 D[v]
// 若 P[v][w] 为 True 则 w 是从 v0 到 v 当前求得最短路径上的顶点
// final[v] 为 True 当且仅当 v∈S,即已经求得 v0 到 v 的最短路径
int i=0, j, v, w, min;
bool final[MAX_VERTEX_NUM];
for (v=0; v<G.vexnum; ++v){
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; w<G.vexnum; ++w)
P[v][w] = FALSE; // 设空路径
if (D[v] < INFINITY){
P[v][v0] = TRUE;
p[v][v] = TRUE;
}
}
// 初始化, v0 顶点属于 S 集
D[v0] = 0;
final[v0] = TRUE;
// 开始主循环,每次求得 v0 到某个 v 顶点的最短路径,并加 v 到 S 集合
for (i=1; i<G.vexnum; i++){ //其余 G.vexnum-1 个顶点
min = INFINITY; // 当前所知离 v0 顶点的最短距离
for (w=0; w<G.vexnum; w++)
if (!final[w]) // w 顶点在 V-S 中
if (D[w]<min){ // 顶点离 v0 顶点更加
v = w;
min = D[w];
}
final[v] = TRUE; // 离 v0 顶点最近的 v 添加 S 集
for (w=0; i<G.vexnum; w++) // 更新当前最短路径及距离
if (!final[w] && (min+G.arcs[v][w].adj < D[w])){
// 修改 D[w] 和 P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for (j=0; j<G.vexnum; j++)
p[w][j] = P[v][j]; // 第 v 行赋值于第 w 行
p[w][w] = TRUE;
}
}
}
int search_seq(SSTable ST, KeyType key){
// 在顺序表中查找关键字等于 key 的数据元素
// 若找到,则将该元素与其前驱交换(若存在),并返回其在表中的位置(交换后),否则为-1
for (int i=0; i<ST.length; i++){
if (key == ST.elem[i]){ // 找到 key 数据元素
if (i>0){ // 存在前驱,交换
ElemType temp = ST.elem[i];
ST.elem[i] = ST.elem[i-1];
ST.elem[i-1] = temp;
return i-1;
}
else{ // 不存在前驱
return 0
}
}
}
return -1
}
LinkNode* search_seq2(LinkList L, KeyType key){
// 在链表中 L(带头结点)查找关键字等于 key 的数据元素
// 若找到,则将该元素与其前驱交换(若存在),并返回其在表中的位置(交换后),否则为 NULL
LinkNode* p = L->next, pre = L;
while (p != NULL){
if (key == p->data){ // 找到 key 数据元素
if (pre != L){ // 存在前驱,交换
ElemType temp = pre->data;
pre->data = p->data;
p->data = temp;
return pre;
}
else{ // 不存在前驱
return p;
}
}
}
return NULL;
}
BT
为树根指针的二叉树叶子结点个数// 采用先序遍历整棵二叉树,统计叶子结点个数
int count = 0;
void Count(BTreeNode* BT){
if (BT!=NULL){
if (BT->lchild == NULL && BT->rchild == NULL)
count++;
Count(BT->lchild);
Count(BT->rchild);
}
}
BST
为树根指针的二叉搜索树上进行查找值为 Item
的结点的非递归算法// 根据 item 的值和当前节点的比较,如果相等就找到返回,如果小于,当前节点移动到右孩子,否则移动找左孩子,重复上述过程。如果最后没有找到,返回 false
bool Find(BTreeNode* BST, ElemType &item){
BTreeNode* p = BST;
while(!p){
if (item == p->data){
item = p->data;
return TRUE;
}
else if (item < p->data)
p = p->left;
else
p = p->right;
}
return FALSE;
}
int BinarySearch(SeqList L, ElemType key){
// 在有序表 L 中查找关键字为 key 的元素,若存在则返回位置,不存在则返回-1
int low = 0, high = L.TableLen-1, mid;
while (low <= high){
mid = (low + high) / 2; // 取中间位置
if (L.elem[mid] == key) // 查找成功返回所在位置
return mid;
else if (L.elem[mid] > key) // 从前半部分查找
high = mid - 1;
else
low = mid + 1;
}
return -1
}
L
的数据建立一棵二叉排序树int BST_Insert(BiTree &T, KeyType k){
// 在二叉排序树 T 中插入一个关键字 k 的节点
if (T == NULL){ // 原树为空,新插入的记录为根节点
T = (BiTree)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = T->rchild = NULL;
return 1 // 返回 1,表示树空间申请成功,并建立根节点
}
else if (k == T->key) // 树中存在相同的关键字节点,跳过该节点
else if (k < T->key)
return BST_Insert(T->lchild, k); // 插入到 T 的左子树
else
return BST_Insert(T->rchild, k); // 插入到 T 的右子树
}
void Create_BST(BiTree &T, KeyType L[], int n){
// 用长度为 n 的线性表建立一个二叉排序树
T = NULL; // 初始化 T 为空
for (int i=0; i<n; i++)
BST_Insert(T, L[i]);
}
L
中所有其值大于等于 min
小于等于max
的结点void rangeDelete(LinkList & L, ElemType min, ElemType max){
// q 初始化指向待处理链表的头结点指针,而p始终为下一节点指针
// 如果 q 的下一节点(p)不在min-max范围内,则将 q 的下一节点变为下下一节点(p->next)
ListNode* q = L, *p = L->next;
while (p!=NULL){
if (p->data >= min && p->data <= max){ // 需要删除
q->next = p->next; // 将 q 的下一节点取代为下下一节点
free(p); // 清理下一节点的空间
p = q->next // 重置 p 为删除后链表 L 的下一节点
}
else{
q = p; // 同等于 q = q->next;
p = p->next;
}
}
}
DFS
生成树(生成森林)的算法,并打印所有的树边int visited[MAXNUM]; // 访问标致数组
void DFSTraverseTree (ALGraph *G){
// 求深度优先生成树(以邻接表表示的图 G)
for (int i=0; i<n; i++)
visited[i] = FALSE; // 初始化访问标志数组
for (int i=0; i<n; i++)
if (!visited[i]) // 第 i 个结点没有访问过
DFSTree(G, i); // 以 vi 为源点开始 DFS 遍历 G
}
void DFSTree (ALGraph* G, int i){
// 以 vi 为出发点对邻接表表示的图 G 进行深度优先搜索,打印出生成树的边
EdgeNode *p;
visited[i] = TRUE; // 标记 vi 已访问
p = G->adjlist[i].firstEdge; // 取 vi 边表的头指针
while(p){
// 依次搜索 vi 的邻接点vj, 这里 j=p->adjvex;
if (!visited[p->adjvex]){ // 若 vj 尚未被访问
// 打印边
printf("(%c, %c)\n", G.vertex[i]->adjlist, G.vertex[p->adjvex]-adjlist);
DFSTree(G, p->adjvex);
}
p = p->next;
}
}
bool ListInsert(Sqlist &L, int i, ElemType e){
// 本算法实现将元素 e 插入到顺序表 L 中第 i 个位置
if (i<1 || i>L.length+1) // 判断 i 的范围是否有效
return FALSE;
if (L.length >= MaxSize) //当前存储空间已满,不能插入
return FALSE;
for (int j=L.length; j>=i; j--) // 将第 i 个元素及之后的元素后移
L.data[j] = L.data[j-1];
L.data[i-1] = e; // 在位置 i 处放入 e
L.length++;
return TRUE;
}
bool ListDelete(Sqlist &L, int i, int &e){
// 本算法实现删除顺序表 L 中第 i 个位置的元素
if (i<1 || i>L.length) // 判断 i 的范围是否有效
return FALSE;
e = L.data[i-1]; // 在位置 i 处放入 e
for (int j=i; j<L.length; j++) // 将第 i 个位置之后的元素前移
L.data[j-1] = L.data[j];
L.length--;
return TRUE;
}
X
的结点。删除后仍为二叉排序树(不考虑 X
为根)思路:先用层次遍历思想查找到值为 X 的结点, 然后根据其是否有左右孩子情况删除处理。如果无左孩子,直接将右子树代替它。同理如果没有右孩子,直接将左子树代替它。如果左右孩子都存在,边在左子树中找一个值最大的结点代替它。
int DeleteBST (BiTree &T, ElemType X){
// 删除二叉排序树 T 中,结点值为 X 的结点
if (!T)
return 0; //不存在这样的结点
else{
if (X==T.key)
return Delete(T);
else if (X<T.key)
return DeleteBST(T->lchild, X);
else
return DeleteBST(T->rchild, X);
}
}
int Delete(BiTree & p){
// 从二叉树排序树中删除结点 p,并且重接他的左或右子树
if (!p->rchild){ // 右子树为空,只需重接左子树
q = p;
p = p->lchild;
free(q);
}
else if (!p->rchild){ // 左子树为空,只需要重接右子树
q = p;
p = p->rchild;
free(q);
}
else{ // 左右子树均不空
q = p;
s = p->lchild;
while (s->rchild){ // 找到左子树中结点值最大的结点 s
q = s;
s = s->rchild;
}
p->key = s->key;
if (q != p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
free(s);
}
return 1;
}
X
和 Y
是表示成单链表的两个串,找出 X
中第一个不在 Y
中出现的字符采用带头结点的单链表作为串的存储结构,找出 X 中第一个不在 Y 中出现的结点的算法
char find(LinkList X, LinkList Y){
LNode* p = X->next, *q;
while(p){
// 遍历 Y,查找是否存在值为 p->data 的结点
q = Y->next;
while(q){
if (p->data == q->data)
break;
else
q = q->next;
}
if (!q)
return p->data; // Y 中没有找到
else
p = p->next; // Y 中找到,继续查找下一个元素
}
}
L
中所含元素的个数,并给出单链表的数据结构示意图int CountNode(LinkList L){
int count = 0;
LNode * p = L->next;
while(p){
count++;
p = p->next;
}
return count;
}
# 示意图:
#
# A->B->C...->N
int Height(BiTree T){
if (T == NULL)
return 0;
int ld = Height(T->lc);
int rd = Height(T->rc);
return (ld>rd ? ld+1 : rd+1);
}
思路:采用还在兄弟链表示的树 T,对其从所有结点进行遍历。在访问结点是判定当前结点是否有孩子,如果没有孩子则该结点是叶子结点,计数器加一,遍历结束后,就能得到叶子结点数。
int CountLeafNode(CSTree T){
static int count = 0;
if (T){
if (!T->firstchild){
count++;
}
else{
CountLeafNode(T->nextsibling);
}
return count;
}
}
X
的结点(二叉树中)。用 C 语言打印值为 X
的结点的所有祖先并分析时间复杂度思路:采用非递归后序遍历,最后访问根节点,当访问到值为 x 的结点时,栈中所有元素均为该节点的祖先。因为采用的是后序遍历算法,故时间复杂度为O(n)
void search(BiTree bt, ElemType x){
BiTree t;
int tag;
}stack; // tag = 0 表示左子树被方法,tag = 1 表示左子树被访问
void Search(BiTree bt, ElemType x){
// 在二叉树 bt 中,查找值为 x 的结点,并打印其所有祖先
stack s[];
top = 0;
while (bt != NULL && bt->data != x){ // 结点入栈
s[++top].t = bt;
s[top].tag = 0;
bt = bt->lchild; // 沿左分支向下
}
if (bt->data == x){
printf("所查结点的所有祖先结点的值为:\n"); // 找到 x
for (i=1; i<=top; i++){ // 输出祖先值后结束
printf("%d\n", s[i].t->data);
exit(1);
}
}
while (top != 0 && s[top].tag == 1) // 退栈(空遍历)
top--;
if (top!=0){
s[top].tag = 1;
bt = s[top].t->rchild; // 沿右分支向下遍历
}
}
L1
、L2
为两循环单链表的头结点指针。m
,n
分别为数据结点个数。用最快速度将两表并成一个带头结点的循环单链表思路:采用头插法,将短链表插入到长链表中。时间复杂度为O(min(n, m))
void merge(LinkList &L1, LinkList &L2){
LinkList *p = L1->next, *q = L2->next;
if (m>n){
L3 = L1;
L3->next = q;
while (q->next != L2)
q = q->next;
q->next = p;
free(L2);
}
else{
L3 = L2;
L3->next = p;
while (p->next != L1)
p = p->next;
p->next = q;
free(L1)
}
}
G
(采用邻接表存储)的连通分量的个数思路:利用 DFS 算法一次遍历图中的一个连通分量,统计遍历完图总共调用 DFS 算法的次数即该图的连通块的个数。
// 从顶点 v 出发深度优先访问 G 的一个连通块
void DFS(Graph G, int v){
visited[v] = TRUE; // 标记访问 v 顶点
for (w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G, v, w)){
if (!visited[w])
DFS(G, w); // 对 v 的尚未访问的邻接顶点调用 DFS 访问
}
}
int GetConnSubGraphNum(Graph G){
int count = 0;
// 初始化访问标记数组
for (v=0; v<G.vexnum; v++)
visited[v] = FALSE;
for (v=0; v<G.vexnum; v++){
if (!visited[v]){
count++; // 连通块数量+1
DFS(G, v);
}
}
return count;
}
T
。统计二叉树 T
中结点的个数思路:一棵树的总结点数等于它的左子树上的结点数加上右子树上的节点数再加上其本身,空树的结点数为0,利用递归思想,求树 T 的总结点数
int CountNode (BiTree T){
if (T == NULL)
return 0; // 空树的结点数为 0
else
// 非空树结点数等于它的左子树上的结点数加上右子树上的结点数再加上其本身
return (1+CountNode(T->lc)+CountNode(T->rc));
}
(a1, a2, … , an)
设计把所有偶数移动所有奇数前面。(时间最少,辅助空间最多)思路:采用快速排序思想,整个算法只需仿照快速排序的第一趟,只是判别条件不再是当前元素和枢轴值比较而是判断当前元素的奇偶性。时间复杂度O(n), 空间复杂度为O(1)
void sheft(int *a, int n){
// 将长度为n的线性表a中的偶数移动到奇数前面
int temp = a[0];
int i = 0, j = n-1; // 记录当前区间的小标
while (i<j){
while(i<j && a[j]%2!=0)
j--; // 查找从前区间的最后面的一个偶数
a[i] = a[j]; // 将这个偶数移动到当前区间的最前面
while (i<j && a[i]%2 == 0)
i++; // 查找从前区间的最前面的一个奇数
a[j] = a[i]; // 将这个奇数移动到当前区间的最后面
}
a[i] = temp;
}
X
的 结点为根的子树的深度思路:求二叉树的深度可以递归求左右子树的深度,然后取其较大者加一
int getDeepth(BiTree T){
// 求二叉树 T 的深度
int ld, rd;
if (T == NULL)
return 0; // 空树
ld = getDeepth(T->lchild);
rd = getDeepth(T->rchild);
return (ld>rd ?ld:rd)+1;
}
void visit(BiTree, int x){
// 对结点进行访问,如果结点权值为 x 时,打印以该节点的根的子树的深度
if (T->data == x){
printf("%d\n", getDeepth(T));
}
}
// 先序遍历二叉树
void preOrderVisit(BiTree T, int x){
if (T!=NULL){
visit(T, x);
preOrderVisit(T->lchild);
preOrderVisit(T->rchild);
}
}
思路:对于二叉排序树来说,其中序遍历序列为一个递增有序序列。因此,对给定的二叉树进行中序遍历,如果始终能保持前一个值比后一个值小,则说明该二叉树是一棵二叉排序树
KeyType predt = -32767; // predt 为全局变量。保存当前节点中序前驱的值
// 初值为负无穷
// 若二叉树 bt 是二叉排序树 jugedBST 返回值 1,否则返回 0
int JugedBST(BiTree bt){
int b1, b2;
if (bt == NULL) // 空树
return 1;
else{
b1 = JugedBST(bt->lchild); // 判断左子树是否是二叉排序树
if (b1==0 || predt>=bt->data) // 若左子树返回值0或前驱大于等于当前节点
return 0; // 则不是二叉排序树
predt = bt->data; // 保存当前节点的关键字
b2 = JugedBST(bt->rchild); // 判断右子树
return b2; // 返回右子树的结果
}
}
思路: 首先初始化邻接表。遍历邻接矩阵,在遍历顶点 i 时,若发现v[i][j] 不等于 0 或无穷,则表示i, j有边,将这条边节点插入到邻接表的第i个表头节点之前。
int INF = 32767; // 全局变量表示无穷
void Convert(int G[N][N], ALGraph &ALGraph){
// 此算法将邻接矩阵 G 转换为邻居表 ALGraph
for (i=0; i<N; i++){
for (i=0; j<N; j++){
if (G[i][j]!=0 && G[i][j]!=INF){ // 顶点 i 和 j 有边
ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode)); // 创建边表节点 p
p->adjvex = j;
p->next = ALGraph[i].frist; // 将 p 插入顶点表节点之后
ALGraph[i].first = p;
}
}
}
}
G = (V, E)
其中 G
包含 n
个点和 m
条边。统计 G
中连通块分量的个数思路:由于深度优先搜素算法每次能遍历一个连通块,故只需统计调用 DFS 调用的次数即可。
int count = 0; // 全局变量,记录图G连通块的数目
bool visited[MAX_VERTEX_NUM]; // 访问标记数组
void CountConnectedBlock(Graph G){
// 该算法统计图 G 的连通块数目
for (v=0; v<G.vexnum; v++)
visited[v] = FALSE; // 初始化访问标记数组
for (v=0; v<G.vexnum; v++){
// 如果没有访问,从该顶点出发,调用 DFS,访问该顶点所在的连通块,并将连通数量+1
if (!visited[v]){
count++;
DFS(G, v);
}
}
}
void DFS(Graph G, int v){
// 从顶点 v 出发,采用递归思想,深度优先遍历图 G
visit(v); // 访问顶点 v
visited[v] = TRUE; // 设已访问标记、
for (w=FirstNeigbor(G, v); w>=0; w=NextNeighbor(G, v, w)){
if (!visited[w]){ // w 为 v 的尚未访问邻接节点
DFS(G, w);
}
}
}
TODO
TODO
T
设计算法复制二叉树 T
TODO
G = (V, E)
和 G
中两个顶点 S
, T
求一条顶点 t
到顶点 S
的简单路径TODO
T
(非递归)TODO
A
和 B
分别用线性表 L1
和 L2
存储。算法求解 A∪BTODO
后缀表达式为
ABC *+ DE /-` 设计算法将原表达式转为为后缀表达式TODO
T1
和 T2
判断 T1
与 T2
是否相同(二叉树)TODO
La
、Lb
两个带头结点单链表表示的多项式)TODO
TODO