前言
在前面我们了解了线性表中的顺序表优点,顺序表可以将数放到一片连续的内存里且存储效率高,但是增加和删除效率很低,不可以增加长度,而今天的链表刚好解决了这些问题,链表在增加和删除中有着很高的效率,而且不像顺序表那样每删一个要顺序的移动
定义
链表是数据储存单元中非连续数据结构,数据的储存结构是通过指针链接依次实现的,链表由一系列结点组成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。
单链表的数据结构
typedef int datatyda; //类型名字的转换
typedef sturuct lian_ //类型名字的转换
{
datatyda data; //定义指针的储存数据
struct lian_ *next; //储存下一个地址的指针域
}w;
单链表头节点的创建
w link_creat ()
{
w *l = (w*)malloc(sizeof (w)); //堆区内存的申请
if (l == NULL ) return NULL; // 指针为空的话返回
l -> data =0 //节点初始化
l ->next = NULL;
return l; // 返回地址
}
节点的添加之尾插法
int list_add_taill (w *l,datatyda a)
{
w *n = malloc (sizeof (w); // 申请一个新的节点
p ->data =a; // 定义节点数据
p -> next =NULL;
w *p =l; //指针的定义
if (p -> next !=NULL)
{
p = p -> next; //指针的移动,直到最后一位
}
p ->next = n; // 指向 NULL的指针指向n
l ->data ++; // 个数记录
return 0;
}
节点添加之头插法
int list_add_head (w *l,datatype a)
{
w p* = l;
p ->next = l ->next; // l 指向的下一位变为p指向的下一位
l ->next = n; // l指向n
l ->data ++; // 个数记录
}
链表的查看
int list_show (w *l)
{
w *p =l ;
while (p != NULL)
{
p = p ->next;
printf ("data=%d",p ->data);
}
return 0;
}
链表的插入之按数值插入
int list_insert_var (w *l, datatype a,int b)
{
w *n = malloc(sizeof(w));
w *p = l ;
n ->data =b;
n ->next = NULL;
while (p->next !=NULL)
{
p= p ->next;
if (p ->data==a)
{
p ->next = n->next;
p ->next =n;
}
}
return 0;
}
链表的删除之按位置删除
int list_del_sit (w *l,datatype a)
{
w p1* = l ->next;
w p2 = l;
int b =0;
while (p1 !=NULL)
{
b ++
if (b ==a)
{
p1 ->next = p2 ->next;
free (p2);
p2 = p1 -next;
}
else
{
p1 =p1 ->next;
p2 = p2 -> next;
}
}
return 0;
}
链表的按值修改
int list_change (w *l,datatype a,datatype b)
{
w *p = l->next;
while (p != NULL)
{
if (p ->data == a)
{
p -> data =b;
}
p = p ->next;
}
return 0;
}
链表的释放
int list_free (w *l)
{
while (l ->next != NULL)
{
free (l )
l = l ->next
}
free (l);
return 0;
}
总结
这里只是一些链表的基础,其中没有包括的还有一些链表的按位置和按值查询的方法,在这里就不多写了,主要的思路的就是断开当前的链,连接到下一个节点,然后通过下一个指针不为空的条件循环下去,找到自己需要二点条件,同时写链表的时候主要要注意链表的指针的位置,注意表头和表尾的特殊情况就好。