重新实现了单链表，以指针而非哑节点的方式去指向第一个节点。

 

代码如下：

 

1 /*  2  * 第二版链表实现   3  * 原先的实现，是以哑节点的方式来做链表的头部。  4  * 现在我们使用一个指针来做链表的头部，节约一个struct Node的空间   5  */  6   7 #include 
     
        8 #include 
      
         9  10 typedef int itemType; 11 struct Node; 12 typedef struct Node *pNode; 13 typedef pNode list; 14 typedef pNode position; 15  16 struct Node { 17     itemType item; 18     position next; 19 }; 20  21 int 22 IsEmpty(list l) 23 { 24     return l == NULL; 25 } 26  27 int 28 IsLast(position p, list l) 29 { 30     return p->next == NULL; 31 } 32  33 position 34 Find(itemType item, list l) 35 { 36     while (l != NULL && l->item != item) { 37         l = l->next; 38     } 39      40     return NULL; 41 } 42  43 list 44 Delete(itemType item, list l) 45 { 46     position p, prev; 47     prev = NULL; 48      49     for (p = l; p != NULL; p = p->next) { 50         if (p->item != item) { 51             prev = p; 52         } else { 53             if (prev == NULL) { 54                 l = l->next; 55             } else { 56                 prev->next = p->next; 57             } 58             free(p); 59             return l; 60         } 61     } 62      63     printf("Item: %d is not found!\n", item); 64     return l;          65 } 66  67 list 68 InsertFront(itemType x, list l) { 69     position newNode; 70     newNode = (position)malloc(sizeof(struct Node)); 71     if (newNode == NULL) { 72         printf("Out of space!\n"); 73         return NULL; 74     } 75      76     newNode->item = x; 77     newNode->next = l; 78     return newNode; 79 } 80  81 void 82 DeleteList(list l) 83 { 84     position p, tmp; 85      86     p = l; 87     while (p != NULL) { 88         tmp = p; 89         p = p->next; 90         free(tmp); 91     }    92 } 93  94 position 95 Header(list l) 96 { 97     return l; 98 } 99 100 position101 Advance( position p )102 {103     return p->next;104 }105 106 itemType107 Retrieve( position p )108 {109     return p->item;110 }111 112 void113 PrintList( list l)114 {115     position p;116     p = Header(l);117     while (p != NULL) {118         printf("%d\t", Retrieve(p));119         p = Advance(p);120     }121     printf("\n");122 }123 124 int125 main(int argc, char** argv)126 {127     list l;128     l = NULL;129     // insert some elememts130     for (int i = 0; i < 10; i++) {131         l = InsertFront(i, l);132     }133     // retrieve134     PrintList(l);135     // find and delete136     l = Delete(0, l);137     l = Delete(9, l);138     l = Delete(100, l);139     PrintList(l);140     141     system("pause");142     return 0;143 }