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

一介白书生

#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

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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. typedef struct _list
   
4. {
   
5.         int elem;
   
6.         struct _list *pPre;
   
7.         struct _list *pNext;
   
8. }List;
   
9. List *CreatList()//创建一个双线链表
   
10. {
    
11.         List *pHead = (List*)malloc(sizeof(List));
    
12.         pHead->elem = 0;
    
13.         pHead->pNext = pHead->pPre = NULL;
    
14.         return pHead;
    
15. }
    
16. void InsertList(List *pHead,int elem)//头插法插入数据函数
    
17. {
    
18.        
    
19.         if ((pHead->pNext==NULL) && (pHead->pPre==NULL))
    
20.         {
    
21.                 pHead->elem = elem;//数据初始化
    
22.                 pHead->pNext = pHead->pPre = pHead;
    
23. 
    
24.         }else
    
25.         {
    
26.                 List *pCur = pHead,*pTemp = pCur->pNext;
    
27.                 List *pNew = (List*)malloc(sizeof(List));
    
28.                 pNew->elem = elem;//数据初始化
    
29.                 pNew->pNext = pHead;
    
30.                 pNew->pPre = pHead->pPre;
    
31. 
    
32.                 pHead->pPre->pNext = pNew;
    
33.                 pHead->pPre = pNew;
    
34. 
    
35.         }
    
36.        
    
37.        
    
38. }
    
39. void Print(List *pHead)//打印链表函数
    
40. {
    
41.         printf("%d,",pHead->elem);
    
42.         List *pCurrent = pHead->pNext;
    
43.         while(pCurrent!=pHead)
    
44.         {
    
45.                 printf("%d,",pCurrent->elem);
    
46.                 pCurrent = pCurrent->pNext;
    
47.         }
    
48. }
    
49. void main()
    
50. {
    
51.         List *pHead = CreatList();
    
52.         List *pCur = pHead,*pPrev,*pT=pHead;
    
53.         int data[] = {1,32,4,3,24,2,5},count = 0,i = 0;
    
54.         count = sizeof(data)/sizeof(data[0]);
    
55.         for(i=0;i<count;i++)
    
56.         {
    
57.                 InsertList(pHead,data[i]);
    
58.         }
    
59.         //下面是插入法排序的算法，
    
60. //         while(pCur->pNext!=pHead)
    
61. //         {
    
62. //                 pPrev = pCur;
    
63. //                 for(pT=pPrev->pPre;pT!=pHead;pT=pT->pPre)
    
64. //                 {
    
65. //                         if(pT->elem <= pPrev->elem)
    
66. //                         {
    
67. //                                 break;
    
68. //                         }
    
69. //                 }
    
70. //                 pPrev->pNext = pT->pNext;
    
71. //                 pT->pNext = pPrev;
    
72. //                 pPrev->pPre = pT->pNext->pPre;
    
73. //                 pT->pNext->pPre = pPrev;
    
74. //
    
75. //         }
    
76.         Print(pHead);
    
77.         getchar();
    
78. }

复制代码

殇冰逝水

又学会了一招

向往青莲

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;

    }

1. void main()
   
2. {
   
3.     List *pHead = CreatList();
   
4.     List *pCur = pHead->pNext,*pPrev,*pT=pHead;
   
5.     int data[] = {1,32,4,3,24,2,5},count = 0,i = 0, j=0, Temp;
   
6.     count = sizeof(data)/sizeof(data[0]);
   
7.     for(i=0;i<count;i++)
   
8.     {
   
9.         InsertList(pHead,data[i]);
   
10.     }
    
11.   //???????????,
    
12.         for (i=0 ; i < count; i++)
    
13.         {
    
14.                 pT = pCur->pNext;
    
15.                 for(j=count-i; j>0; j--)
    
16.                 {
    
17.                         if (pT->elem < pCur->elem)
    
18.                         {
    
19.                                 Temp = pCur->elem;
    
20.                                 pCur->elem = pT->elem;
    
21.                                 pT->elem = Temp;
    
22.                         }
    
23.                         pT = pT->pNext;
    
24.                 }
    
25.                 pCur = pCur->pNext;
    
26.         }
    
27.         Print(pHead);
    
28. }

复制代码

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