c语言链表
1. 链表介绍
c语言的单向链表翻转是面试官常问问题之一,故此,咱就谈一谈,链表并不是如此可怕,学不会,想不通.
链表和数组一样都是存储数据,链表是非连续,非顺序的存储结构.
链表是灵活的内存动态管理(随机分配空间),删除创建结点非常方便
链表组成:由一系列结点组成.
链表结点:实际上是结构体变量.
typedef struct _LINKNODE
{
int data;// 数据域
struct _LINKNODE *next;// 指针域
}Link_Node;
链表结点包含两个部分:
1.存储数据元素的数据域(结构体),
2.存储下一个结点地址的指针域.
上图中的就是一个简单的单向链表,明白了单向链表就可以进军其余的链表结构了,都是一一相通的.
结点:data数据域就是存放的结构体(含有各种数据),或者理解为int data;
next就是链表的核心了,就是一个指针,指向下一个结点,与下一个结点建立联系.
2. 链表和数组的区别
数组:一次性分配连续的存储区域,int num[60] = {0};
优点:随机访问元素效率高
缺点:
l 开辟内存过大时,易分配失败
l 插入和删除元素效率低下
链表:无需一次性分配连续的存储空间,只需要分配n快结点存储区域,通过指针建立联系
优点:
l 不需要一次性分配连续的存储区域
l 删除和插入效率高
缺点:
随机访问元素效率低
3. 链表分类
l 1. 静态链表和动态链表
链表按照线性表链式存储结构分为静态链表和动态链表
静态链表:是在初始化的时候分配好足够的内存空间,存储空间是静态的,分配在栈上,模拟数组实现的,是顺序的存储结构
动态链表:是动态申请内存的,每个节点物理地址不连续
静态链表实例:
#pragma warning(disable:4996)
#include <>
#include <>
#include <>
// 定义链表结点
typedef struct _LINKNODE
{
int data;// 数据域
struct _LINKNODE *next;// 指针域
}Link_Node;
int main(int argc, char *argv[])
{
// 初始化三个链表结点(结构体)
Link_Node Node1 = {1,NULL};
Link_Node Node2 = {2,NULL};
Link_Node Node3 = {3,NULL};
// 链表串联起来,第一个结点指向第二个
= &Node2;// Node1的next指针指向Node2
= &Node3;
= NULL;// 尾结点
// 定义头结点,指向第一个结点
Link_Node *head = &Node1;
// 遍历链表,头结点-->尾结点
while (head != NULL)
{
printf("data : [ %d ]\n",head->data);
// 指针下移
head = head->next;
}
printf("hello...\n");
system("pause");
return 0;
}
动态链表实例:
#pragma warning(disable:4996)
#include <>
#include <>
#include <>
// 定义链表结点
typedef struct _LINKNODE
{
int data;// 数据域
struct _LINKNODE *next;// 指针域
}Link_Node;
int main(int argc, char *argv[])
{
// 动态申请3个结点
Link_Node *Node1 = (Link_Node *)malloc(sizeof(Link_Node));
// 初始化数据域
Node1->data = 1;// Node是指针所以用指向箭头
Link_Node *Node2 = (Link_Node *)malloc(sizeof(Link_Node));
Node2->data = 2;
Link_Node *Node3 = (Link_Node *)malloc(sizeof(Link_Node));
Node3->data = 3;
// 建立结点关系
Node1->next = Node2;// Node1的next指向Node2;
Node2->next = Node3;
Node3->next = NULL;
// 定义头结点指向第一个结点Node1
Link_Node *head = Node1;
// 遍历链表
while (head != NULL)
{
printf("data:[ %d ]\n",head->data);
// 指针下移
head = head->next;
}
printf("hello...\n");
system("pause");
return 0;
}
l 2. 带头链表和不带头链表
n 带头链表:固定一个节点作为头结点,不关心数据域,起一个标志位的作用,链表结点如何变化,此头结点固定不变
n 不带头结点:头结点不固定,所有结点都可以作为头,可以随机变化
链表按照类型:又划分为:单链表,双链表,循环链表
单向链表:
双向链表:
循环链表:
双向循环链表
4. 链表的基本操作à基于单向链表
1. 创建链表结点域
链表结点:数据域和指针域à结构体
typedef struct _LINKNODE
{
int data;// 数据域
struct _LINKNODE *next;// 指针域
}Link_Node;
2. 创建链表
建立带头结点的单向链表,循环创建结点,结点数值为<=0时,作为结束,链表的头结点地址作为函数值返回.
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 = cur = pNew;// head作为头结点,cur保存结点
// 循环创建结点
int dataid = 0;
while (1)
{
printf("请输入data id编号:");
scanf("%d",&dataid);
if (dataid <= 0)
{
break;// 跳出循环
}
// 创建新结点
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;
}
// 保存链表(带头链表的除了头之外的链表)
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;
}
// 保存第一个有效结点
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;
}
// 保存结点,获取最后一个结点
Link_Node *cur = head;
while (cur->next != NULL)
{
// 结点后移
cur = cur->next;
}
// 创建新结点,插入
Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));
pNew->data = dataid;
// 尾结点的next指向新结点
cur->next = pNew;
// 新结点的next指向NULL
pNew->next = NULL;
}
6.指定位置
// 找到data为num的前面插入,找不到就尾插
void Init_Insert_Link_Node(Link_Node *head,int num,int dataid)
{
if (head == NULL)
{
return;
}
// cur为第一个有效结点
Link_Node *cur = head->next;
Link_Node *pre = head;//保存前结点
while (cur != NULL)
{
if (cur->data == num)
{
break;
}
// 循环查找data
// 指针下移
pre = pre->next;
cur = cur->next;
}
// 1.找到匹配结点,cur为匹配结点,pre为上一个结点
// 2.没有找到,说明cur指向NULL,pre为cur的上一个结点
// pre->next = cur
// cur = NULL
// 插入新结点
Link_Node *pNew = (Link_Node *)malloc(sizeof(Link_Node));
pNew->data = dataid;
// 尾结点的next指向新结点
pre->next = pNew;
// 新结点的next指向NULL
pNew->next = cur;
}
7. 删除指定data第一个值
// 删除指定data第一个值
void Del_Link_Node(Link_Node *head,int dataid)
{
if (head == NULL)
{
return;
}
// cur为第一个有效结点
Link_Node *cur = head->next;
// pre保存cur的上个结点
Link_Node *pre = head;
// 没有找到匹配结点,1代表找到
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 (0 == flag)
{
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 = NULL;
// 当前结点下移
cur = head;
}
printf("链表清空\n");
}
函数
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);
// 尾插法
Init_Tail_Link_Node(headLink_Node,2222);
Print_Link_Node(headLink_Node);
// 查找4,插入
Init_Insert_Link_Node(headLink_Node,4,3333);
Print_Link_Node(headLink_Node);
// 删除2
Del_Link_Node(headLink_Node,2);
Print_Link_Node(headLink_Node);
// 清空链表
Destroy_Link_Node(headLink_Node);
printf("hello...\n");
system("pause");
return 0;
}