栈与链表小结
1.栈
栈的特点就是后进先出，始终使用top和pop语句来实现每一个元素的遍历，同时在使用pop和top函数的时候，要先使用empty来判断栈是否为空。
下面为一道很经典的栈的例题
1.1
题目描述
读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。
输入
测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。
输出
对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。
样例输入
30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
0样例输出
12178.21
分析：
这道题考查的是中缀表达式转后缀表达式，以及后缀表达式的计算
首先是中缀表达式转后缀表达式：
- 从左向右扫面中缀表达式，碰到操作数，就把操作数放到后缀表达式中（为队列），可能会有十位数，百位数，因此要进行数字转换为十位数百位数的计算
- 如果碰到了操作符，则先将其优先级与操作符栈中的第一个操作符进行比较
-
如果操作符的优先级大于栈顶的优先级，则将其压入到操作符栈中
-
如果优先级低于或等于栈顶，则将操作符栈的操作符不断弹出，放到后缀表达式中，直到该操作符的优先级大于栈顶的优先级
- 依次重复，当扫面完后栈中还有操作符，则将他们依次弹出到后缀表达式队列中
然后进行后缀表达式的计算：
为了解释后缀表达式的好处，我们先来看看，计算机如何应用后缀表达式计算出最终的结果20的。
后缀表达式：9 3 1-3*+ 10 2/+
-
规则：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。
下面是详细的步骤：
1. 初始化一个空栈。此桟用来对要运算的数字进出使用。
2. 后缀表达式中前三个都是数字，所以9、3、1进栈。
3. 接下来是减号“-”，所以将栈中的1出栈作为减数，3出栈作为被减数，并运算3-1得到2，再将2进栈。
4. 接着是数字3进栈。
5. 后面是乘法“*”，也就意味着栈中3和2出栈，2与3相乘，得到6，并将6进栈。
6. 下面是加法“+”，所以找中6和9出找，9与6相加，得到15，将15进栈。
7. 接着是10与2两数字进栈。
8. 接下来是符号因此，栈顶的2与10出栈，10与2相除，得到5，将5进栈。
9. 最后一个是符号“+”，所以15与5出找并相加，得到20，将20进栈。
10. 结果是20出栈，栈变为空。
具体代码如下：
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
using namespace std;
struct node{
double num;
char op;
bool flag;
}; //定义的结构体为存放中缀表达式中的内容， true为操作数，false为操作符
string str;
stack<node> s; //定义操作符栈
queue<node> q; //存放后缀表达式
map<char,int> op; //定义一个map 用于表达操作符的优先级
void change(){
node temp;
for(int i=0;i<str.length();){
if(str[i]>='0'&&str[i]<='9'){
temp.flag=true;
temp.num=str[i++]-'0'; //记录第一个数位
while(i<str.length() &&str[i]<='0'&&str[i]>='9'){
temp.num=temp.num*10+(str[i]-'0');
i++;
} //如果中缀表达式中是个位以上的数，就要将每个数字转换为数，存放在队列中
q.push(temp);
}
else{ //存放操作符
temp.flag=false;
while(!s.empty()&&op[str[i]]<=op[s.top().op]){
q.push(s.top());
s.pop();
}
temp.op=str[i];
s.push(temp);
i++;
}
}
while(!s.empty()){ //最后 如果中缀表达式扫面完毕，栈中还有元素，就把操作符全部弹出
q.push(s.top());
s.pop();
}
}
double cal(){ //计算后缀表达式
double temp1,temp2;
node cur,temp;
while(!q.empty()){
cur=q.front();
q.pop();
if(cur.flag==true) s.push(cur);
else{
temp2=s.top().num;
s.pop();
temp1=s.top().num;
s.pop();
temp.flag=true;
if(cur.op=='+') temp.num=temp1+temp2;
else if(cur.op=='-') temp.num=temp1-temp2;
else if(cur.op=='*') temp.num=temp1*temp2;
else temp.num=temp1/temp2;
s.push(temp);
}
}
return s.top().num;
}
int main(){
op['+'] =op['-'] =1; //定义操作符的优先级
op['*'] =op['/'] =2;
while(getline(cin,str),str!="0"){
for(string::iterator it=str.begin();it !=str.end();it++){ //使用迭代器遍历
if(*it==' ') str.erase(it);
}
while(!s.empty()) s.pop(); //在栈使用pop前，要判定是否为空
change();
printf("%.2f\n",cal());
}
return 0;
}参考链接：图解后缀表达式
2.链表
1.创建链表
#include<iostream>
using namespace std;
struct node{
int data;
node * next;
};
node* create(int array[]){
node *p,*pre,*head; //关键是要定义pre这个前驱结点，head为头结点
head=new node;
head ->next=NULL;
pre =head;
for(int i=0;i<5;i++){
p=new node;
p->data=array[i];
p->next=NULL;
pre->next=p; //依次把当前的结点给前驱结点，使他每次都能指向下一个结点
pre=p;
}
return head;
}
int main(){
int array[5]={5,3,6,1,2};
node* L=create(array);
L=L->next;
while(L !=NULL){
printf("%d",L->data);
L=L->next;
}
}2.查找元素
int search(node* head,int x){
int count=0;
node *p=head->next; //从head指向的第一个元素开始，head中是不含有数据的
while(p !=NULL){
if(p->data==x) count++;
p=p->next
}
}3.插入元素
void insert(node* head,int pos,int x){
node *p=head;
for(int i=0;i<pos;i++){
p=p->next;
}
node *q=new node;
q->data=x;
q->next=p->next;
p->next=q;
}4.删除元素
void del(node* head,int x){
node* p=head->next;
node* pre=head; //pre始终用来保持p的前驱结点
while(p !=NULL){
if(p->data==x){
pre->next=p->next;
delete(p);
p=pre->next;
}
else{
pre =p; // 注意顺序，应该是从左向右依次移动，先移动pre 再移动p
p=p->next;
}
}
}可以总结为：
在链表插入、查找元素的时候，只是对链表中的一个结点进行操作，一个是对新节点和前一个结点的操作，一个对结点进行遍历，所以不需要前驱结点
但是在删除结点的时候，需要将其中的一个结点拿出，同时将上一个结点与后一个结点连接，因此需要定义前驱结点
例题：
题目描述：
To store English words, one method is to use linked lists and store a word letter by letter. To save some space, we may let the words share the same sublist if they share the same suffix. For example, "loading" and "being" are stored as showed in Figure 1.
You are supposed to find the starting position of the common suffix (e.g. the position of "i" in Figure 1).
Input Specification:
Each input file contains one test case. For each case, the first line contains two addresses of nodes and a positive N (<= 10^5^), where the two addresses are the addresses of the first nodes of the two words, and N is the total number of nodes. The address of a node is a 5-digit positive integer, and NULL is represented by -1.
Then N lines follow, each describes a node in the format:
Address Data Next
where Address is the position of the node, Data is the letter contained by this node which is an English letter chosen from {a-z, A-Z}, and Next is the position of the next node.
Output Specification:
For each case, simply output the 5-digit starting position of the common suffix. If the two words have no common suffix, output "-1" instead.
Sample Input 1:
11111 22222 9
67890 i 00002
00010 a 12345
00003 g -1
12345 D 67890
00002 n 00003
22222 B 23456
11111 L 00001
23456 e 67890
00001 o 00010
Sample Output 1:
67890
Sample Input 2:
00001 00002 4
00001 a 10001
10001 s -1
00002 a 10002
10002 t -1
Sample Output 2:
-1
代码如下：
主要是通过静态链表实现
#include<iostream>
using namespace std;
const int maxn=10000;
struct Node{
int next;
char data;
bool flag; // 通过 flag true为链表中存在这个结点，false为没有 当第二个链表遍历到这个true的结点时，就说明两个链表存在公用的结点
}node[maxn];
int main(){
for(int i=0;i<maxn;i++){
node[i].flag=false;
}
int s1,s2,n;
scanf("%d%d%d",&s1,&s2,&n);
int address,next;
char data;
for(int i=0;i<n;i++){
scanf("%d %c %d",&address,&data,&next);
node[address].data=data;
node[address].next=next;
}
int p;
for(p=s1;p !=-1;p=node[p].next){
node[p].flag=true;
}
for(p=s2;p !=-1;p=node[p].next){
if(node[p].flag==true) break;
}
if(p !=-1) printf("%05d\n",p);
else printf("-1\n");
}