武汉纺织大学《数据结构》实验报告

班级：  12  级     专业  班   姓名：          序号：

实验时间：  20##  年 4  月 4  日    指导教师：   宋泽源  

 

实验一：线性结构的基本操作

一、实验目的：

  1、熟悉Java 上机环境，掌握Java语言编程方法，熟练运用Java语言实现数据结构设计和算法设计。

2、掌握线性表的顺序存储结构和链式存储结构的定义与基本操作，并能用Java语言实现线性表基本功能。

3、掌握栈、队列的存储结构与基本操作，并能利用该结构编写算法解决实际问题。

二、实验内容：

  1、编写一个Java语言程序，利用线性表实现约瑟夫环问题，参考书本程序示例【例2.1】，完善该程序并运行。

    实验步骤：

    ①、在Java编辑环境中新建程序，根据【例2.1】输入完整程序内容，并保存和编译；

    ②、运行程序，输入约瑟夫环长度number、起始位置start、计数值distance；

    ③、依次输入约瑟夫环中number个数据元素；

    ④、输出约瑟夫环执行过程。

2、编写一个程序，利用栈解决递归问题，实现n阶Hanoi塔问题。

  实验步骤：

    ①、在Java编辑环境中新建程序，输入n阶Hanoi塔程序内容，并保存和编译；

  ②、运行程序，输入盘子数目n。

  ③、输出n阶Hanoi塔问题解决过程。

参考程序如下：

import java.util.Scanner;
public class MethodOfHanoi{
public static void main(String[] args){
System.out.println(“请输入盘子数目：”);
Scanner scan=new Scanner(System.in);                  //输入盘子数目
int number=scan.nextInt();
hanoi(number,‘A’,‘B’,‘C’);                    //调用hanoi方法
}
public static void hanoi(int num, char a,char b,char c){
if (num==1)                                 //只有一个盘子，直接移动

{
move(a,c);
}else{
hanoi(num-1,a,c,b);                             //递归调用
move(a,c);
hanoi(num-1,b,a,c);                            //递归调用
}
}                                                                               

public static void move(char a,char c)       //移动过程方法
{    
 System.out.println("从 "+a+" 移到 "+c);
 }                                                                    }

3、编写一个程序，利用Java语言建立一个空队列，如果输入奇数，则奇数入队列；如果输入偶数，则队列中的第一个元素出队列；如果输入0，则退出程序。

实验步骤：

    ①、在Java编辑环境中新建程序，输入程序内容，并保存和编译；

  ②、运行程序，输入数据并进行相应队列操作。

  ③、输出每次输入数据后的队列结果。

三、操作步骤：

1．代码：

import java.util.ArrayList;

import java.util.List;

publicclass  YSfh{

public YSfh(int number, int start, int distance) {

List<String> list = new ArrayList<String>(number);

for (int i = 0; i < number; i++)

list.add((char) ('A' + i) + "");

System.out

.print("约瑟夫环(" + number + "," + start + "," + distance + "),");

System.out.print(list.toString());

int i = start;

while (list.size() > 1) {

i = (i + distance - 1) % list.size();

System.out.print("删除" + list.remove(i).toString() + ",");

System.out.print(list.toString());

}

System.out.print("被赦免者是" + list.get(0).toString());

}

publicstaticvoid main(String args[]) {

new YSfh(5, 0, 2);

}

}

运行结果：

2.代码：

import java.util.Scanner;

publicclass MethodOfHanoi{

publicstaticvoid main(String[] args){

System.out.println("请输入盘子数目:");

Scanner scan=new Scanner(System.in);                  //输入盘子数目

int number=scan.nextInt();

hanoi(number,'A','B','C');                 

}

publicstaticvoid hanoi(int num, char a,char b,char c){

if (num==1)                                 //只有一个盘子，直接移动

{

move(a,c);

}else{

hanoi(num-1,a,c,b);                             //递归调用

move(a,c);

hanoi(num-1,b,a,c);                            //递归调用

}

}                                                                                

publicstaticvoid move(char a,char c)       //移动过程方法

{   

 System.out.println("从 "+a+" 移到 "+c);

 }                                     

}

运行结果：

3.代码

QQueue.java

publicinterface QQueue<T> {

    boolean isEmpty();

    boolean enqueue(T x);

    T dequeue();

}

SeqQueue.java

publicclass SeqQueue<T> implements QQueue<T> {

    private Object element[];

    privateint front, rear;

    public SeqQueue(int length) {

       if (length < 64)

           length = 64;

       this.element = new Object[Math.abs(length)];

       this.front = this.rear = 0;

    }

    public SeqQueue() {

       this(64);

    }

    publicboolean isEmpty() {

       returnthis.front == this.rear;

    }

    publicboolean enqueue(T x) {

       if (x == null)

           returnfalse;

       if (this.front == (this.rear + 1) % this.element.length) {

           Object[] temp = this.element;

           this.element = new Object[temp.length * 2];

           int i = this.front, j = 0;

           while (i != this.rear) {

              this.element[j] = temp[i];

              i = (i + 1) % temp.length;

              j++;

           }

           this.front = 0;

           this.rear = j;

           returntrue;

       }

       this.element[this.rear] = x;

       this.rear = (this.rear + 1) % this.element.length;

       returntrue;

    }

    public T dequeue() {

       if (isEmpty())

           returnnull;

       T temp = (T) this.element[this.front];

       this.front = (this.front + 1) % this.element.length;

       return temp;

    }

    public String toString() {

       String str = "(";

       if (!isEmpty()) {

           str += this.element[this.front].toString();

           int i = (this.front + 1) % this.element.length;

           while (i != this.rear) {

              str += "," + this.element[i].toString();

              i = (i + 1) % this.element.length;

           }

       }

       return str + ")";

    }

}

ts3.java

import java.util.Scanner;

publicclass ts3{

    publicstaticvoid main(String[] args) {

       Scanner in = new Scanner(System.in);

       SeqQueue<Integer> queue = new SeqQueue(64);

       int num = -1;

      

       while(num != 0) {

           num = in.nextInt();

          

           if (num % 2 == 0) {

              if (queue.dequeue() == null) {

                  System.out.println("当前队列为空！");

              }

           } else {

              if (!queue.enqueue(num)) {

                  System.out.println("当前队列满！");

               }

           }

           System.out.println("当前队列:" + queue.toString())       

}

}

}

四、实验收获和建议：

通过这次实验，完成了三个具体的操作任务，对课堂上学到的知识有了进一步的了解，虽然有些地方还不是很懂，通过与其他同学的交流，更深入的理解了线性表，串，栈，队列的相关学习内容

 

第二篇：天津理工大学数据结构实验报告1

计算机科学与工程系

计算机科学与工程系

2

计算机科学与工程系

附录（可包括源程序清单或其它说明）

#include<iostream.h>

#include<stdlib.h>

#include"stdio.h"

typedef struct LNode{ //链表类型

int data;

struct LNode *next;

}LNode,*LinkList;

void createLink(LinkList &L,int n); //创建链表 void printList(LinkList L,int n); //输出链表

void Josephus(LinkList &L,int s,int m); //约瑟夫环 void createLink(LinkList &L,int n){

LinkList p,r;

L=(LinkList)malloc(sizeof(LNode));

r=(LinkList)malloc(sizeof(LNode));

r=L;

L->data=1;

L->next=NULL;

for(int i=2;i<=n;i++){

p=(LinkList)malloc(sizeof(LNode)); p->data=i;

p->next=NULL;

r->next=p;

r=p;

}

r->next=L;

}

void Josephus(LinkList &L,int s,int m){

LinkList p,q;

int count=1,t;

p=L;

for(int i=1;i<s;i++)

p=p->next;

while(p->next!=p){

if(count==m){

q=p->next;

p->next=p->next->next;

cout<<p->data<<" ";

t=p->data;

p->data=q->data;

delete q;

count=1;

}

count++;

3

计算机科学与工程系

p=p->next;

}

cout<<p->data<<endl;

delete p;

}

void printList(LinkList L,int n){

LinkList p;

p=L;

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

cout<<p->data<<" ";

p=p->next;

}

cout<<endl;

}

void main(){

LinkList L;

int n,s,m;

cout<<"请输入Josephus环所需要的总人数n，起始点s，数过的人数m"<<endl; cin>>n;

cin>>s;

cin>>m;

createLink(L,n);

cout<<"链表输出：";

printList(L,n);

cout<<"约瑟夫环的出圈顺序：";

Josephus(L,s,m);

}

运行结果：

1. 当n=9，s=1，m=5 时

2. 当n=9，s=1，m=10 时

4