链表
文章目录
- 链表
- 创建链表
- 单链表
- 实现
- 错例
- 循环链表
- 单独创建
- 逐节点创建
- 约瑟夫环问题
- 删除节点
- 实现方式一:
- 实现方式二:
- 删除节点并建立新链表
- 逆置链表
- 实现:
- 链表排序
struct List { int data; struct List* next; }
创建链表
单链表
实现
struct List* listCreate() { int data; struct List* head = NULL; struct List* pre = NULL; struct List* current = NULL; while(scanf("%d",&data) && data != -1) { current = (struct List*)malloc(sizeof(struct List)); if(head == NULL) head = current; else pre->next = current; current->next = NULL; current->data = data; pre = current; } return head; }
错例
struct List* listCreate() { int data;; struct List* current = NULL; struct List* head = current; while (scanf("%d", &data) && data != -1) { current = (struct List*)malloc(sizeof(struct List)); if (head == NULL) head = current; current->data = data; current = current->next; } return head; }
在使用malloc函数开辟的空间中,不要进行指针的移动,因为一旦移动之后可能出现申请的空间和释放空间大小的不匹配
循环链表
单独创建
struct List* circle_listCreate() { int data; struct List* head = NULL; struct List* pre = NULL; struct List* current = NULL; while(scanf("%d",&data) && data != -1) { current = (struct List*)malloc(sizeof(struct List)); if(head == NULL) head = current; else pre->next = current; current->next = head; current->data = data; pre = current; } return head; }
逐节点创建
void Append(struct List** L,int data) { struct List* head = *L; struct List* newNode = NULL; if((*L) == NULL) { (*L) = (struct List*)malloc(sizeof(struct List)); (*L)->data = data; head = (*L); (*L)->next = head; } else { while ((*L)->next != head){ (*L) = (*L)->next; } newNode = (struct List*)malloc(sizeof(struct List)); newNode->data = data; (*L)->next = newNode; newNode->next = head; *L = head; } }
约瑟夫环问题
void Append(struct List** L,int data) { struct List* head = *L; struct List* newNode = NULL; if((*L) == NULL) { (*L) = (struct List*)malloc(sizeof(struct List)); (*L)->data = data; head = (*L); (*L)->next = head; } else { while ((*L)->next != head){ (*L) = (*L)->next; } newNode = (struct List*)malloc(sizeof(struct List)); newNode->data = data; (*L)->next = newNode; newNode->next = head; *L = head; } } void Display(struct List* L,int num) { struct List* head = L; struct List* pre = NULL; struct List* kill = NULL; int nodeNum = 0; while (L->next != head) { nodeNum++; L = L->next; } pre = L; L = L->next; nodeNum++; while (nodeNUm) { if (nodeNum == 1) { printf("%d",L->data); free(L); return; } for (int i=1; i < m; i++) { pre = L; L = L->next; } printf("%d ", L->data); kill = L; L = L->next; free(kill); nodeNum--; } }
删除节点
实现方式一:
struct list* listDelete(struct list* L,int data) { struct list* pre = L; struct list* head = L; struct list* kill; while(head != NULL && head->data == m) { kill = head; head = head->next; free(kill); } if(head == NULL) return head; pre = head; kill = head->next; while(kill!=NULL) { if(kill->data == m) { pre->next = kill->next; free(kill); kill = pre->next; } else { pre = kill; kill = kill->next; } } return head; }
实现方式二:
struct list* listDelete(struct list** L,int data) { struct list* head = (*L), * pre = (*L); struct list* newL = *L; struct list* kill = NULL; while (*L !- NULL) { if((*L)->data == data) { if((*L) == newL) newL == newL->next; else pre->next = (*L)->next; kill = (*L); (*L) = (*L)->next; free(kill); } else { pre = (*L); (*L) = (*L)->next; } } *L = newL; return head; }
删除节点并建立新链表
struct list* list_Delete_Create(struct list** L) //数据为奇数存为新链表 { struct list* newhead = NULL, * newcurrent = NULL, * newpre = NULL; struct list* newL = *L; struct list* kill = NULL; struct list* pre = *L; while (*L) { if((*L)->data%2 == 1) { newcurrent = (struct list*)malloc(sizeof(struct list)); if(newhead == NULL) newhead = newcurrent; else newpre->next = newcurrent; newcurrent->data = (*L)->data; newcurrent->next = NULL; newpre = newcurrent; if((*L) == newL) newL = newL->next; else pre-next = (*L)->next; kill = (*L); (*L)=(*L)->next; free(kill); } else { pre = (*L); (*L) = (*L)->next; } } *L = newL; return newhead; }
逆置链表
实现:
struct list* reverse(struct list* L) { struct list* newhead = NULL, * current; while (L != NULL) { current = (struct list*)malloc(sizeof(struct list)); current->data = L->data; L = L->next; current->next = newhead; newhead = current; } free(L); return newhead; }
链表排序
猜你喜欢
网友评论
- 搜索
- 最新文章
- 热门文章