数据结构算法复习

考前整理的算法，也顺便放到博客上吧ヾ(•ω•`)o

# 数据结构代码复习

# 3.单链表逆置

带头结点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int Inverse_Link(LinkList *L)
{
    LinkList *cur, *p;
    if (L->next && L->next->next)
    {
        p = L->next->next;
        L->next->next = NULL;
        while (p)
        {
            cur = L->next;
            L->next = p;
            p = p->next;
            L->next->next = cur;
        }
    }
    return 0;
}

# 5.双向链表

双链表定义：

1
2
3
4
5
6


typedef struct DuLinkList
{
    int data;
    struct DuLinkList *prior;
    struct DuLinkList *next;
} DuLinkList;

遍历：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void Printlist_DuL(DuLinkList *L)
{
    DuLinkList *s;
    s = L->next;
    if (L->next != NULL)
    {
        printf("当前的双向链表值为：");
        do
        {
            printf("%d ", s->data);
            s = s->next;
        } while (s != NULL);
    }
    printf("\n");
}

交换：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


int ListSwap_DuL(DuLinkList *L, int i)
{
    //在带头结点的双向链表中交换第i个，i+1个位置的元素
    DuLinkList *p = L, *q;
    int j = 0;
    while (p && j < i - 1)
    {
        p = p->next;
        j += 1;
    }
    if (!p || j > i - 1)
        return -1;
    p = p->next;
    q = p->next;
    p->prior->next = q;  //1  ->q    p    2
    q->prior = p->prior; //1<-->q    p    2
    p->next = q->next;   //1<-->q    p  ->2
    q->next->prior = p;  //1<-->q    p<-->2
    q->next = p;         //1<-->q  ->p<-->2
    p->prior = q;        //1<-->q<-->p<-->2
    return 0;
}

# 6.链表回文

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


bool isPalindrome(struct ListNode *head)
{
    Lstack *s;
    int e;
    struct ListNode *p = head;
    s = (Lstack *)malloc(sizeof(Lstack));
    Initlist_Stack(s);
    while (p)
    {
        push(s, p->val);
        p = p->next;
    }
    p = head;
    while (p)
    {
        e = pop(s);
        if (p->val != e)
            break;
        p = p->next;
    }
    if (p)
        return false;
    else
        return true;
}

# 7-1.链队列

定义：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


typedef struct QNode //队列
{
    int data;
    struct QNode *next;
} QNode;

typedef struct LinkQueue //对列相关的指针
{
    QNode *front; //对头指针
    QNode *rear;  //队尾指针
} LinkQueue;

插入：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


int EnQueue(LinkQueue *q, int e)
{
    //[入队]将元素e放入队尾，带头结点
    QNode *p;
    p = (QNode *)malloc(sizeof(QNode));
    p->data = e;
    p->next = NULL;
    q->rear->next = p;
    q->rear = p;
    return 0;
}

# 7-2.循环链表

插入和普通单链表没区别，这里就列举部分

1
2
3
4


    s = (LinkList *)malloc(sizeof(LinkList));
    s->data = e;
    s->next = p->next;
    p->next = s;

# 8.求二叉树各种数的算法

# （1）求高度

高度很简单，来个递归就完事了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int BiTreeHeight(BiTNode *T)
{
    //求二叉树的高度
    int treeHeight = 0;
    if (T != NULL)
    {
        int leftHeight = BiTreeHeight(T->lchild);
        int rightHeight = BiTreeHeight(T->rchild);
        treeHeight = leftHeight >= rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    return treeHeight;
}

# （2）求叶子数

叶子数也一样，递归永远滴神

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


void BiTreeLeafCount(BiTNode *T, int *count)
{
    //求二叉树叶子结点数
    if (!T)
        return;
    if (T->lchild == NULL && T->rchild == NULL)
        *count += 1;
    BiTreeLeafCount(T->lchild, count);
    BiTreeLeafCount(T->rchild, count);
}

# （3）求结点数

这不就遍历嘛，直接看下面吧=￣ω￣=

# 9.二叉树的中序遍历

递归：

1
2
3
4
5
6
7
8
9


int InOrderTraverse(BiTNode *T)
{
    //中序遍历二叉树T的递归算法
    if (T == NULL)
        return 0;
    InOrderTraverse(T->lchild);
    printf("%c ", T->data);
    InOrderTraverse(T->rchild);
}

非递归（重要）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


int inorder(BiTNode *T)
{
    //中序遍历二叉树T的非递归算法
    BiTNode *s[MAXSIZE + 1];
    int top = 0;
    while (T != NULL || top != 0)
    {
        while (T != NULL)
        {
            s[++top] = T;
            T = T->lchild;
        }
        if (top != 0)
        {
            T = s[top--];
            printf("%c ", T->data);
            T = T->rchild;
        }
    }
    return 0;
}

# 10.二叉排序树

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


int Search_BST(BSTree t, int key, BSTree f, BSTree *p)
{
    //在指针t所指的二叉排序树上查找key，成功则p指向该元素数据结点并返回0
    //否则p指向查找路径上最后一个结点并返回1，f指向T的双亲，初始值为NULL
    if (!t)
    {
        *p = f;
        return 1;
    }
    else if (key == t->data)
    {
        *p = t;
        return 0;
    }
    else if (key < t->data)
    {
        return Search_BST(t->lchild, key, t, p);
    }
    else
        return Search_BST(t->rchild, key, t, p);
}

int Insert_BST(BSTree *t, int key)
{ //二叉排序树的插入，当不存在key时插入并返回0，否则返回1
    BSTree p, s;
    p = NULL;
    if (Search_BST(*t, key, NULL, &p))
    {
        s = (BSTree)malloc(sizeof(BSTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if (!p)
            *t = s;
        else if (key < p->data)
            p->lchild = s;
        else
            p->rchild = s;
        return 0;
    }
    else
        return 1;
}

# 14.图的遍历

# （1）深度优先

入栈时打印结点信息

递归：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


void DFS(ALGraph *G, int v, int visited[])
{
    ArcNode *p;
    int w, i;
    visited[v] = 1;
    printf("%d ", v);
    p = G->vertices[v].firstarc;
    while (p != NULL)
    {
        w = p->adjvex;
        if (visited[w] == 0)
            DFS(G, w, visited);
        p = p->nextarc;
    }
}

非递归：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


void DFS1(ALGraph *G, int v)
{
    ArcNode *p;
    int w, i;
    int visited[MAX_VERTEX_NUM];
    ArcNode *s[MAX_VERTEX_NUM]; //顺序栈
    int top = 0;
    for (i = 1; i <= G->vexnum; i++)
        visited[i] = 0; //访问标志数组初始化
    visited[v] = 1;
    printf("%2d", v);
    p = G->vertices[v].firstarc;
    while (p != NULL || top != 0)
    {
        while (p != NULL)
        {
            w = p->adjvex;
            if (visited[w] == 0)
            {
                printf("%2d", w);
                visited[w] = 1;
                s[++top] = p;
                p = G->vertices[w].firstarc;
            }
            else
                p = p->nextarc;
        }
        if (top != 0)
        {
            p = s[top--];
            p = p->nextarc;
        }
    }
}

# （2）广度优先

出队列时打印结点信息

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


void BFS(ALGraph *G, int v)
{
    ArcNode *p;
    int w, i;
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0; // 定义循环队列
    int visited[MAX_VERTEX_NUM];
    for (i = 1; i <= G->vexnum; i++)
        visited[i] = 0; //访问标志数组初始化
    printf("%2d", v);   //输出被访问顶点的编号
    visited[v] = 1;     //置已访问标记
    rear = (rear + 1) % MAX_VERTEX_NUM;
    queue[rear] = v;      //v进队
    while (front != rear) // 队列不空时循环
    {
        front = (front + 1) % MAX_VERTEX_NUM;
        w = queue[front];            //出队并赋给w
        p = G->vertices[w].firstarc; //找w的第一个的邻接点
        while (p != NULL)
        {
            if (visited[p->adjvex] == 0)
            {
                printf("%2d", p->adjvex); //访问之
                visited[p->adjvex] = 1;
                rear = (rear + 1) % MAX_VERTEX_NUM; //相邻顶点进队
                queue[rear] = p->adjvex;
            }
            p = p->nextarc; //找下一个邻接顶点
        }
    }
}

# 15.双向冒泡

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


void BubbleSort1(int R[], int n)
{ //双向冒泡
    int i, j, lastExchange, lastExchange1, i1, temp;
    i = n; //i 指示无序序列中最后一个记录的位置
    i1 = 1;
    while (i > i1)
    {
        lastExchange = 1;  //记录正序最后一次交换发生的位置
        lastExchange1 = n; //记录逆序最后一次交换发生的位置
        for (j = i1; j < i; j++)
            if (R[j] > R[j + 1])
            {
                temp = R[j];
                R[j] = R[j + 1];
                R[j + 1] = temp; //逆序时交换
                lastExchange = j;
            }
        for (j = lastExchange; j > i1; j--)
            if (R[j] < R[j - 1])
            {
                temp = R[j];
                R[j] = R[j - 1];
                R[j - 1] = temp; //逆序时交换
                lastExchange1 = j;
            }
        i = lastExchange;
        i1 = lastExchange1;
    }
}