{
p=Q->rear->next; /*p指向第一个结点*/ Q->rear->next=s; /*将s链接到队尾*/ Q->rear=s; /*Q->rear指向队尾*/ s->next=p; } }
void delqueue(LinkQueue *Q) /*出队算法*/ {
struct node *t; if (Q->rear==NULL) { printf(\队列为空!\\n\ return(0); }
else if (Q->rear->next==Q->rear) /*只有一个结点时*/ { t=Q->rear; Q->rear=NULL; }
else /*有多个结点时*/ { t=Q->rear->next; /*t指向第一个结点*/ Q->rear->next=t->next; /*引成循环链*/
}
free(t); }
elemtype gethead(LinkQueue *Q) /*取队首元素算法*/ {
if (Q->rear==NULL) printf(\队列为空!\\n\ else return(Q->rear->next->data); }
int emptyqueue(LinkQueue *Q) /*判断队列是否为空算法*/ { if (Q->rear==NULL) return(1); /*为空,则返回true*/
else return(0); /*不为空,则返回flase*/ }
void dispqueue(LinkQueue *Q) /*显示队列中元素算法*/ {
struct node *p=Q->rear->next; printf(\队列元素:\ while (p!=Q->rear) { printf(\ p=p->next; }
printf(\}
4．“回文”是指一个字符串从头读到尾和从尾读到头都一样。假设字符串是从输人设备一次一个字节的读人，并且读到字符“＃”的时候表示结束。请用栈和队列编写一个算法判
断一个字符串是否回文。
int isPalindrome( ) { /*回文判定算法*/ InitStack(S); InitQueue(Q); While((c=read())!='#') { push(S,c); /*读入字符分别保存在栈和队列中*/ EnQueue(Q,c); } While( !QmptyStack( S ) && ! EmptyQueue( Q ) ) { if (pop(S) != DelQueue(Q)) /*正序和逆序字符的比较*/ return (FALSE); } if ( !EmptyStack(S) || ! EmptyQueue( Q ) return (FALSE); return( TRUE ); } /*isPalindrome*/
5．假设表达式中有三种括号：圆括号“（）”、方括号“[ ]”和花括号“{ }”用C语言编写程序判断读人的表达式中不同括号是否正确配对，假定读人的表达式以”#”结束。
#include \#include \#define FALSE 0 #define TRUE 1
#define LEN sizeof( struct node ) struct node { char data; struct node *next; };
typedef struct node *stack;
void push_stack(stack *, char ); int pop_stack(stack *); void main() { stack s; int valid=TRUE; char ch,symble; symble=getchar(); s=NULL; push_stack(&s, '#'); while ((symble != '#' ) && (valid ==TRUE) ) { if ( symble !='(' && symble !=')' && symble != '[' && symble != ']' && symble !='{' && symble != '}' ) { symble=getchar(); } else if (symble=='(' || symble=='[' || symble=='{' ) { push_stack(&s, symble ); symble=getchar(); } else if ( s==NULL ) { valid=FALSE; } else { ch=pop_stack(&s); if ( (ch=='(' && symble==')') || (ch=='[' && symble==']') || ch==('{' && symble=='}') ) { valid=TRUE; symble=getchar(); } else valid=FALSE; }
} if ( valid == TRUE ) printf(\ else printf(\}
void push_stack( stack *topptr, char ch ) { stack newptr; newptr=(struct node * ) malloc( LEN ); newptr->data=ch; newptr->next=*topptr; *topptr=newptr; }
int pop_stack( stack topptr ) { stack tempptr; char popvalue; if (topptr!=NULL ) { tempptr=topptr; popvalue=topptr->data; topptr=topptr->next; free( tempptr ); return popvalue; } else return 0; }
6．用C语言编写背包问题的算法。背包问题的描述是：假设有n件质量分别为w1，w2，?，wn的物品和一个最多能装载总质量是T的背包，问能否从这n件物品中选择若干件物品装人背包，并且使被选物品的总质量恰好等于背包所能装载的最大质量，即Wxl＋Wx2＋?Wxk＝T。若能，则背包问题有解，否则背包问题无解。
#include \
#define NUMBER 20 /*定义物品个数*/ #define TRUE 1 #define FALSE 0
int stack[NUMBER];