代码实现如下：
1 #include2 #include 3 4 typedef int itemType; 5 struct Node; 6 typedef struct Node *pNode; 7 typedef pNode list; 8 typedef pNode position; 9 10 struct Node { 11 itemType item; 12 position prev, next; 13 }; 14 15 list 16 MakeEmpty(list l) 17 { 18 l->item = 0; 19 l->prev = NULL; 20 l->next = l; 21 } 22 23 int 24 IsEmpty(list l) 25 { 26 /* 27 if (l->next == NULL) { 28 return 1; 29 } else { 30 return 0; 31 } 32 */ 33 return l->next == NULL; 34 } 35 36 int 37 IsLast(position p, list l) 38 { 39 return p->next == l; 40 } 41 42 position 43 Find(itemType item, list l) 44 { 45 position p; 46 47 p = l->next; 48 while (p != l && p->item != item) { 49 p = p->next; 50 } 51 52 return p; 53 } 54 /* 55 position 56 FindPrevious(itemType item, list l) 57 { 58 position p; 59 60 p = l; 61 while (p->next != NULL && p->next->item != item) { 62 p = p->next; 63 } 64 65 return p; 66 } 67 */ 68 void 69 Delete(itemType item, list l) 70 { 71 position p, tmp; 72 73 p = Find(item, l); 74 75 if (p != l) { 76 p->next->prev = p->prev; 77 p->prev->next = p->next; 78 free(p); 79 } 80 } 81 82 void 83 Insert(itemType item, list l, position p) 84 { 85 position tmp; 86 87 tmp = (position)malloc(sizeof(struct Node)); 88 if (tmp == NULL) { 89 printf("Out of space!\n"); 90 return; 91 } 92 93 tmp->item = item; 94 tmp->next = p->next; 95 tmp->prev = p; 96 p->next = tmp; 97 if (IsLast(tmp, l)) { 98 l->prev = tmp; 99 }100 }101 102 void103 DeleteList(list l)104 {105 position p, tmp;106 107 p = l->next;108 while (p != NULL) {109 tmp = p;110 p = p->next;111 free(tmp);112 } 113 free(l);114 }115 116 position117 Header(list l)118 {119 return l;120 }121 122 position123 First(list l)124 {125 return l->next;126 }127 128 position129 Advance( position p )130 {131 return p->next;132 }133 134 itemType135 Retrieve( position p )136 {137 return p->item;138 }139 140 void141 PrintList( list l)142 {143 position p;144 p = First(l);145 while (p != l) {146 printf("%d\t", Retrieve(p));147 p = Advance(p);148 }149 printf("\n");150 }151 152 int153 main(int argc, char** argv)154 {155 list l;156 // init157 l = (list)malloc(sizeof(struct Node));158 MakeEmpty(l);159 // insert some elememts160 position p;161 p = Header(l);162 for (int i = 1; i < 11; i++) {163 Insert(i, l, p);164 p = Advance(p);165 }166 // retrieve167 PrintList(l);168 // find and delete169 Delete(1, l);170 Delete(10, l);171 Delete(100, l);172 PrintList(l);173 174 printf("%d\n", l->prev->item);175 176 system("pause");177 return 0;178 }