数据结构002-线性表资料.pptx

第2章 线性表;主要内容;1、线性表 (Linear List);线性表的抽象数据类型1;线性表的抽象数据类型2;2、线性表：顺序表;;顺序表(SqList)类的定义; // 读取到线性表中的第i个数据元素并由函数返回其值。 public Object get(int i) throws Exception { if (i 0 || i curLen - 1) // i小于0或者大于表长减1 throw new Exception(第 + i + 个元素不存在); // 输出异常 return listElem[i]; // 返回顺序表中第i个数据元素 } // 在线性表的第i个数据元素之前插入一个值为x的数据元素。 public void insert(int i, Object x) throws Exception { …… } // 将线性表中第i个数据元素删除。 public void remove(int i) throws Exception { ……} // 返回线性表中首次出现指定元素的索引，如果列表不包含此元素，则返回 -1 public int indexOf(Object x) { …… } // 输出线性表中的数据元素 public void display() { for(int j=0;jcurLen;j++) System.out.print(listElem[j]+ ); System.out.println(); } };2.1 顺序表的插入操作;顺序表插入操作的实现;2.2 顺序表的删除操作;顺序表删除操作的实现;2.3 顺序表的查找操作;顺序表查找操作的实现;2.4 顺序表示例;顺序表示例-【例2】;public class SeqListTest2{ public static void main(String args[]){ SqList seqList=new SqList(100); Student[] student ; student=new Student[3]; student[0]=new Student(2000001,张三,男,20); student[1]=new Student(2000002,李四,男,21); student[2]=new Student(2000003,王五,女,22); int n=3; try{ for(int i = 0; i n; i++){seqList.insert(i,student[i]);} for(int i=0;iseqList.curLen;i++){ Student st=(Student)seqList.get(i); System.out.println(st.getNumber()+ + st.getName()+ +st.getSex()+ +st.getAge()); } } catch(Exception e){System.out.println(e.getMessage());} } };2.5 顺序存储结构的优缺点;3、线性表：链表;3.1 单链表;单链表特点;3.1.1 单链表定义-结点;单链表定义-链表（1）;单链表定义-链表（2）;3.1.2 单链表上的查找;单链表查找操作get(int i)的实现;单链表上的查找;// 在带头结点的单链表中查找值为x的元素，如果找到，则函数返回该元素在线性表中的位置，否则返回-1 public int indexOf(Object x) { // 初始化,p指向首结点结点,j为计数器 Node p = head.getNext(); int j = 0; // 从头结点开始查找，直到p.getData()指向元素x或到达表尾 while (p != null !p.getData().equals(x)) { p = p.getNext(); ++j; } if (p != null) return j; // 如果p指向表中的某一元素，返回其位置 else return -1;// x元素不在顺序表中 }; // 输出线性表中的数据元素 public void display() { Node node = head.getNext(); // 取出带头结点的单链表中的首结点元素