数据结构,清华大学出版社,严蔚敏吴伟民编著

第一章绪论1、数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。2、程序设计=算法+数据结构3、解决问题方法的效率：跟数据的组织方式有关跟空间的利用效率有关跟算法的巧妙程度有关4、数据：所有能输入到计算机中,且被计算机处理的符号的集合，是计算机操作对象的总称；是计算机处理的信息的某种特定的符号表示形式。5、数据元素：数据中的一个“个体”,数据结构中讨论的基本单位。相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。6、数据项:相当于记录的“域”,是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。7、数据对象：性质相同的数据元素的集合.例如:所有运动员的记录集合8、数据结构：是相互间存在某种关系的数据元素集合。9、数据结构是带结构的数据元素的集合。10、不同的关系构成不同的结构。11、次序关系：{ai,ai+1|i=1,2,3,4,5,6}12、对每种数据结构，主要讨论如下两方面的问题：1）数据的逻辑结构，数据结构的基本操作；2）数据的存储结构，数据结构基本操作的实现；13、数据的逻辑结构：数据之间的结构关系，是具体关系的抽象。数据结构的基本操作：指对数据结构的加工处理。14、数据的存储结构(物理结构)：数据结构在计算机内存中的表示。数据结构基本操作的实现：基本操作在计算机上的实现（方法)。15、数据结构的有关概念16、数据元素的4类的基本结构：○1集合；○2线性结构：结构中数据元素之间存在一对一的关系；○3树形结构：结构中数据元素之间存在一对多的关系；○4图状结构或网状结构：结构中数据元素之间存在多对多的关系。17、C语言的优点：C语言可以直接操作内存。18、每个节点都由两部分组成：数据域和指针域。19、链接存储结构特点：比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。逻辑上相邻的节点物理上不必相邻。插入、删除灵活(不必移动节点，只要改变节点中的指针)。20、数据类型是一个值的集合和定义在此集合上的一组操作的总称。21、ADT有两个重要特征:数据抽象和数据封装。22、抽象数据类型(AbstractDataType简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。23、抽象数据类型有：数据对象〈数据对象的定义〉、数据关系〈数据关系的定义〉、基本操作〈基本操作的定义〉。24、数据类型的定义和含义。定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。含义：将数据按一定次序与形式存放的结构。24、算法空间复杂度S(n)算法的存储量包括：①输入数据所占的空间；②程序本身所占的空间；③辅助变量所占的空间。25、算法具有有穷性、确定性、可行性、输入和输出五大特性。26、抽象数据类型具有数据抽象、数据封装的特点。27、数据的储存结构分为：顺序存储结构和链式存储结构。第二章线性表1、线性结构的特点：在数据元素中的非空有限集中。（1）存在唯一的一个被称作“第一”的数据元素；（2）存在唯一的一个被称作“最后一个”的数据元素；（3）除第一个外，集合中的每一个数据元素均只有一个前驱；（4）除最后一个外，集合中的每一个数据元素均只有一个后继。2、线性表(LinearList)：一个线性表是n个数据元素的有限序列。3、线性表的顺序存储实现：typedefstruct{ElementTypeData[MAXSIZE];intLast;}List;ListL,*PtrL;4、初始化（建立空的顺序表）List*MakeEmpty(){List*PtrL;PtrL=(List*)malloc(sizeof(List));PtrL-Last=-1;returnPtrL;}5、查找intFind(ElementTypeX,List*PtrL){inti=0;while(i=PtrL-Last&&PtrL-Data[i]!=X)i++;if(iPtrL-Last)return-1;/*如果没找到，返回-1*/elsereturni;/*找到后返回的是存储位置*/}6、插入算法voidInsert(ElementTypeX,inti,List*PtrL){intj;if(PtrL-Last==MAXSIZE-1){/*表空间已满，不能插入*/printf(＂表满＂);return;}if(i1||iPtrL-Last+2){/*检查插入位置的合法性*/printf(＂位置不合法＂);return;}for(j=PtrL-Last;j=i-1;j--)PtrL-Data[j+1]=PtrL-Data[j];/*将ai～an倒序向后移动*/PtrL-Data[i-1]=X;/*新元素插入*/PtrL-Last++;/*Last仍指向最后元素*/return;}7、删除算法voidDelete(inti,List*PtrL){intj;if(i1||iPtrL-Last+1){/*检查空表及删除位置的合法性*/printf(“不存在第%d个元素”,i);return;}for(j=i;j=PtrL-Last;j++)PtrL-Data[j-1]=PtrL-Data[j];/*将ai+1～an顺序向前移动*/PtrL-Last--;/*Last仍指向最后元素*/return;}8、求表长intLength(List*PtrL){List*p=PtrL;/*p指向表的第一个结点*/intj=0;while(p){p=p-Next;j++;/*当前p指向的是第j个结点*/}returnj;}9、查找（1）按序号查找:FindKth;List*FindKth(intK,List*PtrL){List*p=PtrL;inti=1;while(p!=NULL&&iK){p=p-Next;i++;}if(i==K)returnp;/*找到第K个，返回指针*/elsereturnNULL;/*否则返回空*/}（2）按值查找:FindList*Find(ElementTypeX,List*PtrL){List*p=PtrL;while(p!=NULL&&p-Data!=X)p=p-Next;returnp;}10、插入（在链表的第i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)List*Insert(ElementTypeX,inti,List*PtrL){List*p,*s;if(i==1){/*新结点插入在表头*/s=(List*)malloc(sizeof(List));/*申请、填装结点*/s-Data=X;s-Next=PtrL;returns;/*返回新表头指针*/}p=FindKth(i-1,PtrL);/*查找第i-1个结点*/if(p==NULL){/*第i-1个不存在，不能插入*/printf(＂参数i错＂);returnNULL;}else{s=(List*)malloc(sizeof(List));/*申请、填装结点*/s-Data=X;s-Next=p-Next;/*新结点插入在第i-1个结点的后面*/p-Next=s;returnPtrL;}}11、删除（删除链表的第i(1≤i≤n)个位置上的结点)List*Delete(inti,List*PtrL){List*p,*s;if(i==1){/*若要删除的是表的第一个结点*/s=PtrL;/*s指向第1个结点*/PtrL=PtrL-Next;/*从链表中删除*/free(s);/*释放被删除结点*/returnPtrL;}p=FindKth(i-1,PtrL);/*查找第i-1个结点*/if(p==NULL){printf(“第%d个结点不存在”,i-1);returnNULL;}elseif(p-Next==NULL){printf(“第%d个结点不存在”,i);returnNULL;}else{s=p-Next;/*s指向第i个结点*/p-Next=s-Next;/*从链表中删除*/free(s);/*释放被删除结点*/returnPtrL;}}12、链表不具备的特点是1。①可随机访问任一节点②插入删除不须要移动元素③不必事先估计存储空间④所需空间与其长度成正比13、带头结点的单链表head为空的判定条件是2。①head==NULL②head-next==NULL③head-next==head④head!=NULL14、如果最常用的操作是取第i个结点及其前驱，则采用4存储方式最节省时间。①单链表②双链表③单循环链表④顺序表第三章Chapter3栈(stacks)和队列（queues）1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。2、栈的特点是“后进栈的元素先出栈”（lastin,firstout），故栈又称为后进先出表（LIFO）。3、一个栈是一些元素的线形列表，其中元素的插入和删除均在表的同一端进行。插入和删除发生的一端称为栈顶（thetopofthestack）。4、第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素。5、连续栈(ContiguousStack)的类型定义#defineMaxStack50Typedefstruct{datatypestack[MaxStack];inttop;}Seqstack;Seqstack*s;6、判断栈是否已满？viodPush(Seqstack*s,datatypex){if(s-top=MaxStack-1)printf(“overflow”);else{s-top++;s-stack[s-top]=x;}}7、判断栈是否为空？datatypepop(Seqstack*s){if(s-top0){printf(“underflow”);return(NULL);}return(s-stack[s-top]);s-top--;}8、返回栈顶元素的值，栈不发生变化。datatypetop(Seqstack*s){if(s-top0){printf(“underflow”);return(NULL);}return(s-stack[s-top]);}9、链栈（LinkedStack)的类型定义栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。链栈的类型说明如下：typedefstructstacknode{datatypedatastructstacknode*next}stacknode10、链式栈的特点：链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操作。11、栈是限定仅能在表的一端进行插入、删除操作的线性表。12、栈的元素具有后进先出的特点。13、栈顶元素的位置由栈顶指针的指示,进栈、出栈操作要修改栈顶指针。14、抽象数据类型队列的定义：队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。15、队列亦称作先进先出(FirstInFirstOut)的线性表，简称FIFO表。16、双端队列：就是限定插入和删除操作在表的两端进行的线性表。17、链队列结点定义：typedefstructQnode{QElemTypedata;structQNode*next;}QNode,*QueuPtr;18、队列的顺序存储结构称为顺序队列，在队列的顺序存储结构中，除了用一组地址连续的储存单元依次存放从队头到队尾的元素之外，尚需要附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。19、在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。20、栈的特点是先进后出，队列的