Microsoft PowerPoint - DS_Ch2_EN [兼容模式]

Transcription

1 Data Structure Ch.2 Linear List Dr. He Emil Huang School of Computer Science and Technology Soochow University 苏州大学计算机科学与技术学院网络工程系 本章 ppt 与教材对应情况 本章涉及所有内容涵盖了教材以下章节 P212~P (List definition 表的定义 ) 6.2 (Implementation of Lists 表的实现 ) 6.5 (Linked Lists in Arrays 数组链表, 自学 ) huangh@suda.edu.cn Logical Structure of Linear List Linear List:a finite sequence composed of n (n 0) nodes, namely, a 1,, a n, 典型线性结构 Denoted by( 记作 ):L = (a 1, a 2,, a n ) Attribute( 属性 ): a i 只是一个抽象符号 Length number of nodes, denoted by n, L is an empty list ( 空表 ) when n=0 a i generally the same type head 开始结点, 表头 tail 终端结点, 表尾 Logical Structure of Linear List Logical Structure and Feature ( 逻辑结构 ) when L Ф, 1 Lhasone, and only one, start node a 1 and end node a n,a 1 has only one immediatesuccessor( 直接后继 ), a n has only one immediate predecessor ( 直接前驱 ); 2 interior node ( 内部结点 )a i (2 i n-1) has both one immediate predecessor a i-1 and one immediate successor a i+1 ; The logical relationship between nodes is determined by the position sequence, a i appears at the i-th position of list, which is linear ( 线性的 ), sol is called Linear List ( 线性表 ) Logical Structure of Linear List Examples: English Alphabet (A, B,, Z) Numbers of Playing Cards (2, 3,, 10, J, Q, K, A) Student Grade Sheet ( 学生成绩表 ) DEPT={ 通信, 计算机, 自动化, 城市轨道交通, etc. 2.1 Logical Structure of Linear List Basic Operations: InitList(L) ListLength(L) GetNode(L, i) etc., 从函数名我们基本能猜出函数的功能, 命名的重要性, 接下来很多功能基本相同的程序由于版本不同 ( 如同时列出了 C 版本实现,C++ 版本实现 ), 因此实现细节会有细微差别 a i ----abstract Symbol, which could be a structured object in practice ( 具体应用可能是一个结构类型对象 ); Linear List is flexible. Thelength of a linear list could be enlarged or shortened according to users various demands. 5 Complex functions could be implemented from the basic operations. ( 许多复杂的函数功能可以通过基本操作实现 ) 6 1

2 Ch.2 Linear List The ADT Definition of a Linear List ADT List{ // 线性表的 ADT 表示 Data Object:D = { a i a i ElemSet, i=1,2,,n, n 0 Data Relation:R = {<a i-1, a i > a i-1, a i D, i=2,3,,n Basic Operations: InitList (&L) Result: Construct an empty linear list L; ListEmpty (L) Initial Conditions: The linear list L is NOT null; Result: Return TRUE, if L is empty, or FALSE, otherwise. Ch.2 Linear List. GetElem ( L, i, &e ) Initial Conditions: The linear list L is NOT null; 1 i ListLength (L); Result: Assign e the value of the i-th element in L, then return. ListInsert ( L, i, &e ) Initial Conditions: The linear list L is NOT null; 1 i ListLength (L); Result: Insert e as the i-th element of linear list L; // 此处省略诸多线性表 ADT 运算 ADT List Ch.2 Linear List ( 课本 6.1 节表的定义, P213) A list of elements of type T is a finite sequence of elements of T together with the following operations: Construct the list, leaving it empty ( 构建空线性表 ) Determine whether the list is empty or not ( 判空 ) Determine whether the list is full or not ( 判满 ) Find the size of the list ( 返回线性表长度 ) Clear the list to make it empty ( 清空表 ) Insert an entry at a specified position of the list ( 指定位置插入 ) Remove an entry from a specified position in the list. ( 指定位置删除 ) Retrieve an entry from a specified position in the list. ( 检索表中指定位置元素 ) Replace the entry at a specified position in the list. ( 替换表中指定位置的元素 ) Traverse the list, performing a given operation on each entry. ( 遍历表, 对表中每个元素执行给定操作 ) Ch2. Linear List Definition Recall Some Important Concepts ADT (Abstract Data Type) STL (Standard Template Library, C++ 标准模板库 P213) STL 是 C++ 标准库的一部分, 标准库包含了各类函数和类的实现, 它为许多数据结构提供了方便的实现, 数据结构课程介绍的结构几乎全部在 STL 模板类中均有实现 STL classes list and vector, 其中 vector 模板类与下面介绍的 List ADT 类似 ( 如遗忘或未学习过, 请同学们课下务必自学或复习巩固 ) Method Specifications (P214) 构造函数, 创建 list 并将其初始化为空 删除所有的 list 元素 Ch2. Linear List Definition Method Specifications 根据 list 是否为空, 返回 true or false 根据 list 是否为满, 返回 true or false 将 x 插入到 List 中的 position 位置 ; 注意位置是从 0 开始还是从 1 开始 ; Error_code (P58 & P679): enum 类型, 类的方法应该通过错误诊断代码指明问题 ; 返回 list 中元素个数 我们的课本是通过 Error_code 枚举类型报告所有来自程序和函数的错误 ; 如 :TRUE,FALSE,range error 等 注 :entry 有记录的涵义, 故课本中的 entry 这么理解就容易懂了! 2

3 删除 position 位置上的元素, 参数 x 记录 List 中原先 position 位置处元素的副本 将 position 位置上的元素复制到 x 中, 所有 List 中原先元素保持不变 类成员函数后加 const: 表示在这个成员函数里不会修改类的成员变量的值, 从安全性角度出发 (P215) 另外,const 成员函数在执行的时候不能调用非 const 成员函数 在线性表的每个元素上执行函数 *visit 指定的动作 用 x 替换 position 位置上的元素, 所有 List 中原先元素保持不变, 若失败返回 Error_code; 类成员函数形参加 const: 当参数为引用时, 如果不希望引用类型的形参在被调用的函数内部被修改, 就可以使用 const 修饰符修饰引用参数 ( 你们 C++ 教材 P198) 在 C++ 中不带任何圆括号的函数名字被看作指向函数的指针 ( 函数指针 ), 在 List 类的成员方法 traverse 的形参 visit( 注 :visit 外面的括号是为了编译时不出现误解 ) 必须被声明为一个指向函数的指针 函数 *visit 拥有一个 List_entry 类型的引用参数和 void 返回类型 ; 使用 : 假设 print 函数作用为打印元素值, 那么我们声明一个 List 对象 the_list ( 声明语句 :List the_list; the_list 为一个类对象 ) 调用语句 the_list.traverse(print) 即可 ; 好处 : 通用性更强 2.2 The Sequential Linear List The Sequential Linear List ( 顺序表, or contiguous( 临近 ) list) P219 contiguous Definition: The elements of a Sequential Linear List are stored in a contiguous set of memory ( 一组地址连续的存储单元 ), in their logical order. Address Computation: Assume the size of each element is l units, the address of the i-th elements is Loc(a i ) = Loc(a 1 ) + (i-1) * l Sizeof(Element) Sequential Linear List Features ( 顺序表特点 ): 1 Randomized access ( 随机存取 ); 2 顺序表无需额外的空间来存储其逻辑关系, 但是因为空闲区的大小难以估计, 有可能造成空间的浪费 ; 3 The memories could be allocated statically (implemented with an vector) or dynamically (result in lots of copying operations while expanding an existed linear list). Base Address ( 基地址 ) of the sequential List L

4 2.2.1 Sequential Linear List Implementation:With 1-D Array(Vector) 顺序表的 C 语言结构代码 #define ListSize 100; // 假定顺序表最大存储量 typedef int DataType; // 依具体使用来定 typedef struct { DataType data[listsize]; // 存放结点 int length; // 当前表长 n Seqlist; Seqlist:Sequential List 顺序表 19 Class Template ( 类模板 P217~P218) Define format ( 类模板形式定义 ) template <class Entry_type_param( 元素类型 )> class List{ //Add in member information for the class ; Usage way ( 如何使用自己定义的类模板 ) List <real_type( 真实类型 )> list_obj; example: List <int> first_list; 定义一个整型数据构成的线性表对象 List<char> second_list; 定义了一个字符构成的线性表对象 Contiguous Implementation ( 课本版本 ) Sequential List template definition (P219 in text book) class SeqList{ List ( ); // 构造函数类模板中使用泛化元素类型,list_entry 就 int size ( ) const; 是泛化类型 可以通过 typedef 进行定义 e.g. typedef int List_entry bool full ( ) const; bool empty ( ) const; void clear ( ); void traverse(void (*visit)(list_entry& )); Error_code retrive(int position,list_entry& x) const; Error_code replace(int position, const List_entry& x); Error_code remove(int position, List_entry& x); Error_code insert(int position, const List_entry& x); private: // 私有成员数据 int count; List_entry entry[max_list]; // 所谓 contiguous 是指采用数组方式存储 ; 顺序表 (SeqList) 类的定义 (C++ 版本 ) #include <iostream.h> // 定义在 SeqList.h 中 #include <stdlib.h> #include "LinearList.h" const int defaultsize = 100; // 类型参数 T class SeqList: public LinearList<T> { //SeqList 继承了 LinearList 线性表抽象基类 protected: // 以下属性封装在类的私有域中 T *data; // 声明存储空间基地址, 存放数组 int maxsize; // 最大可容纳表项的项数 int n; // 当前已存表项数 void resize(int newsize); // 改变数组空间大小 22 public: SeqList(int sz = defaultsize); // 构造函数 SeqList(SeqList<T>& L); // 复制构造函数 ~SeqList( ) {delete[ ] data; // 析构函数 int Size( ) const {return maxsize; // 求表最大容量 int Length( ) const {return n; // 计算表长度 int Search(T& x) const; // 搜索 x 在表中位置, 函数返回表项序号 int Locate(int i) const; // 定位第 i 个表项, 函数返回表项序号 bool Insert(int i, T& x); // 插入 bool Remove(int i, T& x); // 删除第 i 个表项, 用 x 返回 SeqList 类的构造函数 : SeqList<T>::SeqList(int sz){ // 通过指定参数 sz 定义数组长度, 即 ListSize if(sz>0){ maxsize=sz; n=0; //n: 当前已存表项数 data=new T[maxSize]; // 存储空间基地址 if(data==null) { cerr<< 存储分配错误 <<endl; exit(1); // 程序结束返回 1 给系统 ;

5 SeqList<T>::SeqList(SeqList<T>& L){ // 用参数表中给出的已有顺序表初始化新建顺序表 maxsize=l.size(); n=l.length(); T value; data=new T[maxSize]; if(data==null) { 拷贝构造函数用一个对象值初始化一个新构造的对象 cerr<< 存储分配错误! <<endl; exit(1); for(int i=1; i<=n;i++) {L.getData(i,value); data[i-1]=value; Basic Operations in SeqList 1. Insert Basic Ideas: 请同学注意课本的合法 position 从 0 开始 Insert x in the i-th position of L (1 i n+1) : x (a 1,, a i-1, a i, a i+1,, a n ) (a 1,, a i-1, x, a i,, a n+1 ) To keep the order both physically and logically, we should: 1Move down a n,, a i for 1 position, free the i-th position; 2Insert x; 3Increase the length of linear list with Basic Operations in SeqList Algorithms (C version): void InsertList(SeqList *L, DataType x, int i){ int j; // 注意数组 1-st 位置的下标为 0. a i 的位置是 data[i-1]. if (i<1 i>l->length+1) //1 i n+1 是合法插入位置 Error( Position error! ); if (L->length >= ListSize) Error ( Overflow ); // 溢出 for (j = L->length-1; j>=i-1; j--) L->data[j+1] = L->data[j]; // 结点后移 L->data[i-1] = x; // 插入 x L->length++; // 长度加 Basic Operations in SeqList Algorithms: bool SeqList<T>::Insert (int i, T& x) { // 将新元素 x 插入到表中第 i(1 i n+1) 个表项位置 // 函数返回插入成功的信息 if (n == maxsize) return false; // 表满 if (i < 1 i > n+1) return false; // 参数 i 不合理 for (int j = n; j >= i; j--) // 依次后移 data[j] = data[j-1]; data[i-1] = x; // 插入 ( 第 i 表项在 data[i-1] 处 ) n++; return true; // 插入成功 ; ; Basic Operations in SeqList Analysis: 循环后移, 移动节点数为 n-i+1, 时间与 相关 1 Best Conditions: 当 i=n+1, 不移动 O(1) 常数时间解释 O(n 0 ) 与 n 无关 2 Worst Conditions: 当 i=1, 全部后移 O(n) 3 Average Conditions: 设任何合法位置上插入的概率相等 : ( 位置 i 插入的概率 ) 当位置 i 确定时, 后移次数亦确定 :n-i+1. 故表中平均移动结点为 : 即插入时, 平均移动表中一半结点 29 课本程序供大家课后进一步深入体会 (P220) Error_code List<List_entry>::insert(int position, const List_entry& x){ if (full()) return overflow; // 溢出 if (position<0 position>count) return range_over; // 插入点错误 for (int i=count-1;i>=position; i--) entry[i+1]=entry[i]; // 移动元素 ( 从后向前 ) entry[position]=x; // 放入元素 count++; // 增加统计个数 return success; 课本 P219 SeqList 类声明 // 加上图示算法分析 : 最好情况下没有元素移动, 最坏情形下移动元素 n 个, 平均情况下元素移动的个数为 n/2, 即与 n 成正比 T(n)=O(n) 5

6 L.Insert (4, 66) i position i i i count Basic Operations in SeqList 2. Delete Basic Idea: Delete the i-th elements in L (1 i n) (a 1,, a i-1, a i, a i+1,, a n ) (a 1,, a i-1, a i+1,, a n-1 ) for (int i=count-1;i>=position; i--) entry[i+1]=entry[i]; // 移动元素 ( 从后向前 ) entry[position]=x; // 放入元素 为保持物理与逻辑顺序一致, 须 : 1 前移 : 将 a i+1,, a n 依次前移 1 位, 填补删除 a i 留下的空间 ; 2 Decrease the list length by Basic Operations in SeqList Algorithms (C version) : void DeleteList(SeqList *L, int i){ int j, n=l->length; if (i<1 i>n) Error( Position error! ); // 非法位置 for (j = i; j<=n-1; j++) L->data[j-1] = L->data[j]; // 结点前移 L->length--; // 长度减 1 ; Basic Operations in SeqList Algorithms: bool SeqList<T>::Remove (int i, T& x) { // 从表中删除第 i(1 i n) 个表项, 通过引用型参 // 数 x 返回被删元素 函数返回删除成功信息 if (n == 0) return false; // 表空 if (i < 1 i > n) return false; // 参数 i 不合理 x = data[i-1]; for (int j = i; j <= n-1; j++) // 依次前移, 填补 data[j-1] = data[j]; n--; return true; ; Basic Operations in SeqList Analysis: 前移次数与 n 和 i 相关, 移动节点数 n-i 1 Best Conditions: 当 i=n, 不移动 O(1) 2 Worst Conditions: 当 i=1, 前移 n-1 次 O(n) 3 Average Conditions: 课本程序供大家课后进一步深入体会 Error_code List<List_entry> :: remove(int position, List_entry &x) { if (count == 0) return underflow; if (position < 0 position >= count) return range_error; x = entry[position]; count--; while (position < count-1) { entry[position] = entry[position + 1]; position++; return success; 35 6

7 L.remove( 4, e) p 56 p 87 p count-1 while (position < count-1) { entry[position] = entry[position + 1]; position++; p Error_code List<List_entry> :: retrieve(int position, List_entry &x) const // 如果 position 值非法, 返回出错信息, 否则根据 position 的值, 取得表中的第 position 个元素, 并由 x 返回 { if (position < 0 position >= count) return range_error; x = entry[position]; return success; 在顺序结构中, 元素的获取是随机得到的, 只要根据数组下标就可以计算出该元素的存储位置, 顺序存储结构的特征是随机存取 void List<List_entry>::traverse(void (*visit) (List_entry&)) { for (int i=0;i<count;i++) (*visit)(entry[i]); // 此处,visit 函数表示指定的遍历时对每个表元素执行的具体动作, 课本 P Linear Linked List ( 链表 ) Contiguous Implementation Properties Disadvantages: 移动节点, 不利于动态插入和删除 Advantages: 随机存取, 得到第 i 个结点的时间为 O(1) 与表长和位置无关 ( 单链表, a.k.a Linear Linked List) Storage Strategy: 用一组任意存储单元来存放结点 ( 可连续, 亦可不连续 ); 为表示逻辑关系, 须存储后继或前驱信息课本 P221,6.2.3 Simply Linked Implementation 40 Storage Structure of Node (a i ) Data Field Pointer Field (Link Field, 链域 ) next field points to the address of subsequent nodes Expression 1 开始结点无前驱, 用头指针表示 2 终端结点无后继,next 域为空 (NULL, 在 Logical Status One head pointer represents one linked list. 链表由头指针唯一确定 Storage Status Figure 6.1 in textbook (P222) Features 1 顺序存取 ( 回忆之前的顺序表是 存取??) 2 用指针表示结点间逻辑关系 3 动态分配, 表长易扩充 <iostream.h> 中被定义为数值 0) 7

8 Implementations (C version): typedef struct node{ // 结点类型定义 DataType data; // 数据域 单链表 C 语言结构声明 struct node *next; // 指针域 课下自己阅读 ListNode; typedef ListNode *LinkList; // 链表类型定义 ListNode *p; // 结点定义 LinkList head; // 链表头指针定义, 也可以表示 ListNode *head; 43 Implementations (C++ version): 链表类和链表结点类定义 ( 嵌套方式 ) class List { //List 类定义, 嵌套方式 private: class ListNode { // 嵌套链表结点 ListNode 类 public: int data; ListNode *next; ; ListNode *first; // 表头指针, first 即 C 版本中的 head public: // 链表操作 ; 44 链表类和链表结点类定义 ( 继承方式, 基类和派生类 ) class ListNode { // 链表结点类 protected: int data; ListNode 类声明为基类,List 类 ListNode * next; 声明为派生类,List 类继承 ListNode 类数据成员和成员函数 ; class List : public class ListNode { // 链表类, 继承链表结点类的数据和操作 private: ListNode *first; // 表头指针, first 即 C 版本中的 head public: // 链表操作 head 也好,first 也好, 但是从字面直接就能理解为头指针! 45 链表类和链表结点类定义 ( 结构方式 ) struct ListNode { // 链表结点类 int data; ListNode * next; ; class List { // 链表类, 直接使用链表结点类的数据和操作 private: ListNode *first; // 表头指针, first 即 C 版本中的 head ; 优势 : 尽管用 struct 结构体方式声明的 ListNode 类使得该类失去了封装性, 但简化了描述! 46 链表类和链表结点类定义 ( 复合方式 ) class List; // 复合方式 class ListNode { // 链表结点类 friend class List; // 链表类为其友元类 private: int data; // 结点数据, 整型 ListNode * next; // 结点指针 ; class List { // 链表类 private: ListNode *first ; // 表头指针 ; 47 链表类和链表结点类定义 ( 类模板定义 ) // 构建模板类, 模板类型参数 T 代表结点的数据类型 struct ListNode { // 链表结点类的定义 T data; //data 为 T 类型的结点数据域 ListNode<T> *next; // 链指针域 ListNode(ListNode<T> *ptr = NULL) { next = ptr; // 仅初始化指针成员的构造函数 ListNode(T item, ListNode<T> *ptr = NULL) { data = item; next = ptr; // 初始化数据与指针成员的构造函数 ; 链表结点类 ( 结构体模板 ) 定义 48 8

9 class List : public LinearList<T> { // 单链表类定义, 不用继承也可实现 protected: ListNode<T> *first; // 表头指针 public: List ( ) { first = new ListNode<T>; // 构造函数 List (const T& x) { first = new ListNode<T>(x); List ( List<T>& L); // 拷贝构造函数 ~List ( ){makeempty( ) ; // 析构函数 void makeempty( ); // 将链表置为空表 int Length ( ) const; // 计算链表的长度 49 ListNode<T> *Search(T x); // 搜索含 x 元素 ListNode<T> *Locate(int i); // 定位第 i 个元素 T *getdata(int i); // 取出第 i 元素值 void setdata(int i, T& x); // 更新第 i 元素值 bool Insert (int i, T& x); // 在第 i 元素后插入 bool Remove(int i, T& x); // 删除第 i 个元素 bool IsEmpty() const ; // 判表空否在这里引入头结点 { return first->next == NULL? true : false; ListNode<T> *getfirst() const { return first; void setfirst(listnode<t> *f ) { first = f; void Sort(); // 排序 ; 50 Declarations Node template: 链表结点类定义课本 P221 template <class Node_entry> struct Node{ Node_entry entry; // 数据域 Node<Node_entry> *next; // 指针域 Node ( ); Node (Node_entry, Node<Node_entry>* link=null); // 此处提供了两个构造函数, 彼此间是函数的重载关系 ; head List template class List{ public: List(const List<List_entry>& copy); // 拷贝构造函数 ~List(); // 析构函数 void operator=(const List<List_entry>& copy); // 赋值运算符号的重载 // 声明 ADT 中定义的 insert remove 等 protected: int count; // 结点数量 Node <List_entry> *head; // 单链表的头指针 Node <List_entry> * set_position(int position) const; // 获得第 position 个结点的位置 返回指针 ; List Node & Pointer 结点变量与指针变量 Pointer p:the address of a node Node Variable *p:the content of a node Dynamic Allocation,Garbage Collection 1. Create Singly Linked List (1) Insert from HEAD: 从空表开始, 重复读入数据 : 申请新结点 插入表头, 直至输入结束 ; 表次序与输入次序相反 ; 处理自然简单

10 前 ( 头 ) 插法建立单链表 void List<T>:: inputfront (T endtag, List<T>& L) { ListNode<T> *newnode, *newf; T val; cin >> val; L.setFirst(newF); while (val!= endtag) { if (L.isEmpty()){ // 如果链表为空, 则用 val 创建初始链表 newf = new ListNode<T>(val); cin>>val; continue; newnode = new ListNode<T>(val); newnode->next = newf; // 插在表前端 newf = newnode; cin >> val; 55 (2)Insert from TAIL: 设为指针 r 指向当前链尾 ( 初值为 NULL) 1 申请新结点 s 2 将读入数据写入 3 新结点链到表尾 ( 应注意边界条件 ) 4 修改尾指针 r 56 为简便起见, 设结点数据类型 DataType 为 char, 输入字符, 换行符结束 LinkList CreateList(void){ //ch, head, r 为局部量 head = r = NULL; // 开始为空表 while ((ch = getchar())!= \n ){ // 输入流中读取字符 s = (ListNode*)malloc(sizeof(ListNode)); // 1 s->data = ch; // 2 if (head == NULL) // 插入空表 head = s; // 新结点插入空表 ( 边界 ),r 为空 else 57 else r->next = s; // 3 r = s; // 4 if (r!= NULL) r->next = NULL; // 非空表, 终端结点指针为空无后继 return head; 边界条件处理 : 空表和非空表处理不一致简化方法 : 引入头结点 ( 哨兵 ), 其中 data 域可做它用 ( 如表长 58 度 ) 尾插法建立单链表 void inputfront (T endtag, List<T>& L) { ListNode<T> *newnode, *last; T val; cin >> val; L.setFirst(last); while (val!= endtag) { if (L.isEmpty()){ // 如果链表为空, 则用 val 创建初始链表 last = new ListNode<T>(val); cin>>val; continue; newnode = new ListNode<T>(val); last->next = newnode; // 插在表后端 last = newnode; cin >> val; 59 dummy node LinkList CreateList(void){ // 用尾插法建立带头结点的单链表 char ch; LinkList head = (Linklist)malloc(sizeof(ListNode)); ListNode *s, *r; r = head; // 尾指针初始指向头结点 while ((ch=getchar( ))!= \n ) { s = (ListNode*)malloc(sizeof(ListNode)); s->data = ch; // 生成头结点 60 10

11 r->next = s; r = s; r->next = NULL; // 终端结点指针置空, 或空表时头结点指针置空 return head; Note: 为简化起见, 申请结点时不判断是否申请到 Time Complexity: O(n) 61 带头结点的头插法建立单链表 void inputfront (T endtag, List<T>& L) { ListNode<T> *newnode, *newf; T val; newf = new ListNode<T>; L.setFirst (newf); //first->next 默认值为 NULL cin >> val; while (val!= endtag) { newnode = new ListNode<T>(val); newnode->next = newf->next; // 插在表前端 newf->next = newnode; cin >> val; 62 带头结点的尾插法建立单链表 void inputrear ( T endtag, List<T>& L ) { ListNode<T> *newnode, *last; T val; last = new ListNode<T>; // 建立链表的头结 L.setFirst(last); // 为链表 L 的 first 赋值 cin >> val; while ( val!= endtag ) { //last 指向当前的表尾 newnode = new ListNode<T>(val); last->next = newnode; last = newnode; cin >> val; // 插入到表末端 头结点 : 在单链表的开始结点之前附设一个类型相同的结点, 称之为 头结点 头结点的作用 : 1 方便单链表的特殊操作 插入在表头或者删除第一个结点, 这样保持了单链表操作的统一性, 减少程序复杂性和出现 bug 的机会 ; 处理不带头结点的链表时, 需要对开始结点和中间结点分别处理 2 形参声明 不带头结点的单链表在进行 头插法 时需改变头指针的值, 在 C 语言的函数形参中头指针一般使用指针的指针 ; 而带头结点的单链表不需改变头指针的值 last->next = NULL; // 表收尾 由于开始结点的位置被存放在 的指针域中, 所以在链表第一个位置上的操作与在表其他位置上的操作, 无需特殊处理 ; 2 无论链表 Linklist 是否为空, 头指针是指向头结点的非空指针, 空白与非空表的处理 Search 1 Search with VALUE Find the list node with value k 2 Search with INDEX 合法位置 1 i n. 头结点可看作第 0 个结点 返回第 i 个结点的地址, 即找到第 i-1 个结点, 返回其 next 域 Basic ideas: 顺链扫描 :p---- 当前扫描到的结点, 初始指向头结点 j---- 计数器 累加扫描到的结点, 初始值为 0 每次加 1, 直至 j=i 为止,p 指向 i-th 结点 66 Algorithms: 11

12 ListNode *GetNode(LinkList head, int i){ // 在链表 ( 有头结点 ) 中查找 ith 结点找到 (0 i n) 则返回该结点的存储 // 位置, 否则返回 NULL int j; ListNode *p; p = head; j = 0; // 头结点开始扫描 while (p->next && j<i) {// 顺链扫描, 至 p->next 为空或 j=i 为止 p = p->next; j++; if (i == j) return p; // 找到 else return NULL; // 当 i<0 或 i>n 时未找到 我们给出的版本是带头结点的 C 版本程序 C++ 版本请见课本 P223 Finding a list position 确认是否有头结点 Time Complexity Analysis 循环终止条件是搜索到表尾或 j=i 复杂度最多为 i, 与查找位置相关 67 //i=0, 找头结点 ListNode<T> * List<T>::Search(T x) { // 在表中搜索含数据 x 的结点, 搜索成功时函数返 // 该结点地址 ; 否则返回 NULL ListNode<T> *current = first->next; while ( current!= NULL && current->data!= x ) current = current->next; // 沿着链找含 x 结点 return current; ; Insert Question: 将值为 x 的结点插到表的第 i 个结点位置上 即在 a i-1 和 a i 之间插入 故须找到第 a i-1 个结点的地址 p, 然后生成新结点 *s, 将其链到 a i-1 之后,a i 之前 69 void InsertList (LinkList head, DataType x, int i) { // 带头结点 1 i n+1 ListNode *p; p = GetNode(head, i-1); // 寻找第 i-1 个结点 1 if (p== NULL) // i<1 或 i>n+1 时插入位置 i 有错 Error("position error"); s = (ListNode *)malloc(sizeof (ListNode)); //2 s->data=x; //3 s->next=p->next; //4 p->next=s; //5 Consider: 若无头结点, 边界如何处理? Time Complexity: 主要是 GetNode O(n) 合法位置 1 i n+1 GetNode: 0 i n 70 bool List<T>::Insert (int i, T& x) { // 将新元素 x 插入在链表中第 i 个结点之后 ListNode<T> *current = Locate(i-1); if (current == NULL) return false; // 无插入位置 ListNode<T> *newnode = new ListNode<T>(x); // 创建新结点 if(newnode==null){cerr<< Error <<endl; exit(1); newnode->next = current->next; // 链入 current->next = newnode; return true; // 插入成功 ; 同时阅读课本 P224 insert 实现 Delete 删 ith 结点 首先找 a i

13 void DeleteList (LinkList head, int i){ // 合法位置是 1 i n p = GetNode (head, i-1); //1 if (!p!(p->next)) // i<1 或 i>n 时删除位置有错 Error("position error"); r = p->next; //2 令 r 指向被删结点 a i p->next = r->next; // 3 将 a i 从链上摘下 free(r); // 4 释放 a i 73 bool List<T>::Remove (int i, T& x ) { // 删除链表第 i 个元素, 通过引用参数 x 返回元素值 ListNode<T> *current = Locate(i-1); if ( current == NULL current->next == NULL) return false; // 删除不成功 ListNode<T> *del = current->next; current->next = del->next; x = del->data; delete del; return true; ; 74 Correctness Analysis 1 i<1 时,GetNode 中的参数 <0 此时返回 p 为空 2 i=n+1 时,GetNode 中参数 =n 返回终端结点, 此时 p->next 为空 3 i>n+1 时,GetNode 返回 p 为空 Time Complexity O(n) Conclusion: 链表上插入 删除操作无须移动结点, 仅需修改指针 Circular Linked List 首尾相接 : 不增加存储量, 只修改连接方式 Advantages: 从任一结点出发可访问到表中任一其它结点, 如找前驱 (O(n)) 遍历表的终止方式 : p 为空或 p->next 为空 p=head 或 p->next=head Circular Linked List(Singly) 仅设尾指针更方便 : 访问开始结点和终端结点的时间均为 O(1) 例如 : 合并两个单循环链表的时间为 O(1), 但用头指针表示时 : T(m,n)=O(max(m,n)) 或 O(min(m,n)) Doubly Linked List (Circular) 单链表只有后向链, 找一结点的后继时间为 O(1), 但找前驱费时, 若经常涉及找前驱和后继, 则可选双链表

14 2.3.3 Doubly Linked List Structure 对称结构 : 若 p 不空, 则 p->prior->next = p = p->next->prior Advantages: 1 找一结点前驱和找一结点后继同样方便 2 删 *p 本身和删 *p 的后继同样方便 Doubly Linked List (Circular) 例 1: 前插 例 2: 删 *p s->data=x; // 2 s->prior=p->prior; // 3 s->next=p; // 4 p->prior->next=s; // 5 p->prior=s; // 6 p->prior->next=p->next; p->next->prior=p->prior; free(p); Doubly Linked List Characteristic of simply linked List 1 Can access entry in forward order (by the pointer next ) 2 Accessing entry in backward order is difficult. Doubly Linked List (P227) Doubly Linked List (Circular) Doubly Linked List Node definition: ( 双向链表结点定义 ) template <class Node_entry> struct Node{ Node_entry entry; // 数据域 Node<Node_entry> *next; Node<Node_entry> *back; // 两个指针域分别指向后继和前驱 Node ( ); Node (Node_entry, Node<Node_entry>* link_back=null, Node<Node_entry>* link_next=null); ; 请注意课本中的双向链表与严蔚敏老师教材双循环链表结构不完全一致 Doubly Linked List(Circular) Doubly Linked List Definition of doubly-linked list class: class List{ public: //Add specification for methods of the list ADT //constructors and deconstructor protected: int count; // 双向链表结点数 mutable int current_position; mutable Node<List_entry>* current; // 注意 : 仅仅设置了指向 List 当前访问结点的指针 current void set_position(int position) const; ; important characteristic: current=current->next->back=current->back->next; Doubly Linked List(Circular) Doubly Linked List realization of some member functions set_position ( 设置位置 ) void List<List_entry>::set_position(int position) const{ if (current_position<=position) //current 指针后移 for ( ;current_position!=position;current_position++) current=current->next; // 利用循环进行后移 else for (;current_position!=position;current_position--) current=current->back; // 利用循环进行前移 与课本 P226 的 set_position 加以区分 14

15 We can move either direction through the List while keeping only one pointer, current, into the List. ( 只有 current 一个指针 ) We do not need pointers to the head or the tail of the List, since they can be found by tracing back or forth from any given node. ( 解释为何可以不需要头指针或尾指针 ) Doubly Linked List (Circular) Doubly Linked List Realization of some member functions: Insert( 插入结点 ) To find any position in the doubly linked list, we first decide whether to move forward or backward from the current position, and then we do a partial traversal of the list until we reach the desired position. ( 定位之前, 先确定是应该往前还是往后, 然后再作相应的移动 ) Doubly Linked List (Circular) Error_code List<List_entry>::insert(int position, const List_entry& x){ if (position<0 position>count) return range_error; Node<List_entry> *new_node,*following,*preceding; // 为插入做好准备工作, 包括 following 和 preceding if (position==0){ if (count==0) following=null; else{ set_position(0); following=current; preceding=null; Doubly Linked List (Circular) else{ set_position(position-1); preceding=current; following=preceding->next; // 新增结点, 并进行插入 new_node=new Node<List_entry>(x,preceding,following); if (new_node==null) return overflow; if (preceding!=null) preceding->next=new_node; if (following!=null) following->back=new_node; // 插入需要修改两个方向上的指针域 current=new_node; current_position=position; count++; return success; (6.5 Linked List in Arrays textbook) 上述链表是由指针实现的, 其中结点分配和回收是由系统实现的, 系统提供了 malloc 和 free 动态执行, 故称为动态链表 动态 ---- 程序执行时系统动态分配和回收 静态链表 ---- 先分配大空间作为备用结点空间 ( 即存储池 ) 用下标 ( 亦称游标 cursor) 模拟指针, 自定义分配和释放结点函数 1. 定义 #define nil 0 // 空指针 #define MaxSize 1000 // 可容纳的结点数 typedef struct { // 静态链表结构声明 DataType data; // 结点数据域 int next; node, NodePool[MaxSize]; typedef int StaticList;

16 2. 基本操作 ( 模拟动态链表 ) 1 初始化将整个表空间链成一个备用链表, 只做一次 void Initiate(NodePool space) { // 备用链表的头结点位置为 space[0] for (i=0; i<maxsize-1; i++) space[i].next = i+1; space[maxsize-1].next = nil; 2 分配结点在备用链表上申请一个结点, 返回非空 ( 不等于 0) 成功, 否则失败 int AllocNode(NodePool space) { i = space[0].next; // 取备用链表上开始结点, 位置为 i, 即 space 的第 i 个分量 if (i) // 开始结点非空 space[0].next = space[i].next; // 将开始结点从备用链表上摘下 return i; // 为 nil 时失效 释放结点 3. 一般操作 将释放结点收还到备用链表的头上 void FreeNode(NodePool space, int ptr) { // 将 ptr 所指结点回收到备用链表头结点之后 space[ptr].next = space[0].next; space[0].next = ptr; 93 1 插入 void Insert(NodePool space, StaticList L, DataType x, int i) { // 在带头结点的静态链表 L 的第 i 个结点 a i 之前插入新结点 x p = Locate(space, L, i-1); // 找 L 中 a i 的前驱 1 if (p == nil) Error( Position error! ); // 位置错 S = AllocNode(space); // 申请结点 2 if (s == nil) Error( Overflow ); // 申请失败, 空间不足判定 space[s].data = x; // 3 space[s].next = space[p].next; // 4 space[p].next = s; // 删除 void Delete(NodePool space, StaticList L, int i) { p = Locate(space, L, i-1); // 找 L 中 a i 的前驱 1 if (p == nil space[p].next == nil) Error( Position error! ); // 位置错 q = space[p].next; // q 指向被删结点 a i 2 space[p].next = space[q].next; // 将 a i 摘下 3 FreeNode(space, q); // 4 注意 : 链表头指针实际上整数, 即 space 的下标

17 97 98 Comparison of Implementations Contiguous storage is generally preferable when the size of the list is known when the program is written; when the entries are individually very small; when few insertions or deletions need to be made except at the end of the list; when random access is important Linked storage prove superior when the size of the list is not known in advance; when the entries are large; when flexibility is needed in inserting, deleting and rearranging the entries To choose among linked list implementations, consider: Which of the operations will actually be performed on the list and which of these are the most important?( 需要哪些操作, 那个最重要?) Is there locality of reference? That is, if one entry is accessed, is it likely that it will next be accessed again?( 引用是否有连续性 ) Are the entries processed in sequential order? If so, then it may be worthwhile to maintain the last-used position as part of the list structure.( 元素是否按顺序访问, 如果是, 则值得保留一个最近使用的位置 ) Is it necessary to move both directions through the list? If so,then doubly linked lists may prove advantageous.( 是否需要向两个方向操作? 如果是, 则用双向链表比较好 ) 思考 1. 为什么在单循环链表中设置尾指针比设置头指针更好? 2. 写一个算法将单链表中值重复的结点删除, 使所得的结果表中各结点值均不相同 17