谭浩强C程序设计数据结构部分

ITEducation&TrainingDate:17February2020数据结构ITEducation&TrainingDate:17February2020第一部分数据结构基础知识ITEducation&TrainingDate:17February2020数据结构•数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。ITEducation&TrainingDate:17February2020基本概念•数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。•数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。•数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。ITEducation&TrainingDate:17February2020数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：ITEducation&TrainingDate:17February2020主要内容•1.1线性表以及其应用•1.2栈、队列•1.3排序、查找ITEducation&TrainingDate:17February20201.1线性表以及其应用（1）•线性表–分为静态线性表和动态线性表–静态线性表•特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；•存储表示如下图•数据结构如下图数据1后继:2数据2后继:3数据3后继:4…………数据n-1后继:n数据nendtypedefstruct{Data_tdata;//数据域intnext;//后继域}Node_t,*PNode_t;//提供的操作有：初始化、插入、删除等。ITEducation&TrainingDate:17February2020线性表•顺序存储结构特定：借助元素在存储器中的相对位置（即，物理位置相邻）来表示数据元素之间的逻辑关系。缺点：插入、删除时，需移动大量数据。一次性分配内存空间。表的容量难以扩充。ITEducation&TrainingDate:17February2020图顺序存储结构内存结构示意图ITEducation&TrainingDate:17February20201.1线性表以及其应用（2）–动态线性表•特征：表中节点的存储是不连续的，一般节点的数量是不固定的；•存储表示如下图•数据结构如下图typedefstruct{Data_tdata;//数据域Node_t*next;//后继域}Node_t,*PNode_t;//提供的操作有：初始化、插入、删除等。数据1后继数据2后继数据3后继…………数据n-1后继数据nendITEducation&TrainingDate:17February2020链式存储结构•链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始时链式存储结构为空链，每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。ITEducation&TrainingDate:17February2020链式存储结构•每个结点有两个域，其中存储数据元素信息的域称为整数域；存储直接后继存储位置的域称为指针域。structNode{intdata;structNode*Next;};typedefstructNodeNode_t;ITEducation&TrainingDate:17February2020•链式存储结构存储线性结构数据元素集合的方法是用结点（Node）构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。只有一个指针域的结点结构如图所示。ITEducation&TrainingDate:17February2020图只有一个指针域的结点结构数据域指针域datanext或ITEducation&TrainingDate:17February2020•根据指针域的不同和结点构造链的方法不同，链式存储结构存储线性结构数据元素的方法主要有单链、单循环链和双向循环链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。头结点是指头指针所指的不存放数据元素的结点。其中，带头结点的链式结构在表的存储中更为常用，不带头结点的链式结构在堆栈和队列的存储中更为常用。ITEducation&TrainingDate:17February2020•我们把图中头结点的数据域部分涂上阴影，以明显表示该结点为头结点。图2和图3中的指针域为指向下一个结点的指针。图4中结点右部的指针域为指向下一个结点的指针，结点左部的指针域为指向上一个结点的指针。在以后的图示中，头指针将用head表示。ITEducation&TrainingDate:17February2020图2带头结点的单链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:17February2020图3带头结点的单循环链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:17February2020图4带头结点的双循环链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:17February2020•图中的符号“∧”表示空指针，空指针在算法描述中用NULL表示。空指针是一个特殊标识，用来标识链的结束。NULL在C中宏定义为0，因此空指针在C中也就是0地址。为与顺序表中数据元素从a0开始相一致，讨论链表时数据元素也从a0开始。•链式存储结构也可以方便地存储非线性结构的数据元素。链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。ITEducation&TrainingDate:17February2020•添加•插入•删除ITEducation&TrainingDate:17February2020图单链表在第一个位置删除结点过程heada0a1…an－1p=a.next;a.next=a.next.next;dispose(p);ITEducation&TrainingDate:17February2020图单链表在第一个位置插入结点过程（a）插入前；（b）插入后new(s);s.data=x;s.next=a.next;a.next=s;heada0a1…an£1xs(a)heada0a1…an£1x(b)ITEducation&TrainingDate:17February2020循环链表(circularlinkedlist)–循环链表是表中最后一个结点的指针指向头结点，使链表构成环状–特点：从表中任一结点出发均可找到表中其他结点，提高查找效率–操作与单链表基本一致,循环条件不同•单链表p或p-next=NULL•循环链表p或p-next=Hhh空表ITEducation&TrainingDate:17February2020双向链表–双向链表(Doublelinkedlist):–在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。ITEducation&TrainingDate:17February2020•双向链表（doublelinkedlist）–结点定义TypedetstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;priorelementnextL空双向循环链表：非空双向循环链表：LABbcapp-prior-next=p=p-next-proir;ITEducation&TrainingDate:17February2020栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表栈（stack）一、栈的定义和特点•定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈•特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)ITEducation&TrainingDate:17February2020栈的表示和实现栈有两种存储表示方法:•顺序栈•链栈ITEducation&TrainingDate:17February2020顺序栈–实现：top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF栈的初始空间为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空ITEducation&TrainingDate:17February2020•链栈栈顶^…...topdatalink栈底–入栈算法–出栈算法^…...栈底toptopxptop^…...栈底topqITEducation&TrainingDate:17February2020•栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)ITEducation&TrainingDate:17February2020例如(159)10=(237)8，其运算过程如下:nndiv8nmod81591971923202实际情况:(159)10=(237)81598198280237余7余3余2toptop7top73top732ITEducation&TrainingDate:17February2020•队列–队列的定义及特点•定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表–队尾(rear)——允许插入的一端–队头(front)——允许删除的一端•队列特点：先进先出(FIFO)a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)ITEducation&TrainingDate:17February2020–队列的顺序存储结构•实现：用一维数组实现sq[M]front=0rear=0123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素后一位置；front指示队头元素位置初值front=rear=0空队列条件：front==rear入队列：sq[rear++]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontITEducation&TrainingDate:17February2020•存在问题设数组长度为M，则：–当front=0,rear=M时，再有元素入队发生溢出——真溢出–当front0,rear=M时，再有元素入队发生溢出——假溢出•解决方案–队首固定，每次出队剩余元素向下移动——浪费时间–循环队列»基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11