【数据结构课件】线性表.pptVIP

第二章 线性表 线性表的存储结构 操作线性表 应用线性表 2.1 线性表的特性 存在一个唯一的被称为“第一个”的数据元素 存在一个唯一的被称为“最后一个”的数据元素 除第一个外，集合中的每个元素均只有一个前驱和一个后继。 集合中的数据元素同属于一个数据对象 2.2 线性表的存储结构 线性表的链式存储结构（顺序表） 按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。 在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的 。 线性表的链式存储结构（链表） 用一组 任意的存储单元来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。链表中结点的逻辑次序和物理次序不一定相同 ，但必须能正确表示结点间的逻辑关系。 顺序表 顺序线性表结构的语言描述 顺序表使用内存中一组连续的存储空间，连续存放属于同一数据对象的多个数据元素 链表 链表结构的语言描述 单链表 带有头节点单链表 循环链表 双向循环链表 2.3 线性表的基本操作 构建空表 init ( ) 插入 insert ( ) 删除 delete ( ) 取值 getelem ( ) *计算机科学系 李长志 * An … A4 A2 A3 An-1 A5 A1 ElemType a[N]； ElemType *a； Typedef struct { ElemType elem; int length; int listsize; } SQlist ; length listsize elem 头指针：一个单链表由头指针的名字来命名。 线性单链表 ^ head Typedef struct node { ElemType data; struct node *next; } Lnode ; Lnode *head; //① ① Typedef struct node { int length; struct node *head; } LinkList ; Li Qian Sun Zhou Wu Zheng Wang ^ head 头指针：一个单链表由头指针的名字来命名。 含有头节点的线性链表 头节点 问题： 如何在顺序表（链表）中实现这些操作？ *计算机科学系 李长志