顺序表与链表-课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,软件技术基础,自动化学院,参考书籍,1,、数据结构概念及顺序表,VC+,工具使用,1.1,数据结构基本概念,1,数据（,data,）,数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合,。,2,数据元素（,data element,）,数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是组成数据的最小单位,数据结构（,data structure,）,是指相互之间存在一种或多种特定关系的数据元素所组成的集合。数据结构包含三个方面的内容，即数据的逻辑结构，数据的存贮结构和对数据所施加的运算,。,这三个方面的关系为,：,数据的逻辑结构独立于计算机，是数据本身所固有的,存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。,运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮结构。,数据结构基本类型,线性结构,通迅录、成绩单、花名册,树形结构,电子字典、家谱、目录,图状结构,交通线路、通信网络,数据结构中常用的存贮结构,(1),顺序存贮,所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。,(2),链式存贮,所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。,(3),索引存贮（略）,(4),散列存贮（略）,算法（,algorithm,）,通俗地讲，算法就是一种解题的方法。更严格地说，算法是由若干条指令组成的有穷序列，它必须满足下述条件（也称为算法的五大特性）：,（,1,）输入：,具有,0,个或多个输入的外界量（算法开始前的初始量）,（,2,）输出：,至少产生一个输出，它们是算法执行完后的结果。,（,3,）有穷性：,每条指令的执行次数必须是有限的。,（,4,）确定性：,每条指令的含义都必须明确，无二义性。,（,5,）可行性：,每条指令的执行时间都是有限的。,1,.2,线性数据结构,线性表是由有限个同类型的数据元素组成的有序序列，一般记作（,a,1,a,2,a,n,）。除了,a,1,和,a,n,之外，任意元素,a,i,都有一个直接前趋,a,i-1,和一个直接后继,a,i+1,。,a,1,无前趋，,a,n,无后继。,线性表的存储结构主要有顺序存储结构和链式存储结构两种。,顺序表,采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。,假定元素,a,1,的物理地址是,Loc(a,1,),，每个元素占,d,个存储单元，则第,i,个元素的存储位置为,：,Loc(a,i,)=Loc(a,1,)+(i-1)*d,length=n maxsize,0 1 i-2 i-1 i n-1,a,2,a,i-1,a,i,a,i+1,a,1,a,n,顺序表的主要算法,（,1,）在表中第,i,个位置插入新元素,x,算法实现的主要步骤是：,判断插入位置的合理性以及表是否已满。,从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第,i,个元素为止。,向空出的,第,i,个位置存入新元素,x,。,最后还要将线性表长度加一。,（,2,）在表中删除第,i,个元素,算法实现的主要步骤是：,判断删除位置的合理性。从第,i+1,个元素开始，依次向后直到最后一个元素为止，将每个元素向前移动一个位置。这时第,i,个元素已经被覆盖删除。,最后还要将线性表长度减一。,（,3,）在表中查找某个元素,下面是根据数据元素本身的值进行查询的算法，,x,为需要查找的元素，算法返回元素的实际位置。,int Find(ElemType x),for(int i=0;inext,=,head,;,head,=,p;,（插入前）（插入后）,x,head,p,p,x,head,第二种情况：在链表中间插入,p,-next,=q,-next,;,q,-next,=p,；,x,(,插入前,)(,插入后,),p,x,q,p,q,第三种情况：在链表末尾,插入,p-next=q-next,;/p-next=null;,q,-next,=,p,；,p,(,插入前,)(,插入后,),p,q,q,2.,线性链表的删除,线性链表的删除：,在链式存储结构下的线性表中删除包含指定元素的结点。,首先要在线性链表中找到这个结点；,然后将要删除结点的存储空间释放回系统。,线性链表的删除运算,删除前,删除后,a,i-1,x,a,i+1,q,p,q,a,i-1,a,i+1,x,p=q,-next,;,q-next=p-next;,分析,插入与删除算法需要考虑的,两种特殊情况,：,在插入时，对于,空表,或者在,第一个结点之前插入,必须单独考虑；,在删除时，对于,空表,及,删除第一个结点,必须单独考虑，并且还要考虑到,链表中不存在被删除元素,的情况。,2.3.3,循环链表,对于线性单链表，其插入与删除操作虽然比较方便，但还存在一个问题：对于,空表,与对,第一个结点,的处理必须单独考虑，使得,空表,与,非空表,的运算不统一,。,解决方法：,循环链表,（,Circular Linked List,）。,循环链表的两个特点,在循环链表中增加了一,表头结点,，其,数据域,为任意或者根据需要来设置，,指针域,指向线性表的第一个元素的结点。循环链表的,表头指针,HEAD,指向表头结点。,循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构造了一个,环状链,。,图,2.28,循环链表的逻辑状态,循环链表与线性单链表的比较,判断,线性单链表,为空的条件：,判断,循环链表,为空的条件：,head=NULL,head-next=head,a,1,a,2,a,n-1,a,n,.,HEAD,a,1,a,2,a,n-1,a,n,.,HEAD,HEAD,循环链表,表头结点,首元结点,线性单链表,实验要点,设计接口函数,链表成员插入函数,参数：插入位置；,插入成员,(,结构体变量,),；,返回值：成功，失败,链表成员删除函数,参数：删除位置；,返回值：成功，失败,查找成员函数,(,定义查询规则,),参数：查询参数,学号、姓名、电话号码,返回值：位置,内存申请与释放,申请内存,(void*)malloc(intsize),释放内存,void free(void*ptr),谢谢！,39,