logo资料库

数据结构总结.doc

发布时间：2022-06-13 发布人：admin 分类：说明书 资料大小：3.84M 资料格式：doc 举报 版权申诉
第1页 / 共36页
第2页 / 共36页
第3页 / 共36页
第4页 / 共36页
第5页 / 共36页
第6页 / 共36页
第7页 / 共36页
第8页 / 共36页
资料共36页，剩余部分请下载后查看
    第 1 章 绪论 1.1 数据结构的基本概念 1.1.1 基本概念和术语 1.数据 2.数据元素：可由若干数据项组成，数据项是不可分割的最小单位 3.数据对象：具有相同性质的数据元素的集合 4.数据类型：是一个值的集合和定义在此集合上一组操作的总称 5.抽象数据类型（ADT）：包括数据对象、数据关系和基本操作集 6.数据结构：逻辑结构、存储结构和数据的运算 1.1.2 数据结构的三要素 1.逻辑结构：分为线性和非线性结构 2.存储结构（物理结构）：包括顺序、链式、索引和散列存储 3.数据的运算：运算的定义和实现 1.2 算法和算法评价 1.2.1 算法的基本概念 1.五个重要特性：有穷、确定、可行、输入和输出 2.好的算法目标：正确性、可读性、健壮性、高效率与低存储量 1.2.2 算法效率的度量 )( ，通常指最坏情况下时间复杂度 1.时间复杂度： )) ( nfOnT  ( 2.空间复杂度：原地工作指算法所需的辅助空间是常量 第 2 章 线性表 2.1 线性表的定义及基本操作 2.1.1 线性表的定义 1.线性表是具有 n 个相同类型数据元素的有限序列，n 为表长，n=0 是空表 2.1.2 线性表的基本操作 1.InitList(&L) 2.Length(L) 3.LocateElem(L,e) 4.GetElem(L,i) 5.ListInsert(&L,i,e) 6.ListDelete(&L,i,&e) 7.Empty(L) 8.DestroyList(&L) 2.2 线性表的顺序表示 2.2.1 顺序表的定义 1.元素逻辑位置与物理位置相同，线性表的顺序从 1 开始 2.线性表的顺序存储类型 （1）一位数组静态分配
    （2）动态分配 C 的初始动态分配语句 L.data = (ElemType*)malloc(sizeof(ElemType)*InitSize); 3.顺序表特点：随机访问，存储密度高，插入和删除需要移动大量元素 2.2.2 顺序表上基本操作的实现 （1）插入：在第 i 个位置插入 e( )，i 不合法则返回 false；否则，将第 i 个 元素及其后所有元素右移一个位置；插入 e，表长加 1，返回 true（从后往前依次后移一个） . length Li  1  1 平均移动 n/2 个元素，则时间复杂度为 O(n) （2）删除：删除第 i 个元素，成功返回 true，并将元素用 e 返回，否则返回 false（从前往 后依次前移一个） 平均移动(n-1)/2 个元素，则时间复杂度为 O(n) （3）按值查找（顺序查找）：若成功返回元素位序，若失败返回 0 平均比较次数(n+1)/2，时间复杂度为 O(n) 2.3 线性表的链式表示 2.3.1 单链表的定义：每个链表结点除了存放自身信息，还存放指向其后继结点的指针；顺 序存取，从表头开始查找 1.通常用头指针标识一个单链表，如单链表 L，头指针为“NULL”表示一个空表；通常在单 链表前面附加一个头结点（不设数据，指针域指向线性表第一个结点） 2.引入头结点优点：（1）由于开始结点的位置被存放在头结点指针域中，所以在链表第一 个位置上的操作和其他位置上一样（2）无论链表是否为空，其头指针是指向头结点的非空 指针，因此空表和非空表同样处理
    2.3.2 单链表上基本操作实现 1.头插法建立单链表：每次插入结点插到表头之后 时间复杂度 O(n) 2.采用尾插法建立单链表：需增加一个尾指针，使其始终指向尾结点 3.按序号查找结点值：从第一个结点出发，顺 next 往下查找，O(n) 4.按值查找元素：O(n)
    5.插入结点：插入到第 i 个位置，先检查插入位置合法性，然后找到第 i-1 个结点，在其后插 入 p = GetElem(L.i-1); s->next = p->next; p->next = s; （1）时间复杂度为 O(n)，若在给定序号后插入时间复杂度为 O(1) （2）扩展：对某一结点进行前插操作：仍将*s 插入到*p 后面，然后将 p->data 与 s->data 换位置 6.删除结点操作：先检查位置合法性，找到 i-1 个位置，即被删除结点的前驱结点位置 p = GetElem(L,i-1); q = p->next; p->next = q->next; free(q); 2.3.3 双链表 两个指针 prior（指针前驱）和 next（指向后继） typedef struct DNode { ElemType data; struct DNode *prior,*next; }DNode *DLinkList; 1.双链表的插入 2.双链表的删除 2.3.4 循环链表
    1.循环单链表：表中最后一个元素不是指向 NULL，而是指向头结点；判断是否为空是头结 点是否等于头指针；若操作经常在表头和表尾进行，可设置尾指针，这样效率为 O(1) 2.循环双链表：空表时头结点的 prior 和 next 都是 L 3.静态链表：指针是数组下标 第 3 章 栈和队列 3.1 栈 3.1.1 栈的基本概念 1.栈的定义：只允许在一端进行插入和删除操作的线性表。栈顶（允许插入和删除的一端）、 栈底、空栈，后进先出 2.栈的基本操作 （1）InitStack(&S) （2）StackEmpty(S) （3）Push(&S,x) （4）Pop(&S,&x) （5）GetTop(S,&x) （6）ClearStack(&S) 3.1.2 栈的顺序存储结构 1.顺序栈的实现：用一维数组存放自栈底到栈顶的数据元素，同时附设一个指针（top）指 示当前栈顶位置 （1）栈顶指针 S.top 初始为-1，栈顶元素 S.data[S.top] （2）进栈：栈不满，栈顶指针先加 1，再送值到栈顶元素 （3）出栈：栈非空，先取栈顶元素值，再讲栈顶指针减 1 （4）栈空：S.top==-1，栈满 S.top==MaxSize-1，栈长 S.top+1 2.顺序栈的基本运算 （1）初始化 （2）判栈空
    （3）进栈 （4）出栈 （5）读栈顶元素 3.共享栈：栈满 top1-top=1 3.1.3 栈的链式存储结构 所有操作都是在单链表表头进行，第一个插入的结点在尾结点，之后依次往前插入，生成表 头 注：n 个不同的元素入栈，有 1  1 nC 2 n 个出栈序列 n 3.2 队列 3.2.1 队列的定义 1.队列的定义：只允许在表的一端插入在另一端删除，入队和出队，先进先出 2.队列常见的基本操作 （1）InitQueue(&Q) （2）QueueEmpty(Q) （3）EnQueue(&Q,x) （4）DeQueue(&Q,&x) （5）GetHead(Q,&x) 3.2.2 队列的顺序存储结构 1.队列的顺序存储：附设两个指针 front 和 rear 分别指示队头元素和队尾元素的下一个位置
    初始状态（队空）：Q.front==Q.rear==0 进队操作（队不满）：先送值到队尾，再将队尾指针加 1 出队操作（队不空）：先取队头值，再讲队头指针加 1 2.循环队列 （1）初始时：Q.front=Q.rear=0 （2）队首指针进 1：Q.front=(Q.front+1)%MaxSize （3）队尾指针进 1：Q.rear=(Q.rear+1)%MaxSize （4）队列长度：(Q.rear+MaxSize-Q.front)%MaxSize 队空条件：Q.front==Q.rear 为了区分队满还是队空：牺牲一个单元，队头指针在队尾指针的下一个位置作为队满标志； 队满条件为(Q.rear+1)%MaxSize==Q.front 3.循环队列的操作 （1）初始化 （2）判断空 （3）入队 （4）出队 3.2.3 队列的链式存储结构 1.队列的链式存储：是一个同时带有队头指针和队尾指针的单链表，头指针指向队头结点，
    尾指针指向队尾结点 当 Q.front==Q.rear==NULL 时链队列为空，通常将链队列设计一个头结点 2.链队列的基本操作 （1）初始化 （2）判断空 （3）入队 （4）出队 3.2.4 双端队列 两端均允许进队和出队的队列：重点是受限制的双端队列，即进队只有一端出队有两端或相 反 3.3 栈和队列的应用 3.3.1 栈在括号匹配中的应用 3.3.2 栈在表达式求值中的应用：中缀表达式与后缀表达式相互转换 1.中缀表达式 A+Bx(C-D)-E/F 转化为后缀表达式为 ABCD-x+EF/- 2.操作：如果该项是操作数，则将其压入栈中；如果该项是操作符，则连续从栈中弹出操作 数 Y 和 X，做 YX 操作，并将其重新压入栈 3.3.3 栈在递归中的应用：效率并不高 3.3.4 队列在层次遍历中的应用
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料