双向链表的插入排序，顺便问问单链表怎样写插入排序》？？

一介白书生

#include <stdio.h>
#include <stdlib.h>
typedef struct _list
{
    int elem;
    struct _list *pPre;
    struct _list *pNext;
}List;
List *CreatList()//创建一个双线链表
{
    List *pHead = (List*)malloc(sizeof(List));
    pHead->pNext = pHead->pPre = pHead;
    return pHead;
}
void InsertList(List *pHead,int elem)//头插法插入数据函数
{
     List *pCur = pHead,*pTemp = pCur->pNext;
    List *pNew = (List*)malloc(sizeof(List));
    pNew->elem = elem;//数据初始化
//以下是插入过程
    pNew->pNext = pCur->pNext;
    pCur->pNext = pNew;

    pNew->pPre = pTemp->pPre;
    pTemp->pPre = pNew;
}
void Print(List *pHead)//打印链表函数
{
    List *pCurrent = pHead->pNext;
    while(pCurrent!=pHead)
    {
        printf("%d,",pCurrent->elem);
        pCurrent = pCurrent->pNext;
    }
}
void main()
{
    List *pHead = CreatList();
    List *pCur = pHead->pNext,*pPrev,*pT=pHead;
    int data[] = {1,32,4,3,24,2,5},count = 0,i = 0;
    count = sizeof(data)/sizeof(data[0]);
    for(i=0;i<count;i++)
    {
        InsertList(pHead,data[i]);
    }
  //下面是插入法排序的算法，
    while(pCur->pNext!=pHead)
    {
        pPrev = pCur;
        for(pT=pPrev->pPre;pT!=pHead;pT=pT->pPre)
        {
            if(pT->elem <= pPrev->elem)
            {
               break;
            }
        }
        pPrev->pNext = pT->pNext;
        pT->pNext = pPrev;
        pPrev->pPre = pT->pNext->pPre;
        pT->pNext->pPre = pPrev;

    }
    Print(pHead);
}我觉得插入法的算法是对的，但就是不能运行，为什么？？求大神解决，另外那个单向链表的插入法的算法该如何解决？？

小新110

老实说没怎么看懂你的代码，双向链表我也不是很懂，所以查资料搞了半天也没全搞出来。
大概你的意思是先创建一个双向循环链表，插入元素，然后排序，最后输出。
改了一部分，可以实现创建，插入还有输出了，排序还没看，没想到办法呢
明天学习一下再看
以下是代码，仅供参考：

#include <stdio.h>
#include <stdlib.h>
typedef struct _list
{
        int elem;
        struct _list *pPre;
        struct _list *pNext;
}List;
List *CreatList()//创建一个双线链表
{
        List *pHead = (List*)malloc(sizeof(List));
        pHead->elem = 0;
        pHead->pNext = pHead->pPre = NULL;
        return pHead;
}
void InsertList(List *pHead,int elem)//头插法插入数据函数
{
        
        if ((pHead->pNext==NULL) && (pHead->pPre==NULL))
        {
                pHead->elem = elem;//数据初始化
                pHead->pNext = pHead->pPre = pHead;

        }else
        {
                List *pCur = pHead,*pTemp = pCur->pNext;
                List *pNew = (List*)malloc(sizeof(List));
                pNew->elem = elem;//数据初始化
                pNew->pNext = pHead;
                pNew->pPre = pHead->pPre;

                pHead->pPre->pNext = pNew;
                pHead->pPre = pNew;

        }
        
        
}
void Print(List *pHead)//打印链表函数
{
        printf("%d,",pHead->elem);
        List *pCurrent = pHead->pNext;
        while(pCurrent!=pHead)
        {
                printf("%d,",pCurrent->elem);
                pCurrent = pCurrent->pNext;
        }
}
void main()
{
        List *pHead = CreatList();
        List *pCur = pHead,*pPrev,*pT=pHead;
        int data[] = {1,32,4,3,24,2,5},count = 0,i = 0;
        count = sizeof(data)/sizeof(data[0]);
        for(i=0;i<count;i++)
        {
                InsertList(pHead,data[i]);
        }
        //下面是插入法排序的算法，
//         while(pCur->pNext!=pHead)
//         {
//                 pPrev = pCur;
//                 for(pT=pPrev->pPre;pT!=pHead;pT=pT->pPre)
//                 {
//                         if(pT->elem <= pPrev->elem)
//                         {
//                                 break;
//                         }
//                 }
//                 pPrev->pNext = pT->pNext;
//                 pT->pNext = pPrev;
//                 pPrev->pPre = pT->pNext->pPre;
//                 pT->pNext->pPre = pPrev;
// 
//         }
        Print(pHead);
        getchar();
}

殇冰逝水

又学会了一招

向往青莲

while(pCur->pNext!=pHead)
    {
        pPrev = pCur;
        for(pT=pPrev->pPre;pT!=pHead;pT=pT->pPre) //第一次跑到这里，然后不成立，就跑过for循环
        {
            if(pT->elem <= pPrev->elem)
            {
               break;
            }
        }
        pPrev->pNext = pT->pNext;//来到这里就开始出错了  你的链表最后一个节点指向Head节点，不是指向Head->pNext节点，Head节点只是便于操作的指针，没有数值，而你又用前指针排序，肯定错误，因为看了很久不知道你到底打算怎么排序，所以我就直接来来个冒泡排序，你懂得
        pT->pNext = pPrev;
        pPrev->pPre = pT->pNext->pPre;
        pT->pNext->pPre = pPrev;

    }

void main()
{
    List *pHead = CreatList();
    List *pCur = pHead->pNext,*pPrev,*pT=pHead;
    int data[] = {1,32,4,3,24,2,5},count = 0,i = 0, j=0, Temp;
    count = sizeof(data)/sizeof(data[0]);
    for(i=0;i<count;i++)
    {
        InsertList(pHead,data[i]);
    }
  //???????????,
        for (i=0 ; i < count; i++)
        {
                pT = pCur->pNext;
                for(j=count-i; j>0; j--)
                {
                        if (pT->elem < pCur->elem)
                        {
                                Temp = pCur->elem;
                                pCur->elem = pT->elem;
                                pT->elem = Temp;
                        }
                        pT = pT->pNext;
                }
                pCur = pCur->pNext;
        }
        Print(pHead);
}

252013680

学习{:1_1:}{:1_1:}

一介白书生

向往青莲 发表于 2013-4-26 00:23

                               
登录/注册后可看大图

while(pCur->pNext!=pHead)
    {
        pPrev = pCur;

还是很感谢你，我这个还是想用插入法排序实现哈

一介白书生

小新110 发表于 2013-4-25 23:56

                               
登录/注册后可看大图

老实说没怎么看懂你的代码，双向链表我也不是很懂，所以查资料搞了半天也没全搞出来。
大概你的意思是先创 ...

还是很谢谢你的，希望你能给我答案，插入法排序

向往青莲

一介白书生 发表于 2013-4-26 16:56

                               
登录/注册后可看大图

还是很感谢你，我这个还是想用插入法排序实现哈

话说啥叫插入法排序   我一般需要这种时候都是查书的   完全没去记这些排序的名称   抱歉啊    因为挺忙的  就懒得弄了   have a good luck

小新110

一介白书生 发表于 2013-4-26 16:59

                               
登录/注册后可看大图

还是很谢谢你的，希望你能给我答案，插入法排序

同问，啥叫  插入法排序？

殇冰逝水

看看，长知识了

540167078

我只是路过打酱油的。

lsh華

无回帖，不论坛，这才是人道。

y290176346

我是来领鱼币的

东河

看看

鱼C工作室.YCGZS

顿时释然饿了

susijie0021

:smile