链表的基本操作

链表操作——纯C代码

链表顺序建立链表逆序建立链表链表的逆置有序链表的归并单链表的拆分有序链表的建立单链表中重复元素的删除

链表

顺序建立链表

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; chain* set(int n)//建表函数 { chain* head, * p, * tail; head = (chain*)malloc(sizeof(chain)); head->next = NULL; tail = head; for (int i = 0; i < n; i++) { p = (chain*)malloc(sizeof(chain)); scanf("%d",&p->data); p->next = tail->next; tail->next = p; tail = p; } return head; } int main() { chain* head,*q; int n; scanf("%d", &n); head = set(n); q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } return 0; }

逆序建立链表

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; int main() { chain* head, * p; head = (chain*)malloc(sizeof(chain)); head->next = NULL; int n; scanf("%d", &n); for (int i = 0; i < n; i++) { p = (chain*)malloc(sizeof(chain)); scanf("%d", &p->data); p->next = head->next; head->next = p; } chain* q; q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } return 0; }

链表的逆置

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; chain* reverse(chain* head) { chain* p,*r; p = head->next; r = p; head->next = NULL; while (p) { p = p->next; r->next = head->next; head->next = r; r = p; } return head; } int main() { chain* head, * p,*tail; head = (chain*)malloc(sizeof(chain)); head->next = NULL; tail = head; int n; while(~scanf("%d",&n)&&n!=-1) { p = (chain*)malloc(sizeof(chain)); p->data = n; p->next = tail->next; tail->next = p; tail = p; } chain *head1 = reverse(head); chain* q; q = head1->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } return 0; }

有序链表的归并

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; chain* set(int n)//建表 { chain* head, * p,*tail; head = (chain*)malloc(sizeof(chain)); head->next = NULL; tail = head; for (int i = 0; i < n; i++) { p = (chain*)malloc(sizeof(chain)); scanf("%d", &p->data); p->next = tail->next; tail->next = p; tail = p; } return head; } chain* guibing(chain* head1,chain *head2)//归并排序 { chain* p,*r,*head,*p1,*p2,*tail; p1 = head1->next; p2 = head2->next; head = (chain*)malloc(sizeof(chain)); head->next = NULL; tail = head; while (p1||p2) { p = (chain*)malloc(sizeof(chain)); if (p1->data > p2->data) { p->data = p2->data; p2 = p2->next; } else if (p1->data <= p2->data) { p->data = p1->data; p1 = p1->next; } p->next = tail->next; tail->next = p; tail = p; if (p1 == NULL) { tail->next = p2; break; } if (p2 == NULL) { tail->next = p1; break; } } return head; } int main() { chain* head1,*head2, * p,*tail; int n,m; scanf("%d %d", &n, &m); head1 = set(n); head2 = set(m); chain *head = guibing(head1, head2); chain* q; q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } return 0; }

单链表的拆分

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; chain* set(int n) { chain* head, * p,*tail; head = (chain*)malloc(sizeof(chain)); head->next = NULL; tail = head; for (int i = 0; i < n; i++) { p = (chain*)malloc(sizeof(chain)); scanf("%d", &p->data); p->next = tail->next; tail->next = p; tail = p; } return head; } chain* chaifen(chain* head,int n) { chain* p,*head1,*head2,*p1,*p2,*tail; p = head->next; head1 = (chain*)malloc(sizeof(chain)); head1->next = NULL; tail = head1; while (p) { p1 = (chain*)malloc(sizeof(chain)); if (p->data % 2 == n) { p1->data = p->data; p1->next = tail->next; tail->next = p1; tail = p1; } p = p->next; } return head1; } int len(chain* head) { chain* p = head; int l = 0; while (p->next) { l++; p = p->next; } return l; } void print(chain* head) { chain* q; q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } } int main() { chain* head1,*head2,*head,*p,*tail; int n,m; scanf("%d", &n); head = set(n); head1 = chaifen(head, 0); head2 = chaifen(head, 1); int len1 = len(head1); int len2 = len(head2); printf("%d %d\n", len1, len2); print(head1); print(head2); return 0; }

有序链表的建立

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; chain* set(int n) { chain* head, * p,*tail; head = (chain*)malloc(sizeof(chain)); head->next = NULL; tail = head; for (int i = 0; i < n; i++) { p = (chain*)malloc(sizeof(chain)); scanf("%d", &p->data); p->next = tail->next; tail->next = p; tail = p; } return head; } chain* sorted(chain* head) { int t; chain* p,*q; for (p = head->next; p != NULL; p = p->next) { for (q = p->next; q != NULL; q = q->next) { if(p->data>q->data) { t = p->data; p->data = q->data; q->data = t; } } } return head; } void print(chain* head) { chain* q; q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } } int main() { chain* head1,*head2,*head,*p,*tail; int n,m; scanf("%d", &n); head = set(n); sorted(head); print(head); return 0; }

单链表中重复元素的删除

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; }chain; chain* set(int n) { chain* head, * p; head = (chain*)malloc(sizeof(chain)); head->next = NULL; for (int i = 0; i < n; i++) { p = (chain*)malloc(sizeof(chain)); scanf("%d", &p->data); p->next = head->next; head->next = p; } return head; } int len(chain* head) { chain* p = head; int l = 0; while (p->next) { l++; p = p->next; } return l; } chain* del(chain* head) { chain* p, * r,*q; p = head->next; while (p) { r = p->next; q = p; while (r) { if (p->data == r->data) { q->next = r->next; free(r); r = q->next; } else { q = q->next; r = r->next; } } p = p->next; } return head; } void print(chain* head) { chain* q; q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } } int main() { chain* head1,*head2,*head,*p,*tail; int n,m; scanf("%d", &n); head = set(n); printf("%d\n", n); print(head); head1=del(head); int l = len(head1); printf("%d\n", l); print(head1); return 0; }