数据结构（Java语言实现） 课件 第2章 线性表

第2章线性表结构Java实据现数目录CONTENTS2.1

线性表的定义及抽象数据类型2.2线性表的顺序表示与实现2.3线性表的链式表示与实现2.7小结2.6一元多项式的表示与相乘2.4循环单链表2.5双向链表2.1线性表的定义及抽象数据类型1.线性表的定义唐·欧·克努特（DonaldErvinKnuth）教授开创了数据结构的最初体系，他所著的《计算机程序设计技巧》第一卷《基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。英文单词“China”“Science”“Structure”等就属于线性结构，其中的每一个英文字母就是一个数据元素，数据元素之间存在着一对一的顺序关系。如“China”中字母“C”的直接后继是字母“h”，字母“h”的直接后继是字母“i”。线性表是由n个类型相同的数据元素组成的有限序列，记(a1,a2,…,ai-1,ai,ai+1,…,an)。数据元素可以是原子类型，也可以是结构类型。在线性表中，数据元素ai-1称为ai的直接前驱元素，ai称为ai-1的直接后继元素。2.1线性表的定义及抽象数据类型一个数据元素可以由若干个数据项组成，如图2.2所示的一个学校的教职工情况表，一个数据元素由姓名、性别、出生年月、籍贯、学历、职称及任职时间七个数据项组成。数据元素也称为记录。2.1线性表的定义及抽象数据类型学习基础学习认知能力ADTList{

数据对象：D={ai|ai∈ElemSet，i=1，2，…，n，n≥0}

数据关系：R={<ai-1,ai>|ai-1，ai∈D，i=2，3，…，n}

基本操作：（1）InitList(&L)

初始条件：表L不存在。操作结果：建立一个空的线性表L。这就像日常生活中，新生入学刚建立一个学生情况表，准备登记学生信息。（2）ListEmpty(L)

初始条件：表L存在。操作结果：若表L为空，返回1，否则返回0。这就像日常生活中，刚刚建立了学生情况表，还没有学生来登记。2.1线性表的定义及抽象数据类型学习基础学习认知能力（3）GetElem(L,i,&e)

初始条件：表L存在，且i值合法，即1≤i≤ListLength(L)。操作结果：返回表L的第i个位置元素值给e。这就像在学生情况表查找一个学生，将查到的学生情况报告给老师。（4）LocateElem(L,e)

初始条件：表L存在，且e为合法元素值。操作结果：在表L中查找与给定值e相等的元素。如果查找成功，则返回该元素在表中的序号；如果这样的元素不存在，则返回0。这就像在学生情况表查找一个学生，只报告是否找到这个学生，并不报告这个学生的基本情况。（5）InsertList(&L,i,e)

初始条件：表L存在，e为合法元素且1≤i≤ListLength(L)。操作结果：在表L中的第i个位置插入新元素e。这就像新来了一个学生报到，被登记到学生情况表中。2.1线性表的定义及抽象数据类型学习基础学习认知能力（6）DeleteList(&L,i,&e)

初始条件：表L存在且1≤i≤ListLength(L)。操作结果：删除表L中的第i个位置元素，并用e返回其值。这就像一个学生违反了校规，被学校开除，需要把该学生从学生情况表中删除。（7）ListLength(L)

初始条件：表L存在。操作结果：返回表L的元素个数。这就像学校招了新生之后，需要统计下学生的总人数，查找下学生情况表，看有多少个学生。（8）ClearList(&L)

初始条件：表L存在。操作结果：将表L清空。这就像学生已经毕业，不再需要保留这些学生信息，将这些学生信息全部清空。}ADTList2.2线性表的顺序表示与实现2.2.1线性表的顺序存储线性表的顺序存储指的是将线性表中的各个元素依次存放在一组地址连续的存储单元中。用这种方法存储的线性表称为顺序表。顺序表具有以下特征：逻辑上相邻的元素，在物理上也是相邻的。

假设线性表有n个元素，每个元素占用m个存储单元，如果第一个元素的存储位置为LOC(a1)，第i个元素的存储位置为LOC(ai)，第i+1个元素的存储位置为LOC(ai+1)。则线性表的第i+1个元素的存储位置与第i个元素的存储位置满足以下关系：LOC(ai+1)=LOC(ai)+m2.2线性表的顺序表示与实现2.2.1线性表的顺序存储线性表的顺序存储结构是一种随机存取的存储结构。只要知道其中一个元素的存储地址，就可以得到线性表中任何一个元素的存储地址。线性表的顺序存储结构如图2.3所示。2.2线性表的顺序表示与实现2.2.1线性表的顺序存储由于在Java语言中，数组具有随机存取、且存储地址连续的特点，因此，可采用数组来存储顺序表中的元素。publicclassSeqList<T>{staticfinalintLISTSIZE=100;privateintlength;Tlist[];}LISTSIZE表示数组能容纳的元素个数，length表示当前数组中存储的元素个数，list[]用于存储线性表中的元素。2.2线性表的顺序表示与实现2.2.2顺序表的基本运算①顺序表的构造方法。SeqList(){list=(T[])newInteger[LISTSIZE];length=0;}②判断线性表是否为空。publicbooleanListEmpty()//判断线性表是否为空{if(length==0)returntrue;elsereturnfalse;

}2.2线性表的顺序表示与实现2.2.2顺序表的基本运算③按序号查找。publicTGetElem(inti)//取线性表中某一位置上的元素值{if(i>=1&&i<=length)returnlist[i-1];elsethrownewIllegalArgumentException("i超出了线性表的有效范围！");}2.2线性表的顺序表示与实现2.2.2顺序表的基本运算④按内容查找。从线性表中的第一个元素开始，依次与e比较，如果相等，返回该序号表示成功；否则返回0表示查找失败。publicintLocateElem(Tx){inti;for(i=0;i<length;i++){if(list[i]==x)returni+1;}return-1;}2.2线性表的顺序表示与实现2.2.2顺序表的基本运算⑤插入操作。插入操作就是在线性表L中的第i个位置插入新元素e，使线性表{a1,a2,…,ai-1,ai,…,an}变为{a1,a2,…,ai-1,e,ai,…,an}，线性表的长度也由n变成n+1。例如，在线性表{9,12,6,15,20,10,4,22}中，要在第5个元素之前插入1个元素28，需要将序号为8、7、6、5的元素依次向后移动1个位置，然后在第5号位置插入元素28，这样，线性表就变成了{9,12,6,15,28,20,10,4,22}，如图2-3所示。2.2线性表的顺序表示与实现2.2.2顺序表的基本运算publicbooleanInsertList(inti,Te){if(length>=LISTSIZE){System.out.println("顺序表空间已满!");returnfalse;}if(i<1||i>length+1){System.out.println("插入位置不合法");returnfalse;}else{for(intj=length;j>i-1;j=j-1)list[j]=list[j-1];list[i-1]=e;length+=1;returntrue;}}2.2线性表的顺序表示与实现2.2.2顺序表的基本运算⑥删除第i个元素。删除第i个元素之后，线性表{a1,a2,…,ai-1,ai,ai+1,…,an}变为{a1,a2,…,ai-1,ai+1,…,an}，线性表的长度由n变成n-1。例如要删除线性表{9,12,6,15,28,20,10,4,22}的第4个元素，需要依次将序号为5、6、7、8、9的元素向前移动一个位置，并将表长减1，如图2-4所示。2.2线性表的顺序表示与实现2.2.2顺序表的基本运算publicbooleanDeleteList(inti)

{

if(i>=1&&i<length){

for(intj=i;j<length;j++)

list[j-1]=list[j];

length-=1;

returntrue;

}

else

returnfalse;

}2.2线性表的顺序表示与实现⑦求线性表的长度。publicintListlength(){returnlength;}⑧清空顺序表。publicvoidClearList(){length=0;}2.2.2顺序表的基本运算2.2线性表的顺序表示与实现在顺序表的实现算法中，除了按内容查找运算、插入和删除操作外，算法的时间复杂度均为O（1）。在按内容查找的算法中，若要查找的是第一个元素，则仅需要进行一次比较；若要查找的是最后一个元素，则需要比较n次才能找到该元素（设线性表的长度为n）。设Pi表示在第i个位置上找到与e相等的元素的概率，若在任何位置上找到元素的概率相等，即Pi=1/n，则查找元素需要的平均比较次数为

==，因此，按内容查找的平均时间复杂度为O（n）。2.2.3基本操作性能分析=2.2线性表的顺序表示与实现在顺序表的插入算法中，时间的耗费主要集中在移动元素上。设pi为在第i个位置上插入元素的概率，假设在任何位置上找到元素的概率相等，即pi=1/(n+1)，则顺序表的插入操作需要移动元素的平均次数为：2.2.3基本算法性能分析插入操作的平均时间复杂度为O(n)。2.2线性表的顺序表示与实现在顺序表的删除算法中，时间的耗费同样在移动元素上。设pi表示删除第i个位置上的元素的概率，假设在任何位置上找到元素的概率相等，即pi=1/n，则顺序表的删除操作需要移动元素的平均次数为：2.2.3基本操作的性能分析删除操作的平均时间复杂度为O(n)。2.2线性表的顺序表示与实现staticvoidUnionAB(SeqList<Integer>LA,SeqList<Integer>LB)//合并顺序表LA和LB的元素，并保持非递减排列{inti=1,pos;Integere;while(i<=LB.Listlength()){e=LB.GetElem(i);//取出顺序表LA中第i个元素

pos=LA.LocateElem(e);if(pos==-1)//若LA中的元素小于LB中的元素

{LA.InsertList(LA.Listlength()+1,e);//则将当前元素插入到LA中

}i+=1;}

}【例2.1】假设线性表LA和LB分别表示两个集合A和B，利用线性表的基本运算实现新的集合A=AB，即扩大线性表ListA，将存在于线性表LB中且不存在于LA中的顺序表LA中有10个元素:11121314151617181920顺序表LB中有6个元素:4812162024将LB中不存在LA的元素合并到LA中，LA中有13个元素:1112131415161718192048242.2线性表的顺序表示与实现【例2-2】编写一个算法，把一个顺序表分拆成两个部分，使顺序表中小于等于0的元素位于左端，大于0的元素位于右端。要求不占用额外的存储空间。例如顺序表（-12,3,-6,-10,20,-7,9,-20）经过分拆调整后变为（-12,-20,-6,-10,-7,20,9,3）。staticvoidSplitSeqList(SeqList<Integer>L){inti=0,j=L.Listlength()-1;//指示器i和j分别指示顺序表的左端和右端元素

Integere;Integerzero=newInteger(0);while(i<j)//若未扫描完毕所有元素

{while(L.list[i].compareTo(zero)<=-1)//i遇到小于等于0的元素

i++;//略过

while(L.list[j].compareTo(Integer.valueOf(0))>0)//j遇到大于0的元素

j--;//略过

if(i<j){e=L.list[i];L.list[i]=L.list[j];L.list[j]=e;}}

}顺序表L中有8个元素:-123-6-1020-79-20调整后的顺序表L的元素依次为：

-12-20-6-10-72093【考研真题】设将n（n>1）个整数存放到一维数组R中，试设计一个在时间和空间两方面都尽可能高效的算法，将R中保存的序列循环左移p（0<p<n）个位置，即把R中的数据序列由(x0,x1,…,xn-1)变换为(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。要求如下。（1）给出算法的基本设计思想。（2）根据设计思想，采用Java语言描述算法。（3）说明所设计算法的时间复杂度和空间复杂度。【分析】该题目主要考查对顺序表的掌握情况，具有一定的灵活性。（1）先将这n个元素序列(x0,x1,…,xp,xp+1,…,xn-1)就地逆置，得到(xn-1,xn-2,…,xp,xp-1,…,x0)，然后再将前n-p个元素(xn-1,xn-2,…,xp)和后p个元素(xp-1,xp-2,…,x0)分别就地逆置，得到最终结果(xp,xp+1,…,xn-1,x0,x1,…,xp-1)。publicstaticvoidReverse(SeqListR,intleft,intright)

//将n个元素序列逆置{intk=left;intj=right;while(k<j)//若未完成逆置{//将这n个元素序列逆置处理过程

t=R.mylist[k];R.mylist[k]=R.mylist[j];R.mylist[j]=t;k++;j--;}}publicstaticvoidLeftShift(SeqListR,intn,intp)

//将R中保存的序列循环左移p（0<p<n）个位置{

if(p>0&&p<n)//若循环左移的位置合法{

Reverse(R,0,n-1);//将全部元素逆置

Reverse(R,0,n-p-1);//逆置前n-p个元素

Reverse(R,n-p,n-1);//逆置后n个元素}}2.3线性表的链式表示与实现为了表示这些元素之间的逻辑关系，除了需要存储元素本身的信息外，还需要存储指示其后继元素的地址信息。这两部分组成的存储结构，称为结点。结点包括两个域：数据域和指针域。一个采用链式存储结构的线性表(Hou,Geng,Zhou,Hao,Chen,Liu,Yang)的存储结构如图2.9所示。2.3.1单链表的存储结构2.3线性表的链式表示与实现一般情况下，我们只关心链表的逻辑顺序，而不关心链表的实际存储位置。通常用箭头代替指针来连接结点序列。因此，图2.9所示的线性表可以形象化为图2.10所示的序列。

2.3.1单链表的存储结构2.3线性表的链式表示与实现在单链表的第一个结点之前增加一个结点，称为头结点。头结点的数据域可以存放线性表的附加信息，如线性表的长度。若带头结点的链表为空链表，则头结点的指针域为“空”，如图2.12所示。2.3.1单链表的存储结构2.3线性表的链式表示与实现classListNode//单链表中结点的存储结构{intdata;ListNodenext;ListNode(intdata,ListNodenext){this.data=data;this.next=next;}ListNode(intdata){this.data=data;}}2.3.1单链表的存储结构2.3线性表的链式表示与实现①判断单链表是否为空。若单链表为空，返回true；否则返回false。publicbooleanListEmpty(){if(head.next==null)returntrue;elsereturnfalse;}2.3.2单链表上的基本运算2.3线性表的链式表示与实现②按序号查找操作。从单链表的头指针head出发，利用结点的指针域依次扫描链表的结点，并进行计数，直到计数为i，就找到了第i个结点。如果查找成功，返回该结点的指针，否则返回null表示查找失败。publicListNodeGetNode(inti){ListNodecur=head;//标记当前结点

intj=1;while(cur!=null&&j<i){cur=cur.next;j++;}if(j==i)returncur;elsereturnnull;}2.3线性表的链式表示与实现③按内容查找，查找元素值为e的结点。从单链表中的头指针开始，依次与e比较，如果找到返回该元素结点的指针；否则返回null。publicListNodeLocateElem(inte)

{ListNodep=head.next;//p指向第一个结点

while(p!=null){if(p.data!=e)//没有找到与e相等的元素

p=p.next;//继续找下一个元素

else//找到与e相等的元素

break;//退出循环

}returnp;//返回元素值为e的结点引用

}2.3线性表的链式表示与实现④定位操作。定位操作与按内容查找类似，只是返回的是该结点的序号。publicintLocatePos(inte){inti;ListNodep;if(ListEmpty())//查找第i个元素之前，判断链表是否为空

return0;p=head.next;i=1;//从第一个结点开始查找while(p!=null){if(p.data==e)//找到与e相等的元素

returni;//返回该序号

else

//否则继续查找

{p=p.next;i=i+1;}}if(p==null)//如果没有找到与e相等的元素，返回0，表示失败

return0;}2.3线性表的链式表示与实现⑤在第i个位置插入元素e。插入成功返回1，否则返回0；如果没有与e值相等的元素，返回0表示失败。假设p指向存储元素e的结点，要将p指向的结点插入pre和pre.next之间，无需移动其他结点，只需要修改p指向结点的指针域和pre指向结点的指针域即可。即先把pre指向结点的直接后继结点变成p的直接后继结点，然后把p变成pre的直接后继结点，如图2-14所示booleanInsertList(inti,inte){intj=1;ListNodepre;if(i<1)returnfalse;if(i==1){ListNodenewNode=newListNode(e);head=newNode;returntrue;}

else{pre=head;while(pre.next!=null&&j<i-1){pre=pre.next;j++;}if(j!=i-1){System.out.println("插入位置错误!");returnfalse;}ListNodenewNode=newListNode(e);newNode.next=pre.next;pre.next=newNode;returntrue;}}2.3线性表的链式表示与实现⑥删除第i个结点。假设p指向第i个结点，要将该结点删除，只需要使它的直接前驱结点的指针指向它的直接后继结点，即可删除链表的第i个结点。将单链表中第i个结点删除可分为3步：

第1步找到第i个结点的直接前驱结点，即第i-1个结点，并用pre指向该结点，p指向其直接后继结点，即第i个结点，如图2-19所示；

第2步将p指向结点的数据域赋值给e；

第3步删除第i个结点，即pre.next=p.next，并释放p指向结点的内存空间。删除过程如图2-20所示。2.3线性表的链式表示与实现publicintDeleteList(inti)//删除单链表中的第i个位置的结点。删除成功返回1，失败返回0{ListNodepre,p;intj,e;pre=head;j=0;while(pre.next!=null&&j<i-1)//在寻找的过程中确保被删除结点存在

pre=pre.next;j++;if(pre.next==null||j!=i-1)//如果没找到要删除的结点位置，说明删除位置错误

{System.out.println("删除位置错误");return0;}

p=pre.next;pre.next=p.next;//将前驱结点的指针域指向要删除结点的下一个结点

e=p.data;returne;}2.3线性表的链式表示与实现⑦求表长操作。求表长操作即返回单链表的元素个数。publicintListLength(){intlength=0;ListNodecur=head;while(cur!=null){cur=cur.next;length++;}returnlength;}2.3.3单链表存储结构与顺序存储结构的优缺点1．存储分配方式顺序存储结构用一组连续的存储单元依次存储线性表的数据元素。单链表采用链式存储结构，用一组任意的存储单元存放线性表的数据元素。2．时间性能采用顺序存储结构时，查找操作时间复杂度为O（1），插入和删除操作时间复杂度为O（n）。采用单链表存储结构时，查找操作时间复杂度为O（n），插入和删除操作时间复杂度仅为O(1)。3．空间性能采用顺序存储结构时，需要预先分配存储空间。采用单链表存储结构时，可根据需要临时分配，不需要估计问题的规模大小。2.3线性表的链式表示与实现【例2-3】已知两个单链表A和B，其中的元素都是非递减排列，编写算法将单链表A和B合并得到一个递减有序的单链表C（值相同的元素只保留一个），并要求利用原链表结点空间。staticLinkListMergeList(LinkListA,LinkListB)//将非递减排列的单链表A和B中的元素合并到C中，使C中的元素按递减排列，相同值的元素只保留一个

{ListNodepa,pb,qa,qb;LinkListC=newLinkList();pa=A.head;pb=B.head;

//利用头插法将链表A和B中的结点插入到链表C中（先插入元素值较小的结点）

while(pa!=null&&pb!=null)//单链表A和B均不空时

{if(pa.data<pb.data)//pa指向结点元素值较小时，将pa指向的结点插入到C中

{qa=pa;pa=pa.next;

//qa指向待插入结点，pa指向下一个结点

if(C.head==null)//单链表C为空时，直接将结点插入到C中

{qa.next=C.head;C.head=qa;}

elseif(C.head.data<qa.data)//pa指向的结点元素值不同于已有结点元素值

{qa.next=C.head;C.head=qa;}}2.3线性表的链式表示与实现else//pb指向结点元素值较小，将pb指向的结点插入到C中

{qb=pb;pb=pb.next;//qb指向待插入结点，pb指向下一个结点

if(C.head==null)//单链表C为空时，直接将结点插入到C中

{qb.next=C.head;C.head=qb;}

elseif(C.head.data<qb.data)//pb指向的结点元素值不同于已有结点元素时

{qb.next=C.head;C.head=qb;}}}while(pa!=null)//如果pb为空、pa不为空，则将pa指向的后继结点插入到C中

{qa=pa;pa=pa.next;//qa指向待插入结点，pa指向下一个结点

if(C.head!=null&&C.head.data<qa.data){//pa指向的结点元素值不同于已有结点元素时，才将结点插入

qa.next=C.head;C.head=qa;}}

while(pb!=null)//将pb指向的后继结点插入C中

{qb=pb;

//qb指向待插入结点

pb=pb.next;//pb指向下一个结点

if(C.head!=null&&C.head.data<qb.data)//pb指向的结点元素值不同于已有结点元素

{qb.next=C.head;C.head=qb;}}returnC;}}程序的运行结果如下所示。表A中的元素有6个：81015216791表B中的元素有7个：591013217891将A和B合并到表C中，表C中的元素有10个：917867211513109852.3线性表的链式表示与实现【例2-4】利用单链表的基本运算，求两个集合的交集。【分析】假设A和B是两个带头结点的单链表，分别表示两个给定的集合A和B，求C=A带头。先将单链表A和B分别从小到大排序，然后依次比较两个单链表中的元素值大小，pa指向A中当前比较的结点，pb指向B中当前比较的结点，如果pa.data<pb.data，则pa指向A中下一个结点；如果pa.data>pb.data，则pb指向B中下一个结点；如果pa.data==pb.data，则将当前结点插入C中。2.3线性表的链式表示与实现【例2-4】利用单链表的基本运算，求两个集合的交集。staticpublicLinkListInteractionAB(LinkListA,LinkListB){LinkListC;ListNodepa,pb,pc;Sort(A);Sort(B);//对A和B进行排序pa=A.head;pb=B.head;//pa和pb分别指向A、B的第一个结点

C=newLinkList();//为指针C指向的新链表动态分配内存空间

while(pa!=null&&pb!=null){//若pa和pb指向的结点都不为空if(pa.data<pb.data)//如果pa指向的元素值小于pb指向的元素值

pa=pa.next;//则略过该结点

elseif(pa.data>pb.data)//pa指向的元素值大于pb指向的元素值

pb=pb.next;///则略过该结点

else//否则,即pa.data==pb.data，则将当前结点插入C中

{pc=newListNode(pa.data);pc.next=C.head;C.head=pc;pa=pa.next;pb=pb.next;//则pa指向A中下一个结点，pb指向B中下一个结点

}}returnC;}程序的运行结果如下所示。A中有8个元素：5962070584481B中有9个元素：2181831566209550排序后A中的元素:5692044587081排序后B中的元素:5820213150668195A和B的交集有3个元素：81205【考研真题】假设一个带有表头结点的单链表，结点结构如下。

假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点数据域的值，并返回1；否则返回0。要求如下。（1）描述算法的基本设计思想。（2）描述算法的详细实现步骤。（3）根据设计思想和实现步骤，采用程序设计语言描述算法。2.4循环单链表循环单链表（CircularLinkedList）是一种首尾相连的单链表。在线性链表中，每个结点的指针都指向它的下一个结点，最后一个结点的指针域为空，不指向任何结点，仅表示链表结束。若把这种结构改变一下，使最后一个结点的指针域指向链表的第一个结点，就构成了循环链表。2.4循环单链表【例2-5】已知一个带哨兵结点h的循环单链表中的数据元素含有正数和负数，试编写一个算法，构造两个循环单链表，使一个循环单链表中只含正数，另一个循环单链表只含负数。【分析】初始时，先创建两个空的单链表ha和hb，然后依次查看指针p指向的结点元素值，如果值为正数，则将其插入ha中，否则将其插入hb中。最后使最后一个结点的指针域指向头结点，构成循环单链表。2.4循环单链表publicstaticvoidSplit(CycLinkListha,CycLinkListhb){

//将一个循环单链表ha构造成两个循环单链表，其中ha中的元素只含正数，hb中的元素只含负数

ListNodep,ra,rb;intv;p=ha.head.next;//定义3个指针变量

ra=ha.head;ra.next=null;

rb=hb.head;rb.next=null;

while(p!=ha.head)//当ha中还有结点没有被处理时

{

v=p.data;//取出p指向结点的数据

if(v>0)//若该结点的元素值大于0，则将其插入ha中

{

ra.next=p;//将p指向的结点插入到ra指向的结点之后

ra=p;//使ra指向ha的最后一个结点

}

else//若元素值小于0，则将其插入hb中

{

rb.next=p;//将p指向的结点插入到rb指向的结点之后

rb=p;//使rb指向hb的最后一个结点

}

p=p.next;//使p指向下一个待处理结点

}

ra.next=ha.head;rb.next=hb.head;

//使ha，hb变为循环单链表

}

}请输入第1个结点的data域值:26请输入第2个结点的data域值:-92请输入第3个结点的data域值:66请输入第4个结点的data域值:90请输入第5个结点的data域值:-5请输入第6个结点的data域值:83请输入第7个结点的data域值:-60请输入第8个结点的data域值:22请输入第9个结点的data域值:186请输入第10个结点的data域值:0输出循环单链表A(正数):2666908322186输出循环单链表B(负数):-92-5-602.5双向链表双向链表中，每个结点有两个指针域：一个指向直接前驱结点，另一个指向直接后继结点。双向链表的结点结构如图2.28所示。双向链表的结点类型描述如下：classDListNode{intdata;DlistNodeprior,next;DListNode(intdata){this.data=data;#数据域

this.prior=null;#指向前驱结点的指针域

this.next=null;#指向后继结点的指针域}}2.5双向链表（1）插入操作public

booleanInsertDList(inti,inte)://双向链表插入操作的算法实现{

DListNodep=head.next,s;//p指向链表的第一个结点

intj=1;//计数器初始化为1

while(p!=head&&j<i)//若还未到第i个结点{

p=p.next;//则继续查找下一个结点

j++;//计数器加1}

if(j!=i)//若不存在第i个结点{

System.out.println('插入位置不正确');//则输出错误提示信息

returnfalse;}

s=newDListNode(e);

s.prior=p.prior;

p.prior.next=s;

s.next=p;

p.prior=s;

returntrue;}2.5双向链表（2）删除操作删除操作就是将带头结点的双向循环链表中的第i结点删除。（1）修改p的前驱结点的next域，使其指向p的直接后继结点，即p.prior.next=p.next。（2）修改p的直接后继结点的prior域，使其指向p的直接前驱结点，即p.next.prior=p.prior。2.5双向链表publicbooleanDeleteDList(inti)//双向链表删除操作

{DListNodep=head.next;//p指向双向链表的第一个结点

intj=1;//计数器初始化为1while(p!=head&&j<i)//若还为找到待删除的结点{p=p.next;

j++;}if(j!=i)//若不存在待删除的结点位置{System.out.println('删除位置不正确');

returnfalse;}p.prior.next=p.next;p.next.prior=p.prior;

returntrue;}2.5双向链表【例2-6】约瑟夫环问题。有n个小朋友，编号分别为1，2，…，n，按编号围成一个圆圈，他们按顺时针方向从编号为k的人由1开始报数，报数为m的人出列，他的下一个人重新从1开始报数，数到m的人出列，照这样重复下去，直到所有人都出列。编写一个算法，输入n、k和m，按照出列顺序输出编号。publicvoidJosephus(intn,intm,intk){//在长度为n的双向循环链表中，从第k个人开始报数，数到m的人出列

DListNodep=head,q=null;inti;for(i=1;i<k;i++)//从第k个人开始报数

{q=p;p=p.next;}while(p.next!=p){for(i=1;i<m;i++)//数到m的人出列

{q=p;p=p.next;//p指向下一个结点}q.next=p.next;//将p指向的结点删除，即报数为m的人出列

p.next.prior=q;System.out.print(p.data+"");//输出被删除的结点

p=q.next;//p指向下一个结点，重新开始报数

}System.out.print(p.data);//输出最后出列的人}输入环中人的个数n=9输入开始报数的序号k=3报数为m的人出列m=4当前链表中的元素：123456789依次出列的序号为：6152879432.6一元多项式的表示与相加2.4.1一元多项式的表示一元多项式An(x)可以写成降幂的形式：一元多项式An(x)=anxn+an-1xn-1+…+a1x+a0的系数和指数同时存放，可以表示成一个线性表，线性表的每一个数据元素由一个二元组构成。classPolyNode{floatcoef;intexpn;PolyNodenext;PolyNode(floatcoef,intexpn){this.coef=coef;this.expn=expn;next=n