内容发布更新时间 : 2024/12/23 9:49:50星期一 下面是文章的全部内容请认真阅读。
}
}
}
qa->next=A->next; A->next=qa;
//将当前最小结点插入A表表头
else{ }
qb=pb; pb=pb->next; qb->next=A->next; A->next=qb;
//将当前最小结点插入A表表头
while(pa){ }
while(pb){ } pb=B; free(pb); return OK;
qb=pb; pb=pb->next; qb->next=A->next; A->next=qb; qa=pa; pa=pa->next; qa->next=A->next; A->next=qa;
2.13 设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,...,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,...,an,...,a4,a2)。
void Reform(DuLinkedList &L)//按1,3,5,...4,2 的顺序重排双向循环链表L 中的所有结点 { p=L.next;
while(p->next!=L&&p->next->next!=L) {
p->next=p->next->next; p=p->next;
} //p指向最后一个奇数结点
if(p->next==L) //结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点 p->next=L->pre->pre;
else//结点个数是偶数，使最后一个奇数结点next指向最后一个偶数结点 p->next=L->pre;
p=p->next; //此时p 指向最后一个偶数结点
while(p->pre->pre!=L) {
p->next=p->pre->pre; p=p->next; }
p->next=L;//最后一个结点next指向头结点
//调整了next 链的结构,此时pre 链仍为原状 //调整pre 链的结构
for(p=L;p->next!=L;p=p->next) p->next->pre=p; L->pre=p; //头结点的pre指向a2结点
}//Reform
第三章 栈和队列
3.6 试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符‘&’,且序列2是序列1的逆序。例如，“a+b&b+a”是属于该模式的字符序列，而“1＋3&3－1”则不是。 算法：
int SeqReverse()//判断输入的字符串中'&'前和'&'后部分是否为逆串,是则返回1,否则返回0 {
InitStack(s);
while((e=getchar())!='&') {
if(e==’@’)
return 0;//不允许在’&’之前出现’@’ push(s,e); }//序列1输入完毕 while( (e=getchar())!='@') {
if(StackEmpty(s)) return 0; pop(s,c); if(e!=c) return 0; }
if(!StackEmpty(s))
return 0;//序列1元素还有剩余 return 1;
}//IsReverse
3.7 假设一个算术表达式中可以包含三种符号：圆括号“(”和“)”、方括号“[”和“]”、花括号“{”和“}”，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法（已知表达式已存入数据元素为字符的顺序表中）。 算法：
Status BracketTest(char *str)//判别表达式中三种括号是否匹配 {
InitStack(s); for(p=str;*p;p++) {
if(*p=='(' || *p=='[' || *p=='{' ) push(s,*p); else
if(*p==' ) ' || *p==' ] ' || *p==' } ') {
if(StackEmpty(s)) return ERROR; pop(s,c);
if(*p==')'&&c!='(') return ERROR; if(*p==']'&&c!='[') return ERROR;
if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配 }//if }//for
if(!StackEmpty(s)) return ERROR;//进栈的符号还有剩余，Error return OK; }//BracketTest
3.8 设表达式由单字母变量、双目运算符和圆括号组成（如:“(a*(b+c)-d)/e）”。试写一个算法，将一个书写正确的表达式转换为逆波兰式。
思路：
1.遇到数字直接发送 2.遇到’(’直接入栈 3.遇到’)’则将栈内元素发送直至遇到’(’ 4.栈空则直接入栈 5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈
int RankOfOperator(char c){ switch(c){
case '#': return -1; case '(': return 0; case '+':
case '-': return 1;
case '*': case '/':
case ')':return 2; } }
int Precede(char c, char ch){
return RankOfOperator(c)>RankOfOperator(ch); }
void ExpressionTOPolandStyle(char suffix[],char *exp){ Stack s; InitStack(s,100); int i=0; char c;
while(*exp){
if(isdigital(*exp)) suffix[i++]=*exp; else{
switch(*exp){
case '(': push(s,'(');
case ')': while((c=pops(s))!='(') suffix[i++]=c; break;
default: if(IsEmpty(s)) push(s,*exp); else{
suffix[i++]=pop(s); exp--;
//与后面的exp++相抵消，使得栈内优先级大于等于栈外的都出栈
}
}
}//end switch }//end else exp++; }//end while
while(!IsEmpty(s)) suffix[i++]=pop(s); suffix[i]=0;
3.10 假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队算法（在出队算法中要传回队头元素的值）
要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性
typedef int DataType