【MOOC-浙大数据结构】第二周的编程作业——线性结构

绝地灬酷狼 2021-11-29 07:20 345阅读 0赞

**第二周的编程作业：**

**1.**[**两个有序链表序列的合并**][Link 1]

List Merge( List L1, List L2 )
    {
    	List Res,tmp,pa,pb;	
    	Res=(List)malloc(sizeof(struct Node));
    	pa=L1->Next;
    	pb=L2->Next;
    	tmp=Res;
    	while(pa&&pb)
    	{
    		if(pa->Data<=pb->Data)
    		{
    			tmp->Next=pa;
    			tmp=pa;
    			pa=pa->Next;
    		}
    		else
    		{
    			tmp->Next=pb;
    			tmp=pb;
    			pb=pb->Next;
    		}
    	}
    	tmp->Next=pa?pa:pb;
    	L1->Next=NULL;
    	L2->Next=NULL;
    	return Res;
    }

2.[**一元多项式的乘法与加法运算**][Link 2]

//写了好久

//来自退休老阿姨的挣扎

#include <stdio.h>
    #include <stdlib.h>
    typedef struct PolyNode *PolyNomial;
    struct PolyNode{
    	int coef;
    	int expon;
    	PolyNomial link;
    };
    
    void Attach(int c,int e,PolyNomial *pRear)
    {
    	PolyNomial P=(PolyNomial)malloc(sizeof(struct PolyNode));
    	P->coef=c;
    	P->expon=e;
    	P->link=NULL;
    	(*pRear)->link=P;
    	*pRear=P;
    } 
    PolyNomial ReadPoly()
    {
    	PolyNomial P,Rear,t;
    	P=(PolyNomial)malloc(sizeof(struct PolyNode));
    	P->link=NULL;
    	Rear=P;
    	
    	int n,c,e;
    	scanf("%d",&n);
    	while(n--)
    	{
    		scanf("%d%d",&c,&e);
    		Attach(c,e,&Rear);
    	}
    	t=P;
    	P=P->link;
    	free(t);//不要头结点 
    	return P;
    }
    PolyNomial Mult(PolyNomial P1,PolyNomial P2)
    {
    	if(!P1||!P2)
    	return NULL;	//测试点4-判断两个多项式都不为零多项式
    	
    	PolyNomial P,Rear,t1,t2,t;
    	P=(PolyNomial)malloc(sizeof(struct PolyNode));
    	P->link=NULL;
    	Rear=P;
    	t1=P1;t2=P2;
    	while(t2)
    	{
    		Attach(t1->coef*t2->coef,t1->expon+t2->expon,&Rear);
    		t2=t2->link;
    	}
    	t1=t1->link;
    	while(t1)
    	{
    		t2=P2;
    		Rear=P;
    		while(t2)
    		{
    			int c=t1->coef*t2->coef;
    			int e=t1->expon+t2->expon;
    			while(Rear->link&&Rear->link->expon > e)
    			{
    				Rear=Rear->link;
    			}
    			if(Rear->link&&Rear->link->expon==e)
    			{
    				if(Rear->link->coef+c!=0)	
    				{
    					Rear->link->coef+=c;
    				}
    				else
    				{							
    					Rear->link->coef=0;
    					Rear->link->expon=0;
    				}
    			}
    			else
    			{
    				t=(PolyNomial)malloc(sizeof(PolyNode));
    				t->coef=c;
    				t->expon=e;
    				t->link=Rear->link;
    				Rear->link=t;
    				Rear=Rear->link;
    			}			
    			t2=t2->link;
    		}		
    		t1=t1->link;
    	}
    	Rear=P;
    	P=P->link;
    	free(Rear);
    	return P;
    }
    PolyNomial Add(PolyNomial P1,PolyNomial P2)
    {
    	PolyNomial P,Rear,t1,t2;
    	P=(PolyNomial)malloc(sizeof(struct PolyNode));
    	P->link=NULL;
    	Rear=P;
    	t1=P1;t2=P2;
    	while(t1&&t2)
    	{
    		if(t1->expon==t2->expon)
    		{
    			if((t1->coef+t2->coef)==0)
    			{
    				t1=t1->link;
    				t2=t2->link;
    			}
    			else
    			{
    				Attach(t1->coef+t2->coef,t1->expon,&Rear);
    				t1=t1->link;
    				t2=t2->link;
    			}
    		} 
    		else if(t1->expon > t2->expon)
    		{
    			Attach(t1->coef,t1->expon,&Rear);
    			t1=t1->link;
    		}
    		else if(t1->expon < t2->expon)
    		{
    			Attach(t2->coef,t2->expon,&Rear);
    			t2=t2->link;
    		}
    	}
    	while(t1)
    	{
    		Attach(t1->coef,t1->expon,&Rear);
    		t1=t1->link;
    	}
    	while(t2)
    	{
    		Attach(t2->coef,t2->expon,&Rear);
    		t2=t2->link;
    	}
    	Rear=P;
    	P=P->link;
    	free(Rear);
    	return P;
    }
    void PrintPoly(PolyNomial P)
    {
    	if(!P)
    	printf("0 0\n");
    	else
    	{
    		while(P)
    		{
    			printf("%d %d",P->coef,P->expon);
    			P=P->link;
    			if(P)		
    			printf(" ");
    		}
    		printf("\n");
    	}
    }
    int main()
    {
    	PolyNomial P1,P2,PP,PS;
    	P1=ReadPoly();
    	P2=ReadPoly();	
    	PP=Mult(P1,P2);
    	PrintPoly(PP);
    	PS=Add(P1,P2);
    	PrintPoly(PS);
    }

3.[**Reversing Linked List**][Reversing Linked List]

//一开始读错题了，以为只要反转K个就好了，没想到是每K个都要翻转5555

//数据点5超时卡了半个小时，心累

然后改成了while就过了，然后再用for交居然也过了，我？？？？

#include<stdio.h>
    #include<map>
    #include<string>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    string s[100005];
    int main()
    {
    	int n,k,i,j,x,l;
    	string bg,a,b;
    	map<string,int> data;//存data 
    	map<string,string> next;//模拟指针 
    	
    	cin>>bg>>n>>k;
    	for(i=0;i<n;i++)
    	{
    		cin>>a>>x>>b;
    		data[a]=x;
    		next[a]=b;
    	} 
    	l=0;
    	string c=bg;
    	while(1)
    	{
    		if(c=="-1")break;
    		s[l++]=c;
    		c=next[c];
    	}
    	for(i=0;i+k<=l;i+=k)
    	reverse(s+i,s+i+k);
    	for(i=0;i<l-1;i++)
    	cout<<s[i]<<" "<<data[s[i]]<<" "<<s[i+1]<<endl;
    	cout<<s[l-1]<<" "<<data[s[l-1]]<<" -1"<<endl;
    }

4.[**Pop Sequence**][Pop Sequence]

#include<stdio.h>
    #include<stack>
    #include<iostream>
    using namespace std;
    int a[1005];
    int main()
    {
    	int m,n,l,i,j,k;
    	scanf("%d%d%d",&m,&l,&n);
    	while(n--)
    	{		
    		for(i=0;i<l;i++)
    		scanf("%d",&a[i]);
    		
    		stack<int> s;
    		int rs=1;//放入的数字 
    		k=0;//flag
    		
    		for(i=1;i<=a[0];i++)
    		s.push(rs++);
    		
    		if(s.size()>m)
    		k=1;//爆栈
    		
    		s.pop();
    		
    		for(i=1;i<l;i++)
    		{
    			if(!s.empty())
    			{
    				if(a[i]==s.top())
    				{
    					s.pop();
    				}
    				else
    				{
    					for(;rs<=a[i];)
    					s.push(rs++);
    									
    					if(s.size()>m)
    					k=1;//爆栈 
    					
    					if(a[i]==s.top())
    					s.pop();
    				}	
    			}			
    			else
    			{
    				for(;rs<=a[i];)
    				s.push(rs++);			
    				
    				if(s.size()>m)
    				k=1;//爆栈 
    				
    				s.pop();
    			}			
    		}
    		if(!s.empty()||rs!=l+1)//栈不空or数字没有放完 
    		k=1;
    		
    		if(k)printf("NO\n");
    		else printf("YES\n");
    	}
    }

[Link 1]: https://pintia.cn/problem-sets/1134360184290500608/problems/1138764336949059584
[Link 2]: https://pintia.cn/problem-sets/1134360184290500608/problems/1138764336949059585
[Reversing Linked List]: https://pintia.cn/problem-sets/1134360184290500608/problems/1138764336949059586
[Pop Sequence]: https://pintia.cn/problem-sets/1134360184290500608/problems/1138764336949059587