[cpp] view plaincopy

 

1. typedef struct NODE{  
2.     struct NODE *fwd;  
3.     struct NODE *bwd;  
4.     int value;  
5. }Node;  

双链表的根节点的bwd指针指向双链表的最后一个节点，fwd指针指向双链表的第一个节点，双链表的value字段为空

以下程序是将一个值插入到一个有序的双链表中，如果链表中已经有和该值相同的节点则不插入

[cpp] view plaincopy

 

1. #include <stdio.h>  
2. #include <stdlib.h>  
3.   
4. typedef struct NODE{  
5.     struct NODE *bwd;  
6.     struct NODE *fwd;  
7.     int value;  
8. }Node;  
9.   
10. bool insert(Node *Rootnode,int newvalue);  
11.   
12. bool insert(Node *Rootnode,int newvalue)  
13. {  
14.     Node temnode;  
15.     int i = 0;  
16.     temnode = Rootnode;  
17.     Node *newnode = (Node*)malloc(sizeof(Node));  
18.     if(newnode ==NULL)  
19.     {  
20.         printf("malloc fail");  
21.         return false;  
22.     }  
23.     newnode->value = newvalue;  
24.     if (Rootnode->bwd == NULL)  
25.     {  
26.         Rootnode->bwd = newnode;  
27.         Rootnode->fwd = newnode;  
28.         return true;  
29.     }  
30.     for(;temnode->fwd != NULL;temnode = temnode->fwd)  
31.     {  
32.         i++;  
33.         if (temnode->value == newvalue)  
34.         {  
35.             printf("newvalue is already in double link list");  
36.             return true;  
37.         }  
38.         if (temnode->value > newvalue)  
39.         {  
40.             if (i==1)  
41.             {  
42.                 newnode->fwd = Rootnode->fwd;  
43.                 Rootnode->fwd = newnode;  
44.                 newnode->bwd = Rootnode;  
45.                 newnode->fwd->bwd=newnode;  
46.             }  
47.             else   
48.             {  
49.                 temnode = temnode->bwd;  
50.                 newnode->fwd = temnode->fwd;  
51.                 temnode->fwd = newnode;  
52.                 newnode->bwd = temnode;  
53.                 newnode->fwd->bwd=newnode;  
54.             }  
55.         }  
56.         else  
57.         {  
58.             temnode = temnode->bwd;  
59.             newnode = temnode->fwd;  
60.             newnode->bwd = temnode;  
61.         }  
62.     }  
63.   
64.     return true;  
65.   
66. }  

[数据结构]双链表