首页 > 代码库 > 单链表（二）
单链表（二）
重新实现了单链表，以指针而非哑节点的方式去指向第一个节点。
代码如下：
1 /* 2 * 第二版链表实现 3 * 原先的实现，是以哑节点的方式来做链表的头部。 4 * 现在我们使用一个指针来做链表的头部，节约一个struct Node的空间 5 */ 6 7 #include <cstdio> 8 #include <cstdlib> 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 }
单链表（二）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。