设为首页 加入收藏

TOP

面试题:链表插入排序、冒泡排序
2019-05-12 02:04:36 】 浏览:105
Tags:试题 插入 排序 冒泡
前些天去华赛面试,在经过详细的面试后,考官最后让我写一个链表排序的小程序,居然还写错了,惭愧回来痛定思痛,重新再实现了一遍
template<typename T>
struct list_node
{
    struct list_node<T> *next;
    T value;
};

template<typename T>
struct _list
{
    struct list_node<T> *head;
    int size;
};
template<typename T>
void SortLink(struct _list<T> * link) {

    struct list_node<T> *pHead,*pRear,*p,*tp;

    if (!link) return;

    for (pHead=link->head,pRear=0;pHead;pHead=pHead->next) {

        for (tp=pHead,p=pHead->next;p;tp=p,p=p->next)

            if (pHead->value>=p->value)

                tp->next=p->next,p->next=pHead,pHead=p,p=tp;

        if (!pRear) link->head=pHead;

        else pRear->next=pHead;

        pRear=pHead;

    }

}
template<typename T>
void InsertSort(struct _list<T> * list) {

    struct list_node<T> *pHead,*p,*tp,*m,*n;

    if (!list) return;

    pHead=list->head;
    p=pHead->next;
    while(!p)
    {
        tp=p;
        p=p->next;

        for(m=NULL;n=pHead;n!=NULL &&tp->next>n->value;m=n,n=n->next);
        if(!m)
            pHead=tp;
        else
        {
            m->next=tp;
        }
        tp->next=n;
        
    }
}
template <typename T>
void ReverseList(struct _list<T> * link)
{
    struct list_node<T> *pHead,*pRear,*p,*tp;
    pHead=link->head;
    p=pHead->next;
    pHead->next=NULL;
    for(;p;p=tp)
    {
        tp=p->next;
        p->next=pHead;
        pHead=p;

    }
    link->head=pHead;
};


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇jquery的parents()和parents的比较 下一篇oracle基础知识8_plsql_光标

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目