链表——用来解决：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); }
