数据结构--链表.ppt

节点操作示例 --用结构 struct Node { int value; Node next; }; void main () { Node p1, p2; } public class Node // 定义结点类 { public Student data; //每个结点的数据域是一个学生 public Node next; // 下一个结点对象，也是一个Node类型 public Node(Student s) // 构造函数 { data = s; next = null; } } public class LinkedList { //定义链表类 private Node head; //定义表头节点 private Node tail; //定义表尾节点 private Node current; //定义当前工作节点方便遍历 public LinkedList() //构造方法 { head = null; tail = null; current = null; } 。。。 } public bool append(Student s) // 向链表尾部增加一个结点 { 代码实现 } public bool isEmpty() //判链表是否为空 { return head == null; } public void gotoHead() //定位当前工作节点指向表头，为链表遍历而设 { current = head; } public Student getValue() //获取当前工作结点中的数据 { return current.data; } public int getLength() //求取链表中包含的元素个数 { 代码实现 } public void next() //使当前工作节点移动到下一个结点 { current = current.next; } public bool isEnd() //当前工作节点是否已是链表的尾结点 { return current==null; } 链表的其他基本操作： ①遍历链表，即输出其所有数据，这需要辅助判断链表结尾的方法的支持。 ②统计链表中节点的个数。 ③查找链表中的某个节点。 ④在链表中插入一个新节点。 ⑤删除链表中的某个节点。 ⑥链表排序。 单链表中的插入 第一种情况：在链表最前端插入 ; ; 第二种情况：在链表中间插入(插入到指针p所指向的节点之后) ; ； 第三种情况：在链表末尾插入 ; 假定已有一个链表的表头为head,其data域的值由小到大排列,现插入一个新的结点newNode,要求插入后仍保持由小到大的顺序,通过前面的讨论,可将插入操作分为如下几种: 1.若链表为空,则将newNode的next置为NULL,并将head指向newNode 2.若链表不是空表，则首先确定newNode的插入位置。 则分三种情况: ①插在第一个结点之前： 将newNode的next指向head的第一个结点,再将head指向newNode ②插在链表中间(假设在p指向的结点后插入)： 将newNode的next指向p的next ,再将p的next指向newNode ③插在链表的末尾： 将最后一个结点的next指向newNode，将newNode的next置为NULL。 public bool insert(Student newValue) // 表中元素有序时，插入新元素，插入后仍然有序 { Node newNode=new Node(newValue); //生成