内容发布更新时间 : 2024/7/2 7:13:49星期一 下面是文章的全部内容请认真阅读。

◆ 队列的定义及操作，队列的删除在一端（队尾），而插入则在队列的另一端（队头）。因此在两种存储结构中，都需要队头和队尾两个指针。

队列：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 链队列

结点类型定义：

typedef Struct QNode{

QElemType data; //元素

Struct QNode *next; //指向下一结点的指针 }Qnode , * QueuePtr ; 链队列类型定义： typedef struct {

QueuePtr front ; //队首指针 QueuePtr rear ; //队尾指针 } LinkQueue; 链队示意图：

① 空链队的特征：front=rear

② 链队会满吗？一般不会，因为删除时有free动作。除非内存不足！ ③ 入队（尾部插入）：rear->next=S; rear=S; 出队（头部删除）：front->next=p->next; 2.顺序队

顺序队类型定义：

#define QUEUE-MAXSIZE 100 //最大队列长度 typedef struct {

QElemType *base; //队列的基址

int front; //队首指针 int rear; //队尾指针 }SqQueue 建队核心语句：

q . base=(QElemType *)malloc(sizeof (QElemType ） * QUEUE_MAXSIZE; //分配空间 顺序队示意图：

循环队列：

队空条件 : front = rear (初始化时：front = rear ) 队满条件： front = (rear+1) % N (N=maxsize) 队列长度（即数据元素个数）：L=（N＋rear－front）% N 1）初始化一个空队列

Status InitQueue ( SqQueue &q ) //初始化空循环队列 q {

q . base=(QElemType *)malloc(sizeof(QElemType） * QUEUE_MAXSIZE); //分配空间

if (!q.base) exit(OVERFLOW);//内存分配失败，退出程序 q.front =q.rear=0; //置空队列 return OK; } //InitQueue;

2）入队操作

Status EnQueue(SqQueue &q, QElemType e) {//向循环队列 q 的队尾加入一个元素 e

if ( (q.rear+1) % QUEUE_MAXSIZE = = q.front )

return ERROR ; //队满则上溢，无法再入队 q.rear = ( q . rear + 1 ) % QUEUE_MAXSIZE; q.base [ q.rear ] = e; //新元素e入队 return OK; }// EnQueue;

3）出队操作

Status DeQueue ( SqQueue &q, QElemType &e) {//若队列不空，删除循环队列q的队头元素， //由 e 返回其值，并返回OK

if ( q.front = = q.rear ) return ERROR;//队列空 q.front=(q.front+1) % QUEUE_MAXSIZE ; e = q.base [ q.front ] ; return OK; }// DeQueue

◆ 链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。

补充重点：

1.为什么要设计堆栈？它有什么独特用途？ ① 调用函数或子程序非它莫属； ② 递归运算的有力工具； ③ 用于保护现场和恢复现场； ④ 简化了程序设计的问题。

2.为什么要设计队列？它有什么独特用途？

① 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）； ② 操作系统中的作业调度（一个CPU执行多个作业）； ③ 简化程序设计。

3.什么叫“假溢出” ？如何解决？

答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径———采用循环队列。

4.在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先 移动队首位置 ，后 取出元素。

5.线性表、栈、队的异同点：

相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。 不同点：① 运算规则不同： 线性表为随机存取；

而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；

队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。

第四章 串 内容提要 ：

◆ 串是数据元素为字符的线性表，串的定义及操作。

串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 串比较：int strcmp(char *s1,char *s2);

求串长：int strlen(char *s); 串连接：char strcat(char *to,char *from) 子串T定位：char strchr(char *s,char *c);

◆ 串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。 模式匹配算法 。

串有三种机内表示方法：

模式匹配算法 ：

算法目的：确定主串中所含子串第一次出现的位置（定位） 定位问题称为串的模式匹配，典型函数为Index(S,T,pos) BF算法的实现—即编写Index(S, T, pos)函数 BF算法设计思想：

将主串S的第pos个字符和模式T的第1个字符比较， 若相等，继续逐个比较后续字符；

若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。

直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。

否则，匹配失败，返回值 0。

Int Index_BP(SString S, SString T, int pos)

{ //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0. // 其中，T非空，1≤pos≤StrLength(S) i=pos; j=1;

while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围， {

if (S[i] = = T[j] ) {++i, ++j; } //则继续比较后续字符 else {i=i-j+2; j=1;} //若不相等，指针后退重新开始匹配 }

if(j>T[0]) return i-T[0]; //T子串指针j正常到尾，说明匹配成功， else return 0; //否则属于i>S[0]情况，i先到尾就不正常 } //Index_BP