搜索
1第1章绪论1.1数据是表示客观事物的符号，是对客观事物的抽象，是信息的载体。对计算机科学而言，经抽象(数字化)后，能被计算机识别、存储和加工处理的客观事物均称作数据。1.2具有某种共同属性的数据集合称作数据对象。数据集中的元素称作数据元素，简称元素，又称结点、顶点、记录等。数据对象={数据元素，数据元素，…，数据元素}1.3就数据的自身结构而言，分为原子型和结构型，前者是不可分解或无须分解的数据，后者可分解为若干个数据项。1.4通常，数据项是无须分解或不可分解的所谓最小数据单位，数据元素是作为整体对待的基本数据单位。1.5数据集和其上定义的一组操作合称数据类型，即，数据类型=数据集+一组操作=(数据集，一组操作)[了解]狭义地说，数据类型侧重于数据的值，不区分值相同的数据，忽略数据的自身结构。例.复数类=(复数集，运算集)，复数集以复数为基本元素，复数由两个数据项组成：实部和虚部或模和幅角。1.6数据集和其元素间的一组关系合称数据结构，即，数据结构=数据对象+数据关系=(数据对象，数据关系)1.7数据结构的抽象描述称作逻辑结构。逻辑结构分为：①集合结构；②线性结构；③树形结构(简称树结构)；④图形结构(简称图结构)。1.8树结构和图结构统称非线性结构。1.9数据结构在计算机上的具体实现称作存储结构或物理结构。存储结构分为：①顺序存储；②链式存储；③索引存储；④散列存储。1.10数据结构和其上定义的一组操作的抽象描述合称抽象数据类型，即，抽象数据类型=数据结构+基本操作=数据对象+数据关系+基本操作1.11求解问题的步骤称作算法，是合法指令的有限序列，具有以下主要特性：①有穷性；②确定性；③可行性。1.12算法所用的总时间称作时间复杂度，通常用算法中执行次数最多(频度最高)的操作的执行次数(频度)或数量级表示。时间复杂度又称时间效率，但两者的高低是相反的。1.13算法所用最大存储量称作空间复杂度。空间复杂度又称空间效率，但两者的高低是相反的。1.14从数量级上说，算法的时间复杂度和空间复杂度与规模n的某个函数同级。常见数量级由低到高排列如下：1、logan、nk、an、n!、nn(k0,a1)对同一个具体问题，数据本身所用存储量与算法无关，通常，空间复杂度只考虑附加存储空间复杂度。1.15算法的性能分析主要包括时间复杂度和空间复杂度。1.16数据元素间的关系分为有序关系和无序关系。有序关系简称弧(或有向弧、有向边)，无序关系简称边(或无向弧、无向边)，分别表为:前驱，后继、(元素，元素)或前驱→后继、元素—元素1.17k阶斐波那契序列的定义及其化简式。f0=f1=…=fk-2=0，fk-1=1，n≥k时，fn=fn-1+fn-2+…+fn-k1.18一元多项式的高效计算式。Pn(x)=p0+p1x+p2x2+…+pnxn=p0+x(p1+x(…Pn-1+xpn…))递推算法为：for(P=p[n],i=n-1;i=0;i--)(P*=x)+=p[i];第2章线性表2.1同类型元素的有限序列称作线性表。简记为(a1,a2,…,an)或a1,a2,…,an或({ai|i=1,2,…,n},{ai,ai+1|i=1,2,…,n-1})2.2线性表中元素的个数称作表长，表长为0的线性表称作空表。2.3在线性表中，第一个元素称作首元，它没有前驱，其它元素均有唯一前驱；最后一个元素称作尾元，它没有后继，其它元素均有唯一后继。线性表的这种关系称作一对一关系，记作1:1。例.既有首元又有尾元的线性表的表长≥1，某元素既有前驱又有后继的线性表的表长≥3。2.5用连续的一片存储空间依次顺序存放线性表的元素，称作线性表的顺序存储，简称顺序表。2顺序表中逻辑相邻者的存储位置也相邻。顺序表有三个要素：①基址；②表长(或尾元下标)；③预留表长(或最大下标)。如果顺序表的预留表长是常量，可用普通数组存储(称作静态顺序表，只有两个要素)，否则，用动态数组存储(称作动态顺序表)。对于顺序表，附加存储空间复杂度为O(1)，插入、删除、查找操作的时间复杂度为O(n)，其它基本操作的时间复杂度均为O(1)。2.6附加“链”将逻辑相邻数据元素的存储位置链接起来的存储结构称作链式存储。链式存储的线性表称作线性链表，简称链表。附加一个链的线性链表称作单链表。习惯上，链域指向其后继。单链表中第一个结点的地址称作头指针。作为线性链表首元的形式前驱的附加结点称作头结点。对于单链表，附加存储空间复杂度为O(n)，初始化操作的时间复杂度为O(1)，其它基本操作的时间复杂度均为O(n)。2.7静态顺序表的具体实现⑴存储结构typedefstruct{//用静态数组存储的顺序表intlast;//尾元下标(表长-1)DataTypedata[MAX];//MAX为最大表长(常量)}SeqList;⑵初始化操作的核心步骤SeqList*p=newSeqList;p-last=-1;⑶插入操作的核心步骤for(j=L-last++;j=i-1;j--)//后移L-data[j+1]=L-data[j];L-data[i-1]=x;//插入x注意后移次序：从后向前逐个后移。⑷删除操作的核心步骤for(j=i;j=L-last;j++)//前移L-data[j-1]=L-data[j];L-last--;//修改表长注意前移次序：从前向后逐个前移。2.8单链表的具体实现⑴结点的存储结构typedefstructnode{//结点结构DataTypedata;//数据域structnode*next;//指针域}Lnode,*LinkList;//结点及结点的地址⑵附加头结点初始化操作的核心步骤Lnode*L=newLnode;L-next=0;⑶求表长操作的核心步骤for(intj=0;L;L=L-next)j++;returnj;附加头结点时，j的初值改为-1或返回值改为j-1或intj=0;while(L=L-next)j++;⑷在结点p之后插入元素x的核心步骤s=newLnode;s-data=x;s-next=p-next;p-next=s;⑸删除结点p后继的核心步骤s=p-next;p-next=s-next;deletes;⑹返回第i个元素地址的核心步骤for(intj=1;ji&&L;L=L-next)j++;returni1||!L?0:L;附加头结点时，j的初值改为0或intj=1;while(ji&&L=L-next)j++;⑺返回数据元素x地址的核心步骤while(L&&L-data!=x)L=L-next;returnL;附加头结点时，改为：while(L=L-next&&L-data!=x);⑻返回数据元素x序号的核心步骤intj=1;while(L&&L-data!=x)L=L-next,j++;returnL?j:0;附加头结点时，改为：while(L=L-next&&L-data!=x)j++;⑼清空操作的核心步骤Lnode*p;while(p=L){L=L-next;deletep;}另外，调用后需补上语句：L=0;附加头结点时，改为：while(p=L-next){L=p-next;deletep;}⑽某些操作的递归算法①求表长returnL?1+Len(L-next):0;②清空if(L)Clear(L-next);deleteL;3第3章栈和队列3.1只许在一端插入和删除的线性表称作栈，此端称作栈顶，另一端称作栈底。3.2栈具有先进后出的特点(FILO)，即，后进先出的特点(LIFO)。3.3由入栈序列“…前…中…后…”不可能得到出栈序列“…后…前…中…”。3.4只许一端插入、另端删除的线性表称作队列，允许删除的一端称作队首，另端称作队尾。3.5队列具有先进先出的特点(FIFO)，即，后进后出的特点(LILO)。出队序列和入队序列相同。3.6顺序存储的栈简称顺序栈。通常，顺序栈以表尾作为栈顶。⑴存储结构typedefstruct{//静态顺序栈inttop;//栈顶下标(或栈长)DataTypedata[MAX];}SeqStack;⑵初始化的核心步骤Stack*s=newSeqStack;s-top=-1;⑶栈空的条件：s-top==-1⑷栈满的条件：s-top+1==MAX⑸入栈的核心步骤s-data[++s-top]=x;⑹出栈的核心步骤return&s-data[s-top--];或returns-data[s-top--];或x=&s-data[s-top--];或x=s-data[s-top--];3.7链式存储的栈简称链栈。通常，链栈以表头作为栈顶。⑴结点存储结构typedefstructnode{DataTypedata;structnode*next;}StackNode,*LinkStack;⑵栈空的条件：!L或L==0⑶入栈的核心步骤LinkStackp=newStackNode;p-data=x;p-next=s;s=p;⑷出栈的核心步骤Stackp=s;s=p-next;*x=p-data;deletep;⑸清空操作Stackp;while(s){p=s;s=s-next;deletep;}3.8由“入栈序列”、“出栈序列”、“栈操作序列”中的任意两项可确定另一项。例.习题3-2。3.9对于双目运算，运算符在两个操作数之前的表达式称作波兰式或前缀表达式。同理，可定义逆波兰式(或后缀表达式)。例.计算43+21*-和-+43*21。第4章串4.1字符串简称串。串中一段连续字符称为该串的子串。串是其子串的主串。4.2子串的第一个字符在主串中的序号称作子串在主串中的位置，并约定，非子串的位置是0。4.3查找一个串在另一串的位置简称串定位，或模式匹配，被查找的串又称模式串。4.4附加结束标志的定长顺序存储结构为：typedefcharString[MAX+1];通常，结束标志为空字符'\0'。4.4内嵌串长的定长顺序存储结构为：typedefcharString[MAX+1];//s[0]的值为串长4.5KMP算法中next函数的计算公式为：0j=1时next[j]=max{k|1kj且t1…tk-1=tn…tj-1}1其它情况显然，next(1)=1，next(2)=1。4.6next函数的算法为：voidNext(Stringt,intnext[]){inti=1,j=0;next[1]=0;while(it[0])if(!j||t[i]==t[j])next[++i]=++j;elsej=next[j];}4第5章数组和广义表5.1线性表称作一维数组或向量，以同类同长一维数组为元素的一维数组称作二维数组或矩阵，一般地，以同类同阶i维数组为元素的n-i维数组称作n维数组。5.2n维数组的逻辑结构表现为数据元素间的n维序关系，数组中的每个元素有唯一的被称作下标的n维位置序列。5.3掌握多维数组的低下标优先和高下标优先顺序存储的内存映象公式(例如，习题5-1)。5.5掌握压缩存储对称矩阵、三角矩阵的的内存映象公式(参见图5-6、5-8、5-9)。5.5掌握稀疏矩阵的三元组表示及其转置和加法。非零元素的三元组：(行,列,值)稀疏矩阵：(行数,列数,个数,三元组序列)约定，三元组序列按行优先排列。例如，a=(3,5,3,(1,1,1),(1,5,2),(3,3,-3))，b=(3,5,3,(1,5,-2),(3,3,2),(3,5,1))，a'=(5,3,3,(1,1,1),(3,3,-3),(5,1,2))，a+b=(3,5,3,(1,1,1),(3,3,-1),(3,5,1))5.6广义表是线性结构的嵌套，一般形式为：(a1,a2,…,an)其中，a1,a2,…,an是单个元素或广义表，n称作表长，最大嵌套层数称作表深，当ai是单个元素时简称单元素，当ai是广义表时简称表元素或子表。5.