Question

一个C++数据结构问题 求大大详解QAQ！

针对带表头结点的单链表，试编写下列函数。

(1) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。

(2) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。

(3) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点位置及其值。

我想要程序W 谢谢啦

Answer 1

针对带表头结点的单链表，试编写下列函数。
struct Node
{
int data;
struct Node *next;
}*head=NULL;

(1) 建立函数create：根据一维数组a[n]建立一个单链表，使单链表中各元素的次序与a[n]中各元素的次序相同，要求该程序的时间复杂性为O(n)。

void create(int a[],int n)
{
struct Node *p,*q;
int i=0;
for(;i<n;i++)
{
p=new Node;
p->data=a[i];
p->next=NULL;
if(head==NULL)
{
head=p;
q=p;
}
else
{
q->next=p;
q=p;
}
}
}

(2) 定位函数Locate：在单链表中寻找第i个结点。若找到，则函数返回第i个结点的地址；若找不到，则函数返回NULL。

struct Node * Locate(int i)
{
struct Node *p;
p=head;
int num=1;
while(p!=NULL && num!=i)
{ p=p->next;num++;}

return p;

}

(3) 求最大值函数max：通过一趟遍历在单链表中确定值最大的结点位置及其值。
void Max()
{
struct Node *p;
p=head;
int d=p->data;
struct Node *q=p;
while(p!=NULL)
{
if(d<p->data)
{
d=p->data;
q=p;
}
p=p->next;
}
cout<<"最大值为："<<d<<endl;
cout<<"最大值的位置："<<q<<endl;
}