链表：
只有一个前驱和一个后继，每一个节点通过指针链接
每一个链表都有一个头结点。
头结点：
链表的第一个结点，数据域无效。（大家都默认，第一个结点的数据域我们不去使用它，头节点只是代表整个链表的开端）
结构体：
struct link{
datatype data; //数据域
struct link *next; //指针域
};
优点： 插入和删除很方便
缺点： 查找 麻烦
缺陷：----》 一旦往后走 就 无法回头
如何弥补单向链表的缺陷？？---- 使用双向链表
#include
#include
typedef int datatype;
typedef struct link{
datatype data; //数据域
struct link *next; //指针域
} link_t;
static void node_insert_behind(link_t *p,link_t *node)
{
node->next = p->next;
p->next = node;
}
static link_t * create_node(datatype d)
{
link_t *p = (link_t *)malloc(sizeof(link_t));
if(p==NULL){
perror("create_node malloc error");
return NULL;
}
p->data = d;
p->next = NULL;
return p;
}
static void del_behind_node(link_t *p)
{
link_t *node = p->next;
p->next = node->next; //node->next里面保存的就是被删除的节点的下一个节点的地址
node->next = NULL;
free(node); //释放被删除的节点
}
link_t *link_init(void)
{
//在堆中开辟空间
link_t *p = (link_t *)malloc(sizeof(link_t));
if(p==NULL){
perror("link_init malloc error");
return NULL;
}
//赋值
p->next = NULL;
//返回
return p;
}
void link_add_head(link_t *p,datatype d)
{
//创建新的节点
link_t *node = create_node(d);
if(node==NULL)
return;
// 将新的节点插入到头节点的后面
node_insert_behind(p,node);
}
void link_add_tail(link_t *p,datatype d)
{
//创建新的节点
link_t *node = create_node(d);
if(node==NULL)
return;
// 找到链表末尾节点的地址
while(p->next!=NULL)
p = p->next;
// 将新的节点插入到p的后面，即：插到末尾节点的后面
node_insert_behind(p,node);
}
void link_del(link_t *p,datatype d)
{
//寻找节点
while(p->next!=NULL){
if(p->next->data == d ){
del_behind_node(p);
continue;
}
p = p->next;
}
}
void display(link_t *p)
{
printf("单向链表遍历结果：");
while(p->next!=NULL){
p=p->next;
printf("%d ",p->data);
}
printf("n");
}
#include
#include
typedef int datatype;
typedef struct link{
datatype data; //数据域
struct link *next; //指针域
} link_t;
static void node_insert_behind(link_t *p,link_t *node)
{
node->next = p->next;
p->next = node;
}
static link_t * create_node(datatype d)
{
link_t *p = (link_t *)malloc(sizeof(link_t));
if(p==NULL){
perror("create_node malloc error");
return NULL;
}
p->data = d;
p->next = p;
return p;
}
static void del_behind_node(link_t *p)
{
link_t *node = p->next;
p->next = node->next;
node->next = node;
free(node);
}
static void replace(link_t *xx,link_t *new)
{
//得到旧节点
link_t *old = xx->next;
//新节点替换旧节点
new->next = old->next;
xx->next = new;
//释放旧节点
old->next = old;
free(old);
}
link_t *link_init(void)
{
//在堆中开辟空间
link_t *p = (link_t *)malloc(sizeof(link_t));
if(p==NULL){
perror("link_init malloc error");
return NULL;
}
//赋值
p->next = p; //自己指向自己
//返回
return p;
}
void link_add_head(link_t *p,datatype d)
{
//创建新的节点
link_t *node = create_node(d);
if(node==NULL)
return;
// 将新的节点插入到 头节点的后面
node_insert_behind(p,node);
}
void link_add_tail(link_t *p,datatype d)
{
//保存头
link_t *head = p;
//创建新的节点
link_t *node = create_node(d);
if(node==NULL)
return;
// 跳到尾巴上
while(p->next!=head) //注意：此处单向循环链表的判断条件与单向链表的不一样
p = p->next;
// 将新的节点插入到 p的后面
node_insert_behind(p,node);
}
void link_del(link_t *p,datatype d)
{
//保存头
link_t *head = p;
//寻找节点
while(p->next!=head){ //注意：此处单向循环链表的判断条件与单向链表的不一样
if(p->next->data == d ){
del_behind_node(p);
continue;
}
p = p->next;
}
}
void link_update(link_t *p,datatype old_data,datatype new_data)
{
//保存头
link_t *head = p;
link_t *new_node = NULL;
//通过 old_data 找到 其 节点
while(p->next!=head){
if(p->next->data == old_data){
// 找到后 ，通过 new_data 创建新的节点
new_node = create_node(new_data);
if(new_node == NULL)
return;
// 新的节点替换旧的节点
replace(p,new_node);
}
p= p->next;
}
}
void display(link_t *p)
{
//保存头
link_t *head = p;
printf("单向循环链表遍历结果：");
while(p->next!=head){
p=p->next;
printf("%d ",p->data);
}
printf("n");
}
