链表查找(线性表)

链表查找(线性表)

时间: 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;} 

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

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注