(30页Word修改版)数据结构复习重点

数据结构复习重点第一章绪论1.1数据、数据元素、数据项、数据结构等基本概念1.数据（data）：客观事物的符号表示，在计算机科学中指所有能输入计算机中并被计算机处理的符号总称。整数、浮点数、字符串、声音、图像。2.数据元素（dataelement）：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。3.一个数据元素可能由若干个数据项（dataitem）组成。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段）。故不是组成数据的最小单位。数据项是构成数据的最小单位。4.数据对象（dataobject）：性质相同的数据元素的集合，是数据的一个子集。5.数据结构（datastructure）：数据元素以及数据元素之间存在的关系。6.数据结构主要描述：数据元素之间的逻辑关系、数据在计算机系统中的存储方式和数据的运算，即数据的逻辑结构、存储结构和数据的操作集合1.2数据结构的逻辑结构、存储结构的含义及其相互关系1.数据的逻辑结构：用形式化方式描述数据元素间的关系。数据的逻辑结构独立于计算机，是数据本身所固有的。用于算法的设计。2.有两大类逻辑结构：线性结构（线性表、栈、队列、数组和串），非线性结构（树和图）。3.数据的物理结构（也称存储结构）：数据在计算机中的具体表示。包括数据元素的表示和关系的表示。存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。用于算法的实现。4.数据的存储方式可分为如下两类：顺序存储、链接存储。1.3算法1.算法的定义：算法是对特定问题求解步骤的一种描述，是指令的有限序列。2.算法的特性：有穷性——算法必须在执行有穷步之后结束，而且每一步都可在有穷时间内完成确定性——每条指令无二义性。并且，相同的输入只能得到相同的输出；可行性——算法中描述的每一操作，都可以通过已实现的基本运算来实现。输入——算法有零至多个输入。输出——算法有一个至多个输出3.算法效率的度量：时间复杂度和空间复杂度及计算。第二章线性表2.1线性表的逻辑结构特征存在唯一的一个被称作第一个的数据元素；存在唯一的一个被称作最后一个的数据元素；除第一个元素之外，集合中的每个数据元素均只有一个前驱；除最后一个元素之外，集合中的每个数据元素均只有一个后继。2.2线性表的顺序存储结构1.用一组连续的存储单元依次存储线性表的数据元素。在线性表的顺序存储表示中，只要确定了线性表的起始位置，线性表中任一数据元素都可随机存取。线性表的顺序存储结构是一种随机存取的存储结构。LOC(ai+1)=LOC(ai)+lLOC(ai+1)=LOC(a1)+i*lLOC(ai)表示元素ai的存储位置；LOC(a1)表示第一个数据元素的存储位置，通常称为线性表的起始位置或基地址每个数据元素占用l个存储单元。2.线性顺序表上的插入是指在第i(1≤i≤n+1)个位置插入一个新的数据元素，需将第i至第n共(n-i+1)个元素后移注意：顺序表中数据区域有listSize个存储单元，所以在向顺序表中做插入时先检查表空间是否满了，在表满的情况下不能再做插入，否则产生溢出错误。要检验插入位置的有效性，这里i的有效范围是：1=i=n+1，其中n为原表长。注意数据的移动方向算法时间复杂度：移动元素个数：n-i+1平均移动元素个数：n/2T（n）=O（n）；3.线性顺序表上的删除是指第i(1≤i≤n)个数据元素删除掉，需将第i+1至第n共（n-i)个元素前移注意：删除第i个元素，i的取值为1=i=n,否则第i个元素不存在，因此，要检查删除位置的有效性。当表空时不能做删除。删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。算法时间复杂度：移动元素个数：n-i平均移动元素个数：（n-1）/2T（n）=O（n）；4.线性表的顺序存储。优点：逻辑相邻，物理相邻可以实现数据元素的随机存取；缺点：在作插入或是删除操作时，需要移动大量数据元素2.3线性表的链式存储结构1.线性表链式存储结构的特点：用一组任意的存储单元存储线性表的数据元素。在线性表的链式存储中，在进行插入或是删除操作时，不需要进行数据元素的移动，但不能实现数据元素的随机存取。2.线性链表的表示：数据元素、数据元素之间的关系；数据域存储数据元素，指针域存储数据元素之间的关系：直接后继的存储位置，线性链表：每个节点只包含一个指针域3.假定指针p指向线性链表中的第i个数据元素，则p-next为指向线性链表中第i+1个数据元素的指针。即p-data为ai，p-next-data为ai+1。(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).nextp-next表示p指向结点的指针域4.在单链表中查找第i个元素StatusgetElem_L(LinkListL,inti,ElemType&e){//获取线性链表中的第i个数据元素p=L-next;j=1;while(p&&ji){p=p-next;++j;}if(!p‖ji)returnERROR;returnp-data;}//GetElem_L5.在单链表中插入数据元素S-next=P-next；P-next=S;StatuslistInsert_L(LinkList&L,inti,ElemTypee){p=L;j=0;while(p&&ji-1){p=p-next;++j；}if(!p‖ji-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s-data=e;s-next=p-next;p-next=s;returnOK;}6.在单链表中删除数据元素P-＞next=P-＞next-＞next;或q=p-next;p-next=q-next;free(q);StatuslistDelete_L(LinkList&L,inti){p=L;j=0;while(p-next&&ji-1){p=p-next;++j;}if(!(p-next)‖ji-1)returnERROR;//删除位置不合理q=p-next;p-next=q-next;free(q);//删除并释放结点returnOK;}//ListDelete_L7.循环链表：表中最后一个结点的指针域指向头结点，整个链表形成一个环。循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是后继是否为空，而是后继是否为头结点。(1)单链表p或p-next==NULL(2)循环链表p-next==L8.双向链表有两个指针域，一个指向直接前驱，一个指向直接后继。1）向双向链表中插入一个结点：s-＞prior=p-＞prior；p-＞prior-＞next=s；s-＞next=p；p-＞prior=s；2）向双向链表中插入一个结点：：s-＞prior=p；s-＞next=p-next；p-next-＞prior=s；p-＞next=s；3）从双向链表中删除一个结点①p-＞prior-＞next=p-＞next；②p-＞next-＞prior=p-＞prior；第三章栈和队列3.1栈和队列的逻辑结构特征1.栈（stack）和队列（queue）是两种重要的线性结构，特殊性在于其基本操作是线性表操作的子集，是操作受限的线性表（操作限定在两个端点进行），为具有限定性的数据结构。栈按“后进先出”的规则进行操作，队列按“先进先出”的规则进行操作。2.栈是限定在表尾进行插入和删除操作的线性表。允许插入,删除的一端称为栈顶(top),另一端称为栈底(bottom)。3.栈的基本运算主要有两个：Push(S,e)，进栈，插入（压入）元素e为新的栈顶元素，Pop(S)，出栈，删除（弹出）S的栈顶元素。如：若元素入栈的顺序为1234，为了得到1342出栈顺序，操作序列为：Push(S,1)，Pop(S)，Push(S,2)，Push(S,3)，Pop(S)，Push(S,4)，Pop(S)，Pop(S)。3.2栈的顺序存储结构1.顺序栈：利用一组地址连续的存储单元一次存放从栈底到栈顶的数据元素，用指针top指示栈顶元素在顺序栈中的位置。入栈时，首先判栈是否满了，栈满的条件为：S.top-S.base=S.stacksize，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。2.用数组的索引值表示栈底和栈顶top指向栈顶元素的下一个位置top指向栈顶元素初始化：top=0top=-1判栈空：top==0top==-1入栈：v[top++]=x（先压后加）v[++top]=x（先加后压）栈满：top-base=stacksize;top-base=stacksize-1;出栈：y=v[--top])（先减后弹）y=v[top--])（先弹后减）3.两栈共享空间:top[0]表示第一个栈的栈顶;top[1]表示第二个栈的栈顶栈空:top[0]=-1;top[1]=n入栈:a[++top[0]]=e;a[--top[1]]=e栈满:top[0]+1=top[1]出栈:e=a[top[0]--];e=a[top[1]++]4.关于顺序栈的说明:入栈时，首先判栈是否满了，栈满时，不能入栈;否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产生错误。通常栈空时常作为一种控制转移的条件。top指向栈顶元素的下一个位置top指向栈顶元素初始化：S.top=S.baseS.top=S.base-1判栈空：S.base==S.topS.base==S.top-1入栈：*s-top++=e（先压后加）*++s-top=e（先加后压）栈满：S.top-S.base=S.stacksizeS.top-S.base=S.stacksize-1出栈：e=*--S.top（先减后弹）e=*S.top--（先弹后减）3.3栈的顺序链式存储入栈：p=newLNode;//建新的结点if(!p)exit(1);//存储分配失败p-data=e;p-next=S-top;//链接到原来的栈顶S-top=p;//移动栈顶指针出栈：if(!S-top)returnNULL;else{e=S-top-data;//返回栈顶元素q=S-top;S-top=S-top-next;//修改栈顶指针free(q);//释放被删除的结点空间returne;}3.4栈的应用举例1.数制转换#defineNUM10voidconversion(intN，intr){ints[NUM],top;/*定义一个顺序栈*/intx;top=-1;/*初始化栈*/while(N){s[++top]=N%r;/*余数入栈*/N=N/r;/*商作为被除数继续*/}while(top!=-1){x=s[top--];printf(“%d”,x);}}2.括号匹配的检验：3.表达式求值：熟悉前缀、中缀和后缀表达式，表达式求值时栈的状态变化。4.栈与递归的实现：熟悉使用递归解决3.5队列的逻辑结构特征队列:只允许在一端进行插入，而在另一端删除元素。允许插入的一端为队尾(rear),允许删除的一端为队头(front)。3.6队列的顺序存储结构1.循环队列的顺序存储结构:队列存放数组被当作首尾相接的表处理。队头、队尾指针加1时用语言的取模(余数)运算实现。队列初始化：front=rear=0;队空条件：front==rear;队满条件：(rear+1)%MAXQSIZE==front队头指针进1:front=(front+1)%MAXQSIZE;队尾指针进1:rear=(rear+1)%MAXQSIZE;队中元素个数：（rear-front+MAXQSIZE）%MAXQSIZE2.链式