《数据结构》 (java版) 课件 4-6实验一讲解

两种链表的对应关系a1a2a3tailtail头节点：head<=>tail.next遍历完的标志：p==null<=>p==tail.next第1个节点:head.next<=>tail.next.next最后1个节点<=>taila0a1a2headhead带头结点的单链表geta0a1a2head

publicTget(int

index){ checkElementIndex(index); Node<T>p=head.next;//第1个结点

//i次

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }带头结点的单循环链表get

publicTget(int

index){ checkElementIndex(index); Node<T>p=tail.next.next;//第1个结点

//移动i次

for(int

i=0;i<index;i++)

p=p.next;

return

p.data; }a0a1a2tail带头结点的单链表indexOfa0a1a2head

public

intindexOf(Tx){

int

pos=0;

for(Node<T>p=head.next;p!=null;p=p.next){

if(p.data.equals(x))

return

pos; ++pos; }

return-1; }带头结点的单循环链表indexOf

public

intindexOf(Tx){

int

pos=0;

for(Node<T>p=tail.next.next;p!=tail.next;p=p.next){

if(p.data.equals(x))

return

pos; ++pos; }

return-1; }a0a1a2taila0a1a2tailpa0a1a2tailpremoveadd字段tail引用表尾结点tail带头结点的单(向)循环链表带头结点的单链表adda0a1a2head

public

voidadd(int

index,Tx){ checkPositionIndex(index); Node<T>p=head;

for(int

i=0;i<index;i++)

p=p.next;//找到前驱

p.next=newNode<T>(x,p.next); ++size;

return; }带头结点的单循环链表adda0a1a2tail

public

voidadd(int

index,Tx){ checkPositionIndex(index);

if(index==size){//在最后1个结点的后面插入数据

tail.next=newNode<>(x,tail.next);

tail=tail.next; }else{ Node<T>p=tail.next;//头结点

//移动i次，指向第i-1个结点

for(int

i=0;i<index;i++)

p=p.next;

p.next=newNode<T>(x,p.next); } ++size;

return; }带头结点的单循环链表adda0a1a2tail

public

voidadd(int

index,Tx){ rangeCheckForAdd(index); Node<T>p=tail.next;//头结点

//移动i次，指向第i-1个结点

for(int

i=0;i<index;i++)

p=p.next;

p.next=newNode<T>(x,p.next);

if(index==size)//在最后1个结点的后面插入数据，tail要跟着发生变化

tail=tail.next; ++size;

return; }带头结点的单链表cleara0a1a2head

public

voidclear(){

while(head.next!=null){//head一直作为前驱，删除它后面的节点 Node<T>q=head.next;//q待删除节点

head.next=q.next;//将q从链表中移除

q.data=null;//帮助GC

q.next=null; }

size=0; }带头结点的单循环链表clear

public

voidclear(){

tail=tail.next;//tail引用头节点

while(tail.next!=tail){//如果tail.next==tail，则只剩下了头结点 Node<T>q=tail.next;//q是待删除节点，tail是q的前驱，

tail.next=q.next;//将q从链中移除

q.data=null;//帮助GC

q.next=null; }

size=0; }a0a1a2taila0a1a2tailb0tail合并2个单循环链表：a0a1a2tailb0tail带头结点的单(向)循环链表b1b1带头结点的单(向)循环链表

//将other的数据结点合并到this，other变成空表

public

voidmerge(CircularLinkedListWithHeadNodeUsingTail<T>other){

if(other.size==0)//因为后面的代码不能正确的处理空表

return; Node<T>p=other.tail.next;//other的头结点

other.tail.next=tail.next;

tail.next=p.next;

tail=other.tail;

size+=other.size;

other.tail=p;

other.tail.next=other.tail;

other.size=0; }如何在一组数据中找最小的数据？返回最小值的索引号a0，a1,a2,…,an1、使用min记录最小的值，p记录它的索引号，初始时min=a0，p=0;2、逐个比较:用i记录下一个要比较的数据的索引号，i=1,…,n比较时，如果ai小于min，则min=ai，p=i

public

static

intfindMin(int[]a){//要求至少有一个数据

int

min=a[0];

int

p=0;

for(int

i=1;i<a.length;i++){

if(a[i]<min){//基本类型的比较使用<

min=a[i];

p=i; } }

return

p; }带头结点的单(向)循环链表

@SuppressWarnings("unchecked")

public

static<T>intfindMin(T[]a){//要求至少有一个数据 Tmin=a[0];

int

p=0;

for(int

i=1;i<a.length;i++){

//引用类型的比较，使用compareTo(需要实验接口Comparable),或compare(接口Comparator)

if(((Comparable<?superT>)a[i]).compareTo(min)<0){

min=a[i];

p=i; } }

return

p; }

//限制T必须实现了接口Comparable

public

static<TextendsComparable<?superT>>intfindMin1(T[]a){ Tmin=a[0];

int

p=0;

for(int

i=1;i<a.length;i++){

if(a[i].compareTo(min)<0){

min=a[i];

p=i; } }

return

p; }带头结点的单(向)循环链表

public

static

voidmain(String[]args){

int[]a={2,8,4,6,1,5,9}; System.out.println(findMin(a)); Integer[]b={2,8,4,6,1,5,9}; System.out.println(findMin(b)); System.out.println(findMin1(b)); }如果将findMin1更名为findMin，编译不会报错，重载的效果是调用findMin1的代码。带头结点的单(向)循环链表a0a1a2tailputMinToFirstpreTmin:记录最小值；Node<T>pre:记录最小值结点的前驱如何逐一比较？c引用下一个要比较的结点，p引用c的前驱找到最小值结点后：1、将最小值结点从链表中摘除2、将最小值结点作为表头结点带头结点的单(向)循环链表带头结点的单(向)循环链表

//需要测试能否处理空表、只有1个结点，因为下面的注解已经表明，假设至少有2个结点了

//测试结果表明能正确处理空表和只有1个结点的特殊情况，想想原因？

public

voidputMinToFirst(){// if(size<=1)//下面的代码可以处理空表和只有一个结点的情况// return; Node<T>preMin=tail.next;//最小值结点的前驱，初始为头结点

//假设第1个结点的值最小 Comparable<?superT>min=(Comparable<?superT>)preMin.next.data;

//cur从第2个结点开始比较

for(Node<T>pre=tail.next.next,cur=pre.next;cur!=tail.next;pre=cur,cur=cur.next){

if(min.compareTo(cur.data)>0){

preMin=pre;//记住最小值所在结点的前驱

min=(Comparable<?superT>)cur.data; } }

//下一句没有使用if语句，希望能帮助CPU的流水线

tail=preMin.next==tail?preMin:tail;//判断最小值结点是否表尾结点 Node<T>q=preMin.next;//最小值结点

preMin.next=q.next;//从链表中移走最小值结点 Node<T>p=tail.next;//将最小值结点加入头结点的后面

q.next=p.next;

p.next=q;

tail=tail==p?p.