链表查找(线性表)
时间： 1ms 内存：128M
描述：
本题只需要提交填写部分的代码已知非空线性链表由list指出，链结点的构造为（data,link）.请写一算法，将链表中数据域值最小的那个链结点移到链表的最前面。要求：不得额外申请新的链结点代码：#include <iostream>
using namespace std;
struct list
{
int data; //数据域
struct list *link; //指针域
};
struct list *listcreate(struct list *head,int n) //建立链表
{
struct list *previous; //前驱结点
struct list *current; //当前结点
head=NULL;
if(n<1)
return NULL; //建立空链表
previous=head=new struct list; //建立首结点
cin>>head->data; //输入数据
while(--n)
{
current=new struct list; //建立新结点
cin>>current->data; //输入数据
previous->link =current; //新节点挂在表尾
previous=current;
}
previous->link=NULL; //置表尾结束标志
return head; //返回首结点指针
}struct list *minmovefirst(struct list *head) //将最小结点移至表尾
{
struct list *minnode; //最小结点
struct list *previousminnode; //最小结点的前驱结点
struct list *previous; //前驱结点
struct list *current; //当前结点
if(NULL==head)
return head; //空链表直接返回
/************查找最小结点*****************/
minnode=previous=head;
current=head->link;
while(NULL!=current)
{
if(current->data<minnode->data) //结点数据比较
{
/*
请在该部分填写缺少的代码
*/
}
previous=current; //记录前驱结点
current=current->link; //当前结点后移
}
//此时的previous指向表尾
/************从链表摘下最小结点*****************/
if(minnode==head) //最小结点是首结点
head=head->link; //首结点后移
else
previousminnode->link=minnode->link;/************将最小结点放在表头*****************/
minnode->link = head;
head = minnode;
return head;
}
void listoutput(struct list *head)
{
struct list *current=head;
while(current!=NULL)
{
cout<<current->data<<" "; //输出结点数据
current=current->link; //结点指针后移
}
}
int main()
{
struct list *head=NULL;
int n;
cin>>n;
head=listcreate(head,n);
head=minmovefirst(head);
listoutput(head);
return 0;
}
输入：
输入长度n:6
输入数据：4 2 6 88 34 6
输出：
2 4 6 88 34 6
示例输入：
5
11 6 8 7 9示例输出：
6 11 8 7 9 提示：
参考答案（内存最优[748]）：
#include <stdio.h>#include <stdlib.h>
struct u_node_s
{int data;struct u_node_s* link;};
int main()
{struct u_node_s *link;
struct u_node_s *current;
struct u_node_s *temp;int n = 0;
int i = 0;
scanf("%d", &n);
current = link = (struct u_node_s *)
malloc(sizeof(struct u_node_s));
link->link = NULL;
for(i = 0; i < n; i++)
{temp = (struct u_node_s *)malloc(sizeof(struct u_node_s));
scanf("%d", &(temp->data));
temp->link = NULL;
current->link = temp;current = current->link;}current = link;
while(current->link != NULL)
{temp = current;current = current->link;
if(link->link->data > current->data)
{temp->link = current->link;
current->link = link->link;
link->link = current;}}
current = link;
while(current->link != NULL)
{current = current->link;printf("%d ", current->data);}
return 0;}
参考答案（时间最优[0]）：
#include <stdio.h>#include <stdlib.h>
struct u_node_s
{int data;struct u_node_s* link;};
int main()
{struct u_node_s *link;
struct u_node_s *current;
struct u_node_s *temp;int n = 0;
int i = 0;
scanf("%d", &n);
current = link = (struct u_node_s *)
malloc(sizeof(struct u_node_s));
link->link = NULL;
for(i = 0; i < n; i++)
{temp = (struct u_node_s *)malloc(sizeof(struct u_node_s));
scanf("%d", &(temp->data));
temp->link = NULL;
current->link = temp;current = current->link;}current = link;
while(current->link != NULL)
{temp = current;current = current->link;
if(link->link->data > current->data)
{temp->link = current->link;
current->link = link->link;
link->link = current;}}
current = link;
while(current->link != NULL)
{current = current->link;printf("%d ", current->data);}
return 0;}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。