数据结构：链表（c语言）

1.链表简介：
链表和数组一样，都是存储数据，链表是非连续，非顺序的存储结构
链表是灵活的内存动态管理（随机分配空间），删除创建结点非常方便
链表组成：由一系列结点组成
链表结点：实际上是结构体变量

typedef struct LINKNODE
{int data;// 数据域struct _LINKNODE *next;// 指针域
}Link_Node;

链表结点包含两个部分：
1.存储数据元素的数据域
2.存储下一个结点地址的指针域

2.链表和数组的区别
数组：一次性分配连续的存储区域
优点：随机访问元素效率搞
缺点：开辟内存过大时，易分配失败；插入和删除效率低下
链表：无需一次性分配连续的存储空间，只需要分配n块结点存储区域，通过指针建立联系
优点：不需要一次性分配连续的存储区域；删除和插入效率高
缺点：随机访问元素效率低

3.静态链表：是在初始化的时候就分配好足够的内存空间，存储空间是静态的，分配在栈上，模拟数组实现的，是顺序的存储结构

#include<stdio.h>
#include<string.h>
#include<stdlib.h>typedef struct LINKNODE{int data;struct LINKNODE *next;
}Link_Node;int main()
{Link_Node Node1={1,NULL};Link_Node Node2={2,NULL};Link_Node Node3={3,NULL};Node1.next=&Node2;Node2.next=&Node3;Node3.next=NULL;Link_Node *head=&Node1;while(head!=NULL){printf("data:[%d]\n",head->data);head=head->next;}return 0;
}

4.动态链表

#include<stdio.h>
#include<string.h>
#include<stdlib.h>typedef struct LINKNODE{int data;struct LINKNODE *next;
}Link_Node;int main()
{Link_Node *Node1=(Link_Node *)malloc(sizeof(Link_Node));Link_Node *Node2=(Link_Node *)malloc(sizeof(Link_Node));Link_Node *Node3=(Link_Node *)malloc(sizeof(Link_Node));Node1->data=1;Node2->data=2;Node3->data=3;Node1->next=Node2;Node2->next=Node3;Node3->next=NULL;Link_Node *head=&Node1;while(head!=NULL){printf("data:[%d]\n",head->data);head=head->next;}return 0;
}

5.带头链表和不带头链表
带头链表：固定一个结点作为头结点，不关心数据域，起一个标志位的作用，链表结点如何变化，此头结点固定不变
不带头结点：头结点不固定，所有结点都可以作为头，可以随机变化
6.链表按照类型又划分为：单向链表，双向链表，循环链表
7.链表的基本操作（基于单向链表）
1.创建链表结点域

typedef struct LINKNODE{int data;struct LINKNODE *next;
}Link_Node;

2.创建链表

Link_Node *Init_Link_Node()
{Link_Node *cur=NULL;//保存上一个结点 Link_Node *pNew=NULL;//辅助指针 Link_Node *head=NULL;//固定为头结点 //创建头结点 pNew=(Link_Node)malloc(sizeof(Link_Node));pNew->data=-1;pNew->next=NULL;head=pNew;cur=pNew;//head作为头结点，cur保存结点 //创建循环结点 int dataid; while(1){printf("请输入data id编号：");scanf("%d",&dataid);if(dataid<=0) break;else{//创建新结点 pNew=(Link_Node)malloc(sizeof(Link_Node));pNew->data=dataid;cur->next=pNew;//头结点（head）指向新结点 pNew->next=NULL;cur=pNew;//指针下移 }}return head;	
}

3.遍历链表

int Print_Link_Node(Link_Node *head)
{if(head==NULL) return -1;else{Link_Node *cur=head->next;printf("head->");while(cur!=NULL){printf("%d->",cur->data);cur=cur->next;} printf("NULL\n");//cur指向了NULL }	
}

4.在头部插入结点

void Init_Head_Link_Node(Link_Node *head,int dataid)
{if(head==NULL) return -1;else{Link_Node *cur=head->next;//保存第一个有效结点 Link_Node *pNew=(Link_Node *)malloc(sizeof(Link_Node));pNew->data=dataid;//建立关系 head->next=pNew;pNew->next=cur;}
}

5.尾部插入

void Init_Tail_Link_Node(Link_Node *head,int dataid)
{if(head==NULL) return -1;else{Link_Node *cur=head;//保存结点，获取最后一个结点 while(cur->next!=NULL){cur=cur->next;//结点后移 }Link_Node *pNew=(Link_Node *)malloc(sizeof(Link_Node));pNew->data=dataid;cur->next=pNew;pNew->next=NULL;		}	
}

6.指定位置

//找到data为num的前面插入，找不到就尾插 
void Init_Insert_Link_Node(Link_Node *head,int num,int dataid)
{if(head==NULL){return;}//一定记得判断headLink_Node *cur=head->next;//cur为第一个有效结点 Link_Node *pre=head;//pre保存cur的前一个结点 while(cur!=NULL){//此循环体是查找插入位置，找到则跳出循环 if(cur->next==num){break;} pre=pre->next; cur=cur->next;} Link_Node *pNew=(Link_Node *)malloc(sizeof(Link_Node));pNew->data=dataid;pre->next=pNew;pNew->next=cur; }

7.删除指定data第一个值

void Del_Link_Node(Link_Node *head,int dataid)
{if(head==NULL) return;Link_Node *cur=head->next;Link_Node *pre=head;int flag=0;while(cur!=NULL){if(cur->data==dataid){flag=1;pre->next=cur->next;free(cur);cur=NULL;break;}pre=pre->next;cur=cur->next;} if(flag==0){printf("没有找到%d的结点\n",dataid);}
}

8.释放链表

void Destroy_link_Node(Link_Node *head)
{link_Node *cur=head;while(cur->next!=NULL){head=head->next;free(cur);cur->next=NULL;cur=head;}printf("链表清空\n");
}

9.main函数

int main(int argc,char argv[])
{//创建链表 Link_Node *headLink_Node=Init_Link_Node();Print_Link_Node(headLink_Node);//头插法Init_Head_Link_Node(headLink_Node,1111);Print_Link_Node(headLink_Node);//尾插法Init_Tail_Link_Node(headLink_Node,2222); Print_Link_Node(headLink_Node);//查找插入Init_Insert_Link_Node(headLink_Node,4,3333);Print_Link_Node(headLink_Node);//删除Del_Link_Node(headLink_Node,2);Print_Link_Node(headLink_Node);//清空链表Destroy_Link_Node(headLink_Node); 
}