数据结构中的链式存储
一，概念
程序中存储多个数据时，数据与数据之间的存储不⼀定是连续的，数据元素 的存储位置可以是任意的，随机的。不能像之前的顺序存储⼀样，可以使⽤ 地址来表⽰先后。链式存储就不⾏，不能⽤地址的先后来表⽰。
链式存储：存储 数据+关系
数据元素：
| 数据（前一个元素的地址） | 关系（后一个元素的地址） |
即在存储数据的同时也存储数据的关系，用来表示数据间的先后关系。
二，单向列表
概念： 在使用有先后关系的链式存储时，在存储关系时只存储后一个元素的地址就能知道元素的值。
链表元素（图形表示）：
| next（下一个元素的地址） |
链表元素(代码表示)：
struct node
{
xxx data;
struct node * next;
};
链表概念
1. 头指针：是⼀个指针，存储链表中第0个元素的地址（永远表⽰链表的 开始）；便于说明链表的位置，⽅便后期找到链表
2. 节点：链表中的⼀个元素就叫做⼀个节点 头节点：在链表中通常会加⼊⼀个不存储任何数据的空节点，作为链表 的第0个元素，作⽤是之后⽅便操作链表。
链表的运算
创建链表
执行链表的运算首先就得创建一个链表
//类型声明
#include//类型声明
struct node
{
int data;
struct node * next;
};
//创建一个链表
struct node * create()
{
//创建一个空节点，头节点不存储任何数据相当于空节点
struct node * p = malloc(sizeof(struct node)); //申请一个结构体作为空节点。
if(p == NULL)
{
printf("malloc error\n");
return NULL;
}
//头节点不存储任何数据，所以p->next是没有数据的。
p->next = NULL;
return p;
}
1， 链表元素插⼊
要插入一个数据元素，就是把要插入位置的数据元素向后移动然后插入需要插入的数据元素。即先移位后插入
void insert(struct node * head,int pos,int data) //head;头指针，头节点的地址
{
struct node * p = head;//p也是头节点的地址
int i = 0;//当前有0个
//找到待插入的前一个元素的地址
while(p->next != NULL && i< pos-1)//条件就是i == pos前一个 pos作为元素地址下标
{
p = p->next;//p
i++;
}
//p;就是要插入位置的前一个
//创建新节点
struct node * q = malloc(sizeof(struct node));
q->data = data;
//插入数据元素
q->next = p->next;
p->next = q;
}
//函数调用
int main()
{
struct node * head = create();
insert(head,插入位置的地址下标,10);
}2， 删除元素
要删除数据元素首先要确定数据元素是否为空。
//删除数据元素
int empty(struct node * head) //要删除数据元素首先要判断数据元素是否存在。
{
if(head->next == NULL)
{
printf("is empty\n"); //如果数据元素不存在就返回为1
return 1;
}
else
return 0; //如果数据元素存在就返回0
}
//执行数据的删除
void del(struct node * head,int data)
{
struct node * p = head; //head和p都作为头节点
if( empty(head) )
{
return ; //数据元素不为空就执行操作
}
while(p->next != NULL)
{
if(p->next->data == data) //找到要删除的数据元素。
{
struct node * q = p->next;//q就是要删除的数据元素的地址下标
p->next = q->next;
printf("del is %d\n",q->data);
free(q); //申请的空间需要得到释放
break;
}
p = p->next;
}
}
//函数调用
int main()
{
struct node * head = create();
del(head,数据元素下标);
}3，查找：
//判断数据元素是否存在
int empty(struct node * head)
{
if(head->next == NULL)
{
printf("is empty\n"); //如果数据元素不存在就返回为1
return 1;
}
else
return 0; //如果数据元素存在就返回0
}
//查找数据元素
void search(struct node * head,int data)
{
if( empty(head) ) //首先也的判断数据元素是否为空。
{
return ; //数据元素不为空就执行操作
}
struct node * p = head;
while(p->next != NULL)
{
p = p->next;
if( p->data == data )
{
printf("find data %d\n",data);
return ;
}
}
}
//函数调用
int main()
{
struct node * head = create();
search(head,需要查找的数据元素下标);
}4，修改
需要修改一个数据元素首先就要找打这个数据元素。
//修改数据元素
void update(struct node * head,int src,int dest)
{
struct node * p = head;
while(p->next != NULL) //要修改数据元素首先要找到这个数据元素然后再执行操作。
{
p = p->next;
if( p->data == src )
{
p->data = dest; //找到数据元素执行修改。
printf("update ok\n");
return ;
}
}
}
//函数调用
int main()
{
struct node * head = create();
update(head,需要被修改的元素的地址下标,修改后的数据元素);
}5，显示所有的数据元素
//显示所有的数据元素
void show(struct node * head)
{
struct node * p = head;
//struct node * p = head->next; p != NULL
while(p->next != NULL) //当数据元素为空就停止访问
{
p = p->next;
printf("%d ",p->data);
}
printf("\n");
}
//函数调用
int main()
{
struct node * head = create();
show(head);
}
单向循环链表： 整个数据的最后一个元素不在是空（NULL）而是指向头指针，存储head。
即：P->NULL改为p->head.
双向链表：数据的关系不再是只存储后一个元素的地址，而是存储前一个和后一个的地址。
数据元素（图形说明）：
| 数据 | 关系 prior（前一个元素的地址） | 关系next（后一个元素的地址） |
数据元素（代码说明）：
struct node
{
xxx data;
struct *prior（前一个元素的地址）
struct *next（后一个元素的地址）；
};
在创建链表时，只需要在单向列表的基础上加上 p->prior==NULL即可。
在修改链表数据时：
q->prior = p;
q->next = p->next;
p->next = q;
q->next->prior = q;
在删除链表数据元素时：
q = p->next;
p->next = q->next;
q->next->prior = p;
free(q);
你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧