1. 首页
  2. 文章中心
  3. 数据结构

数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式

62 阅读 0 评论
我是靠谱客的博主 怕黑水杯，最近开发中收集的这篇文章主要介绍数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

目录

        • 约瑟夫环的不同玩法
        • 一元多项式的各种操作

约瑟夫环的不同玩法

约瑟夫环作为数据结构的经典问题，本来就会演化为各种各样的问题，我前面也写了用三种方法实现约瑟夫环问题，请点击传送门
这边的话，是我们老师给了我们一个上机实验的任务，然后这里是对约瑟夫环问题进行了一点小小的改变，不变实质，变问题。
第一个问题

编号为1，2，…，n的n个人按顺时针方向围坐在一张圆桌周围，每人持有一个密码（正整数）。一开始任选一个正整数m作为报数上限值，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数，报m的那个人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，数到m的那个人又出列；如此下去，直至圆桌周围的人全部出列为止。要求按出列顺序输出n个人的编号。

我们实现约瑟夫环的思维是，对一个循环的结构不断遍历，并且遍历到一定的次数，我们就弹出该元素，那么第一个问题，并不难解决，我们只要每一次遍历都改变这个一定次数就可以了。
代码：

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
	int num[2];
	struct node *next;
}list;
list * creat(int n);
void print(list * head);
void find_died(list *head,int k);
int main(){
	int n,k;
	scanf("%d %d",&n,&k);
	list *head=creat(n);
	//print(head);
	find_died(head,k);
	return 0;
}
list * creat(int n){
	list *head=(list*)malloc(sizeof(list));
	list *q,*p=head;
	scanf("%d",&p->num[0]);
	p->num[1]=1;
	for(int i=2;i<=n;i++){
		q=(list*)malloc(sizeof(list));
		scanf("%d",&q->num[0]);
		q->num[1]=i;
		p->next=q;
		p=p->next;
	}
	p->next=head;
	return head;
}
void print(list * head){
	list * p=head;
	while(p->next!=head){
		printf("%d->%dn",p->num[1],p->num[0]);
		p=p->next;
	}
	printf("%d->%dn",p->num[1],p->num[0]);
}
void find_died(list *head,int k){
	list * p = head;
	list * q;
	while(p->next!=p){
		for(int i=0;i<k-1;i++){
			q=p;
			p=p->next;
		}
		q->next=p->next;
		printf("%d ",p->num[1]);
		k=p->num[0];
		free(p);
		p=q->next;
	}
	printf("%d ",p->num[1]);
}
  • 代码利用的数据结构为循环链表，该结构很容易解出该问题，当然仁者见仁智者见智，利用队列或者遍历数组当然也可以实现。
  • 我个人觉得循环链表相对于遍历数组有优势，一个是利用指针的不断开辟空间，能做到对空间的完全利用，如果开辟数组的话，会导致，在不断的弹出之后，数组的空间浪费。
  • 如果利用队列的话，等于是利用了队列的后进前出，整个构成了一个循环的过程，对于队列结构比较熟练的话，思路会很明确，当然，你也得提前开辟很大的空间，所以虽然方法很多，但是我觉得还是循环链表相对于其他的要好很多。

好了，看第二个问题
在这里插入图片描述
简化，输入两个数字，一个为总人数，一个为数到几弹出，输出一个弹出的序列，几乎对约瑟夫环没有什么更改，直接上代码。

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
	int x;
	struct node *next;
}list;
//鏋勫缓寰幆閾捐〃
list* creat(int n){
	list *head=(list*)malloc(sizeof(list));
	head->x=1;
	list *q,*p=head;
	for(int i=2;i<=n;++i){
		q=(list*)malloc(sizeof(list));
		q->x=i;
		p->next=q;
		p=p->next;
	}
	p->next=head;
	return head;
} 
//鍒╃敤璇ュ嚱鏁版壘鍒版瘡涓€娆′細涓㈠け鐨勪汉 
void find_died(list *head,int d){
	list *p=head,*q;
	while(p->next!=p){
		for(int i=1;i<d;i++){
			q=p;
			p=p->next;
		}
		q->next=p->next;
		printf("%d ",p->x);
		free(p);
		p=q->next;
	}
	printf("%d ",p->x);
}
int main(){
	int n,d;
	scanf("%d %d",&n,&d);
	list *head=creat(n);
	find_died(head,d);
	return 0;
}

在这里插入图片描述
没什么问题，看第三个。
在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

typedef struct Person {
    int order;
    struct Person * next;
} Person;
Person * pHead = NULL;  // 全局变量 
Person * pFront = NULL;
Person * per = NULL;
int n, m;
int b[100], k;
// 函数
void Create(); 
void Joseph(int number, int m);
int main()
{
    scanf("%d %d", &n, &m);
    int i;
    int a[n];
    for (i = n - m ; i < n; i++)
        scanf("%d", &a[i]);
    for (i = 1; i <= n; i++) {
        pHead = NULL;
        pFront = NULL; 
        k = 0;
        int flag = 1;
        Create();
        per = pHead;
        Joseph(n, i);
        for (int j = n - m; j < n; j++) {
            if (a[j] != b[j]) {
                flag = 0;
                break; 
            }
        }
        if (flag == 1) {
            printf("%d", i);
            return 0;
        }
    }
    printf("0");
    return 0;
} 

void Create() {
    Person * tail;
    for (int i = 0; i < n; i++) {
        Person * person;
        person = (Person *) malloc(sizeof(Person));
        person->order = i + 1;//对本身的数据结构赋值 
        if (pHead == NULL)//构造链表的不同方法 
            pHead = person;
        else
            tail->next = person;
        tail = person;
    }
    tail->next = pHead;
    pFront = tail;
}

void Joseph(int number, int m) {
    if (number == 0) {
        return;
    }
    int count = 1;
    Person * p = NULL;
    while (count != m) {
        per = per->next;
        pFront = pFront->next;
        count++;
    }
    p = per;
    pFront->next = per->next;
    b[k++] = p->order;
    per = per->next;
    free(p);
    Joseph(number - 1, m); 
}
  • 这里我们需要用到递归，因为会节省很大的代码量，如果不使用递归的话，我们需要写好几个循环来构造数组，判断等等操作。
  • 我们用一个大的for循环，每一次循环都会通过递归获得一个b数组，之后我们通过循环判断该数组是否符合，不符合的话直接break，跳出循环，到下一个循环。不断的判断。
  • 思路的话比较容易想到，但是代码实现的话还是有些难度的。
一元多项式的各种操作

一元多项式这个实验，一般情况下是在顺序表章节会给的任务，也确实，虽然对于线性结构的顺序表来说，可能不太友好，因为存在空间分配等等问题，但是，如果利用链式结构实现的话应该会方便许多。
题目一
在这里插入图片描述
这里我发现，c语言怎么搞都会有问题。????但是我本人又不太明白问题在哪????
在这里插入图片描述
希望有人能发现问题吧。
代码：

#include<stdio.h>
#include<stdlib.h>
int main()
{
    int n;
    int a[1000][2];
    scanf("%d", &n);
    getchar();
    for(int i=1; i<=n; i++)			//输入
        scanf("(%d,%d)", &a[i][1], &a[i][2]);
    fflush(stdin);
    getchar();
    for(int i=1; i<n; i++)				//冒泡排序
        for(int j=1; j<n-i; j++)
            if(a[j][2]>a[j+1][2])
            {
                int t=a[j+1][2];
                a[j+1][2]=a[j][2];
                a[j][2]=t;
                t=a[j+1][1];
                a[j+1][1]=a[j][1];
                a[j][1]=t;
            }
    for(int i=1; i<=n; i++)			//输出
    {
        printf("%d", a[i][1]);
        if(a[i][2]==0)
            printf("");
        else if(a[i][2]==1)
            printf("X");
        else
            printf("X^%d", a[i][2]);
        if(i!=n && a[i+1][1]>0)
            printf("+");
    }
}

题目二
这里我直接放弃了链表，这个pta多多少少沾点问题，真的在搞人心态。
在这里插入图片描述在这里插入图片描述
代码：

#include<stdio.h>
#include<stdlib.h>
int sub(int max[][3], int min[][3], int n1, int n2)   
{
    int cnt=n1+1;
    for(int i=1; i<=n2; i++)
    {
        int flag=1;                                         //标记是否可以加到现有的项中
        for(int j=1; j<=n1; j++)
        {
            if(min[i][2]==max[j][2])
            {
                max[j][1]+=min[i][1];                     //加到了现有的项
                flag=0;
                break;
            }
        }
        if(flag)                                                 //如果没有加到则放在表达式的后面
        {
            max[cnt][1]=min[i][1];
            max[cnt++][2]=min[i][2];
        }
    }
    return cnt-1;
}
void sort(int a[][3], int n)   //按指数对所有项进行从小到大排序
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n-i; j++)
        {
            if(a[j][2]>a[j+1][2])
            {
                int t=a[j+1][2];
                a[j+1][2]=a[j][2];
                a[j][2]=t;
                t=a[j+1][1];
                a[j+1][1]=a[j][1];
                a[j][1]=t;
            }
        }
    }
}
 
void print(int a[][3], int n)                 //输出
{
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i][1]==0)
        {
            if(cnt!=0 && a[i+1][1]>0 && i!=n)
                printf("+");
 
        }
        else if(a[i][1]==1)
        {
            if(a[i][2]==0){
                printf("1");
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("X");
                 cnt=1;
            }
            else{
                printf("X^%d", a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
        else if(a[i][1]==-1)
        {
            if(a[i][2]==0){
                printf("-1");
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("-X");
                 cnt=1;
            }
            else{
                printf("-X^%d", a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
        else
        {
            if(a[i][2]==0){
                printf("%d", a[i][1]);
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("%dX", a[i][1]);
                 cnt=1;
            }
            else{
                printf("%dX^%d", a[i][1], a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
    }
}
int main()
{
    int n1, n2;
    int n;
    int a[100][3], b[100][3];
    scanf("%d", &n1);				 //输入第一个
    getchar();
    for(int i=1; i<=n1; i++) 
        scanf("(%d,%d)", &a[i][1], &a[i][2]);
    scanf("%d", &n2);				//输入第二个
    getchar();//利用getchar清楚缓存区 
    for(int i=1; i<=n2; i++)
        scanf("(%d,%d)", &b[i][1], &b[i][2]);
    n=n1>n2?sub(a, b, n1, n2):sub(b, a, n2, n1);
    if(n1>n2)
    {
    sort(a,n);
    print(a,n);
	}
	else
	{
	sort(b,n);
    print(b,n);	
	}
 
 
}

题目三
这里注意所谓的减法，我们只需要对加法的代码进行变换就可以了，只需要将输入的数据变成其相反数便可。因此不难，这里我提供一段java代码
代码：

import java.util.Scanner;

class Calculator{
    //计算器减法操作
    public int[] subtraction(int[]nums1,int[]nums2){     //nums1减num2
        int[]sum = new int[nums1.length+nums2.length];
        int x=0,y=0,z=0;
        while(x<nums1.length||y<nums2.length){
            if (x>=nums1.length&&y<nums2.length){       //当num1长度小于num2时
                sum[z] = (-1)*nums2[y];                 //系数变为负数
                sum[z+1] = nums2[y+1];
                z=z+2;
                y=y+2;
            }
            if (y>=nums2.length&&x<nums1.length){       //当num2长度小于num1时
                sum[z] = nums1[x];                      //系数不变
                sum[z+1] = nums1[x+1];
                z=z+2;
                x=x+2;
            }
            if(x<nums1.length&&y<nums2.length&&nums1[x+1]<nums2[y+1]){                   //第一组指数小于第二组，第一组到下一个节点
                sum[z] = nums1[x];
                sum[z+1] = nums1[x+1];
                z = z+2;
                x = x+2;
            }
            else if (x<nums1.length&&y<nums2.length&&nums1[x+1]==nums2[y+1]){            //指数相等，系数相加
                sum[z] = nums1[x]-nums2[y];
                sum[z+1] = nums1[x+1];
                z = z+2;
                x = x+2;
                y = y+2;
            }
            else if(x<nums1.length&&y<nums2.length&&nums1[x+1]>nums2[y+1]){             //第二组指数小于第一组，第二组到下一节点
                sum[z] = (-1)*nums2[y];
                sum[z+1] = nums2[y+1];
                z = z+2;
                y = y+2;
            }
        }
        return sum;
    }

    //打印出结果
    public void print(int[]sum){
        int index=0,judge=0;
        while(index < sum.length){
            if (sum[index+1]!=0&&sum[index]!=0){        //指数和系数都不为0的情况
                if (sum[index+1]==1){
                    judge++;
                    System.out.print(sum[index]+"X");
                }
                else{
                    judge++;
                    System.out.print(sum[index]+"X^"+sum[index+1]);
                }
                if (index+2<sum.length){
                    if (sum[index+2]>0){
                        System.out.print("+");
                    }
                }
            }
            else if(sum[index+1]==0&&sum[index]!=0){        //指数为0，系数不为0的情况
                judge++;
                System.out.print(sum[index]);
                if (index+2<sum.length){
                    if (sum[index+2]>0){
                        System.out.print("+");
                    }
                }
            }
            else if(sum[index]==0){                   //系数为0的情况
                if (index+2<sum.length){
                    if (sum[index+2]>0){
                        System.out.print("+");
                    }
                }
            }
            index = index+2;
        }
        if (judge==0){
            System.out.println(0);
        }
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n=input.nextInt();
        input.nextLine();
        String string1 = input.nextLine();
        int m=input.nextInt();
        input.nextLine();
        String string2 = input.nextLine();
        string1 = string1.replace("(","");
        string1 = string1.replace(")",",");
        string2 = string2.replace("(","");
        string2 = string2.replace(")",",");
        String[]strings1 = string1.split(",");
        String[]strings2 = string2.split(",");
        int[]nums1 = new int[n*2];
        int[]nums2 = new int[m*2];
        Calculator calculator = new Calculator();
        for(int i=0;i<strings1.length-1;i++){
            if (i%2==0){
                nums1[i] = Integer.parseInt(strings1[i]);
                nums1[i+1] = Integer.parseInt(strings1[i+1]);
            }
        }
        for(int i=0;i<strings2.length-1;i++){
            if (i%2==0){
                nums2[i] = Integer.parseInt(strings2[i]);
                nums2[i+1] = Integer.parseInt(strings2[i+1]);
            }
        }
        int[]sum = calculator.subtraction(nums1,nums2);
        calculator.print(sum);
    }
}

题目四
乘法：
代码：

#include<stdio.h>
#include<stdlib.h>
int map(int a[][3], int b[][3], int c[][3], int n1, int n2);
void sort(int a[][3], int n);
void print(int a[][3], int n);
int main()
{
	int n1, n2;
	int n;
	int a[100][3], b[100][3], c[100][3];
	scanf("%d ", &n1);
	for(int i=1; i<=n1; i++)
		scanf("(%d,%d)", &a[i][1], &a[i][2]);
	scanf("%d ", &n2);
	for(int i=1; i<=n2; i++)
		scanf("(%d,%d)", &b[i][1], &b[i][2]);
    n=map(a, b, c, n1, n2);
    sort(c, n);
    print(c, n);
    return 0;
}

int map(int a[][3], int b[][3], int c[][3], int n1, int n2)
{
	int cnt=1;
	for(int i=1; i<=n1; i++)
	{
		for(int j=1; j<=n2; j++)
        {
            int flag=1;
            int c1=a[i][1]*b[j][1];
            int c2=a[i][2]+b[j][2];
            for(int k=1; k<cnt; k++)
                if(c[k][2]==c2)
                {
                    c[k][1]+=c1;
                    flag=0;
                    break;
                }
            if(flag)
            {
                c[cnt][1]=c1;
                c[cnt++][2]=c2;
            }
        }
	}
	return cnt-1;
}
void sort(int a[][3], int n)
{
	for(int i=1; i<=n; i++)
		for(int j=1; j<=n-i; j++)
			if(a[j][2]>a[j+1][2])
			{
				int t=a[j+1][2];
				a[j+1][2]=a[j][2];
				a[j][2]=t;
				t=a[j+1][1];
				a[j+1][1]=a[j][1];
				a[j][1]=t;
			}

}

void print(int a[][3], int n)
{
    int cnt=0;
	for(int i=1; i<=n; i++)
	{
	    if(a[i][1]==0)
        {
            if(cnt!=0 && a[i+1][1]>0 && i!=n)
                printf("+");

        }
        else if(a[i][1]==1)
        {
            if(a[i][2]==0){
                printf("1");
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("X");
                 cnt=1;
            }
            else{
                printf("X^%d", a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
        else if(a[i][1]==-1)
        {
            if(a[i][2]==0){
                printf("-1");
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("-X");
                 cnt=1;
            }
            else{
                printf("-X^%d", a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
        else
        {
            if(a[i][2]==0){
                printf("%d", a[i][1]);
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("%dX", a[i][1]);
                 cnt=1;
            }
            else{
                printf("%dX^%d", a[i][1], a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
	}
}

题目五
求值：

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
typedef struct node{
	double num[2];
	struct node * next;
}list;
list * creat(int n){
	if(n==0)
		return NULL;
	list * head=(list*)malloc(sizeof(list));
	list * q,* p=head;
	scanf("(%lf,%lf)",&head->num[0],&head->num[1]);
	for(int i=1;i<n;i++){
		q=(list*)malloc(sizeof(list));
		scanf("(%lf,%lf)",&q->num[0],&q->num[1]);
		p->next=q;
		p=p->next;
	}
	p->next=NULL;
	return head;
}
double add(list *a,double x)//求和 
{
	list *q=a;
	double answer=0; 
	while(q!=NULL){
		answer+=(q->num[0]*pow(x,q->num[1]));
		q=q->next;
	}
	return answer;
}
int main(){
	int n;
	scanf("%d ",&n);
	fflush(stdin);
	list * head=creat(n);
	double x;
	scanf("%lf ",&x);
	getchar();
	printf("%.0lf",add(head,x));
	return 0;
}

题目六：
求导：


#include<stdio.h>
#include<stdlib.h>
void derivative(int list[][3],int n)   
{
	for(int i=1;i<=n;i++){
		if(list[i][1]==0||list[i][2]==0){
			list[i][1]=0;
			list[i][2]=0;
		}
		else{
			list[i][1]*=list[i][2];
			list[i][2]-=1;
		}
	}
}
void sort(int a[][3], int n)   //按指数对所有项进行从小到大排序
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n-i; j++)
        {
            if(a[j][2]>a[j+1][2])
            {
                int t=a[j+1][2];
                a[j+1][2]=a[j][2];
                a[j][2]=t;
                t=a[j+1][1];
                a[j+1][1]=a[j][1];
                a[j][1]=t;
            }
        }
    }
}
 
void print(int a[][3], int n)          
{
    int cnt=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i][1]==0)
        {
            if(cnt!=0 && a[i+1][1]>0 && i!=n)
                printf("+");
 
        }
        else if(a[i][1]==1)
        {
            if(a[i][2]==0){
                printf("1");
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("X");
                 cnt=1;
            }
            else{
                printf("X^%d", a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
        else if(a[i][1]==-1)
        {
            if(a[i][2]==0){
                printf("-1");
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("-X");
                 cnt=1;
            }
            else{
                printf("-X^%d", a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
        else
        {
            if(a[i][2]==0){
                printf("%d", a[i][1]);
                cnt=1;
            }
            else if(a[i][2]==1){
                 printf("%dX", a[i][1]);
                 cnt=1;
            }
            else{
                printf("%dX^%d", a[i][1], a[i][2]);
                cnt=1;
            }
            if(a[i+1][1]>0 && i!=n)
                printf("+");
        }
    }
}
int main()
{
    int n;
    int list[100][3];
    scanf("%d ", &n);			
    for(int i=1; i<=n; i++) 
        scanf("(%d,%d)", &list[i][1], &list[i][2]); 
    sort(list,n);
    derivative(list,n);
    print(list,n);
}

最后

以上就是怕黑水杯为你收集整理的数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式的全部内容，希望文章能够帮你解决数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式所遇到的程序开发问题。

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

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(41)

相关文章

美学心得（第一百九十集） 罗国正
美学心得（第一百九十集） 罗国正
美学心得（第二百三十三集） 罗国正
美学心得（第二百三十三集） 罗国正
八数码问题
八数码问题
美学心得(第二百二十四集)罗国正
美学心得(第二百二十四集)罗国正
数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式
数据结构 第一次实验总结变着法子玩约瑟夫环和一元多项式
vue心得
vue心得
版本管理工具面试总结
版本管理工具面试总结
学习mybatis时遇到的问题前言mybatis
学习mybatis时遇到的问题前言mybatis

评论列表共有 0 条评论

立即
投稿
返回
顶部