零基础学数据结构 样张试读2

<chsdate w:st="on" year="1899" month="12" day="30" islunardate="False" isrocdate="False"><span lang="EN-US">5.3.3</span></chsdate> 链式队列实例

下面通过一个实例来说明链式队列的具体使用。

例5_3 编程判断一个字符序列是否是回文。回文是指一个字符序列以中间字符为基准两边字符完全相同，即顺着看和倒着看是相同的字符序列。如字符序列“XYZAZYX”就是回文，而字符序列"XYZBZXY"就不是回文。

分析：考察栈的“先进后出”和队列的“先进先出”的特点，可以通过构造栈和队列实现。可以把字符序列分别存入队列和堆栈，然后依次把字符逐个出队列和出栈，比较出队列的字符和出栈的字符是否相等，如果全部相等则该字符序列是回文，否则不是回文。

我们在这里采用链式堆栈和只有队尾指针的链式循环队列实现，实现代码如下。

#include<stdio.h> /*包含输出函数*/

#include<stdlib.h> /*包含退出函数*/

#include<string.h> /*包含字符串长度函数*/

#include<malloc.h> /*包含内存分配函数*/

typedef char DataType; /*类型定义为字符类型*/

/*链式堆栈结点类型定义*/

typedef struct snode

{

DataType data;

struct snode *next;

}LSNode;

/*只有队尾指针的链式循环队列类型定义*/

typedef struct QNode

{

DataType data;

struct QNode *next;

}LQNode,*LinkQueue;

void InitStack(LSNode **head)

/*带头结点的链式堆栈初始化*/

{

if((*head=(LSNode*)malloc(sizeof(LSNode)))==NULL)/*为头结点分配空间*/

{

printf("分配结点不成功");

exit(-1);

}

else

(*head)->next=NULL; /*头结点的指针域设置为空*/

}

int StackEmpty(LSNode *head)

/*判断带头结点链式堆栈是否为空。如果堆栈为空，返回1，否则返回0*/

{

if(head->next==NULL) /*如果堆栈为空，返回1，否则返回0*/

return 1;

else

return 0;

}

int PushStack(LSNode *head,DataType e)

/*链式堆栈进栈。进栈成功返回1，否则退出*/

{

LSNode *s;

if((s=(LSNode*)malloc(sizeof(LSNode)))==NULL)/*为结点分配空间，失败退出程序并返回-1*/

exit(-1);

else

{

s->data=e; /*把元素值赋值给结点的数据域*/

s->next=head->next; /*将结点插入到栈顶*/

head->next=s;

return 1;

}

}

int PopStack(LSNode *head,DataType *e)

/*链式堆栈出栈，需要判断堆栈是否为空。出栈成功返回1，否则返回0*/

{

LSNode *s=head->next; /*指针s指向栈顶结点*/

if(StackEmpty(head)) /*判断堆栈是否为空*/

return 0;

else

{

head->next=s->next; /*头结点的指针指向第二个结点位置*/

*e=s->data; /*要出栈的结点元素赋值给e*/

free(s); /*释放要出栈的结点空间*/

return 1;

}

}

void InitQueue(LinkQueue *rear)

/*将带头结点的链式循环队列初始化为空队列，需要把头结点的指针指向头结点*/

{

if((*rear=(LQNode*)malloc(sizeof(LQNode)))==NULL)

exit(-1); /*如果申请结点空间失败退出*/

else

(*rear)->next=*rear; /*队尾指针指向头结点*/

}

int QueueEmpty(LinkQueue rear)

/*判断链式队列是否为空，队列为空返回1，否则返回0*/

{

if(rear->next==rear) /*判断队列是否为空。当队列为空时，返回1，否则返回0*/

return 1;

else

return 0;

}

int EnterQueue(LinkQueue *rear,DataType e)

/*将元素e插入到链式队列中，插入成功返回1*/

{

LQNode *s;

s=(LQNode*)malloc(sizeof(LQNode)); /*为将要入队的元素申请一个结点的空间*/

if(!s) exit(-1); /*如果申请空间失败，则退出并返回参数-1*/

s->data=e; /*将元素值赋值给结点的数据域*/

s->next=(*rear)->next; /*将新结点插入链式队列*/

(*rear)->next=s;

*rear=s; /*修改队尾指针*/

return 1;

}

int DeleteQueue(LinkQueue *rear,DataType *e)

/*删除链式队列中的队头元素，并将该元素赋值给e，删除成功返回1，否则返回0*/

{

LQNode *f,*p;

if(*rear==(*rear)->next) /*在删除队头元素即出队列之前，判断链式队列是否为空*/

return 0;

else

{

f=(*rear)->next; /*使指针f指向头结点*/

p=f->next; /*使指针p指向要删除的结点*/

if(p==*rear) /*处理队列中只有一个结点的情况*/

{

*rear=(*rear)->next;/*使指针rear指向头结点*/

(*rear)->next=*rear;