数据结构学位考复习课(1)第一部分：数据结构与算法的基本概念基本概念和术语数据的逻辑、物理（存储）结构逻辑结构：数据元素之间的逻辑关系物理结构：数据元素在计算机中的存储方法（表现和实现）数据结构的分类：按照逻辑结构的不同分为：集合、线性结构、树状结构、网状结构按照物理结构的不同分为：顺序结构：利用在存储器中的物理关系来表示逻辑关系。链式结构：用在存储器中附加指针的方式来表示逻辑关系。算法：对特定问题求解步骤的一种描述，是指令的有序序列算法的五个特性：有穷性、确定性、可行性、输入、输出算法设计的要求：时间复杂度，空间复杂度时间复杂度：算法执行时间随规模增长而增长的趋势T(n)=O(f(n))f(n)算法规模，T(n)称算法复杂度估算办法：以算法中重复执行的次数作为算法时间复杂度的依据。三种最常见时间复杂度：O(1)常量级O(n)线性级O(n2)平方级算法的空间复杂度S(n)=O(f(n))算法执行过程中所需的最大空间估算方法：输入数据所占空间+程序所占空间+辅助变量所占空间第二部分线性表、栈、队列1.线性表的顺序表示和实现顺序表的特点表示方法：在高级语言中，用一维数组表示：表示方法：constLIST_INIT_SIZE=100;//表初始分配空间constLISTINCREMENT=10;//空间分配增量typedefstruct{ElemType*elem;//存储空间intlength;//当前长度intlistsize;//当前存储容量intLISTINCREMENT;//可增加存储空间}SqList;注意：1.数组指针elem指示线性表的基地址，length:线性表的当前长度。2.C语言数组的下标从0开始，即数组中的第i个元素为L.elem[i-1]2.线性表的链式表示和实现线性链表线性链表（单链表）的定义：typedefstructLNode{ElemTypedata;structLnode*next;}Lnode,*LinkList循环链表双向链表双向循环链表3.栈的表示和实现顺序栈的表示和实现顺序表示#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;其中stacksize表示栈当前可以使用的最大容量。base为栈底，top为栈顶。栈顶指针指向栈顶元素的下一个位置（即下次压栈时元素所放的位置）顺序栈的结构链栈的结构和表示4.队列的表示和实现链式队列typedefstructQnode{QElemTypedata;structQnode*next;}Qnode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;课堂练习：链队列的操作入对列、出队列顺序队列#defineMAXQSIZE100typedefstruct{QElemType*base;intfront;intrear;}SqQueue;其中base为连续空间首地址，front为队首，rear为队尾。为什么用循环队列来实现顺序队列？循环队列：关键问题2：出队时，判断空队Q.rear==Q.front;入队时，判断满队(Q.rear+1)modMAXSIZE==Q.front;典型例题2.5画出执行下列各行语句后各指针及链表的示意图L=(LinkList)malloc(sizeof(LNode));P=L;for(i=1;i<=4;i++){P->next=(LinkList)malloc(sizeof(LNode));P=P->next;P->data=i*2-1;}P->next=NULL;for(i=4;i>=1;i--)Ins_LinkLIst(L,i+1;i*2);for(i=1;i<=3;i++)Del_LinkList(L,i);2.8已知P结点是双向链表的中间结点，试写出下列操作的语句序列：(1)在P结点后插入s结点(2)在P结点前插入s结点(3)删除P结点的直接后继结点(4)删除P结点的直接前驱结点(5)删除P结点设rear是指向非空带头节点的单循环链表的尾指针，则写出删除表首结点的操作的语句序列2.33已知一个线性链表表示的线性表中含有三类字符的数据元素（如字母、数字、和其他），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表表示的线性表中均只含一类字符。要求：充分用原来的存储空间；问题：如果要求建立3个单链表