四川大学数据结构第2章 线性表.pptVIP

数据结构与算法(C++版) 第2章 线性表 一、线性表基本操作 1. 顺序表的定义和特点 定义 ：将线性表中的元素相继存放在一个连续的存储空间中。 特点：可利用一维数组描述存储结构，采用线性表的顺序存储方式 2. 顺序表(SeqList)类模板的定义 // 顺序表类模板 template class ElemType class SqList { protected: // 顺序表实现的数据成员: int count; // 元素个数 int maxSize; // 顺序表最大元素个数 ElemType *elems; // 元素存储空间 // 辅助函数模板 bool Full() const; // 判断线性表是否已满 void Init(int size); // 初始化线性表 public: // 抽象数据类型方法声明及重载编译系统默认方法声明: SqList(int size = DEFAULT_SIZE);// 构造函数模板 virtual ~SqList(); // 析构函数模板 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); // 插入元素 SqList(const SqListelemType copy); // 复制构造函数模板 SqListelemType operator =(const SqListelemType copy); // 重载赋值运算符 }; 3. 顺序表辅助函数模板的实现 template class ElemType bool SqListElemType::Full() const // 操作结果：如线性表已满，则返回true，否则返回false { return count == maxSize; } 4. 顺序表部分操作的实现 template class ElemType SqListElemType::SqList(int size) // 操作结果：构造一个最大元素个数为size的空顺序表 { elems = NULL; // 未分配存储空间前,elems为空 Init(size); // 初始化线性表 } template class ElemType SqListElemType::~SqList() // 操作结果：销毁线性表 { delete []elems; // 释放存储空间 } 3. 单链表中的插入与删除 插入 newPtr = new NodeElemType(e, tmpPtr-next); tmpPtr-next = newPtr; 删除 nextPtr = tmpPtr-next; // nextPtr为tmpPtr的后继 tmpPtr-next = nextPtr-next;// 删除结点 delete nextPtr; // 释放被删结点 循环链表是单链表的变形。 循环链表最后一个结点的next指针不为 NULL，而是指向了表的前端。 为简化操作，在循环链表中往往加入表头结点。 循环链表的特点是：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。 2. 循环链表示例 4. 循环链表的应用——用循环链表求解约瑟夫问题 约瑟夫问题的提法 n 个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 例如 n = 8 m = 3 三、双向链表 (Doubly Linked List) 1. 双向链表的概念 双向链表是指在前驱和后继方向都能游历(遍历)的线性链表。 双向链表每个结点结构：