线性表编程作业——解题报告
3-1两个有序链表序列的合并
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：
List Merge( List L1, List L2 );
其中List结构定义如下：
typedef struct Node *PtrToNode;
struct Node {
ElementType Data; /* 存储结点数据 */
PtrToNode Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。
裁判测试程序样例：
#include <stdio.h>
#include <stdlib.h>
typedef int ElementType;
typedef struct Node *PtrToNode;
struct Node {
ElementType Data;
PtrToNode Next;
};
typedef PtrToNode List;
List Read(); /* 细节在此不表 */
void Print( List L ); /* 细节在此不表；空链表将输出NULL */
List Merge( List L1, List L2 );
int main()
{
List L1, L2, L;
L1 = Read();
L2 = Read();
L = Merge(L1, L2);
Print(L);
Print(L1);
Print(L2);
return 0;
}
/* 你的代码将被嵌在这里 */
输入样例：
3
1 3 5
5
2 4 6 8 10
输出样例：
1 2 3 4 5 6 8 10
NULL
NULL
代码长度限制
时间限制
内存限制
思路：
Code：
List Merge(List l1,List l2){
List L1=l1,L2=l2;
l1=l1->Next;
l2=l2->Next;
List l3=(List)malloc(sizeof (struct Node)); //表头
List now3=l3;
while(l1||l2){
if(!l2||l1&&l1->Data<=l2->Data){
now3->Next=l1;
now3=l1;
l1=l1->Next;
}else{
now3->Next=l2;
now3=l2;
l2=l2->Next;
}
}
now3->Next=NULL;
L1->Next=NULL;
L2->Next=NULL;
return l3;
}
3-2最长连续递增子序列
给定一个顺序存储的线性表，请设计一个算法查找该线性表中最长的连续递增子序列。例如，中最长的递增子序列为。
输入格式:
输入第1行给出正整数n；第2行给出n个整数，其间以空格分隔。
输出格式:
在一行中输出第一次出现的最长连续递增子序列，数字之间用空格分隔，序列结尾不能有多余空格。
输入样例：
15
1 9 2 5 7 3 4 6 8 0 11 15 17 17 10
输出样例：
3 4 6 8
代码长度限制
时间限制
内存限制
思路：
记录递增序列的开头st，和长度len
维护len的最大值，并记录长度取最大时的开头ansst
每遇到破坏递增的时候，记录当前元素为新的一段的开始，并重新计数
Code：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int R(){int a=0,b=1;char c=getchar();while(c<"0"||c>"9"){if(c=="-")b=-1;c=getchar();}while(c>="0"&&c<="9"){a=a*10+c-"0";c=getchar();}return a*b;}
int a[100010];
int main(){
int n=R();
int st=1,ansst,len=0,ma=0;
a[0]=-1;
for(int i=1;i<=n;++i){
a[i]=R();
if(a[i]>a[i-1]){
len++;
if(len>ma){
ma=len;
ansst=st;
}
}else{
st=i;
len=1;
}
}
for(int i=ansst;i<=ansst+ma-1;++i){
printf("%d",a[i]);
if(i!=ansst+ma-1)printf(" ");
}
return 0;
}
3-3一元多项式的乘法与加法运算
设计函数分别求两个一元多项式的乘积与和。
输入格式:
输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数。数字间以空格分隔。
输出格式:
输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出00。
输入样例:
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
输出样例:
15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0
代码长度限制
时间限制
内存限制
利用map，可动态开辟空间，记录乘法和加法后不同指数的系数，然后利用迭代器输出
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int R(){int a=0,b=1;char c=getchar();while(c<"0"||c>"9"){if(c=="-")b=-1;c=getchar();}while(c>="0"&&c<="9"){a=a*10+c-"0";c=getchar();}return a*b;}
int n,m;
int ak[1010],bk[1010],ap[1010],bp[1010];
map<int,int> mul,add;
int main(){
n=R();
for(int i=1;i<=n;++i){
ak[i]=R();ap[i]=R();
add[ap[i]]+=ak[i];
}
m=R();
for(int i=1;i<=m;++i){
bk[i]=R();bp[i]=R();
add[bp[i]]+=bk[i];
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
mul[ap[i]+bp[j]]+=ak[i]*bk[j];
}
}
map<int,int>::iterator it1=mul.end(),it2=add.end();
if(mul.empty()){
printf("0 0");
}else{
bool bj=0;
for(it1--;it1!=mul.begin();it1--){
if(it1->second){
if(bj)printf(" ");
printf("%d %d",it1->second,it1->first);
bj=1;
}
}
if(it1->second){
if(bj)printf(" ");
printf("%d %d",it1->second,it1->first);
bj=1;
}
if(!bj)printf("0 0");
}
putchar("
");
if(add.empty()){
printf("0 0");
}else{
bool bj=0;
for(it2--;it2!=add.begin();it2--){
if(it2->second){
if(bj)printf(" ");
printf("%d %d",it2->second,it2->first);
bj=1;
}
}
if(it2->second){
if(bj)printf(" ");
printf("%d %d",it2->second,it2->first);
bj=1;
}
if(!bj)printf("0 0");
}
return 0;
}
单链表的基本操作
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
int x;
node *next;
};
typedef node *List;
const int inf=0x3f3f3f3f;
List l1,l2;
List build(){
int n;
do{
cout<<"请输入初始序列长度n：（n应为非负整数）
";
cin>>n;
if(n<0)cout<<"输入不合法
";
}while(n<0);
List head=new node,now,last;
last=now=head;
if(n!=0){
cout<<"请输入序列:
";
for(int i=1;i<=n;++i){
now=new node;
cin>>now->x;
last->next=now;
last=now;
}
}
now->next=NULL;
return head;
}
int find_id(List head,int x){
List now=head;
while(x--){
now=now->next;
if(now==NULL)return -inf;
}
if(now==NULL)return -inf;
return now->x;
}
int find_val(List head,int x){
List now=head->next;
int cnt=1;
while(now->x!=x){
now=now->next;
if(now==NULL)return -inf;
cnt++;
}
if(now==NULL)return -inf;
return cnt;
}
void insert(List head,int id,int x){
List now=head;
id--;
while(id--){
now=now->next;
}
List brand=new node;
brand->x=x;brand->next=now->next;
now->next=brand;
}
void del(List head,int id){
List now=head;
id--;
while(id--){
now=now->next;
}
now->next=(now->next)->next;
}
int len(List head){
List now=head;
int cnt=0;
while(now->next){
now=now->next;
cnt++;
}
return cnt;
}
void print(List head){
List now=head;
while(now->next){
now=now->next;
cout<<now->x<<" ";
}
cout<<"
";
}
void work(){
while(1){
int type;
cin>>type;
switch(type){
case 2:{
int x;
cin>>x;
int t=find_id(l1,x);
if(t==-inf)cout<<"超出序列长度
";
else cout<<"第"<<x<<"个数是："<<t<<"
";
break;
}
case 3:{
int x;
cin>>x;
int t=find_val(l1,x);
if(t==-inf)cout<<"不存在这个数
";
else cout<<"第一个"<<x<<"的位置是："<<t<<"
";
break;
}
case 4:{
int id,x;
cin>>id>>x;
if(id<1||id>len(l1)+1)cout<<"输入不合法
";
else{
insert(l1,id,x);
cout<<"插入成功
";
}
break;
}
case 5:{
int id;
cin>>id;
if(id<1||id>len(l1))cout<<"输入不合法
";
else{
del(l1,id);
cout<<"删除成功
";
}
break;
}
case 6:{
cout<<"当前长度="<<len(l1)<<"
";
break;
}
case 7:{
cout<<"当前序列如下：
";
print(l1);
break;
}
}
}
}
void shijian1(){
l1=build();
string s="--------------
操作类型：
2:按序号查找（输入：id）
3:按值查找（输入：value）
4:在第i个位置插入x（输入：i，x）
5:删除第i个位置（输入：i）
6:求表长
7:打印序列
--------------
";
cout<<s;
work();
}
int main(){
shijian1();
return 0;
}
文章为作者独立观点，不代表 股票程序化软件自动交易接口观点
相关文章
股民评论