链表查找(线性表)
时间: 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
提示:
参考答案:
文章评论