数据结构教程(Java)习题解答
1
第一章
第一章第一章
第一章
绪论
绪论绪论
绪论
1
11
1.
..
.1
11
1
单选题
单选题单选题
单选题
1. D 2. C 3. D 4. B 5. A
6. B 7. C 8. C 9. A 10. B
第10小题提示：在含有n个元素的数据表中顺序查找任一元素的平均比较次数为pcii
i
n
=∑1，pi为查找第i个元素的概率，ci是查找第i个元素时需要比较的元素数，查找所
有元素的概率之和为1，若查找每个元素的概率相同，则平均查找长度的计算公式可简化为1
1
n
i
i
nc=∑。
此题的计算式为)
76543(
12
1
2
4
1
1
3
1
+++++×+×=35/12
1.
1.1.
1.2
22
2
算法分析题
算法分析题算法分析题
算法分析题
1. 判断n是否为一个素数，若是则返回逻辑值true，否则返回逻辑值false。该算法的
时间复杂度为O(n)。
2. 计算∑=
n
ii1!的值。时间复杂度为O(n)。
3. 计算∑=
n
ii1!的值。时间复杂度为O(n2)。
4. 求出满足不等式1+2+3+...+i≥
n的最小i值。时间复杂度为O(n)。
提示：因为1+2+3+...+i=(1+i)i/2，即当n很大时i的平方与n成正比，所以i的值（即
函数中while循环的次数）与n的平方根成正比。
5. 打印出一个具有n行的乘法表，第i行（1≤i≤n）中有n-i+1个乘法项，每个乘法
项为i与j（i≤j≤n）的乘积。时间复杂度为O(n2)。
6. 统计并返回二维数组a中大于等于k的元素的个数。时间复杂度为O(m×n)，假定m
和n分别表示二维数组a的行数和列数。
7. 矩阵相乘，即a[m][n]×b[n][p]→c[m][p]。时间复杂度为O(M×N×P)。这里假定
二维数组a的行列数为m和n，二维数组b的行列数为n和p，二维数组c的行列数为m和p。
1.
1.1.
1.3
33
3
算法设计题
算法设计题算法设计题
算法设计题
设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为Quadratic，该类型的数据
部分为双精度类型的3个系数项a、b和c，操作部分为：
(1) 初始化二次多项式中的三个数据成员a、b和c。
Quadratic(double aa, double bb, double cc);
(2) 做两个多项式加法，即它们对应的系数相加，返回相加结果。
Quadratic add(Quadratic q);
(3) 根据给定x的值计算多项式的值并返回。
double value(double x);
(4) 计算多项式等于0时的两个实数根，对于有实根、无实根和不是二次方程（即a==0）
这3种情况需要返回不同的整数值(1,0,-1)，以便调用函数能够做不同的处理。当有实数根
时，分别用r[1]和r[2]保存所得到的两个实数根。
2 int seekRoot(dou
ble[] r);
(5) 按照a*x**2+b*x+c的格式（x2用x**2表示）输出二次多项式，在输出时要注意去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
void print();
请写出上面的抽象数据类型所对应的Java类。
抽象数据类型如下
抽象数据类型如下抽象数据类型如下
抽象数据类型如下：
：：
：
ADT Quadratic is
Data:
double a,b,c; //二次项、一次项和常数项系数
Operations:
public Quadratic(double aa, double bb, double cc);//构造函数
public Quadratic add(Quadratic q); //二次多项式相加
public double value(double x); //二次多项式求值
public int seekRoot(double[] r); //二次多项式方程求解
public void print(); //输出二次多项式
end Quadratic
Java
JavaJava
Java类
类类
类参考答案如下
参考答案如下参考答案如下
参考答案如下：
：：
：
public class Quadratic
{
private double a,b,c;
public Quadratic(double aa, double bb, double cc) {
a=aa; b=bb; c=cc;
}
public Quadratic add(Quadratic q) {
Quadratic qq=new Quadratic(0,0,0);
qq.a=a+q.a;
qq.b=b+q.b;
qq.c=c+q.c;
return qq;
}
public double value(double x) {
return a*x*x+b*x+c;
}
public int seekRoot(double[] r) {
if(a==0) return -1; //不是二次方程返回-1
double x=b*b-4*a*c;
if(x>=0){
r[1]=(-b+Math.sqrt(x))/(2*a);
r[2]=(-b-Math.sqrt(x))/(2*a);
return 1; //有实数根返回1
3 }
else
return 0; //有虚数根返回0
}
public void print() {
if(a!=0.0) //输出二次项
System.out.print(a+"*x**2");
if(b!=0.0) //输出一次项
if(b>0) System.out.print("+"+b+"*x");
else if(b<0) System.out.print(b+"*x");
if(c!=0.0) //输出常数项
if(c>0) System.out.print("+"+c);
else if(c<0) System.out.print(c);
System.out.println();
}
}
用于调试的主函数类如下
用于调试的主函数类如下用于调试的主函数类如下
用于调试的主函数类如下：
：：
：
public class Chap1_x2
{
public static void main(String[] args)
{
double a1=3,b1=5,c1=-2;
double a2=1,b2=6,c2=5;
Quadratic q1=new
Quadratic(a1,b1,c1);
Quadratic q2=new Quadratic(a2,b2,c2);
Quadratic q3;
q3=q1.add(q2);
double x=q1.value(2);
double[] r=new double[3];
int t1=q1.seekRoot(r);
if(t1==-1) System.out.println("不是二次方程!");
else if(t1==0) System.out.println("有虚数根!");
else System.out.println("有实数根!");
q1.print();
q2.print();
q3.print();
System.out.println(x+" "+r[1]+" "+r[2]);
}
}
4
运行结果如下
运行结果如下运行结果如下
运行结果如下：
：：
：
D:\xuxk>javac Quadratic.java
D:\xuxk>javac Chap1_x2.java
D:\xuxk>java Chap1_x2
有实数根!
3.0*x**2+5.0*x-2.0
1.0*x**2+6.0*x+5.0
4.0*x**2+11.0*x+3.0
20.0 0.3333333333333333 -2.0
第二章
第二章第二章
第二章
集合
集合集合
集合
习题二
习题二习题二
习题二
2
22
2.1
.1.1
.1
选择题
选择题选择题
选择题
1. 在一个长度为n的顺序存储的集合中查找值为x的元素时，在等概率情况下，查找成
功时的平均查找长度为( )。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
2. 在一个长度为n的链接存储的集合中查找值为x的元素时，算法的时间复杂度为
( )。
A. O(1) B. O(n) C. O(n*n) D. O(log2n)
3. 已知一个元素x不属于一个长度为n的顺序或链接存储的集合set中的元素，在插入
前若省去顺序查找过程而直接进行插入，则算法的时间复杂度为( )。
A. O(1) B. O(log2n) C.
O(n) D. O(n*n)
4. 从一个长度为n的顺序或链接存储的集合set中删除值为obj的一个元素时，其平均
时间复杂度为( )。
A. O(1) B. O(log2n) C.
O(n) D. O(n*n)
5. 从一个长度为n的链接存储的集合S中删除表头结点的时间复杂度为( )。
A. O(n*n) B. O(log2n) C.
O(n) D. O(1)
6. 从顺序存储的集合中删除一个元素时，其空出的位置由（ ）元素填补。
A. 表头 B. 表尾 C. 前驱 D. 后继
2
22
2.2
.2 .2
.2 填空题
填空题填空题
填空题
1. 向顺序存储的集合中插入元素是把该元素插入到________。
2. 向链接存储的集合中插入元素是把该元素的结点插入到________。
3. 从顺序存储的集合中删除一个元素时只需要移动________个元素。
4. 求顺序或链接集合长度算法的时间复杂度为________。
5. 由集合set1和集合set2
的并运算得到的结果集合set，该集合的长度必然
________set1和set2中任一个集合的长度。
6. 由集合set1和集合set的交运算得到的结果集合set，该集合的长度必然__________
set1和set2中任一个集合的长度。
5 7. 设集合set的长度为n，则判断x是否属于集合set的时间复杂度为__________。
8. 设集合set1和集合set2的长度分别为n1和n2，则进行并运算的时间复杂度为
__________。
9. 设集合set1和集合set2的长度分别为n1和n2，则进行交运算的时间复杂度为
__________。
10. 在集合的链接存储中，表头指针head所指向的结点为__________。
2.3
2.3 2.3
2.3 运算题
运算题运算题
运算题
1. 假定一个集合S={23,56,12,49,35}采用顺序存储，若按照教材中的相应算法先向它
插入元素72，再从中删除元素56，写出运算后得到的集合S。
2. 假定一个集合S={23,56,12,49,35,48}采用顺序存储，若按照教材中的相应算法依次
从中删除元素56和23，写出运算后得到的集合S。
3. 假定一个集合S={23,56,12,49,35}采用链接存储，若按照教材中的相应算法插入62
和删除23，写出运算后得到的集合S。
4. 假定集合S1={23,56,12,49,35}和集合S2={23,12,60,38}均采用顺序存储，若按照教
材中集合并运算的算法对S1和S2进行并运算，写出并运算后的结果集合。
5. 假定集合S1={23,56,12,49,35}和集合S2={23,12,60,38}均采用顺序存储，若按照教
材中集合交运算的算法对S1和S2进行交运算，写出交运算后的结果集合。
2.
2.2.
2.4
44
4
算法设计题
算法设计题算法设计题
算法设计题
1. 修改从顺序存储的集合中删除元素的算法，要求当删除一个元素后检查数组空间的大
小，若空间利用率小于40%同时数组长度大于maxSize时则释放数组的一半存储空间。
2. 编写顺序存储集合类sequenceSet中的构造方法，它包含有一维数组参数Object[] a，
该方法中给setArray数组分配的长度是a数组长度的1.5倍，并且根据a数组中的所有不同
的元素值建立一个集合。
3. 编写一个静态成员方法，返回一个顺序存储的集合set中所有元素的最大值，假定元
素类型为Double。
4. 编写顺序存储集合类sequenceSet中的复制构造方法，它包含有一个参数为Set set，
实现把set所指向的顺序集合的内容复制到当前集合中的功能。
5. 编写一个静态成员方法，实现两个顺序存储集合的差运算，并返回所求得的差集。
6. 编写一个静态成员方法，实现两个链接存储集合的差运算，并返回所求得的差集。
2
22
2.1
.1.1
.1
选择题
选择题选择题
选择题
1. C 2. B 3. A 4. C 5. D 6. B
2
22
2.2
.2 .2
.2 填空题
填空题填空题
填空题
1. 表尾 2.表尾 3. 1 4. O(1) 5. 大于等于
6. 小于等于 7. O(n) 8. O(n1*n2) 9. O(n1*n2) 10. 附加头结点
2.3
2.3 2.3
2.3 运算题
运算题运算题
运算题
1. S={23,72,12,49,35}
2. S={35,48,12,49}
3. S={56,12,49,35,62}
4. {23,56,12,49,35,60,38}
5. {23,12}
2.
2.2.
2.4
44
4
算法设计题
算法设计题算法设计题
算法设计题
61.
public boolean remove(Object obj) //从集合删除一个元素
{
int i;
for(i=0; i
if(i
//把集合中最后一个元素赋给被删除元素的位置
length--;
int ms=setArray.length;
if((double)length/ms<0.4 && ms>maxSize) {
Object[] p=new Object[ms/2];
for(int j=0; j
}
return true; //删除成功返回真
}
else return false; //删除失败返回假
}
提示：在原来的删除算法remove中的length--语句的下面增加如下两条语句。
int ms=setArray.length;
if((double)length/ms<0.4 && ms>maxSize) {
Object[] p=new Object[ms/2];
for(int j=0; j
}
2.
public sequenceSet(Object[] a)
{
length=0;
setArray=new Object[(int)(a.length*1.5)];
for(int i=0; i
for(j=0; j
if(j==length) {setArray[length]=a[i]; length++;}
}
}
3.
7 public static Object maxValue(Set set)
{
sequenceSet dset=(sequenceSet)set;
if(dset.size()==0) return null;
Double x=(Double)dset.value(1);
for(int i=1; i
if(https://www.wendangku.net/doc/7711542532.html,pareTo(x)>0) x=y;
}
return x;
}
4.
public sequenceSet(Set set)
{
sequenceSet dset=(sequenceSet)set;
setArray=new Object[dset.set
Array.length];
for(int i=0; i
length=dset.length;
}
5.
public static Set difference(Set set1, Set set2)
{
sequenceSet dset2=(sequenceSet)set2;
sequenceSet1 dset3=new sequenceSet(set1);
for(int i=0; i
}
6.
public static Set difference1(Set set1, Set set2)
{
linkSet dset1=(linkSet)set1;
linkSet dset2=(linkSet)set2;
linkSet dset3=new linkSet();
for(int i=0; i
}
8第三章
第三章第三章
第三章
线性表
线性表线性表
线性表
习题三
习题三习题三
习题三
3.1
3.1 3.1
3.1 单选题
单选题单选题
单选题
1. 在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）位置插入一个
新元素时，需要从后向前依次后移( )个元素。
A. n-i B. n-i+1 C. n-i-1 D. i
2. 在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前
向后依次前移( )个元素。
A. n-i B. n-i+1 C. n-i-1 D. i
3. 在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时
的平均查找长度（即需要比较的元素个数）为( )。
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
4．在一个长度为 n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次
数为( )。
A. (n+1)/2 B. n/2 C. n D. n+1
5. 在一个顺序表的表尾插入一个元素的时间复杂度为( )。
A. O(n) B. O(1) C. O(n*n) D. O(log2n)
6. 若一个结点的引用为p，在p结点后面插入一个值为x的新结点的操作为( )。
A. p=new Node(x,p) B. p=new Node(x,p.next)
C. p.next=new Node(x,p) D. p.next=new Node(x,p.next)
7. 若一个结点的引用为p，它的前驱结点的引用为q，则删除p的后继结点的操作为
( )。
A. p=p.next.next B. p.next=p.next.next
C. q.next=p.next D. q.next=q.next.next
8. 假定一个多项式中x的最高次幂为n，则在保存所有系数项的线性表表示中，其线性
表长度为( )。
A. n+1 B. n C. n-1 D. n+2
3.1
3.1 3.1
3.1 单选题
单选题单选题
单选题
1. B 2. A 3. C 4. C 5. B 6. D 7. B 8. A
3.2
3.2 3.2
3.2 填空题
填空题填空题
填空题
1．对于当前长度为n的线性表，共包含有________多个插入元素的位置，共包含有
________多个删除元素的位置。
2．若经常需要对线性表进行表尾插入和删除运算，则最好采用________存储结构，若经
常需要对线性表进行表头插入和删除运算，则最好采用________存储结构。
3．由n个元素生成一个顺序表，若每次都调用插入算法把一个元素插入到表头，则整个
算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法
的时间复杂度为________。
4．由n个元素生成一个单链表，若每次都调用插入算法把一个元素插入到表头，则整个
算法的时间复杂度为________，若每次都调用插入算法把一个元素插入到表尾，则整个算法
的时间复杂度为________。
9 5. 对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为________，
在表尾插入元素的时间复杂度为________。
6. 对于一个单链接存储的线性表，在表头插入结点的时间复杂度为________，在表尾插
入结点的时间复杂度为________。
7. 在线性表的单链接存储中，若一个元素所在结点的引用为p，结点的类型为Node，则
其后继结点的引用为________。
8. 从一个顺序表和单链表中访问任一个给定位置序号的元素（结点）的时间复杂度分别
为________和_______。
9. 在多项式的线性表表示中，有两种表示方法，对应的线性表中的元素分别包含有
________和_______个数据项。
10.假定一个稀疏矩阵具有m行、n列和t个非0元素，在对它进行快速转置的算法中，
使用了两个整型数组num和pot，其中num的所有元素值之和为________，pot[1]的值为
_______。
3.2
3.2 3.2
3.2 填空
填空填空
填空题
题题
题
1. n+1、n 2. 顺序、链接
3. O(n2)
O(n) 4. O(n) O(n2)
5. O(n) O(1) 6. O(1) O(n)
7. p.next 8. O(1) O(n)
9. 1、2 10. t、1
3.3
3.3 3.3
3.3 写出下面主控程序类
写出下面主控程序类写出下面主控程序类
写出下面主控程序类Chap3_13
Chap3_13Chap3_13
Chap3_13中的每个静态成员方法的功能并给出程序运行结果
中的每个静态成员方法的功能并给出程序运行结果中的每个静态成员方法
的功能并给出程序运行结果
中的每个静态成员方法的功能并给出程序运行结果
public class Chap3_13
{
public static Comparable minimum(sequenceList list)
{
if(list.size()==0) return null;
Comparable min=(Comparable)list.value(1);
for(int i=2; i<=list.size(); i++) {
Comparable x=(Comparable)list.value(i);
if(https://www.wendangku.net/doc/7711542532.html,pareTo(min)<0) min=x;
}
return min;
}
功能：求出并返回顺序存储的list线性表中所有元素的最小值。
public static void separate(sequenceList list, Comparable com)
{
int n=list.size();
if(n==0 || n==1) return;
int i=1, j=n;
while(i<=j) {
while((i<=j) && ((Comparable)list.value(i)).compareTo(com)<0) i++;
while((i<=j) && ((Comparable)list.value(j)).compareTo(com)>=0) j--;
if(i
10 Comparable x=(Comparable)list.value(i);
list.modify(list.value(j), i);
list.modify(x, j);
i++; j--;
}
}
}
功能：重新调整顺序存储的线性表list中元素值的排列次序，使得前面的元素都小于参
数com的值，后面的元素都大于等于参数com的值。调整的方法是分别从两头向中间扫描，
若碰到需要调整的元素就交换位置。
static void insertTail(sequenceList list, Object [] a)
{
for(int i=0; i
}
功能：向顺序存储的线性表list的表尾依次插入数组a中的每个元素。
static void insertTop(sequenceList list, Object [] a)
{
for(int i=0; i
}
功能：向顺序存储的线性表list的表头依次插入数组a中的每个元素。
public static void main(String[] args)
{
sequenceList std=new sequenceList();
int []r={15,9,20,14,15,8,12};
int i;
for(i=0; i
System.out.println();
int x=(Integer)minimum(std);
System.out.println("x="+x);
System.out.println();
separate(std,15);
std.nextOrder();
System.out.println();
Integer []a1={13,18,5,6};
11 Integer []a2={2,10,15,7};
insertTail(std, a1); //运行时间较少
insertTop(std, a2); //运行时间较多
std.nextOrder();
System.out.println("长度："+std.size());
}
}
程序运行结果如下：
D:\xuxk>javac Chap3_13.java
D:\xuxk>java
Chap3_13
15
9
20
14
15
8
12
x=8
12
9
8
14
15
20
15
7
15
10
2
12
9
8
14
15
20
15
13
18
5
6
长度：15
12
3.
3.3.
3.4
44
4
写出下面主控程序类
写出下面主控程序类写出下面主控程序类
写出下面主控程序类Chap3_1
Chap3_1Chap3_1
Chap3_14
44
4中的每个静态成员方法的功能并给出程序运行结果
中的每个静态成员方法的功能并给出程序运行结果中的每个静态成员方法的功能并给出程序运行结果
中的每个静态成员方法的功能并给出程序运行结果
public class Chap3_14
{
public static Comparable minimum(linkList
list)
{
if(list.size()==0) return null;
Node p=list.prior(), q=p.next;
Comparable min=(Comparable)q.element;
while(q.next!=p) {
q=q.next;
Comparable x=(Comparable)q.element;
if(https://www.wendangku.net/doc/7711542532.html,pareTo(min)<0) min=x;
}
return min;
} 功能：求出并返回链接存储的list线性表中所有元素的最小值。
public static void separate(linkList list,
Comparable com)
{
int n=list.size();
if(n==0 || n==1) return;
Node p=list.prior(), head=p;
while(p.next!=head) p=p.next;
Node r=head, s=head.next;
for(int i=1; i<=n; i++) {
if(((Comparable)s.element).compareTo(com)<0)
{r=s; s=s.next;}
else {
r.next=s.next;
s.next=p.next;
13 p=p.next=s;
s=r.next;
}
} }
功能：重新调整链接存储的线性表list中结点的链接次序，使得前面结点的值都小于参
数com的值，后面结点的值都大于等于参数com的值。调整的方法是从表头顺序向后扫描，
若碰到需要调整的结点则把它摘除并插入到表尾。
static void insertTail(linkList list, Object [] a)
{
Node p=list.prior(), head=p;
while(p.next!=head) p=p.next;
for(int i=0; i
list.setSize(list.size()+a.length);
}
功能：向链接存储的线性表list的表尾依次插入数组a中的每个元素。
static void insertTop(linkList list, Object [] a)
{
Node p=list.prior();
for(int i=0; i
;
list.setSize(list.size()+a.length);
}
功能：向链接存储的线性表list的表头依次插入数组a中的每个元素。
public static void main(String[] args)
{
linkList std=new linkList();
int []r={15,9,20,14,15,8,12};
int i;
for(i=0; i
std.nextOrder();
System.out.println();
int x=(Integer)minimum(std);
System.out.println("x="+x);
System.out.println();
14 separate(std,15);
std.nextOrder();
System.out.println();
Integer []a1={13,18,5,6};
Integer []a2={2,10,15,7};
insertTail(std, a1);
insertTop(std, a2);
std.nextOrder();
System.out.println("长度："+std.size());
}
}
程序运行结果如下：
D:\xuxk>javac Chap3_14.java
D:\xuxk>java Chap3_14
15
9
20
14
15
8
12
x=8
9
14
8
12
15
20
15
7
15
10
2
9
14
8
12
15
20
15
15 13
18
5
6
长度：15
3.
3.3.
3.5
55
5
使用顺序存储的线性表类
使用顺序存储的线性表类使用顺序存储的线性表类
使用顺序存储的线性表类sequenceList
sequenceListsequenceList
sequenceList的编程练习
的编程练习的编程练习
的编程练习
在一个任意设定的类中，不妨设定的类名为seqListExtend，按照下列每小题的要求和
方法声明编写出相应的方法。
1．根据数组a中的所有元素建立并返回一个顺序存储的线性表。
public static sequenceList create(Object[] a);
public static sequenceList create(Object[] a)
{ //根据数组a中的所有元素建立并返回一个线性表
sequenceList s=new sequenceList(); //定义和创建一个空表
for(int i=0; i
return s; //返回所建立的线性表
}
2．统计并返回顺序存储的线性表list中值为obj的元素个数。
public static int count(sequenceList list, Object obj);
public static int count(sequenceList list, Object obj)
{ //统计并返回参数线性表中值为obj的元素个数
int c=0; //用c作为统计变量，初值为0
for(int i=0; i
return c; //返回统计结果
}
3．求出并返回顺序存储的线性表list中的所有元素的最大值。
public static Comparable maximum(sequenceList list);
public static Comparable maximum(sequenceList list)
{ //求出并返回参数线性表中的所有元素的最大值
if(list.size()==0) return null; //若线性表为空则返回空值
Comparable max=(Comparable)list.value(1); //第1个元素值赋给max
for(int i=1; i
if(https://www.wendangku.net/doc/7711542532.html,pareTo(max)>0) max=x;
}
return max; //返回所求得的最大值
}
16
4．将顺序存储的线性表list中的所有元素按照原来的相反次序排列。
static void selfContrary(sequenceList list);
static void selfContrary(sequenceList list)
{ //将线性表中的元素按照相反的次序排列
Object x;
int n=list.size(); //线性表长度赋给n，以便使用
for(int i=1; i<=n/2; i++) { //线性表中的前后元素对调位置
x=list.value(i); //第i个元素暂存x中
list.modify(list.value(n+1-i), i); //后面元素对调到前面位置
list.modify(x, n+1-i); //原前面元素对调到后面位置
}
}
5．将顺序存储的线性表list中的所有元素按照相反的次序排列生成一个新的顺序存储
的线性表并返回，而list中的元素次序保持不变。
public static sequenceList returnContrary(sequenceList list);
public static sequenceList returnContrary(sequenceList list)
{ //将参数线性表中的元素按照相反的次序排列而建立新线性表并返回
sequenceList s=new sequenceList(list.size()); //定义和创建新表
int n=list.size(); //线性表长度赋给n，以便使用
s.setSize(n); //设置新表的长度与原表相同
for(int i=1; i<=n/2; i++) { //原表元素到新表中对调位置
s.modify(list.value(i),n+1-i); //前面元素对调到后面
s.modify(list.value(n+1-i), i); //后面元素对调到前面
}
if(n%2==1) s.modify(list.value(n/2+1), n/2+1); //写入中点元素
return s; //返回保存运算结果的线性表
}
6．使顺序
存储的线性表list中的所有重复元素只保留最前面的一个，其余的都删除。
如对于线性表(2,8,9,2,5,5,6,8,7,2)，则执行此算法后变为(2,8,9,5,6,7)。
public static void deleteRepeat(sequenceList list);
public static void deleteRepeat(sequenceList list)
{ //参数线性表中的所有重复元素只保留最前面一个，其余都删除
int i=1;
while(i<=list.size()) { //每次循环将删除其后与第i个元素相同的所有元素
int j=i+1; //从后一位置起查找重复元素
while(j<=list.size()) //扫描后面的每一个位置
{
if((list.value(j)).equals(list.value(i))) //条件成立则删除
17 list.remove(j);//删除后再从j的位置起扫描
else j++; //不成立则继续向后扫描
}
i++; //外循环继续向后扫描
}
}
public static void deleteRepeat2(sequenceList list)
{ //参数线性表中的所有重复元素只保留最前面一个，其余都删除
int i=1;
while(i
int j=i+1; //从后一位置起查找重复元素
do { //此循环将删除所有与x相同的元素
int k=list.find(x, j); //查找与x相同的重复元素的位置k
if(k==-1) break; //如果查找失败，表明第i个元素已无重复
else list.remove(k); //删除第k个位置的重复元素
j=k; //为再向后继续查找重复元素做准备
} while(j<=list.size()); //未查找到表尾则继续循环
i++; //外循环继续向后扫描
}
}
7．从顺序存储的线性表list中删除与obj相同的所有元素。
public static void deleteAll(sequenceList list, Object obj);
public static void deleteAll(sequenceList list, Object obj)
{ //从参数线性表list中删除与obj相同的所有元素
int i=1;
while(i<=list.size()) { //从头到尾依次扫描每个元素
int k=list.find(obj, i); //从第i个元素起查找值为obj的元素
if(k==-1) break; //若查找失败则结束查找
else list.remove(k); //删除第k个元素
i=k; //为继续向后查找做准备
}
}
8．从顺序存储的线性表list中删除取值在obj1和obj2之间的所有元素，要求obj1
小于等于obj2，否则退出运行。
public static void deleteArea(sequenceList list, Obj
ect obj1, Object obj2);
public static void deleteArea(sequenceList list, Object obj1, Object obj2)
{ //从list中删除取值在obj1和obj2之间的所有元素，要求obj1<=obj2
if(((Comparable)obj1).compareTo((Comparable)obj2)>0) {
18 System.out.println("参数值不合法，无法删除元素，退出程序运行!");
System.exit(1); //退出程序运行
}
int i=1;
while(i<=list.size()) { //从头到尾依次扫描每个元素
Comparable x=(Comparable)(list.value(i)); //读取第i个元素
if(https://www.wendangku.net/doc/7711542532.html,pareTo((Comparable)obj1)<0) {i++; continue;} //不删除
if(https://www.wendangku.net/doc/7711542532.html,pareTo((Comparable)obj2)>0) {i++; continue;} //不删除
list.remove(i); //属于被删除范围内的元素则删除之
}
}
3.
3.3.
3.6
66
6
使用
使用使用
使用链接
链接链接
链接存储的线性表类
存储的线性表类存储的线性表类
存储的线性表类link
linklink
linkList
ListList
List的编程练习
的编程练习的编程练习
的编程练习
在一个任意设定的类中，不妨设定的类名为linkListExtend，按照下列每小题的要求和
方法声明编写出相应的方法。为了减少算法的运行时间，请尽量采用指针（引用），而不是
象处理顺序表那样调用现成的方法，因为在链表中读取任一个结点的平均时间复杂度为
O(n)，而在顺序表中为O(1)。
1．根据数组a中的所有元素建立并返回一个链接存储的线性表。
public static linkList create(Object[] a);
public static linkList create(Object[] a)
{ //根据数组a中的所有元素建立并返回一个链接存储的线性表
linkList s=new linkList(); //定义和创建一个空链表
Node p=s.prior(); //让p初始指向表头附加结点
for(int i=0; i
s.setSize(a.length); //设置线性表的长度
return s; //返回所建立的线性表
}
2．统计并返回链接存储的线性表list中值为obj的元素个数。
public static int count(linkList list, Object obj);
public static int count(linkList list, Object obj)
{ //统计并返回参数线性表中值为obj的元素个数
Node p=list.prior(),head=p; //list的表头指针赋给p，并保存到head
int c=0; //用c作为统计变量，初值为0
for(p=p.next; p!=head; p=p.next) //扫描整个线性表进行统计
if(
p.element.equals(obj)) c++;
return c; //返回统计结果
}
3．求出并返回链接存储的线性表list中的所有元素的最大值。
public static Comparable maximum(linkList list);
19
public static Comparable maximum(linkList list)
{ //求出并返回参数线性表中的所有元素的最大值
if(list.size()==0) return null; //若线性表为空则返回空值
Node p=list.prior(),head=p; //list的表头指针赋给p，并保存到head
Comparable max=(Comparable)p.next.element; //第1个元素值赋给max
for(p=p.next.next; p!=head; p=p.next) { //扫描剩余结点求出最大值
Comparable x=(Comparable)p.element;
if(https://www.wendangku.net/doc/7711542532.html,pareTo(max)>0) max=x;
}
return max; //返回所求得的最大值
}
4．将链接存储的线性表list中的所有元素按照原来的相反次序排列。
static void selfContrary(linkList list);
static void selfContrary(linkList list)
{ //将链接存储的线性表中的元素按照相反的次序排列
Node p=list.prior(); //表头指针赋给p
if(p.next==p || p.next.next==p) return;//原为空表或单元素则返回
Node q=p.next.next; //把第2个结点的引用赋给q
p.next.next=p; //由第1个结点构成循环链表
int i=1;
while(i<=list.size()-1) {//对其余的每个结点依次按相反次序链接
Node r=q.next; //把q的后继结点的引用赋给r
q.next=p.next; p.next=q; //将q结点插入到表头
q=r; //使q指向下一个被转换的结点
i++; //每转换过一个结点后i增1
}
}
5．将链接存储的线性表list中的所有元素按照相反的次序排列生成一个新的顺序存储
的线性表并返回，而list中的元素次序保持不变。
static linkList returnContrary(linkList list);
static linkList returnContrary(linkList list)
{ //将参数线性表中的元素按照相反的次序排列而建立新线性表并返回
linkList s=new linkList(); //定义和创建新的链接空表
Node p=list.prior(),head=p; //list的表头指针赋给p，并保存到head
Node q=s.prior(); //s的表头指针赋给q
while(p.next!=head) { //依次扫描list中的每个结点
q.next=new Node(p.next.element,q.next);//新结点插入s的表头
p=p.next; //为扫描下一个结点做准备
}
20 s.setSize(list.size()); //将s的长度修改为原表长度
return s; //返回新的链接表
}
6．使链接存储的线性表list中的所有重复元素只保留最前面的一个，其余的都删除。
public static void deleteRepeat(linkList list);
public static void deleteRepeat(linkList list)
{ //参数线性表中的所有重复元素只保留最前面一个，其余都删除
int i=1;
Node p=list.prior(),head=p; //list的表头指针赋给p，并保存到head
p=p.next; //使p指向第1个元素结点
while(p!=head) { //每次循环将删除其后与p结点值相同的所有结点
Node r=p, s=p.next; //s初始指向p的后继结点，r为s的前驱
while(s!=head) { //扫描后面的每一个结点
if(s.element.equals(p.element)) { //条件成立则删除重复结点，
r.next=s.next; s=s.next; //并修改s指针，r不变
list.setSize(list.size()-1); //长度减1
}
else {r=s; s=s.next;} //条件不成立则同时修改r和s
}
p=p.next; //使外循环的p指向下一个结点
}
}
7．从链接存储的线性表list中删除与obj相同的所有元素。
public static void deleteAll(linkList list, Object obj);
public static void deleteAll(linkList list, Object obj)
{ //从参数线性表list中删除与obj相同的所有元素
Node p=list.prior(),head=p; //list的表头指针赋给p，并保存到head
Node q=p.next; //使q指向第1个元素结点, p为q的前驱
while(q!=head) { //从头到尾依次扫描每个结点
if(q.element.equals(obj)) {
p.next=q.next; q=q.next; //删除q结点,q指向下一个结点
list.setSize(list.size()-1); //长度减1
}
else {p=q; q=q.next;} //使p和q顺序指向下一个结点
}
}
8．从链接存储的线性表list中删除取值在obj1和obj2之间的所有元素，要求obj1
小于等于obj2，否则退出运行。
public static void deleteArea(linkList list, Object obj1, Object obj2);
21
public static void deleteArea(linkList list, Object obj1, Object obj2)
{ //从list中删除取值在obj1和obj2之间的所有元素，要求obj1<=obj2
if(((Comparable)obj1).compareTo((Comparable)obj2)>0) {
System.out.println("参数值不合法，无法删除元素，退出程序运行!");
System.exit(1); //退出程序运行
}
Node p=list.prior(),head=p; //list的表头指针赋给p，并保存
到head
Node q=p.next; //使q指向第1个元素结点, p为q的前驱
while(q!=head) { //从头到尾依次扫描每个结点
Comparable x=(Comparable)(q.element); //读取一个元素
if(https://www.wendangku.net/doc/7711542532.html,pareTo((Comparable)obj1)<0) { //q不是要删除的元素
p=q; q=q.next; //不删除，向后扫描
}
else if(https://www.wendangku.net/doc/7711542532.html,pareTo((Comparable)obj2)>0) { //q不是要删除的元素
p=q; q=q.next; //不删除，向后扫描
}
else { //q是要删除的元素
p.next=q.next; q=q.next; //删除q结点,q指向下一个结点
list.setSize(list.size()-1); //长度减1
}
}
}
3.
3.3.
3.7
77
7
使用顺序存储的
使用顺序存储的使用顺序存储的
使用顺序存储的有序表
有序表有序表
有序表类
类类
类seq
seqseq
seqSorted
SortedSorted
SortedList
ListList
List的编程练习
的编程练习的编程练习
的编程练习
在一个任意设定的类中，不妨设定的类名为seqSortedListExtend，按照下列每小题的
要求和方法声明编写出相应的方法。
1．根据数组a中的所有元素建立并返回一个顺序存储的有序线性表。
public static seqSortedList create(Object[] a);
public static seqSortedList create(Object[] a)
{ //根据数组a中的所有元素建立并返回一个顺序存储的有序线性表
seqSortedList s=new seqSortedList(); //定义和创建一个空的有序表
for(int i=0; i
return s; //返回所建立的有序表
}
2．根据两个顺序存储的有序线性表合并产生一个新的有序线性表。
public static seqSortedList merge(seqSortedList list1,seqSortedList list2)
public static seqSortedList merge(seqSortedList list1,seqSortedList list2)
{ //根据list1和list2合并生成一个新的有序表并返回
seqSortedList s=new seqSortedList(list1); //定义和创建一个有序表s
22 for(int i=1; i<=list2.size(); i++) //依次向s中插入list2中的元素
s.insert(list2.value(i));
return s; //返回所建立的有序表s
}
3．求出并返回顺序存储的有序线性表list中的所有元素的最大值。
public static Comparable maximum(seqSortedList list);
public static Comparable maximum(seqSortedList list)
{ //求出并返回顺序存储的有序表中的所有元素的最大值
if(list.size()==0) return null; //若有序表为空则返回空值
return
(Comparable)list.value(list.size()); //返回最后一个元素值
}
4．从顺序存储的有序线性表list中删除与obj相同的所有元素。
public static void deleteAll(seqSortedList list, Object obj);
public static void deleteAll(seqSortedList list, Object obj)
{ //从顺序存储的有序表list中删除与obj相同的所有元素
int k=list.find(obj, 1); //从第1个元素起查找，返回序号k
if(k==-1) return; //若查找失败则结束删除过程
int i=k+1; //从第k+1个元素起查找与obj相同的元素
while(i<=list.size()) { //若相同则继续向后查找，否则结束查找
if(list.value(i).equals(obj)) i++;
else break;
}
int c=i-k; //值为obj的元素序号为k~i-1，c保存其个数
for(int j=i; j<=list.size(); j++) //把后面的元素依次前移c个位置
list.modify(list.value(j), k++);
list.setSize(list.size()-c); //有序表的长度减少c
}
5．从顺序存储的有序线性表list中删除取值在obj1和obj2之间的所有元素，要求obj1
小于等于obj2，否则退出运行。
public static void deleteArea(seqSortedList list, Object obj1, Object obj2);
public static void deleteArea(seqSortedList list, Object obj1, Object obj2)
{ //从list中删除取值在[obj1, obj2]区间内的所有元素，要求obj1<=obj2
if(((Comparable)obj1).compareTo((Comparable)obj2)>0) {
System.out.println("参数值不合法，无法删除元素，退出程序运行.");
System.exit(1);
}
int i, k=1;
while(k<=list.size()) { //从头开始顺序查找满足要求的元素，序号为k
23 if(((Comparable)list.value(k)).compareTo((Comparable)obj1)<0) k++;
else break; //查找到区间[obj1,obj2]的起点元素的序号k则退出
}
if(k>list.size()) return; //若有序表中无区间内的元素则返回
i=k+1; //从k+1起连续查找区间内的元素
while(i<=list.size()) { //循环查找时若碰到大于obj2的元素则退出
if(((Comparable)list.value(i)).compareTo((Comparable)obj2)>0) break;
else i++;
}
int c=i-k; //满足[obj1,obj2]中的元素序号从k到i-1，c保存元素个数
for(int j=i; j<=list.size(); j++) //将后面所有元素依次前移c个位置
list.modify(list.value(j), k++);
list.setSize(list.size()-c); //设置删除后的有序表长度
}
3.
3.3.
3.8
88
8
使用
使用使用
使用链接
链接链接
链接存储的
存储的存储的
存储的有序
有序有序
有序线性表类
线性表类线性表类
线性表类linkSorted
linkSortedlinkSorted
linkSortedList
ListList
List的编程练习
的编程练习的编程练习
的编程练习
在一个任意设定的类中，不妨设定的类名为linkSortedListExtend，按照下列每小题的
要求和方法声明编写出相应的方法。为了减少算法的运行时间，有的算法需要采用指针（引
用），而不是象处理顺序存储的有序表那样调用现成的方法，因为在链表中读取任一个结点
的平均时间复杂度为O(n)，而在顺序表中为O(1)。
1．根据数组a中的所有元素建立并返回一个链接存储的有序线性表。
public static linkSortedList create(Object[] a);
public static linkSortedList create(Object[] a)
{ //根据数组a中的所有元素建立并返回一个链接存储的有序线性表
linkSortedList s=new linkSortedList(); //定义和创建一个空的有序表
for(int i=0; i
return s; //返回所建立的有序表
}
2．根据两个链接存储的有序线性表合并产生一个新的有序线性表。
public static linkSortedList merge(linkSortedList list1, linkSortedList list2);
public static linkSortedList merge(linkSortedList list1, linkSortedList list2)
{ //根据list1和list2合并生成一个新的有序表并返回
linkSortedList s=new linkSortedList(list1); //定义和创建一个链接有序表
Node p=(list2.prior()).next;
for(int i=1; i<=list2.size(); i++) { //依次向s中插入list2中的结点值
s.insert(p.element);
p=p.next;
}
return s; //返回所建立的有序表s
}
24
3．求出并返回链接存储的有序线性表list中的所有元素的最大值。
public static Comparable maximum(linkSortedList list);
public static Comparable maximum(linkSortedList list)
{ //求出并返回链接存储的有序表中的所有元素的最大值
if(list.size()==0) return null; //若有序表为空则返回空值
return (Comparable)list.value(list.size()); //返回最后一个元素的值
}
4．从链接存储的有序线性表list中删除与obj相同的所有元素。
public static void deleteAll(linkSortedList list, Object obj);
public static void deleteAll(linkSortedList list, Object obj)
{ //从链接存储的有序表list中删除与obj相同的所有元素
Node p=list.prior(), head=p, q=p.next; //q指向表头结点，p是q的前驱
while(q!=head) { //循环结束后，q结点的值等于obj
if(q.elem
ent.equals(obj)==false) {p=q; q=q.next;}
else break;
}
if(q==head) return; //有序表中没有值为obj的元素，算法结束返回
int c=1; //用c统计值为obj的元素的个数
Node r=q, s=q.next; //从q的后继结点起继续查找值为obj的结点
while(s!=head) { //循环结束后，s结点的值不等于obj
if(s.element.equals(obj)==true) {c++; r=s; s=s.next;}
else break;
}
p.next=r.next; //删除值为obj的所有结点，即把r的后继表链接到p之后
list.setSize(list.size()-c); //有序表的长度减少c
}
5．从链接存储的有序线性表list中删除取值在obj1和obj2之间的所有元素，要求obj1
小于等于obj2，否则退出运行。
public static void deleteArea(linkSortedList list, Object obj1, Object obj2);
public static void deleteArea(linkSortedList list, Object obj1, Object obj2)
{ //从list中删除取值在obj1和obj2之间的所有元素，要求obj1<=obj2
if(((Comparable)obj1).compareTo((Comparable)obj2)>0) {
System.out.println("参数值不合法，无法删除元素，退出程序运行.");
System.exit(1);
}
Node p=list.prior(), head=p, q=p.next; //q指向表头结点，p是q的前驱
while(q!=head) { //循环结束后，q结点的值刚好大于等于obj1
if(((Comparable)q.element).compareTo((Comparable)obj1)<0)
25 {p=q; q=q.next;}
else break;
}
if(q==head) return; //有序表中没有被删除的区域，算法结束返回
int c=1; //用c统计值为[obj1,obj2]区间内的元素的个数
Node r=q, s=q.next; //从q的后继结点起继续查找值小于等于obj2的结点
while(s!=head) { //循环结束后，s结点的值刚好大于obj2
if(((Comparable)s.element).compareTo((Comparable)obj2)>0) break;
else {c++; r=s; s=s.next;}
}
p.next=r.next; //删除q至r之间的所有结点，即把r的后继表链接到p后
list.setSize(list.size()-c); //有序表的长度减少c
}
3
33
3.
..
.9
99
9
编写解决约瑟夫问题的算法
编写解决约瑟夫问题的算法编写解决约瑟夫问题的算法
编写解决约瑟夫问题的算法
编写一个带有主函数的程序，其中包含两个静态成员方法，分别为使用顺序和链接存储
的线性表解决约瑟夫（Josephus）问题。约瑟夫的问题是：设有n个人围坐在一张圆桌周围，
现从某个人开始从1报数，数到m的人出列（即离开坐位，不参加以后的报数），接着从出
列的下一个人开始重新从1报数，
数到m的人又出列，如此下去直到所有人都出列为止，试
求出这n个人的出列次序。
例如，当n=8,m=4时，若从第一个人开始报数，假定n个人对应的编号依次为1、2、…、
n，则得到的出列次序为：4,8,5,2,1,3,7,6。
在每个解决约瑟夫问题的静态成员方法中，要求以整型对象n、m和s作为参数，n表示
开始参加报数的人数，m为下一次要出列的人所报出的数字序号，s为最开始报数的那个人的
编号。
注意：人的座位是首位相接的，所以报数是循环进行的，最后一个人报数后，接着是最
前面的一个人报数。
参考程序如下：
public class Chap3_15
{
static void seqJosephus(int n, int m, int s)
{ //使用顺序表解决约琵夫问题的算法，n为人数，每次报数到m出列
if(n<=0 || m<=0 || s<=0) {
System.out.println("参数值不合法，退出运行！");
System.exit(1);
}
sequenceList a=new sequenceList(n); //定义和创建一个线性表a
int i,k;
for(i=1; i<=n; i++) a.add(i,i); //插入n个元素，元素值依次为1~n
k=s; //给k赋初值为s,开始从编号为s的人起报数
for(i=1; i
if(k==0) k=a.size(); //若k的值为0则应修改为表尾的序号
26 System.out.print(a.value(k)+", "); //输出序号为k的元素值
a.remove(k); //从线性表中删除序号为k的元素
}
System.out.println(a.value(1)); //输出最后剩余的一个元素的值
}
static void linkJosephus(int n, int m, int s)
{ //使用链表解决约琵夫问题的算法，n为人数
if(n<=0 || m<=0 || s<=0) {
System.out.println("参数值不合法，退出运行！");
System.exit(1);
}
linkList a=new linkList(); //定义和创建一个空的线性链表a
int i,k;
for(i=n; i>=1; i--) a.add(i,1); //插入n个结点，结点值依次为1~n
Node p=a.prior(), q=p.next, head=p; //q指向表头结点，p为前驱
k=1; //给k赋初值1
while(k
if(q==head) {p=q; q=q.next;}//若q为附加表头结点，则移到表头
k++;
}
for(i=1; i