数据结构算法背诵
一、线性表
1. 逆转顺序表中的所有元素
算法思想：第一个元素和最后一个元素对调，第二个元素和倒数第二个元素对调，……，依此类推。
void Reverse(int A[], int n)
{
int i, t;
for (i=0; i < n/2; i++)
{
t = A[i];
A[i] = A[n-i-1];
A[n-i-1] = t;
}
}
2. 删除线性链表中数据域为 item 的所有结点
算法思想：先从链表的第 2 个结点开始，从前往后依次判断链表中的所有结点是否满足条件，若某个
结点的数据域为 item，则删除该结点。最后再回过头来判断链表中的第 1 个结点是否满足条件，若
满足则将其删除。
void PurgeItem(LinkList &list)
{
LinkList p, q = list;
p = list->next;
while (p != NULL)
{
if (p->data == item) {
q->next = p->next;
free(p);
p = q->next;
} else {
q = p;
p = p->next;
}
}
if (list->data == item)
{
q = list;
list = list->next;
free(q);
}
}
2
3. 逆转线性链表
void Reverse(LinkList &list)
{
LinkList p, q, r;
p = list;
q = NULL;
while (p != NULL)
{
r = q;
q = p;
p = p->next;
q->next = r;
}
list = q;
}
4. 复制线性链表（递归）
LinkList Copy(LinkList lista)
{
LinkList listb;
if (lista == NULL)
return NULL;
else {
listb = (LinkList)malloc(sizeof(LNode));
listb->data = lista->data;
listb->next = Copy(lista->next);
return listb;
}
}
5. 将两个按值有序排列的非空线性链表合并为一个按值有序的线性链表
LinkList MergeList(LinkList lista, LinkList listb)
{
LinkList listc, p = lista, q = listb, r;
// listc 指向 lista 和 listb 所指结点中较小者
if (lista->data <= listb->data) {
listc = lista;
r = lista;
p = lista->next;
} else {
listc = listb;
r = listb;
q = listb->next;
}
while (p != NULL && q != NULL)
{
if (p->data <= q->data) {
r->next = p;
r = p;
p = p->next;
} else {
r->next = q;
r = q;
q = q->next;
}
}
// 将剩余结点（即未参加比较的且已按升序排列的结点）链接到整个链表后面
r->next = (p != NULL) ? p : q;
return listc;
}
3
二、树
1. 二叉树的先序遍历（非递归算法）
算法思想：若 p 所指结点不为空，则访问该结点，然后将该结点的地址入栈，然后再将 p 指向其左孩
子结点；若 p 所指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址），将 p 指向其右孩子
结点。重复上述过程，直到 p = NULL 且堆栈为空，遍历结束。
#define MAX_STACK 50
void PreOrderTraverse(BTree T)
{
BTree STACK[MAX_STACK], p = T;
int top = -1;
while (p != NULL || top != -1)
{
while (p != NULL)
{
VISIT(p);
STACK[++top] = p;
p = p->lchild;
}
p = STACK[top--];
p = p->rchild;
}
}
2. 二叉树的中序遍历（非递归算法）
算法思想：若 p 所指结点不为空，则将该结点的地址 p 入栈，然后再将 p 指向其左孩子结点；若 p 所
指向的结点为空，则从堆栈中退出栈顶元素（某个结点的地址）送 p，并访问该结点，然后再将 p 指
向该结点的右孩子结点。重复上述过程，直到 p = NULL 且堆栈为空，遍历结束。
#define MAX_STACK 50
void InOrderTraverse(BTree T)
{
BTree STACK[MAX_STACK], p = T;
int top = -1;
while (p != NULL || top != -1);
{
while (p != NULL)
{
STACK[++top] = p;
p = p->lchild;
}
p = STACK[top--];
VISIT(p);
p = p->rchild;
}
}
4
3. 二叉树的后序遍历（非递归算法）
算法思想：当 p 指向某一结点时，不能马上对它进行访问，而要先访问它的左子树，因而要将此结点
的地址入栈；当其左子树访问完毕后，再次搜索到该结点时（该结点地址通过退栈得到），还不能对
它进行访问，还需要先访问它的右子树，所以，再一次将该结点的地址入栈。只有当该结点的右子
树访问完毕后回到该结点时，才能访问该结点。为了标明某结点是否可以访问，引入一个标志变量
flag，当 flag = 0 时表示该结点暂不访问，flag = 1 时表示该结点可以访问。flag 的值随同该结点的地
址一起入栈和出栈。因此，算法中设置了两个堆栈，其中 STACK1 存放结点的地址，STACK2 存放
标志变量 flag，两个堆栈使用同一栈顶指针 top，且 top 的初始值为 −1。
#define MAX_STACK 50
void PostOrderTraverse(BTree T)
{
BTree STACK1[MAX_STACK], p = T;
int STACK2[MAX_STACK], flag, top = -1;
while (p != NULL || top != -1)
{
while (p != NULL) {
STACK1[++top] = p;
STACK2[top] = 0;
p = p->lchild;
}
p = STACK1[top];
flag = STACK2[top--];
if (flag == 0) {
STACK1[++top] = p;
STACK2[top] = 1;
p = p->rchild;
} else {
VISIT(p);
p = NULL;
}
}
}
4. 二叉树的按层次遍历
算法思想：设置一个队列，首先将根结点（的地址）入队列，然后依次从队列中退出一个元素，每
退出一个元素，先访问该元素所指的结点，然后依次将该结点的左孩子结点（若存在的话）和右孩
子结点（若存在的话）入队列。如此重复下去，直到队列为空。
#define MAX_QUEUE 50
void LayeredOrderTraverse(BTree T)
{
BTree QUEUE[MAX_QUEUE], p;
int front, rear;
if (T != NULL)
{
QUEUE[0] = T;
front = -1;
rear = 0;
while (front < rear)
{
p = QUEUE[++front];
VISIT(P);
if (p->lchild != NULL)
QUEUE[++rear] = p->lchild;
if (p->rchild != NULL)
QUEUE[++rear] = p->rchild;
}
}
}
5
5. 建立二叉树（从键盘输入数据，先序遍历递归算法）
BTree CreateBT()
{
char ch;
BTree T;
sacnf("%c", &ch);
if (ch == ' ')
return NULL;
else {
T = (BTree)malloc(sizeof(BTNode));
T->data = ch;
T->lchild = CreateBT();
T->rchild = CreateBT();
return T;
}
}
6. 建立二叉树（从数组获取数据）
BTree CreateBT(int A[], int i, int n)
{
BTree p;
if (i > n)
return NULL;
else {
p = (BTree)malloc(sizeof(BTNode));
p->data = A[i];
p->lchild = CreateBT(A, 2*i, n);
p->rchild = CreateBT(A, 2*i+1, n);
return p;
}
}
T = CreateBT(A, 1, n);
--------------------------------------------------------
BTree CreateBT(int A[], int n)
{
int i;
BTree *pT;
// 对应 n 个结点申请可容纳 n 个指针变量的内存空间
pT = (BTree *)malloc(sizeof(BTree)*n);
// 若数组中的某个元素不等于零，则申请相应的结点空间并进行赋值
for (i=1; i <= n; i++)
{
if (A[i] != 0) {
pT[i] = (BTree)malloc(sizeof(BTNode));
pT[i]->data = A[i];
} else {
pT[i] = NULL;
}
}
// 修改结点的指针域的内容，使父结点指向左、右孩子结点
for (i=1; i <= n; i++)
{
if (pT[i] != NULL)
{
pT[i]->lchild = pT[2*i];
pT[i]->rchild = pT[2*i+1];
}
}
}
