数据结构C语言版复习攻略

第一章：绪论一、基础知识概念和术语(黑体字部分)。另外，注意：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)1，O(nlog2n)，O(2n)语句频度，用归纳法计算。10、算法的空间复杂度P17二、算法起泡排序。P16另一种形式voidBubbleSort(DataTypea[],intn){for(i=0;in-1;i++)for(j=0;jn-i-1;j++)if(a[j]a[j+1])a[j]—a[j+1];}或voidBubbleSort(DataTypea[],intn){for(i=1;in;i++)for(j=0;jn-i;j++)if(a[j]a[j+1])a[j]—a[j+1];}或1分析算法的时间复杂度时，log2n常简单记作logn。voidBubbleSort(DataTypea[],intn){for(i=0;in-1;i++){change=fasle;for(j=0;jn-i-1;j++)if(a[j]a[j+1]){a[j]—a[j+1];change=true;}if(!change)break;}}说明：a)考试中要求写算法时，可用类C，也可用C程序。b)尽量书写算法说明，言简意赅。c)技巧：用“边界值验证法”检查下标越界错误。如上第一个：第二个循环条件若写作jn-i，则当i=0时a[j+1]会越界。d)时间复杂度为O(n2)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。第二章、线性表一、基础知识和算法1、线性表及其特点线性表是n个数据元素的有限序列。线性结构的特点：①“第一个”②“最后一个”③前驱④后继。22、顺序表—线性表的顺序存储结构（1）特点：a)逻辑上相邻的元素在物理位置上相邻。b)随机访问。（2）类型定义简而言之，“数组+长度”3。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+增2这里太简炼了，只是为了便于记忆。3不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。量)重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。（3）基本形态1°.顺序表空条件L.length==0不允许删除操作2°.顺序表满条件L.length==MAXSIZE不允许插入操作3°.不空也不满可以插入，删除（4）基本算法——遍历4°.顺序访问所有元素for(i=0;iL.length;i++)visit(L.elem[i]);5查找元素xfor(i=0;iL.length;i++)if(L.elem[i]==x)break;if(iL.length)找到;else未找到;(2)插入算法ListInsert(&L,i,x)1°.前提：表不满2°.合理的插入范围：1≤i≤L.length+1注：位序i在C/C++中对应于下标i-1。3°.步骤第i至最后所有元素后移一个元素在第i个位置插入元素x表长增14°.算法bool4ListInsert(SqList&L,inti,DataTypex){if(L.length==MAXSIZE||i1||iL.length+1)returnfalse;//失败//元素后移for(j=L.length-1;j=i-1;j--)//这里j为下标，从L.length-1到i-1L.elem[j+1]=L.elem[j];//若作为位序，有如何修改？//插入xL.elem[i-1]=x;//表长增1L.length++;4这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。01MAXSIZE-1...L.elem[]L.elem[]L.elem[]L.length==0L.length==MAXSIZE0L.lengthMAXSIZEreturntrue;//插入成功}(3)删除算法ListDelete(&L,i,&x)1°.前提：表非空2°.合理的删除范围：1≤i≤L.length3°.步骤取出第i个元素第i个元素之后的元素向前移动一个位置表长减14°.算法boolListDelete(SqList&L,inti,DataType&x){if(L.length==0||i1||iL.length)returnfalse;//失败x=L.elem[i-1];for(j=i;jL.length;j++)L.elem[j-1]=L.elem[j];L.length--;returntrue;//删除成功}(4)算法分析表错误!文档中没有指定样式的文字。.1顺序表插入和删除算法的分析插入删除基本操作平均移动次数移动元素2)1(1111ninnni移动元素21)(11ninnni时间复杂度O(n)O(n)尾端操作插入第n+1个元素，不移动删除第n个元素，不移动插入、删除需移动大量元素O(n)；但在尾端插入、删除效率高O(1)。(5)其他算法1°.InitList(&L),ClearList(&L)L.length=0;2°.ListEmpty(L)returnL.length==0;3°.ListLength(L)returnL.length;4°.GetElem(L,i,&e)e=L.elem[i-1];单链表——线性表的链式存储结构之一(6)概念线性链表，单链表，结点；数据域，指针域；头指针，头结点。(7)特点用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。(8)类型定义简而言之，“数据+指针”5。typedefstructLNode{DataTypedata;structLNode*next;}LNode,*LinkList;(9)基本形态带头结点的单链表的基本形态有：1°.单链表空条件：L-next==02°.单链表不空条件：L-next!=0(10)基本算法（遍历）1°.顺序访问所有元素借助指针，“顺藤摸瓜．．．．”(沿着链表访问结点)。p=L-next;//注意起始位置的考虑while(p!=NULL){//判表尾，另外(p!=0)或(p)均可visit(p-data);//访问:可以换成各种操作p=p-next;//指针沿着链表向后移动}例：打印单链表中的数据。voidPrintLinkList(LinkListL){p=L-next;while(p!=NULL){print(p-data);//访问：打印数据域p=p-next;}}2°.查找元素x//在单链表L中查找元素x5不准确的说法，只为便于理解和记忆，不要在正式场合引用。/\an/\CBA(b)(a)Ea1LL...datanext//若找到，返回指向该结点的指针；否则返回空指针LinkListFind(LinkListL,DataTypex){p=L-next;while(p!=NULL){if(p-data==x)returnp;//找到xp=p-next;}returnNULL;//未找到}//在单链表L中查找元素x//若找到，返回该元素的位序；否则返回0intFind(LinkListL,DataTypex){p=L-next;j=1;while(p!=NULL){if(p-data==x)returnj;//找到xp=p-next;j++;//计数器随指针改变}return0;//未找到}前一个算法的另一种写法：p=L-next;while(p&&p-data!=x)p=p-next;if(p&&p-data==x)returnp;elsereturn0;或者p=L-next;while(p&&p-data!=x)p=p-next;returnp;//为什么3°.查找第i个元素LinkListGet(LinkListL,inti){p=L-next;j=1;while(p&&ji){p=p-next;j++;}if(p&&j==i)returnp;elsereturn0;}4°.查找第i-1个元素p=L;j=0;while(p&&ji-1){p=p-next;j++;}if(p&&j==i-1)returnp;elsereturn0;(11)插入算法ListInsert(&L,i,x)技巧：画图辅助分析。思路：先查找第i-1个元素若找到，在其后插入新结点bool6ListInsert(LinkList&L,inti,DataTypex){//查找第i-1个元素pp=L;j=0;while(p&&ji-1){p=p-next;j++;}//若找到，在p后插入xif(p&&j==i-1){s=(LinkList)malloc(sizeof(LNode));s-data=x;s-next=p-next;//①p-next=s;//②returntrue;//插入成功}elsereturnfalse;//插入失败}注意：a)要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。b)能够插入的条件：p&&j==i-1。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。c)新建结点时需要动态分配内存。s=(LinkList)malloc(sizeof(LNode));若检查是否分配成功，可用if(s==NULL)exit(1);//分配失败则终止程序d)完成插入的步骤：①②。技巧：先修改新结点的指针域。6这里返回true表示正确插入，返回false表示插入失败。ai-1·-插入前执行①之后执行②之后·-pxsai-1·-·-px·-sai-1·-·-px·-s①②①(12)删除算法ListDelete(&L,i,&x)思路：先查找第i-1个元素若找到且其后存在第i个元素，则用x返回数据，并删除之boolListDelete(LinkList&L,inti,int&x){//查找第i-1个元素pp=L;j=0;while(p&&ji-1){p=p-next;j++;}//若存在第i个元素，则用x返回数据，并删除之if(p&&j==i-1&&p-next){//可以删除s=p-next;//①p-next=s-next;//②x=s-data;free(s);returntrue;}elsereturnfalse;}注意：a)要求p找到第i-1个而非第i个元素。为什么？b)能够进行删除的条件：p&&j==i-1&&p-next。条件中的p-next就是要保证第i个元