定义：数据元素随机存储，并通过指针表示数据之间逻辑关系的存储结构就是链式存储结构
节点
链表中每个数据的存储称为节点由两部分组成：
- 数据元素本身，其所在的区域称为数据域；
- 指向直接后继元素的指针，所在的区域称为指针域；
链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中
链表的构成
一个完整的链表需要由以下几部分构成：
- 头指针：一个普通的指针，它的特点是永远指向链表第一个节点的位置。很明显，头指针用于指明链表的位置，便于后期找到链表并使用表中的数据；
- 节点：链表中的节点又细分为头节点、首元节点和其他节点：
- 头节点：其实就是一个不存任何数据的空节点，通常作为链表的第一个节点。对于链表来说，头节点不是必须的，它的作用只是为了方便解决某些实际问题；
- 首元节点：由于头节点（也就是空节点）的缘故，链表中称第一个存有数据的节点为首元节点。首元节点只是对链表中第一个存有数据节点的一个称谓，没有实际意义；
- 其他节点：链表中其他的节点；
链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点
链表的创建
- 声明一个头指针（如果有必要，可以声明一个头节点）；
- 创建多个存储数据的节点，在创建的过程中，要随时与其前驱节点建立逻辑关系；
//声明节点结构
typedef struct Link {
int elem;//存储整形元素
struct Link *next;//指向直接后继元素的指针
}link;
//创建链表的函数
link * initLink() {
link * p = (link*)malloc(sizeof(link));//创建一个头结点
link * temp = p;//声明一个指针指向头结点，用于遍历链表
int i = 0;
//生成链表
for (i = 1; i < 5; i++) {
//创建节点并初始化
link *a = (link*)malloc(sizeof(link));
a->elem = i;
a->next = NULL;
//建立新节点与直接前驱节点的逻辑关系
temp->next = a;
temp = temp->next;
}
return p;
}
链表插入元素
向链表中增添元素，根据添加位置不同，可分为以下 3 种情况：
- 插入到链表的头部（头节点之后），作为首元节点；
- 插入到链表中间的某个位置；
- 插入到链表的最末端，作为链表中最后一个数据元素；
新元素插入步骤：
- 将新结点的 next 指针指向插入位置后的结点；
- 将插入位置前结点的 next 指针指向插入结点；
//p为原链表，elem表示新数据元素，add表示新元素要插入的位置
link * insertElem(link * p, int elem, int add) {
link * temp = p;//创建临时结点temp
link * c = NULL;
int i = 0;
//首先找到要插入位置的上一个结点
for (i = 1; i < add; i++) {
if (temp == NULL) {
printf("插入位置无效\n");
return p;
}
temp = temp->next;
}
//创建插入结点c
c = (link*)malloc(sizeof(link));
c->elem = elem;
//向链表中插入结点
c->next = temp->next;
temp->next = c;
return p;
}
链表删除元素
操作步骤：
- 将结点从链表中摘下来;
temp->next=temp->next->next; - 手动释放掉结点，回收被结点占用的存储空间;
free(del);
链表元素查找
从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对，直至比对成功或遍历至链表最末端的 NULL
链表元素更新
遍历找到存储此元素的节点，对节点中的数据域做更改操作即可
栈
栈是一种只能从表的一端存取数据且遵循 "先进后出" 原则的线性存储结构。
栈的开口端被称为栈顶；相应地，封口端被称为栈底
- 向栈中添加元素，此过程被称为"进栈"（入栈或压栈）；
- 从栈中提取出指定元素，此过程被称为"出栈"（或弹栈）；
链栈
采用链式存储结构实现栈结构；
通常将链表的头部作为栈顶，尾部作为栈底，
将链表头部作为栈顶的一端，可以避免在实现数据 "入栈" 和 "出栈" 操作时做大量遍历链表的耗时操作。
链表的头部作为栈顶，意味着：
- 在实现数据"入栈"操作时，需要将数据从链表的头部插入；
- 在实现数据"出栈"操作时，需要删除链表头部的首元节点；
队列
数据从表的一端进，从另一端出，且遵循 "先进先出" 原则的线性存储结构就是队列。
链式队列
链式队列，简称"链队列"，即使用链表实现的队列存储结构。
初始状态
初始状态的队列中没有存储任何数据元素，top(队头) 和 rear(队尾) 指针都同时指向头节点。
//链表中的节点结构
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//创建链式队列的函数
QNode * initQueue(){
//创建一个头节点
QNode * queue=(QNode*)malloc(sizeof(QNode));
//对头节点进行初始化
queue->next=NULL;
return queue;
}
...
QNode * queue,*top,*rear;
queue=top=rear=initQueue();//创建头结点
链式队列数据入队
链队队列中，当有新的数据元素入队，只需进行以下 3 步操作：
- 将该数据元素用节点包裹，例如新节点名称为 elem；
- 与 rear 指针指向的节点建立逻辑关系，即执行 rear->next=elem；
- 最后移动 rear 指针指向该新节点，即 rear=elem；
QNode* enQueue(QNode * rear,int data){
//1、用节点包裹入队元素
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//2、新节点与rear节点建立逻辑关系
rear->next=enElem;
//3、rear指向新节点
rear=enElem;
//返回新的rear，为后续新元素入队做准备
return rear;
}
链式队列数据出队
链式队列中队头元素出队，需要做以下 3 步操作：
- 通过 top 指针直接找到队头节点，创建一个新指针 p 指向此即将出队的节点；
- 将 p 节点（即要出队的队头节点）从链表中摘除；
- 释放节点 p，回收其所占的内存空间；
void DeQueue(QNode * top,QNode * rear){
QNode * p=NULL;
if (top->next==NULL) {
printf("队列为空");
return ;
}
p=top->next;
printf("%d",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
}
注意：将队头元素做出队操作时，需提前判断队列中是否还有元素，如果没有，要提示用户无法做出队操作，保证程序的健壮性。
网友评论