算法问题(线性表)

算法问题(线性表)

时间： 1ms        内存：128M

描述：

（线性表）已知一个单链表中每个结点存放一个整数，并且结点数不少于2，请设计算法以判断该链表中第二项起的每个元素值是否等于其序号的平方减去其前驱的值，若满足则返回ture，否则返回false.

输入：

第一行为输入线性表的节点数N；

第二行为N个整数。

输出：

true或者false;

示例输入：

7
2 2 7 9 16 20 29

示例输出：

true

提示：

参考答案（内存最优[748]）：

#include<stdio.h> 
#include<stdlib.h> 
struct f  
{ 
    int x; 
    struct f *next; 
}; 
struct f *p; 
struct f *f1(int m)  
{  
    struct f *head,*p1,*p2; 
    head=NULL;  
    while(m--)  
    {  
        p1=(struct f *)malloc(sizeof(struct f));  
        scanf("%d",&p1->x); 
        if(head==NULL)  
            head=p1;  
        else
            p2->next=p1;  
        p2=p1;  
    }  
    p2->next=NULL;  
    return head;  
} 
int main()  
{   
    struct f *p1,*p2,*p;  
    int m,t=2,flag=0; 
    scanf("%d",&m); 
    p=f1(m);  
    for(p1=p;p1!=NULL;p1=p1->next)  
    {  
		p2=p1->next ;
		if(p1->next =NULL)
			break;
		if(p2->x==(t*t-(p1->x )))
			flag=1;
		else
		{
			flag=0;
			break;
		}
		t++;
    }  
    if(flag)
		printf("true\n");
	else
		printf("false\n");
    return 0;  
}  

参考答案（时间最优[0]）：

#include<iostream>
using namespace std;
#define NULL 0
int i,len,j,n,m;
struct linklist
{
	int num;
	linklist *next;
};
linklist *creat()
{
	cin>>m;
   linklist *p1,*head,*p2;
   p1=new linklist;
	for(int x=1;x<=m;x++)
	{
		cin>>p1->num;
		if(x==1) head=p1;
		p2=p1;       
		p1=new linklist;
		p2->next=p1;
		if(x==m) delete p1,p2->next=NULL;
	}
	  return head;
}
bool build_print_linklist(linklist *a)
{
	linklist *p,*p2;
	p=a->next;p2=a;
	int n=1;
	while(p!=NULL)
	{
		n++;
		if(n*n-p2->num!=p->num) return false;
		p2=p;p=p->next;
	}
	/*while(a!=NULL)
	{
		cout<<a->num<<" ";
		a=a->next;
	}
	cout<<endl;*/
	return true;
}
int main()
{
	linklist *heada,*headb;
	heada=creat();
	//headb=creat();
    if(build_print_linklist(heada)) cout<<"true"<<endl;
	else cout<<"false"<<endl;
	return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。