资源描述：
《数据结构复习整理》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、1初始化操作InitList(&L)功能：建立空的线性表L：2销毁操作DetroyList(&L)功能：冋收为线性衣L动态分配的存储空间；3置空操作ClearList(&L)功能：L中己存在，重新将其置成空表；4判空操作ListEmpty(L)功能：判断线性表L是否为空表，若为空表返冋TRUE,否则返冋FALSE；5求表长操作ListLength(L)功能：返回线性表L的表长；6取元素操作:GetElem(Lzi,&e)功能：将线性表L中第i个元素赋值给e；7查找操作LocateElem(L,e,compare)))功能:在线性
2、表L屮查找与元素e满足compare()的第1个元素,返回该元素在表中的序号(或位置)，若表中不存在这样的元素，则返冋0；8查找前驱PriorElem(L,cur_e,&pre_e)功能：若cur_e是L中的数据元素且不是第一个，则用pre.e返冋它的前驱，否则失败，pre_e无定义。9查找后继NextElem(L,cur_e,&next_e)功能：若cur_e是L中的数据元素且不是最后一个，则用next_e返回它的后继，否则失败，next_e无定义。10插入操作Listinsert(&L,i,e)功能：在线性表L的第i个元素之
3、前插入1个新元素e；22删除操作ListDelete(&L,i,&e)功能：删除线性表L的第i个元素，并用e返回；12遍历操作ListTraverse(L,visit())功能：依次对线性表L的每个元素调川函数visit()o若visit()失败，则返回ERROR,否则返回0K：顺序存储表示是将数据元索存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发牛改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序(没有规定兀素进栈顺序),平
4、均需要移动一半(或近一半)元素，修改效率不启j。链接存储表示的存储空间--般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原來的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。作为一般规律，当线性表中元素个数变化鮫大或者耒知时，故好使用链表实现；而如果用户事先知道线性表的大致长度，使用顺序表的空间效率会更高。链表是一种物理存储单元上非连续、非顺序的存储结
5、构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表山一系列结点（链农中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储卜•一个结点地址的指针域。相比于线性表顺序结构，链表比较方便插入和删除操作。对线性表的基木操作栈是限定仅能在表尾一端进行插入、删除操作的线性表能进行插入和删除的一端称为栈顶，另一端称为栈底。称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。1、栈是限定仅能在表尾一端进行插入、删除操作的线性表2、栈的元素具有后进先出的特点3、栈
6、顶元素的位置由一个称为栈顶指针的变量指示，进栈和出栈操作都要修改栈顶指针栈的特点后进先出第一个进栈的元素在栈底最后一个进栈的元素在栈顶第一个出栈的元素为栈顶元素栈的示意图最后一个出栈的元素为栈底元素队列是限定仅能在衣头进行删除，表尾进行插入的线性表。能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。队列的示意图P第一个入队的元素在队头最后一个入队的元素在队尾第一个岀队的元素为队头元素最后一个岀队的元素为队尾元素三、队列的应用1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争
7、问题；3）离散事件的模拟——模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程。1、队列是限定仅能在表尾一端进行插入，表头一端进行删除的线性表；2、队列中的元素具有先进先出的特点；3、队头、队尾元素的位置分别市称为队头指针和队尾指针的变量指示；4、入队操作要修改队尾指针，出队操作要修改队头指针。数组的概念数量固定，数据类型相同的（变量）元素组合在一起。使用-•个名称代农它。这个名称就是数组名。如果要访问其中某个元素（变量），可以使用元素的索引值（下标）来访问它。在C语言中，数组元索的索引值从0开始。数组的存储
8、两种形式：既可以是顺序存储，也可以采用链式结构。稀疏矩阵含有较多值相同元索或较多零元索，□值相同元索或者零元索分布没有一定规律的矩阵称为稀疏矩阵如何设计递归函数？一、分治法（DivideandConquer）（又称分割求解法）二、后置递归法（Postponing
