数据结构----链表
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;
}