更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://www.diyifanwen.net//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
return Q->count==QueueSize; ④ 入队
Q->count ++; //队列元素个数加1 Q->data[Q->rear]=x; //新元素插入队尾 Q->rear=(Q->rear+1)%QueueSize; ⑤ 出队
temp=Q->data[Q->front];
Q->count--; //队列元素个数减1
Q->front=(Q->front+1)%QueueSize; //循环意义下的头指针加1 return temp; ⑥取队头元素
return Q->data[Q->front];
11. 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。
链队列的基本运算:
（1） 置空队：Q->front=Q->rear=NULL;
（2） 判队空：return Q->front==NULL&&Q->rear==Null;
（3） 入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode));//申请新结点 p->data=x; p->next=NULL; if(QueueEmpty(Q))
Q->front=Q->rear=p; //将x插入空队列 else { //x插入非空队列的尾
Q->rear->next=p; //*p链到原队尾结点后 Q->rear=p; //队尾指针指向新的尾 （4） 出队：p=Q->front; //指向对头结点
x=p->data; //保存对头结点的数据 Q->front=p->next; //将对头结点从链上摘下
if(Q->rear==p)//原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q->rear=NULL;
free(p); //释放被删队头结点 return x; //返回原队头数据 （5） 取队头元素：if(QueueEmpty(Q))
Error(\ return Q->front->data;
①和链栈类似，无须考虑判队满的运算及上溢。
②在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。
③以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算。
12. 递归是指：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://www.diyifanwen.net//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
递归的，或者是递归定义的。
调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。 第四章 串
1. 串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。串（String）是零个或多个字符组成的有限序列。一般记为S=\1a2??an\
将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。 2. 长度为零的串称为空串（Empty String），它不包含任何字符。 仅由一个或多个空格组成的串称为空白串（Blank String）。
″ ″和″″分别表示长度为1的空白串和长度为0的空串。
3. 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。 ①空串是任意串的子串 ②任意串是其自身的子串。
4. 通常在程序中使用的串可分为：串变量和串常量。串变量和其它类型的变量一样，其取值是可以改变的。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。 5.串的基本运算：
①求串长：int strlen(char *s);//求串s的长度
②串复制：char *strcpy(char *to,*from)；//将from串复制到to串中，并返回to开始处指针 ③联接：char *strcat(char *to,char *from);//将from串复制到to串的末尾， //并返回to串开始处的指针 ④串比较：int strcmp(char *s1,char *s2);//比较s1和s2的大小， //当s1
⑤字符定位：char *strchr(char *s,char c);//找c在字符串s中第一次出现的位置， //若找到，则返回该位置，否则返回NULL 6. 串的顺序存储结构简称为顺序串。
与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。按其存储分配的不同可将顺序串分为如下两类：
（1）静态存储分配的顺序串
①串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作
②直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值为MaxStrSize时，最多只能放MaxStrSize-1个字符。C语言中以字符'\\0'表示串值的终结。
（2）动态存储分配的顺序串:顺序串的字符数组空间可使用C语言的malloc和free等动态存储管理函数，来根据实际需要动态地分配和释放。
7. 用单链表方式存储串值，串的这种链式存储结构简称为链串。
①链串和单链表的差异仅在于其结点数据域为单个字符： ②一个链串由头指针唯一确定。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://www.diyifanwen.net//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
链串的结点大小:
①为了提高存储密度，可使每个结点存放多个字符。
②当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。
③虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。
8. 子串定位运算又称串的模式匹配或串匹配。子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。 在串匹配中，一般将主串称为目标（串），子串称为模式（串）。
串匹配就是对于合法的位置（又称合法的位移）0≤i≤n-m，依次将目标串中的子串\iti+1?ti+m-1\和模式串\0p1p2?pm-1\进行比较：
①若\iti+1?ti+m-1\＝\0p1p2?pm-1\，则称从位置i开始的匹配成功，或称i为有效位移。 ②若\iti+1?ti+m-1\0p1p2?pm-1\，则称从位置i开始的匹配失败，或称i为无效位移。 因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。 有些应用中要求求出P在T中所有出现的有效位移。
9.朴素的串匹配算法的基本思想：即用一个循环来依次检查n-m+1个合法的位移i（0≤i≤n-m）是否为有效位移。
顺序串上的串匹配算法：
①最坏时间复杂度：为O((n-m+1)m)。
②模式匹配算法的改进：朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移i是否为有效位移时，没有利用检查位移i-1，i,?,0时的部分匹配结果。
若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏时间控制在O（m+n）数量级上。
链串上的子串定位运算：用结点大小为1的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移shift是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。
════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://www.diyifanwen.net//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
第五章 多维数组和广义表
1. 多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。
2. 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。 同一数组的不同元素通过不同的下标标识。 （a1,a2,?,an)
3. 二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。
4. 多维数组: 三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量??
三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量??
5. 数组的顺序存储方式: 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。 （1）行优先顺序：将数组元素按行向量排列，第i+1个行向量紧接在第i个行向量后面。 【例】二维数组Amn的按行优先存储的线性序列为： a11,a12,?,a1n,a21,a22,?,a2n,??，am1,am2,?，amn （2）列优先顺序
将数组元素按列向量排列，第i+1个列向量紧接在第i个列向量后面。 【例】二维数组Amn的按列优先存储的线性序列为： a11,a21,?,am1,a12,a22,?,am2,??，a1n,a2n,?，amn 6.数组元素的地址计算公式:
（1）按行优先顺序存储的二维数组Amn地址计算公式
LOC(aij)=LOC(a11)+[(i-1)×n+j-1]×d (注：此公式下界为1，如下界为0，则公式变为[i×n+j]) ①LOC(a11)是开始结点的存放地址（即基地址） ②d为每个元素所占的存储单元数
③由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。
即顺序存储的数组是随机存取结构。
（2）按列优先顺序存储的二维数组Amn地址计算公式
LOC(aij)=LOC(a11)+[(j-1)×m+i-1]×d(注：此公式下界为1，如下界为0，则公式变为[j×m+i]) （3）按行优先顺序存储的三维数组Amnp地址计算公式
LOC(aijk)=LOC(a111)+[(i-1)×n×p+(j-1)×p+k-1]×d
(注：此公式下界为1，如下界为0，则公式变为[i×n×p+j×p+k]) （4）下界不为1的二维数组的地址计算公式
①二维数组A[c1..d1,c2..d2]的地址计算公式： LOC(aij)=LOC(ac1c2)+[(i-c1)×(d2-c2+1)+j-c2]×d ②下界为0的二维数组的地址计算公式（C语言中使用） LOC(aij)=LOC(a00)+[i×(d2+1)+j]×d
7. 矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。
矩阵的压缩：矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可════════════════════════════════════════════════════════════════════
自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园....
俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
更多优质自考资料尽在百度贴吧自考乐园俱乐部
（http://tieba.http://www.diyifanwen.net//club/5346389）欢迎?加入...欢迎?交流...止不住的惊喜等着你.........
以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。
8. 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。 （1）对称矩阵
在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≤i，j≤n-1 （2）对称矩阵的压缩存储
对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。
①按\行优先顺序\存储主对角线(包括对角线)以下的元素
（下三角矩阵中，元素总数为n(n+1)/2）。
即按a00,a10,a11,??，an-1,0,an-1,1?，an-1,n-1次序存放在一个向量sa[0．．n(n+1)/2-1]中
sa[0]=a00 ,sa[1]=a10 ,??,sa[n(n+1)/2-1]= an-1,n-1 ②元素aij的存放位置: sa[i×(i+1)/2+j]=aij
③aij和sa[k]之间的对应关系：
令I=max(i,j)，J=min(i,j)，则k和i，j的对应关系可统一为： k=I×(I+1)/2+J 0≤k LOC(aij)=LOC(sa[0])+[I×(I+1)/2+J]×d，其中I=max(i,j)，J=min(i,j) 9. 三角矩阵的划分： 以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。 ①上三角矩阵：如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。 ②下三角矩阵：与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。 10.三角矩阵的压缩存储：三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)/2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)/2]中，其中c存放在向量的最后一个分量中。 ①上三角矩阵中aij和sa[k]之间的对应关系 k=i×(2n-i+1)/2+j-i 当i≤j k=n×(n+1)/2 当i＞j ②下三角矩阵中aij和sa[k]之间的对应关系 k=i×(i+1)/2+j 当i≥j k=n×(n+1)/2 当i＜j 三角矩阵的压缩存储结构是随机存取结构。 ════════════════════════════════════════════════════════════════════ 自考乐园,自考学习交流、资料共享的好去处！自考乐园,自考人自己的家园.... 俱乐部id：5346389（请牢记它哦~在百度贴吧的搜索框中输入俱乐部id,可以直接进入俱乐部
自考数据结构重点（珍藏版）
