单链表
时间：2019-07-12 来源：沈阳中心，杨老师
链表用来解决1 顺序表数据大量移动的问题
2 解决顺序表元素数量固定的问题
链表分为单向链表，双向链表，单向循环链表，双向循环链表
单链表通常有两个域
数据域(保存数据)
指针域(保存下一个节点的位置)
单链表结构体定义如下
typedef struct node_t
{
int data; //数据域
struct node_t *next; //指针域，通过指针域可以找到下一个节点
}link_node_t;
typedef struct node_t
{
struct student data; //数据域
struct node_t *next; //指针域，通过指针域可以找到下一个节点
}link_node_t;
typedef struct node_t
{
char name[20]; //数据域
struct node_t *next; //指针域，通过指针域可以找到下一个节点
}link_node_t;
/////////////////////////
有这些名字，我们用单链表将这些名字连接起来
"yang", "li", "liu", "wang"
#include <stdio.h>
typedef struct node_t
{
char name[20]; //数据域
struct node_t *next; //指针域，通过指针域可以找到下一个节点
}link_node_t;
int main()
{
link_node_t *h;
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;
h = &A;
//输出每个节点
while(h != NULL)
{
printf("%s\n", h->name);
h = h->next;
}
}
/////////////
单向链表 两种类型
1 不带头结点的单向链表(链表中所有元素都是有效的)
上面名字例子：
2 带头结点的单向链表 (头结点: 是一个空节点，这个节点不存有效数据，只有next是有效的)
#include <stdio.h>
typedef struct node_t
{
char name[20]; //数据域
struct node_t *next; //指针域，通过指针域可以找到下一个节点
}link_node_t;
int main()
{
link_node_t h; //头结点
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;
h.next = &A;
link_node_t *p;
p = &h;
//输出每个节点
while(p->next != NULL)
{
p = p->next;
printf("%s\n", p->name);
}
}
用带头结点的单向链表存储n个学生成绩 ，成绩由键盘输入，输入<=0 时结束
////
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t
{
int score; //数据域
struct node_t *next; //指针域，通过指针域可以找到下一个节点
}link_node_t;
int main()
{
int s;
//创建一个头结点
link_node_t *p, *q, *h;//p 是新节点 q 是最后一个节点 h是第一个节点
p = malloc(sizeof(link_node_t));
p->next = NULL;
q = p;
h = p;
while(1)
{
scanf("%d", &s);
if(s <= 0)
break;
p = malloc(sizeof(link_node_t));
p->score = s;
p->next = NULL;
q->next = p;
q = p;
}
p = h;
while(p->next != NULL)
{
p = p->next;
printf("%d\n", p->score);
}
//再写个释放程序
while(h != NULL)
{
p = h->next;
free(h);
h = p;
}
}
链表有这些操作
#include <stdio.h>
#include <stdlib.h>
typedef struct node_t
{
int data; //数据域
struct node_t *next; //指针域
}link_node_t, *link_list_t;
//1 创建空链表(带头结点的单向链表)
link_node_t *CreateEmptyLinklist()
{
link_node_t *p = malloc(sizeof(link_node_t));
p->next = NULL;
return p;
}
//2 判断表是否为空 1 空 0 非空
int EmptyLinklist(link_node_t *p)
{
if(p->next == NULL)
return 1;
else
return 0;
}
//2.5 求链表长度
int LengthLinklist(link_node_t *p)
{
int i = 0;
while(p->next != NULL)
{
i++;
p = p->next;
}
return i;
}
//3 查找某个位置元素的值
int GetLinklist(link_node_t *p, int pos)
{
int i;
if(pos > LengthLinklist(p) + 1 || pos < 1)
return -1;
for(i = 0; i < pos; i++)
{
p = p->next;
}
return p->data;
}
//4 插入元素
int InsertLinklist(link_node_t *p, int pos, int x)
{
int i;
link_node_t *q;
if(pos > LengthLinklist(p) + 1 || pos < 1)
return -1;
for(i = 0; i < pos - 1; i++)
{
p = p->next;
}
q = malloc(sizeof(link_node_t));
q->data = x;
q->next = p->next;
p->next = q;
return 0;
}
//5 删除元素
int DeleteLinklist(link_node_t *p, int pos)
{
int i;
link_node_t *q;
if(pos > LengthLinklist(p) + 1 || pos < 1)
return -1;
for(i = 0; i < pos - 1; i++)
{
p = p->next;
}
q = p->next;
p->next = q->next;
free(q);
return 0;
}
//6 将链表倒置(逆转)
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;
}
//7 输出链表中所有元素
void PrintLinklist(link_node_t *p)
{
while(p->next != NULL)
{
p = p->next;
printf("%d ", p->data);
}
printf("\n");
}
int main()
{
link_node_t *h = CreateEmptyLinklist();
printf("%d\n", InsertLinklist(h, 1, 40));
InsertLinklist(h, 1, 20);
InsertLinklist(h, 2, 30);
PrintLinklist(h); //20 30 40
InsertLinklist(h, 1, 10);
PrintLinklist(h); //10 20 30 40
DeleteLinklist(h, 3);
PrintLinklist(h); //10 20 40
ReverseLinklist(h);
PrintLinklist(h); //40 20 10
}
