通过栈判断链表是否对称

设单链表的表头指针为L，data域为字符型，判断该链表的全部n个字符是否中心对称
xyx，xyyx

算法思想

使用栈来判断链表中的数据是否中心对称，让链表的前一半元素依次进栈
在处理链表的后一半元素时，当访问到链表的一个元素后，就从栈中弹出一个元素，两个元素比较，若相等，则将链表中的下一个元素与栈中再弹出的元素进行比较，直至链表尾。这时若栈是空栈，则得出链表中心对称的结论；否则当链表中的元素与栈中弹出元素不等时，结论为链表非中心对称，结束算法的执行

假设n是奇数，5
n/2=2，前两个元素入栈

创建s字符数组，大小是n/2=2

用i开始遍历数组，同时cur指针遍历链表，将链表前半的数据入栈

入栈完毕，如果n是偶数，则这时cur直接指向后半部分的首元素，由于这里n是奇数cur指向中间元素，需要后移一位

由于for循环最后一轮是i=2=n/2，循环结束
所以需要将i–，让i指向栈顶元素

通过while循环判断是否中心对称
若d4等于s1，i–，cur指向cur的next

若d5等于s0，i–，cur指向cur的next
这时cur指向NULL，循环结束
此时i=-1，说明链表中心对称，返回true

bool dc(LinkList L, int n)
{int i;// s字符栈char s[n/2];// 工作指针cur，指向待处理的当前元素LNode* cur = L->next;// 链表前一半元素入栈for (i = 0; i < n; i++){s[i] = cur->data;cur = cur->next;}// 恢复最后的i值i--;// 若n是奇数，后移过中心节点if (n % 2 == 1)cur = cur->next;// 检测是否中心对称while (cur && s[i] == cur->data){// i充当栈顶指针i--;cur = cur->next;}// 若栈为空栈if (i == -1)// 链表中心对称return true;else// 链表中心不对称return false;
}

共享栈入栈出栈

设有两个栈S1和S2都采用顺序栈的方式，并共享一个存储区，0-maxsize-1，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的存储方式
实现入栈和出栈

算法思想

两个栈共享向量空间，将两个栈的栈底设在向量两端，初始时，S1栈顶指针为-1，S2栈顶指针为maxsize，两个栈顶指针相邻时为栈满
两个栈顶相向，迎面增长，栈顶指针指向栈顶元素
top指向的是栈顶元素，所以入栈的时候，先移动top指针，然后再输入x
出栈的时候，先返回出栈的元素值，再移动top指针

#define maxsize 100
// 两个栈共享顺序存储空间所能达到的最多元素数，初始化为100
#define ElemType int
// 假设元素类型为整型
typedef struct
{// 栈空间ElemType st[maxsize];// top为两个栈顶指针int top[2];
}ST;
ST s;// 入栈操作，i为栈号，i=0表示S1栈，i=1表示S2栈，x是入栈元素
// 入栈成功返回1，否则返回0
int push(int i, ElemType x)
{// 如果i不是0也不是1，退出程序if (i < 0 || i > 1){printf("栈号输入错误");exit(0);}// 如果两个栈顶指针相差1，即相邻，表示栈满if (s.top[1] - s.top[0] == 1){printf("栈已满");return 0;}switch(i){// 输入0，在S1栈输入xcase 0:// 先移动top0，再输入xs.st[++s.top[0]] = x;return 1;break;case 1:// 先移动top1，再输入xs.st[--s.top[1]] = x;return 1;}
}// 出栈算法，i表示栈号，0表示S1栈，1表示S2栈
int pop(int i)
{if (i < 0 || i > 1){printf("栈号输入错误");exit(0);}switch(i){case 0:// 如果top0指向-1，表示S1栈空if (s.top[0] == -1){printf("栈空\n");return -1;}else// 先返回栈顶元素，再移动top0指针return s.st[s.top[0]--];break;case 1:if (s.top[1] == maxsize){printf("栈空\n");return -1;}elsereturn s.st[s.top[1]++];break;}
}

括号匹配

设表达式以字符形式已存入数组E[n]中，’#‘为表达式的结束符
判断表达式中的括号是否配对：EXYX(E)

算法思想

判断表达式中的括号是否匹配，可以通过栈，是左括号时进栈，右括号时出栈
出栈时，若栈顶元素是左括号，则新读入的右括号与栈顶左括号就可以消去
输入表达式结束时，栈空则正确，否则括号不匹配

int EXYX(char E[], int n)
{// s是一维数组，容量足够大，用作存放括号的栈char s[30];// 用top做括号的栈顶指针int top = 0;// #先入栈，用于和表达式结束符号#匹配s[top] = '#';// 字符数组的工作指针int i = 0;// 逐字符处理字符表达式的数组while (E[i] != '#'){switch(E[i])case '(':// 左括号，入栈s[++top] = '(';i++;break;case ')':// 右括号，如果和栈顶匹配，左括号出栈if (s[top] == '('){top--;i++;break;}else{printf("括号不配对");exit(0);}case '#':if (s[top] == '#'){pritnf("括号配对");return 1;}else{printf("括号不配对");return 0;}default:i++;}
}

多种括号配对

设计一个算法，判断一个算数表达式中的括号是否匹配，算数表达式保存在带头节点的单循环链表中，每个节点有两个域，ch和next

算法思想

括号有三种圆括号，方括号和大括号
使用栈，当为左括号时，入栈，右括号时，若栈顶是其对应的左括号，则出栈，若不是其对应的左括号，则结论为括号不配对，
当表达式结束，若栈为空，则结论表达式括号配对，否则，结论表达式括号不配对

int Match(LinkList L)
{char s[];LNode* cur = L->next;STInit(s);while (cur != L){switch (cur->ch){case '(':STPush(s, cur->ch);break;case ')':if (STEmpty(s) || STTop(s) != '('){printf("括号不配对");return 0;}else{STPop(s);break;}case '[':STPush(s, cur->ch);break;case ']':if (STEmpty(s) || STTop(s) != '['){printf("括号不配对");return 0;}else{STPop(s);break;}case '{':STPush(s, cur->ch);break;case '}':if (STEmpty(s) || STTop(s) != '{'){printf("括号不配对");return 0;}else{STPop(s);break;}}cur = cur->next;}if (STEmpty(s)){printf("括号配对");return 1;}else{printf("括号不配对");return 0;}
}

递归求序列最大值

设整数序列a1，a2，…，an，使用递归思想求解最大值

int findMax(int a[], int left, int right)
{if(left == right){return a[left];}int mid = (left + right) / 2;int leftMax = findMax(a, left, mid);int rightMax = findMax(a, mid + 1, right);return max(leftMax, rightMax);
}