数据结构（Java语言描述）上机实训（全书1-10章）

第一章绪论

上机实训

1.设n为在算法前边定义的整数类型已赋值的变量，分析下列各算法中加下划线语句

的执行次数，并给出各算法的时间复杂度T(n)。

(1)inti=1,k=0;

While(i<n-1){

k=k+10*i;

i=i+1;

)

(2)inti=1fk=0;

do{

k=k+10*i;

i=i+1;

}while(i!=n);

(3)inti=1,j=1;

while(i<=n&&j<=n){

i=i+1;

j=j+1；

)

(4)intx=n;

inty=0;

while(x>=(y+l)*(y+1)){

y++；

)

(5)inti,j,k,x=0;

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

For(j=0;j<i;j++)

For(k=0;k<j;k++)

x=x+2;

参考答案：(1)O(n)(2)O(n)(3)O(n)(4)O(n1/2)(5)O(n3)

2.如下算法是用冒泡排序法对数组a中的n个整数类型的数据元素从小到大进行排序，

求该算法的时间复杂度。

voidbubbleSort(inta[]){

intn=a.length;

inti,j,temp,flag=l;

for(i=l;i<n&&flag==l;i++){

flag=0;

for(j=0;j<n-i;j++){

if(a[j]>a[j+l]){

flag=1;

temp=a[j];

a[j]=a[j+l];

a[j+1]=temp;

)

)

}

)

参考答案：0(1?)

3.下边算法是一个有n个数据元素的数组a中删除第pos个位置的数组元素，求该算

法的时间复杂度。

booleandelete(inta[],intpos){

intn=a.length;

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

returnfalse;//删除失败返回

for(intj=pos+l;j<n;j++){

a[j-l]=a[j];//顺次移位填补

}

returntrue;//删除成功返回

}

参考答案：O(n)

4.分析如下算法的空间复杂度。

staticvoidreversel(int[]a,int[]b){

intn=a.length;

for(inti=0;i<n;i++){

b[i]=a[n-l-i];

}

)

参考答案：O(n)

第二章线性表

上机实洌

1.编写一个顺序表类的成员函数，实现对顺序表循环右移k位的操作。即原来顺序表

为(ai,a2,an-k,aa-w,,,,,a„),循环向右移动k位后变成(an-w,•,,,an,ai,a2,•,,,a„-k)»

要求时间复杂度为0(n)o

参考答案：

packagesjsx.c02;

importjava.util.Arrays;

publicclassSequenceList<T>{

〃默认长度

privateintDEFAULT_SIZE=2;

〃定义一个数组用于保存莪性表的长度

privateObject[]elementData;

//用于保存数组长度

privateintcapacity;

//保存顺序表中当前元素的个数

privateintsize=0;

/**

*构造一个默认长度的空线性表

*/

publicSequenceList(){

capacity=DEFAULT_SIZE;

elementData=newObject[capacity];

}

/★★

*用一个初始化元素来创建线性表

*@paramelement初始化元素

*/

publicSequenceList(Telement){

this();

elementData[0]=element;

size++;

)

/**

*用一个元素和指定长度来创建线性表

*@paramelement元素

*@paraminitSize指定长度

publicSequenceList(Telement,intinitSize){

capacity=1;

if(capacity<initSize){

capacity=initSize+2;

)

elementData=newObject[capacity];

elementData[0]=element;

size++;

)

/**

*向顺序表中插入元素

*@paramelement待插入的元素

*@paramindex待插入的位置

*/

publicvoidinsert(Telement,intindex){

if(index<0||index>size){

thrownew工ndexOutOfBoundsException(”数组越界异常”)；

}

ensureCapacity(size+1);

//把index以后的元素都后移一位

System.arraycopy(elementData,index,elementData,index+1,

size-index);

elementData[index]=element;

size++;

)

/**

*表长

*@return

*/

publicintlength(){

returnsize;

)

/★★

*向表中添加元素

*@paramelement

*/

publicvoidadd(Telement){

insert(element,size);

}

/**

*得到线性表存储的对象

*@paramindex获得的位置

*@return得到的结果

publicTget(intindex){

if(index<0||index>size)

thrownewIndexOutOfBoundsException("数组越界异常”);

return(T)elementData[index];

)

/★★

*判断线性表是否为空

大@return

*/

publicbooleanisEmpty(){

returnsize==0;

)

/**

★清空线性表

*/

publicvoidclear(){

Arrays.fill(elementData,null);

size=0;

)

/★*

*获取指定位置的前一个元素

*@paramindex线性表位置，若是取线性表最后一个元素，必须index=size,

*size为线性表元素个数

*©return

*/

publicTpriorElem(intindex){

if(index>O&&index<size+l)

return(T)elementData[index-1];

else{

thrownew工ndexOutOfBoundsException("数组越界异常”)；

}

)

/**

*删除指定位置的元素

*@paramindex

*/

publicvoiddelete(intindex){

if(index<0||index>size-l){

thrownew工ndexOutOfBoundsException("数组越界异常”)；

}else{

//把数组前移一位

System.arraycopy(elementData,index+1,elementData,index,

size-index-1);

size一一;

//清空最后一个元素

elementData[size]=null;

)

)

*获取指定线性表位置的后一个元素

大@paramindex线性表位置，若是取线性表第0个元素，必须index=-l

*@return

*/

publicTnextElem(intindex){

if(index==-l){

return(T)elementData[0];

}

elseif(index<size-l&&index>-l){

return(T)elementData[index+1];

}else{

thrownewIndexOutOfBoundsException("数组越界异常”);

)

)

*确保数组所需长度大于数组原有长度

大@paramincapacity数组所需长度

*/

privatevoidensureCapacity(intinCapacity){

if(mCapacity>capacity){

capacity=mCapacity+2;

elementData=Arrays.copyOf(elementData,capacity);

}

)

/**

*实现对顺序表元素的输出

*/

publicvoiddisplay(){

for(inti=0;i<this.length();i++){

System.out.print(this.get(i)+”n);

)

System.out.printIn();

)

/**

★实现对顺序表循环右移k位的操作

*@paramk循环右移的位数

*/

publicvoidshit(intk){

intn=this.length(),p=0,i,j,1;

Objecttemp;

for(i=l;i<=k;i++)

if(n%i==0&&k%i==0)//求n和k的最大公约数p

p=i；

for(i=0;i<p;i++){

j=i；

1=(i+n-k)%n;

temp=this.elementData[i];

while(1!=i){

this.elementData[j]=this.elementData[1];

j=l;

l=(j+n-k)%n;

)//循环右移一步

this.elementData[j]=temp;

}

)

)

//测试

publicclassMainOl{

publicstaticvoidmain(String[]args)throwsException{

SqListL=newSqList(10);

for(inti=0;i<=8;i++)

L.insert(i,i);

System.out.printIn("右移前顺序表中的各个数据元素为：”);

L.display();

L.shit(3);

System.out.printIn("右移3位后顺序表中的各个数据元素为：”);

L.display();

)

)

2.编写两个单链表类的成员函数，分别实现链表反转、查找单链表的中间节点两个功

能。

参考答案：

publicclassLinkList<T>{

//定义一个内部类Node,代表链表的节点

privateclassNode{

privateTdata;//保存数据

privateNodenext;//指向下个节点的引用

//无参构造器

publicNode(){

}

//初始化全部属性的构造器

publicNode(Tdata,Nodenext){

this.data=data;

this.next=next;

)

)

privateNodeheader;//保存头结点

privateNodetail;//保存尾节点

privateintsize;//保存已含有的节点数

//创建空链表

publicLinkList(){

header=null;

tail=null;

)

//已指定数据元素创建链表，只有一个元素

publicLinkList(Telement){

header=newNode(element,null);

//只有一个节点，header,tail都指向该节点

tail=header;

size++;

)

//返回链表的长度

publicintlength(){

returnsize;

)

//获取指定索引处的元素

publicTget(intindex){

returnthis.getNodeBylndex(index).data;

}

//获取指定位置的节点

privateNodegetNodeBylndex(intindex){

if(index<0IIindex>size-1){

thrownew工nd㊀xOutOfB。undsExcepti。n("索弓|超出线性表范围”);

)

Nodecurrent=head㊀r;//从header开始遍历

for(inti=0;i<size&¤t!=null;

i++zcurrent=current.next){

if(i==index){

returncurrent;

)

)

returnnull;

}

//按值查找所在位置

publicintlocate(Telement){

Nodecurrent=header;

for(inti=0;i<size&¤t!=null;i++,

current=current.next){

if(current.data.equals(element)){

returni;

)

)

return-1;

}

//指定位置插入元素

publicvoidinsert(Telement,intindex){

if(index<0||index>size){

thrownew工ndexOutOfBoundsException("索弓I超出线性表范围”);

)

//如果是空链表

if(header==null){

add(element);

}

else{

//当index为0时，即在链表头处插入

if(0==index){

addAtHead(element);

)

else{

Nodeprev=getNodeBylndex(index-1);//获取前一个节点

//让prev的next指向新节点，新节点的next指向原来prev的下一

个节点

prev.next=newNode(element,prev.next);

size++;

)

}

)

//在尾部插入元素

publicvoidadd(Telement){

//如果链表是空的

if(header==null){

header=newNode(element,null);

//只有一个节点，headwe,tail都该指向该节点

tail=header;

)

else{

NodenewNode=newNode(element,null);//仓惟新节点

tail.next=newNode;//尾节点的next指向新节点

tail=n㊀wNode;//将新节点作为尾节点

)

size++;

)

//头部插入

publicvoidaddAtHead(Telement){

//创建新节点，让新节点的next指向header

〃并以新节点作为新的header

NodenewNode=newNode(element,null);

newNode.next=header;

header=newNode;

//若插入前是空表

if(tail==null){

tail=header;

}

size++;

)

//删除指定索引处的元素

publicTdelete(intindex){

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

thrownew工ndexOutOfBoundsException("索弓I超出线性表范围”);

)

Nodedel=null;

//若要删除的是头节点

if(index==0){

del=header;

header=header.next;

}

else{

Nodeprev=getNodeBylndex(index-1);//获取待删除节点的前一

个节点

del=prev.next;//获取待删除节点

prev.next=del.next;

del.next=null;//将被删除节点的next引用置为空

}

size--;

returndel.data;

}

//删除最后一个元素

publicTremove(){

returndelete(size-1);

)

//判断线性表是否为空

publicbooleanisEmpty(){

returnsize==0;

}

//清空线性表

publicvoidclear(){

//将headerrtail置为null

header=null;

tail=null;

size=0;

}

publicStringtoString(){

if(isEmpty()){

returnH[]n;

}

else{

StringBuildersb=newStringBuilder(n[n);

for(Nodecurrent=header;current!=null;current=

current.next){

sb.append(current.data.toString()+”,H);

)

intlen=sb.length();

returnsb.delete(len-2,len).append(”]”).toString();

)

/★★

*链表反转

*@return

*/

publicNodeReverselteratively(){

NodepReversedHead=this.header;

NodepNode=this.header;

NodepPrev=null;

while(pNode!=null){

NodepNext=pNode.next;

if(pNext==null){

pReversedHead=pNode;

)

pNode.next=pPrev;

pPrev=pNode;

pNode=pNext;

}

this.header=pReversedHead;

returnthis.header;

}

/**

*查找单链表的中间节点

*@return

*/

publicNodeSearchMid(){

Nodep=this.header,q=this.header;

while(p!=null&&p.next!=null&&p.next.next!=null)

p=p.next.next;

q=q.next;

)

System.out.printIn(nMid:n+q.data);

returnq;

)

)

//测试类

publicclassMain02{

publicstaticvoidmain(String[]args)throwsException{

//测试构造函数

LinkList<Integer>list=newLinkList(1);

//测试添加元素

for(inti=2;i<=9;i++)

list.add(i);

System.out.printIn(list);

//链表反转

list.ReverseIteratively();

System.out.printIn(list);

//查找单链表的中间节点

list.SearchMid();

System.out.printIn(list);

第三章栈和队列

上机实洌

1.编写一个程序，用两个队列实现一个栈。

参考答案：

packagec03;

importjava.util.LinkedList;

importjava.util.Queue;

publicclassMainOl{

publicstaticvoidmain(String[]args){

push(l);

push(2);

push⑶;

pop();

push(4);

pop0;

pop0;

)

privatestaticQueue<Object>queuel=newLinkedList<Object>();

privatestaticQueue<Object>queue2=newLinkedList<Object>();

publicstaticvoidpush(Objectitem){

if(!queue1.isEmpty())

queue1.offer(item);

else

queue2.offer(item);

System.out.printin("入栈元素为："+item);

)

publicstaticvoidpop(){

if(!isEmpty()){

if(queue1.isEmpty()){

while(queue2.size()>l){

queue1.offer(queue2.poll());

)

System,out.printin("出栈元素为："+queue2.poll());

}else{

while(queue1.size()>l){

queue2.offer(queuel.poll());

)

System.out.printin("出栈元素为："+queuel.poll());

)

)

else

thrownewRuntimeException("栈为空，无法执行出栈操作”)；

)

privatestaticbooleanisEmptyO{

returnqueuel.isEmpty()&&queue2.isEmptyO;

)

}

2.编写一个程序，输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个

序列是否可能为该栈的弹出顺序。

参考答案：

packagec03;

importjava.util.Arrays;

importjava.util.Stack;

publicclassMain02{

publicstaticvoidmain(String[]args){

int[]arrl={1,2,3,4,5};

int[]arr2={4,5,3,2,1};

System,out.printIn("进栈序列："+Arrays.toString(arrl));

System.out.printing进栈序列：“+Arrays.toString(arr2));

System,out.printin(“判断结果：*+IsPopOrder(arrl,arr2));

)

publicstaticbooleanIsPopOrder(int[]pushA,int口popA){

Stack<Integer>stack=newStackO();

for(inti=0,j=0;i<pushA.length;){

stack,push(pushA[i++]);

while(!stack.isEmptyO&&stack,peek()=popA[j]&&j<popA.length)

stack,pop();

j++；

}

returnstack.isEmptyO;

第四章串

上机实训

1.已知两个串：sl=，zfgcdbcabcadrz/,s2="abc”,试求两个串的长度，判断串s2是否是

串si的子串，并指出串s2在串si中的位置。

参考答案：

publicclassMain02{

publicstaticvoidmain(String[]args){

Stringsi="I'mastudent”,s2="student”,s3="teacher”;

System,out.println(sl.indexOf(s2));

System,out.println(sl.indexOf(s3));

System.out.printin(s2.charAt(3));

System,out.println(s3.substring(2,5));

)

)

sl:14;s2:3

s2在si的开始位置是：9

2.已知：sl=Tmastudent”,s2=〃student”,s3="teacher”,试求下列各运算的结果：

si.indexOf(s2);

si.indexOf(s3);

s2.charAt(3);

s3.substring(2,5);

参考答案：

publicclassMain02{

publicstaticvoidmain(String[]args){

Stringsi=T'mastudent”,s2="student”,s3="teacher”;

System,out.println(sl.indexOf(s2));

System,out.println(sl.indexOf(s3));

System,out.println(s2.charAt(3));

System,out.println(s3.substring(2,5));

}

)

6

-1

d

ach

3.设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s

的子串。如果是，输出子串所在位置(第一个字符)，否则输出0。

参考答案：

publicclassMain03{

publicstaticintstrMatch(chart]s,chart]t){

inti=0,j=0;

intm=s.length,n=t.length;

if(m<n)

return0;

else{

for(i=0;i<m;i++){

for(j=0;j<n;j++){

if(s[i+j]!=t[j])

break;

else{

if(j==n-l&&s[i+j]=t[j])

returni+1;

)

}

)

)

return0;

}

publicstaticvoidmain(String[]args){

intm,n;

System.out.printin("请输入两个字符串的长度M和N");

Scannersc=newScanner(System,in);

m二sc.nextlnt();

n=sc.nextlnt();sc.nextLine();

System,out.printin("请输入第一个长度为的字符串：“);

char[]s=sc.nextLine().toCharArray();

System.out.printin("请输入第二个长度为"+n+”的字符串：”)；

char[]t=sc.nextLine().toCharArray();

System,out.printint));

)

)

4.输入一个字符串，内有数字和非数字字符，如：akl23x45617960?302gef4563,将其中

连续的数字作为一个整体，依次存放到一数组a中，例如123放入a[01,456放入a[l],…。

编程统计其共有多少个整数，并输出这些数。

参考答案：

importjava.util.Scanner;

publicclassMain04{

publicstaticvoidmain(String[]args){

Scannersc=newScanner(System./n);

System.oUprinllnC'请输入字符串:")；

char[]s=sc.nextLine().toCharAiTay();

int[]a=newint[100];

booleanflag=false;

Stringtmp=nn;

intc=0;

for(inti=O;i<s.length;i++){

if(flag){

if(s[i]>=,0,&&s[i]<=,9,){

tmp+=s[i];

}else{

a[c]=Integer

C++；

flag=false;

tmp=,,n;

)

}else{

if(s[i]>=<0,&&s[i]<=,9,){

tmp+=s[i];

flag=true;

)

)

if(i==s.length-l&&flag二二true){

a|cj=Integer.ptzwe/(tmp);

C++；

)

)

System.ow/.println(c);

for(inti=0;i<c;i++){

System.^M/.print(a[i]+"")；

5.编写程序，统计在输入字符串中各个不同字符出现的频度。

参考答案：

importjava.util.Scanner;

publicclassMain05{

publicstaticvoidmain(String[]args){

Scannersc=newScanner(System.nj)；

System.o〃f.println("请输入字符串:");

char[]ch=sc.nextLine().toCharArray();

char[]s=newchar[100J;

int[]num=newint[100];

inti=0,j=0,n=0;

for(i=0;i<ch.length;i++){

for(j=0;j<n;j++)

if(ch[i]==s[j])break;

if(j<n){

num[j]++;

}else{

s[n]=ch[i];

num[n]=l;

n++;

)

}

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

System.o〃£.println(“字符"+s[i]+”出现了”+num[i]+”次");

第五章多维数组和广义表

上机实洌

1.如果矩阵A中存在这样的一个元素A[i,j]满足条件：A[i,jJ是第i行中值最小的元素，

且又是第j列中值最大的元素，此时则称之为该矩阵的一个马鞍点。请编程查找出M*N的

矩阵A中的所有马鞍点。

参考答案：

importjava.util.Scanner;

publicclassMainOl{

publicstaticvoidmain(String[]args){

Scannersc=newScanner(System.in);

intm=sc.nextlnt();

intn=sc.nextlnt();

int[][]a=newint[m][n];//定义M*N的数组/数据元素的输入

for(inti=0;i<m;i++){

for(intj=0;j<n;j++){

a[i][j]=sc.nextlnt();

)

}

int[]R=newint[m];

int[]C=newint[n];

.找每行的最小值并保存到数组R中

for(inti=0;i<m;i++){

R[i]=a[i][0];

for(intj=l;j<n;j++){

if(R[i]>a[i][j]){R[i]=a[i][j];}

)

}

//2.找每列的最大值并保存到数组C中

for(intj=0;j<n;j++){

C[j]=a[0][j];

for(inti=l;i<m;i++){

if(C[j]<a[i][j]){C[j]=a[i][j];}

)

)

//3.遍历每个元素a[i][j],与R[i]和C[j]的值是否相等，如果相等则是马

鞍点并输出

for(inti=0;i<m;i++){

for(intj=0;j<n;j++){

if(a[i][j]==R[i]&&a[i][j]==C[j])

System.out.printin("第"+(i+1)+”行，第”+(j+1)+”列：

n+a[i][j]);

)

)

}

2.编写程序实现广义表以下相关操作：广义表的构造、求广义表的深度、求广义表的

长度、按照深度优先顺序打印广义表、求广义表表头、求广义表表尾。

参考答案：

importjava.util.Stack;

/*★

*广义表操作：

*1、广义表的构造：

*1.1构造一个空的广义表

*1.2根据现有的广义表，构造一个新的广义表

*1.3根据广义表字符串构造一个广义表

*2、广义表的深度

*3、广义表的长度

*4、按照深度优先顺序打印广义表

*5、求广义表表头

*6、求广义表表尾

*

*/

publicclassGeneralizedTable{

publicstaticfinalintTAG_ITEM=0;//原子节点

publicstaticfinalintTAG_TABLE=1;//表节点

/*

大广义表支持的符号包括，，尸，U，，，}，，

*广义表表示符号，使用字符串构造广义表时第一个字符必须是，「，T，L之

一并以D之一结束，

*并且各符号相对应

*/

privatecharmStartSymb=1(1;

privatecharmEndSymb=')1;

privateNodemGenTable;

publicGeneralizedTable(){

mGenTable=newNode(null,null,TAG_TABLE,null);

)

//使用广义表src构造一个新的广义表

publicGeneralizedTable(GeneralizedTablesrc){

if(src!=null){

mGenTable=src.mGenTable;

)

)

/**

*@paramgenTable

*/

publicGeneralizedTable(StringgenTable){

if(genTable==null){

thrownewNullPointerException(

"genTableisnullinconstructor

GeneralizedTable!・,•”);

}

initTable(genTable);

)

privatevoidinitTable(StringgenTable){

Stringts=genTable.replaceAll(n\\sn,n");

intlen=ts.length();

Stack<Character>symbStack=newStack<Character>();

Stack<Node>nodeStck=newStack<Node>();

initSymbolicCharactor(ts);

mGenTable=newNode(null,null,TAG_TABLEZnull);

NodeitemNode,tableNode=mGenTable,tmpNode;

for(inti=0;i<len;i++){

if(ts.charAt(i)==mStartSymb){

tmpNode=newNode(null,null,TAG_TABLE,null);

//tableNode=tableNode.mPt;

symbStack.push(ts.charAt(i));

if(symbStack.size()>1){

nodeStck.push(tableNode);

tableNode.mPh=tmpNode;

tableNode=tableNode.mPh;

}else{

tableNode.mPt=tinpNocie;

tableNode=tableNode.mPt;

)

}elseif(ts.charAt(i)==mEndSymb){

if(symbStack.isEmpty()){

thrownewIllegalArgumentException(

nIllegalArgumentExceptioninconstructor

GeneralizedTable!..

}

if(symbStack.size()>1){

tableNode=nodeStck.pop();

}

symbStack.pop();

}elseif(ts.charAt(i)==，，'){

tableNode.mPt=newNode(null,null,TAG_TABLEfnull);

tableNode=tableNode.mPt;

}else{

itemNode=newNode(null,null,TAG__ITEM,ts.charAt(i));

tableNode.mPh=itemNode;

)

}

if(!symbStack.isEmpty()){

thrownewIllegalArgumentException(

nIllegalArgumentExceptioninconstructor

GeneralizedTable!・・.");

}

)

privatevoidinitSymbolicCharactor(Stringts){

mStartSymb=ts.charAt(0);

switch(mStartSymb){

case'(':

mEndSymb=11;

break;

case,{1：

mEndSymb='}';

break;

case1[1:

mEndSymb=1]f；

break;

default:

thrownewIllegalArgumentException(

nIllegalArgumentException--->

initSymbolicCharactor0);

)

}

publicvoidprint(){

print(mGenTable);

)

privatevoidprint(Nodenode){

if(node==null){

return;

)

if(node.mTag==0){

System.out.print(node.mData.toString()+”\tn);

}

print(node.mPh);

print(node.mPt);

}

publicintdepth(){//广义表的深度

if(mGenTable==null){

thrownewNullPointerException(nGeneralizedTableis

null!,,-->methoddepth'*);

)

returndepth(mGenTable);

)

privateintdepth(Nodenode){

if(node==null||node.mTag==TAG_ITEM){

retu