链表——用来解决:1 顺序表数据大量移动的问题。2 解决顺序表元素数量固定的问题。
链表分为 1.单向链表 2.双向链表 3.单向循环链表 4.双向循环链表
单向链表有两个域,数据域和指针域
typedef struct node_t { int data; //数据域 struct node_t *next; //指针域,通过指针域可以找到下一个节点 }link_node_t;
例:
有这些姓氏,我用链表将这些名字连接起来 "yang", "li", "liu", "wang" #includetypedef struct node_t { char name[20]; struct node_t *next; }link_node_t; int main() { link_node_t A = {"yang", NULL}; link_node_t B = {"li", NULL}; link_node_t C = {"liu", NULL}; link_node_t D = {"wang", NULL}; A.next = &B; B.next = &C; C.next = &D; link_node_t *p = &A; //输出????? while(p != NULL) { printf("%sn", p->name); p = p->next; } }
单向链表有2种类型:
1) 带头结点的单向链表
2) 不带头结点的单向链表
1.带头结点 (头结点: 是一个空节点,这个节点不存有效数据,只有next是有效的) 上面名字例子改为用带头结点的单向链表实现: #includetypedef struct node_t { char name[20]; struct node_t *next; }link_node_t; int main() { link_node_t A = {"yang", NULL}; link_node_t B = {"li", NULL}; link_node_t C = {"liu", NULL}; link_node_t D = {"wang", NULL}; link_node_t E = {" ", &A}; A.next = &B; B.next = &C; C.next = &D; link_node_t *p = &E; //输出????? while(p->next != NULL) { p = p->next; printf("%sn", p->name); } }
例:
用带头结点的单向链表存储n个学生成绩 ,成绩由键盘输入,输入<=0 时结束 // #include#include typedef struct node_t { int data; struct node_t *next; }link_node_t; int main() { link_node_t *h = malloc(sizeof(link_node_t));//h 是头节点 h->next = NULL; link_node_t *q = h; //q 永远指向最后一个节点 while(1) { int n; scanf("%d", &n); if(n <= 0) break; link_node_t *p = malloc(sizeof(link_node_t));//p 是新节点 p->data = n; p->next = NULL; q->next = p; q = p; } while(h->next != NULL) { h = h->next; printf("%dn", h->data); } }
2.不带头结点 while(p != NULL) { printf("%dn", p->data); p = p->next; } #include#include typedef struct { char name[20]; int age; int score; }student; typedef struct node_t { student s; //数据域 struct node_t *next; //指针域 }link_node_t; int main() { link_node_t *h = malloc(sizeof(link_node_t)); //先定义一个头结点 link_node_t *p, *q; //p 指向新节点, q指向最后一个节点 h->next = NULL; q = h; while(1) { student s; scanf("%s%d%d", s.name, &s.age, &s.score); if(s.age <= 0) { break; } p = malloc(sizeof(link_node_t)); //申请一个新节点 p->s = s; p->next = NULL; q->next = p; q = p; //每次让q变成最后一个节点,连接新节点 } while(h->next != NULL) { h = h->next; printf("%s, %d, %dn", h->s.name, h->s.age, h->s.score); } }
链表有这些操作
1 创建空链表(带头结点的单向链表)
#include#include typedef struct node_t { int data; struct node_t *next; }link_node_t; link_node_t *CreateEmptyLinklist() { //malloc 一个头节点, 头节点的next = NULL , 然后返回 link_node_t *p = malloc(sizeof(link_node_t)); p->next = NULL; return p; }
//1 求链表长度
int LengthLinklist(link_node_t *p) { int len = 0; while(p->next != NULL) { len++; p = p->next; } return len; }
//2 取出某个位置元素的值
int getValue(link_node_t *p, int pos) { int i; for(i = 0; i < pos; i++) p = p->next; return p->data; }
//3 插入元素 (成功: 返回0 失败返回 -1)
int InsertLinklist(link_node_t *p, int pos, int x) { int i; //容错处理, 如果pos 错,不能插入 if(pos > LengthLinklist(p) + 1) return -1; for(i = 0; i < pos - 1; i++) p = p->next; link_node_t *q = malloc(sizeof(link_node_t)); q->data = x; q->next = p->next; p->next = q; return 0; }
//4 删除元素 (成功: 返回0 失败返回 -1)
int DeleteLinklist(link_node_t *p, int pos) { int i; if(pos > LengthLinklist(p)) return -1; for(i = 0; i < pos - 1; i++) p = p->next; link_node_t *q = p->next; p->next = q->next; free(q); return 0; } void print_all(link_node_t *p) { while(p->next != NULL) { p = p->next ; printf("%d,", p->data); } printf("n"); }
2 反向输出 (递归实现)
void reverse_print_all(link_node_t *p) { if(p->next == NULL) return; reverse_print_all(p->next); printf("%d,", p->next->data); }
3 链表逆转 (原来的最后一个节点,变成第一个节点)
void ReverseLinklist(link_node_t *h) { link_node_t *p, *q; p = h->next; h->next = NULL; while (p != NULL) { q = p; p = p->next; q->next = h->next; h->next = q; } return; }
4 链表的释放
void free_list(link_node_t *p) { while(p != NULL) { link_node_t *q = p->next; //保存下一个节点 free(p); printf("1n"); p = q; } }
主函数部分:
int main() { link_node_t *h = CreateEmptyLinklist(); InsertLinklist(h, 1, 40); //40 InsertLinklist(h, 1, 30); //30, 40 InsertLinklist(h, 1, 10); //10, 30, 40 InsertLinklist(h, 2, 20); //10, 20, 30, 40 print_all(h); //打印所有元素 ReverseLinklist(h); print_all(h); //打印所有元素 //40, 30, 20, 10 DeleteLinklist(h, 2); print_all(h); //打印所有元素 //10, 30, 40 reverse_print_all(h); //40, 30, 10 free_list(h); //释放所有元素(每释放一个,打印1) }
单向循环链表: 一般是不带头结点的,所有节点都有效 (尾节点的next 是首节点)
约瑟夫问题(经典,请记住)
1) 形成有8个节点的单向循环链表,里面的值(1,2,3,4,5,6,7,8)
2) 先找到k(3)
3) 循环报数m(4)(删除节点), 直到只剩一个节点
4) 将最后一个节点输出
#include#include typedef struct node_t { int data; struct node_t *next; }link_node_t; int main() { int i, k = 3, m = 4; link_node_t *h = malloc(sizeof(link_node_t)); //先创建 新节点 link_node_t *p, *q = h; h->data = 1; h->next = NULL; for(i = 2; i <= 8; i++) { p = malloc(sizeof(link_node_t)); p->data = i; q->next = p; q = p; } q->next = h; //构成单向循环链表 for(i = 0; i < k - 1; i++) h = h->next; //找到第k个节点 while(h->next != h) //循环报数 说明还有多于1个节点 { //报数, 报道m 出局,应该找到 m 前面的节点 for(i = 0; i < m - 1 - 1; i++) { h = h->next; } q = h->next; //q 要删除的节点 h->next = q->next; //从链表中删除 printf("%dn", q->data); free(q); //释放掉 h = h->next; //从下一个开始报数 } printf("%dn", h->data); }