顺序表与链表-课件.ppt

1、自动化学院参考书籍VC+VC+工具使用1.1 1.1 数据结构基本概念1 1数据（数据（datadata）数据是指能够输入到计算机中，并被计算机识数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合别和处理的符号的集合。2 2数据元素（数据元素（data elementdata element）数据元素是组成数据的基本单位。数据元素是数据元素是组成数据的基本单位。数据元素是一个数据整体中相对独立的单位。但它还可以分一个数据整体中相对独立的单位。但它还可以分割成若干个具有不同属性的项（字段），故不是割成若干个具有不同属性的项（字段），故不是组成数据的最小单位组成数据的最小单位数据结构（数

2、据结构（data structuredata structure）这三个方面的关系为这三个方面的关系为：数据的逻辑结构独立于计算机，是数据本身所固数据的逻辑结构独立于计算机，是数据本身所固有的有的存贮结构是逻辑结构在计算机存贮器中的映像，存贮结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。必须依赖于计算机。运算是指所施加的一组操作总称。运算的定义直运算是指所施加的一组操作总称。运算的定义直接依赖于逻辑结构，但运算的实现必依赖于存贮接依赖于逻辑结构，但运算的实现必依赖于存贮结构。结构。数据结构基本类型数据结构基本类型 线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构

3、树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路、通信网络交通线路、通信网络数据结构中常用的存贮结构数据结构中常用的存贮结构(1)(1)顺序存贮顺序存贮所有元素存放在一片连续的存贮单元中，逻辑上所有元素存放在一片连续的存贮单元中，逻辑上相邻的元素存放到计算机内存仍然相邻。相邻的元素存放到计算机内存仍然相邻。(2)(2)链式存贮链式存贮所有元素存放在可以不连续的存贮单元中，元素所有元素存放在可以不连续的存贮单元中，元素之间的关系通过地址确定，逻辑上相邻的元素存之间的关系通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的。放到计算机内存后不一定是相邻的。(3

4、)(3)索引存贮（略）索引存贮（略）(4)(4)散列存贮（略）散列存贮（略）算法（算法（algorithmalgorithm）（1 1）输入：）输入：具有具有0 0个或多个输入的外界量（算法开始前个或多个输入的外界量（算法开始前的初始量）的初始量）（2 2）输出：）输出：至少产生一个输出，它们是算法执行完后的至少产生一个输出，它们是算法执行完后的结果。结果。（3 3）有穷性：）有穷性：每条指令的执行次数必须是有限的。每条指令的执行次数必须是有限的。（4 4）确定性：）确定性：每条指令的含义都必须明确，无二义性。每条指令的含义都必须明确，无二义性。（5 5）可行性：）可行性：每条指令的执行时间都

5、是有限的。每条指令的执行时间都是有限的。1 1.2.2 线性数据结构线性表的存储结构主要有顺序存储结构和链式存储结构两种。顺序表顺序表 采用顺序存储结构的线性表称为顺序表，它的数采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。相邻。假定元素假定元素a a1 1的物理地址是的物理地址是Loc(aLoc(a1 1)，每个元素占，每个元素占d d个存储单元，则第个存储单元，则第i i个元素的存储位置为个元素的存储位置为：Loc

6、(aLoc(ai i)=Loc(a)=Loc(a1 1)+(i-1)+(i-1)*d d length=n maxsize0 1 i-2 i-1 i n-1 a2ai-1aiai+1a1an顺序表的主要算法顺序表的主要算法（1 1）在表中第）在表中第 i i 个位置插入新元素个位置插入新元素x x 算法实现的主要步骤是：算法实现的主要步骤是：判断插入位置的合理性以及表是否已满。判断插入位置的合理性以及表是否已满。从最后一个元素开始依次向前，将每个从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第元素向后移动一个位置，直到第i i个元素为个元素为止。止。向空出的向空出的第第i i个位

7、置存入新元素个位置存入新元素x x。最后还要将线性表长度加一。最后还要将线性表长度加一。0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 x ai an-1 an 0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 ai ai+1 an 序号序号 内容内容 序号序号 内容内容 插入前插入前 插入后插入后 顺序表中插入元素前后状态顺序表中插入元素前后状态（2）在表中删除第i个元素 算法实现的主要步骤是：算法实现的主要步骤是：判断删除位置的合理性。判断删除位置的合理性。从第从第i+1i+1个元素开始，依次向后个元素开始，依次向后直到最后一个

8、元素为止，将每个元直到最后一个元素为止，将每个元素向前移动一个位置。这时第素向前移动一个位置。这时第i i个元个元素已经被覆盖删除。素已经被覆盖删除。最后还要将线性表长度减一。最后还要将线性表长度减一。0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 ai+1 an 0 1 2 i-2 i-1 i n maxsize a1 a2 a3 ai-1 ai ai+1 an 序号序号 内容内容 序号序号 内容内容 删除前删除前 删除后删除后 顺序表中删除元素前后状态顺序表中删除元素前后状态（3）在表中查找某个元素 下面是根据数据元素本身的值进行查询的下面是根据数据元素本身

9、的值进行查询的算法，算法，x x为需要查找的元素，算法返回元素的为需要查找的元素，算法返回元素的实际位置。实际位置。int Find(ElemType x)int Find(ElemType x)for(int i=0;ilength;i+)for(int i=0;ilength;i+)/查找成功，返回元素位置查找成功，返回元素位置 if(datai=x)return i+1;if(datai=x)return i+1;return 0;return 0;/查找失败，返回查找失败，返回 0 0 1 1.3 3 实验内容1、使用顺序表实现学生名册管理程序，名册中的每条记录包括学号、姓名、联系电话

10、等项。2、实现数字化菜单管理、学生名册的建立、记录的添加、查找、删除和显示等功能。线性链表的基本概念线性表的顺序存储存在以下几个方面的缺点：1、插入或者删除一个节点，需要涉及到大量元素的移动问题。2、容易出现上溢或者下溢现象，存储空间不易扩展。3、多个线性表共享存储空间时，存在存储问题。因此在涉及到元素大量移动变动的表中，不宜采用线性表结构。线性链表的基本概念链式存储结构：链式存储结构：每个节点有两部分组成：一个部分用存储数据元素，称为数据域；另外一部分存放指针，叫为指针域。链式存储中元素之间的前后件关系可以通过指针来标识。链式存储结构既可以用于顺序存储，也可以用于较复杂的非线性存储。线性链表

11、的基本概念 线性链表链式的存储结构线性链表的逻辑结构2.3.1 线性链表的基本概念线性链表例2.3.1 线性链表的基本概念相关操作首先定义一个线性链表类linked_Llist，具体如下：/文件名linked_Llist.h#include using namespace std;template /T为虚拟类型struct node T d;node*next;1.线性链表的插入线性链表的插入：在链式存储结构下的线性表中插入一个新元素。首先要给该元素分配一个新结点，以便用于存储该元素的值；然后将存放新元素值的结点链接到线性链表中指定的位置。此外，在插入时，对于空表或者在第一个结点之前插入必须

12、单独考虑。线性链表的插入运算线性链表的插入运算插入（三种情况）第一种情况：在第一个结点前插入第一种情况：在第一个结点前插入 p p-next-next=head;=head;head=p;head=p;（插入前）（插入前）（插入后）（插入后）xheadppxhead第二种情况：在链表中间插入第二种情况：在链表中间插入 p p-next-next=q=q-next-next;q q-next-next=p=p；x (插入前插入前)()(插入后插入后)pxqpq第三种情况：在链表末尾插入第三种情况：在链表末尾插入p-next=q-next;/p-next=null;p-next=q-next;/p

13、-next=null;q q-next-next=p=p；p (插入前插入前)()(插入后插入后)p qq2.线性链表的删除线性链表的删除：在链式存储结构下的线性表中删除包含指定元素的结点。首先要在线性链表中找到这个结点；然后将要删除结点的存储空间释放回系统。线性链表的删除运算删除前删除前删除后删除后ai-1xai+1qpqai-1ai+1xp=q-next-next;q-next=p-next;分析插入与删除算法需要考虑的两种特殊情况：在插入时，对于空表或者在第一个结点之前插入必须单独考虑；1.在删除时，对于空表及删除第一个结点必须单独考虑，并且还要考虑到链表中不存在被删除元素的情况。2.3

14、.3 循环链表对于线性单链表，其插入与删除操作虽然比较方便，但还存在一个问题：对于空表与对第一个结点的处理必须单独考虑，使得空表与非空表的运算不统一。解决方法：循环链表（Circular Linked List）。循环链表的两个特点在循环链表中增加了一表头结点，其数据域为任意或者根据需要来设置，指针域指向线性表的第一个元素的结点。循环链表的表头指针HEAD指向表头结点。循环链表中最后一个结点的指针域不是空，而是指向表头结点。即在循环链表中，所有结点的指针构造了一个环状链。图图2.28 循环链表的逻辑状态循环链表的逻辑状态循环链表与线性单链表的比较判断判断线性单链表线性单链表为空的条件：为空的条件：判断判断循环链表循环链表为空的条件：为空的条件：head=NULLhead-next=heada1a2an-1an.HEADa1a2an-1an.HEADHEAD循环链表循环链表表头结点表头结点首元结点首元结点线性单链表线性单链表实验要点设计接口函数链表成员插入函数 参数：插入位置；插入成员(结构体变量)；返回值：成功，失败链表成员删除函数 参数：删除位置；返回值：成功，失败查找成员函数(定义查询规则)参数：查询参数,学号、姓名、电话号码 返回值：位置内存申请与释放申请内存 (void*)malloc(int size)释放内存 void free(void*ptr)39谢谢！谢谢！