首页 > 代码库 > 数据结构之链表
数据结构之链表
---恢复内容开始---
1：有头节点、单向、不循环链表
对于这种有头节点的单向不循环链表插入数据如下图：
1)头部插入
2)尾部插入
代码如下 :
1 #include "stdafx.h" 2 #include<iostream> 3 4 using namespace std; 5 6 typedef int DATA; 7 typedef struct node* LIST; 8 9 struct node 10 { 11 DATA data; 12 struct node* next; //指向下一个节点的指针 13 }; 14 15 //创建头节点 16 LIST ListCreate() 17 { 18 struct node* head = (struct node*) malloc(sizeof(*head)); 19 if (head == NULL) 20 { 21 return NULL; 22 } 23 //这个时候只有头节点，head->next = null;数据为空 24 head->next = NULL; 25 //返回指向头节点的头指针 26 return head; 27 } 28 29 //判断一个链表是否是空链表 30 int ListIsEmpty( LIST l) 31 { 32 return l->next == NULL; 33 } 34 35 //判断是不是链表的最后一个元素 36 int ListIsLast(LIST l, struct node* p) 37 { 38 return p->next == NULL; 39 } 40 41 //插入链表元素 其实这个地方主要分为尾部插入，还是头部插入 42 int ListInsert(LIST l, struct node* prev,const DATA *data ) 43 { 44 struct node* cur = (struct node*)malloc(sizeof(*cur)); 45 if (cur == NULL) 46 { 47 return -1; 48 } 49 cur->data = http://www.mamicode.com/*data; 50 cur->next = prev->next; 51 prev->next = cur; 52 return 0; 53 } 54 55 int ListInsertHead(LIST l, const DATA* data) 56 { 57 return ListInsert(l,l,data); 58 } 59 60 int ListInsertTail( LIST l, const DATA* data ) 61 { 62 struct node* tail = l; 63 for (; tail->next != NULL; tail = tail->next); //空循环，找到尾节点 64 return ListInsert(l,tail,data); 65 } 66 67 //查找 68 struct node* ListFind(LIST l,const DATA* data ) 69 { 70 struct node* p = l->next; //要考虑到空链表的情况就是p != null 从头节点的next开始查找，是因为头节点是不存放数据的，所以从头节点开始查找是没有意义的。 71 for (; p != NULL && p->data != *data; p = p->next); 72 return p; 73 } 74 75 //查找前驱节点 76 struct node* ListFindPrev(LIST l, const DATA* data) 77 { 78 struct node* p = l; //查找前驱的话不能再指向头节点的下一个节点了，如果是一个空链表的话，就没有意义了， 79 80 for (;p->next != NULL && p->next->data != *data; p = p->next); 81 82 return p; 83 } 84 85 //删除链表元素 86 int ListDelete(LIST l, const DATA* data) 87 { 88 //头节点是不能删除的 89 struct node* prev = ListFindPrev(l,data); //这里就能处理到找不到或者是头节点的情况 90 if (!ListIsLast(l, prev)) 91 { 92 struct node *q = prev->next; //即q就是要删除的元素； 93 prev->next = q->next; 94 free(q); 95 return 0; 96 } 97 return -1; 98 } 99 100 //打印列表 101 void ListDisplay(LIST l) 102 { 103 struct node * p = l->next; 104 while (p != NULL ) 105 { 106 printf("%d ", p->data); 107 p = p->next; 108 } 109 printf("\n"); 110 } 111 112 //销毁链表 113 void ListDispose(LIST l) 114 { 115 struct node *p = l->next; 116 struct node* q; 117 while (p != NULL) 118 { 119 q = p; 120 p = p->next; 121 free(q); 122 } 123 124 free(l); 125 } 126 127 int main() 128 { 129 int i; 130 DATA x; 131 132 LIST head = ListCreate(); 133 if (head == NULL) 134 return -1; 135 136 //插入 137 for (i = 0; i < 6; i++) 138 { 139 x = i + 1; 140 //ListInsertHead(head,&x); 141 ListInsertTail(head,&x); 142 } 143 printf("链表里面的元素:: "); 144 ListDisplay(head); 145 146 printf("从链表里面查找元素3\n"); 147 DATA y = 3; 148 //查找 149 struct node* p = ListFind(head,&y); 150 if (p == NULL) 151 printf("not find!!!\n"); 152 else 153 printf("data = http://www.mamicode.com/%d/n", p->data); 154 155 printf("从链表里面删除元素3\n"); 156 ListDelete(head,&y); 157 ListDisplay(head); 158 159 // 160 printf("销毁链表\n"); 161 ListDispose(head); 162 system("pause"); 163 164 return 0; 165 }
2:有头节点、单向、循环链表
1):头部插入
2)尾部插入
代码如下：
1 // test04.cpp : Defines the entry point for the console application. 2 //有头节点、单向、循环链表 3 4 #include "stdafx.h" 5 #include<iostream> 6 7 using namespace std; 8 9 struct node; 10 typedef int DATA; 11 typedef struct node* LIST; 12 13 struct node 14 { 15 DATA data; 16 struct node* next; 17 }; 18 19 //创建头节点 20 LIST ListCreate() 21 { 22 LIST head = (struct node*)malloc(sizeof(*head)); 23 if ( head == NULL ) 24 { 25 return NULL; 26 } 27 28 head->next = head; 29 30 return head; 31 } 32 33 //插入 34 int ListInsert( LIST l, struct node* position, const DATA* data ) 35 { 36 struct node* cur = (struct node*)malloc(sizeof(*cur)); 37 if ( cur == NULL ) 38 { 39 return 0; 40 } 41 cur->data = http://www.mamicode.com/*data; 42 cur->next = position->next; 43 position->next = cur; 44 45 return 0; 46 } 47 48 //头部插入 49 int ListHeadInsert(LIST l, const DATA* data) 50 { 51 return ListInsert(l,l,data); 52 } 53 54 //尾部插入 55 int ListTailHead(LIST l, const DATA* data ) 56 { 57 struct node* tail = l; 58 for (; tail->next != l; tail = tail->next); 59 return ListInsert(l,tail,data); 60 } 61 62 //查找 63 struct node* ListFind( LIST l, const DATA* data ) 64 { 65 struct node* p = l->next; 66 for (; p != l && p->data != *data; p = p->next); 67 return p; 68 } 69 70 struct node* ListFindPrev(LIST l, const DATA* data) 71 { 72 struct node* p = l; 73 for (; p->next != l && p->next->data != *data; p = p->next); 74 return p; 75 } 76 //删除 77 int ListDelete( LIST l, const DATA* data ) 78 { 79 struct node* prev = ListFindPrev( l, data ); 80 if ( prev != l) //不是头节点 81 { 82 struct node* q = prev->next; 83 prev->next = q->next; 84 free(q); 85 } 86 return 0; 87 } 88 89 //打印出来列表 90 void ListDisplay(LIST l) 91 { 92 struct node* p = l->next; 93 while (p != l) 94 { 95 printf("%d ",p->data); 96 p = p->next; 97 } 98 printf("\n"); 99 } 100 101 //消耗链表 102 void ListDispose(LIST l) 103 { 104 struct node* p = l->next; 105 struct node* q; 106 while (p != l) 107 { 108 q = p; 109 p = p->next; 110 free(q); 111 } 112 free(l); 113 } 114 115 int main() 116 { 117 int i; 118 DATA x; 119 LIST head = NULL; 120 head = ListCreate(); 121 if (head == NULL) 122 { 123 return 0; 124 } 125 126 for (i = 0; i < 6; i++) 127 { 128 x = i + 1; 129 //ListHeadInsert(head,&x); 130 ListTailHead(head,&x); 131 } 132 // 133 printf("打印链表::\n"); 134 ListDisplay(head); 135 136 DATA y = 3; 137 struct node* p = ListFind(head,&y); 138 if (p == NULL) 139 printf("not find!!!!"); 140 else 141 printf("找到元素%d\n", p->data); 142 143 //删除元素 144 printf("删除元素之前，删除的元素是3\n"); 145 ListDelete(head,&y); 146 printf("删除元素之后\n"); 147 ListDisplay(head); 148 149 ListDispose(head); 150 151 system("pause"); 152 return 0; 153 }
输出如下:
3:有头节点、双向、循环链表
1):头部插入
2):尾部插入
代码如下：
1 // test02.cpp : Defines the entry point for the console application. 2 // 3 4 #include "stdafx.h" 5 #include<iostream> 6 7 using namespace std; 8 9 typedef struct headnode* LIST; 10 11 typedef void print_s(const void*); 12 typedef int cmp(const void*, const void*); 13 14 #define HEADINSERT 1 15 #define TAILINSERT 2 16 #define NAMESIZE 24 17 //有头节点、双向、循环链表 18 typedef struct stuinfo 19 { 20 int id; 21 char name[NAMESIZE]; 22 int math; 23 } DATA; 24 25 struct listnode 26 { 27 void* data; 28 struct listnode* prev; 29 struct listnode* next; 30 }; 31 struct headnode 32 { 33 int size; //指向下面要插入数据的大小 34 struct listnode head; //指向下一个节点的指针 35 }; 36 37 //创建头节点 38 LIST ListCreate( int size ) 39 { 40 LIST handle = (struct headnode*)malloc(sizeof(*handle)); 41 if (handle == NULL) 42 { 43 return NULL; 44 } 45 handle->size = size; 46 handle->head.data =http://www.mamicode.com/ NULL; 47 handle->head.prev = handle->head.next = &handle->head; 48 49 return handle; 50 } 51 52 //插入链表元素 其实这个地方主要分为尾部插入，还是头部插入 53 int ListInsert( LIST l,const void *data, int mode ) 54 { 55 struct listnode* cur = (struct listnode*)malloc(sizeof(*cur)); 56 if (cur == NULL) 57 { 58 return -1; 59 } 60 cur->data = http://www.mamicode.com/malloc(l->size); 61 if (cur->data =http://www.mamicode.com/= NULL) 62 { 63 free(cur); 64 return -1; 65 } 66 memcpy(cur->data,data,l->size); 67 if (mode == HEADINSERT) //首部插入 68 { 69 cur->prev = &l->head; 70 cur->next = l->head.next; 71 ///// 72 //cur->prev->next = cur; 73 //cur->next->prev = cur; 74 } 75 else if (mode == TAILINSERT) 76 { 77 cur->next = &l->head; 78 cur->prev = l->head.prev; 79 /////// 80 //cur->prev->next = cur; 81 //cur->next->prev = cur; //可以把相同的两句话提取出来 82 } 83 else 84 { 85 free(cur->data); 86 free(cur); 87 return -1; 88 } 89 cur->prev->next = cur; 90 cur->next->prev = cur; 91 92 return 0; 93 } 94 95 96 //查找 97 struct listnode* ListFind(LIST l,const void* key,cmp* funp) 98 { 99 struct listnode* p = l->head.next; // 100 for (; p != &l->head && funp(key, p->data); p = p->next); 101 102 return p; 103 } 104 105 //找到指定的元素 106 void* listfind(LIST l, const void* key, cmp* funp) 107 { 108 return ListFind(l,key,funp)->data; 109 } 110 111 //删除链表元素 112 int ListDelete(LIST l, const void* key, cmp* funp ) 113 { 114 //找到指定的元素删除 115 struct listnode* p = ListFind(l,key,funp); 116 if ( p == &l->head ) //头节点不会删除掉 117 { 118 return 0; 119 } 120 121 p->prev->next = p->next; 122 p->next->prev = p->prev; 123 124 free(p->data); 125 free(p); 126 127 return 0; 128 } 129 130 //打印链表 131 void ListDisplay(LIST l, print_s* funp ) 132 { 133 struct listnode* p = l->head.next; 134 while (p != &l->head) 135 { 136 funp(p->data); 137 p = p->next; 138 } 139 } 140 141 //销毁链表 142 void ListDispose( LIST l ) 143 { 144 struct listnode* p = l->head.next; 145 struct listnode* q; 146 147 while (p != &l->head) 148 { 149 q = p; 150 p = p->next; 151 152 free(q->data); 153 free(q); 154 } 155 free(l); 156 } 157 158 static int IdCmp(const void* key, const void* data) 159 { 160 const int *id = (const int*)key; 161 const DATA* stup = (const DATA*)data; 162 163 return (*id - stup->id); 164 } 165 166 static int NameCmp(const void* key, const void* data ) 167 { 168 const char* name = (const char*)key; 169 const DATA* stup = (const DATA*)data; 170 171 return strcmp(name,stup->name); 172 } 173 174 static void print(const void* data) 175 { 176 const DATA* stup = (const DATA*)data; 177 printf(" id::%d name::%s math::%d\n",stup->id, stup->name, stup->math); 178 179 } 180 181 int main() 182 { 183 int i; 184 int id = 5; 185 char name[NAMESIZE] = "stu3"; 186 DATA stu; 187 188 LIST handle = NULL; 189 handle = ListCreate(sizeof(DATA)); 190 if (handle == NULL ) 191 return 0; 192 193 for (i = 0; i < 6; i++ ) 194 { 195 stu.id = i + 1; 196 snprintf(stu.name,NAMESIZE,"stu%d",i+1); 197 198 stu.math = 100 - i; 199 ListInsert(handle,&stu,HEADINSERT);//首部插入 200 } 201 printf("打印整个链表\n"); 202 ListDisplay(handle, print); 203 204 // 205 printf("从链表查找元素id=5\n\n"); 206 struct listnode* stup = ListFind(handle,&id,IdCmp); 207 if (stup == NULL) 208 printf("not find!!!\n"); 209 else 210 print_s(stup); 211 printf("\n"); 212 213 //删除元素 214 printf("删除元素之前，删除的元素是id=5\n"); 215 ListDelete(handle, &id, IdCmp); 216 printf("删除元素之后\n"); 217 ListDisplay(handle,print); 218 219 printf("删除元素之前，删除的元素是name=stu3\n"); 220 ListDelete(handle,name,NameCmp); 221 printf("删除元素之后\n"); 222 ListDisplay(handle, print); 223 224 ListDispose(handle); 225 226 system("pause"); 227 return 0; 228 }
输出的结果为
4:有头节点、双向、不循环列表
1）头部插入
2)尾部插入
代码如下
1 // test02.cpp : Defines the entry point for the console application. 2 // 3 4 #include "stdafx.h" 5 #include<iostream> 6 7 using namespace std; 8 9 typedef struct headnode* LIST; 10 11 typedef void print_s(const void*); 12 typedef int cmp(const void*, const void*); 13 14 #define HEADINSERT 1 15 #define TAILINSERT 2 16 #define NAMESIZE 24 17 //有头节点、双向、不循环链表 18 typedef struct stuinfo 19 { 20 int id; 21 char name[NAMESIZE]; 22 int math; 23 } DATA; 24 25 struct listnode 26 { 27 void* data; 28 struct listnode* prev; 29 struct listnode* next; 30 }; 31 32 struct headnode 33 { 34 int size; //指向下面要插入数据的大小 35 struct listnode head; //指向下一个节点的指针 36 }; 37 38 //创建头节点 39 LIST ListCreate( int size ) 40 { 41 LIST handle = (struct headnode*)malloc(sizeof(*handle)); 42 if (handle == NULL) 43 { 44 return NULL; 45 } 46 handle->size = size; 47 handle->head.data =http://www.mamicode.com/ NULL; 48 handle->head.next = NULL; 49 handle->head.prev = NULL; 50 51 return handle; 52 } 53 54 //插入链表元素 其实这个地方主要分为尾部插入，还是头部插入 55 int ListInsert( LIST l, struct listnode* position, const void *data ) 56 { 57 struct listnode* cur = (struct listnode*)malloc(sizeof(*cur)); 58 if (cur == NULL) 59 { 60 return -1; 61 } 62 cur->data = http://www.mamicode.com/malloc(l->size); 63 if (cur->data =http://www.mamicode.com/= NULL) 64 { 65 free(cur); 66 return -1; 67 } 68 memcpy(cur->data, data, l->size); 69 cur->next = position->next; 70 cur->prev = position; 71 if(cur->next != NULL) 72 cur->next->prev = cur; 73 cur->prev->next = cur; 74 75 return 0; 76 } 77 78 int ListHeadInsert( LIST l, const void* data ) 79 { 80 return ListInsert(l,&l->head,data); 81 } 82 83 int ListTailInsert(LIST l, const void* data) 84 { 85 struct listnode* tail = &l->head; 86 for (; tail->next != NULL; tail = tail->next); 87 return ListInsert(l,tail,data); 88 } 89 90 struct listnode* ListFind(LIST l,const void* key,cmp* funp) 91 { 92 struct listnode* p = l->head.next; // 93 for (; p != NULL && funp(key, p->data); p = p->next); 94 95 return p; 96 } 97 98 //找到指定的元素 99 void* listfind(LIST l, const void* key, cmp* funp) 100 { 101 return ListFind(l,key,funp)->data; 102 } 103 104 //删除链表元素 105 int ListDelete(LIST l, const void* key, cmp* funp ) 106 { 107 //找到指定的元素删除 108 struct listnode* p = ListFind(l,key,funp); 109 if (p == NULL) 110 { 111 return 0; 112 } 113 const DATA* stup = (const DATA*)(p->data); 114 cout << stup->name << endl; 115 if (p->next == NULL) 116 { 117 p->prev->next = NULL; 118 } 119 else 120 { 121 p->prev->next = p->next; 122 p->next->prev = p->prev; 123 } 124 free(p->data); 125 free(p); 126 return 0; 127 } 128 129 //打印链表 130 void ListDisplay(LIST l, print_s* funp ) 131 { 132 struct listnode* p = l->head.next; 133 while ( p != NULL ) 134 { 135 funp(p->data); 136 p = p->next; 137 } 138 } 139 140 //销毁链表 141 void ListDispose( LIST l ) 142 { 143 struct listnode* p = l->head.next; 144 struct listnode* q; 145 146 while (p != NULL ) 147 { 148 q = p; 149 p = p->next; 150 151 free(q->data); 152 free(q); 153 } 154 free(l); 155 } 156 157 static int IdCmp(const void* key, const void* data) 158 { 159 const int *id = (const int*)key; 160 const DATA* stup = (const DATA*)data; 161 162 return (*id - stup->id); 163 } 164 165 static int NameCmp(const void* key, const void* data ) 166 { 167 const char* name = (const char*)key; 168 const DATA* stup = (const DATA*)data; 169 170 return strcmp(name,stup->name); 171 } 172 173 static void print(const void* data) 174 { 175 const DATA* stup = (const DATA*)data; 176 printf(" id::%d name::%s math::%d\n",stup->id, stup->name, stup->math); 177 178 } 179 180 int main() 181 { 182 int i; 183 int id = 5; 184 char name[NAMESIZE] = "stu3"; 185 DATA stu; 186 187 LIST handle = NULL; 188 handle = ListCreate(sizeof(DATA)); 189 if (handle == NULL ) 190 return 0; 191 192 for (i = 0; i < 6; i++ ) 193 { 194 stu.id = i + 1; 195 snprintf(stu.name,NAMESIZE,"stu%d",i+1); 196 197 stu.math = 100 - i; 198 ListHeadInsert(handle,&stu);//首部插入 199 } 200 printf("打印整个链表\n"); 201 ListDisplay(handle, print); 202 203 // 204 printf("从链表查找元素id=5\n\n"); 205 struct listnode* stup = ListFind(handle,&id,IdCmp); 206 if (stup == NULL) 207 printf("not find!!!\n"); 208 else 209 print(stup->data); 210 printf("\n"); 211 212 //删除元素 213 printf("删除元素之前，删除的元素是id=5\n"); 214 ListDelete(handle, &id, IdCmp); 215 216 217 printf("删除元素之后\n"); 218 ListDisplay(handle,print); 219 220 printf("删除元素之前，删除的元素是name=stu3\n"); 221 ListDelete(handle,name,NameCmp); 222 printf("删除元素之后\n"); 223 ListDisplay(handle, print); 224 225 ListDispose(handle); 226 227 system("pause"); 228 return 0; 229 }
输出结果为：
数据结构之链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。