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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176

// 栈的基本 ADT 函数有：

// 1. 置空栈。函数原型为: `void MakeEmpty(SqStack s);`
// 2. 元素e入栈。函数原型为: `void Push(SqStack s,ElemType e);`
// 3. 出栈，返回栈顶元素。函数原型为: `ElemType pop(SqStack s);`
// 4. 判断栈是否为空。函数原型为: `int isEmpty(SqStack s);`
#include <iostream>

using namespace std;

#define StackSize 10
typedef int ElemType;

// 栈结构
class SqStack {
private:
    ElemType data[StackSize];
    int top;
public:
    SqStack(): top(-1) {}

    // 1. 置空栈
    void makeEmpty() {
      this->top = -1;
    }

    // 2. 元素e入栈
    void push(ElemType e) {
      if (this->isFull()) {
        std::cout << "栈满" << std::endl;
        return;
      }

      this->data[++this->top] = e;
    }

    // 3. 出栈，返回栈顶元素
    ElemType pop() {
      if (this->isEmpty()) {
        std::cout << "栈空" << std::endl;
        return -1;
      }

      return this->data[this->top--];
    }

    // 4. 判断栈是否为空
    bool isEmpty() {
      return this->top == -1;
    }

    // 5. 栈满
    int isFull() {
      return this->top == StackSize;
    }
};

// 队列的基本ADT函数有：

// （1）元素e入队。函数原型为：void enQueue(Queue q,ElemType e);
// （2）出队，返回队头元素。函数原型为：ElemType deQueue(Queue q);（
// （3）判断队是否为空。函数原型为：int isEmpty(Queue q);
#define QueueSize 10

// 队列结构
class Queue {
private:
    ElemType data[QueueSize];
    int front, real;
public:
    Queue(): front(0), real(0) {}

    // 队列是否已满
    int isQueueFull() {
      return (this->real + 1) % QueueSize == this->front;
    }

    // 元素e入队
    void enQueue(ElemType e) {
      if (isQueueFull()) {
        std::cout << "队列满" << std::endl;
        return;
      }

      this->data[this->real] = e;
      // 循环意义下的 +1
      this->real = (this->real + 1) % QueueSize;
    }

    // 出队列
    ElemType deQueue() {
      if (this->isEmpty()) {
        std::cout << "队列空" << std::endl;
        return -1;
      }

      ElemType e = this->data[this->front];
      this->front = (this->front + 1) % QueueSize;

      return e;
    }

    // 判断队列是否为空
    int isEmpty() {
      return this->front == this->real;
    }
};

// 队列元素倒序, 这里注意要用 & 取引用才有副作用
void reverseQueue(Queue &q) {
  SqStack s;
  int val;

  while (!q.isEmpty()) {
    val = q.deQueue();
    s.push(val);
  }

  while (!s.isEmpty()) {
    val = s.pop();
    q.enQueue(val);
  }
}

// (1) 编程实现队列和栈的ADT函数
// (2) 仅用队列和栈的ADT函数和少量工作变量，编写将队列Q的所有元素逆置的函数。
// (3) 测试该函数
int main() {
  cout << "准备测试 stack 数据结构" << endl;
  SqStack s;

  cout << "[stack] 1. test SqStack.push" << endl;
  int testData1[] = {109, 108, 107};
  for (int i = 0; i < 3; i++) {
    s.push(testData1[i]);
  }

  cout << "[stack] 2. test SqStack.isEmpty: " << (s.isEmpty() ? "" : "非") << "空栈" << endl;
  cout << "[stack] 3. test SqStack.pop: " << s.pop() << endl;
  cout << "[stack] 4. test SqStack.makeEmpty" << endl;
  s.makeEmpty();

  cout << "[stack] 5. check stack now is empty: " << (s.isEmpty() ? "" : "非") << "空栈" << endl;
  cout << "============================================" << endl;

  cout << "准备测试 queue 数据结构" << endl;
  Queue q;

  cout << "[queue] 1. test SqStack.push" << endl;
  for (int i = 0; i < 3; i++) {
    q.enQueue(testData1[i]);
  }

  cout << "[queue] 2. test Queue.isEmpty: " << (q.isEmpty() ? "空队列" : "非空队列") << endl;
  while (!q.isEmpty()) {
    cout << "[queue] 3. test Queue.pop: " << q.deQueue() << endl;
  }

  cout << "[queue] 4. check queue now is empty: " << (q.isEmpty() ? "空队列" : "非空队列") << endl;
  cout << endl << endl;
  cout << "============================================" << endl;

  cout << "仅用队列和栈的ADT函数和少量工作变量，编写将队列Q的所有元素逆置的函数。" << endl;
  const int reverseTestData[] = {11,12,13,14,15};
  for (int i = 0; i < 5; i++) {

    q.enQueue(reverseTestData[i]);
  }
  reverseQueue(q);

  while(!q.isEmpty()) {
    cout << "reverseQueue deQueue: " << q.deQueue() << endl;
  }

  return 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
28
29
30
31
32
33
34

#include <iostream>
using namespace std;

void SelectSort(int arr[], int n) {
  int k;
  for (int i = 0; i < n; i++) {
    k = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < arr[k]) {
        k = j;
      }
    }

    if (k != i) {
      swap(arr[i], arr[k]);
      int temp = arr[i];
      arr[i] = arr[k];
      arr[k] = temp;
    }
  }
}

int main() {
  int arr[] = {4, 3, 2, 9, 8, 6, 7, 1, 5, 10};
  int n = sizeof(arr) / sizeof(arr[0]);
  cout << sizeof(arr[0]) << "\n";

  SelectSort(arr, n);

  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
}

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

void InsertSort(int arr[], int n) {
  int i, j, tmp;
  // 对顺序表做直接插入排序
  for(i = 1; i < n; i++) {
    // 当前值比上一个值小，则交换位置
    if (arr[i] < arr[i - 1]) {

      tmp = arr[i];
      // 对有序区逐项向后 diff，寻找合适的插入位置
      for(j = i - 1; j >= 0 && tmp < arr[j]; j--) {
        arr[j + 1] = arr[j];
      }
      arr[j + 1] = tmp;
    }
  }
}

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

void BubbleSort(int *arr, int n) {
  int i, j, flag, temp;
  for (i = 0; i < n; i++) {
    flag = 0;

    // 从右向左对比
    for (j = n - 1; j >= i; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr[j], arr[j - 1]);
       // temp = arr[j];
       // arr[j] = arr[j - 1];
       // arr[j - 1] = temp;
        flag = 1;
      }
    }

    if (flag == 0) return;
  }
}

1
2
3
4
5
6

01100101
10011101
-------- 进行异或(^)
11111000
--------
5个1，汉明距离 = 5

1
2

1. 子网地址: 主机 IP 地址 & 子网掩码
2. 广播地址: 子网地址  | 子网掩码反码