open-graph-logo

189 次

一、实验目的

  1. 掌握线性表的逻辑结构;
  2. 顺序表和链表的基本操作的实现;
  3. 掌握利用C/C++编程语言实现数据结构的编程方法;
  4. 通过上机时间加强利用数据结构解决实际应用问题的能力;

二、实验相关知识

  1. 线性表的顺序存储结构的实现;
  2. 线性表的链式存储结构的实现;
  3. 线性表的应用——一元多项式的表示及相加。

三、实验内容与要求

1.利用顺序表或链表表示两个一元多项式,并完成两多项式的乘法运算。按指数的升序输入两个一元多项式polya与polyb各项的指数和系数,且以输入0 0结束。输出两一元多项式乘积的一元多项式polyc,并进行算法时间复杂度的分析

例1:(2+3x-3x4)*(4x2+6x6 )= (8x2+12x3+18x7-18x10)

【测试用例】

输入 0 2 1 3 4 -3 0 0 2 4 6 6 0 0 0 2 1 3 2 -3 0 0 1 1 2 4 0 0
输出 2 8 3 12 7 18 10 -18 1 2 2 11 3 9 4 -12

【设计要求】在给出的代码素材polymul.cpp文件中补充完整以下函数,实现多项式相乘的计算。

void polyadd(Polylist poly,int coef,int exp)

void  polymul(Polylist polya, Polylist polyb,Polylist polyc)

2.利用循环单链表求解约瑟夫环问题(即n个人围成一个圆圈,然后从第一个人开始,按:1,2,3,…,m报数,数到m的人出圈,并有出圈者的下一个人重新开始报数,数到m又要出圈,如此类推,直到所有人都出圈,打印出圈的次序,其中n和m为输入数据)

【测试用例】

输入 9 3 6 2
输出 3,6,9,4,8,5,2,7,1 2 4 6 3 1 5

【设计要求】在给出的代码素材josephus.cppp文件中补充完整以下函数,求解约瑟夫环中出列的人的编号。

link creatlink(int n)//创建值为1~n的n个结点的不带头结点的循环单链表

void josephus(link joselink,int n,int m)//用循环链表求解约瑟夫环

Node * move(Node *p,int i)//p指针向前走i步

四、程序代码及运行结果

1、【程序代码】

void polyadd(Polylist poly,int coef,int exp)
{ 
   	Polylist s;
	s = (Polynode *)malloc(sizeof(Polynode));
	s->coef = coef;
	s->exp = exp;
	Polynode *p;
	p = poly->next;
	bool flag = false;
	while (p != NULL)
	{
		if (p->exp == exp)
		{
			p->coef += coef;
			flag = true;
			break;
		}
		p = p->next;
	}
	if (flag == false)
	{
		s->next = poly->next;
		poly->next = s;
	}
}

void  polymul(Polylist polya, Polylist polyb,Polylist polyc)
{  
 	Polynode *p = polya->next;
	while (p != NULL)
	{
		polyadd(polyc, p->coef, p->exp);
		p = p->next;
	}
	p = polyb->next;
	while (p != NULL)
	{
		polyadd(polyc, p->coef, p->exp);
		p = p->next;
	}
}

【运行结果】

【算法时间复杂度分析】

T = O(n3)

2、【程序代码】

link creatlink(int n)
{
	link joselink, current, s;
	joselink = (Node *)malloc(sizeof(Node));
	current = (Node *)malloc(sizeof(Node));
	current = joselink;
	joselink->next = NULL;
	joselink->data = 1;
	while (current->data < n)
	{
		s = (Node *)malloc(sizeof(Node));
		s->data = current->data + 1;
		current->next = s;
		current = current->next;

	}
	current->next = joselink;
	return joselink;
}

void josephus(link joselink, int n, int m)
{
	link p;
	p = (Node *)malloc(sizeof(Node));
	p->next = joselink;
	int i = 0;
	for (; p->next != NULL; p = p->next)
	{
		i++;
		if (i%m == 0)
		{
			i = 1;
			printf("%d ", p->next->data);
			p->next = p->next->next;
		}
		if (p->next == p)
		{
			printf("%d", p->data);
			return;
		}
	}
}

Node * move(Node * p, int i)
{
	link start = p;
	while (i--)
	{
		p = p->next;
	}
	return p;
}

【运行结果】

五、实验心得体会

学习到有关链表的知识,体会到链表在增加和删除的方便性。

赞赏

微信赞赏支付宝赞赏

评论

电子邮件地址不会被公开。 必填项已用*标注

CAPTCHAis initialing...

%d 博主赞过: