2.3线性表的链式存储结构线性表的链式存储结构一链表2.3.1线性表：(ag, ai,, ai, ai1,",an-1)映射结点结点包含有元素值和前后继结点的地址信息1/85
线性表： （a0，a1，.，ai，ai+1，.，an-1） 结点包含有元素值和前后继结点的地址信息 结点 映射 1/85
如果每个结点只设置一个指向其后继结点的指针成员，这样的链表称为线性单向链接表，简称单链表。头结点开始结点尾结点head(a）单链表如果每个结点中设置两个指针成员，分别用以指向其前驱结点和后继结点，这样的链表称之为线性双向链接表，简称双链表头结点开始结点尾结点dhead-aean-1（b）双链表2/85
如果每个结点只设置一个指向其后继结点的指针成员，这样的链表 称为线性单向链接表，简称单链表。 头结点 开始结点 尾结点 head a0 a1 . an-1 ∧ （a）单链表 如果每个结点中设置两个指针成员，分别用以指向其前驱结点和后 继结点，这样的链表称之为线性双向链接表，简称双链表。 头结点 开始结点 尾结点 dhead a0 a1 . an-1 ∧ （b）双链表 2/85
2.3.2单链表头结点尾结点开始结点head每个结点为LinkNode泛型类对象，包括存储元素的数据成员data（设其数据类型为E）和存储后继结点的指针成员next。1/单链表结点泛型类classLinkNodef E data;LinkNodenext;1/构造方法publicLinkNode()next=null;}包//重载构造方法public LinkNode(E d)data=d;next=null;3/85
每个结点为LinkNode泛型类对象，包括存储元素的数据成员 data（设其数据类型为E）和存储后继结点的指针成员next。 class LinkNode //单链表结点泛型类 { E data; LinkNode next; public LinkNode() //构造方法 { next=null; } public LinkNode(E d) //重载构造方法 { data=d; next=null; } } 头结点 开始结点 尾结点 head a0 a1 . an-1 ∧ 3/85
单链表泛型类LinkListclass//单链表泛型类public class LinkListclass/存放头结点LinkNode head;/ /构造方法publicLinkListclass()//创建头结点head=new LinkNode();//头结点next成员置为nexthead.next=null;71/基本运算算法7head4/85
单链表泛型类LinkListClass public class LinkListClass //单链表泛型类 { LinkNode head; //存放头结点 public LinkListClass() //构造方法 { head=new LinkNode(); //创建头结点 head.next=null; //头结点next成员置为next } //基本运算算法 } head ∧ 4/85
结点引用方式：L.head L.head.nexthead单链表对象L：5/85
head . ∧ 单链表对象L： L.head L.head.next 结点引用方式： 5/85
1.插入和删除结点操作插入结点操作：将结点s插入到单链表中p结点的后面。(a）插入前(b) s.next=p.next（d）插入后(c) p.next=s6/85
1. 插入和删除结点操作 插入结点操作：将结点s插入到单链表中p结点的后面。 . a p b . x s （b）s.next=p.next . a p b . x s （c）p.next=s . a p x b . s （d）插入后 . a p b . s x （a）插入前 6/85
删除结点操作：删除单链表中p结点的后继结点。(a）删除前（b）删除后7/85
删除结点操作：删除单链表中p结点的后继结点。 . a p b . （a）删除前 . a p b . （b）删除后 7/85
整体建立单链表2通过一个含有n个元素的a数组来建立单链表。建立单链表的常用方法有两种：头插法和尾插法。8/85
2. 整体建立单链表 通过一个含有n个元素的a数组来建立单链表。 建立单链表的常用方法有两种：头插法和尾插法。 8/85
头插法建表从一个空表开始，依次读取数组a中的元素。生成新结点S，将读取的数据存放到新结点的数据成员中。将新结点s插入到当前链表的表头上。s.next=head.next;aihead.next=s;head9/85
从一个空表开始，依次读取数组a中的元素。 生成新结点s，将读取的数据存放到新结点的数据成员中。 将新结点s插入到当前链表的表头上。 s.next=head.next; head.next=s; head . ∧ ai s 9/85
public void CreateListF(E[] a)//头插法：由数组a整体建立单链表LinkNode S;//循环建立数据结点Sfor (int i=o;i(a[i]);广//将s结点插入到开始结点之前，头结点之后s.next=head.next;head.next=s;a=('a',"b'，'c'，'d')，调用CreateListF(a)headdcb+aa头插法建立的单链表中数据结点的次序与a数组中的次序正好相反10/85
public void CreateListF(E[] a) //头插法：由数组a整体建立单链表 { LinkNode s; for (int i=0;i(a[i]); //新建存放a[i]元素的结点s s.next=head.next; //将s结点插入到开始结点之前,头结点之后 head.next=s; } } a=('a','b','c','d')，调用CreateListF(a) head d c b a ∧ 头插法建立的单链表中数据结点的次序与a数组中的次序正好相反 10/85