双向链表排序、插入删除等基本操作

  1 // list.cpp : 定义控制台应用程序的入口点。
  2 //
  3 
  4 #include "stdafx.h"
  5 #include<stdlib.h>
  6 typedef struct tag_data
  7 {
  8     int age;
  9 }Data;
 10 typedef struct tag_node Node;
 11 typedef struct tag_node
 12 {
 13     Node* pnext;
 14     Node* pprev;
 15     Data data;
 16 }Node;
 17 typedef struct tag_nodecb NodeCb;
 18 typedef struct tag_nodecb
 19 {
 20     Node* pHead;
 21     Node* pTail;
 22     int nodecount;
 23 }NodeCb;
 24 NodeCb* g_pNodeCb = NULL;
 25 int InitList(NodeCb** ppNodeCb)
 26 {
 27     NodeCb* pNodeCbTmp = (NodeCb*)malloc(sizeof(NodeCb));
 28     if (pNodeCbTmp == NULL)
 29     {
 30         printf("malloc NodeCb failed...\n");
 31         return -1;
 32     }
 33     pNodeCbTmp->pHead = NULL;
 34     pNodeCbTmp->pTail = NULL;
 35     pNodeCbTmp->nodecount = 0;
 36 
 37     *ppNodeCb = pNodeCbTmp;
 38     return 0;
 39 }
 40 Node* FindNode(NodeCb* pNodeCb, int index)
 41 {
 42     //0,max  
 43     int i;
 44     Node* pNodeTmp = g_pNodeCb->pHead;
 45     for (i = 1; i < index; i++, pNodeTmp = pNodeTmp->pnext)
 46     {
 47 
 48     }
 49     return pNodeTmp;
 50 
 51 }
 52 int InsertNode(Node* pNodeNew, int index)
 53 {
 54     if (g_pNodeCb->pTail == NULL || g_pNodeCb->pHead == NULL)
 55     {
 56         g_pNodeCb->pHead = pNodeNew;
 57         g_pNodeCb->pTail = pNodeNew;
 58         pNodeNew->pnext = NULL;
 59         pNodeNew->pprev = NULL;
 60         (g_pNodeCb->nodecount) ++;
 61         return 0;
 62     }
 63     if (index > g_pNodeCb->nodecount)
 64     {
 65         pNodeNew->pnext = NULL;
 66         pNodeNew->pprev = g_pNodeCb->pTail;
 67         g_pNodeCb->pTail->pnext = pNodeNew;
 68         g_pNodeCb->pTail = pNodeNew;
 69         (g_pNodeCb->nodecount)++;
 70         return 0;
 71     }
 72     if (index == 1 || index ==0)
 73     {
 74         g_pNodeCb->pHead->pprev = pNodeNew;
 75         pNodeNew->pprev = NULL;
 76         pNodeNew->pnext = g_pNodeCb->pHead;
 77         g_pNodeCb->pHead = pNodeNew;
 78         (g_pNodeCb->nodecount)++;
 79         return 0;
 80     }
 81     
 82     Node* pNodeTmp = FindNode(g_pNodeCb, index);
 83     pNodeNew->pnext = pNodeTmp;
 84     pNodeNew->pprev = pNodeTmp->pprev;
 85     pNodeTmp->pprev->pnext = pNodeNew;
 86     pNodeTmp->pprev = pNodeNew;
 87     (g_pNodeCb->nodecount)++;
 88     return 0;
 89 }
 90 int DeleteNode(NodeCb* pNodeCb, int index)
 91 {
 92     if (g_pNodeCb->pTail == NULL || g_pNodeCb->pHead == NULL)
 93     {
 94         printf("empty list...\n");
 95         return -1;
 96     }
 97     if (index == 0 || index == 1)
 98     {
 99         g_pNodeCb->pHead = g_pNodeCb->pHead->pnext;
100         g_pNodeCb->pHead->pprev = NULL;
101         (g_pNodeCb->nodecount)--;
102         //malloc的节点需要free
103         return 0;
104     }
105     if (index >= g_pNodeCb->nodecount)
106     {
107         g_pNodeCb->pTail = g_pNodeCb->pTail->pprev;
108         g_pNodeCb->pTail->pnext = NULL;
109         (g_pNodeCb->nodecount)--;
110         //malloc的节点需要free
111         return 0;
112     }
113     Node* pNodeTmp = FindNode(g_pNodeCb, index);
114 
115     pNodeTmp->pnext->pprev = pNodeTmp->pprev;
116     pNodeTmp->pprev->pnext = pNodeTmp->pnext;
117     (g_pNodeCb->nodecount)--;
118     //malloc的节点需要free
119     return 0;
120 }
121 int ShowList(NodeCb* pNodeCb)
122 {
123     Node* pNodeTmp = pNodeCb->pHead;
124 
125     for (int i = 0; i < pNodeCb->nodecount; i++, pNodeTmp = pNodeTmp->pnext)
126         printf("%d\n", pNodeTmp->data.age);
127     printf("--------------------------\n");
128     return 0;
129 }
130 int SwapNode( Node* pNodeJ,Node* pNodeJ_1)
131 {
132     if (pNodeJ->pprev == NULL)
133     {
134         pNodeJ->pnext = pNodeJ_1->pnext;
135         pNodeJ_1->pnext->pprev = pNodeJ;
136         pNodeJ_1->pnext = pNodeJ;
137         pNodeJ->pprev = pNodeJ_1;
138         g_pNodeCb->pHead = pNodeJ_1;
139         pNodeJ_1->pprev = NULL;
140         return 0;
141     }
142     if (pNodeJ_1->pnext == NULL)
143     {
144         pNodeJ->pprev->pnext = pNodeJ_1;
145         pNodeJ_1->pprev = pNodeJ->pprev;
146         pNodeJ_1->pnext = pNodeJ;
147         pNodeJ->pprev = pNodeJ_1;
148         pNodeJ->pnext = NULL;
149         g_pNodeCb->pTail = pNodeJ;
150         return 0;
151     }
152 
153     pNodeJ->pprev->pnext = pNodeJ_1;
154     pNodeJ_1->pprev = pNodeJ->pprev;
155     
156     pNodeJ->pnext = pNodeJ_1->pnext;
157     pNodeJ_1->pnext->pprev = pNodeJ;
158     pNodeJ_1->pnext = pNodeJ;
159     pNodeJ->pprev = pNodeJ_1;
160     return 0;
161 
162 
163 }
164 int BubbleSort(NodeCb* pNodeCb)
165 {
166     Node* pNodeJ = NULL;
167     Node* pNodeJ_1 = NULL;
168     int i = 1, j = 2;
169 
170     for (i = pNodeCb->nodecount; i > 1; i--)
171     for (j = 1; j < i; j++)
172     //for (j = 1; j < pNodeCb->nodecount; j++)
173     {
174         pNodeJ   = FindNode(pNodeCb, j);
175         pNodeJ_1 = FindNode(pNodeCb, j + 1);
176 
177         if (pNodeJ->data.age>pNodeJ_1->data.age)
178         {
179             SwapNode(pNodeJ, pNodeJ_1);
180         }
181     }
182     return 0;
183 }
184 int _tmain(int argc, _TCHAR* argv[])
185 {
186     Node a, b, c, d, e, f,g,h;
187     a.data.age = 4;
188     b.data.age = 8;
189     c.data.age = 2;
190     d.data.age = 5;
191     e.data.age = 10;
192     f.data.age = 6;
193     g.data.age = 3;
194     h.data.age = 1;
195     InitList(&g_pNodeCb);
196     InsertNode(&a, 1);
197     InsertNode(&b, 10);
198     InsertNode(&c, 10);
199     InsertNode(&d, 2);
200     InsertNode(&e, 4); 
201     InsertNode(&f, 10);
202     InsertNode(&g, 5);
203     InsertNode(&h, 6);
204     ShowList(g_pNodeCb);
205     //DeleteNode(g_pNodeCb, 5);
206     //ShowList(g_pNodeCb);
207     BubbleSort(g_pNodeCb);
208     ShowList(g_pNodeCb);
209     return 0;
210 }