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

本文主要是介绍【MOOC-浙大数据结构】第二周的编程作业——线性结构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第二周的编程作业：

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.一元多项式的乘法与加法运算

//写了好久

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

#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 

//一开始读错题了，以为只要反转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

#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;//flagfor(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");}
}

 

这篇关于【MOOC-浙大数据结构】第二周的编程作业——线性结构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---