论坛 › 数据结构与算法 › 双向链表的插入排序，顺便问问单链表怎样写插入排序》？？

一介白书生 发表于 2013-4-25 22:01:10

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

#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);
    for(i=0;i<count;i++)
    {
      InsertList(pHead,data);
    }
//下面是插入法排序的算法，
    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 发表于 2013-4-25 23:56:05

老实说没怎么看懂你的代码，双向链表我也不是很懂，所以查资料搞了半天也没全搞出来。
大概你的意思是先创建一个双向循环链表，插入元素，然后排序，最后输出。
改了一部分，可以实现创建，插入还有输出了，排序还没看，没想到办法呢
明天学习一下再看
以下是代码，仅供参考：
#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);
        for(i=0;i<count;i++)
        {
                InsertList(pHead,data);
        }
        //下面是插入法排序的算法，
//         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();
}

殇冰逝水 发表于 2013-4-26 00:01:30

又学会了一招

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

本帖最后由 向往青莲 于 2013-4-26 00:26 编辑

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);
    for(i=0;i<count;i++)
    {
      InsertList(pHead,data);
    }
//???????????,
      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 发表于 2013-4-26 15:38:27

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

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

向往青莲 发表于 2013-4-26 00:23 static/image/common/back.gif
while(pCur->pNext!=pHead)
    {
      pPrev = pCur;


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

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

小新110 发表于 2013-4-25 23:56 static/image/common/back.gif
老实说没怎么看懂你的代码，双向链表我也不是很懂，所以查资料搞了半天也没全搞出来。
大概你的意思是先创 ...

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

向往青莲 发表于 2013-4-26 17:56:15

一介白书生 发表于 2013-4-26 16:56 static/image/common/back.gif
还是很感谢你，我这个还是想用插入法排序实现哈

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

小新110 发表于 2013-4-27 10:54:26

一介白书生 发表于 2013-4-26 16:59 static/image/common/back.gif
还是很谢谢你的，希望你能给我答案，插入法排序

同问，啥叫插入法排序？

殇冰逝水 发表于 2013-4-28 09:19:45

看看，长知识了

540167078 发表于 2013-5-8 20:47:22

我只是路过打酱油的。

lsh華 发表于 2013-6-8 13:55:35

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

y290176346 发表于 2015-9-19 16:40:44

我是来领鱼币的

东河 发表于 2015-9-21 15:37:48

看看

鱼C工作室.YCGZS 发表于 2015-12-7 17:10:28

顿时释然饿了

susijie0021 发表于 2015-12-10 13:11:40

:smile

查看完整版本: 双向链表的插入排序，顺便问问单链表怎样写插入排序》？？