清华大学：《数据结构》课程教学资源（PPT课件讲稿）第三章 链表

第章 单链表(Singly Linked List 循环链表(Circular List) 多项式及其相加 双向链表(Doubly Linked List) 稀疏矩阵

单链表 (Singly Linked List) 循环链表 (Circular List) 多项式及其相加 双向链表 (Doubly Linked List) 稀疏矩阵

单链表( Singly linked List) 特点 每个元素(表项由结点(Node)构成。 element 线性结构 first l0 02 03 last 0结点可以不连续存储 0表可扩充

单链表 (Singly Linked List) 特点 每个元素(表项)由结点(Node)构成。 线性结构 结点可以不连续存储 表可扩充

单链表的存储映像 (a)可用存储空间 ree C0 1 3 first ree b)经过一段运行后的单链表结构st

单链表的存储映像

单链表的类定义 多个类表达一个概念(单链表) 0链表结点 Listnode)类 0链表Lis)类 0链表游标erto)类 定义方式 0复合方式 0嵌套方式

单链表的类定义 多个类表达一个概念(单链表)。 链表结点(ListNode)类 链表(List)类 链表游标(Iterator)类 定义方式 复合方式 嵌套方式

class Lists )合类定义 class Listnode i ∥链表结点类 friend class list;1表类为其友元类 rivate int data '结点数据,型 Listnode ilink 结点指针 class list ∥/链表类 publica ∥表公共操作 private Listnode*frst,ast;表头和表尾指针

class List; //复合类定义 class ListNode { //链表结点类 friend class List; //链表类为其友元类 private: int data; //结点数据, 整型 ListNode *link; //结点指针 }; class List { //链表类 public: //链表公共操作 ……… private: ListNode *first, *last; //表头和表尾指针 };

class list{∥表类定义(嵌套方式) public. 链表操作 p rivate class listnode{∥l套链表结点类 publico int data Listnode links Listnode*rst2*lat;表头和表尾指针

class List { //链表类定义(嵌套方式) public: //链表操作 ……… private: class ListNode { //嵌套链表结点类 public: int data; ListNode *link; }; ListNode *first, *last; //表头和表尾指针 };

单链表中的插入与删除 插入 第一种情况:在第一个结点前插入 newnode-link=first first=newnode; newnode newnode x first (插入前) (插入后)

单链表中的插入与删除 插入 第一种情况：在第一个结点前插入 newnode→link = first ; first = newnode； （插入前） （插入后）

第二种情况:在链表中间插入 newnode-link=p→link p-link= newnode newnan neun x x 插入前) 插入后)

(插入前) (插入后) 第二种情况：在链表中间插入 newnode→link = p→link; p→link = newnode；

第三种情况:在链表末尾插入 newnode-link=p-link; p-link=last= newnode; neon wnoce Last last (插入前) (插入后)

第三种情况：在链表末尾插入 newnode→link = p→link; p→link = last = newnode； (插入前) (插入后)

int List: Insert( const int x, const int i)t /在链表第i个结点处插入新元素x Node p=first; int k=0; while(p !- null & ki-I {p=p→link;k++;}/找第i1个结点 if(p== null & first I = NULL)& cout <<"Invalid position for Insertation!n?: return 0 Node newnode= new Node(x, null); /创建新结点,其数据为x,指针为0

int List::Insert ( const int x, const int i ) { //在链表第 i 个结点处插入新元素 x Node *p = first; int k = 0; while ( p != NULL && k< i -1 ) { p = p→link; k++; } //找第i-1个结点 if ( p == NULL && first != NULL ) { cout << “Invalid position for Insertation!\n”; return 0; } Node *newnode= new Node(x, NULL); //创建新结点,其数据为x,指针为0