《数据结构》课件-项目二 线性表

用线性表实现诗词大赛项目概述线性表是一种常见的数据结构，在实际中有着广泛的应用。各类信息表的管理，如对图书信息的添加、修改、删除、查找。多项式的表达与计算，可以表示为线性表，多项式中非零项的系数和指数组成的数据元素序列构成了线性表。著名的约瑟夫环问题中，可以用线性表求解圆圈中最后剩下的数字。线性表通常是以栈、队列、字符串、数组等特殊形式来使用的。几乎所有的程序语言中都包含数组这种数据结构，一个数组中的若干数据元素是按照顺序存储在相邻的计算机内存中，这就是一种典型的线性表。项目目标序号能力目标知识要点1理解线性表的逻辑结构线性表的基本概念、基本操作、抽象数据类型2理解线性表的顺序与链式存储结构及其算法实现线性表顺序存储：顺序表线性表链式存储：单链表、双向链表、循环链表3熟悉Java的线性表实现类线性表顺序存储实现类：ArrayList<E>线性表链式存储实现类：LinkedList<E>4能在实际问题中找出线性表并用线性表解决实际问题使用线性表解决诗词大赛中随机组卷问题；5线性表的时间复杂度插入、删除、查找常用算法的时间复杂度计算方法项目情境-编程实现诗词大赛

1．情境描述

《中国诗词大会》是央视首档全民参与的诗词节目，节目以“赏中华诗词、寻文化基因、品生活之美”为基本宗旨，力求通过对诗词知识的比拼及赏析，带动全民重温那些曾经学过的古诗词，分享诗词之美，感受诗词之趣，从古人的智慧和情怀中汲取营养，涵养心灵。图为《中国诗词大会》第五季比赛现场。2．基本要求编写程序模拟中国诗词大会的个人追逐赛比赛过程，要求如下：(1)

模拟4位挑战者与百人选手团比拼过程。(2)比赛结束后,选出4位挑战者中总分最高的挑战者。每场比赛都由个人追逐赛、攻擂资格争夺赛、擂主争夺赛三部分组成。在个人追逐赛中，由4位挑战者分别上台与百人团共同答题，如果百人团选手答错，其盾牌将会被击碎，击碎人数量即为台上挑战者的得分，每位挑战者最多答5道题，答错进入绝对反击环节，进行自救环节，自救成功将继续答题，失败将终止答题，4位选手中总分最高者直接进入擂主争夺赛。本教学情模拟个人追逐赛，省略绝对反击环节，答错即终止答题，题目类型为单选题，题目的格式如表所示，每道题由编号、题干、选项、和答案4个部分组成。用线性表实现诗词大赛项目概述线性表是一种常见的数据结构，在实际中有着广泛的应用。各类信息表的管理，如对图书信息的添加、修改、删除、查找。多项式的表达与计算，可以表示为线性表，多项式中非零项的系数和指数组成的数据元素序列构成了线性表。著名的约瑟夫环问题中，可以用线性表求解圆圈中最后剩下的数字。线性表通常是以栈、队列、字符串、数组等特殊形式来使用的。几乎所有的程序语言中都包含数组这种数据结构，一个数组中的若干数据元素是按照顺序存储在相邻的计算机内存中，这就是一种典型的线性表。项目目标序号能力目标知识要点1理解线性表的逻辑结构线性表的基本概念、基本操作、抽象数据类型2理解线性表的顺序与链式存储结构及其算法实现线性表顺序存储：顺序表线性表链式存储：单链表、双向链表、循环链表3熟悉Java的线性表实现类线性表顺序存储实现类：ArrayList<E>线性表链式存储实现类：LinkedList<E>4能在实际问题中找出线性表并用线性表解决实际问题使用线性表解决诗词大赛中随机组卷问题；5线性表的时间复杂度插入、删除、查找常用算法的时间复杂度计算方法项目情境-编程实现诗词大赛

1．情境描述

《中国诗词大会》是央视首档全民参与的诗词节目，节目以“赏中华诗词、寻文化基因、品生活之美”为基本宗旨，力求通过对诗词知识的比拼及赏析，带动全民重温那些曾经学过的古诗词，分享诗词之美，感受诗词之趣，从古人的智慧和情怀中汲取营养，涵养心灵。图为《中国诗词大会》第五季比赛现场。2．基本要求编写程序模拟中国诗词大会的个人追逐赛比赛过程，要求如下：(1)

模拟4位挑战者与百人选手团比拼过程。(2)比赛结束后,选出4位挑战者中总分最高的挑战者。每场比赛都由个人追逐赛、攻擂资格争夺赛、擂主争夺赛三部分组成。在个人追逐赛中，由4位挑战者分别上台与百人团共同答题，如果百人团选手答错，其盾牌将会被击碎，击碎人数量即为台上挑战者的得分，每位挑战者最多答5道题，答错进入绝对反击环节，进行自救环节，自救成功将继续答题，失败将终止答题，4位选手中总分最高者直接进入擂主争夺赛。本教学情模拟个人追逐赛，省略绝对反击环节，答错即终止答题，题目类型为单选题，题目的格式如表所示，每道题由编号、题干、选项、和答案4个部分组成。任务一

分析线性表的逻辑结构学习目标理解线性表定义及特点理解线性表的基本运算12理解线性表的抽象数据类型3

在用计算机解决一个具体的问题时，首先对问题抽象，进行逻辑建模。一是确定数据对象的逻辑结构，即从诗词大赛问题中提取操作的数据对象，找出构成数据对象的数据元素之间的关系。二是确定为求解问题需要对数据对象进行的操作或运算，从诗词大赛问题中抽取相应的运算。最后将数据的逻辑结构及其在该结构上的运算进行封装得到抽象数据类型。任务描述步骤一：分析线性表的逻辑结构任务实施线性表的定义题号题干选项答案1"但愿人长久,千里共婵娟"中的"婵娟"指的是?A.月亮B.姻缘C.太阳A2"千门万户曈曈日,总把新桃换旧符"中的"新桃"指的是?A.早开的桃花B.新的桃符C.新年的寿桃馒头B3"商女不知亡国恨,隔江犹唱后庭花"中的"国"是指哪个朝代?A.商朝B.陈朝C.唐朝B4"爆竹声中一岁除,春风送暖入屠苏"中的"屠苏"指的是?A.苏州B.房屋C.酒C5"月上柳梢头,人约黄昏后"描写的是哪个传统节日?A.中秋节B.元宵节C.端午节B6...............诗词大赛题库信息表

线性表是由n(n≥0)个相同类型的数据元素构成的有限序列，通常表示为(a0，a1，…ai，ai+1，…an-1)。其中下标i表示数据元素在线性表中的位序，n为线性表的表长，当n=0时，此线性表为空表。

其中：n：数据元素的个数，也称表的长度空表：n=0，记为（）什么叫线性表？

线性表的定义12345678一组数字组成线性表

一组图片组成线性表

有且仅有一个开始结点a0，它没有直接前趋，而仅有一个直接后继a1有且仅有一个终端结点an-1，它没有直接后继，而仅有一个直接前趋an-2。除第一个节点外，线性表中的其它结点ai(1≤i≤n-1)都有且仅有一个直接前趋ai-1。除最后一个节点外，线性表中的其它节点ai(0≤i≤n-2)都有且仅有一个直接后继ai+1。线性表的特点a0a1a2......ai-1aiai+1......an-2an-1步骤二：分析线性表的基本运算任务实施线性表的基本操作a0a1a2......ai-1aiai+1......an-2an-1初始化线性表：创建一个空的线性表添加元素

booleanadd(Ea)：将新的数据元素添加在线性表的末尾插入元素

booleanadd(inti,Ea)：在线性表中指定的位置插入一个新的数据元素删除元素Eremove(inti)：删除线性表中指定的位置的数据元素定位元素

intindexOf(Ea)：返回指定数据元素在线性表中首次出现的位置取表元素

Eget(inti)：返回线性表指定位置的数据元素替换元素

Eset(inti,Ea)：替换线性表指定位置的元素为新的数据元素，并返回该元素求表长度

intsize()：返回线性表中所有数据元素的个数清空线性表voidclear()：清除线性表中的所有元素判断是否为空

booleanisEmpty()：如线性表不包含任何数据元素则返回true，否则返回false步骤三：定义线性表的抽象数据类型任务实施线性表的抽象数据类型ADT线性表（List）数据对象：

D={ai|0≤i≤n-1,n≥0,ai为E类型}数据关系:

R={<ai,ai+1>|ai,ai+1∈D,i=0,...,n-2}数据操作将对线性表的基本操作定义在接口IList中，代码如下:public

interfaceIList<E>{

booleanadd(Ea);//添加元素

booleanadd(inti,Ea);//插入元素Eremove(inti);//删除元素

intindexOf(Ea);//定位元素Eget(inti);//取表元素Eset(inti,Ea);//替换元素

intsize();//求线性表长度

voidclear();//清空线性表booleanisEmpty();//判断线性表是否为空

}线性表在生活中随处可见，一个公司的员工信息表、一个学校的学生成绩表......，一个数据元素跟着一个数据元素,一个开头，一个收尾。元素间紧密相连，前后相依，如人生成长的足迹，一步一个脚印，串联起高效运算与逻辑构建，为程序世界筑牢坚实根基。任务二

用顺序表实现诗词大赛学习目标理解单链表的存储结构掌握单链表的算法实现方法12能用单链表实现诗词大赛3

在任务一中，己分析出诗词大赛问题的试题信息表的逻辑结构为线性表，并定义了线性表的抽象数据类型。接下来考虑将逻辑结构为线性表的试题信息表存储到计算机中去，进行存储结构的设计。存储结构有顺序存储结构和链式存储结构两种，线性表采用顺序存储的方式存储就称之为顺序表。本任务将线性表的逻辑结构映射成顺序存储结构，并基于顺序存储结构实现线性表的基本操作，最后，将己实现的顺序表应用在诗词大赛问题中，编写程序实现诗词大赛。任务描述步骤一：将线性表的逻辑结构映射成顺序表存储结构任务实施线性表的顺序存储结构将线性表的数据元素按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表假设顺序表中的每个数据元素在存储器中占用k个存储单元，序号为0的数据元素的内存地址为Loc(a0)，序号为i的数据元素ai的内存地址为：

LOC(ai)=LOC(a0)+i*ka0a1aian-1……Loc(a0)Loc(a0)+kLoc(a0)+i×kLoc(a0)+(n-1)×k创建一个顺序表创建一个类SeqList，实现接口Ilist。声明三个存储变量data、maxsize和n，依次表示存储线性表中数据元素的数组、数组的最大容量、数组的实际长度。初始化线性表，在构造函数中，对存储变量data、maxsize和n进行初始化。maxsize的值为构造函数参数中maxsize的值，n的值为0。

importjava.lang.reflect.Array;publicclassSeqList<E>implementsILinarList<E>{privateE[]data;//存储顺序表中数据元素的数组private

int

maxsize;//顺序表的最大容量private

int

n;//顺序表的实际长度//初始化线性表publicSeqList(Class<E>type,int

maxsize){this.maxsize=maxsize;n=0;data=(E[])Array.newInstance(type,maxsize);}//实现接口的代码}在Java中，声明的数组变量是在JVM的栈内存中分配空间，创建的数组空间是在JVM的堆内存中分配的，程序根据构造函数中指定的数据元素类型和长度创建数组空间，并为每个数组元素空间设置初始值，因泛型数据类型为引用数据类型，因此数组元素默认值都为null，不指向任何数据。创建完数组空间后，会将数组空间的首地址存储到了data变量中,通过data变量可以访问到数组对象空间中的每一个元素。顺序表存储空间初始化顺序表存储空间初始化诗词大赛题库信息表顺序存储空间示间图顺序表是将表中的结点依次存放在计算机内存中一段地址连续的存储单元中。数据元素在内存中的位置反映了它们之间的逻辑关系，可以通过下标快速的存取表中的任一元素。步骤二：基于顺序表存储结构实现线性表的基本操作任务实施求表长度、判断为空、清空顺序表、判断为满//求顺序表长度public

intsize(){return

n;}//判断顺序表是否为空public

booleanisEmpty(){return

n==0;}//判断顺序表是否为满public

booleanisFull(){return

n==maxsize;}//清空顺序表public

voidclear(){n=0;}求表长度：返回线性表中所有数据元素的个数。

参数：无。返回值：一个整数n，表示顺序表中元素的数量。解释：n是一个成员变量，用于记录顺序表中当前存储的元素个数。判断为空：如线性表不包含任何数据元素，则返回true，否则返回false。

参数：无。返回值：布尔值。若顺序表为空（n==0），返回true；否则返回false。解释：通过比较n（顺序表中的元素个数）与0，可以确定顺序表是否为空。判断为满：如线性表数据元素个数己达到最大容量，返回true，否则返回false。参数：无。返回值：布尔值。若顺序表已满（n==maxsize），返回true；否则返回false。解释：这里的maxsize是一个成员变量，表示顺序表的最大容量。通过比较n（顺序表中的元素个数）与maxsize，可以确定顺序表是否已满。清空线性表：设置线性表的长度为0。

参数：无。

返回值：无。解释：将顺序表元素个数n设为0可清空表，但未删除元素，仅重置计数器。因此，尽管表看似空，原元素占用的内存未被释放。

假设线性表中己有n(0≤n≤maxsize-1)个数据元素，在线性表末尾处添加元素a添加元素booleanadd(Ea)（1）若插入下标位置n=maxsize，则无法插入，否则转入步骤（2）//添加元素，将元素添加在顺序表的末尾public

boolean

add(Ea){if

(!isFull()){}

elsereturn

false;}假设线性表中己有n(0≤n≤maxsize-1)个数据元素，在线性表末尾处添加元素a添加元素booleanadd(Ea)（1）若插入下标位置n=maxsize，则无法插入，否则转入步骤（2）（2）将元素a放在下标位置为n的存储位置上//添加元素，将元素添加在顺序表的末尾public

boolean

add(Ea){if

(!isFull()){data[n]=a;return

true;}

elsereturn

false;}假设线性表中己有n(0≤n≤maxsize-1)个数据元素，在线性表末尾处添加元素a添加元素booleanadd(Ea)（1）若插入下标位置n=maxsize，则无法插入，否则转入步骤（2）（2）将元素a放在下标位置为n的存储位置上（3）实际长度n的值加1，元素a的下标变成n-1//添加元素，将元素添加在顺序表的末尾public

boolean

add(Ea){if

(!isFull()){data[n++]=a;return

true;}

elsereturn

false;}假设线性表中己有n(0≤n<maxsize-1)个数据元素，在下标位置i(0≤i≤n)处插入一个新的数据元素。插入元素booleanadd(inti,Ea)（1）指定插入下标位置i，如图所示,若插入下标位置i<0或i>n，则无法插入，否则转入步骤（2）。public

booleanadd(int

i,Ea){if(i<0||i>n)throw

new

IndexOutOfBoundsException("i越界");

}假设线性表中己有n(0≤n<maxsize-1)个数据元素，在下标位置i(0≤i≤n)处插入一个新的数据元素。插入元素booleanadd(inti,Ea)（1）指定插入下标位置i，如图所示,若插入下标位置i<0或i>n，则无法插入，否则转入步骤（2）。（2）将下标位置为i~n-1存储位置上的元素（共n-i个数据元素）依次后移后，将新的数据元素置于i位置上。public

booleanadd(int

i,Ea){if(i<0||i>n)throw

new

IndexOutOfBoundsException("i越界");if(!isFull()){for(int

j=n-1;j>=i;j--){

data[j+1]=data[j];}data[i]=a;

}

elsereturn

false;}假设线性表中己有n(0≤n<maxsize-1)个数据元素，在下标位置i(0≤i≤n)处插入一个新的数据元素。插入元素booleanadd(inti,Ea)（1）指定插入下标位置i，如图所示,若插入下标位置i<0或i>n，则无法插入，否则转入步骤（2）。（2）将下标位置为i~n-1存储位置上的元素（共n-i个数据元素）依次后移后，将新的数据元素置于i位置上。（3）使顺序表长度n加1。public

booleanadd(int

i,Ea){if(i<0||i>n)throw

new

IndexOutOfBoundsException("i越界");if(!isFull()){for(int

j=n-1;j>=i;j--){

data[j+1]=data[j];}data[i]=a;

n++;return

true;

}

elsereturn

false;}假设顺序表中己有n(1≤n≤maxsize)个数据元素，删除指定下标位置i的数据元素。删除操作remove(inti)（1）如果i不符合0≤i≤n-1，则抛出越界异常；否则转入步骤（2）。public

Eremove(int

i){if

(i

<0||i

>=n)throw

new

IndexOutOfBoundsException("i越界");if

(!isEmpty()){EoldValue

=data[i];for

(int

j

=i;j

<n

-1;j++){data[j]=data[j

+1];}data[--n]=null;return

oldValue;}

elsereturn

null;}假设顺序表中己有n(1≤n≤maxsize)个数据元素，删除指定下标位置i的数据元素。删除操作remove(inti)（1）如果i不符合0≤i≤n-1，则抛出越界异常；否则转入步骤（2）。（2）将第i+1到第n-1下标位置上数据元素（共n-1-i个数据元素）依次前移。（3）使顺序表的表长度n减1public

Eremove(int

i){if

(i

<0||i

>=n)throw

new

IndexOutOfBoundsException("i越界");if

(!isEmpty()){EoldValue

=data[i];for

(int

j

=i;j

<n

-1;j++){data[j]=data[j

+1];}data[--n]=null;return

oldValue;}

elsereturn

null;}假设顺序表中己有n(1≤n≤maxsize)个数据元素，删除指定下标位置i的数据元素。删除操作remove(inti)（1）如果i不符合0≤i≤n-1，则抛出越界异常；否则转入步骤（2）。（2）将第i+1到第n-1下标位置上数据元素（共n-1-i个数据元素）依次前移。（3）使顺序表的表长度n减1public

Eremove(int

i){if

(i

<0||i

>=n)throw

new

IndexOutOfBoundsException("i越界");if

(!isEmpty()){EoldValue

=data[i];for

(int

j

=i;j

<n

-1;j++){data[j]=data[j

+1];}data[--n]=null;return

oldValue;}

elsereturn

null;}在顺序表中查找指定元素第一次出现的索引位置。定位操作intindexOf(Ea)public

intindexOf(Ea){

for(int

i=0;i<n;i++)

if(a.equals(data[i]))

return

i;

return-1;}（1）定义了一个名为indexOf的公共方法。public：这是一个访问修饰符，表示该方法是公共的，可以被其他类访问。int：表示该方法的返回值类型为整数，即元素在数组中第一次出现的索引位置。Ea：方法的参数a是要查找的元素，类型为E，是一个泛型类型。（2）在方法中定义一个for循环，通过遍历顺序表中每一个的元素，查找元素a。使用equals方法比较传入的元素a和数组data中索引为i的元素是否相等，如果找到了与a相等的元素（即if语句的条件为真），则方法立即返回当前元素的索引i。（3）如果循环结束后没有找到与a相等的元素，则方法返回-1。在Java中，返回-1通常表示“未找到”或“不存在”的意思。返回顺序表中指定下标位置i处的数据元素。取表元素Eget(inti)publicEget(int

i){

if(i<0||i>=n)

throw

newIndexOutOfBoundsException("下标越界");

return

data[i];}publicEget(inti):一个公开（public）的方法，返回类型是泛型E，表示返回的元素类型与顺序表中存储的元素类型相同。它接受一个参数i，类型为int，表示要获取的元素的索引。参数检查:if(i<0||i>=n):在尝试获取元素之前，方法首先检查提供的索引i是否有效。如果索引i小于0或大于等于n，则认为索引无效，因为数组索引是从0开始的，最大索引为n-1。异常抛出:如果索引无效（即不满足0<=i<n的条件），则方法会抛出一个IndexOutOfBoundsException异常。这个异常是Java标准库中的一个运行时异常，用于指示索引超出字符串或数组的有效范围。异常的消息被设置为“下标越界”。返回元素:returndata[i]返回数组中索引为i处的元素，元素类型为泛型E。将顺序表中指定索引位置的元素替换为新元素，并返回被替换后的元素。替换元素Eset(inti,Ea)publicEset(int

i,Ea){

if(i<0||i>=n)

throw

newIndexOutOfBoundsException("下标越界");

data[i]=a;

return

data[i];}方法签名:publicEset(inti,Ea）方法的返回类型是泛型E，它接受两个参数，一个是int类型的i，表示要设置元素的索引；另一个是泛型E类型的a，表示要设置的新元素。参数检查:用if(i<0||i>=n):检查提供的索引i是否有效，如果索引i小于0或大于等于n，则认为索引无效，因为数组索引是从0开始的，最大索引为n-1。异常抛出:如果索引无效（即不满足0<=i<n的条件），则方法会抛出一个IndexOutOfBoundsException异常，异常的消息被设置为中文“下标越界”，以便更清楚地指示问题所在。设置元素:如果索引有效，则方法将顺序表中索引为i处的元素设置为参数a指定的新元素。返回被设置的元素:方法返回刚刚被设置的元素（即参数a指定的新元素），以便调用者验证设置操作是否成功，并获得新元素的值。a步骤三：对顺序表的基本操作进行测试任务实施测试单链表public

classTestList{

public

static

voidmain(String[]args){IList<Integer>list=newSeqList<QuestionNode>();

int[]data={23,45,3,7,6,945};Scannersc=newScanner(System.in);System.out.println("-----------------------------");System.out.println("操作选项菜单");

System.out.println("1.添加元素");

System.out.println("2.插入元素");

System.out.println("3.删除元素");

System.out.println("4.定位元素");

System.out.println("5.取表元素");

System.out.println("6.替换元素");

System.out.println("7.显示线性表");

System.out.println("0.退出");

System.out.println("-----------------------------");

char

ch;

do{System.out.print("请输入操作选项：");

ch=sc.next().charAt(0);

switch(ch){

case

'1’:

for(int

i=0;i<data.length;i++){ list.add(data[i]);}System.out.println("添加操作成功！");break;

case

'2':……}while(ch!='0');

sc.close();}}（1）创建线性表实例：创建了一个SeqList<Integer>的实例,定义数据数组：data。（2）用户交互菜单：程序通过一个do-while循环提供了一个操作选项菜单，允许用户通过输入字符来选择要执行的操作。这些操作包括添加元素、插入元素、删除元素、定位元素、取表元素、替换元素、显示线性表和退出程序。（3）操作实现：添加元素(case'1')：遍历data数组，并将每个元素添加到线性表中。注意，这个操作在每次运行程序时都会重复添加相同的元素。插入元素(case'2')：用户输入插入位置和要插入的值，然后调用list.add(loc-1,num)来插入元素。这里假设用户输入的位置是从1开始的，而线性表的索引是从0开始的。删除元素(case'3')：用户输入要删除元素的位置，然后调用list.remove(loc-1)来删除元素。定位元素(case'4')：用户输入要查找的元素值，程序输出该值在线性表中的位置（如果有的话）。位置是从1开始计算的。取表元素(case'5')：用户输入要获取元素的位置，程序输出该位置上的元素值。替换元素(case'6')：用户输入要替换元素的位置和新值，然后调用list.set(loc-1,num)来替换元素，并输出被替换的旧值。显示线性表(case'7')：遍历线性表，并输出每个元素的值。（4）退出程序(case'0')：当用户输入0时，循环结束，程序通过调用sc.close()关闭Scanner对象并退出。顺序表是将表中的结点依次存放在计算机内存中一段地址连续的存储单元中。数据元素在内存中的位置反映了它们之间的逻辑关系，可以通过下标快速的存取表中的任一元素。任务三

用链队列实现排队叫号学习目标理解队列的链式存储结构掌握链队列基本操作的实现方法12能用链队列实现排队叫号3

在任务二中用顺序队列实现了排队叫号，但在用顺序队列存储顾客的服务序号时，是有容量限制的，最大容量为maxsize，如果超过了这个容量，新来的顾客就不能申请到服务序号。有时，一些排队软件不需要这个限制，为了解决这个问题，可以采用链式存储结构存储服务序号队列，本任务将队列的逻辑结构映射成链式存储结构，基于链式存储结构实现队列的基本运算，并将链队列应用在排队叫号问题中。。任务描述步骤一：将队列的逻辑结构映射成链式存储结构任务实施队列的链式存储结构用链式存储结构存储的队列称为链队列(linkedqueue)。链队列通常用单链表来表示。链队列结点的结构与单链表结点的结构一样，由数据域data和引用域next两部分组成。设队头指针为front指向链队列的第一个数据元素，队尾指针rear指向链队列的最后一个数据元素。链队列的结构示意图链队列的结点结构创建一个链队列创建一个链队列类LinkQueue<E>，该类实现接口IQueue<E>，接口中定义的基本操作的算法实现在步骤二完成。创建一个内部类Node,表示链队列的结点类型，包含两个成员变量：data是结点数据域，类型为泛型，next是下一个结点的引用域，类型为Node。定义三个类变量front、rear、maxsize，其中front为队头指针，rear为队尾指针，maxsize为队列的容量，假如为0，不限容量。public

classLinkQueue<E>implementsIQueue<E>{

private

classNode{Edata;Nodenext;

publicNode(Edata){

this.data=data;}}

privateNodefront;//队头指针

privateNoderear;//队尾指针private

int

maxsize;//队列的容量，假如为0，不限容量//初始化队列

……//IQueue接口中定义的运算方法

……}初始化链队列初始化链队列就是创建一个空队列，在Java中通过调用类的构造函数进行初如化。将队头指针front和队尾指针rear设为null。根据队列是否限容时将其设为0或指定的容量数值。

public

classLinkQueue<E>implementsIQueue<E>{

private

classNode{Edata;Nodenext;

publicNode(Edata){

this.data=data;}}

privateNodefront;//队头指针

privateNoderear;//队尾指针private

int

maxsize;//队列的容量，假如为0，不限容量//初始化不限容量的链队列publicLinkQueue(){

front=rear=null;

maxsize=0;}

//初始化限容量的链队列

publicLinkQueue(int

maxsize){

this.maxsize=maxsize;}//IQueue接口中定义的运算方法

……}链队列以其灵活的内存分配和高效的元素管理著称。它采用链表形式，节点间通过指针相连，头尾指针分别指向队列的首尾元素，实现了元素的先进先出。这种存储结构不仅节省空间，还能在动态环境中保持高性能，展现出强大的适应性和稳定性，是数据处理中的优选方案。。步骤二：完成链队列类中队列的基本运算算法任务实施求队列长度、判断为空、判断为满//求队列的长度public

intsize(){

int

n=0;

Nodep=front;

while(p!=null){

n++;

p=p.next;

}

return

n;}//判断队列是否为空public

booleanisEmpty(){

return

front==null;} //判断循环顺序队列是否为满public

booleanisFull(){

if(maxsize!=0&&size()==maxsize){

return

true;

}else{

return

false;

}}求表长度：返回队列中所有数据元素的个数。使用一个while循环来遍历链表。循环的条件是p不等于null，意味着只要p还指向一个有效的结点，循环就继续。n++;:在循环体内，每次迭代都将n的值增加1。这表示访问了一个结点，因此链表的结点数量增加1。p=p.next;:将p更新为当前结点的下一个结点。这是通过访问当前结点的next属性实现的，该属性存储了对下一个结点的引用判断为空：如队列中不包含任何数据元素，则返回true，否则返回false。

队空时，队头指针front=null和队尾指针rear=null，只要front=null，就可断定队列中没有元素。判断为满：如队列中数据元素个数己达到最大容量，返回true，否则返回false。从理论上讲链队列是没有容量限制的，但在实际应用中有时需要对队列的容量进行限制，这里使用maxsize属性，如果该属性为0，说明没有容量限制。因此判断队列为满的条件是如果maxsize不为0并且队列的长度等于maxsize，则返回true，否则返回false。

入队操作是将一个给定的元素保存在队列的尾部入队操作offer(Ea))（1）创建一个新结点，为新结点分配内存和值（2）如果队列为空，将front和rear都指向新结点。（3）如果队列不为空，将rear的next指向新结点,rear指向新结点//入队列操作public

booleanoffer(Ea){

if(!isFull())

return

false;Nodenewnode=newNode(a);

if(isEmpty()){

front=newnode;

rear=newnode;}else{rear.next=newnode;

rear=newnode;}

return

true;}top-1出队操作是指在队列不为空的情况下，删除队列的前端元素。出队操作poll()（1）如果队列为空，返回null。（2）将front指向拟出队结点存放在一个临时变量node里。（3）将front指向链队列中的下一个结点，使之成为队列头结点。（4）如果front为null，将rear也设为null。（5）将出队结点的node的数据返回给调用者。//出队列操作publicEpoll(){

if(isEmpty())

return

null;Nodenode=front;

front=front.next;

if(front==null){

rear=null;}

return

node.data;}取队头元素操作与出队操作相似，只是取队头元素操作不改变原有队列，不删除取出的队头元素。取队头元素：peek()//取对头元素

publicEpeek(){

if(!isEmpty())

return

null;

else

return

front.data;}

（1）如果队列为空，返回null。（2）否则将出队结点的node的数据返回给调用者。步骤三：对链队列实现的基本运算的算法进行测试任务实施使用队列数据结构进行元素的入队和出队操作。测试顺序栈public

static

voidmain(String[]args){

int[]data={23,45,3,7,6,945};

//注意给定的循环队列长度至少要比实际长度大1

IQueue<Integer>queue=newLinkQueue<Integer>();

//入队操作

System.out.println("*******入队操作*******");

for(inti=0;i<data.length;i++){ queue.offer(data[i]);System.out.println(data[i]+"入队");}

intsize=queue.size();

//出队操作

System.out.println("*******出队操作*******");

for(inti=0;i<size;i++){System.out.println(queue.poll()+"出队");

}

}}类定义:定义了一个名为TestQueue的公共类。主方法:定义了程序的入口点，即主方法。数据初始化:定义并初始化了一个整型数组data，包含六个整数。队列的创建:创建一个链队列实例。入队操作:通过一个for循环，代码遍历data数组，并使用queue.offer(data[i])将每个元素依次入队。同时，每次入队后都会打印出当前入队的元素值。获取队列的大小:获取队列中当前元素的数量，并将其存储在变量size中。出队操作:通过另一个for循环，代码执行出队操作size次。每次出队后，都会打印出被移除的元素值。基于链队列实现队列操作，是一场有序且充满活力的数据之旅。入队时，新元素如新生力量加入队伍，为队列注入生机；出队时，元素似英勇先锋冲锋在前，开启新征程。节点间灵活相连，像紧密团结的伙伴，不受空间限制，能高效协作。这一进一出间，队列运转流畅，展现着秩序之美与奋进力量，助力数据处理稳步向前。。任务四

用双向链表实现线性表学习目标理解双向链表的存储结构掌握双向链表的算法实现方法12能用双向链表实现诗词大赛3单链表允许从一个结点直接访问它的后继结点，所以找直接后继结点的时间复杂度是O(1)。但是，要找某个结点的直接前驱结点，只能从表的头引用开始遍历各结点。也就是说，找直接前驱结点的时间复杂度是O(n)，n是单链表的长度。如果希望找直接前驱结点和直接后继结点的时间复杂度都是O(1)，可以使用双向链表，本任务将线性表的逻辑结构映射成双向链表存储结构，并基于双向链表存储结构实现线性表的基本操作。任务描述步骤一：将线性表的逻辑结构映射成双向链表存储结构任务实施双向链表的存储结构双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表在结点中设两个引用域，一个保存直接前驱结点的地址prev，一个直接后继结点的地址next，这样的链表就是双向链表(doublylinkedlist)。双向链表结点的定义与单链表的结点的定义很相似，只是双向链表多了一个字段prev。

创建一个双向链表创建一个双向链表类DLinkList<E>，该类实现接口IList<E>，接口中定义的基本操作的算法实现在步骤二完成。创建一个内部类Node<E>,表示双向链表的结点类型，包含三个成员变量：data是结点数据域，类型为泛型；prev是上一个结点的引用域，类型为Node<E>；next是下一个结点的引用域，类型为Node<E>。声明一个为双向链表结点类型的start变量,用来指向双向链表的第一个结点。在双向链表的构造函数中将start变量的值赋为null。

public

classDLinkList<E>implementsILinarList<E>{

privateNode<E>start;//双向链表的头引用

private

static

classNode<E>{Edata;

Node<E>prev;Node<E>next;Node(Edata,Node<E>prev,Node<E>next){

this.data=data;

this.next=next;

this.prev=prev;}}

//初始化双向链表

publicDLinkList(){

start=null;}………}步骤二：基于双向链表存储结构实现线性表的基本操作任务实施假设线性表中己有n(0≤n≤maxsize-1)个数据元素，在线性表末尾处添加元素a。添加元素booleanadd(Ea)public

booleanadd(Ea){Node<E>newnode=newNode<E>(a,null);

if(start==null){

start=newnode;}else{Node<E>current=start;

while(current.next!=null){

current=current.next;}current.next=newnode;newnode.prev=current;}

return

true;}（1）为新结点分配内存并为数据字段分配值（2）如果头结点start为null,使start指向新结点，否则转向（3）。（3）找到链表中的最后一个结点，将它标记为current（4）current的next字段指向新结点，新结点的prev字段指向current所引用结点假设线性表中己有n(0≤n<maxsize-1)个数据元素，在下标位置i(0≤i≤n)处插入一个新的数据元素。插入元素booleanadd(inti,Ea)第一种情况：在头结点前插入元素（1）为新结点分配内存并为数据字段分配值public

booleanadd(int

i,Ea){

if(i<0||i>size()||a==null)

return

false;Node<E>newnode=newNode<E>(a,null,null);

//在空链表或第一个元素前插入第一个元素

if(i==0){

newnode.next=start;

if(start!=null)start.prev=newnode;

start=newnode;

return

true;}

//双向链表的两个元素间插入一个元素

Node<E>previous=start;

intj=0;

while(previous!=null&&j<i-1){previous=previous.next;j++;}

if(previous!=null&&j==i-1){newnode.next=previous.next;newnode.prev=previous;previous.next.prev=newnode;previous.next=newnode; }

return

true;}（2）使新结点的next字段指向start（3）如果为不为空链表，使start的prev字段指向新结点假设线性表中己有n(0≤n<maxsize-1)个数据元素，在下标位置i(0≤i≤n)处插入一个新的数据元素。插入元素booleanadd(inti,Ea)第二种情况：在指定下标位置i(1≤i≤size())插入元素。（1）为新结点分配内存并为数据字段分配值（2）根据下标i的值确定要插入结点的前一个结点，将该结点标记为previousa.使previous变量指向第一个结点。b.比较previous所指结点的下标和下标i-1，否则重复步骤c。c.使previous指向链表中的下一个结点public

booleanadd(int

i,Ea){

if(i<0||i>size()||a==null)

return

false;Node<E>newnode=newNode<E>(a,null,null);

//在空链表或第一个元素前插入第一个元素

if(i==0){newnode.next=start;if(start!=null)start.prev=newnode;start=newnode;

return

true;}

//双向链表的两个元素间插入一个元素

Node<E>previous=start;

int

j=0;

while(previous!=null&&j<i-1){

previous=previous.next;

j++;}

if(previous!=null&&j==i-1){newnode.next=previous.next;newnode.prev=previous;previous.next.prev=newnode;previous.next=newnode; }

return

true;}插入元素booleanadd(inti,Ea)（3）使新结点的next指向previous的下一个结点（4）将新结点的prev指向previous（5）使previous下一个结点的prev指向新结点public

booleanadd(int

i,Ea){

if(i<0||i>size()||a==null)

return

false;Node<E>newnode=newNode<E>(a,null,null);//在空链表或第一个元素前插入第一个元素

if(i==0){newnode.next=start;if(start!=null)start.prev=newnode;start=newnode;

return

true;}

//双向链表的两个元素间插入一个元素

Node<E>previous=start;

intj=0;

while(previous!=null&&j<i-1){previous=previous.next;j++;}

if(previous!=null&&j==i-1){

newnode.next=previous.next;

newnode.prev=previous;previous.next.prev=newnode;

previous.next=newnode; }

return

true;}（6）使previous的next指向新结点假设双向链表中己有n(1≤n≤maxsize)个数据元素，删除指定下标位置i的数据元素。删除操作remove(inti)第一种情况：要删除的结点为双向链表的第一个结点。（1）将start指向start的下一个结点。（2）将start指向结点的prev设置为null。publicEremove(int

i){

if(i<0||i>size()-1){

returnnull;

}

EoldValue=null;

if(i==0&&start!=null){oldValue=start.data;

start=start.next;

start.prev=null;

returnoldValue;

}

Node<E>previous=start;

intj=0;

while(j<i-1){

previous=previous.next;

j++;

}

oldValue=previous.next.data;

previous.next=previous.next.next;

previous.next.next.prev=previous;

returnoldValue;

}删除操作remove(inti)第二种情况：要删除的结点双向链表的第一个结点（1）使previous变量指向ai-1。具体步骤如下：a.将previous设置为start。b.比较previous下标位置和要删除结点的前一个结点的下标位置i-1，直到相等，否则转向c。c.previous指向链表中的下一个结点。（2）当previous指向结点的下标为i-1时，使previous的next指向ai的next，即指向ai+1。（3）通过previous.next定位到ai+1，使ai+1的prev指向previous指向结点ai-1。publicEremove(int

i){

if(i<0||i>size()-1){

returnnull;

}

EoldValue=null;

if(i==0&&start!=null){oldValue=start.data;

start=start.next;

start.prev=null;

returnoldValue;

}

Node<E>previous=start;

int

j=0;

while(j<i-1){

previous=previous.next;

j++;

}

oldValue=previous.next.data;

previous.next=previous.next.next;

previous.next.next.prev=previous;

return

oldValue;

}步骤三：对双向链表的基本操作进行测试任务实施测试双向链表public

classTestList{

public

static

voidmain(String[]args){IList<Integer>list=newDLinkList<QuestionNode>();

int[]data={23,45,3,7,6,945};Scannersc=newScanner(System.in);System.out.println("-----------------------------");System.out.println("操作选项菜单");

System.out.println("1.添加元素");

System.out.println("2.插入元素");

System.out.println("3.删除元素");

System.out.println("4.定位元素");

System.out.println("5.取表元素");

System.out.println("6.替换元素");

System.out.println("7.显示线性表");

System.out.println("0.退出");

System.out.println("-----------------------------");

char

ch;

do{System.out.print("请输入操作选项：");

ch=sc.next().charAt(0);

switch(ch){

case

'1’:

for(int

i=0;i<data.length;i++){ list.add(data[i]);}System.out.println("添加操作成功！");break;

case

'2':……}while(ch!='0');

sc.close();}}将测试单链表中的代码：IList<Integer>list=newSLinkList<Integ