04_01_数据结构(压缩版)_01_V1

HuazhongUniv.ofSci.andTech.WuhanPolytechnicUniversity单片机原理与应用2020/1/16第4部分数据结构(压缩版)——1SCHOOLofELECTRICALandELECTRONICENG.学习内容和目标①数据结构的基本知识：指出方向②线性表的概念链表注意：①思维一定要开阔一些，多问为什么。②允许不用举手，并随时打断，向我提任何和课程相关的问题。2020/1/162本节学习目标SCHOOLofELECTRICALandELECTRONICENG.1.1引论当前看待程序和软件的主流观点：①程序=算法(处理问题的策略)+数据结构(问题的数学模型)②软件工程的观点：软件=程序+文档数据结构：由若干特性相同的数据元素构成的集合，且在集合上存在一种或多种关系。即数据的组织形式。2020/1/1631数据结构概述数学代数系统硬件计算机系统设计软件计算机程序设计数据结构编码理论数据类型数据表示数据运算数据结构数据存取①三个内容：逻辑结构、存储结构、基本操作（运算）②数据类型：一个值的集合和定义在这个值集上的一组操作。程序设计语言中对于给定变量的所有可能取值的集合。③抽象数据类型（ADT）SCHOOLofELECTRICALandELECTRONICENG.逻辑结构：S={D,R}；D表示数据元素的集合，R表示元素间关系的集合四种结构：集合、线表、树、图①R1={φ}②R2={a,b,b,c,c,d,d,e,e,f,f,g}③R3={a,b,a,c,a,d,b,e,b,f,c,g}④R4={a,e,b,c,c,a,e,f,f,g,c,f}2020/1/1641.1引论(续1)abcefgabcdefgabcdefgabcefg存储结构：数据元素的表示及元素之间关系的表示。顺序存储结构、链式存储结构基本操作及其实现：对数据元素的修改、增加、删除，移动等。SCHOOLofELECTRICALandELECTRONICENG.本课程的讲述特点、目标、和方法：①在同学们的原有基础上，对数据结构进行概括；②由于时间有限，并且是在单片机课程中，因此将挑选几个主要的数据结构；③采用压缩的方式讲述数据结构，关键在于给出思想和方法；④通过指导培养自学能力；⑤掌握几种数据结构的思想，并能够处理相关问题；2020/1/1651.2教学方法和目标SCHOOLofELECTRICALandELECTRONICENG.主要涉及的数据结构：算法：排序和查找（其他略）①有穷性---执行了有限条指令后一定要终止。②确定性（无二义）---③可（能）行性---④输入数据---⑤输出数据---2020/1/1661.3当前的数据结构表堆栈队列链表树二叉树图串SCHOOLofELECTRICALandELECTRONICENG.2.1概念和定义线性结构：①有且仅有一个头元素②有且仅有一个尾元素③除第一个数据元素外，其余的数据元素有且仅有一个直接前驱④除末尾数据元素外，其余的数据元素有且仅有一个直接后继线性表的概念：①线性表是n(n=0)个数据元素的有限序列。②记作：(a1,a2,a3,...ai,...,an),下标i表示数据元素在线性表中的位序。③n定义为线性表的长度；n为0表示该线性表为空表。④线性表中的数据元素可以是一个数、一个符号或由多个数据项所构成的。2020/1/1672线性表SCHOOLofELECTRICALandELECTRONICENG.线性表的抽象数据类型(ADT)定义：2020/1/1682.1线性表的概念和定义(续1)}0,,...,2,1,|{nniElemSetaaDii},...,2,1,,|,{11niDaaaaRiiiiADTlist{数据对象：数据关系：基本操作：InitList(&L)/*初始化线性表*/DestroyList(&L)/*销毁线性表*/ListEmpty(L)/*判断是否为空线性表*/......}SCHOOLofELECTRICALandELECTRONICENG.例：利用线性表求集合A∪B：集合A和B分别用线性表LA和LB表示依次扫描LB的元素，若不存在LA中，则插入LA中2020/1/1692.2线性表的示例voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb)for(i=1;i=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal)){ListInsert(La,++La_len,e);}}}SCHOOLofELECTRICALandELECTRONICENG.线性表的顺序表示－随机存取的存储结构①用一组连续的存储单元依次存储线性表中的数据元素。②表中第一个元素的起始位置称为顺序表的基地址。③线性表中任一数据元素的存储位置为(s表示每个数据元素所占存储空间大小。i表示数据元素的位序)：由于线性表的长度可变，因此对顺序表的定义除了需要一个存储元素的空间以外，还需要两个数据成员：其中一个指示顺序表中已有的元素个数length，另一个指示该顺序表允许存放的数据元素个数的最大值listsize。2020/1/16102.3顺序表siaLOCaLOCi)1()()(1a1a2a3ai-1ai……L.lengthL.listsizeSCHOOLofELECTRICALandELECTRONICENG.操作内容：①顺序表的初始化：固定长度和动态长度②顺序表的插入：③顺序表的删除：④顺序表的查找：顺序表的初始化：例如，分配一个预定义大小的一段连续单元，并将其初始长度设为02020/1/16112.4顺序表的操作intInitList_sq(Sqlist*L){L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L-slist)returnERROR;/*初始化失败，返回0*/L-length=0;/*置空表长度为0*/L-listsize=INIT_SIZE;/*置初始空间容量*/returnOK;/*初始化成功，返回1*/}/*InitList*/SCHOOLofELECTRICALandELECTRONICENG.顺序表的插入：在第i个元素之前插入一个新元素，此时因为逻辑结构发生了变化，相应的存储结构也随之变化，就需要调整顺序表中各元素的相对位置。插入算法的基本步骤：①判断插入位置是否超过了表的实际长度；②判断插入后，是否超过了表的实际空间，若发生溢出，则应先增加表的空间，再完成插入；③为插入的元素空出位置，将插入位置开始的元素依次向后移动，完成插入；④更新表的实际长度和实际空间大小。2020/1/16122.4顺序表的操作(续1)SCHOOLofELECTRICALandELECTRONICENG.顺序表的插入示例：2020/1/16132.4顺序表的操作(续2)/*在顺序表的第i个位置之前插入新元素e*/intListInsert_sq(Sqlist*L,inti,ElemTypee){intk;if(i1||iL-length+1)returnERROR;/*插入位置不合法*/if(L-length=L-listsize){/*存储空间满，重新分配空间*/L-slist=(ElemType*)realloc(L-slist,(INIT_SIZE+INCREM)*sizeof(ElemType));if(!L-slist)returnERROR;/*存储分配失败*/L-listsize+=INCREM;/*修改存储空间大小*/}for(k=L-length-1;k=i-1;k--){/*插入位置之后元素后移*/L-slist[k+1]=L-slist[k];}L-slist[i-1]=e;/*插入元素*/L-length++;/*顺序表长度加1*/returnOK;}/*ListInsert*/SCHOOLofELECTRICALandELECTRONICENG.顺序表的删除：删除表中第i个位置的元素。实现步骤：①判断i是否超过当前表的长度；②取出欲删除元素③将该位置后的元素依次向前移动一个位置；④修改当前表的长度2020/1/16142.4顺序表的操作(续3)/*在顺序表中删除第i个元素*/intListDelete_sq(Sqlist*L,inti){intk;if(i1||iL-length)returnERROR;/*删除位置不合法*/for(k=i-1;kL-length-1;k++)/*元素前移*/L-slist[k]=L-slist[k+1];L-length--;/*顺序表长度减1*/returnOK;}SCHOOLofELECTRICALandELECTRONICENG.顺序表的插入、删除算法分析：在顺序表中插入和删除元素，其时间耗费主要在元素的移动上。2020/1/16152.4顺序表的操作(续4)在第i个元素前插入一个新元素，移动元素次数为：n-i+111112)1(11)1(niniiisninninpE平均移动次数删除第i个元素，移动元素次数为：n-ininiidlninninqE1121)(1)(平均移动次数时间复杂度：O(n)SCHOOLofELECTRICALandELECTRONICENG.顺序表的查找：在顺序表中查找某个值等于给定值的元素位置。实现步骤：①从顺序表的起始位置开始依次比较；②若找到对应的元素，则返回该元素在表中的位置；③若找到表的末尾位置，还未找到，则返回失败标识。顺序表的特点：①简单直观，容易理解；②能够实现随机存取；③插入和删除需要移动大量的数据元素；④长度相对固定，易导致存储空间的浪费；2020/1/16162.4顺序表的操作(续5)SCHOOLofELECTRICALandELECTRONICENG.链表：采用一组任意的存储单元来存放线性表中的数据元素，这些存储单元可以是连续的，也可以是不连续的。数据元素间的逻辑关系通过附加信息－指针来描述。数据元素除了具有代表其本身信息的数据域外，还有一个用来指示逻辑关系的指针域。这样的存储方式称为结点。链表的实现主要使用结构体：2020/1/16172.5线性表的链式表示数据域data指针域next结点nodetypedefstructLNode{ElemTypedata；/*结点的数据域*/structLNode*next；/*结点的指针域*/}LNode,*Llist;若LNode*p，则p的含义是什么？若p的值非空，则表明p指向某个结点，p-data表示p所指结点中的数据域，p-next表示p所指结点中的指针域，若非空，则指向其后继结点。SCHOOLofELECTRICALandELECTRONICENG.线性链表是一种动态存储结构，当线性链表要增加一个结点时，向系统申请一个存储空间，删除结点时要将空间释放。单链表：结点中只有一个指针域2020/1/16182.5线性表的链式表示(续1)p=(LNode*)malloc(sizeof(LNode));free(p);不带头结点的单链表，头指针指向第一个数据元素带头结点的单链表，头指针指向头结点，头结点的数据域为空，指针域为第一个数据元素的地址不带头结点的单链表为空，则头指针为空，而带头结点的，则头结点的指针域为空SCHOOLofELECTRICALandELECTRONICENG.单向循环链表的特点：表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个