目錄
鏈表基本操作
刪除重復元素?
查找倒數第N個節點
查找中間節點
約瑟夫環
循環鏈表
合并有序鏈表
逆置鏈表
逆置鏈表(雙向鏈表)
鏈表基本操作
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned char elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;
}void insert_node(int pos, unsigned char elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(void)
{struct node *p;for(p = head; p; p = p->next)printf("%c", p->elem);printf("\n");
}int search(unsigned char elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>struct node
{unsigned char elem;struct node *next;
};void create_list(unsigned char elem);
void insert_node(int pos, unsigned char elem);
void delete_node(int pos);
void print_linklist(void);
int search(unsigned char elem);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{create_list('A');create_list('B');create_list('C');create_list('D');print_linklist();delete_node(0);print_linklist();insert_node(0, 'F');insert_node(2, 'Z');print_linklist();if(search('C'))printf("the elem is found in the linklist\n");elseprintf("Can not find it\n");return 0;
}
刪除重復元素?
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(struct node *linklist_head)
{struct node *p;for(p = linklist_head; p; p = p->next)printf("%5d", p->elem);printf("\n");
}int search(unsigned int elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}void delete_repeat(struct node *head)
{int flag[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};struct node *p = head;struct node *q = NULL;flag[p->elem] = 1;while(p->next != NULL){if(flag[p->next->elem] == 0){flag[p->next->elem] = 1;p = p->next;}else{q = p->next;p->next = q->next;free(q);}}
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>extern struct node *head;
extern struct node *tail;struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);
void delete_repeat(struct node *head);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{create_list(1);create_list(2);create_list(8);create_list(2);create_list(3);create_list(9);create_list(4);create_list(6);create_list(4);create_list(8);create_list(7);create_list(5);create_list(2);create_list(9);create_list(6);print_linklist(head);delete_repeat(head);print_linklist(head);return 0;
}
查找倒數第N個節點
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(struct node *linklist_head)
{struct node *p;for(p = linklist_head; p; p = p->next)printf("%5d", p->elem);printf("\n");
}int search(unsigned int elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}int find_mid(struct node *linklist_head)
{struct node *p;struct node *q;p = q = linklist_head;while(p != NULL && p->next != NULL){p = p->next->next;q = q->next;}return q->elem;
}int find_last_nth(struct node *linklist_head, int n)
{int i;struct node *p;struct node *q;p = q = linklist_head;for(i = 0; i < n-1; i++)p = p->next;while(p->next != NULL){p = p->next;q = q->next;}return q->elem;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>extern struct node *head;
extern struct node *tail;struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);
int find_mid(struct node *linklist_head);
int find_last_nth(struct node *linklist_head, int n);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{int n;create_list(1);create_list(2);create_list(3);create_list(4);create_list(5);create_list(6);create_list(7);create_list(8);create_list(9);create_list(10);print_linklist(head);printf("Please enter the last one you want to show:");scanf("%d", &n);printf("the last n :%d\n", find_last_nth(head, n));return 0;
}
查找中間節點
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(struct node *linklist_head)
{struct node *p;for(p = linklist_head; p; p = p->next)printf("%5d", p->elem);printf("\n");
}int search(unsigned int elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}int find_mid(struct node *linklist_head)
{struct node *p;struct node *q;p = q = linklist_head;while(p != NULL && p->next != NULL){p = p->next->next;q = q->next;}return q->elem;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>extern struct node *head;
extern struct node *tail;struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);
int find_mid(struct node *linklist_head);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{create_list(1);create_list(2);create_list(3);create_list(4);create_list(5);create_list(6);create_list(7);create_list(8);create_list(9);create_list(10);print_linklist(head);printf("mid = %d\n", find_mid(head));return 0;
}
約瑟夫環
約瑟夫問題是個著名的問題：N個人圍成一圈，第一個人從1開始報數，報M的將被殺掉，下一個人接著從1開始報。如此反復，最后剩下一個，求最后的勝利者。
例如只有三個人，把他們叫做A、B、C，他們圍成一圈，從A開始報數，假設報2的人被殺掉。
●首先A開始報數，他報1。僥幸逃過一劫。
●然后輪到B報數，他報2。非常慘，他被殺了
●C接著從1開始報數
●接著輪到A報數，他報2。也被殺死了。
●最終勝利者是C
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;tail->next = head;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;tail->next = head;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == head)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);tail->next = head;}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == head)tail = pre;free(p);}
}void print_linklist(void)
{struct node *p;p = head;// for(p = head; p != head; p = p->next)
// printf("%d", p->elem);do{printf("%5d", p->elem);p = p->next;}while(p != head);printf("\n");
}int search(unsigned int elem)
{struct node *p;p = head;// for(p = head; p; p = p->next)
// if(p->elem == elem)
// return 1;do{if(p->elem == elem)return 1;p = p->next;}while(p != head);return 0;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>extern struct node *head;
extern struct node *tail;struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(void);
int search(unsigned int elem);#endif//main.c#include <stdio.h>
#include "linklist.h"
#include <stdlib.h>int main(void)
{int n, k, m;int i;struct node *p, *q;printf("Please enter the number of person:");scanf("%d", &n);for(i = 1; i <= n; i++)create_list(i);print_linklist();p = head;printf("Please enter the start num:");scanf("%d", &k);while(--k)p = p->next;
// printf("p->elem = %d\n", p->elem);printf("Please enter the m:");scanf("%d", &m);if(1 == m){for(i = 0; i < n; i++){printf("%3d", p->elem);p = p->next;}printf("\n");}else{while(n--){for(i = 1; i < m - 1; i++)p = p->next;q = p;p = p->next;printf("%3d", p->elem);q->next = p->next;free(p);p = p->next;}printf("\n");}return 0;
}
循環鏈表
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;tail->next = head;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;tail->next = head;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == head)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);tail->next = head;}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == head)tail = pre;free(p);}
}void print_linklist(void)
{struct node *p;p = head;// for(p = head; p != head; p = p->next)
// printf("%d", p->elem);do{printf("%5d", p->elem);p = p->next;}while(p != head);printf("\n");
}int search(unsigned int elem)
{struct node *p;p = head;// for(p = head; p; p = p->next)
// if(p->elem == elem)
// return 1;do{if(p->elem == elem)return 1;p = p->next;}while(p != head);return 0;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(void);
int search(unsigned int elem);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{create_list(1);create_list(2);create_list(3);create_list(4);create_list(5);create_list(6);create_list(7);print_linklist();insert_node(0, 11);print_linklist();delete_node(6);print_linklist();delete_node(0);print_linklist();delete_node(0);print_linklist();delete_node(4);print_linklist();insert_node(0, 8);print_linklist();insert_node(5, 9);print_linklist();insert_node(2, 13);print_linklist();return 0;
}
合并有序鏈表
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(struct node *linklist_head)
{struct node *p;for(p = linklist_head; p; p = p->next)printf("%5d", p->elem);printf("\n");
}int search(unsigned int elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>extern struct node *head;
extern struct node *tail;struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{struct node *head1 = NULL;struct node *head2 = NULL;struct node *p = NULL; //head1struct node *q = NULL; //head2create_list(1);create_list(9);create_list(13);create_list(27);head1 = head;print_linklist(head1);head = NULL;create_list(3);create_list(5);create_list(14);create_list(81);create_list(88);create_list(95);create_list(99);head2 = head;print_linklist(head2);head = NULL;p = head1;q = head2;while(p && q){if(p->elem <= q->elem){if(head == NULL)head = p;elsetail->next = p;tail = p;p = p->next;}else{if(head == NULL)head = q;elsetail->next = q;tail = q;q = q->next;}}tail->next = p?p:q;print_linklist(head);return 0;
}
逆置鏈表
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->next = NULL;if(head == NULL)head = p;elsetail->next = p;tail = p;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->next = pre->next;pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(struct node *linklist_head)
{struct node *p;for(p = linklist_head; p; p = p->next)printf("%5d", p->elem);printf("\n");
}int search(unsigned int elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}int find_mid(struct node *linklist_head)
{struct node *p;struct node *q;p = q = linklist_head;while(p != NULL && p->next != NULL){p = p->next->next;q = q->next;}return q->elem;
}int find_last_nth(struct node *linklist_head, int n)
{int i;struct node *p;struct node *q;p = q = linklist_head;for(i = 0; i < n-1; i++)p = p->next;while(p->next != NULL){p = p->next;q = q->next;}return q->elem;
}void reverse_linklist(struct node *linklist_head)
{struct node *p, *n;p = linklist_head->next;linklist_head->next = NULL;while(p->next != NULL){n = p->next;p->next = linklist_head;linklist_head = p;p = n;}p->next = linklist_head;linklist_head = p;head = linklist_head;
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>extern struct node *head;
extern struct node *tail;struct node
{unsigned int elem;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(struct node *linklist_head);
int search(unsigned int elem);
int find_mid(struct node *linklist_head);
int find_last_nth(struct node *linklist_head, int n);
void reverse_linklist(struct node *linklist_head);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{int n;create_list(1);create_list(2);create_list(3);create_list(4);create_list(5);create_list(6);create_list(7);create_list(8);create_list(9);create_list(10);print_linklist(head);reverse_linklist(head);print_linklist(head);return 0;
}
逆置鏈表(雙向鏈表)
//linklist.c#include "linklist.h"
#include <stdlib.h>struct node *head = NULL;
struct node *tail = NULL;void create_list(unsigned int elem)
{struct node *p = (struct node *)malloc(sizeof(struct node));p->elem = elem;p->pre = NULL;p->next = NULL;if(head == NULL)head = p;else{tail->next = p;p->pre = tail;}tail = p;
}void insert_node(int pos, unsigned int elem)
{struct node *pre;pre = head;int i = 0;struct node *p = (struct node *)malloc(sizeof(struct node));if(pos == 0){p->elem = elem;p->next = head;head->pre = p;p->pre = NULL;head = p;}else{while(i < pos - 1){pre = pre->next;i++;}p->elem = elem;p->pre = pre;p->next = pre->next;if(p->next != NULL)pre->next->pre = p; pre->next = p;if(p->next == NULL)tail = p;}
}void delete_node(int pos)
{struct node *pre, *p;pre = head;int i = 0;if(pos == 0){head = head->next;head->pre = NULL;free(pre);}else{while(i < pos - 1){pre = pre->next;i++;}p = pre->next;pre->next = p->next;if(p->next != NULL)p->next->pre = pre;else//if(p->next == NULL)tail = pre;free(p);}
}void print_linklist(void)
{struct node *p;for(p = head; p; p = p->next)printf("%5d", p->elem);printf("\n");
}int search(unsigned int elem)
{struct node *p;for(p = head; p; p = p->next)if(p->elem == elem)return 1;return 0;
}void reverse_print_linklist(void)
{struct node *p;for(p = tail; p; p = p->pre)printf("%5d", p->elem);printf("\n");
}
//linklist.h#ifndef LINKLIST_H__
#define LINKLIST_H__#include <stdio.h>struct node
{unsigned int elem;struct node *pre;struct node *next;
};void create_list(unsigned int elem);
void insert_node(int pos, unsigned int elem);
void delete_node(int pos);
void print_linklist(void);
int search(unsigned int elem);
void reverse_print_linklist(void);#endif//main.c#include <stdio.h>
#include "linklist.h"int main(void)
{create_list(1);create_list(2);create_list(3);create_list(4);create_list(5);create_list(6);create_list(7);print_linklist();reverse_print_linklist();
/*insert_node(0, 11);print_linklist();delete_node(6);print_linklist();delete_node(0);print_linklist();delete_node(0);print_linklist();delete_node(4);print_linklist();insert_node(0, 8);print_linklist();insert_node(5, 9);print_linklist();insert_node(2, 13);print_linklist();
*/ return 0;
}
)
