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);
}