运行时错误，插入不对
#include "ElemType.h"
#include "DuNode.h"
#include "stdlib.h"
#include "stdio.h"

DuLinkList Init(){
    DuLinkList L = ( DuLinkList ) malloc ( sizeof ( DuNode ) ) ;
    L -> data = 0 ;
    L -> next = L -> prior = NULL ;
    return L;
}
void Insert ( DuLinkList L , int i , ElemType e ) {
    DuLinkList s  , p = L->next ;
     int k ;
   
    if(i < 1 || i > GetLength( L )+1 )
    {
        printf( "插入数据位置错误\n" ) ; return ;
    }
   
    s = ( DuLinkList ) malloc ( sizeof ( DuNode ) ) ;
    s -> data = e ;

   for( k = 1 ; k < i ; k++)
   {                //找到插入的位置的后一个节点
       p = p -> next ;
   }
   s->prior = p ->prior ;
   p->prior->next = s;

   s->next = p;
   p->prior = s;
   
}


int  GetLength( DuLinkList L ){
    int k = 0 ;
    DuLinkList p = L ;
    while ( p->next )
    {
     k ++ ;
    }
    return k ;
   // return L -> data ;
}
void DeleteIndex ( DuLinkList L , int i ) {
   
    DuLinkList p = L , q = L ;
    int k = 0 ;

    if ( i< 1 || i > GetLength( L ) )
    {
    printf ( "删除数据位置错误 \n" ) ;
    }

    for( k = 1 ; k < i ; k++ ) //找到要删除的数据的前一个节点.
        p = p -> next ;

    q = p -> next ;

    p -> next = q -> next ;
    q -> next -> prior = p ;
    free ( q ) ;
    printf("\n删除%d位置的数据成功\n");
}

void DeleteElem ( DuLinkList L , ElemType e ){
    DuLinkList p = L ;
    int i = 0 ;
    while( p->next ){
        p = p -> next ;
        i ++ ;
        if( p -> data == e  )
        {
        DeleteIndex( L , i);
        }
    }


    }

void Traverse(DuLinkList L){ //正向遍历
    DuLinkList p = L ;
    printf ( " \n正向遍历数据 : \n" );
    while( p -> next )
    {
        p= p-> next ;
        printf ( " %d\t " , p -> data );
    }

}
void Display (DuLinkList L){ //反向遍历

    DuLinkList p = L ;
    printf ( "\n 反向遍历数据 : \n" );
    while( p -> next )
    {
        p = p -> next ;
    }

    while (p -> prior -> prior )
    {
        printf(" %d\t " , p->data ) ;
    }

}

#include<iostream>
#include<cstdlib>
#include<utility>
#include<cassert>
using std::pair;
template<class Type>
class List
{
public:
    struct Node{
        Type val;
        Node():pre(this),next(this){}
        Node(Type key):pre(this),next(this)
            {
                val=key;
            }
        Node(Node &node)
            {
                this->val=node.val;
            }
        Node &operator=(Node & node)
            {
                this->val=node.val;
            }
        ~Node()
            {

            }
        friend std::ostream & operator<<(std::ostream &os,Node &node)
            {
                os<<node.val<<" ";
                return os;
            }
        Node* pre;
        Node* next;
    };
    typedef Node* iter;
    List()
        {
            tail=new Node();
        }
    virtual ~List(){
        destroy();
        assert( tail->next==tail);
        delete tail;
    }
    std::size_t size();
    virtual void insert(Type key);
    virtual void erase(iter it);
    iter begin(){ return tail->next;}
    iter end(){ return tail;}
    void walk();
protected:
    void swap(Node  &n1,Node &n2)
        {
            Node tmp=n1;
            n1=n2;
            n2=tmp;
        }
    void destroy();
private:
    iter tail;
};

template<class Type>
void List<Type>::insert(Type key)
{
    if( NULL==tail )
    {
        tail=new Node(key);
        tail->pre=tail;
        tail->next=tail;
    }
    else
    {
        iter it=new Node(key);
        it->pre=tail->pre;
        it->pre->next=it;
        it->next=tail;
        it->next->pre=it;
    }
}
template<class Type>
void List<Type>::erase(iter it)
{
    it->pre->next=it->next;
    it->next->pre=it->pre;
    delete it;
}
template<class Type>
std::size_t List<Type>::size()
{
    if( tail==tail->next)
        return 0;
    else
    {
        std::size_t sz=0;
        for(iter it=begin();it!=end();it=it->next)
        {
            sz++;
        }
        return sz;
    }
}
template<class Type>
void List<Type>::walk()
{
    iter it=tail;
    if( NULL != tail)
    {
        for(it=tail->next;it!=tail;it=it->next)
        {
            std::cout<<*it<<" ";
        }
        std::cout<<std::endl;
    }
}
template<class Type>
void List<Type>::destroy()
{
    for(List<Type>::iter it=begin();it !=end();it=it->next)
    {
        erase(it);
    }
}
template<class Type>
class Rank:public List<Type>{
public:
    Rank():List<Type>(){}
    void qsort()
        {
            sort(1,List<Type>::size(),List<Type>::begin(),(List<Type>::end())->pre);
        }
    typename List<Type>::Node * _rank_k(int k);
    ~Rank(){}
protected:
    pair<typename List<Type>::Node*,int> 
    partition(int p,int r,typename List<Type>::Node * pt,typename List<Type>::Node* rt)
        {
            Type x=rt->val;
            int i=p-1,j;
            typename List<Type>::Node* it;
            typename List<Type>::Node* jt;
            it=pt->pre;
            jt=pt;
            for(j=p;j<r;j++)
            {
                if(jt->val<=x)
                {
                    i=i+1;
                    it=it->next;
                    swap(*it,*jt);
                }
                jt=jt->next;
            }
            swap(*(it->next),*rt);
            return std::make_pair(it->next,i+1);
        }
    void sort(int p,int r,typename List<Type>::Node* pt,typename List<Type>::Node* rt)
        {
            if( p< r )
            {
                pair<typename List<Type>::Node*,int> qt;
                qt=partition(p,r,pt,rt);
                sort(p,qt.second-1,pt,qt.first->pre);
                sort(qt.second+1,r,qt.first->next,rt);
            }
        }
    typename List<Type>::Node* select(int p,int r,int i,typename List<Type>::Node* pt,typename List<Type>::Node* rt);
}; 
template<class Type>
typename List<Type>::Node * Rank<Type>::_rank_k(int k)
{
    assert(k+1<=List<Type>::size() &&k+1>0);
    return select(1,List<Type>::size(),k+1,List<Type>::begin(),List<Type>::end());
}
template<class Type>
typename List<Type>::Node* 
Rank<Type>::select(int p,int r,int i,typename List<Type>::Node*pt,typename List<Type>::Node * rt)
{
    if( p == r )
    {
        return pt;
    }
    pair<typename List<Type>::Node *,int>qt;
    qt=partition(p,r,pt,rt);
    int k=(qt.second)-p+1;
    if( i == k )
        return qt.first;
    else if( i< k)
        return select(p,qt.second-1,i,pt,qt.first->pre);
    else
        return select(qt.second+1,r,i-k,qt.first->next,rt);
}
int main()
{
    srand(time(NULL));
    Rank<int> rank;
    for(int i=0;i<10;i++)
    {
        int key=rand()%50;
        rank.insert(key);
    }
    rank.walk();
    //std::cout<<rank.size()<<std::endl;
    std::cout<<*(rank._rank_k(5))<<std::endl;
    //rank.qsort();
    //rank.walk();
    return 0;
}

我这个就是基于C++双向链表实现的算法。

你完全可以借鉴看看。