自考数据结构重点.pdf

《自考数据结构重点.pdf》由会员分享，可在线阅读，更多相关《自考数据结构重点.pdf（31页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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；有

7、且仅有一个终结结点 an，没有直接后继，有且仅有一个直接前趋 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中没有结点的值为

8、x，则返回一个特殊值表示查找失败。(5)InsertList（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.顺序存储方法：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。顺序表（Seque

9、ntial List）：用顺序存储方法存储的线性表简称为顺序表。顺序表是一种随机存取结构,顺序表的的特点是逻辑上相邻的结点其物理位置亦相邻。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，D

10、ataType x，int i)/将新结点 x 插入 L所指的顺序表的第 i 个结点ai的位置上 算法的时间主要花费在 for 循环中的结点后移语句上。该语句的执行次数是 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，则必须将表

11、中位置 i+1，i+2，n 的结点，依次前移到位置 i，i+1，n-1 上，以填补删除操作造成的空缺。具体算法：void DeleteList(SeqList*L,int i)/从 L所指的顺序表中删除第 i 个结点 ai 结点的移动次数由表长 n 和位置 i 决定：i=n 时，结点的移动次数为 0，即为 0(1)，i=1 时，结点的移动次数为 n-1，的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前

12、趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 算法时间复杂度分别是 O(n)顺序表上做删除运算，平均要移动表中约一半的结点（n-1）/2，平均时间复杂度也是 O(n)。7.链接方式存储的线性表简称为链表（Linked List）。链表的具体存储表示为：用一组任意的存储单元来存放线性表的结点，链表中结点的逻辑次序和物理次序不一定相同（这组存储单元既可以是连续的，也可以是不连续的）。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）。8.链表的结点结构：data 域-

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

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

15、法：s=(ListNode*)malloc(sizeof(ListNode);/生成新结点 s-data=ch;/将读入的数据放入新结点的数据域中 if(head!=NULL)head=s;/新结点插入空表 else r-next=s;/将新结点插到*r 之后 r=s;/尾指针指向新表尾 的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品

16、文档 精品文档（3）尾插法建带头结点的单链表：头结点及作用：头结点是在链表的开始结点之前附加一个结点。它具有两个优点:由于开始结点的位置被存放在头结点的指针域中,所以在链表的第一个位置上的操作就和在表的其它位置上操作一致,无须进行特殊处理;无论链表是否为空，其头指针都是指向头结点的非空指针（空表中头结点的指针域空），因此空表和非空表的处理也就统一了。头结点数据域的阴影表示该部分不存储信息。在有的应用中可用于存放表长等附加信息。具体算法：r=head;/尾指针初值也指向头结点 while(ch=getchar()!=n)s=(ListNode*)malloc(sizeof(ListNode);/

17、生成新结点 s-data=ch;/将读入的数据放入新结点的数据域中 r-next=s;r=s;r-next=NULL;/终端结点的指针域置空，或空表的头结点指针域置空 以上三个算法的时间复杂度均为 O(n)。11.单链表上的查找：（1）链表不是随机存取结构 在链表中，即使知道被访问结点的序号 i，也不能像顺序表中那样直接按序号 i 访问结点，而只能从链表的头指针出发，顺链域 next 逐个结点往下搜索，直至搜索到第 i 个结点为止。因此，链表不是随机存取结构。（2）查找的思想方法 计数器 j 置为 0 后，扫描指针 p 指针从链表的头结点开始顺着链扫描。当 p 扫描下一个结点时，计数器 j相应

18、地加 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+;if(i=j)return p;/找到了第 i 个结点 else return NULL;/当 i0 时，找不到第 i 个结点 时间复杂度：在等概率假设下，平均时间复杂度为：为 n/2=O(n)（2）按值查找：具体算法：ListNode*p=head-next;/从开始结点比较。表非空

19、，p 初始值指向开始结点 while(p&p-data!=key)/直到 p 为 NULL或 p-data 为 key 为止 p=p-next;/扫描下一结点 的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 return p;/若 p=NULL，则查找失败，否则 p 指向值为 key 的结点 时间复杂度为：O(n)12.

20、插入运算：插入运算是将值为 x 的新结点插入到表的第 i 个结点的位置上，即插入到 ai-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;算法的时间主要耗费在查

21、找操作 GetNode 上，故时间复杂度亦为 O(n)。13.删除运算 删除运算是将表的第 i 个结点删去。具体步骤：（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 指向被删除

22、的结点 ai p-next=r-next;/将 ai从链上摘下 free(r);/释放结点 ai的空间给存储池 算法的时间复杂度也是 O（n）。链表上实现的插入和删除运算，无须移动结点，仅需修改指针。的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 14.单循环链表在单链表中，将终端结点的指针域 NULL改为指向表头结点或

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

24、为非空循环链表的尾指针 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 是否为空，而是判别它们是否等于某一指定指针，如头指针或尾指针等。在单链表中，从一已知结点出发，只能访问到该结点及其后续结点，无法找到该结点之前的其它结点。而在单循环链表中，从任一结点出发都可访问到表中所有结点，这一优点使某些

25、运算在单循环链表上易于实现。17.双向链表:双（向）链表中有两条方向不同的链，即每个结点中除 next 域存放后继结点地址外，还增加一个指向其直接前趋的指针域 prior。双链表由头指针 head 惟一确定的。带头结点的双链表的某些运算变得方便。将头结点和尾结点链接起来，为双（向）循环链表。的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精

26、品文档 精品文档 18.双向链表的前插和删除本结点操作 双链表的前插操作 void DInsertBefore(DListNode*p,DataType x)/在带头结点的双链表中，将值为 x 的新结点插入*p 之前，设pNULL DListNode*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-prio

27、r-next=p-next;/p-next-prior=p-prior;/free(p);/与单链表上的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为 O(1)。19.存储密度（Storage Density）是指结点数据本身所占的存储量和整个结点结构所占的存储量之比，即,存储密度=（结点数据本身所占的存储量）/（结点结构所占的存储总量）。的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插

28、入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 20.顺序表和链表比较 顺序表和链表各有短长。在实际应用中究竟选用哪一种存储结构呢？这要根据具体问题的要求和性质来决定。通常有以下几方面的考虑：顺序表 链表 分配方式 静态分配。程序执行之前必须明确规定存储规模。若线性表长度 n 变化较大，则存储规模难于预先确定估计过大将造成空间浪费，估计太小又将使空间溢出机会增多。动态分配只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。存储密度 为 1。当线性表的

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

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

31、化的，用一个整型量 top（通常称 top 为栈顶指针）来指示当前栈顶位置 3.进栈操作：进栈时，需要将 S-top 加 1，S-top=StackSize-1表示栈满 上溢现象-当栈满时，再做进栈运算产生空间溢出的现象。退栈操作：退栈时，需将 S-top 减 1 S-topfront=Q-rear=0;Q-count=0;判队空:return Q-count=0;判队满:return Q-count=QueueSize;入队 的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运

32、算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 Q-count+;/队列元素个数加 1 Q-dataQ-rear=x;/新元素插入队尾 Q-rear=(Q-rear+1)%QueueSize;出队 temp=Q-dataQ-front;Q-count-;/队列元素个数减 1 Q-front=(Q-front+1)%QueueSize;/循环意义下的头指针加 1 return temp;取队头元素 return Q-dataQ-front;11.队列的链式存储结构简称为链队列。它是限制仅

33、在表头删除和表尾插入的单链表。链队列的基本运算:（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;/指向对头结

34、点 x=p-data;/保存对头结点的数据 Q-front=p-next;/将对头结点从链上摘下 if(Q-rear=p)/原队中只有一个结点，删去后队列变空，此时队头指针已为空 Q-rear=NULL;free(p);/释放被删队头结点 return x;/返回原队头数据（5）取队头元素：if(QueueEmpty(Q)Error(Queue if empty.);return Q-front-data;和链栈类似，无须考虑判队满的运算及上溢。在出队算法中，一般只需修改队头指针。但当原队中只有一个结点时，该结点既是队头也是队尾，故删去此结点时亦需修改尾指针，且删去此结点后队列变空。以上讨论的

35、是无头结点链队列的基本运算。和单链表类似，为了简化边界条件的处理，在队头结点前也可附加一个头结点，增加头结点的链队列的基本运算。12.递归是指：若在一个函数、过程或者数据结构定义的内部，直接（或间接）出现定义本身的应用，则称它们是递归的，或者是递归定义的。调用函数时，系统将会为调用者构造一个由参数表和返回地址组成的活动记录，并将其压入到由系统提供的运行时刻栈的栈顶，然后将程序的控制权转移到被调函数。若被调函数有局部变量，则在运行时刻栈的栈顶也要为其分配相应的空间。因此，活动记录和这些局部变量形成了一个可供被调函数使用的活动结构。的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的

36、逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 第四章 串 1.串（又称字符串）是一种特殊的线性表，它的每个结点仅由一个字符组成。串（String）是零个或多个字符组成的有限序列。一般记为 S=a1a2an 将串值括起来的双引号本身不属于串,它的作用是避免串与常数或与标识符混淆。2.长度为零的串称为空串（Empty String），它不包含任何字符。仅由一个或多个空格组成的串称为空白串

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

38、*strcat(char*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

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

40、malloc 和 free 等动态存储管理函数，来根据实际需要动态地分配和释放。7.用单链表方式存储串值，串的这种链式存储结构简称为链串。链串和单链表的差异仅在于其结点数据域为单个字符：一个链串由头指针唯一确定。链串的结点大小:为了提高存储密度，可使每个结点存放多个字符。当结点大小大于 1 时，串的长度不一定正好是结点大小的整数的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个

41、典型的线性结构栈队列串等都是线性结构精品文档 精品文档 倍，因此要用特殊字符来填充最后一个结点，以表示串的终结。虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动，给运算带来不便。8.子串定位运算又称串的模式匹配或串匹配。子串定位运算类似于串的基本运算中的字符定位运算。只不过是找子串而不是找字符在主串中首次出现的位置。此运算的应用非常广泛。在串匹配中，一般将主串称为目标（串），子串称为模式（串）。串匹配就是对于合法的位置（又称合法的位移）0in-m，依次将目标串中的子串titi+1ti+m-1和模式串p0p1p2pm-1进行比较：若titi+1ti+m-1p0

42、p1p2pm-1，则称从位置 i 开始的匹配成功，或称 i 为有效位移。若titi+1ti+m-1p0p1p2pm-1，则称从位置 i 开始的匹配失败，或称 i 为无效位移。因此，串匹配问题可简化为找出某给定模式串 P在给定目标串 T中首次出现的有效位移。有些应用中要求求出 P在 T中所有出现的有效位移。9.朴素的串匹配算法的基本思想：即用一个循环来依次检查 n-m+1个合法的位移 i（0in-m）是否为有效位移。顺序串上的串匹配算法：最坏时间复杂度：为 O(n-m+1)m)。模式匹配算法的改进：朴素的串匹配算法虽然简单，但效率低。其原因是在检查位移 i 是否为有效位移时，没有利用检查位移 i

43、-1，i,0时的部分匹配结果。若利用部分匹配结果，模式串右滑动的距离就不会是每次一位，而是每次使其向右滑动得尽可能远。这样可使串匹配算法的最坏时间控制在 O（m+n）数量级上。链串上的子串定位运算：用结点大小为 1 的单链表做串的存储结构时，实现朴素的串匹配算法很简单。只是现在的位移 shift是结点地址而非整数，且单链表中没有存储长度信息。若匹配成功，则返回有效位移所指的结点地址，否则返回指针。的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索

44、插入终端结点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档 第五章 多维数组和广义表 1.多维数组和广义表是一种复杂的非线性结构，它们的逻辑特征是：一个数据元素可能有多个直接前驱和多个直接后继。2.一维数组（向量）是存储于计算机的连续存储空间中的多个具有统一类型的数据元素。同一数组的不同元素通过不同的下标标识。（a1,a2,an)3.二维数组 Amn可视为由 m个行向量组成的向量，或由 n 个列向量组成的向量。二维数组中的每个元素 aij既属于第i 行的行向量，又属于第 j 列的列向量。4.多维数组:三维数组 Amnp可视为以二

45、维数组为数据元素的向量。四维数组可视为以三维数组为数据元素的向量 三维数组中的每个元素 aijk都属于三个向量。四维数组中的每个元素都属于四个向量 5.数组的顺序存储方式:由于计算机内存是一维的，多维数组的元素应排成线性序列后存人存储器。数组一般不做插入和删除操作，即结构中元素个数和元素间关系不变化。一般采用顺序存储方法表示数组。（1）行优先顺序：将数组元素按行向量排列，第 i+1 个行向量紧接在第 i 个行向量后面。【例】二维数组 Amn的按行优先存储的线性序列为：a11,a12,a1n,a21,a22,a2n,，am1,am2,，amn（2）列优先顺序 将数组元素按列向量排列，第 i+1

46、个列向量紧接在第 i 个列向量后面。【例】二维数组 Amn的按列优先存储的线性序列为：a11,a21,am1,a12,a22,am2,，a1n,a2n,，amn 6.数组元素的地址计算公式:（1）按行优先顺序存储的二维数组 Amn地址计算公式 LOC(aij)=LOC(a11)+(i-1)n+j-1d (注：此公式下界为 1，如下界为 0，则公式变为i n+j)LOC(a11)是开始结点的存放地址（即基地址）d 为每个元素所占的存储单元数 由地址计算公式可得，数组中任一元素可通过地址公式在相同时间内存取。即顺序存储的数组是随机存取结构。（2）按列优先顺序存储的二维数组 Amn地址计算公式 LO

47、C(aij)=LOC(a11)+(j-1)m+i-1d(注：此公式下界为 1，如下界为 0，则公式变为j m+i)（3）按行优先顺序存储的三维数组 Amnp地址计算公式 LOC(aijk)=LOC(a111)+(i-1)np+(j-1)p+k-1d (注：此公式下界为 1，如下界为 0，则公式变为i np+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)

48、+jd 7.矩阵用二维数组描述时，存储的密度为 1。可以对其元素进行随机存取，各种矩阵运算也非常简单。矩阵的压缩：矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。8.所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。的逻辑结构数据的存储结构数据的运算数据元素之间的逻辑关系也称数据的逻辑结构数据的逻辑结构是从逻辑关系上据的存储结构是逻辑结构用计算机语言的实现它依赖于计算机语言数据的运算即对数据施加的操作最常用的检索插入终端结

49、点并且所有结点都最多只有一个直接前趋一个直接后继线性表是一个典型的线性结构栈队列串等都是线性结构精品文档 精品文档（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次序存放在一个向量 sa0 n(n+1)/2-1中 sa

50、0=a00,sa1=a10,san(n+1)/2-1=an-1,n-1 元素 aij的存放位置:sai(i+1)/2+j=aij aij和 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为稀疏矩阵。为了节省存储单元，可只存储非零元素。由于非零元素的分布一