算法与数据结构实战实验——线性数据结构实现与应用（使用java）

实验目的——通过实验达到：
⑴ 理解和掌握线性结构的概念及其典型操作的算法思想；
⑵ 熟练掌握基本线性结构的链式存储结构及其操作的实现；
⑶ 理解和掌握受限线性结构——堆栈、队列的概念及其典型操作的算法思想、实现。

题目1：一元多项式的操作

设有两个一元多项式：
p(x)=p0+p1x+p2x2+···+pnxn
q(x)=q0+q1x+q2x2+···+qmxm
多项式项的系数为实数，指数为整数，设计实现一元多项式操作的程序：
① 多项式链表建立：以（系数，指数）方式输入项建立多项式，返回所建立的链表的头结点；
② 多项式排序：将所建立的多项式按指数非递减（从小到大）进行排序；
③ 多项式相加：实现两个多项式相加操作。操作生成一个新的多项式，原有的两个多项式不变，返回生成的多项式的头结点；
④ 多项式的输出；
⑤ 主函数通过调用多项式链表建立函数，输入两个多项式并分别输出；输出排序后的两个多项式；分别调用多项式相加函数实现多项式相加、相减操作，分别输出操作结果。

⑴ 所定义的数据结构:

class node{
int a;//系数
int b;//指数
node next=null;
node(int i,int j){
a=i;
b=j;
}
}

⑵ 主要操作算法思想或算法步骤:

package edu.dgut.experiment.one;
//数据结构
class node{
int a;//系数
int b;//指数
node next=null;
node(int i,int j){
a=i;
b=j;
}
}
//链表及其操作
public class Link {
node head=null;//头结点
//创建链表
/*Link(int n){
}*/
//添加结点
public void addNode(int a,int b){
node newNode=new node(a,b);
if(head==null) {//判断是否添加至头结点
head=newNode;
return;
}
//从尾部添加
node temp=head;
while(temp.next!=null) {
temp=temp.next;
}
temp.next=newNode;
}
//排序（冒泡）
public void sort() {
if(head == null || head.next == null) {
//链表为空或者仅有单个结点
//System.out.println("");
return;
}
node cur = head, tail = null;
while(cur.next != tail){
while(cur.next != tail){
if(cur.b > cur.next.b){
int tmp1 = cur.b;
cur.b = cur.next.b;
cur.next.b = tmp1;
int tmp2 = cur.a;
cur.a = cur.next.a;
cur.next.a = tmp2;
}
cur = cur.next;
}
tail = cur;
//下一次遍历的尾结点是当前结点
cur = head;
//遍历起始结点重置为头结点
}
return;
}
//输出
public void print() {
sort();//————以排序为前提
node cur=head;
//排序后的第一项
if(cur.a==1&&cur.b==1)
System.out.print("x");
else if(cur.a==1&&cur.b!=1)
System.out.print("x^"+cur.next.b);
else if(cur.a!=1&&cur.b==1)
System.out.print(cur.a+"x");
else {
System.out.print(cur.a+"x^"+cur.b);
}
//排序后第一项以后
while(cur.next!=null) {
if(cur.next.a==1)
System.out.print("+"+"x^"+cur.next.b);
else
System.out.print("+"+cur.next.a+"x^"+cur.next.b);
cur=cur.next;
}
}
//多项式相加
public node addLink(node h2) {
node h1=head;
Link newLink = new Link();
node cur1=h1,cur2=h2;
//将cur2中各项添加到cur1或newLink中的head
while(cur2!=null) {
boolean isAdd=false;
while(cur1!=null) {
if(cur1.b==cur2.b) {
cur1.a+=cur2.a;//添加到cur1
isAdd=true;
break;
}
cur1=cur1.next;
}
if(!isAdd) {//添加到newLink中的head
newLink.addNode(cur2.a, cur2.b);
}
cur1=h1;
cur2=cur2.next;
}
//将cur1各项添加到newLink中的head尾部
while(cur1!=null) {
newLink.addNode(cur1.a, cur1.b);
cur1=cur1.next;
}
newLink.sort();//排序
this.head=newLink.head;
return newLink.head;
}
public static void main(String[] args) {
System.out.println("多项式1：");
Link link1 = new Link();
link1.addNode(1, 1);
link1.addNode(4, 4);
link1.addNode(3, 3);
link1.sort();
link1.print();
System.out.println();
System.out.println("多项式2：");
Link link2 = new Link();
link2.addNode(2, 2);
link2.addNode(4, 4);
link2.addNode(3, 3);
link2.sort();
link2.print();
System.out.println();
System.out.println("多项式相加：");
link2.addLink(link1.head);
link2.print();
}
}

题目2：顺序循环队列的基本操作

设队列的元素类型为char，实现顺序循环队列的各种基本操作的程序：
① 初始化队列Q；
② 判断队列Q是否为空；
③ 入队操作。循环调用入队操作，将若干元素（不少于10个）入队；
④ 出队操作，出队一个元素，并输出该元素；
⑤ 输出队列元素个数；
⑥ 调用入队操作，依次入队4个元素；
⑦ 输出队列序列；
⑧ 主函数通过函数调用实现以上各项操作。

⑴ 所定义的数据结构:

class qnode{
char data;
qnode next=null;
qnode(char c){
this.data=c;
}
}

⑵ 主要操作算法思想或算法步骤:

package edu.dgut.experiment.one;
//数据结构
class qnode{
char data;
qnode next=null;
qnode(char c){
this.data=c;
}
}
//相关操作
public class Queue {
qnode head=null;
qnode tail=null;
int num=0;//队列元素个数
//初始化
Queue(){
head=tail;
}
//判空
public boolean isEmpty() {
if(head==null)
return true;
else
return false;
}
//入队
public void push(char c) {
qnode newNode = new qnode(c);
if(head==null) {
head=newNode;
tail=head;
num++;
return;
}
tail.next=newNode;
tail=tail.next;
num++;
}
//出队
//出队一个元素，并输出该元素
public void pop() {
if(head==null||num==0) {
System.out.println("队列为空！");
return;
}
qnode node=head;
System.out.println("出队："+node.data);
num--;//元素减一
head=head.next;//后移
node=null;
}
//队列元素个数
public int getQueueNum() {
return num;
}
//输出队列序列
public void print() {
int i=num;
int count=1;//元素个数计数器
qnode node=head;
while(i>0) {
System.out.println("第"+count+"个元素："+node.data);
node=node.next;
count++;
i--;
}
}
public static void main(String[] args) {
//创建队列
Queue Q = new Queue();
//判断队列是否为空
if(Q.isEmpty())
System.out.println("队列为空！");
else
System.out.println("队列不为空！");
//循环入队15个元素
for(int i=0;i<15;i++) {
Q.push('a');
}
//出队一个元素
Q.pop();
//输出队列元素个数
System.out.println("队列元素个数为："+Q.getQueueNum());
//入队4个元素
Q.push('A');
Q.push('B');
Q.push('C');
Q.push('D');
//输出队列序列
System.out.println("输出队列序列:");
Q.print();
}
}

最后

以上就是热心蜡烛为你收集整理的算法与数据结构实战实验——线性数据结构实现与应用（使用java）的全部内容，希望文章能够帮你解决算法与数据结构实战实验——线性数据结构实现与应用（使用java）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。