[初二英语]第02-2讲单链表.ppt

* * 授课者：章 英 E-mail：walking7876@ Essential of Lecture Two-Two ： 一、线性链表 二、单链表及其基本操作 三、单链表实战应用 难点 用一组任意的存储单元存储线性表的数据元素； 利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素； 每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息。 一、线性链表 ( Linked List ) 链式存储结构的特点： 数据域：元素本身信息 指针域：指示直接后继的存储位置 存储地址 1 7 13 19 25 31 37 43 43 13 1 NULL 37 19 25 7 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) 头指针 31 head 结点包括： ZHOU ZHENG ZHAO WU WANG SUN QIAN LI 指针域 数据域 例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG) ZHAO QIAN SUN LI ZHOU WU ZHENG WANG ^ H 逻辑上的示意图： 单链表定义：结点中只含一个指针域的链表叫线性链表。 结点如何实现？ (*p) 表示p所指向的结点 (*p).data 表示p指向结点的数据域 (*p).next 表示p指向结点的指针域 在单链表第一个结点前附设一个结点叫~ ~ 头结点指针域为空表示线性表为空 h a1 a2 头结点 an ^ …... h 空表 ^ 头结点： 实战： 1、单选 下面关于线性表的叙述中，错误的是（ ）。 A 顺序表必须占用一片地址连续的存储单元 B 链表不必占用一片地址连续的存储单元 C 顺序表可以随机存取任一元素 D 链表可以随机存取任一元素 类模板将类的数据成员和成员函数设计得更完整、更灵活。 类模板更易于复用。 在单链表的类模板定义中，增加了表头结点。 C++中链式结构的存储： template class ElemType struct Node { // 数据成员: ElemType data; // 数据域 NodeElemType *next; // 指针域 // 构造函数: Node(); // 无参数的构造函数 Node(ElemType item, NodeElemType *link = NULL);// 已知数据域和指针域建立结构 }; 结点类 参见文件夹S2_3里的文件node.h template class ElemType class SimpleLinkList { protected: // 链表实现的数据成员: NodeElemType *head; // 头结点指针 // 辅助函数 NodeElemType *GetElemPtr(int position) const; // 返回指向第position个结点的指针 void Init(); // 初始化线性表 简单线性链表类 参见文件夹S2_3里的文件simple_lk_list.h public: //抽象数据类型方法声明及重载编译系统默认方法声明: SimpleLinkList(); // 无参数构造函数 virtual ~SimpleLinkList(); // 析构函数 int Length() const; // 求线性表长度 bool Empty() const; // 判断线性表是否为空 void Clear(); // 将线性表清空 void Traverse(void (*Visit)(const ElemType )) const; // 遍历线性表 StatusCode GetElem(int position, ElemType e) const; // 求指定位置的元素 StatusCode SetElem(int position, const ElemType e); // 设置指定位置的元素值 StatusCode Delete(int position, ElemType e); // 删除元素 StatusCode Insert(int position, const ElemType e); // 插入元素 SimpleLinkList(const SimpleLinkListElemType copy); // 复制构造函数 SimpleLinkListElemType operator =(const