数据结构(Java)第二章线性表.pptVIP

单链表上删除操作remove(i)的算法 public void remove(int i) throws Exception { } //算法2.6结束 Node p = head; int j = -1; while (p.getNext()!= null ji-1 ) { p = p.getNext(); ++j; } if (j i-1 || p.getNext() == null ) // i不合法 throw new Exception(“删除位置不合法); 时间复杂度：O（n) p.setNext(p.getNext().getNext()); 问：如果单链表不带头结点，应如何修改此算法？？ 问：如果是删除带头结点的单链表中值为x的结点，应如何修改此算法？？ 2.3.2 单链表上基本操作的实现 4. 单链表的建立操作creat(n)的实现 如何从线性表得到单链表？ 链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。 方法： 头插法 尾插法 方法一、头插法（逆位序法） 操作步骤 当前链表是一个“空表”； 1、输入数据元素an-1， 建立结点并插入在表头； 2、输入数据元素an-2， 建立结点并插入在表头； an-1 an-1 an-2 3、依次类推，直至插入a0为止。 P47/算法2.9 头插法创建单链表每次都是将创建的新结点插入到当前形成的单链表的表头。 头插法创建单链表creat2(n)的算法 public void create2(int n) throws Exception { } //算法2.9结束 Scanner sc = new Scanner(System.in); // 构造用于输入的对象 for (int j = 0; j n; j++) //从键盘读入n个数依次插入到表头 insert(0, sc.next() ); 时间复杂度：O（n) 方法二、尾插法（顺序法） 操作步骤 当前链表仍是一个“空表”； 1、输入数据元素a0， 建立结点并插入在表尾； 2、输入数据元素a1， 建立结点并插入在表尾； 3、依次类推，直至插入an-1为止。 P47/算法2.10 尾插法创建单链表每次都是将创建的新结点插入到当前形成的单链表的表尾 。 a0 a0 a1 尾插法创建单链表creat1(n)的算法 public void create1(int n) throws Exception { } //算法2.10结束 Scanner sc = new Scanner(System.in); // 构造用于输入的对象 for (int j = 0; j n; j++) //从键盘读入n个数依次插入到表尾 insert( length() , sc.next() ); 时间复杂度：O（n) 2.3.3 单链表的应用举例 【例1】编写程序实现：建立一个单链表，然后删除单链表中“多余”的结点，即使操作之后的单链表中只留下不相同的结点，最后输出删除后的单链表中所有结点。 要删除单链表中相同的结点，只要从单链表的首结点开始依次将单链表中每一个结点与它后面的所有结点进行比较，若遇到相等的，则将此结点从链表中删除。当对单链表中的每一个结点都做完处理后，算法结束。。 1）分析： 2）程序代码 （P49） public class Example2_4 { } public static void main(String[] args) throws Exception { System.out.println(请输入单链表中的10个结点值：); LinkList L = new LinkList(10, true); // 尾插法建链表 System.out.println(删除重复结点前单链表中的各个结点值为：); L.display(); removeRepeatElem(L); // 删除单链表中多余的结点 System.out.println(删除重复结点后单链表中的各个结点值为：); L.display(); } …… 2）程序代码 （P49） public cl