## 问题描述 设有主串S和子串T，子串T的定位就是要在主串S中找到一个与子串T相等的子串。 ## 算法简述 在[练习题1](http://blog.csdn.net/u013595419/article/details/50533721)中的算法是最简单的模式匹配算法，但是该种算法每当匹配失败时，对主串已经匹配过的字符又需要重新匹配一次，时间复杂度为O(n2)。因此这里引入了KMP算法。KMP算法与[第2章第3节练习题1 串的模式匹配(Basic) ](http://blog.csdn.net/u013595419/article/details/50533721)中算法最大的不同便是重新创建了一张跳转表，而且使得主串仅可以访问一次，子串可以一次跨过多个元素进行比较。为了从总体上来说明该算法，这里举个例子： 主串S：babcbabcabcaabcabcabcacabc 子串T：abcabcacab 在有些书中将子串T也称为模式串，但这都不重要，本讲解称其为子串。首先给出经过优化后的跳转表（next），从整体上简单的梳理下执行过程。 - **跳转表（next）** | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **next[j]** | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 1 | | **T[j]** | a | b | c | a | b | c | a | c | a | b | 跳转表最大的特色就是决定了子串一次性可以跳过多少个元素与主串进行比较，跳转表的作用是前*`next[j]-1`*个元素组成的字符串和第j号元素之前(不包括第j号元素)的*`next[j]-1`*个字符串相等，这么听起来比较抽象，举个简单的例子说明下，比如以 j=8为例。 当j=8时，查得next[8]=5，则可以推出前4个元素和第8号(不包括第8号元素)元素前面的4个元素相等。 即：T[1]T[2]T[3]T[4]组成的字符串“abca”与T[4]T[5]T[6]T[7]组成的字符串“abcd”相等。 这里简写为T1,2,3,4=T4,5,6,7 不失一般性，进行一次推广，得到广义的公式。这里令k=next[j]，即 T1,2,...,k−1==Tj−(k−1),j−(k−2),...,j−1 - **执行过程** | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c | | **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | | | **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | | | **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | | | **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | | 这里应该特别注意的是主串和子串的下标标号方式不同，**主串下标从0开始，子串下标从1开始**。 - 第一轮比较中，T[1]!=S[0]，查找跳转表得`next[1]=0`此时便可以得出子串的第一个元素与此时主串的元素不匹配，对主串的下一个元素进行比较； - 进入第二轮比较，当比较到T[4]时，发现T[4]!=S[4]，查找跳转表得`next[4]=0`，原因同上，对主串的下一个元素进行比较； - 进入第三轮比较，当比较到T[8]时，发现T[8]!=S[12]，查找跳转表得`next[8]=5`，进入下一轮比较； - 进入第四轮比较，由上轮比较中得到`next[8]=5`，比较T[5]与S[12]，结果发现T[5]!=S[12]，查找跳转表得`next[5]=1`，进入下轮比较； - 进入第五轮比较，由上轮比较中得到`next[5]=1`，比较T[1]与S[12]，然后发现T[1]=S[12]，开始挨个比较，比较到T[8]时，发现T[8]!=S[19]，查找跳转表得`next[8]=5`，进入下轮比较； - 进入第六轮比较，由上轮比较中查找过程得到`next[8]=5`，比较T[5]与S[19]，结果发现T[5]=S[19]，开始逐个比较； - 最后子串T与主串S全部比较完成，返回结果。 这里便可以推出KMP算法的核心执行步骤为： - 如果j==0，则表明子串的第一个元素不满足，则将主串的下一个元素与子串的第一个元素相比； - 如果S[i]==T[j]则开始比较下一个元素，即S[i+1]与T[j+1]； - 如果不相等，则比较S[i]与T[next[j]]； ## 算法详解 在`算法简述`中，简单的梳理了下执行流程，也推出了KMP算法的核心步骤，与[第2章第3节练习题1 串的模式匹配(Basic) ](http://blog.csdn.net/u013595419/article/details/50533721)并无太大差异，只是如果不相等的时候，并不需要对主串S的下标重置，而是对子串T进行移位便可。而真正的难点便是建立跳转表（next），因为满足跳转表（next）的元素有一个非常重要的特性便是： T1,2,...,k−1==Tj−(k−1),j−(k−2),...,j−1 而且由上面的特性很容易发现，当第j号元素与主串相应的元素“失配”时，才需要在子串中重新置位与主串再次相比，这里便引出跳转表（next）的定义： ~~~ next[j] = ⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪0,max{k|1length;j++){ for(k=1;kdata[i]==T->data[j-k+i]&&ilength){ if(T->data[i]==T->data[j]||j==0){ ++i; ++j; next[i]=j; }else{ j=next[j]; } } } ~~~ 最后再将主串S和子串T从头比较一次，熟悉下整个流程，过程如下： | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c | | **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | | | **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | | | **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | | | **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | | ### 思想3 上面虽然已经完成了建立跳转表，使用KMP算法完成了子串的查找，但是通过分析就可以发现，建立跳转表完全可以再优化一次，即一步到位。 - 主串S[4]与子串T[4]完全可以不需要，因为T[4]==T[1]，已经判断出T[4]!=S[4]，也就无需在额外的判断T[1]!=S[4]了； - 主串S[12]与子串T[2]亦完全可以不要 ，原因同上，已知T[5]==T[2] ，也就无需判断T[2] !=S[12]了； 先对跳转表完成优化，如下所示： - **跳转表（next）** | j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **next[j]** | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 5 | 0 | 1 | | **T[j]** | a | b | c | a | b | c | a | c | a | b | - **执行过程** | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 22 | 23 | 24 | |-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----|-----| | **S[i]** | b | a | b | c | b | a | b | c | a | b | c | a | a | b | c | a | b | c | a | b | c | a | c | a | b | c | | **T** | a | | | | | | | | | | | | | | | | | | | | | | | | | | | **T** | | a | b | c | a | | | | | | | | | | | | | | | | | | | | | | | **T** | | | | | | a | b | c | a | b | c | a | c | | | | | | | | | | | | | | | **T** | | | | | | | | | a | b | c | a | b | | | | | | | | | | | | | | | **T** | | | | | | | | | | | | | a | b | c | a | b | c | a | c | | | | | | | | **T** | | | | | | | | | | | | | | | | a | b | c | a | b | c | a | c | a | b | | 对上述过程进行总结，完成对算法的优化，描述如下： ~~~ void BuildNext(String* T, int next[]) { int i, j; i=1; j=0; next[1]=0; while(ilength){ if(T->data[i]==T->data[j]||j==0){ ++i; ++j; if(T->data[i]!=T->data[j]){ next[i]=j; }else{ next[i]=next[j]; } }else{ j=next[j]; } } } ~~~ 至此，KMP算法的讲解算是完成了，具体代码见附件。 ## 附件 ~~~ #include #include #define MaxSize 100 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int length; }String; void StrCreatS(String*); void StrCreatT(String*); void Print(String*); void BuildNext(String*,int*); int KMP(String*,String*,int*); int main(int argc,char* argv[]) { String *s; s=(String*)malloc(sizeof(String)); StrCreatS(s); String *t; t=(String*)malloc(sizeof(String)); StrCreatT(t); int next[MaxSize]={0}; BuildNext(t,next); int flag=KMP(s,t,next); if(flag!=-1){ printf("Position is %d.\n",flag+1); }else{ printf("Illege Find!\n"); } return 0; } //创建主串 void StrCreatS(String* S){ char x; S->length=0; printf("Input String_S(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[S->length++]=x; scanf("%c",&x); } getchar(); } //创建子串 void StrCreatT(String* S){ char x; S->length=0; printf("Input String_T(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[++S->length]=x; scanf("%c",&x); } getchar(); } //打印字符串 void Print(String *S) { for(int i=0;ilength;i++){ printf("%c",S->data[i]); } printf("\n"); } //建立跳转表 void BuildNext(String* T, int next[]) { int i, j; i=1; j=0; next[1]=0; while(ilength){ if(T->data[i]==T->data[j]||j==0){ ++i; ++j; if(T->data[i]!=T->data[j]){ next[i]=j; }else{ next[i]=next[j]; } }else{ j=next[j]; } } } //KMP算法的核心 int KMP(String* S, String* T,int next[]) { int i=0, j=1; while(ilength&&jlength){ if(S->data[i]==T->data[j]||j==0){ ++i; ++j; }else{ j = next[j]; } } if(j==T->length){ return i+1-T->length; }else{ return -1; } } ~~~ 参考文献 Knuth D E, Morris J H, Pratt V R. Fast Pattern Matching in Strings.[J]. Siam Journal on Computing, 1977, 6(2):323-350. 参考Blog [http://blog.csdn.net/joylnwang/article/details/6778316](http://blog.csdn.net/joylnwang/article/details/6778316) [http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)

## 问题描述 设有主串s和子串t,子串t的定位就是要在主串s中找到一个与子串t相等的子串。 通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。 模式匹配成功是指在目标串s中找到一个模式串t；不成功则指目标串s中不存在模式串t。 ## 算法描述 本算法与[第1章第2节练习题14 判断子序列 ](http://blog.csdn.net/u013595419/article/details/50510292)本质相同，那么运用同样的算法也可以解决该问题。 首先对s和t同时进行访问，如果t中的元素有一个与s不匹配，那么对字符串s和字符串t的下标进行重置，s的下标重置为与t开始相比的下一个下标，t的下标置0。 如果s或t有一个已经访问结束，那么判断t是否访问结束。如果是，则标志已经访问完成；如果不是，则表示没有在s中找到子串t。 ## 算法思想 ~~~ int FindSub(String* S, String* T){ int i=0,j=0; while(ilength&&jlength){ if(S->data[i]==T->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j==T->length){ return 0; }else{ return -1; } } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include #define MaxSize 100 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int length; }String; void StrCreat(String*); void Print(String*); int FindSub(String*,String*); int main(int argc,char* argv[]) { String *s; s=(String*)malloc(sizeof(String)); StrCreat(s); String *t; t=(String*)malloc(sizeof(String)); StrCreat(t); int flag=FindSub(s,t); if(flag==0){ printf("t is subString of s!\n"); }else{ printf("t is not subString of s!\n"); } return 0; } //创建串 void StrCreat(String* S){ char x; S->length=0; printf("Input String_S(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[S->length++]=x; scanf("%c",&x); } getchar(); } //模式匹配，寻找s中是否存在子串t int FindSub(String* S, String* T){ int i=0,j=0; while(ilength&&jlength){ if(S->data[i]==T->data[j]){ i++; j++; }else{ i=i-j+1; j=0; } } if(j==T->length){ return 0; }else{ return -1; } } //打印所有串元素 void Print(String* S){ for(int i=0;ilength;i++){ printf("%c",S->data[i]); } printf("\n"); } ~~~

关于串的基本定义已经在[第2章栈和队列以及串](http://blog.csdn.net/u013595419/article/details/50516508#t6)中介绍过了，与栈和队列类似，同样存在顺序结构存储的串（这里简称顺序串）和链式结构存储的串（这里简称链串）。 ## 一.顺序串 ### 1.1定义 串的顺序实现是指分配一块连续的存储单元用于串中的元素，并附设表示串长度的标志。 串的顺序结构存储可以描述为： ~~~ typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int length; }String; ~~~ ### 1.2基本操作 ### 1.2.1创建串 输入字符元素，以“#”号作为结束标志。 ~~~ void StrCreat(String* S){ char x; S->length=0; printf("Input String_S(End of '#'!):\n"); scanf("%c",&x); while(x!='#'){ S->data[S->length++]=x; scanf("%c",&x); } } ~~~ ### 1.2.2求串长度 因为串的定义中有length变量，只需返回结果便可。 ~~~ int StrLength(String* S){ return S->length; } ~~~ ### 1.2.3拷贝字符串 将字符串S拷贝到字符串T中，对字符串依次访问，同时赋值于字符串T即可完成拷贝。 ~~~ void StrCopy(String* S, String* T){ for(int i=0;ilength;i++){ T->data[i]=S->data[i]; } T->length=S->length; } ~~~ ### 1.2.4比较字符串大小 字符串大小比较实际是比较ASCII码大小，从左向右依次比较，如果此时哪个字符串的ASCII码值比较大，则返回结果；如果两个字符串长度不相等，但前面若干个字符均相等，则长度大的字符串比较大。 ~~~ int StrCompare(String* S,String* T){ int i=0; while(i!=S->length&&i!=T->length){ if(S->data[i]data[i]){ return -1; }else if(S->data[i]>T->data[i]){ return 1; }else{ i++; } } if(ilength){ return 1; }else if(ilength){ return -1; }else{ return 0; } } ~~~ ### 1.2.5连接字符串 将字符串T连接在字符串S后，注意此时S的长度以便，注意修改length变量。 ~~~ void StrConcat(String* S, String* T){ int i=S->length; for(i=i+1;ilength+T->length;i++){ S->data[i]=T->data[i-S->length]; } S->length=i; } ~~~ ### 1.2.6以串S中pos位置开始的len个字符生成子串Sub 因为采用的是顺序存储结构，可以使用函数随机访问，直接找到pos位置，然后将其后len个字符串均赋值给新的子串T便可。 ~~~ String* SubString(String*S,int pos,int len){ String *T; T=(String*)malloc(sizeof(String)); T->length=0; if(pos>S->length||(pos+len)>S->length){ printf("Illege Position!\n"); exit(0); } for(int i=pos;idata[T->length++]=S->data[i]; } return T; } ~~~ ## 二.链串 ### 2.1定义 采用链式存储的串称为链串。一般采用不带头结点的单链表实现。 链串的数据结构描述如下： ~~~ typedef struct SNode { ElemType data; struct SNode *next; }String; ~~~ 因为采用链式存储时的串与[第1章的单链表](http://blog.csdn.net/u013595419/article/details/50481785)操作类似，这里便不再详细说明。

### 问题描述 汽车轮渡口，过江渡船每次能载10辆车过江。过江车分为客车和货车类，上渡船有如下规定： 1).同类车先到先上船； 2).客车先于货车上渡船，其每上4辆客车，才允许放上一辆货车； 3).若等待客车不足4辆，则以货车代替； 4).若无货车等待，允许客车都上船。 试设计一个算法模拟渡口管理 ## 算法思想 经过分析，发现此题实际上就是队列的基本操作，唯一的不同就是在入队的时候，对于顺序进行了限制。 - 使用队列Q表示每次载渡的车辆，队列Qp表示客车，Qt表示货车队列； - 如果Qp中元素足够，则每从队列Qp中出队4个元素，从队列Qt中出队1元素，直到队列Q的长度为10； - 若队列Qp中元素不充分，则直接使用队列Qt中的元素补齐。 ## 算法描述 ~~~ void manager(){ if(IsEmpty(&Qp)!=0&&car<4){ DeQueue(&Qp,&e); EnQueue(&Q,e); car++; count++; }else if(car==4&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); car=0; count++; }else{ while(count<=MaxSize&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); count++; } } if(IsEmpty(&Qt)==0&&IsEmpty(&Qp)==0){ count=11; } } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #define MaxSize 10 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int front, rear; }SqQueue; void InitQueue(SqQueue*); void EnQueue(SqQueue*, ElemType); void DeQueue(SqQueue*, ElemType*); int IsEmpty(SqQueue*); void Mangager(SqQueue*, SqQueue*, SqQueue*); void PrintQueue(SqQueue); int main(int argc,char* argv[]) { SqQueue Q; SqQueue Qp;//客车 SqQueue Qt;//货车 InitQueue(&Q); InitQueue(&Qp); InitQueue(&Qt); ElemType x='P'; for(int i=0;i<6;i++){ EnQueue(&Qp,x); } ElemType y='T'; for(int i=0;i<6;i++){ EnQueue(&Qt,y); } int count=0; int car=0; ElemType e; //渡口模拟 while(count<=MaxSize){ if(IsEmpty(&Qp)!=0&&car<4){ DeQueue(&Qp,&e); EnQueue(&Q,e); car++; count++; }else if(car==4&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); car=0; count++; } else{ while(count<=MaxSize&&IsEmpty(&Qt)!=0){ DeQueue(&Qt,&e); EnQueue(&Q,e); count++; } } if(IsEmpty(&Qt)==0&&IsEmpty(&Qp)==0) { count=11; } } PrintQueue(Q); return 0; } /*---------------------------------------------------------------*/ void InitQueue(SqQueue* Q) { Q->front=0; Q->rear=0; } void EnQueue(SqQueue* Q, ElemType x) { if(Q->rear==MaxSize-1){ return; } Q->data[Q->rear++]=x; } void DeQueue(SqQueue* Q, ElemType *x) { if(Q->front==Q->rear&&Q->front==0){ return; } *x=Q->data[Q->front++]; } ~~~

## 问题描述 利用两个栈S1，S2来模拟一个队列，已知栈的4的运算定义如下： Push(S,x); 元素x入栈S Pop(S,x); S出栈并将出栈的值赋给x StackEmpty(S); 判断栈是否为空 StackOverflow(S); 判断栈是否满 Enqueue; 将元素x入队 Dequeue; 出队，并将出队元素存储在x中 QueueEmpty; 判断队列是否为空 那么如何利用栈的运算实现该队列的3个运算？ ## 算法思想 由于栈先进后出的特性，使用两个栈便可完成两次先进先出的过程，即相当于先进先出。 我们设置两个栈S1，S2。 对S2的出栈操作用作出队，若S2为空，则现将S1中所有元素送入S2； 对S1的入栈操作用作入队，若S1为满，必须先保证S2为空，才能将S1中的元素全部插入S2中； ## 算法描述 ~~~ //入队 int EnQueue(SqStack *S1,SqStack *S2,ElemType x) { if(StackOverflow(S1)!=0){ Push(S1,x); return 0; } if(StackOverflow(S1)==0&&StackEmpty(S2)!=0){ printf("The Queue is full!\n"); return -1; } if(StackOverflow(S1)==0&&StackEmpty(S2)==0){ while(StackEmpty(S1)!=0){ Pop(S1,&x); Push(S2,x); } return 0; } return -1; } //出队 int DeQueue(SqStack *S1,SqStack *S2, ElemType* x) { if(StackEmpty(S2)!=0){ Pop(S2,x); }else if(StackEmpty(S1)==0){ printf("The queue is empty!\n"); return -1; }else{ while(StackEmpty(S1)!=0){ Pop(S1,x); Push(S2,*x); } Pop(S2,x); } return 0; } //判断队列是否为空 int QueueEmpty(SqStack *S1, SqStack *S2) { if(StackEmpty(S1)==0&&StackEmpty(S2)==0){ printf("The Queue is empty!\n"); return 0; }else{ return -1; } } ~~~ 具体代码见附件。 ~~~ #include #include #define MaxSize 10 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack*); void Push(SqStack*, ElemType); void Pop(SqStack*, ElemType*); int StackEmpty(SqStack*); int StackOverflow(SqStack*); void Print(SqStack*); int EnQueue(SqStack*,SqStack*,ElemType); int DeQueue(SqStack*,SqStack*,ElemType*); int QueueEmpty(SqStack*, SqStack*); int main(int argc,char* argv[]) { SqStack S1; SqStack S2; InitStack(&S1); InitStack(&S2); for(int i=0;i<10;i++){ EnQueue(&S1,&S2,i); } ElemType x; DeQueue(&S1,&S2,&x); printf("%4d\n",x); DeQueue(&S1,&S2,&x); printf("%4d\n",x); DeQueue(&S1,&S2,&x); printf("%4d\n",x); return 0; } //入队 int EnQueue(SqStack *S1,SqStack *S2,ElemType x) { if(StackOverflow(S1)!=0){ Push(S1,x); return 0; } if(StackOverflow(S1)==0&&StackEmpty(S2)!=0){ printf("The Queue is full!\n"); return -1; } if(StackOverflow(S1)==0&&StackEmpty(S2)==0){ while(StackEmpty(S1)!=0){ Pop(S1,&x); Push(S2,x); } return 0; } return -1; } //出队 int DeQueue(SqStack *S1,SqStack *S2, ElemType* x) { if(StackEmpty(S2)!=0){ Pop(S2,x); }else if(StackEmpty(S1)==0){ printf("The queue is empty!\n"); return -1; }else{ while(StackEmpty(S1)!=0){ Pop(S1,x); Push(S2,*x); } Pop(S2,x); } return 0; } //判断队列是否为空 int QueueEmpty(SqStack *S1, SqStack *S2) { if(StackEmpty(S1)==0&&StackEmpty(S2)==0){ printf("The Queue is empty!\n"); return 0; }else{ return -1; } } /*--------------------------------------------*/ //初始化栈 void InitStack(SqStack *S) { S->top=-1; } //入栈 void Push(SqStack *S, ElemType x) { if(S->top==MaxSize-1){ printf("The Stack is full!\n"); return; } S->data[++S->top]=x; } //出栈 void Pop(SqStack *S, ElemType *x) { if(S->top==-1){ printf("The Stack is empty!\n"); return; } *x=S->data[S->top--]; } //判断栈是否为空 int StackEmpty(SqStack *S) { if(S->top==-1){ return 0; } return -1; } //判断栈是否已满 int StackOverflow(SqStack *S) { if(S->top==MaxSize-1){ return 0; } return -1; } //打印栈中所有元素 void Print(SqStack *S) { int i=S->top; while(i!=-1){ printf("%4d",S->data[i]); i--; } printf("\n"); } ~~~

## 问题描述 > Q是一个队列，S是一个空栈，实现将队列中的元素逆置的算法 ## 算法思想 > 因为Q是一个队列，如果仅仅按照队列先进先出的特性时无法完成自身元素逆置操作的，而题目中又给出了一个可用栈，那么我们只需借助栈先进后出的特性完成元素逆置。 将队列中的元素逐个出队，然后入栈，最后再入队即可完成队列元素的逆置。 ## 算法描述 ~~~ //创建队列 while(x!=999){ EnQueue(&Q,x); scanf("%d",&x); } //出队->入栈 while(Q.front!=Q.rear){ DeQueue(&Q,&x); EnStack(&S,x); } InitQueue(&Q); //出栈->入队 while(S.top!=-1){ DeStack(&S,&x); EnQueue(&Q,x); } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include #define MaxSize 10 typedef int ElemType; //定义队列 typedef struct{ ElemType data[MaxSize]; int front, rear; }SqQueue; //定义栈 typedef struct{ ElemType data[MaxSize]; int top; }SqStack; void InitQueue(SqQueue*); void EnQueue(SqQueue*,ElemType); void DeQueue(SqQueue*,ElemType*); void InitStack(SqStack*); void EnStack(SqStack*,ElemType); void DeStack(SqStack*,ElemType*); void PrintQueue(SqQueue*); int main(int argc,char* argv[]) { SqQueue Q; SqStack S; InitQueue(&Q); InitStack(&S); ElemType x; scanf("%d",&x); while(x!=999){ EnQueue(&Q,x); scanf("%d",&x); } while(Q.front!=Q.rear){ DeQueue(&Q,&x); EnStack(&S,x); } InitQueue(&Q); while(S.top!=-1){ DeStack(&S,&x); EnQueue(&Q,x); } PrintQueue(&Q); return 0; } //初始化队列 void InitQueue(SqQueue *Q) { Q->front=0; Q->rear=0; } //入队 void EnQueue(SqQueue *Q, ElemType x) { Q->data[Q->rear++]=x; } //出队 void DeQueue(SqQueue *Q, ElemType *x) { if(Q->front==Q->rear){ printf("The Queue is empty!\n"); } *x=Q->data[Q->front++]; } //初始化栈 void InitStack(SqStack *S) { S->top=-1; } //入栈 void EnStack(SqStack *S,ElemType x) { S->data[++S->top]=x; } //出栈 void DeStack(SqStack *S,ElemType *x) { if(S->top==-1){ printf("The stack is empty!\n"); return; } *x=S->data[S->top--]; } //打印全部队列元素 void PrintQueue(SqQueue *Q) { while(Q->front!=Q->rear){ printf("%4d",Q->data[Q->front++]); } printf("\n"); } ~~~

## 问题描述 > 设有两个栈s1,s2都采用顺序栈方式，并且共享一个存储区[0,…,MaxSize-1]，为了尽量利用空间，减少溢出的可能，可采用栈顶相向，迎面增长的方式。试设计s1,s2有关入栈和出栈的操作算法。 ## 算法思想 > 因为两个栈公用一个空间，假设一个栈为0#，规定其为空时top[0]==-1；另一个栈为1#规定其为空时，top[1]==MaxSize； 入栈时，先确定栈号是否合法，然后查看是对0#栈还是1#栈进行操作，入栈操作和顺序栈的入栈操作并无太大不同。选定之后进行入栈操作。这里应该注意此共享栈是否已满，如果已满则不能进行入栈操作。如若入栈成功则返回0；入栈失败则返回-1； 出栈时，先确定栈号是否合法，然后查看是对0#栈还是1#栈进行操作，出栈操作和顺序栈的出栈操作并无太大不同。选定之后进行出栈操作。如果出栈成功返回0；出栈失败返回-1； 综上，算法描述如下： ## 算法描述 ~~~ //共享栈的入栈操作 int Push(SqStack*s, ElemType x, int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } if(s->top[1]-s->top[0]==1){ printf("The stack is full!\n"); return -1; } switch(n){ case 0:s->data[++s->top[0]]=x;break; case 1:s->data[--s->top[1]]=x;break; } return 0; } //共享栈的出栈操作 int Pop(SqStack *s, ElemType* x,int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } switch(n){ case 0: if(s->top[0]==-1){ printf("The stack[0] is empty!\n"); } *x=s->data[s->top[0]--]; break; case 1: if(s->top[1]==MaxSize){ printf("The stack[1] is empty!\n"); } *x=s->data[s->top[1]++]; break; } return 0; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include #define MaxSize 100 typedef int ElemType; typedef struct{ ElemType data[MaxSize]; int top[2]; }SqStack; void InitStack(SqStack*); int Push(SqStack*,ElemType,int); int Pop(SqStack*,ElemType*,int); int main(int argc,char* argv[]) { SqStack s; InitStack(&s); ElemType x=5; int n=0; int flagPush; flagPush=Push(&s,x,n); if(flagPush){ printf("Push false!\n"); }else{ printf("Push %d success!\n",x); } int flagPop; flagPop=Pop(&s,&x,n); if(flagPop){ printf("Pop false!\n"); }else{ printf("Pop %d success!\n",x); } return 0; } //初始化共享栈 void InitStack(SqStack *s) { s->top[0]=-1; s->top[1]=MaxSize; } //入栈操作 int Push(SqStack*s, ElemType x, int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } if(s->top[1]-s->top[0]==1){ printf("The stack is full!\n"); return -1; } switch(n){ case 0:s->data[++s->top[0]]=x;break; case 1:s->data[--s->top[1]]=x;break; } return 0; } //出栈操作 int Pop(SqStack *s, ElemType* x,int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } switch(n){ case 0: if(s->top[0]==-1){ printf("The stack[0] is empty!\n"); } *x=s->data[s->top[0]--]; break; case 1: if(s->top[1]==MaxSize){ printf("The stack[1] is empty!\n"); } *x=s->data[s->top[1]++]; break; } return 0; } ~~~

关于队列的基本定义已经在[第2章栈和队列以及串](http://blog.csdn.net/u013595419/article/details/50516508#t3)中说到了，与[栈](http://blog.csdn.net/u013595419/article/details/50518427)类似，同样有使用顺序结构存储的队列（这里简称顺序队列）和链式结构存储的队列（ 这里简称链队列）。 ## 一. 顺序队列 ### 1.1定义 队列的顺序实现是指分配一块连续的存储单元用于存放队列中的元素，并附设两个指针front和rear分别指示头元素和队尾元素。设队头指针指向队头元素的位置，队尾指针指向队尾元素的下一个位置。 队列的顺序存储类型则可以描述为： ~~~ #define MaxSize 50 typedef struct{ ElemType data[MaxSize]; int front,rear; }SqQueue; ~~~ 这里对顺序队列的判断条件进行说明。 > - 队空条件：Q.front==Q.rear==0 > - 队满条件：> ~~Q.rear==MaxSize~~ 这里应当注意到，上述判断队满条件实际是不正确的，比如当front指向队尾元素，而rear的值刚好等于MaxSize。 此时从data[0]到data[MaxSize−2]的所有元素中，均没有存储任何元素，但是根据上述判断条件却“已满”，造成“假溢出”。 为了解决这个问题，常见的有两种解决方法。 > 1. 将队列元素向前“平移”重新占用0至rear-front-1的空间 > 1. 将队列看成首尾相连的循环队列 因为平移会浪费大量的无用时间，因此一般使用循环队列解决判断是否队满的问题。 ## 二.循环队列 ### 2.1定义 循环队列将一个顺序队列“臆造”成一个环状的空间，即把存储队列元素的表从逻辑上看成一个环，物理上依旧使用顺序存储结构。 在引入循环队列的同时，也引入判断队列是否为空或满的三种常见方法。 **1). 牺牲一个单元来区分队空和队满** > - 队空条件：Q.front==Q.rear > - 队满条件：(Q.rear+1)%MaxSize==Q.front > - 队列中元素的个数：(Q.rear-Q.front+MaxSize)%MaxSize **2). 增设表示元素个数的数据成员size** > 队空条件：Q.size==0 队满条件：Q.size=MaxSize 队列中元素的个数：Q.size **3). 增设数据成员标志tag** > 队空条件：Q.tag==0&&Q.front==Q.rear 队满条件：Q.tag==1&&Q.front==Q.rear ### 2.2基本操作 初始化操作，完成对队首指针和队尾指针的复位操作。 ~~~ void InitQueue(SqQueue* Q) { Q->front=0; Q->rear=0; } ~~~ 入队操作，因为队列中规定队尾指针指向队尾元素的下一个位置，因此在入队后需对队尾指针自增1。 ~~~ int EnQueue(SqQueue* Q, ElemType x) { if((Q->rear+1)%MaxSize==Q->front){ return -1; } Q->data[Q->rear]=x; Q->rear=(Q->rear+1)%MaxSize; return 0; } ~~~ 出队操作，如果队空则返回-1；否则返回数据元素。 ~~~ int DeQueue(SqQueue* Q, ElemType* x) { if(Q->rear==Q->front){ return -1; } *x=Q->data[Q->front]; Q->front=(Q->front+1)%MaxSize; return 0; } ~~~ 判断队列是否为空，若为空则返回0；否则返回-1。 ~~~ int QueueEmpty(SqQueue* Q) { if(Q->rear==Q->front){ return 0; }else{ return -1; } } ~~~ ## 三.链队列 ### 3.1定义 采用单链表结构存储的队列称为链队列。它同时带有指向队头结点的指针点和指向队尾结点的尾结点，一般为了方便在队头取出元素和在队尾中添加元素，故一般采用待有头节点的单链表。 如图所示：  这里对链队列的判断条件进行说明。 > - 队空条件：Q.front==Q.rear 队列的链式存储类型则可以描述为： ~~~ typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; typedef struct{ LNode *front; LNode *rear; }LinkQueue; ~~~ 链队特别适合元素数据变化比较大和需要同时使用多个队列的情形，因为不会存在由于队满而溢出的问题。 ### 3.2基本操作 初始化操作。 ~~~ void InitQueue(LinkQueue *Q) { Q->front=(LNode*)malloc(sizeof(LNode)); Q->rear=Q->front; Q->front->next=NULL; } ~~~ 判断队列是否为空，如若为空，则返回0；否则返回-1。 ~~~ int QueueEmpty(LinkQueue *Q) { if(Q->front==Q->rear){ return 0; }else{ return -1; } } ~~~ 入队操作，创建新的结点，然后插入队尾 ~~~ void EnQueue(LinkQueue *Q, ElemType x) { LNode *s; s=(LNode*)malloc(sizeof(LNode)); s->data=x; Q->rear->next=s; Q->rear=s; } ~~~ 出队操作，如果队列为空，则返回-1；若不为空，则返回0。 ~~~ int DeQueue(LinkQueue *Q, ElemType *x) { LNode *p; if(Q->front==Q->rear){ return -1; } p=Q->front->next; *x=p->data; Q->front->next=p->next; if(Q->rear==p){ Q->rear=Q->front; } free(p); return 0; } ~~~ ## 四.双端队列 ### 4.1定义 双端队列是允许两端都可以进行入队和出队操作的队列。 在双端队列进队时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面。在双端队列出队时，无论前端还是后端出队，先出的元素排列在后出的元素的前面。如下图所示：  输出受限的双端队列：允许在一端进行插入和删除，但在另一端只允许插入的双端队列 称为输出受限的双端队列。如下图所示：  输入受限的双端队列：允许在一端进行插入和删除，但在另一端只允许删除的双端队列，而如果限定双端队列从某个端点插入的元素只 能从该端点删除，则该双端队列就蜕变为两个栈底相邻接的栈了。如下图所示： 

## 问题描述 > 试写一算法来判断单链表的前n个字符是否中心对称。 例如xyx，xyyx都是中心对称 ## 算法思想 > 在[第1章第2节练习题19 判断循环双链表对称](http://blog.csdn.net/u013595419/article/details/50511050)中已经初次涉及到了判断链表中心对称的问题，但是因为单链表只能从前往后遍历，因此不能使用与其相同算法进行解决，那么借助栈来判断单链表中的数据是否中心对称。 > 将单链表的前一半元素依次入栈，遍历到单链表的后一半元素的第一个元素时，便从栈中弹出一个元素，对它们俩开始比较。 > - 若相等，则将链表中的下一个元素与栈中再次弹出的元素进行比较，直至单链表到末尾，而且如果此时栈也为空栈，则可得出此单链表是中心对称的结论； > - 若不相等，则单链表不是中心对称。 ## 算法描述 ~~~ int JudgeSym(LNode* head,int n) { LNode *p=head->next; char s[n/2]; int i; for(i=0;idata; p=p->next; } i--; if(n%2){ p=p->next; } while(p&&p->data==s[i]){ p=p->next; i--; } if(i==-1){ return 0; }else{ return -1; } } ~~~ 具体代码见附件。 ## 附件 ~~~ typedef char ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); int JudgeSym(LNode*,int); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=CreatList(head); Print(head); int flag; int n=5; flag=JudgeSym(head,n); if(flag){ printf("The link is not symmetery before %d charactor!\n",n); }else{ printf("The link is symmetery before %d charachtor!\n",n); } return 0; } //尾插法建立单链表 LinkList CreatList(LNode* head) { LNode *L; LNode *r=head; ElemType x; scanf("%c",&x); while(x!='\n'){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%c",&x); } return head; } //判断中心对称 int JudgeSym(LNode* head,int n) { LNode *p=head->next; char s[n/2]; int i; for(i=0;idata; p=p->next; } i--; if(n%2){ p=p->next; } while(p&&p->data==s[i]){ p=p->next; i--; } if(i==-1){ return 0; }else{ return -1; } } //打印全部结点 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4c",p->data); p=p->next; } printf("\n"); } ~~~

## 问题描述 > 假设I和O分别表示入栈和出栈操作。栈的初状和终态均为空，入栈和出栈的操作序列可表示仅由I和O组成的序列，可以操作的序列称为合法序列，否则称为非法序列。 试写一个算法完成对下列输入序列的合法性的判断。 A. IOIIOIOO B. IOOIOIIO C.IIIOIOIO D.IIIOOIOO ## 算法思想 > 将一个指定序列进行入栈，每扫描至任一位置均需检测出栈次数（即O的个数）是否小于入栈的次数（即I的个数），若大于则为非法数列。扫描结束后再判断入栈和出栈次数是否相等，若不相等，则为非法数列。 算法具体描述如下所示： ## 算法描述 ~~~ int JudgeLegal(SqStack *s) { int i=0; int j=0; int k= while(s->data[i]!='\0'){ switch(s->data[i]){ case 'I':j++;break; case 'O':k++; if(k>j){ return -1; } break; } i++; } if(j!=k){ return -1; }else{ return 0; } } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include #define MaxSize 100 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack*); void Push(SqStack*); int JudgeLegal(SqStack*); int main(int argc,char* argv[]) { SqStack s; InitStack(&s); Push(&s); int Flag=JudgeLegal(&s); if(Flag){ printf("The subsqence illegal!\n"); }else{ printf("The subsquence legal!\n"); } return 0; } //初始化栈 void InitStack(SqStack *s) { s->top=-1; } //入栈 void Push(SqStack *s) { ElemType x; do{ scanf("%c",&x); s->data[++s->top]=x; }while(x!='\n'); } //判断合法性 int JudgeLegal(SqStack *s) { int i=0; int j=0; int k=0; while(s->data[i]!='\0'){ switch(s->data[i]){ case 'I':j++;break; case 'O':k++;if(k>j){return -1;}break; } i++; } if(j!=k){ return -1; }else{ return 0; } } ~~~

栈作为一种受限的线性表，同样可以划分为顺序结构存储的栈（这里简称顺序栈）和链式结构存储的栈（这里简称链栈）。 ## 一.顺序栈 ### 1.1定义 栈的顺序存储称为顺序栈，是利用一组地址连续的存储单元存放从栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。如图所示：  栈的顺序存储类型则可以描述为： ~~~ typedef struct{ ElemType data[MaxSize]; int top; }SqStack; ~~~ 这里对顺序栈的判断条件进行说明。 > - 栈空条件：top==-1 > - 栈满条件：top==MaxSize-1 > - 栈长：top+1 ### 1.2基本操作 ### 1.2.1初始化操作 完成对栈顶指针的复位操作。 ~~~ void InitStack(SqStack* s) { s->top=-1; } ~~~ ### 1.2.2判空操作 如果栈为空，则返回0；如果栈不为空，则返回-1。 ~~~ int StackEmpty(SqStack* s) { if(s->top==-1){ return 0; }else{ return -1; } } ~~~ ### 1.2.3入栈操作 首先判断栈是否已满，如果栈已经满了，则返回-1；如若没有满，则在栈顶中插入元素，并返回0。 ~~~ int Push(SqStack* s, ElemType x) { if(s->top==MaxSize-1){ return -1; } s->data[++s->top]=x; return 0; } ~~~ ### 1.2.4出栈操作 首先判断栈是否为空，如果已经为空，则返回-1；如果不为 空，则取得栈顶元素，并返回0。 ~~~ int Pop(SqStack* s, ElemType* x) { if(s->top==-1){ return -1; } *x=s->data[s->top--]; return 0; } ~~~ ### 1.2.5读栈顶元素 首先判断栈是否为空，如果为空，则返回-1；如果不为空，则返回栈顶元素，并返回0。 ~~~ int GetTop(SqStack* s, ElemType *x) { if(s->top==-1){ return -1; } *x=s->data[s->top]; return 0; } ~~~ ## 二.共享栈 ### 2.1定义 利用栈底位置相对不变的特性，可以让两个顺序栈共享一个一维数据空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间中间延伸。如图所示：  则共享栈的数据结构可以描述为： ~~~ typedef struct{ ElemType data[MaxSize]; int top[2]; }SqStack; ~~~ 这里对共享栈的判断条件进行说明。 > - 栈空条件：0号栈【top[0]==-1】；1号栈【top[1]==MaxSize】 > - 栈满条件：top1-top0=1 ### 2.2基本操作 ### 2.2.1初始化操作 完成对栈顶指针的复位操作，按照上述规定，0#栈为空，则top[0]==-1；若1#栈为空，则top[1]==MaxSize; ~~~ void InitStack(SqStack *s) { s->top[0]=-1; s->top[1]=MaxSize; } ~~~ ### 2.2.2判空操作 同样根据上述规定，0#栈为空，则top[0]==-1；若1#栈为空，则top[1]==MaxSize；那么若两个栈均为空则返回0；如果栈不为空，则返回-1。 ~~~ int StackEmpty(SqStack* s) { if(s[0]->top==-1&&s[1]->top==MaxSize){ return 0; }else{ return -1; } } ~~~ ### 1.2.3入栈操作 先确定栈号是否合法，然后查看是对0#栈还是1#栈进行操作，入栈操作和顺序栈的入栈操作并无太大不同。选定之后进行入栈操作。这里应该注意此共享栈是否已满，如果已满则不能进行入栈操作。如若入栈成功则返回0；入栈失败则返回-1。 ~~~ int Push(SqStack*s, ElemType x, int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } if(s->top[1]-s->top[0]==1){ printf("The stack is full!\n"); return -1; } switch(n){ case 0:s->data[++s->top[0]]=x;break; case 1:s->data[--s->top[1]]=x;break; } return 0; } ~~~ ### 2.2.4出栈操作 先确定栈号是否合法，然后查看是对0#栈还是1#栈进行操作，出栈操作和顺序栈的出栈操作并无太大不同。选定之后进行出栈操作。如果出栈成功返回0；出栈失败返回-1。 ~~~ int Pop(SqStack *s, ElemType* x,int n) { if(n<0||n>1){ printf("The stack number is false!\n"); return -1; } switch(n){ case 0: if(s->top[0]==-1){ printf("The stack[0] is empty!\n"); } *x=s->data[s->top[0]--]; break; case 1: if(s->top[1]==MaxSize){ printf("The stack[1] is empty!\n"); } *x=s->data[s->top[1]++]; break; } return 0; } ~~~ ## 三.链栈 ### 3.1定义 采用链式存储的栈称为链栈。 链栈的优点便是便于多个栈共享存储空间和提高其效率，而且不存在栈满上溢的情况。通常采用单链表实现，并规定所有的操作都是在单链表的表头进行的，这里规定链栈没有头节点。如图所示：  链栈的数据结构的描述如下： ~~~ typedef struct LinkNode{ ElemType data; struct LinkNode *next; }LinkStack; ~~~ 因为采用链式存储时的栈与[第1章的单链表](http://blog.csdn.net/u013595419/article/details/50481785)操作类似，这里便不再详细说明。但应当注意区分带头结点的单链表与不带头结点的单链表操作略有不同。 注：在栈的操作中，经常会求到对于n个不同的元素进栈，则出栈序列的个数为多少？ 对于这种题，我们可以引入[卡特兰（Catalan）数](http://baike.baidu.com/link?url=9WJdSO-OKxLm_8wzl8D36hgpYKLRgKx053fSa_cteOBDaO_1YLwbVKV29CreU3Vo7Osopzf00xgGVEEgqLCuXa)进行解决。答案为：1n+1(2nn)

在[绪论](http://blog.csdn.net/u013595419/article/details/50461536)中，我们介绍了数据结构三要素， [第1章](http://blog.csdn.net/u013595419/article/details/50461712)中，讲解了逻辑结构分类中线性结构的第一个部分——一般线性表，这章开始讲解逻辑结构线性结构的第二个部分——受限的线性表。这里先巩固下逻辑结构的分类，如下图所示：  受限线性表最简单直白的理解便是插入，删除，查找等操作时，不能随心所欲的进行，必须遵循一定的限制（规则）。 ## 一.栈 ### 1.1定义 栈（stack）是一种只允许在一端进行插入或删除操作的线性表。 一般规定，栈只能在栈顶进行插入，删除操作。因此访问元素的顺序是先进后出。 如下图所示：  这里介绍几个重要的概念： > - 栈顶（top）：栈的操作中，仅允许插入和删除的那一端。 > - 栈底（bottom）：固定的，不允许进行插入和删除操作的那一端。 > - 空栈：不含有任何元素的空线性表。 ### 1.2基本操作 ~~~ InitStack(&S) //初始化一个空栈S StackEmpty(S) //判断一个栈是否为空 Push(&S,x) //入栈，若栈未满，则将x加入使之称为新栈顶 Pop(&S,x) //出栈，若栈非空，则弹出栈顶元素，并用x返回 GetTop(S,&x) //读取栈顶元素，若栈S非空，则用x返回栈顶元素 ClearStack(S) //销毁栈，并释放栈S占用的存储空间 ~~~ ## 二.队列 ### 2.1定义 队列（Queue）简称队，只允许在线性表的一端进行插入，另一端进行删除。 一般规定，只能在队尾进行插入操作，队头进行删除操作。因此访问时的顺序是先进先出。 如下图所示：  介绍几个重要的概念： > - 队头：允许删除的一端，又称为队首。 > - 队尾：允许插入的一端。 > - 空队列：不含任何元素的空表。 ### 2.2基本操作 ~~~ InitQueue(&Q) //初始化队列，构造一个空队列 QueueEmpty(&Q) //判断队列是否为空 EnQueue(&Q,x) //入队，若队列Q未满，将x加入，使之称为新的队尾 DeQueue(&Q,&x) //出队，若队列Q非空，删除队头元素，并用x返回 GetHead(Q,&x) //读取队头元素，若队列非空，则将队头元素赋值给x ~~~ ## 三.串 ### 3.1定义 字符串（string）简称串，是由零个或多个字符组成的有穷序列。 介绍几个重要概念： > - 串长：串中所含字符的个数 > - 子串：一个串中任意个连续字符组成的子序列(含空串,但不含串本身) > - 主串：包含子串的串 > - 空串：含零个字符的串，通常用 Φ 表示。 ### 3.2基本操作 ~~~ StrAssign(&T,chars) //由字符串常量chars生成字符串T的操作。 StrCopy(&T,S) //由串S复制生成串T的操作。 StrCompare(S,T) //若S=T返回0，S>T返回正数，S ';

本章主要介绍了下线性表的两种存储结构——顺序存储和链式存储，然后引入了大量的练习题来巩固这两种存储方式。 继续使用[第1章线性表 ](http://blog.csdn.net/u013595419/article/details/50461712)中的配图来比较下顺序表和链表。  ## 一.顺序表和链表的比较 ### 1.1存取方式 > - 顺序表既可以顺序存取，又可以随机存取； > - 链表只能从表头到表尾顺序存取。 ### 1.2逻辑结构与物理结构（存储方式） > - 顺序表中，逻辑上相邻的元素，其对应的物理位置亦相邻； > - 链表中，逻辑上相邻的元素，物理位置不一定相邻，其对应的逻辑关系是通过指针链接形成的。 **注：**此处应注意区别存储方式和存取方式的基本定义。 　　存取方式指的是读取数据的方式，比如随机存取，离散存取等； 　　存储方式指的是数据的物理结构，比如顺序存储，离散存储等。 ### 1.3基本操作 ### 1.3.1查找操作 - 按值查找 > 顺序表无序的情况下，查找时间复杂度为O(n)；若有序，查找时间复杂度为O(1)。 链表无论是否有序，查找时间复杂度均为O(n)。 - 按序号查找 > 顺序表支持随机访问，时间复杂度为O(1)； 链表需要从表头遍历到表尾，时间复杂度为O(n)。 ### 1.3.2插入删除操作 > 顺序表需要移动大量元素，时间复杂度为O(n)； 链表只需修改节点的指针域即可，时间复杂度为O(1)。 ### 1.4空间分配 > 顺序表在创建时就要求分配足够大的存储空间。 　采用静态分配时，若分配空间过大，则会造成浪费严重；若分配过小，则会造成溢出； 　采用动态分配时，扩充需要移动大量元素，造成操作效率低下； 链表仅在需要的时候申请分配，只要内存空间足够便可完成分配。 ## 二．顺序表和链表在现实生活中的选择 根据上述顺序表和链表的比较，使得我们更加熟悉了线性表的基本操作。对此我们变可以根据自身的需求来选择合适的线性表结构。下面说明几点参考标准： ### 2.1基于存储的考虑 对于线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度比较低，显然采用链式存储的线性表存储密度是小于1的。 ### 2.2基于运算的考虑 当我们在线性表操作中涉及到大量的按序号查找值的操作时，采用顺序表无疑是一种不错的选择，顺序表因为可以实现离散存取，时间复杂度仅为O(1)；而链表因为必须使用顺序存取，时间复杂度为O(n)。 如果实际使用中使用到了大量的插入和删除操作时，顺序表平均需要移动表中一半的元素，最坏时间复杂度为O(1)；而链表做相同的操作时，时间复杂度仅为O(1)。明显，我们会选择链表。 ### 2.3基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型；而链表的操作是基于指针的，有些高级语言中并不具备指针。 总之，究竟选择顺序表还是链表还是需要根据自身需要来确定，只有合适的才是最好的。

## 问题描述 > 设头指针为L的带有表头结点的非循环双向链表，其每个结点中除有prior（前驱指针），data（数据），next（后继指针）域外，还有一个访问频度域freq。在链表被启用前，其值均初始化为零。每当在连表中进行一次Locate(L,x)运算时，令元素值为x的结点中freq域的值增1，并使此链表中结点保持按访问频度非递增的顺序排列，同时最近访问的结点排在频度相同的结点的前面，以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate(L,x)运算的算法，该运算为函数过程，返回找到结点的地址，类型为指针型。 ## 算法思想 > 本题经过分析之后可以发现，主要考察了双链表的查找，删除，插入操作。 > - 首先在双链表中查找数据域的值为x的结点； > - 找到后，将结点从链表上摘下，然后再从头节点按照频度递减的次序向后查找，插入到同频度出现的第一个位置 > - 这样便完成了一次排序 ## 算法描述 ~~~ void Locate(DNode *head, ElemType x) { DNode *pre=head; DNode *p=head->next; while(p&&p->data!=x){ p=p->next; } if(!p){ printf("The %d isn't exist!\n",x); return; }else{ p->freq++; if(p->next){ p->next->prior=p->prior; } p->prior->next=p->next; pre=p->prior; while(pre!=head&&pre->freqfreq){ pre=pre->prior; } p->next=pre->next; pre->next->prior=p; p->prior=pre; pre->next=p; } } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct DNode{ int freq; ElemType data; struct DNode *prior,*next; }DNode,*DLinkList; DLinkList CreatList(DNode*); void Locate(DNode*,ElemType); void BackPrint(DNode*); int main(int argc,char* argv[]) { DNode *head; head=(DNode*)malloc(sizeof(DNode)); head->prior=NULL; head->next=NULL; head=CreatList(head); BackPrint(head); //模拟结点数据域的值出现的次数 for(ElemType x=1;x<=8;x++){ if(x%2==0){ Locate(head,x); if(x%3==0){ Locate(head,x); } } } BackPrint(head); return 0; } //头插法建立非循环双向链表 DLinkList CreatList(DNode *head) { DNode *L; int freq=0; ElemType x; scanf("%d",&x); while(x!=999){ L=(DNode*)malloc(sizeof(DNode)); L->freq=freq; L->data=x; L->next=head->next; if(head->next){ head->next->prior=L; } L->prior=head; head->next=L; scanf("%d",&x); } return head; } void Locate(DNode *head, ElemType x) { DNode *pre=head; DNode *p=head->next; while(p&&p->data!=x){ p=p->next; } if(!p){ printf("The %d isn't exist!\n",x); return; }else{ p->freq++; if(p->next){ p->next->prior=p->prior; } p->prior->next=p->next; pre=p->prior; while(pre!=head&&pre->freqfreq){ pre=pre->prior; } p->next=pre->next; pre->next->prior=p; p->prior=pre; pre->next=p; } } void BackPrint(DNode *head) { DNode *p=head; while(p->next){ p=p->next; printf("%4d|%d",p->data,p->freq); } printf("\n"); } ~~~

## 问题描述 > 设有一个带头结点的循环单链表，其结点值均为正整数。设计一个算法，反复找出单链表中结点值的最小的结点并输出，然后将该结点从中删除，直到单链表空为止，最后删除头结点 ## 算法思想 > 本题可以借鉴[ 第1章第2节练习题3 删除最小值结点 ](http://blog.csdn.net/u013595419/article/details/50496681)的算法来实现，但是也应该注意到本题时循环单链表，因此判断是否已经为空表的方法是`head->next==head`也就是头节点的next域已经指向自身结点。具体的算法描述如下： ## 算法描述 ~~~ //循环调用，直至为空 while(head->next!=head){ pre=FindMin(head); DelMin(pre); } //发现最小值结点，并打印该结点 LinkList FindMin(LNode *head) { LNode *pre=head; LNode *p=head->next; LNode *premin=head; LNode *min=head->next; while(p!=head){ if(min->data>p->data){ premin=pre; min=p; } pre=p; p=p->next; } printf("%4d",min->data); return premin; } //删除最小值结点 void DelMin(LNode *pre) { LNode *p=pre->next; pre->next=p->next; free(p); } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode *); LinkList FindMin(LNode*); void DelMin(LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head; head=(LNode*)malloc(sizeof(LNode)); head->next=head; head=CreatList(head); Print(head); LNode *pre=head; while(head->next!=head){ pre=FindMin(head); DelMin(pre); } Print(head); free(head); return 0; } //头插法建立单链表 LinkList CreatList(LNode* head) { LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; L->next=head->next; head->next=L; scanf("%d",&x); } return head; } //查找最小值结点 LinkList FindMin(LNode *head) { LNode *pre=head; LNode *p=head->next; LNode *premin=head; LNode *min=head->next; while(p!=head){ if(min->data>p->data){ premin=pre; min=p; } pre=p; p=p->next; } printf("%4d",min->data); return premin; } //删除最小值结点 void DelMin(LNode *pre) { LNode *p=pre->next; pre->next=p->next; free(p); } //打印所有结点 void Print(LNode *head) { LNode *p=head->next; while(head!=p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~

## 问题描述 > 有两个循环单链表，链表头指针分别为h1和h2，编写一个函数将链表h2连接到链表h1之后，要求链表后的链表仍保持循环链表的形式 ## 算法思想 > 因为这是两个循环单链表，仅仅只是考虑将它们连接起来形成新的循环单链表即可。 那么我们首先找到第一个循环单链表h1的尾结点，然后让其next域指向另一个循环单链表h2的第一具有数据域的结点（即头节点的next域所指的那个结点），此时便可以释放掉循环单链表h2的头节点；最后在找到循环单链表h2的尾结点，使其next域重新指向循环单链表h1的头节点便可。 如此以来便将两个循环单链表连接在一起，形成了一个循环单链表。 ## 算法描述 ~~~ //寻找循环单链表“最后一个结点” LNode* FindRear(LNode *head) { LNode *p=head->next; while(p->next!=head){ p=p->next; } return p; } //连接两个循环单链表 LinkList Connect(LNode *head1, LNode *head2) { LNode *r1=FindRear(head1); LNode *r2=FindRear(head2); LNode *p=head2->next; r1->next=p; free(head2); r2->next=head1; return head1; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode,*LinkList; LinkList CreatList(LNode*); LinkList Connect(LNode*, LNode*); LNode* FindRear(LNode*); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2=CreatList(head2); Print(head1); Print(head2); head1=Connect(head1, head2); Print(head1); return 0; } //尾插法建立循环单链表 LinkList CreatList(LNode *head) { LNode *L; LNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=head; return head; } //连接两个不同的循环单链表 LinkList Connect(LNode *head1, LNode *head2) { LNode *r1=FindRear(head1); LNode *r2=FindRear(head2); LNode *p=head2->next; r1->next=p; free(head2); r2->next=head1; return head1; } //寻找最后一个结点 LNode* FindRear(LNode *head) { LNode *p=head->next; while(p->next!=head){ p=p->next; } return p; } //打印全部结点 void Print(LNode *head) { LNode *p=head->next; while(p!=head){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~

## 问题描述 > 设计一算法用于判断带头结点的循环双链表是否对称 ## 算法思想 > 考虑到题目要求的是循环双链表，因此设置两个指针p和q，让p从头节点开始，从前往后遍历；指针q从头节点的prior域指示的尾结点开始，从后往前遍历，直到它们指向同一结点（`循环双链表的结点数为奇数`）或相邻结点时`循环双链表的结点数为偶数`为止。 在遍历期间，如果两个指针指向的结点的数据域的值一直保持相等，则它们沿着各自的方向继续遍历；如果不想等，则终止遍历。 ## 算法描述 ~~~ int JudgeSym(DNode *head) { DNode *p=head->next; DNode *q=head->prior; while(p!=q&&q->next!=p){ if(p->data==q->data){ p=p->next; q=q->prior; }else{ break; } } if(p==q){ return 0; }else{ return -1; } } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode, *DLinkList; DLinkList CreatList(DNode*); int JudgeSym(DNode*); void BackPrint(DNode*); void ForwardPrint(DNode*); int main(int argc,char* argv[]) { DNode *head; head=(DNode*)malloc(sizeof(DNode)); head->next=head; head->prior=head; head=CreatList(head); BackPrint(head); ForwardPrint(head); int flag=JudgeSym(head); if(flag==0){ printf("It is symmery!\n"); }else{ printf("It isn't symmery!\n"); } return 0; } //尾插法建立循环双链表 DLinkList CreatList(DNode* head) { DNode *r=head; DNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(DNode*)malloc(sizeof(DNode)); L->data=x; L->next=head; head->prior=L; r->next=L; L->prior=r; r=L; scanf("%d",&x); } return head; } //判断是否对称，若对称，返回0；否则返回-1。 int JudgeSym(DNode *head) { DNode *p=head->next; DNode *q=head->prior; while(p!=q&&q->next!=p){ if(p->data==q->data){ p=p->next; q=q->prior; }else{ break; } } if(p==q){ return 0; }else{ return -1; } } //向后遍历输出所有结点 void BackPrint(DNode *head) { DNode *p=head->next; while(p!=head){ printf("%4d",p->data); p=p->next; } printf("\n"); } //向前遍历输出所有结点 void ForwardPrint(DNode* head) { DNode *p=head->prior; while(p!=head){ printf("%4d",p->data); p=p->prior; } printf("\n"); } ~~~

## 问题描述 > 已知两个链表A和B分别表示两个集合，其元素递增排列。编写函数，求A与B的交集，并存放于A链表中 ## 算法思想 > 本题算法实际和 [ 第1章第2节练习题17 使用相同值结形成新单链表 ](http://blog.csdn.net/u013595419/article/details/50510681)并无太大区别，但是也应注意到本题中明确要求对单链表A进行拆分，仅仅保留单链表A和单链表B中结点数据域相同的部分，既然这样，我们便可以对单链表A和单链表B分别设置两个指针进行遍历，删除数据域中单链表A中有的，而单链表B中没有的结点便可。算法描述如下： ## 算法描述 ~~~ LinkList Intersection(LNode *head1, LNode *head2) { LNode *prep=head1; LNode *p=head1->next; LNode *q=head2->next; while(p&&q){ if(p->data==q->data){ prep=p; p=p->next; q=q->next; }else if(p->datadata){ prep->next=p->next; free(p); p=prep->next; }else{ q=q->next; } } //若单链表B已经遍历已完成，而A仍有剩余，删除单链表A中的所有结点 while(p){ prep->next=p->next; free(p); p=prep->next; } return head1; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList Intersection(LNode*,LNode*); void Print(LNode*); int main(int argc,char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2=CreatList(head2); Print(head1); Print(head2); head1=Intersection(head1, head2); Print(head1); return 0; } //尾插法建立单链表 LinkList CreatList(LNode *head) { LNode *r=head; LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=NULL; return head; } //查找数据域的值相同的结点 LinkList Intersection(LNode *head1, LNode *head2) { LNode *prep=head1; LNode *p=head1->next; LNode *q=head2->next; while(p&&q){ if(p->data==q->data){ prep=p; p=p->next; q=q->next; }else if(p->datadata){ prep->next=p->next; free(p); p=prep->next; }else{ q=q->next; } } while(p){ prep->next=p->next; free(p); p=prep->next; } return head1; } //打印全部结点 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~

## 问题描述 > 设A和B是两个单链表（带头结点），其中元素按递增有序。设计一个算法从A和B中公共元素产生单链表C，要求不破坏A，B的结点 ## 算法思想 > 本算法实际上和[第1章第2节练习题16 归并并逆序单链表](http://blog.csdn.net/u013595419/article/details/50510558)并没有太大的区别，同样对两张链表进行遍历，对于具有相同值的结点进行一次复制，然后将复制出来的新节点采用尾插法建立单链表的方式形成新的单链表。 ## 算法描述 ~~~ LinkList CreatNew(LNode *head1, LNode *head2, LNode *head) { LNode *p=head1->next; LNode *q=head2->next; LNode *r=head; LNode *L; while(p&&q){ if(p->data==q->data){ L=(LNode*)malloc(sizeof(LNode)); L->data=p->data; r->next=L; r=L; p=p->next; q=q->next; }else if(p->datadata){ p=p->next; }else{ q=q->next; } } r->next=NULL; return head; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList CreatNew(LNode*,LNode*,LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1->next=NULL; head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2->next=NULL; head2=CreatList(head2); LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=CreatNew(head1, head2, head); Print(head1); Print(head2); Print(head); return 0; } //尾插法建立单链表 LinkList CreatList(LNode* head) { LNode *L; LNode *r=head; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } return head; } //查找公共结点 LinkList CreatNew(LNode *head1, LNode *head2, LNode *head) { LNode *p=head1->next; LNode *q=head2->next; LNode *r=head; LNode *L; while(p&&q){ if(p->data==q->data){ L=(LNode*)malloc(sizeof(LNode)); L->data=p->data; r->next=L; r=L; p=p->next; q=q->next; }else if(p->datadata){ p=p->next; }else{ q=q->next; } } r->next=NULL; return head; } //打印所有结点 void Print(LNode *head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~

## 问题描述 > 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。试编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来的两个单链表结点存放归并后的单链表 ## 算法思想 > 分析本题可见，本题实际上就是一次有序归并排序，因此我们借鉴归并排序的思想来实习本算法。 这里图个方便，就又新建了一个头结点，导致本算法中同时出现了三个头节点。 首先对两条已知的单链表进行遍历，每访问一个结点，便对比较一次，哪个结点比较小，就将其取下然后采用头插法建立单链表的方式重新建立单链表，形成元素值递减的单链表。 ## 算法描述 ~~~ LinkList MergeList(LNode *head1, LNode *head2, LNode *head) { LNode *prep=head1; LNode *p=head1->next; LNode *preq=head2; LNode *q=head2->next; //查找较小值 while(p&&q){ if(p->datadata){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; }else{ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } } //若第一个单链表未遍历完成，则继续插入 while(p){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; } //若第二个单链表为遍历完成，则继续插入 while(q){ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } free(head1); free(head2); return head; } ~~~ 具体代码见附件。 ## 附件 ~~~ #include #include typedef int ElemType; typedef struct LNode{ ElemType data; struct LNode *next; }LNode, *LinkList; LinkList CreatList(LNode*); LinkList MergeList(LNode*, LNode*, LNode*); void Print(LNode*); int main(int argc, char* argv[]) { LNode *head1; head1=(LNode*)malloc(sizeof(LNode)); head1=CreatList(head1); LNode *head2; head2=(LNode*)malloc(sizeof(LNode)); head2=CreatList(head2); Print(head1); Print(head2); LNode *head; head=(LNode*)malloc(sizeof(LNode)); head=MergeList(head1, head2, head); Print(head); return 0; } //尾插法建立单链表 LinkList CreatList(LNode *head) { LNode *r=head; LNode *L; ElemType x; scanf("%d",&x); while(x!=999){ L=(LNode*)malloc(sizeof(LNode)); L->data=x; r->next=L; r=L; scanf("%d",&x); } r->next=NULL; return head; } //归并单链表 LinkList MergeList(LNode *head1, LNode *head2, LNode *head) { LNode *prep=head1; LNode *p=head1->next; LNode *preq=head2; LNode *q=head2->next; while(p&&q){ if(p->datadata){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; }else{ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } } while(p){ prep->next=p->next; p->next=head->next; head->next=p; p=prep->next; } while(q){ preq->next=q->next; q->next=head->next; head->next=q; q=preq->next; } free(head1); free(head2); return head; } //打印全部结点 void Print(LNode* head) { LNode *p=head->next; while(p){ printf("%4d",p->data); p=p->next; } printf("\n"); } ~~~