数据结构----链表
1.数据结构基本概念
数据结构：是一组用来保存一种或者多种特定关系的数据的集合，其核心在于如何组织和存储数据。
1.1数据结构的分类
集合：其中的元素之间关系平等，没有明显的层级或关系链。
图形结构：元素之间形成多对多的关系，形成网状结构，非常适合表示复杂的关系网络。
树型结构：元素之间具有一对多的关系，最典型的例子是二叉树，它有效地表达了层级和分支的关系。
线性结构：元素之间仅存在一对一的关系，线性表（如数组、链表）、队列、栈等都是线性
结构的实现。这些结构的特点是数据项之间有序排列。
顺序存储：使用一段连续的内存空间来保存元素。其优点是空间连续，访问方便；但缺点是
插入和删除操作需要移动大量元素，且需要预分配内存空间，易造成存储空间碎片。
链式存储：与顺序存储不同，链式存储采用一组非连续的内存空间来保存元素。每个元素
（或称为节点）除了存储数据外，还包含指向下一个元素的指针（单向链表）或指向前后元素的指
针（双向链表）。优点是插入和删除数据方便，不需要预分配内存；缺点是访问元素效率较低。
其他存储方式
索引存储：通过关键字构建索引表，快速找到数据的存储位置，提高了数据检索的效率。
散列存储（哈希存储）：将数据元素的存储位置与其关键码之间建立确定的对应关系，实现了快速查找的存储方式。
1.2 示例
link.h
#ifndef __LINK_h__
#define __LINK_h__
typedef int DataType;//链表存储数据类型；
typedef struct node//链表结点类型；
{
DataType date; // 数据域；
struct node *pnext; // 指针域；
}Link_node_t;
typedef struct Link //链表对象类型；
{
Link_node_t *phead; //链表头结点地址；
int clen; //链表当前结点数；
}Link_t;
extern Link_t *create_link();//链表创建；
extern int push_link_head(Link_t *plink,DataType data);
extern void printf_link(Link_t *plink);
extern int push_link_tail(Link_t *plink,DataType data);
extern int pop_link_head(Link_t *plink);
extern int pop_link_tail(Link_t *plink);
extern Link_node_t *find_link_data(Link_t *plink, DataType data);
extern int change_link_data(Link_t*plink,DataType data,DataType new_data);
extern int pop_link_all(Link_t * plink);
extern Link_node_t *find_link_end_k_node(Link_t *plink,int k);
extern Link_node_t *find_mid_link_node(Link_t *plink);
extern int delete_link(Link_t *plink , DataType n);
#endiflink.c
#include <stdio.h>
#include <stdlib.h>
#include "link.h"
Link_t *create_link()
{
Link_t *plink = (Link_t *)malloc(sizeof(Link_t));
if(NULL == plink)
{
perror("fail malloc");
return NULL;
}
plink->phead = NULL;
plink->clen = 0;
return plink;
}
int push_link_head(Link_t *plink,DataType data)
{
Link_node_t *pnode = (Link_node_t *)malloc(sizeof(Link_node_t));
if(NULL == pnode )
{
perror("fail malloc");
}
pnode->date = data;
pnode->pnext = NULL;
pnode->pnext= plink->phead;
plink->phead= pnode;
plink->clen +=1;
}
void printf_link(Link_t *plink)
{
Link_node_t *p = plink->phead;
while(p!= NULL)
{
printf("%d ",p->date);
p=p->pnext;
}
printf("clen = %d\n",plink->clen);
}
int push_link_tail(Link_t *plink,DataType data)
{
Link_node_t *pnode = (Link_node_t *)malloc(sizeof(Link_node_t));
if(NULL == pnode )
{
perror("fail malloc");
}
pnode->date = data;
pnode->pnext = NULL;
if(plink->phead == NULL)
{
push_link_head(plink,data);
}
else
{
Link_node_t *p = plink->phead;
while(p->pnext != NULL)
{
p=p->pnext;
}
p->pnext=pnode;
plink->clen+=1;
}
return 0;
}
int pop_link_head(Link_t *plink)
{
Link_node_t *p = plink->phead;
if(NULL == plink->phead)
{
return 0;
}
plink->phead= p->pnext;
free(p);
plink->clen -=1;
return 0;
}
int pop_link_tail(Link_t *plink)
{
Link_node_t *p = plink->phead;
if(NULL == plink->phead)
{
return 0;
}
else if(plink->clen==1)
{
pop_link_head(plink);
}
else
{
while(p->pnext->pnext !=NULL)
{
p=p->pnext;
}
free(p->pnext);
p->pnext = NULL;
plink->clen -=1;
}
return 0;
}
Link_node_t *find_link_data(Link_t *plink, DataType data)
{
Link_node_t *p = plink->phead;
if(plink->clen ==0)
{
return NULL;
}
else
{
while(p!= NULL)
{
if(p->date == data)
{
printf("find\n");
return p;
}
p=p->pnext;
}
printf("no find\n");
return NULL;
}
}
int change_link_data(Link_t *plink,DataType data,DataType new_data)
{
Link_node_t *p =find_link_data(plink,data);
if(p==NULL)
{
return -1;
}
p->date =new_data;
return 0;
}
int pop_link_all(Link_t * plink)
{
for(int i =0;i<plink->clen;++i)
{
pop_link_head(plink);
}
free(plink);
return 0;
}
Link_node_t *find_mid_link_node(Link_t *plink)
{
Link_node_t *p = plink->phead;
if(plink->clen ==0)
{
return NULL;
}
for(int i = 0 ; i < plink->clen / 2; ++i)
{
p = p->pnext;
}
printf("mid=%d\n",p->date);
return p;
}
Link_node_t *find_link_end_k_node(Link_t *plink,int k)
{
Link_node_t *p = plink->phead;
if(plink->clen ==0)
{
return NULL;
}
int a = plink->clen-k;
if(a<0)
{
return NULL;
}
else
{
for(int i = 0 ; i < a; ++i)
{
p = p->pnext;
}
printf("k=%d\n",p->date);
return p;
}
}
int delete_link(Link_t *plink , DataType n)
{
if(plink->clen == 0)
{
return 0;
}
else if(plink->clen == 1)
{
pop_link_head(plink);
return 1;
}
Link_node_t *p = plink->phead;
Link_node_t *q = plink->phead;
int i = 0;
for(i = 0 ; i < n - 1 ; ++i)
{
p = p->pnext;
}
for(i = 0 ; i < n - 2 ; ++i)
{
q = q->pnext;
}
q->pnext = p->pnext;
free(p);
plink->clen--;
return 1;
}