线性表、栈和队列的应用实现
(1) 用随机函数生成10个3位整数(100~999)，把这些整数存于单链表中，然后读入一个整数，以该值为基准把单链表分割为两部分，所有小于该值的结点排在大于或等于该值的结点之前。
(2) 假设一个字符串中可以包含三种括号：( )[ ]{}，且这三种括号可以按任意次序嵌套使用(如：“…[…{…}…[…]…]…(…)” 为合法嵌套，“…[…{… )…[…]…]…(…)”为不合法嵌套)。编写判别给定表达式中所含括号是否正确配对出现的算法，如果是合法嵌套则返回为true，如果是不符合法嵌套则返回为false。
(3) 用队列求解迷宫问题的最短路径
（1）
#include <iostream> #include<math.h> #include<ctime> using namespace std; #define OK 1 #define ERROR 0 typedef int Status; typedef int LElemType; typedef int SElemType; typedef int QElemType; typedef struct LNode { LElemType data; struct LNode* next; LNode* LRear; int length; }LNode, * LinkList; //创建空表 Status EmList(LinkList& L) { L = new LNode; L->next = NULL; L->LRear = L; L->length = 0; return OK; } //链表的存储 Status StoreElem(LinkList& L, LElemType& e) { LNode* p = new LNode; p->data = e; p->next = NULL; L->LRear->next = p; L->LRear = p; L->length++; return OK; } // 输出链表内容 Status ShowElem(LinkList& L) { LNode* p = L->next; cout << "链表输出：" << endl; for (int i = 0; i < L->length; i++) { cout << p->data << ends; p = p->next; } cout << endl << endl; return OK; } Status CreateList(LinkList& L) { for (int i = 0; i < 10; ++i) { int j = rand() % 900 + 100; StoreElem(L, j); } ShowElem(L); LElemType measure; cout << "请输入一个整数，以该值为基准把单链表分割为两部分" << endl; cin >> measure; LNode* flag = L; for (int i = 0, j = 10; i < j; i++) { if (flag->next->data >= measure) { L->LRear->next = flag->next; L->LRear = flag->next; flag->next = flag->next->next; L->LRear->next = NULL; } else flag = flag->next; } ShowElem(L); return OK; } int main() { time_t t; // 定义时间变量 srand((unsigned)time(&t)); //由时间确定随机序列，执行一次 LinkList L; EmList(L); CreateList(L); }
（2）
#include<iostream> #include<string> #include<stack> #include<map> using namespace std; bool judge(string s) { map<char, char> map_s = { {'(',')'},{'[',']'},{'{','}'} }; stack<char> temp; for (int i = 0; i < s.length(); ++i) { if (map_s.find(s[i]) != map_s.end()) temp.push(map_s[s[i]]); else { if (temp.empty()) return false; if (s[i] == temp.top()) temp.pop(); else return false; } } if (temp.empty()) return true; else return false; } int main() { string str; while (1) { getline(cin, str); if (str.length() == 0) break; if (judge(str)) puts("合法嵌套"); else puts("非法嵌套"); } return 0; }
（3）
#include <iostream> using namespace std; #define OK 1 #define ERROR 0 typedef int Status; typedef int QElemType; //队列链式存储结构 typedef struct QNode { QElemType idata; QElemType jdata; struct QNode* next; }QNode, * QueuePtr; typedef struct { QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue; //创建空队列 Status InitQueue(LinkQueue& Q) { Q.front = Q.rear = new QNode; Q.front->next = NULL; return OK; } //入队 Status InQueue(LinkQueue& Q, QElemType i, QElemType j) { QNode* p = new QNode; p->idata = i; p->jdata = j; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } //出队 Status DeQueue(LinkQueue& Q, int e) { if (Q.front == Q.rear) return ERROR; QNode* pQ = Q.front->next; //p指向队头 Q.front->next = pQ->next; //修改头结点指针域 if (e == 1) //若是迷宫没有路，则e==0，不输出值 cout << "a[ " << pQ->idata << " ][ " << pQ->jdata << " ]>" ; if (Q.rear == pQ) Q.rear = Q.front; //最后元素被删，尾指针指向队头 delete pQ; DeQueue(Q, e); return OK; } //求迷宫最短路径 Status LookFor(LinkQueue& Load, int* a, QElemType i, QElemType j) { if (i == 5 && j == 5) { InQueue(Load, i, j); return OK; } if (a[(j + 1) + i * 6] == 0 && j != 5) { a[(j + 1) + i * 6] = 1; InQueue(Load, i, j); LookFor(Load, a, i, j + 1); } else if (a[j + (i + 1) * 6] == 0 && i != 5) { a[j + (i + 1) * 6] = 1; InQueue(Load, i, j); LookFor(Load, a, i + 1, j); } else if (a[(j - 1) + i * 6] == 0 && j != 0) { a[(j - 1) + i * 6] = 1; InQueue(Load, i, j); LookFor(Load, a, i, j - 1); } else if (a[j + (i - 1) * 6] == 0 && i != 0) { a[j + (i - 1) * 6] = 1; InQueue(Load, i, j); LookFor(Load, a, i, j - 1); } return OK; } //输出迷宫 void ShowMaze(int* a) { cout << "迷宫：" << endl; for (int i = 0; i < 6; i++) { for (int j = 0; j < 6; j++) cout << a[i * 6 + j] << ends; cout << endl; } } int main() { LinkQueue Load; InitQueue(Load); int flag = 1;//用来控制出队时是否要输出值 int a[6 * 6] = //创建迷宫，1为障碍，0为道路 { 0,0,0,1,0,1, 1,1,0,0,0,1, 1,1,0,0,0,0, 0,0,0,1,0,1, 0,1,1,1,1,1, 0,0,0,0,0,0 }; ShowMaze(a); cout << "该迷宫路径：" << endl; LookFor(Load, a, 0, 0); if (Load.rear->idata != 5 || Load.rear->jdata != 5) //判断是否达到终点 { flag = 0; cout << "错误，没有路" << endl; DeQueue(Load, flag); } else { flag = 1; cout << endl; DeQueue(Load, flag); } cout << endl << endl; int a0[6 * 6] = //去不了终点的迷宫 { 0,1,1,1,0,1, 0,0,0,1,1,1, 1,0,0,0,0,1, 1,0,1,1,0,1, 1,1,1,1,0,1, 1,1,1,1,0,0 }; ShowMaze(a0); LookFor(Load, a0, 0, 0); if (Load.rear->idata != 5 || Load.rear->jdata != 5) { flag = 0; cout << "错误，没有路" << endl; DeQueue(Load, flag); } else { cout << "该迷宫路径：" << endl; flag = 1; cout << endl; DeQueue(Load, flag); } cout << endl << endl; int a2[6 * 6] = //全是1的迷宫 { 1,1,1,1,1,1, 1,1,1,1,1,1, 1,1,1,1,1,1, 1,1,1,1,1,1, 1,1,1,1,1,1, 1,1,1,1,1,1 }; ShowMaze(a2); cout << "该迷宫路径：" << endl; LookFor(Load, a2, 0, 0); if (Load.rear->idata != 5 || Load.rear->jdata != 5) { flag = 0; cout << "错误，没有路" << endl; DeQueue(Load, flag); } else { flag = 1; cout << endl; DeQueue(Load, flag); } cout << endl << endl; int a1[6 * 6] = //全是0的迷宫 { 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0 }; ShowMaze(a1); cout << "该迷宫路径：" << endl; LookFor(Load, a1, 0, 0); if (Load.rear->idata != 5 || Load.rear->jdata != 5) { flag = 0; cout << "错误，没有路" << endl; DeQueue(Load, flag); } else { flag = 1; cout << endl; DeQueue(Load, flag); } cout << endl << endl; }
