电大自考数据结构重点(珍藏版)小抄参考

《电大自考数据结构重点(珍藏版)小抄参考》由会员分享，可在线阅读，更多相关《电大自考数据结构重点(珍藏版)小抄参考（33页珍藏版）》请在装配图网上搜索。

1、专业好文档自考数据结构重点（周尧整理）第一章 概论1. 数据是信息的载体。2. 数据元素是数据的基本单位。3. 一个数据元素可以由若干个数据项组成。4. 数据结构指的是数据之间的相互关系，即数据的组织形式。5. 数据结构一般包括以下三方面内容：数据的逻辑结构、数据的存储结构、数据的运算数据元素之间的逻辑关系，也称数据的逻辑结构，数据的逻辑结构是从逻辑关系上描述数据，与数据的存储无关，是独立于计算机的。数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。数据的存储结构是逻辑结构用计算机语言的实现，它依赖于计算机语言。数据的运算，即对数据施加的操作。最常用的检索、插入、删除、更新、排序等。

2、6. 数据的逻辑结构分类: 线性结构和非线性结构线性结构：若结构是非空集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 线性表是一个典型的线性结构。栈、队列、串等都是线性结构。非线性结构：一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。7.数据的四种基本存储方法: 顺序存储方法、链接存储方法、索引存储方法、散列存储方法（1）顺序存储方法：该方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。通常借助程序语言的数组描述。（2）链接存储方法：该方法不要求逻辑上相邻的结点在

3、物理位置上亦相邻，结点间的逻辑关系由附加的指针字段表示。通常借助于程序语言的指针类型描述。（3）索引存储方法：该方法通常在储存结点信息的同时，还建立附加的索引表。索引表由若干索引项组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引，稠密索引中索引项的地址指示结点所在的存储位置。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引稀疏索引中索引项的地址指示一组结点的起始存储位置。索引项的一般形式是：(关键字、地址) 关键字是能唯一标识一个结点的那些数据项。（4）散列存储方法：该方法的基本思想是：根据结点的关键字直接计算出该结点的存储地址。8. 抽象数据类型(ADT):是指

4、抽象数据的组织和与之相关的操作。可以看作是数据的逻辑结构及其在逻辑结构上定义的操作。抽象数据类型可以看作是描述问题的模型，它独立于具体实现。它的优点是将数据和操作封装在一起，使得用户程序只能通过在ADT里定义的某些操作来访问其中的数据，从而实现了信息隐藏。9. 算法+数据结构=程序 数据结构：是指数据的逻辑结构和存储结构 算法：是对数据运算的描述10. 数据的运算通过算法描述的。算法是任意一个良定义的计算过程。它以一个或多个值作为输入，并产生一个或多个值作为输出。若一个算法对于每个输入实例均能终止并给出正确的结果，则称该算法是正确的。正确的算法解决了给定的计算问题。11. 选用的算法首先应该是

5、正确的。此外，主要考虑如下三点： 执行算法所耗费的时间； 执行算法所耗费的存储空间，其中主要考虑辅助存储空间； 算法应易于理解，易于编码，易于调试等等。12. 一个算法所耗费的时间=算法中每条语句的执行时间之和，每条语句的执行时间=语句的执行次数(即频度(Frequency Count)语句执行一次所需时间。13.算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。14. 一个算法的时间复杂度T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。平均时间复杂度是指所有可能的输入实例均以等

6、概率出现的情况下，算法的期望运行时间。15. 常见的时间复杂度按数量级递增排列依次为：常数0(1)、对数阶0(log2n)、线形阶0(n)、线形对数阶0(nlog2n)、平方阶0(n2)立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。16. 一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。第二章 线性表1. 线性表（Linear List）是由n（n0）个数据元素（结点）a1,a2,an组成的有限序列。2. 线性表的逻辑结构特征，对于非空的线性表: 有且仅有一个开始结点a1，没有直接前趋，有且仅有一个直接后继a2； 有且仅有一个终结结点an，没有直接后

7、继，有且仅有一个直接前趋an-1； 其余的内部结点ai（2in-1）都有且仅有一个直接前趋ai-1和一个ai+1。3.常见的线性表的基本运算:(1)InitList（L） 构造一个空的线性表L，即表的初始化。(2)ListLength（L）求线性表L中的结点个数，即求表长。(3)GetNode（L，i） 取线性表L中的第i个结点，这里要求1iListLength（L）(4)LocateNode（L，x）在L中查找值为x 的结点，并返回该结点在L中的位置。若L中有多个结点的值和x 相同，则返回首次找到的结点位置；若L中没有结点的值为x ，则返回一个特殊值表示查找失败。(5)InsertList（

8、L，x，i）在线性表L的第i个位置上插入一个值为x 的新结点，使得原编号为i，i+1，n的结点变为编号为i+1，i+2，n+1的结点。这里1in+1，而n是原表L的长度。插入后，表L的长度加1。(6)DeleteList（L，i）删除线性表L的第i个结点，使得原编号为i+1，i+2，n的结点变成编号为i，i+1，n-1的结点。这里1in，而n是原表L的长度。删除后表L的长度减1。4.顺序存储方法：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表（Sequential List）：用顺序存储方法存储的线性表简称为顺序表。顺序表是一种随机存取结构,顺序表的的特点是逻辑上相邻

9、的结点其物理位置亦相邻。5.顺序表中结点ai 的存储地址: LOC（ai）= LOC（a1）+（i-1）*c 1in， 6.顺序表上实现的基本运算：（1）插入：在顺序表中，结点的物理顺序必须和结点的逻辑顺序保持一致，因此必须将表中位置为n ，n-1，i上的结点，依次后移到位置n+1，n，i+1上，空出第i个位置，然后在该位置上插入新结点x。仅当插入位置i=n+1时，才无须移动结点，直接将x插入表的末尾。具体算法：void InsertList(SeqList *L，DataType x，int i) /将新结点x插入L所指的顺序表的第i个结点ai的位置上算法的时间主要花费在for循环中的结点后

10、移语句上。该语句的执行次数是n-i+1，在表中第i个位置插入一个结点的移动次数为n-i+1，当i=n+1：移动结点次数为0，即算法在最好时间复杂度是O(1)，当i=1：移动结点次数为n，即算法在最坏情况下时间复杂度是O(n) 即在顺序表上进行插入运算，平均要移动一半结点（n/2）。（2）删除：在顺序表上实现删除运算必须移动结点，才能反映出结点间的逻辑关系的变化。若i=n，则只要简单地删除终端结点，无须移动结点；若1in-1，则必须将表中位置i+1，i+2，n的结点，依次前移到位置i，i+1，n-1上，以填补删除操作造成的空缺。具体算法：void DeleteList(SeqList *L,in

11、t i) /从L所指的顺序表中删除第i个结点ai结点的移动次数由表长n和位置i决定：i=n时，结点的移动次数为0，即为0(1)，i=1时，结点的移动次数为n-1，算法时间复杂度分别是O(n)顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是O(n)。7. 链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为：用一组任意的存储单元来存放线性表的结点，链表中结点的逻辑次序和物理次序不一定相同（这组存储单元既可以是连续的，也可以是不连续的）。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称

12、为指针（pointer）或链(link)）。8. 链表的结点结构：data域-存放结点值的数据域，next域-存放结点的直接后继的地址（位置）的指针域（链域）单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。终端结点无后继，故终端结点的指针域为空，即NULL。9. 生成结点变量的标准函数 p=( ListNode *)malloc(sizeof(ListNode)； /函数malloc分配一个类型为ListNode的结点变量的空间,并将其首地址放入指针变量p中释放结点变量空间的标准函数 free(p)；/释放p所指的结点变量空间 结点

13、分量的访问 方法二：p-data和p-next指针变量p和结点变量*p的关系: 指针变量p的值结点地址, 结点变量*p的值结点内容10. 建立单链表: （1） 头插法建表：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。算法： s=(ListNode *)malloc(sizeof(ListNode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 s-next=head; head=s;（2） 尾插法建表：从一个空表开始,重复读入数据,生成新结点,将读入数据存放在新结点的数据域中,然

14、后将新结点插入到当前链表的表尾上,直到读入结束标志为止。算法： s=(ListNode *)malloc(sizeof(ListNode); /生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 if (head!=NULL) head=s;/新结点插入空表 else r-next=s;/将新结点插到*r之后 r=s;/尾指针指向新表尾（3） 尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点: 由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理; 无论链表是否

15、为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。具体算法：r=head; /尾指针初值也指向头结点 while(ch=getchar()!=n) s=(ListNode *)malloc(sizeof(ListNode);/生成新结点 s-data=ch; /将读入的数据放入新结点的数据域中 r-next=s; r=s; r-next=NULL;/终端结点的指针域置空，或空表的头结点指针域置空以上三个算法的时间复杂度均为O(n)。11.单链表上的查找：（1）链表不是

16、随机存取结构 在链表中，即使知道被访问结点的序号i，也不能像顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。（2）查找的思想方法 计数器j置为0后，扫描指针p指针从链表的头结点开始顺着链扫描。当p扫描下一个结点时，计数器j相应地加1。当j=i时，指针p所指的结点就是要找的第i个结点。而当p指针指为null且ji时，则表示找不到第i个结点。头结点可看做是第0个结点。算法：p=head;j=0;/从头结点开始扫描 while(p-next&jnext为NULL或i=j为止 p=p-next; j+;

17、if(i=j) return p;/找到了第i个结点 else return NULL;/当i0时，找不到第i个结点时间复杂度：在等概率假设下，平均时间复杂度为：为n/2=O(n)（2） 按值查找：具体算法：ListNode *p=head-next;/从开始结点比较。表非空，p初始值指向开始结点 while(p&p-data!=key)/直到p为NULL或p-data为key为止 p=p-next;/扫描下一结点 return p;/若p=NULL，则查找失败，否则p指向值为key的结点时间复杂度为：O(n)12.插入运算：插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai

18、-1与ai之间。具体步骤： （1）找到ai-1存储位置p （2）生成一个数据域为x的新结点*s （3）令结点*p的指针域指向新结点 （4）新结点的指针域指向结点ai。具体算法：p=GetNode(head,i-1);/寻找第i-1个结点 if (p=NULL)/in+1时插入位置i有错 Error(position error)； s=(ListNode *)malloc(sizeof(ListNode); s-data=x;s-next=p-next;p-next=s;算法的时间主要耗费在查找操作GetNode上，故时间复杂度亦为O(n)。13. 删除运算删除运算是将表的第i个结点删去。具体

19、步骤： （1）找到ai-1的存储位置p（因为在单链表中结点ai的存储地址是在其直接前趋结点ai-1的指针域next中） （2）令p-next指向ai的直接后继结点（即把ai从链上摘下） （3）释放结点ai的空间，将其归还给存储池。具体算法：p=GetNode(head,i-1);/找到第i-1个结点 if (p=NULL|p-next=NULL)/in时，删除位置错 Error(position error);/退出程序运行 r=p-next;/使r指向被删除的结点ai p-next=r-next;/将ai从链上摘下 free(r);/释放结点ai的空间给存储池算法的时间复杂度也是O（n）。

20、链表上实现的插入和删除运算，无须移动结点，仅需修改指针。14.单循环链表在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。判断空链表的条件是head=head-next;15. 仅设尾指针的单循环链表: 用尾指针rear表示的单循环链表对开始结点a1和终端结点an查找时间都是O(1)。而表的操作常常是在表的首尾位置上进行，因此，实用中多采用尾指针表示单循环链表。判断空链表的条件为rear=rear-next;16.循环链表：循环链表的特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。若在尾指针表示的单循环链表上实现，则只需修改指针，无须遍历，其执行

21、时间是O(1)。具体算法：LinkList Connect(LinkList A,LinkList B) /假设A，B为非空循环链表的尾指针LinkList p=A-next;/保存A表的头结点位置 A-next=B-next-next;/B表的开始结点链接到A表尾 free(B-next);/释放B表的头结点 B-next=p;/ return B;/返回新循环链表的尾指针循环链表中没有NULL指针。涉及遍历操作时，其终止条件就不再是像非循环链表那样判别p或p-next是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，

22、无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些运算在单循环链表上易于实现。17. 双向链表: 双（向）链表中有两条方向不同的链，即每个结点中除next域存放后继结点地址外，还增加一个指向其直接前趋的指针域prior。双链表由头指针head惟一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来，为双（向）循环链表。18.双向链表的前插和删除本结点操作双链表的前插操作void DInsertBefore(DListNode *p,DataType x)/在带头结点的双链表中，将值为x的新结点插入*p之前，设pNULL DLis

23、tNode *s=malloc(sizeof(DListNode);/ s-data=x;/ s-prior=p-prior;/ s-next=p;/ p-prior-next=s;/ p-prior=s;/ 双链表上删除结点*p自身的操作void DDeleteNode(DListNode *p) /在带头结点的双链表中，删除结点*p，设*p为非终端结点 p-prior-next=p-next;/ p-next-prior=p-prior;/ free(p);/ 与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。19.

24、 存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即,存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。 20.顺序表和链表比较顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：顺序表链表分配方式静态分配。程序执行之前必须明确规定存储规模。若线性表长度n变化较大，则存储规模难于预先确定估计过大将造成空间浪费，估计太小又将使空间溢出机会增多。动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为

25、存储结构为好。存储密度为1。当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表作为存储结构。1存取方式随机存取结构，对表中任一结点都可在O（1）时间内直接取得线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜。顺序存取结构，链表中的结点，需从头指针起顺着链扫描才能取得。插入删除操作在顺序表中进行插入和删除，平均要移动表中近一半的结点，尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则

26、采用尾指针表示的单循环链表为宜第三章 栈1. 栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。(2)当表中没有元素时称为空栈。(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。 栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中最新的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。2.顺序栈：栈的顺序存储结构简称为顺序栈,它是运算受限的顺序表。顺序栈中元素用向量存放栈底位置是固定不变的，可设置在向量两端的任意一个端点栈顶位置

27、是随着进栈和退栈操作而变化的，用一个整型量top（通常称top为栈顶指针）来指示当前栈顶位置3. 进栈操作：进栈时，需要将S-top加1，S-top=StackSize-1表示栈满上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。退栈操作：退栈时，需将S-top减1S-topfront=Q-rear=0;Q-count=0; 判队空:return Q-count=0; 判队满:return Q-count=QueueSize; 入队Q-count +; /队列元素个数加1Q-dataQ-rear=x; /新元素插入队尾Q-rear=(Q-rear+1)%QueueSize; 出队temp=Q

28、-dataQ-front;Q-count-; /队列元素个数减1Q-front=(Q-front+1)%QueueSize; /循环意义下的头指针加1return temp;取队头元素return Q-dataQ-front;11. 队列的链式存储结构简称为链队列。它是限制仅在表头删除和表尾插入的单链表。链队列的基本运算:（1） 置空队：Q-front=Q-rear=NULL;（2） 判队空：return Q-front=NULL&Q-rear=Null;（3） 入队：QueueNode *p=(QueueNode *)malloc(sizeof(QueueNode);/申请新结点 p-dat

29、a=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） 取队头元素

30、：if(QueueEmpty(Q) Error(Queue if empty.); return Q-front-data; 和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。以上讨论的是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算。12. 递归是指：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。调用函数时，系统将会为调用

31、者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。第四章 串1. 串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。串（String）是零个或多个字符组成的有限序列。一般记为S=a1a2an将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。2. 长度为零的串称为空串（Empty String），它不包含任何字符。 仅由一个或多个空格组成的串称为空白串（Bla

32、nk String）。 和分别表示长度为1的空白串和长度为0的空串。3. 串中任意个连续字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。空串是任意串的子串 任意串是其自身的子串。4. 通常在程序中使用的串可分为：串变量和串常量。串变量和其它类型的变量一样，其取值是可以改变的。串常量和整常数、实常数一样，在程序中只能被引用但不能改变其值。即只能读不能写。5.串的基本运算：求串长：int strlen(char *s);/求串s的长度串复制：char *strcpy(char *to,*from)；/将from串复制到to串中，并返回to开始处指针联接：char *strcat(cha

33、r *to,char *from);/将from串复制到to串的末尾， /并返回to串开始处的指针串比较：int strcmp(char *s1,char *s2);/比较s1和s2的大小， /当s1s2和s1=s2时，分别返回小于0、大于0和等于0的值【例】result=strcmp(baker,Baker); /result0 result=strcmp(12,12); /result=0 result=strcmp(Joe,joseph) /result0字符定位：char *strchr(char *s,char c);/找c在字符串s中第一次出现的位置， /若找到，则返回该位置，否则

34、返回NULL6. 串的顺序存储结构简称为顺序串。 与顺序表类似，顺序串是用一组地址连续的存储单元来存储串中的字符序列。按其存储分配的不同可将顺序串分为如下两类：（1）静态存储分配的顺序串 串值空间的大小在编译时刻就已确定，是静态的。难以适应插入、链接等操作直接使用定长的字符数组存放串内容外，一般可使用一个不会出现在串中的特殊字符放在串值的末尾来表示串的结束。所以串空间最大值为MaxStrSize时，最多只能放MaxStrSize-1个字符。C语言中以字符0表示串值的终结。 （2）动态存储分配的顺序串:顺序串的字符数组空间可使用C语言的malloc和free等动态存储管理函数，来根据实际需要动态

35、地分配和释放。7. 用单链表方式存储串值，串的这种链式存储结构简称为链串。链串和单链表的差异仅在于其结点数据域为单个字符：一个链串由头指针唯一确定。链串的结点大小:为了提高存储密度，可使每个结点存放多个字符。当结点大小大于1时，串的长度不一定正好是结点大小的整数倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。8. 子串定位运算又称串的模式匹配或串匹配。子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。在串匹配中，一般

36、将主串称为目标（串），子串称为模式（串）。串匹配就是对于合法的位置（又称合法的位移）0in-m，依次将目标串中的子串titi+1ti+m-1和模式串p0p1p2pm-1进行比较：若titi+1ti+m-1p0p1p2pm-1，则称从位置i开始的匹配成功，或称i为有效位移。若titi+1ti+m-1p0p1p2pm-1，则称从位置i开始的匹配失败，或称i为无效位移。因此，串匹配问题可简化为找出某给定模式串P在给定目标串T中首次出现的有效位移。有些应用中要求求出P在T中所有出现的有效位移。9.朴素的串匹配算法的基本思想：即用一个循环来依次检查n-m+1个合法的位移i（0in-m）是否为有效位移。顺

37、序串上的串匹配算法：最坏时间复杂度：为O(n-m+1)m)。模式匹配算法的改进：朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移i是否为有效位移时，没有利用检查位移i-1，i,0时的部分匹配结果。 若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏时间控制在O（m+n）数量级上。链串上的子串定位运算：用结点大小为1的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移shift是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。第五章 多维数组和广义表1. 多维

38、数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。2. 一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。同一数组的不同元素通过不同的下标标识。 （a1,a2,an)3. 二维数组Amn可视为由m个行向量组成的向量，或由n个列向量组成的向量。二维数组中的每个元素aij既属于第i行的行向量，又属于第j列的列向量。4. 多维数组: 三维数组Amnp可视为以二维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量 三维数组中的每个元素aijk都属于三个向量。四维数组中的每个元素都属于四个向量5. 数组的顺序存储方式

39、: 由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。（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,，amn6.数组元素的地址计算公

40、式:（1）按行优先顺序存储的二维数组Amn地址计算公式 LOC(aij)=LOC(a11)+(i-1)n+j-1d (注：此公式下界为1，如下界为0，则公式变为in+j) LOC(a11)是开始结点的存放地址（即基地址） d为每个元素所占的存储单元数 由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。（2）按列优先顺序存储的二维数组Amn地址计算公式LOC(aij)=LOC(a11)+(j-1)m+i-1d(注：此公式下界为1，如下界为0，则公式变为jm+i)（3）按行优先顺序存储的三维数组Amnp地址计算公式 LOC(aijk)=LOC(a11

41、1)+(i-1)np+(j-1)p+k-1d(注：此公式下界为1，如下界为0，则公式变为inp+jp+k)（4）下界不为1的二维数组的地址计算公式二维数组Ac1.d1,c2.d2的地址计算公式： LOC(aij)=LOC(ac1c2)+(i-c1)(d2-c2+1)+j-c2d 下界为0的二维数组的地址计算公式（C语言中使用） LOC(aij)=LOC(a00)+i(d2+1)+jd7. 矩阵用二维数组描述时，存储的密度为1。可以对其元素进行随机存取，各种矩阵运算也非常简单。矩阵的压缩：矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩

42、存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。8. 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。（1）对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0i，jn-1（2）对称矩阵的压缩存储对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。按行优先顺序存储主对角线(包括对角线)以下的元素（下三角矩阵中，元素总数为n(n+1)/2）。即按a00,a10,a11,，an-1,0,an-1,1，an-1,n-1次序存放在

43、一个向量sa0n(n+1)/2-1中sa0=a00 ,sa1=a10 ,san(n+1)/2-1= an-1,n-1元素aij的存放位置:sai(i+1)/2+j=aijaij和sak之间的对应关系：令I=max(i,j)，J=min(i,j)，则k和i，j的对应关系可统一为： k=I(I+1)/2+J 0k(k-1)2，则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。12. 稀疏矩阵:设矩阵Amn中有s个非零元素，若s远远小于矩阵元素的总数(即smn)，则称A为稀疏矩阵。为了节省存储单元，可只存储非零元素。由于非

44、零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。13. 三元组表：将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。14.压缩存储结构上矩阵的转置运算一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵，且：Aij=Bji，0im，0jd

45、ata置换为B的三元组表b-data15.三元组表的转置: 由于A的列是B的行，因此，按a-data的列序转置，所得到的转置矩阵B的三元组表b-data必定是按行优先存放的。 按这种方法设计的算法，其基本思想是：对A中的每一列col(0cola-n-1)，通过从头至尾扫描三元组表a-data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b-data中，即可得到B的按行优先的压缩存贮表示。该算法的时间主要耗费在col和p的二重循环上：若A的列数为n，非零元素个数t，则执行时间为O(nt)，即与A的列数和非零元素个数的乘积成正比。通常用二维数组表示矩阵时，其转置算法的执行时

46、间是O(mn)，它正比于行数和列数的乘积。16.带行表的三元组表: 为了方便某些矩阵运算，在按行优先存储的三元组表中，加入一个行表来记录稀疏矩阵中每行的非零元素在三元组表中的起始位置。这就是带行表的三元组表。相应的算法描述较为简单，但这类顺序存储方式对于非零元的位置或个数经常发生变化的矩阵运算就显得不太适合。17. 广义表(Lists，又称列表)是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。广义表是n(n0)个元素a1，a2，ai，an的有限序列。 其中： ai-或者是原子或者是一个广义表。 广义表通常记作：Ls=( a1，a2，ai，an)。 Ls是广义表的名字，

47、n为它的长度。 若ai是广义表，则称它为Ls的子表。注意： 广义表通常用圆括号括起来，用逗号分隔其中的元素。 为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。 若广义表Ls非空(n1)，则al是LS的表头，其余元素组成的表(a1，a2，an)称为Ls的表尾。 广义表是递归定义的广义表的深度：一个表的深度是指表展开后所含括号的层数。18. 广义表的图形形状划分：与树对应的广义表称为纯表，它限制了表中成分的共享和递归允许结点共享的表称再入表，上图(d),子表A是共享结点，它既是C的一个元素，又是子表B的元素；允许递归的表称为递归表上图(e)，表D是其自身的子表。19. 广义表

48、的两个特殊的基本运算：取表头head(Ls)和取表尾tail(Ls)。根据表头、表尾的定义可知：任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，而其表尾必定是子表。head=(a，b)=a，tail(a，b)=(b) head(A，y)=A， tail(A，y)=(y) 由于tail(L)是非空表，可继续分解得到： head(tail(L)=b， tail(tail(L)=() 对非空表A和(y)，也可继续分解。 注意: 广义表()和()不同。前者是长度为0的空表，对其不能做求表头和表尾的运算；而后者是长度为l的非空表(只不过该表中惟一的一个元素是空表)，对其可进行分解，

49、得到的表头和表尾均是空表()。第六章 树1. 树的递归定义： 树(Tree)是n(n0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定的称为根(Root)的结点；(2)其余的结点可分为m(m0)个互不相交的子集Tl，T2，Tm，其中每个子集本身又是一棵树，并称其为根的子树(Subree)。树的递归定义刻画了树的固有特性：一棵非空树是由若干棵子树构成的，而子树又可由若干棵更小的子树构成。2. 广义表表示法: 用广义表的形式表示的。上图(a)树的广义表表示法如图(d)（A（B（E，F（I，J），C，D（G，H）3. 树结构的基本术语（1） 结点的度(Degree

50、) 树中的一个结点拥有的子树数称为该结点的度(Degree)。 一棵树的度是指该树中结点的最大度数。 度为零的结点称为叶子(Leaf)或终端结点。 度不为零的结点称分支结点或非终端结点。 除根结点之外的分支结点统称为内部结点。 根结点又称为开始结点。（2） 孩子(Child)和双亲(Parents) 树中某个结点的子树之根称为该结点的孩子(Child)或儿子，相应地，该结点称为孩子的双亲(Parents)或父亲。同一个双亲的孩子称为兄弟(Sibling)。（3）祖先(Ancestor)和子孙(Descendant)路径（path）若树中存在一个结点序列k1，k2，ki，使得ki是ki+1的双亲(1ij)，则称该结点序列是从kl到kj的一条路径(Path)或道路。 路径的长度指路径所经过的边(即连接两个结点的线段)的数目，等于j-1。祖先(Ancestor)和子孙(Descendant) 若树中结点k到ks存在一条路径，则称k是ks的祖先(Ancestor)，ks是k的子孙