数据结构实验二 线性表

一、实验目的

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

二、实验相关知识

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

三、实验内容与要求

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

例1：(2+3x-3x⁴)*(4x²+6x⁶ )= (8x²+12x³+18x⁷-18x¹⁰)

【测试用例】

输入	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(n³)

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;
}

【运行结果】

五、实验心得体会

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