五、链 表 1、单链表 2、双向链表 3、链表应用

1、单链表 链表的引入 为了解决数组的定长结构的局限性，用“链表”的结构实现一个顺序表。应该说明的是所谓的“链表”结构不仅能表示线性群体，也可以表示非线性群体，如树、图等等。 单链表及其变形是实现线性群体的形式。 单链表是一种最简单的链表，也叫线性链表。每个数据元素占用一个“结点”，每个结点至少要有2个信息：一个该数据元素，另一个反映出它与下一个结点的关联关系，即所谓“指针”，它给出下一个结点的开始存储地址。如下： 空表的标志：head = null 结点(头) 结点 结点(尾) data next → ↑ ≡ head currPtr(当前结点) rear null

单链表(结点定义) ADT Node is Data data // 保存信息 next // 指向下一个结点的指针 Operations Constructor NextNode // 返回下一个结点的地址 InsertAfter // 在当前结点后插入一个新结点，并把 // 新结点作为当前结点 DeleteAfter // 删除当前结点后的直接后继 end ADT Node

next = tempPtr->next; 单链表(结点封装的方法) InsertAfter 操作次序 P->next = next; next = p; DeleteAfter tempPtr = next; next = tempPtr->next; data next ↑ currPtr q 新结点p data next currPtr q tempPtr

单链表(链表的实现) 结点的声明 Template <class T> class Node { private: Node <T> *next; public: T data; Node(const T& item, Node<T> *next = Null); void InsertAfter(Node<T> *p); Node<T> *DeleteAfter(void); }; 例 Node<int> t(10) Node<char> *p, *q; q = new Node<char> (‘B’)’; p = new Node<char> (‘A’, q);

生成结点函数GetNode（初始数据值，指针值），返回新结点的指针。 插入头结点函数INSERTFRONT 单链表(构造链表) 生成结点函数GetNode（初始数据值，指针值），返回新结点的指针。 插入头结点函数INSERTFRONT void InsertFront(Node<T> *&head, T item) { head = GetNode(item, head); }; head head ≡ item item p item null

单链表(构造链表) 插入表尾结点函数INSERTREAR(被插入表的头指针, 初始数据值) 与被插入表的状态有关：如果是空表就转化为插入头结点的情况，如果是非空表，就先要确定表尾的位置。 currPtr 新结点 void InsertRear(Node<T> *&head, const T& item) { Node<T> *newNode, *currPtr = head; if (currPtr = = NULL) InsertFront(head, item); else { while (currPtr->next ! = NULL) currPtr = currPtr ->next ; newNode = GetNode(item); currPtr ->next = newNode; } ≡

例：生成一个数据元素为a 、b 、c 的单链表。 从头部插入生成 单链表(构造链表) 例：生成一个数据元素为a 、b 、c 的单链表。 从头部插入生成 从尾部插入生成 C NULL B C NULL A B C NULL A NULL A B NULL A B C NULL

单链表 单链表几种形式 head null head null tail head ※ 始终标记 head 始终标记 tail

几种单链表表空的判断条件 head = NULL head =NULL tail = NULL ≡ head = 标记结点指针 ※ head ≡ tail ≡

单链表(删除结点) 删除头结点 以简单单链表为例 要点：更新头指针。 next head × × head 删除头结点 以简单单链表为例 要点：更新头指针。 head × × head = head->next; void DeleteFront(Node<T> *& head) { // 保存被删除结点指针 Node<T> * P = head; // 确定该表非空 if (head ! = NULL) head = head->next; //将头指针指向原表的第二个结点 delete p; } next head

通用的删除算法：删除第1个与给定关键字匹配的结点。 单链表(删除结点) 通用的删除算法：删除第1个与给定关键字匹配的结点。 先要确定与给定关键字匹配的结点，还要确定该结点的前驱结点， 引入前驱指针prevPtr。 key prevPtr currPtr

关键：确定加入新结点的位置。办法：扫描链表并进行比较。 确定位置的条件： 例：按输入顺序65，60，82，74建立有序表。 按升序建立有序表。 关键：确定加入新结点的位置。办法：扫描链表并进行比较。 确定位置的条件： 例：按输入顺序65，60，82，74建立有序表。 空表直接用InsertFront 即可。 因为60<65，所以插在65前面，成为新的头结点。也可用InsertFront。 因为82≮60，继续扫描， 82≮65，此时已达表尾，因插入表尾。 65 null 65 null 60 60 65 null 82 null

建立有序表(续) 因为74≮60，继续扫描， 74≮65，继续扫描，74＜82，因此82是第1个data值大于给定关键字值的。说明74应插入在82的前面。而当前结点是82，所以还需要一个指针与当前结点指针同步移动，但始终指向当前结点的前驱。 60 65 82 null 74

建立有序表的算法 void InsertOrder(Node<T> *& head, T item) { Node<T> *currPtr, *prevPtr, *newNode; // currPtr, prevPtr, newNode prevPtr = NULL; currPtr = head; while(currPtr ! = NULL) // 遍历表并找到插入点 if (item< currPtr ->data) // 当item<当前结点数据值, 则找到插入点 break; prevPtr = currPtr; currPtr = cuurPtr->NextNode( ); } if (prevPtr = = NULL) InsertFront(head, team); else newNode = GetNode(item); prevPtr->InsertAfter(newNode);

用链表排序 利用有序表可以对数据元素排序，基本思想如下： 对n个元素的数组，逐个将数组元素插入到一个有序链表中，再遍历该链表，将排好序的元素拷贝回数组。 void LinkSort(T a[], int n) { Node<T> *ordlist = NULL, *currPtr; int i; for (i= 0; i<n; i+ + ） // 按序将元素从数组插入表中 InsertOrder(ordlist, a[i]); currPtr = ordlist; i = 0; while(currPtr ! = NULL) a[+ +] = currPtr->data; currPtr = currPtr->nextNode( ); ClearList(ordlist); }

类LinkedList LinkedList类的实现 data Front Rear prevPtr currPtr Position=2 Size = 4 data

复制表 // 把L拷贝到一初始为空的当前表中 Void LinkedList<T>∷CopyList(const LinkedList<T>& L) { Node<T> *p = L.front; //用指针p遍历表 while (p! =NULL) InsertRear(p->data); p = p->NextNode( ); } if (position = = -1) // 若为空表则返回 return; prevPtr = NULL; // 在新表中重新设置prevP和trcurrPtr currPtr = front; for (int pos = 0; pos! = position; pos + +) prevPtr = currPtr; currPtr = currPtr->NextNode( );

清空表 // 将当前表清空 void LinkedList<T>∷ClearList(void) { // 将当前表清空 void LinkedList<T>∷ClearList(void) { Node<T> *currPosition, *nextPosition; currPosition = front; while(currPosition ! = NULL) nextPosition = currPosition->NextNode( ); FreeNode(currPosition); currPosition = nextPosition; // 移至下一个结点 } front = rear = NULL; prevPtr =currPtr = NULL; size = 0; position = -1;

表遍历 // 将表的位置置到pos void LinkedList<T>∷Reset(int pos) { int StartPos; if (front = = NULL) //若表空，则返回 return; if (pos<0 ‖pos>size -1 ) // 若位置非法，退出程序 cerr<<“Reset: Invalid list position: “<< pos << endl; }

表遍历(续) // 遍历表设置pos点(接上页算法) if (pos = = 0) { prevPtr = NULL; currPtr = front; position = 0; } else // 重置 currPtr, prevPtr 和 position currPtr = front->NextNode( ); prevPtr = front; startPos = 1; for (position = startPos; position ! = pos; position+ +) { // 右移直到position = = pos prevPtr = currPtr; currPtr = currPtr->NextNode();

遍历函数 基本方法：prevPtr移到currptr // 将prevPtr和currPtr 指针右移一个结点 Void LinkedList<T>∷Next(void) { // 若已到表尾或表为空，返回 if (currPtr ! = NULL) // 将两个指针右移一个结点 prevPtr = currPtr; currPtr = currPtr->NextNode( ); position + +; }

表插入方法 往表的当前位置插入结点 Void LinkedList<T>∷InsertAt(const T& item) { Node<T> *newNode; if (prevPtr = = NULL) { // 往表头插入，包括往空表中插入 newNode = GetNode(item, front); front = newNode; } else { // 往表中插入, 在prevPtr后插入结点 newNode = GetNode(item); prevPtr->InsertAfter(newNode);

表插入方法(续) // 若prevPtr = =rear，往空表中插入 if (prevPtr = = rear) { rear = newNode; position = size; } // 改变currPtr及增加表的大小 currPtr = newNode; size + +;

表插入示意 InsertAt示意 NULL NULL NULL front rear prevPtr currPtr position(-1) size(0) front rear prevPtr currPtr position(0) size(1) item front rear prevPtr currPtr position(1) size(3) item item item

表删除方法 // 删除表中的当前结点 Void LinkedList<T>∷DeleteAt(void) { Node<T> *p; if (currPtr = = NULL) // 若表为空或到表尾, 出错 cerr <<“Invalid deletion!” << endl; exit(1); } if (prevPtr = =NULL) // 被删除的结点是头结点或表中结点 p = front; front = front->NextNode( );

表删除方法(续) else // 删除prevPtr之后的中间结点, 并保留其地址 p = prevPtr->DeleteAfter(); // 若表尾被删除, prevPtr为新表尾且position减1; 否则不变。若p是最后结点，则rear =NULL且position = -1 if (p = = rear) { rear = prevPtr; position - -; } currPtr = p->NextNode(); FreeNode(p); size - -;

表删除示意 DeleteAt示意 删除结点后成为空表 NULL NULL NULL front rear prevPtr currPtr position(0) size(1) front rear prevPtr currPtr position(-1) size(0)

表删除示意 DeleteAt示意 当前结点是尾结点的情况 front ∧ rear prevPtr currPtr front ∧ NULL front rear prevPtr currPtr position(3) size(4) ∧ front rear prevPtr currPtr position(2) size(3) ∧

header->next = = header 循环表 循环表的构造 在单链表基础上增加一个构造完全相同，但未作初始化的结点，表尾结点的next域的指针指向这个新结点。这个新增结点称为头结点，用header表示。 头指针 第一个结点 在循环表中，表空的判定条件为： header->next = = header header ∧ next

循环结点定义与实现 循环结点的声明 class Cnode { private: cnode<T> *next; // 指向下一个结点的指针 public: T date; CNode(void); // 构造函数 CNode(const T& item); void InsertAfter(CNode<T> *p): // 修改表的方法 CNode<T> *DeleteAfter(void); // 获取下一个结点的地址 CNode<T> *NextNode(void) const; } 循环结点的实现 一般结点初始化 next = = NULL，循环结点初始化是指向自己 next = = this

p->next = =currPtr->next; currPtr-> = = p; 循环表结点的删除 循环表结点的插入与删除 循环表结点的插入 与一般单链表的区别 currPtr currPtr p->next = =currPtr->next; currPtr-> = = p; 循环表结点的删除 与一般单链表的区别和共同点 tempPtr = = currPtr->next; currPtr->next = = temPtr->next;

循环表的生成 循环链表的生成算法 No Yes 初始化头结点 确定当前指针 还有要插入的结点 结束返回 生成新结点 插入当前结点之后

问题：给定整数m， n个人循环报数，报到数m的人出局，剩下的n-1人继续上述游戏，直到剩下最后1人获胜。 约瑟夫问题 问题：给定整数m， n个人循环报数，报到数m的人出局，剩下的n-1人继续上述游戏，直到剩下最后1人获胜。 遍历循环链表基础上，做相应的操作(删除结点)，直到表中只剩下一个结点。 No Yes 计数 移动指针 初始化 计数不满m次 表中结点数大于1 当前指针指向头结点 删除结点 结束 再次 移动指针

二、双向链表 双向链表的示意 头结点 头指针 left right left right left right

双向链表结点的定义 双向链表结点的声明 class DNode { private： DNode<T> *left; // 指向左、右结点的指针 DNode<T> *right; public： T data； // data为公有成员 DNode(void); // 构造函数 DNode(const T& item); void InsertRight(DNode<T> *p); // 修改表的方法 void InsertLeft(DNode<T> *p); DNode<T> *DeleteNode(void); DNode<T> *NextNodeRight(void) const; // 取得左、右方向结点的指针 DNode<T> *NextNodeLeft(void) const; }

DNode〈T〉∷DNode(const T& item) { // 建立一个指向自身的结点并初始化data域 left = right = this; data = item; } 将结点p插入到当前结点右边 当前结点 右结点 将右结点接入插入结点的右指针域 将插入结点接入右结点的左指针域 ④ ③ ② ① 将当前结点接入插入结点的左指针域 将插入结点接入当前结点的右指针域 p right left left right

插入右结点算法 Insert Right 的方法 void DNode<T> ∷InsertRight(DNode<T> *p) { // 将p与当前结点的右后继结点相连接 p->right = right; right->left = p; // 将p与当前结点相连接 p->left = this; right = p; } 对InsertLeft而言，只要将InsertRight中的right和left互换即可。

删除当前结点算法 删除当前结点 当前结点 将右结点接入左结点的右指针域 将左结点接入右结点的左指针域 Dnode<T> *Dnode<T>∷DeleteNode(void) { left->right = right; // 将右结点接入左结点的右指针域 right ->left = left; // 将左结点接入右结点的左指针域 // 返回当前结点的指针 return this; }

双向链表只有一个结点的情况 被删除结点是双向链表中仅有的一个结点 删除前 删除后

关键：确定加入新结点的位置。办法：扫描链表并进行比较。 例：按输入顺序65，60，82，74建立有序表。 双向链表应用 用双向链表排序 按升序建立有序表。 关键：确定加入新结点的位置。办法：扫描链表并进行比较。 例：按输入顺序65，60，82，74建立有序表。 65 60 65 60 65 82 60 65 74 82

双向链表应用(续) 单链表排序的局限性 Y N Y Y N N Y Y Y N 输入item 左移 当前指针 右移 当前指针 item≤data 当前结点是头结点 当前结点 是头结点 右插 新结点 左插 新结点 item≤data item≤data 继续输入 结束

用“结构”把系数和指数组成单链表结点中的data，取名Term 链表的应用 1、多项式 其中 因此二元组序列 可以唯一确定一个一元多项式 p(x) 单链表结点结构示意 用“结构”把系数和指数组成单链表结点中的data，取名Term coefficient exponent next

多项式相加 PA = 1－10x6＋2x8 ＋7x14 PB = －x4 ＋10x6 －3x10 ＋8x14 ＋4x18 －x21 CA = 1 －x4 ＋2x8 －3x10 ＋15x14 ＋4x18 －x21 PA PB PC 1 -10 6 2 8 7 14 ∧ -1 4 10 6 -3 10 8 14 4 18 -1 21 ∧ 1 -1 4 2 8 -3 10 15 14 4 18 -1 21 ∧

多项式相加(续) 相加算法思想 N Y N N Y Y N Y N Y Currpa为空 两表指数相等 Currpa指数低 初始化 PC=PA、pa=PA、pb=PB currpa=pa->next, currpb=pb->next currpa∧currpb为空 Currpa为空 两表指数相等 Currpa指数低 pb的剩余部分插入pa表尾 系数和等于零 pa当前指针右移 pb当前结点插入pa之前，pb当前指针右移 修改pa的系数，pb删除当前结点，指针右移 pa、pb删除当前结点，指针右移 结束

稀疏矩阵 稀疏矩阵的三元组存储 0 0 1 0 0 0 0 0 0 0 2 5 0 0 0 0 0 7 0 8 三元组序列 进一步可表示成 0 2 1 2 0 2 2 1 5 3 2 7 3 4 8

十字链表表示稀疏矩阵 十字链表的构成 每一行或列中的非零元素分别组成一条循环链表，若某行（列）全为零元素，该行（列）所对应的链表是只含有头结点的空链表。 各行的链表的头结点另行构成一条循环链表，各列的链表亦然。 整个链表由一个“头结点”引入。 每一个非零元素的结点，按其所在的行与列，同时处于相应的行循环链表与列循环链表中。 结点的构造 head row col down value right

十字链表的例 例 T 4 5 T 5 T 5 T 5 T 5 T 5 T 5 F 1 2 T 5 T 5 F 2 F 2 1 5 T 5 F 1 2 T 5 T 5 F 2 F 2 1 5 T 5 F 3 2 7 F 3 4 8

静态链表 用数组模拟链表的操作 0 1 2 3 4 pl = 5 maxsize-1 在a2后插入c pl = 6 删除a1 pl = 2 · · · 1 2 3 4 -1 6 7 n-1 a0 a1 a2 a3 a4 c · · · 1 2 5 4 -1 3 7 n-1 a0 a1 a2 a3 a4 c · · · 2 6 3 4 -1 7 n-1

作 业 书面作业 1、9.7 2、9.30 3、9.31 上机题 1、9.10 2、9.14