队列

head记录的是队首位置 tail记录的是队尾的下一个位置 tail为什么不记录队尾，而是记录队尾的下一个位置？ 因为当队列只剩一个元素的时候，队头和队尾重合回答带来一些麻烦。 因此，规定队首和队尾重合时，队列为空

当出队，则head++ 当入队，则q[tail++]=入队数 这样保证了head和tail之间的为队列中的有效数

代码实现：

#include<stdio.h> int main() { int q[102] = { 0,6,3,1,7,5,8,9,2,4 }, head, tail; //q[0]=0，这是因为，队列从下标1开始 int i; //初始化队列 head = 1; //队头初始化为1 tail = 10; //队尾初始化为10,但实际上，队尾存储只到9。因为tail是指向队尾的的下一个位置 while (head < tail) //当队不空时 { printf("%d ", q[head]); //先打印队头元素 head++; //队头出队 q[tail] = q[head]; //将新队头移到队尾 tail++; //队尾标志后移 head++; //队头标志后移，以标志队头出 } return 0; }

队列是一种特殊的线性结构 只允许在队首进行删除，即出队 在队尾进行插入，即入队 当队列中没有元素时，称为空队列(tail==head) 先进先出

下面是变为数据结构的形式：

struct queue { int data[100]; //队列元素 int head; //队头标志 int tail; //队尾标志 };

将上面的改为队列类型的标准

#include<stdio.h> struct queue { int data[100]; int head; int tail; }; int main() { struct queue q; int i; q.head = 1; q.tail = 1; for (i = 1; i <= 9; i++) { scanf("%d", &q.data[q.tail]); q.tail++; } while (q.head < q.tail) { printf("%d ", q.data[q.head]); q.head++; q.data[q.tail] = q.data[q.head]; q.tail++; q.head++; } return 0; }

栈

需要一个一维数组和一个指向栈顶的变量top top是指向栈顶元素的。 初始化栈 top = 0 入栈： top++; s[top] = x;

回文的匹配，利用栈

int main() { char a[101],s[101]; int len，next,mid; gets(a); len = strlen(a); int top = 0; //栈的初始化 mid = len / 2 - 1; //中点 for (int i = 0; i <= mid; i++) s[++top] = a[i]; //入栈操作 if (len % 2 == 0) //判断字符串的长度是奇数还是偶数，并确定需要进行字符匹配的起始下标 next = mid + 1; else next = mid + 2; for (int i = next; i <= len - 1; i++) { if (a[i] != s[top]) //栈顶元素和后半段匹配 { break; //如果不等，则直接跳出 } top--; //如果相等，则进行栈顶元素出栈，匹配下一个 } if (top == 0) //如果top为0，则说明栈内所有元素都匹配完毕了 printf("YES\n"); else printf("NO\n"); return 0; }

纸牌游戏

规则： 将一副牌均分两份，一人一份 一人将手中的第一张牌放在桌上，另一人也拿出第一张牌置于其上 交替出牌 如果一人打出的牌与桌上某张牌相同，则拿两张相同的牌及其中间所有的牌，放于自己手中牌的末尾 当一人手中牌出完，游戏结束，对手获胜

分析： 手中的牌即是队列 桌上的牌即是栈 因此，两个队列，一个栈即可

出牌是出队，赢牌是入队 打出的牌放在桌子上是入栈 遇到相同的牌，则是顺序出栈

代码实现： 这个代码异常的垃圾。 我所需要的是里面的精华

#include<stdio.h> #include<string.h> typedef struct queue { int head; //队头 int tail; //队尾 int data[1000]; //队中存储的元素 }queue; typedef struct stack { int data[10]; int top; }stack; int main() { queue q1, q2; stack s; int book[10]; //用来做标记 int i, t; q1.head = q1.tail = 1; q2.head = q2.tail = 1; //两个队列的初始化 s.top = 0; //桌子 栈的初始化 memset(book, 0, sizeof(book)); //将标记book初始化为0 for (int i = 1; i <= 6; i++) { scanf("%d", &q1.data[q1.tail++]); } //队列1插入元素 for (int i = 1; i <= 6; i++) { scanf("%d", &q2.data[q2.tail++]); } //队列2插入元素 while (q1.head < q1.tail && q2.head < q2.tail) //没有人出完牌，则游戏保持进行 { t = q1.data[q1.head]; //第一个人亮出一张牌 if (book[t] == 0) //看这张牌在桌子上(栈中)有没有 { //如果没有 q1.head++; //将这张牌出队 s.top++; //桌子上的牌数+1 s.data[s.top] = t; //桌子上顶部的牌变成打出的牌 book[t] = 1; //标记打出的牌在桌子上有了 } else //如果有 { q1.head++; //把打出的牌出队，以把这个打出的牌移至队尾 q1.data[q1.tail++] = t; //队列尾部新添刚刚打出的牌 while (s.data[s.top] != t) //将与打出的牌相同的牌之间的所有牌顺序移至队尾 { book[s.data[s.top]] = 0; //因为移除了，所以这张牌在桌子上不存在了 q1.data[q1.tail] = s.data[s.top]; //队尾新添栈顶 q1.tail++; //队尾长度+1 s.top--; //栈顶位置-1 } } t = q2.data[q2.head]; if (book[t] == 0) //看这张牌在桌子上(栈中)有没有 { //如果没有 q2.head++; //将这张牌出队 s.top++; //桌子上的牌数+1 s.data[s.top] = t; //桌子上顶部的牌变成打出的牌 book[t] = 1; //标记打出的牌在桌子上有了 } else //如果有 { q2.head++; //把打出的牌出队，以把这个打出的牌移至队尾 q2.data[q2.tail++] = t; //队列尾部新添刚刚打出的牌 while (s.data[s.top] != t) //将与打出的牌相同的牌之间的所有牌顺序移至队尾 { book[s.data[s.top]] = 0; //因为移除了，所以这张牌在桌子上不存在了 q2.data[q2.tail] = s.data[s.top]; //队尾新添栈顶 q2.tail++; //队尾长度+1 s.top--; //栈顶位置-1 } } } if (q2.head == q2.tail) { printf("Man Win!\n"); printf("Man's:"); for (i = q1.head; i <= q1.tail - 1; i++) printf(" %d", q1.data[i]); if (s.top > 0) //如果桌子上还有牌剩余 { printf("\n桌子上的牌是："); for (i = 1; i <= s.top; i++) printf(" %d", s.data[i]); } else printf("桌子上已经没牌了\n"); } else { printf("Woman Win!\n"); printf("Woman's:"); for (i = q2.head; i <= q2.tail - 1; i++) printf(" %d", q2.data[i]); if (s.top > 0) //如果桌子上还有牌剩余 { printf("\n桌子上的牌是："); for (i = 1; i <= s.top; i++) printf(" %d", s.data[i]); } else printf("桌子上已经没牌了\n"); } return 0; }

链表

链表结构

typedef struct node { int data; struct node* next; }Node;

建立链表

创建头指针 头指针的作用是：方便以后从头到尾遍历链表 需要一个头指针head指向链表的最开始 当链表还没有建立的时候，head为空

Node* head; head = NULL;//头指针初始化为空

创建结点并初始化

//创建第一个结点 Node* p; //定义一个结点 p = (Node*)malloc(sizeof(Node)); //为这个结点动态申请空间 //初始化结点 scanf("%d", &a); p->data = a; //将要存储的数据存入当前节点的data的数据域 p->next = NULL; //将当前结点的后继指针指向空，表示当前结点的下一个结点为空

形成链表结构

if (head == NULL) head = p; //如果这是第一个创建的结点，则头指针指向该节点 else q->next = p; //如果这不是第一个创建的结点，则上一个结点的后继指针指向该节点 q = p; //q指向当前结点

遍历整个链表 头结点的好处

//输出整个链表 t = head; //这就是头结点的好处 while (t != NULL) { printf(" %d", t->data); t = t->next; }

插入操作

//插入操作 t = head; scanf("%d", &a); while (t != NULL) { if (t->next->data > a) { p = (Node*)malloc(sizeof(Node)); p->data = a; p->next = t->next; t->next = p; break; } t = t->next; }

完整代码

#include<stdio.h> #include<stdlib.h> typedef struct node { int data; struct node* next; }Node; int main() { int i, n, a; Node* head, * p, * q, * t; scanf("%d", &n); head = NULL; for (i = 1; i <= n; i++) { scanf("%d", &a); //初始化结点 p = (Node*)malloc(sizeof(Node)); //为这个结点动态申请空间 p->data = a; //将要存储的数据存入当前节点的data的数据域 p->next = NULL; //将当前结点的后继指针指向空，表示当前结点的下一个结点为空 if (head == NULL) head = p; //如果这是第一个创建的结点，则头指针指向该节点 else q->next = p; //如果这不是第一个创建的结点，则上一个结点的后继指针指向该节点 q = p; //q指向当前结点 } //插入操作 t = head; scanf("%d", &a); while (t != NULL) { if (t->next->data > a) { p = (Node*)malloc(sizeof(Node)); p->data = a; p->next = t->next; t->next = p; break; } t = t->next; } //输出整个链表 t = head; while (t != NULL) { printf(" %d", t->data); t = t->next; } return 0; }

模拟链表

利用数组来实现链表 一个数组存放数据 一个数组存放下一个数的位置

例如： right[1]=2 表示：当前序列中1号元素右边的元素存放在data[2]中 right[9]=0 表示：当前序列中9号元素右边的元素不存在

插入操作： 直接在data末尾，即data[10]的位置，置为6即可。 data[10]=6 接下来，修改right[3]=10 表示新序列中3号元素右边的元素存在data[10]中 再将right[10]改为4，表示新序列中10号元素右边的元素存放在4号位置

完整代码：

#include<stdio.h> int main() { int data[100], right[100]; int i, n, t, len; scanf("%d", &n); for (i = 1; i <= n; i++) //读入已有的数 { scanf("%d", &data[i]); } len= n; for (i = 1; i <= n; i++) //初始化right数组 { if (i != n) right[i] = i + 1; else right[i] = 0; } //插入操作 //直接在data后面加一个数 len++; scanf("%d", &data[len]); //从链表头开始遍历 t = 1; while (t != 0) { if (data[right[t]] > data[len]) //如果当前结点的下一个结点大于待插入数，则将数插入到中间 { right[len] = right[t]; //将待插入数的右边置为当前结点的下一个结点 right[t] = len; break; } t = right[t]; } //遍历模拟链表 t = 1; //从头开始 while (t != 0) { printf("%d ", data[t]); t = right[t]; } return 0; }