《数据结构基础知识要点》由会员分享，可在线阅读，更多相关《数据结构基础知识要点（19页珍藏版）》请在金锄头文库上搜索。
1、第一章数据结构1. 定义数据结构是计算机存储、组织数据的方式.数据结构是抽象数据类型的物理实现.2. 数据结构包括如下几个方面：（1）数据元素之间的逻辑关系，即数据的逻辑结构。（2）数据元素及其关系在计算机存储器中的存储方式，即数据的存储结构，也称为数据的物 理结构。（3）施加在该数据上的操作，即数据的运算。2. 逻辑结构类型（1）集合结构。交通工具的集合，动物的集合（2）线性结构。一对一，综合素质测评产生的学生排名（3）树形结构。一对多，单位的组织结构图，族谱（4）图形结构.多对多，生产流程、施工计划、网络建设图等3. 存储结构类型顺序存储方法。数组链式存储方法。链表（3）索引存储方法散列存
2、储方法4. 算法通常把具体存储结构上的操作实现步骤或过程称为算法。C语言里通常表现为解决问题的步骤程序=算法（加工数据）+数据结构（数据的存储和组织）5. 算法的五个特征（1）有穷性:在有穷步之后结束。（2） 确定性:无二义性.（3）可行性：可通过基本运算有限次执行来实现。（4）有输入：可有零个或多个.（5）有输出:至少有一个输出。6. 算法分析（1）时间复杂度：（算法的工作量大小）通常把算法中包含基本运算次数的多少称为算法的时 间复杂度，也就是说，一个算法的时间复杂度是指该算法的基本运算次数.算法中基本运算次数T（n）是问题规模n的某个函数f（n），记作：T（n）=O（f（n）（2）空间复杂
3、度：实现算法所需的存储单元多少第二章线性表1。线性表的基本概念线性表是具有相同特性的数据元素的一个有限序列.该序列中所含元素的个数叫做线性表 的长度，用n表示，沦0。2。线性结构的基本特征为：(1) 集合中必存在唯一的一个“第一元素；(2) 集合中必存在唯一的一个“最后元素”；(3) 除最后一个元素之外，均有唯一的后继(后件)；(4) 除第一个元素之外，均有唯一的前驱(前件)。3。定义顺序表线性表逻辑结构顺序表存储结构typedefstructElemType dataMAXCOUNT； 定义存放顺序表元素的数组int length； /length为存放线性表的实际长度SqList； 顺序表
4、类型4。顺序表上的运算及其实现(1) .建立顺序表CreateList创建一个空的顺序表，要完成线性表所需空间的分配和其他初始化设置。(2) 求线性表的长度ListLength(3) 输出线性表DispList(4) 在线性表中的指定位置插入一个元素InsertElem根据键值查找指定元素FindElemByNum(6) 获取指定位置的元素信息GetElem(7) 删除指定位置的元素DelElem(8) 释放线性表DestroyList5。线性表的链式存储一一单链表(data域和指针域next)由于顺序表中的每个元素至多只有一个前驱元素和一个后继元素，即数据元素之间是一对一 的逻辑关系，所以当
5、进行链式存储时，一种最简单也最常用的方法是：在每个结点中除包含有数据域外，只设置一个指针域，用以指向其后继结点，这样构成的 链接表称为线性单向链接表，简称单链表；头结点开始结点终端结点head -*a】土 a. 一 1 an I A I7. 单链表的定义LinkList类型的定义如下：typedefstructLNode/大定义单链表结点类型*/ElemType data；structLNode大next; /*指向后继结点大/ LinkList；8. 顺序表上的运算及其实现1、创建单链表 LinkList *CreateList()；2、初始化单链表void InitList (LinkLi
6、st *list);3、释放单链表void DestroyList(LinkList *list);4、获取单链表中元素的数量intListLength(LinkList大list);5、输出单链表中的所有数据void DispList (LinkList大list);6、获取单链表中指定位置的元素 intGetElem(LinkList 大 list, intloc, ElemType *pElem)；7、根据键值查找指定元素 intFindElemByNum (LinkList *list, char 大 keyCh, ElemType *pElem)；8、采用头插法向单链表中插入一个元素
7、intInsertElem_Head (LinkList 大list, ElemTypemyElem);9、采用尾插法向单链表中插入一个元素intInsertElem_Foot (LinkList 大list, ElemTypemyElem)；10、向单链表中的指定位置插入一个元素ntInsertElem_Loc(LinkList *list, intloc, ElemTypemyElem)；11、删除指定位置的元素intDelElem(LinkList *list, intloc, ElemType 大 pElem)；9. 线性表的链式存储一一双链表(data域指针域next和pre前驱)对
8、于双链表，采用类似于单链表的类型定义，其DLinkList类型的定义如下：typedefstructDNode/大定义双链表结点类型*/ElemType data;structDNode大prior；/大指向前驱结点大/structDNode *next;/大指向后继结点大/ DLinkList在双链表中p所指的结点之后插入一个*s结点.其操作语句描述为：s-next=pnext;/*将 s 插入到 p 之后*/pnext-prior=s;s-prior=p；pnext=s；归纳起来，删除双链表L中大p结点的后续结点。其操作语句描述为：p-next=qnext;qnext-prior=p;10
9、. 循环链表循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域不再是 空，而是指向表头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到链表中 其他结点。带头结点的单向循环链表和双向循环链表如下图头结点开始结点终端结点head * a1* a2* a1(a)循环单链表(b)循环双链表第三章栈和队列1。栈的定义及基本运算栈是限定只能在表尾进行插入和删除的线性表，并将表尾称为栈顶，表头称为栈底。栈的基本运算如下：（1） 判栈空IsEmpty（S）。若栈为空则返回“真“，否则返回”假“；（2）入栈操作（压栈）Push（S，x）将新元素压入栈中,使其成为栈顶元素；（3）出栈
10、操作（弹栈）Pop（S, x）若栈不空则返回栈顶元素，并从栈中删除栈顶元素，否则返回NULL；（4） 取栈顶元素GetTop（s，x）若栈不空则返回栈顶元素，否则返回NULL；（5） 置空栈Clear（s）将当前栈设定为空栈；2。顺序栈的存储结构及算法实现1顺序栈顺序栈利用一组连续的存储单元存放从栈底到栈顶的诸元素。typedefstructint 大 data；int capacity;int top; Stack;2顺序栈的基本运算的实现（1）入栈操作 int Push （Stack S， Datatype x）;（2）出栈操作 int Pop（Stack s， Datatype 大 x）
11、;（3）取栈顶操作 intGetTop （Stack S， Datatype 大x）；3。栈的链表存储结构1栈可以用单链表作为存储结构,链表的结点结构描述如下：typedef char ElemType;typedefstructLsnodeElemType data;structLsnode 大 next； Lsnode； 结点的类型标识符Lsnode 大 top;2栈的相关术语1. 初始化空栈voidIniStack（Lsnode *top）topnext=NULL;调用此函数之前，在主调函数中（例如main （）说明一个指针变量后，先为它申请分 配一个结点，然后调用初始化函数。2. 入栈
12、操作链栈入栈操作的含义是：将一个元素推入指定的链栈中。对该操作应设置两个参数，即 在参数中指定一个链栈及入栈的元素.假设指定的链栈top，入栈元素x其类型为ElemType,入栈操作取名为push，则该操作可表示为：viod Push (Lsnode * top,ElemType x)操作的功能为在由top指向的链栈中插入元素x,使x成为栈顶元素.3。出栈操作链栈出栈操作的含义是：从链栈中弹出栈顶结点并返回该结点中的元素值。对该操作应 设置一个参数，即在参数中指定一个链栈。假设指定的链栈top，出栈操作取名为pop, 则该操作可表示为：ElemTypePop(Lsnode *top)操作的功能
13、为从由top指向的链栈中弹出栈顶结点并返回该结点中的元素值。4。队列的基本操作进队算法：根据队列的结构，若队尾指针不在队的最大长度上，则首先队尾指针加1,元素进队，否则 就是队满，无法进队。ADDQUEUE (queue,r，f， in)/*在queue队列中进一个元素in，f和r分别是队首和队尾的标志*/if(r=n)printf(” 队满”)；elser+;queuer =in；出队算法：出队首先要判断队列中是否有元素，即R是否等于F，R=F可能出现在初态，也可能出现在 出队、进队的动态变化中.DELQUEUE(queue,r,f, out)/大在queue队列中退出一个元素到out，f和
14、r分别是队首和队尾的标志*/if(f=r)printf (队空”);elseout=queue +f;5. 链队的存储结构及其运算当队空时，Front=NULL； Rear=NULL;所谓队满，是指在可利用的空间表中，所有的结点被取 完，即AV=NULL时，才表示队满。根据队列的操作特点，进队和退队分别在表的两端进行， 具体表现为先进先出”。从链队的结构可看出，进队的基本操作步骤为(设进队结点的地 址为x)：Rearnext=x；xnext=NULL;Rear=x；第四章串1。串的基本概念串结构的形式化定义为：String= (D, R)其中,D= ai I aiEcharacter, i=1, 2.n, n20,R= a i-1 aiI a i-1,aiED, i=1, 2, .n 串 的基本运算有：初始化ClearString(s):初始化串s.(2) StrAssign (s, ch):串赋值.(3) StrCopy(s, t):串复制。(4) StrConcat(t, s1, s2):串联接。(5) 求串长StrLen(s):返回s串的元素个数，即s串的长度。(6) 串比较 StrCom (s, t)(7) 求子串SubStr (t, s, pos,len)：返回s串的第pos个字符
