数据结构实践

本篇将根据自考实践要求对「数据结构」一科进行简要的复习，代码实现使用 C++ 语言实现。

实践

已知 Q 是一个非空队列，S 是一个空栈。编写算法，仅用队列和栈的 ADT 函数和少量工作变量，将队列 Q 的所有元素逆置。

栈的基本 ADT 函数有：

置空栈。函数原型为: void MakeEmpty(SqStack s);
元素e入栈。函数原型为: void Push(SqStack s,ElemType e);
出栈，返回栈顶元素。函数原型为: ElemType pop(SqStack s);
判断栈是否为空。函数原型为: int isEmpty(SqStack s);

队列的基本ADT函数有：

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

题目要求：

编程实现队列和栈的ADT函数
仅用队列和栈的ADT函数和少量工作变量，编写将队列Q的所有元素逆置的函数
测试该函数







#include <iostream>

using namespace std;

#define StackSize 10
typedef int ElemType;


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

    
    void makeEmpty() {
      this->top = -1;
    }

    
    void push(ElemType e) {
      if (this->isFull()) {
        std::cout << "栈满" << std::endl;
        return;
      }

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

    
    ElemType pop() {
      if (this->isEmpty()) {
        std::cout << "栈空" << std::endl;
        return -1;
      }

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

    
    bool isEmpty() {
      return this->top == -1;
    }

    
    int isFull() {
      return this->top == StackSize;
    }
};






#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;
    }

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

      this->data[this->real] = e;
      
      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);
  }
}




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;
}

排序

选择排序

基本思想: 每一趟在待排序的记录中选出关键字最小的记录，依次存放在已排好序的记录序列的最后，直到全部排序完为止。


#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] << " ";
  }
}

插入排序

基本思想: 每次将一个待排序的记录按其关键字的大小插入到前面已经排序好的文件中的适当位置，直到全部记录插入完位置。

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];
      
      for(j = i - 1; j >= 0 && tmp < arr[j]; j--) {
        arr[j + 1] = arr[j];
      }
      arr[j + 1] = tmp;
    }
  }
}

冒泡排序

冒泡排序的基本思想是：通过相邻元素之间的比较和交换，使娇小的元素逐渐从底部移向顶部，就像水底下气泡一样逐渐向上冒泡。

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]);
       
       
       
        flag = 1;
      }
    }

    if (flag == 0) return;
  }
}

推荐订阅源

Anran758's blog

实践

排序

选择排序

插入排序

冒泡排序