数据结构与算法练习

专升本结束了，纪念一下当时为了数据结构的考试而写的简单算法题目。

头文件

LinkList.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <stdio.h>
#include <stdlib.h>

typedef struct LinkNode{
    int data;
    struct LinkNode *next;
}LinkNode;

LinkNode *initLinkNode(){
    LinkNode *head = (LinkNode *) malloc(sizeof(LinkNode));
    head->next = NULL;
    return head;
}

//在节点后插入新节点
void insertNode(LinkNode *node,int x){
    LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));
    newNode->data = x;
    newNode->next = node->next;
    node->next = newNode;

}

LinkNode *initLinkList(){
    int array[] = {5,3,3,3,4,5,4,6,7,0,8,9};
    LinkNode *head = initLinkNode();
    LinkNode *p = head;
    // printf("%d",sizeof(array));
    for (int i = 0; i < (sizeof(array)/4); i++)
    {
        insertNode(p,array[i]);
        p=p->next;
    }
    return head;
    
}
//将数组里的数字插入到链表中
LinkNode *initLinkListByArray(int array[],int length){
    LinkNode *head = initLinkNode();
    LinkNode *p = head;
    for (int i = 0; i < length; i++)
    {
        insertNode(p,array[i]);
        p=p->next;
    }
    return head;
    
}

void printLinkList(LinkNode *head){
    LinkNode *p = head;
    printf("LinkList =");
    while (p->next != NULL)
    {
        p = p->next;
        printf(" %d ->",p->data);
    }
    printf(" NULL\n");
}

BinaryTree.h

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <stdio.h>
#include <stdlib.h>

typedef struct BinaryTree
{
    int data;
    struct BinaryTree *lchild;
    struct BinaryTree *rchild;
}BinaryTree;

typedef struct Queue{
    BinaryTree *node;
    struct Queue *next;
}Queue;

typedef struct QueuePointer{
    Queue *head;
    Queue *tail;
}QueuePointer;

//初始化树
BinaryTree* initTreeNode(int data)
{
    BinaryTree *tree = (BinaryTree *)malloc(sizeof(BinaryTree));
    tree->data = data;
    tree->lchild = NULL;
    tree->rchild = NULL;
    return tree;
}

//排序二叉树的节点插入
void insert(BinaryTree *tree, int data)
{
    if(tree->data > data)
    {
        if(tree->lchild == NULL)
        {
            tree->lchild = initTreeNode(data);
        }
        else
        {
            insert(tree->lchild, data);
        }
    }
    else
    {
        if(tree->rchild == NULL)
        {
            tree->rchild = initTreeNode(data);
        }
        else
        {
            insert(tree->rchild, data);
        }
    }
}

BinaryTree *initBinaryTree(){
    int array[] = {5, 3, 7, 2, 4, 6, 8, 10, 15};
    //将数组里的数字插入到二叉树中
    BinaryTree *tree = initTreeNode(array[0]);
    for(int i = 1; i < sizeof(array)/4; i++)
    {
        insert(tree, array[i]);
    }
    return tree;
}

BinaryTree *initBinaryTreeByDiy(int array[],int length){
    //将数组里的数字插入到二叉树中
    BinaryTree *tree = initTreeNode(array[0]);
    for(int i = 1; i < length; i++)
    {
        insert(tree, array[i]); 
    }
    return tree;
}


Queue *getQueueNode(BinaryTree *node){
    Queue *queue = (Queue *)malloc(sizeof(Queue));
    queue->node = node;
    queue->next = NULL;
    return queue;
}

//二叉树节点入队
void enQueue(QueuePointer *queuePointer, BinaryTree *node)
{
    Queue *queue = getQueueNode(node);
    if(queuePointer->head == NULL)
    {
        queuePointer->head = queue;
        queuePointer->tail = queue;
    }
    else
    {
        queuePointer->tail->next = queue;
        queuePointer->tail = queue;
    }
}

//二叉树节点出队
BinaryTree *deQueue(QueuePointer *queuePointer)
{
    if(queuePointer->head == NULL)
    {
        return NULL;
    }
    else
    {
        Queue *queue = queuePointer->head;
        BinaryTree *node = queue->node;
        printf("%d ", node->data);
        queuePointer->head = queue->next;
        free(queue);
        return node;
    }
}

//层序遍历打印二叉树
void printBinaryTree(BinaryTree *tree)
{
    //初始化列队头节点以及指针
    QueuePointer *queuePointer = (QueuePointer *)malloc(sizeof(QueuePointer));
    queuePointer->head = NULL;
    queuePointer->tail = NULL;
    enQueue(queuePointer, tree);
    while(queuePointer->head != NULL)
    {
        BinaryTree *node = deQueue(queuePointer);
        if(node->lchild != NULL)
        {
            enQueue(queuePointer, node->lchild);
        }
        if(node->rchild != NULL)
        {
            enQueue(queuePointer, node->rchild);
        }
    }
}

练习

  • 去除重复链表节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void remove_repeat_node(LinkNode *head){
    LinkNode *p,*q,*x;
    for(p = head->next,q = p; p->next; p = p->next,q = p){
        for(LinkNode *n = q->next; n->next;){
            if(n->data == p->data){
                q->next = n->next;
                free(n);
                n = q->next;
            } else{
                q = n;
                n = n->next;
            }
        }
    }
}
  • 两个有序链表合并，并且保持有序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
LinkNode *intergrate(LinkNode *node1,LinkNode *node2){
    LinkNode *p1 = node1;
    LinkNode *p2 = node2;

    while (node1->next)
    {
        p1=node1->next;
        while (p1->data >= p2->next->data){
            p2 = p2->next;
        }
        node1->next = p1->next;
        p1->next = p2->next;
        p2->next = p1;
    }
    return node2;
}
  • 判断两颗二叉树是否相同
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void equal(BinaryTree *node1,BinaryTree *node2,int *p){
    // printf("%d",*p);
    if(*p == 0) return;
    if(node1 == NULL || node2 == NULL){
        if(node1 == NULL && node2 != NULL) *p = 0;
        if(node2 == NULL && node1 != NULL) *p = 0;
        return ;
    }
    printf("%d - %d \n",node1->data,node2->data);
    if(node1->data == node2->data){
        equal(node1->lchild,node2->lchild,p);
        equal(node1->rchild,node2->rchild,p);
    } else{
        *p = 0;
    }
}
  • 二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int binarySearch(int x,int array[],int length){
    int front = 0;
    int trail = length -1;
    
    while(front<=trail){
        int mid = (front+trail)/2;

        if(array[mid] == x){
            return mid+1;
        }

        if(array[mid] > x){
            trail = mid-1;
        }else{
            front = mid+1;
        }
    }

    return 0;
}
  • 判断二叉树是否为排序二叉树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int isSortBinaryTree(BinaryTree *node){
    if(node->lchild == 0 && node->rchild == 0) return 1;
    int l = 1,r = 1;

    if(node->lchild){
        if(node->lchild->data <= node->data) l = isSortBinaryTree(node->lchild);
        else return l = 0;
    }

    if(node->rchild){
        if(node->rchild->data > node->data) r = isSortBinaryTree(node->rchild);
        else return r = 0;
    }

    return l&&r?1:0;
}
  • 链表的直接插入排序
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
void insertionSort(LinkNode *head){
    LinkNode *p,*q,*i;
    p = head->next;

    while(p->next != NULL){

        while(p->next != NULL && p->next->data >= p->data){
            // 先判空再条件判断，否则会有空指针异常
            p = p->next;

        }

        q = p->next;
        i = head;
        while(i->next->data <= q->data && i->next != q){
            i = i->next;
        }

        if(i->next == q) continue;

        p->next = q->next;

        q->next = i->next;
        i->next = q;
        printLinkList(head);
    }
}
  • 链表的简单选择排序
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
void choiseSort(LinkNode *head){
    LinkNode *q,*min;

    q = head;

    while(q->next){
        min = q; //最小值的前一个节点
        for(LinkNode *p = min->next; p->next; p = p->next){
            if(p->next->data < min->next->data){
                min = p;
            }
        }
        printf("%d\n",min->next->data);

        if(min == q){
            q = q->next;
            continue;
        }
        
        LinkNode *m = min->next;
        LinkNode *n = q->next;

        min->next = m->next;
        m->next = q->next;
        q->next = m;
        q = q->next;
        // 如果min和n指向同一节点，n无法交换到min后需要跳过
        // 这种情况出现于min（最小值的前一个节点）刚好为q的下一个节点
        if(min == n) continue; 

        q->next = n->next;
        n->next = min->next;
        min->next = n;
    }
}
  • 求所有子串
1
2
3
4
5
6
7
8
9
10
void substring(char string[],int length){
    for(int i = 1; i <= length;i++){
        for(int j = 0; j+i <= length;j++){
            for(int n = j; n < j+i; n++){
                printf("%c",string[n]);
            }
            printf("\n");
        }
    }
}
  • 查找二叉树结点所在层数
1
2
3
4
5
6
7
8
9
10
11
12
13
int serchLevel(BinaryTree *node,int x,int count){
    if(node == NULL) return 0;
    count++;
    if(node->data == x){
        return count;
    }else{
        int n = serchLevel(node->lchild,x,count);
        int t = serchLevel(node->rchild,x,count);
        if(n) return n;
        else if(t) return t;
        else return 0;
    }
}
  • 设计一个在链式存储结构上统计二叉树中节点个数的算法
1
2
3
4
5
6
7
int countNode(BinaryTree *node){
    if(node == 0) return 0;
    if(node->lchild == 0 && node->rchild == 0) return 1;

    // 左节点加右节点 并且加上自身
    return countNode(node->lchild)+countNode(node->rchild)+1;
}
  • 设计一个算法将无向图的邻接矩阵转化为对应链表的算法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int **transformToMatrix(LinkNode *array[],int count){
    // 初始化矩阵
    int **matrix = (int **)malloc(count * sizeof(int *));
    for(int i = 0; i < count; i++){
        matrix[i] = (int *)malloc(count * sizeof(int));
        for(int j = 0; j < count; j++){
            matrix[i][j] = 0;
        }
    }

    for(int i = 0; i < count; i++){
        if(array[i]->next == NULL) continue;
        for(LinkNode *p = array[i]->next; p->next; p = p->next){
            matrix[i][p->data] = 1;
        }
    }
    
    return matrix;
}
  • 将所有偶数移到奇数面前
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void moveOddNumber(int array[],int length){
    int left = 0;
    int right = length -1;

    while(left < right){
        while(left < right && array[left]%2 != 0) left++;
        while(left < right && array[right]%2 == 0) right--;
 
        int t = array[left];
        array[left] = array[right];
        array[right] = t;
    }

    for(int i = 0; i < length; i++){
        printf("%d ",array[i]);
    }
}