【啊哈！算法】栈、队列、链表

Contents

栈、队列、链表队列栈纸牌游戏 小猫钓鱼链表模拟链表

栈、队列、链表

---

队列栈纸牌游戏 小猫钓鱼链表模拟链表

队列

---

特点：管子，两边开口，先进先出 (First In First Out) 队列的三个基本元素：一个数组，两个变量

#include<iostream> using namespace std; struct queue { int data[100]; //队列主体，用来存储内容 int head; //队首 int tail; //队尾 }; typedef struct queue Queue; //将 struct queue 重命名为 Queue int main() { Queue q; //初始化队列 q.head = 1; q.tail = 1; for(int i = 0; i < 5; i++) { cin >> q.data[q.tail]; q.tail++; //进队列 } while (q.head < q.tail) { cout << q.data[q.head]; q.head++; //出队列 } return 0; }

栈

---

特点：管子，一边开口，后进先出 (Last In First Out) 栈的基本元素：一个数组，一个变量

#include<iostream> using namespace std; struct stack { int data[100]; //栈主体，用来存储内容 int top; //栈顶 栈顶指针 top 指向的是栈顶上的一个空间 }; typedef struct stack Stack; //将 struct stack 重命名为 Stack int main() { Stack s; //初始化栈 s.top = 0; for(int i = 0; i < 5; i++) { cin >> s.data[s.top]; s.top++; //入栈 压栈 } while (s.top > 0) { s.top--; //出栈 cout << s.data[s.top]; } return 0; }

纸牌游戏 小猫钓鱼

---

Question：俗称 “接竹竿”，就是接牌，有相同的将二者之间的牌收入手里，一方无牌则败 分析：两人手中的牌是队列，桌面上的牌是栈 约定：牌面 1~9

#include<iostream> using namespace std; struct stack { int data[100]; //栈主体 int top; //栈顶 }; struct queue { int data[1000]; int head; int tail; }; typedef struct stack Stack; typedef struct queue Queue; int main() { Stack s; Queue q, p; int book[10]; s.top = 0; q.head = 0; q.tail = 0; p.head = 0; p.tail = 0; //初始化标记数组 for (int i = 1; i <= 9; i++) { book[i] = 0; } //读入牌 每人六张 cout << "input q: "; for (int i = 0; i < 6; i++) { cin >> q.data[q.tail]; q.tail++; } cout << "input p: "; for (int i = 0; i < 6; i++) { cin >> p.data[p.tail]; p.tail++; } while(q.head < q.tail && p.head < p.tail) { //q出牌 int t = q.data[q.head]; q.head++; //出队 // int flag = 0; // for (int i = 0; i < s.top; i++) { //遍历栈 这里是遍历表示栈的数组 // if(t == s.data[i]) { // flag = 1; // break; // } // } //用标记数组来判断比遍历栈要方便 // if (flag == 0) { if (book[t] == 0) { s.data[s.top] = t; s.top++; //入栈 book[t] = 1; } else { q.data[q.tail] = t; q.tail++; //入队 do { q.data[q.tail] = s.data[s.top - 1]; q.tail++; book[s.data[s.top - 1]] = 0; s.top--; } while (s.data[s.top] != t); //这里是取了数组的巧 } if (q.head == q.tail) break; //p出牌 t = p.data[p.head]; p.head++; if(book[t] == 0) { s.data[s.top] = t; s.top++; book[t] = 1; } else { p.data[p.tail] = t; p.tail++; do { p.data[p.tail] = s.data[s.top - 1]; p.tail++; book[s.data[s.top - 1]] = 0; s.top--; } while (s.data[s.top] != t); } if (p.head == p.tail) break; cout << "q current: "; for (int i = q.head; i < q.tail; i++) { cout << q.data[i] << " "; } cout << endl; cout << "p current: "; for (int i = p.head; i < p.tail; i++) { cout << p.data[i] << " "; } cout << endl; } if (p.head = p.tail) { cout << "q victory current: " << endl; for (int i = q.head; i < q.tail; i++) { cout << q.data[i] << " "; } } else { cout << "p victory current: " << endl; for (int i = p.head; i < p.tail; i++) { cout << p.data[i] << " "; } } cout << endl; if (s.top > 0) { cout << "stack still have: " << endl; for (int i = 0; i < s.top; i++) { cout << s.data[i] << " "; } } else { cout << "stack is empty." << endl; } return 0; }

链表

---

概念：指针变量 p，作用是存储一个内存空间的首地址 p = &a

间接访问运算符 *，作用是取得指针 p 所指向的内存中的值，还有可以用作声明指针变量动态存储：malloc(4)；作用是从内存中申请分配指定字节大小的内存空间，此处申请四个字节，它的返回是一个指向该空间的 void * 通用指针，需要强转 若不知 int 占用几个字节，可以用 sizeof(int) 获取，写出就是 malloc(sizeof(int))对动态申请的空间进行操作： int *p; p = (int *)malloc(sizeof(int)); //malloc 返回的是 void *，需要强制转换成 int * 访问结构体内部成员：有两种方式 . 和 ->，指针变量不能用 . 访问，只能用后者 p->data 如果你必须要用 . 的话也行，不过在这之前需要将指针指向的内存中的东西取出 像这样 (*p).data，因为 * 的优先级低于 .free(p) 的作用：将指针还原为未初始化状态并使内存块在堆上重新变成可用状态

链表的实现：

#include<iostream> #include<cstdlib> using namespace std; struct node { int data; struct node *next; //结构体指针变量 next }; int main() { struct node *head, *q, *p; int n; head = NULL; cout << "input n: "; cin >> n; for (int i = 0; i < n; i++) { int a; cin >> a; //动态申请一个空间，放一个结点，并用临时指针 p 指向它 p = (struct node *)malloc(sizeof(struct node)); p->data = a; p->next = NULL; if(head == NULL) { head = p; } else { q->next = p; } q = p; } //一个长度为 n 的链表建成 //输出一下 struct node *t; t = head; while (t != NULL) { cout << t->data << " "; t = t->next; } //结束时建议用 free 命令释放动态申请的空间 free(head); free(q); free(p); free(t); return 0; }

插入结点：

int a; cin >> a; t = head; //遍历 while (t != NULL) { if (t->next == NULL || t->next->data > a) { //当 t 为最后一个结点 或 t 的下一个结点的数据域的值大于 a 时插入 p 结点 p = (struct node *)malloc(sizeof(struct node)); p->data = a; p->next = NULL; p->next = t->next; t->next = p; break; } }

模拟链表

---

就是用两个数组，其中一个数组做数据域的集合，另一个数组做指针域的集合

---

End.