链表的应用

链表应用——纯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; } void add(chain* head,int a,int b) { chain* p; int num = 0; p = head; while (p->next) { if (a==num) break; num++; p = p->next; } chain* q; q = (chain*)malloc(sizeof(chain)); q->data = b; q->next = p->next; p->next = q; } void del(chain* head, int a) { chain* p = head; int num = 0; while (p->next) { if (a==num) break; num++; p = p->next; } chain* r = p->next; if (r != NULL) { p->next = r->next; free(r); } } void change(chain* head, int a, int b) { chain* p = head->next; int num = 0; while (p) { if (a==num) break; num++; p = p->next; } p->data = b; } 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; while (~scanf("%d %d", &n, &m)) { head = set(n); int cmd, a, b; for (int i = 0; i < m; i++) { scanf("%d", &cmd); if (cmd == 1) { scanf("%d %d", &a, &b); add(head, a, b); } else if (cmd == 2) { scanf("%d", &a); del(head, a); } else if (cmd == 3) { scanf("%d %d", &a, &b); change(head, a, b); } else if (cmd == 4) { print(head); } } } return 0; }

移动小球

#include <stdio.h> #include <stdlib.h> typedef struct node { int data; struct node* next; } chain; chain* set1(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)); p->data = i + 1; p->next = tail->next; tail->next = p; tail = p; } return head; } void moved(chain* head, int a, int b) { chain *p,*pr; pr=head; p=head->next; while(p) { if(p->data==a) { pr->next=p->next; free(p); break; } p=p->next; pr=pr->next; } chain *q; q=head; while(q->next) { if(q->next->data==b) break; q=q->next; } chain *w; w=(chain *)malloc(sizeof(chain)); w->data=a; w->next=NULL; w->next=q->next; q->next=w; } void Find(chain* head, int x) { chain *p; p=head; while(p->next->data!=x) p=p->next; if(p==head) printf("cyk666\n"); else printf("%d\n",p->data); } int main() { int t; scanf("%d", &t); while (t--) { chain * head; int n, m; scanf("%d %d", &n, &m); head=(chain*)malloc(sizeof(chain)); head=set1(n); for (int i = 0; i < m; i++) { char c; scanf(" %c", &c); if (c == 'A') { int a, b; scanf("%d %d", &a, &b); moved(head, a, b); } if (c == 'Q') { int a; scanf("%d", &a); Find(head,a); } } } 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; } void del(chain* head, int a) { chain* p, * pr; pr = head; p = head->next; while (p) { if (p->data == a) { pr->next = p->next; free(p); break; } p = p->next; pr = pr->next; } } void add(chain* head, int a, int b) { chain* p,*np; p = head->next; while (p->data != 1) { p = p->next; } np = (chain*)malloc(sizeof(chain)); np->data = a; np->next = p->next; p->next = np; chain* q,*nq; q = head->next; while (q->data != 2) { q = q->next; } nq = (chain*)malloc(sizeof(chain)); nq->data = b; nq->next = q->next; q->next = nq; } void Findkey(chain* head) { int sum = 0; chain* p = head->next; while (p) { sum++; p = p->next; } int x=sum / 2 + 1; chain* q = head->next; int key = 1; while (key != x) { q = q->next; key++; } printf("%d\n", q->data); } void print(chain* head) { chain *p; p = head->next; while (p) { printf("%d%c", p->data, p->next == NULL ? '\n' : ' '); p = p->next; } } int main() { chain * head, * p, * tail; int n, m; scanf("%d", &n); head = (chain*)malloc(sizeof(chain)); head=set(n); scanf("%d", &m); for (int i = 1; i <=m; i++) { int f; scanf("%d", &f); if (f == 1) { int x, y; scanf("%d %d", &x, &y); del(head, x); del(head, y); Findkey(head); } if (f == 2) { int x, y; scanf("%d %d", &x, &y); add(head, x, y); Findkey(head); } } return 0; }

素数链表

#include <stdio.h> #include <stdlib.h> #include <math.h> typedef struct node { int data; struct node* next; }chain; int isprime(int x) { if (x == 0 || x == 1)return 0; else { int f = 0; for (int i = 2; i <= sqrt(x); i++) { if (x % i == 0) { f = 1; break; } } if (f == 0) return 1; else return 0; } } 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; } void print(chain *head) { chain* q; q = head->next; while (q) { printf("%d%c", q->data, q->next == NULL ? '\n' : ' '); q = q->next; } } int listprime(chain* r) { int flag = 0; if (r == NULL) flag = 1; else { while (r) { if (!isprime(r->data)) { flag = 1; break; } r = r->next; } } if (!flag) return 1; else return 0; } int main() { int t; scanf("%d", &t); for(int j=1;j<=t;j++) { chain* head, * q, * p; int n, m; scanf("%d %d", &n, &m); head = set(n); int len = n; printf("#%d\n", j); for (int i = 0; i < m; i++) { int x; scanf("%d", &x); if (x > len) printf("Invalid Operation\n"); else { p = head->next; q = head; int a = 1; while (a < x) { p = p->next; q = q->next; a++; } if (isprime(p->data)) { printf("Failed to delete %d\n", p->data); } else { printf("Deleted %d\n", p->data); q->next = p->next; free(p); len--; } } } if (listprime(head->next)) printf("All Completed. It's a Prime Linked List\n"); else printf("All Completed. It's not a Prime Linked List\n"); } return 0; }