谭浩强C语言之数据结构

ITEducation&TrainingDate:5February2020第一部分数据结构基础知识ITEducation&TrainingDate:5February2020数据结构•数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。ITEducation&TrainingDate:5February2020基本概念•数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。•数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。•数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。ITEducation&TrainingDate:5February2020数据的逻辑结构数据的存储结构数据的运算：检索、排序、插入、删除、修改等线性结构非线性结构顺序存储链式存储线性表栈队树形结构图形结构数据结构的三个方面：ITEducation&TrainingDate:5February2020主要内容•1.1线性表以及其应用•1.2栈、队列•1.3排序、查找ITEducation&TrainingDate:5February20201.1线性表以及其应用（1）•线性表–分为静态线性表和动态线性表–静态线性表•特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；•存储表示如下图•数据结构如下图数据1后继:2数据2后继:3数据3后继:4…………数据n-1后继:n数据nendtypedefstruct{Data_tdata;//数据域intnext;//后继域}Node_t,*PNode_t;//提供的操作有：初始化、插入、删除等。ITEducation&TrainingDate:5February2020线性表•顺序存储结构特定：借助元素在存储器中的相对位置（即，物理位置相邻）来表示数据元素之间的逻辑关系。缺点：插入、删除时，需移动大量数据。一次性分配内存空间。表的容量难以扩充。ITEducation&TrainingDate:5February2020图顺序存储结构内存结构示意图ITEducation&TrainingDate:5February20201.1线性表以及其应用（2）–动态线性表•特征：表中节点的存储是不连续的，一般节点的数量是不固定的；•存储表示如下图•数据结构如下图typedefstruct{Data_tdata;//数据域Node_t*next;//后继域}Node_t,*PNode_t;//提供的操作有：初始化、插入、删除等。数据1后继数据2后继数据3后继…………数据n-1后继数据nendITEducation&TrainingDate:5February2020链式存储结构•链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始时链式存储结构为空链，每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。ITEducation&TrainingDate:5February2020链式存储结构•每个结点有两个域，其中存储数据元素信息的域称为整数域；存储直接后继存储位置的域称为指针域。structNode{intdata;structNode*Next;};typedefstructNodeNode_t;ITEducation&TrainingDate:5February2020•链式存储结构存储线性结构数据元素集合的方法是用结点（Node）构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域用来构造数据元素之间的关系。只有一个指针域的结点结构如图所示。ITEducation&TrainingDate:5February2020•根据指针域的不同和结点构造链的方法不同，链式存储结构存储线性结构数据元素的方法主要有单链、单循环链和双向循环链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。头结点是指头指针所指的不存放数据元素的结点。其中，带头结点的链式结构在表的存储中更为常用，不带头结点的链式结构在堆栈和队列的存储中更为常用。ITEducation&TrainingDate:5February2020•我们把图中头结点的数据域部分涂上阴影，以明显表示该结点为头结点。图2和图3中的指针域为指向下一个结点的指针。图4中结点右部的指针域为指向下一个结点的指针，结点左部的指针域为指向上一个结点的指针。在以后的图示中，头指针将用head表示。ITEducation&TrainingDate:5February2020图2带头结点的单链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:5February2020图4带头结点的双循环链结构(a)空链；(b)非空链头指针头指针a0a1…an－1(a)(b)ITEducation&TrainingDate:5February2020•图中的符号“∧”表示空指针，空指针在算法描述中用NULL表示。空指针是一个特殊标识，用来标识链的结束。NULL在C中宏定义为0，因此空指针在C中也就是0地址。为与顺序表中数据元素从a0开始相一致，讨论链表时数据元素也从a0开始。•链式存储结构也可以方便地存储非线性结构的数据元素。链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。ITEducation&TrainingDate:5February2020•添加•插入•删除ITEducation&TrainingDate:5February2020图单链表在第一个位置删除结点过程heada0a1…an－1p=a.next;a.next=a.next.next;dispose(p);ITEducation&TrainingDate:5February2020图单链表在第一个位置插入结点过程（a）插入前；（b）插入后new(s);s.data=x;s.next=a.next;a.next=s;heada0a1…an£1xs(a)heada0a1…an£1x(b)ITEducation&TrainingDate:5February2020循环链表(circularlinkedlist)–循环链表是表中最后一个结点的指针指向头结点，使链表构成环状–特点：从表中任一结点出发均可找到表中其他结点，提高查找效率–操作与单链表基本一致,循环条件不同•单链表p或p-next=NULL•循环链表p或p-next=Hhh空表ITEducation&TrainingDate:5February2020双向链表–双向链表(Doublelinkedlist):–在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。ITEducation&TrainingDate:5February2020例如(159)10=(237)8，其运算过程如下:nndiv8nmod81591971923202实际情况:(159)10=(237)81598198280237余7余3余2toptop7top73top732ITEducation&TrainingDate:5February2020–队列的顺序存储结构•实现：用一维数组实现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:5February2020•存在问题设数组长度为M，则：–当front=0,rear=M时，再有元素入队发生溢出——真溢出–当front0,rear=M时，再有元素入队发生溢出——假溢出•解决方案–队首固定，每次出队剩余元素向下移动——浪费时间–循环队列»基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear»实现：利用“模”运算»入队：rear=(rear+1)%M;sq[rear]=x;»出队：front=(front+1)%M;x=sq[front];»队满、队空判定条件ITEducation&TrainingDate:5February20203）循环队列的删除把队头元素删除StatusDeQueue(SqQueue&Q,QElemTypee){if(Q.front==Q.rear)returnERROR;//队列空e=Q.base[Q.front];//删除当前队头元素Q.front=(Q.front+1)%MAXQSIZE;//修改队头指示器returnOK;}GABCCDGDFEFE图3-14循环队列的删除过程Q.rearQ.rearQ.rearQ.front（1）满（2）删除A、B后的队列（3）删除最后一个元素空队列Q.frontQ.frontITEducation&TrainingDate:5February2020frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^ITEducation&TrainingDate:5February20201.1线性表以及其应用（3）•线性表的应用－－索引表–引出•为便于对数据（线性数据和非线性数据）进行检索和更新；–定义•对数据进行索引的线性表；–分类•索引可以分为单级索引和多级索引•单级索引的图示（如下图）数据1数据2数据3数据4……数据n数据n-1数据1的地址数据1的Key值数据2的地址数据2的Key值…………数据n-1的地址数据n-1的Key值数据n的地址数据n的Key值原始数据：索引表：ITEducation&TrainingDate:5February20201.1线性表以及其应用（5）–使用索引表的好处•可以将一些非线性的问题转换为了线性问题加以解决•提高数据检索的效率•便于数据的更新ITEducation&TrainingDate:5February2020查找–查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素–关键字——是数据元素中某个数据项的值，它可以标识一个数据元素–查找方法评价•查找速度•占用存储空间多少•算法本身复杂程度•平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~个元素所需比较次数为找到表中第个元素的概率，为查找表中第其中：个记录的表，对含有icpipcpASLniniiiniii111ITEducation&TrainingDate:5February2020•顺序查找–查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较–算法描述Ch7_1.ci例01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个元素：n查找第i个元素：n+1-i查找失败：n+1ITEducation&TrainingDate:5February2020–顺序查找方法的ASL212)1(11111