线性表1-顺序表及单链表.ppt

链表中每个节点可以包含若干个数据域和指针域。 根据指针的数量和性质的不同，可以将链表分为以下类型: 按指针数量分类 按指针性质分类 单链表——只有一个指针域 多链表——有多个指针域（多为双向链表） 普通链表（非循环链表） 循环链表 链表的分类 1、定义：若链表中的每个节点只有一个指针域。 2、单链表的逻辑状态和物理状态 数据元素之间的相对关系是由链表中的指针域所指示的； 单链表中的节点之间由链建立起来的逻辑顺序必须和线性表中相应的数据元素的顺序相一致； 数据元素在内存中以任意次序存放。 单链表中必须指出第一个节点的存储地址，所以需要设立一个特殊的指针，称为头指针。整个链表的存取都是从头指针开始进行的。 单链表（线性链表） 例：设有线性表（ a1，a2，a3，a4，a5 ，a6 ），采用单链表进行存储，其物理状态如下图所示: 存储地址 数据域 指针域 21 a5 82 34 a2 45 45 a3 66 50 58 a1 34 66 a4 21 82 a6 NULL 87 58 first 单链表存储状态示例 单链表的逻辑结构示意图 链接（指针）域 数据域 a b c d e NULL first 链表中每个节点代表一个元素； 每个节点包含一个指针，指向下一个节点； 最后一个节点的指针域是NULL。 单链表类定义-节点类ChianNode（程序3-8） template class T class ChainNode { friend ChainT; private: T data; ChainNodeT *link; }; link data 单链表类定义-单链表类Chian（程序3-8） templateclass T class Chain { public: Chain( ) { first = 0; } ~Chain( ); bool IsEmpty( ) const {return first == 0;} int Length( ) const; bool Find(int k, T x) const; int Search(const T x) const; ChainT Delete(int k, T x); ChainT Insert(int k, const T x); void Output(ostream out) const; private: ChainNodeT *first; // 指向第一个节点的指针 }; 线性表的链表描述不需要指定表的最大长度。 补充：指针的基本操作实例 操作内容 执行操作的语句 执行前后 指针指向节点 指针指向后继 指针移动 指针改接 指针改接后继 p=q p=q-link p=p-link p-link=q p-link=q-link B C D p q E F q -操作1：删除表中所有节点（程序3-9） templateclass T ChainT::~Chain() { ChainNodeT *next; while (first) { next = first-link; delete first; first = next; } } 时间复杂度：Θ (n) -操作2：确定链表长度（程序3-10） templateclass T int ChainT::Length( ) const { // Return the number of elements in the chain. ChainNodeT *current = first; int len = 0; while (current) { len++; current = current-link; } return len; } 时间复杂度：Θ (n) -操作3：在链表中查找第k个元素（程序3-11） templateclass T bool ChainT::Find(int k, T x) const { // Set x to the kth element in the chain. // Return false if no kth; return true otherwise. if (k 1) return false; ChainNodeT *current = first;