数据结构经典教程

第一部分 数据结构基础知识,数据结构,数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。,基本概念,数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。,主要内容,1.1 线性表以及其应用 1.2 栈、队列 1.3 排序、查找,1.1 线性表以及其应用（1）,线性表 分为静态线性表和动态线性表 静态线性表 特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的； 存储表示如下图 数据结构如下图,typedef struct Data_t data; /数据域 int next; /后继域 Node_t, *PNode_t; /提供的操作有 ：初始化、插入、删除等。,线性表,顺序存储结构 特定：借助元素在存储器中的相对位置（即，物理位置相邻）来表示数据元素之间的逻辑关系。 缺点： 插入、删除时，需移动大量数据。 一次性分配内存空间。 表的容量难以扩充。,图顺序存储结构内存结构示意图,1.1 线性表以及其应用（2）,动态线性表 特征：表中节点的存储是不连续的，一般节点的数量是不固定的； 存储表示如下图 数据结构如下图,typedef struct Data_t data; /数据域 Node_t* next; /后继域 Node_t, *PNode_t; /提供的操作有 ：初始化、插入、删除等。,链式存储结构,链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。 和顺序存储结构不同， 初始时链式存储结构为空链， 每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。,链式存储结构,每个结点有两个域，其中存储数据元素信息的域称为整数域；存储直接后继存储位置的域称为指针域。 struct Node int data; struct Node *Next; ; typedef struct Node Node_t;,链式存储结构存储线性结构数据元素集合的方法是用结 点（Node）构造链。 线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。只有一个指针域的结点结构如图所示。,图只有一个指针域的结点结构,或,根据指针域的不同和结点构造链的方法不同， 链式存储 结构存储线性结构数据元素的方法主要有单链、 单循环链和双向循环链等三种。 这三种结构中每一种又有带头结点结构和不带头结点结构两种。 头结点是指头指针所指的不存放数据元素的结点。 其中， 带头结点的链式结构在表的存储中更为常用， 不带头结点的链式结构在堆栈和队列的存储中更为常用。,我们把图中头结点的数据域部分涂上阴影， 以明显表示该结点为头结点。 图2和图3中的指针域为指向下一个结点的指针。 图4中结点右部的指针域为指向下一个结点的指针， 结点左部的指针域为指向上一个结点的指针。 在以后的图示中， 头指针将用head表示。,图2 带头结点的单链结构 (a)空链； (b)非空链,图3 带头结点的单循环链结构 (a)空链； (b)非空链,图4 带头结点的双循环链结构 (a)空链； (b)非空链,图中的符号“”表示空指针， 空指针在算法描述中用NULL表示。 空指针是一个特殊标识， 用来标识链的结束。 NULL在C中宏定义为0， 因此空指针在C中也就是0地址。 为与顺序表中数据元素从a0开始相一致， 讨论链表时数据元素也从a0开始。 链式存储结构也可以方便地存储非线性结构的数据元素。 链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。,添加 插入 删除,图 单链表在第一个位置删除结点过程,p=a.next; a.next=a.next.next; dispose(p);,图 单链表在第一个位置插入结点过程 （a）插入前； （b）插入后,new(s); s.data=x; s.next=a.next;a.next=s;,循环链表(circular linked list),循环链表是表中最后一个结点的指针指向头结点，使链表构成环状 特点：从表中任一结点出发均可找到表中其他结点，提高查找效率 操作与单链表基本一致,循环条件不同 单链表p或p-next=NULL 循环链表p或p-next=H,双向链表,双向链表(Double linked list): 在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。,双向链表（double linked list） 结点定义,Typedet struct DuLNode ElemType data; struct DuLNode *prior; struct DuLNode *next; DuLNode,*DuLinkList;,p-prior-next= p= p-next-proir;,栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表 栈（stack） 一、栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO）,栈的表示和实现,栈有两种存储表示方法: 顺序栈 链栈,顺序栈 实现：,栈顶指针top,指向实际栈顶 后的空位置，初值为0,进栈,A,出栈,栈满,B,C,D,E,F,栈的初始空间为M top=0,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow),栈空,链栈,入栈算法,出栈算法,栈的应用举例 由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算),例如 (159)10=(237)8，其运算过程如下: n n div 8 n mod 8 159 19 7 19 2 3 2 0 2,队列 队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)允许插入的一端 队头(front)允许删除的一端 队列特点：先进先出(FIFO),队列的顺序存储结构 实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素后一位置； front指示队头元素位置 初值front=rear=0,空队列条件：front=rear 入队列：sqrear+=x; 出队列：x=sq+front;,存在问题 设数组长度为M，则： 当front=0,rear=M时，再有元素入队发生溢出真溢出 当front0,rear=M时，再有元素入队发生溢出假溢出 解决方案 队首固定，每次出队剩余元素向下移动浪费时间 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;,实现：利用“模”运算 入队： rear=(rear+1)%M; sqrear=x; 出队： front=(front+1)%M; x=sqfront; 队满、队空判定条件,循环队列上的插入操作（进队列） Status EnQueue(SqQueue ,0 1 0 1 C 0 1,7 2 7 2 7 2 C,6 3 6 3 6 3,5 4 5 4 5 4,A B A B,D D,E F E,G,图3-13,循环队列上的插入,Q.rear,Q.rear,Q.rear,Q.front,Q.front,Q.front,满队列,空队列,3）循环队列的删除 把队头元素删除 Status DeQueue(SqQueue ,G,A B,C C,D G D,F E F E,图3-14,循环队列的删除过程,Q.rear,Q.rear,Q.rear,Q.front,（1）满 （2）删除A、B后的队列 （3） 删除最后一个元素空队列,Q.front,Q.front,链队列 结点定义,typedef struct Qnode QElemType data; struct Qnode *next; Qnode, *QueuePtr;,设队首、队尾指针front和rear, front指向头结点，rear指向队尾,typedef struct QueuePtr front; QueuePtr rear; LinkQueue;,1.1 线性表以及其应用（3）,线性表的应用索引表 引出 为便于对数据（线性数据和非线性数据）进行检索和更新 ； 定义 对数据进行索引的线性表； 分类 索引可以分为单级索引和多级索引 单级索引的图示（如下图）,1.1 线性表以及其应用（4）,多级索引(以2级为例)的图示,1.1 线性表以及其应用（5）,使用索引表的好处 可以将一些非线性的问题转换为了线性问题加以解决 提高数据检索的效率 便于数据的更新,1.2 栈、队列,栈 栈的数据结构有什么特点 栈有什么样的应用 队列 队列的数据结构有什么特点 队列有什么样的用途,查找,查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的,顺序查找 查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较 算法描述,Ch7_1.c,64,监视哨,比较次数=5,比较次数： 查找第n个元素： 1 查找第n-1个元素：2 . 查找第1个元素： n 查找第i个元素： n+1-i 查找失败： n+1,顺序查找方法的ASL,折半查找 查找过程：每次将待查记录所在区间缩小一半 适用条件：采用顺序存储结构的有序表 算法实现 设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值 初始时，令low=1,high=n,mid=(low+high)/2 让k与mid指向的记录比较 若k=rmid.key，查找成功 若krmid.key，则low=mid+1 重复上述操作，直至lowhigh时，查找失败,算法描述,Ch7_2.c,分块查找 查找