内容发布更新时间 : 2024/12/26 16:41:10星期一 下面是文章的全部内容请认真阅读。
◆ 队列的定义及操作，队列的删除在一端（队尾），而插入则在队列的另一端（队头）。因此在两种存储结构中，都需要队头和队尾两个指针。
队列：只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 链队列
结点类型定义：
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