数据结构算法背诵
一、线性表
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;
相关推荐：
loading