L05：数据结构2-链表.pdfVIP

第二章 数据结构 （一）线性表（链表） 方钰 fangyu@ 1 本章内容 1. 数据结构概述 2. 线性结构—— ① 线性表（顺序表、链表） ② 栈、队列 3. 树形结构—— ① 树 ② 二叉树 4. 查找 5. 排序 Tongji University 2 单链表——类分析  节点类  数据域  指针域(C#中使用引用型):存放下一个节点的存储地址。  链表类  表头：专门的指针指向链表的头节点。  当前节点  表尾： 注：链表的最后一个节点的指针域置为空（C# 中用null表示）， 图形符号用 “/”表示。 Tongji University 3 单链表——操作方法 ① 遍历链表 ② 统计链表中节点的个数 ③ 查找链表中的某个节点 ④ 在链表中插入一个新节点 ⑤ 删除链表中的某个节点 ⑥ 链表排序 Tongji University 4 例2.4 链表节点类的定义 节点数据域存放学生信息，学生数据类定义见上节PPT public class Node // 定义节点类 { public Student data; // 每个节点的数据域是一个学生 public Node next; // 下一个节点对象也是一个Node类型 public Node(Student s) // 构造函数 { data = s; next = null; } } Tongji University 5 例2.5 链表类定义 public class LinkedList { private Node head; // 定义表头节点 private Node tail; // 定义表尾节点 private Node current; // 定义当前工作节点，以辅助链表的遍历 public LinkedList( ) // 构造函数 { head=null; public bool append(Student s) {} tail=null; public bool delete(Student s) {} } public bool insert(Student s) {} public void sort() {} // 其他方法代码实现 public Student getMax() {} …… } Tongji Uni