Error (\队已满，不可以入队\ Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置 }
(6)取队头元素
DataType FrontQueue( CirQueue *Q) { //取队头元素
if (EmptyQueue( Q))
Error( \队空，无元素可取\ return Q->Data[Q->front]; } 关闭
3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。 解：
算法如下：
//先定义链队结构:
typedef struct queuenode{ Datatype data;
struct queuenode *next;
}QueueNode; //以上是结点类型的定义 typedef struct{
queuenode *rear;
}LinkQueue; //只设一个指向队尾元素的指针 (1)置空队
void InitQueue( LinkQueue *Q)
{ //置空队：就是使头结点成为队尾元素 QueueNode *s;
Q->rear = Q->rear->next;//将队尾指针指向头结点 while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next;
Q->rear->next=s->next; free(s);
}//回收结点空间 }
(2)判队空
int EmptyQueue( LinkQueue *Q) { //判队空
//当头结点的next指针指向自己时为空队
return Q->rear->next->next==Q->rear->next; } (3)入队
void EnQueue( LinkQueue *Q, Datatype x)
{ //入队
//也就是在尾结点处插入元素
QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点
p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;
Q->rear=p;//将尾指针移至新结点 } (4)出队
Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下 Datatype t; QueueNode *p;
if(EmptyQueue( Q ))
Error(\
p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear)
{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点
Q->rear = Q->rear->next; Q->rear->next=p->next;} else
Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; } 关闭
3.14 对于循环向量中的循环队列，写出求队列长度的公式。 解：
公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize
Queuelen=(QueueSize+rear-front)%QueueSize 关闭
3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。 解：
根据题意，可定义该循环队列的存储结构： #define QueueSize 100
typedef char Datatype ; //设元素的类型为char型 typedef struct { int quelen;
int rear;
Datatype Data[QueueSize]; }CirQueue; CirQueue *Q;
循环队列的队满条件是：Q->quelen==QueueSize
知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下： (1)判断队满
int FullQueue( CirQueue *Q)
{//判队满,队中元素个数等于空间大小 return Q->quelen==QueueSize; } (2)入队
void EnQueue( CirQueue *Q, Datatype x) {// 入队
if(FullQueue( Q))
Error(\队已满，无法入队\ Q->Data[Q->rear]=x;
Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1 Q->quelen++; } (3)出队
Datatype DeQueue( CirQueue *Q) {//出队
if(Q->quelen==0)
Error(\队已空，无元素可出队\ int tmpfront; //设一个临时队头指针
tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置
Q->quelen--;
return Q->Data[tmpfront]; }
第四章 串
4.1 简述下列每对术语的区别：
空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。 答：
●空串是指不包含任何字符的串，它的长度为零。
空白串是指包含一个或多个空格的串，空格也是字符。 ●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。
●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。
●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。
动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。
●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。 ●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。
关闭
4.2 假设有如下的串说明：
char s1[30]=\ (1)在执行如下的每个语句后p的值是什么?
p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么?
strcpy(s3,s1); strcat(s3,\ (3)调用函数strcmp(s1,s2)的返回值是什么?
(4)调用函数strcmp(&s1[5],\的返回值是什么? (5)调用函数stlen(strcat(s1,s2))的返回值是什么? 解：
(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。 因此:
执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。
执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。
` 执行p=strchr(s2,'6');之后，p的返回值是NULL。
(2)strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以: 在执行strcpy(s3,s1); 后，s3的值是\
在执行strcat(s3,\后，s3的值变成\
在执行完strcat(s3,s2);后，s3的值就成了\ (3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)
(4)首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],\中，前一个字符串值是\用它和\比较，应该是后者更大，所以返回值是小于0的数。
(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是
\数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。 关闭
4.3 设T[0..n-1]=\当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。 解：
所有的有效位移i的值为：2，5，9。
算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。 关闭
4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。
解：
算法如下：
void StrInsert(char *S, char *T, int i) {//将串T插入到串S的第i个位置上 char *Temp;
if(i<=strlen(S)) {
Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串
strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中 strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符
strcat(S,Temp);//把临时串中的字符联接到串S后面 free( Temp ); } } 关闭
4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void
StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。 解：
算法如下：
void StrDelete(char *S, int i ,int m) { //串删除