第一章：绪论一、基础知识概念和术语(黑体字部分)。另外，注意：1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P53、数据结构及其形式定义。P5四种基本结构：①集合②线性结构③树形结构④图（网）状结构4、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系P65、数据类型P7抽象数据类型（ADT）P7ADT=（数据对象，数据关系，基本操作）ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念P137、算法的五个特征①有穷性②确定性③可行性④输入（0个或多个）⑤输出（1个或多个）8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量其中正确性的四个层次（通常要求达到C层）。9、算法的时间复杂度P15常见有：O(1)，O(n)，O(n2)，O(log2n)分析算法的时间复杂度时，log2n常简单记作logn。，O(nlog2n)，O(2n)语句频度，用归纳法计算。10、算法的空间复杂度P17二、算法起泡排序。P16另一种形式voidBubbleSortXE"BubbleSort"\*MERGEFORMAT(DataTypea[],intn){for(i=0;i<n-1;i++)for(j=0;j<n-i-1;j++)if(a[j]>a[j+1])a[j]<—>a[j+1];}或voidBubbleSortXE"BubbleSort"\*MERGEFORMAT(DataTypea[],intn){for(i=1;i<n;i++)for(j=0;j<n-i;j++)if(a[j]>a[j+1])a[j]<—>a[j+1];}或voidBubbleSortXE"BubbleSort"\*MERGEFORMAT(DataTypea[],intn){for(i=0;i<n-1;i++){change=fasle;for(j=0;j<n-i-1;j++)if(a[j]>a[j+1]){a[j]<—>a[j+1];change=true;}if(!change)break;}}说明：a)考试中要求写算法时，可用类C，也可用C程序。b)尽量书写算法说明，言简意赅。c)技巧：用“边界值验证法”检查下标越界错误。如上第一个：第二个循环条件若写作j<n-i，则当i=0时a[j+1]会越界。d)时间复杂度为O(n2)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。第二章、线性表一、基础知识和算法1、线性表及其特点线性表是n个数据元素的有限序列。线性结构的特点：①“第一个”②“最后一个”③前驱④后继。这里太简炼了，只是为了便于记忆。2、顺序表—线性表的顺序存储结构（1）特点：a)逻辑上相邻的元素在物理位置上相邻。b)随机访问。（2）类型定义简而言之，“数组+长度”不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。。constintMAXSIZE=线性表最大长度;typedefstruct{DataTypeelem[MAXSIZE];intlength;}SqList;注：a)SqList为类型名，可换用其他写法。b)DataType是数据元素的类型，根据需要确定。c)MAXSIZE根据需要确定。如constintMAXSIZE=64;d)课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以e)课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length==L.listsize时，用realloc(L.elem,L.listsize+增量)重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。（3）基本形态顺序表空01MAXSIZE-1...L.elem[]L.elem[]L.elem[]L.length==0L.length==MAXSIZE0<L.length<MAXSIZE条件L.length==0不允许删除操作顺序表满条件L.length==MAXSIZE不允许插入操作不空也不满可以插入，删除（4）基本算法——遍历顺序访问所有元素for(i=0;i<L.length;i++)visit(L.elem[i]);5查找元素xfor(i=0;i<L.length;i++)if(L.elem[i]