【数据结构】之链表（C语⾔描述）
链表是线性表的⼀种，是⼀种物理存储单元上⾮连续的存储结构，链表中的数据元素之间是通过指针链接实现的。
链表由⼀系列节点组成，节点可以在运⾏时动态的⽣成。
链表中国的每个节点分为两部分：⼀部分是存储数据的数据域，另⼀部分是存储下⼀个节点的地址的指针域。
如果要在链表中查某个位置的元素，需要从第⼀个元素开始，循着指针链⼀个节点⼀个节点的，不像顺序表那样可以直接通过下标获取对应的元素，因此，链表不适合查询操作频繁的场景。
如果要在链表中添加或删除某个元素，只需要通过指针操作，将要操作的节点链⼊指针链或从指针链中移除即可，不必像顺序表那样需要移动之后的所有节点，因此，链表更适合增删操作频繁的场景。
使⽤链表不需要像顺序表那样，处处考虑要不要给表扩容，链表中的元素都是在运⾏时动态⽣成的，因此可以充分利⽤计算机的内存空间；但是，由于链表中的每个元素都需要包括数据域和指针域两块区域，因此空间开销也是⽐较⼤的。
下⾯是⽤ C语⾔描述的链表的代码：
链表数据结构的头⽂件LinkedList.h中的代码：
/**
* 线性表（链式存储）
* 注意：线性表的第⼀个节点不存储任何数据，只起到表头的作⽤
*/
#include <stdio.h>
#include <stdlib.h>
// 类型定义
typedef int Status; // ⽅法的返回值
typedef int LinkedElemType; // LinkedList数据结构中节点中存储的数据的类型
// LinkedList中的节点的结构体
typedef struct LinkedNode {
LinkedElemType value;
struct LinkedNode* nextNode;
} LinkedNode;
// LinkedList数据结构
typedef struct LinkedList {
LinkedNode* data;
int length;
} LinkedList;
// 1.创建带头结点的空链表
void initLinkedList(LinkedList* L) {
L->data = (LinkedNode*)malloc(sizeof(LinkedNode));
if(L->data != NULL) {
L->data->nextNode = NULL;
L->length = 0;
printf("创建链表成功！\n");
}
}
// 2.销毁链表
void destroyLinkedList(LinkedList* L) {
LinkedNode* node = NULL;
if(L->data == NULL) {
printf("链表不存在！\n");
exit(1);
}
while(L->data != NULL) {
node = L->data;
L->data = L->data->nextNode;
free(node);
}
printf("销毁链表成功！\n");
}
// 3.清空链表（使链表只剩下表头）
void clearLinkedList(LinkedList* L) {
LinkedNode* node = NULL;
if(L->data == NULL) {
printf("链表不存在！\n");
exit(1);
}
}
L->length = 0;
printf("清空链表成功！\n");
}
// 4.返回链表的长度
int getLinkedListSize(LinkedList* L) {
return L->length;
}
// 5.判断链表中是否存储着数据
Status isLinkedListEmpty(LinkedList* L) {
return L->data->nextNode == NULL;
}
// 6.返回链表中第i个数据元素的值
LinkedElemType getLinkedElemAtPos(LinkedList* L, int i) {
LinkedNode* node = NULL;
int index = -1;
if(L->data == NULL) {
printf("链表不存在！\n");
exit(1);
}
if(i < 1 || i > L->length) {
printf("下标⽆效！\n");
exit(1);
}
node = L->data;
for(index = 1; index <= i; index++) {
node = node->nextNode;
}
return node->value;
}
// 7.在链表L中检索值为e的数据元素（第⼀个元素）
LinkedNode* getLinkedElem(LinkedList* L, LinkedElemType e) {
LinkedNode* node = L->data;
if(L->data == NULL) {
printf("链表不存在！\n");
return NULL;
}
while(node->nextNode != NULL) {
node = node->nextNode;
if(e == node->value) {
return node;
}
}
return NULL;
}
// 8.在链表L中第i个数据元素之前插⼊数据元素e
void insertLinkedElemBefore(LinkedList* L, int i, LinkedElemType e) { LinkedNode* priorNode = L->data;
LinkedNode* nextNode = NULL;
LinkedNode* newNode = NULL;
int index = -1;
if(L->data == NULL) {
printf("链表不存在！\n");
exit(1);
}
if(i < 1 || i >= L->length) {
printf("下标⽆效！\n");
exit(1);
}
newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->value = e;
for(index = 1; index < i; index++) {
priorNode = priorNode->nextNode;
nextNode = priorNode->nextNode;
}
priorNode->nextNode = newNode;
newNode->nextNode = nextNode;
L->length++;
printf("在第%d个位置插⼊%d成功！\n", i, e);
}
// 9.在表尾添加元素e
void insertElemAtEnd(LinkedList* L, LinkedElemType e) {
LinkedNode* currNode = NULL;
LinkedNode* newNode = NULL;
currNode = L->data;
while(currNode->nextNode != NULL) {
currNode = currNode->nextNode;
}
newNode = (LinkedNode*)malloc(sizeof(LinkedNode));
newNode->value = e;
newNode->nextNode = NULL;
currNode->nextNode = newNode;
L->length++;
printf("成功在表尾添加元素%d\n", e);
}
// 10.删除链表中第i个位置上的元素
void deleteLinkedElemAtPos(LinkedList* L, int i) {
LinkedNode* priorNode = L->data;
LinkedNode* nextNode = NULL;
LinkedNode* oldNode = NULL;
int index = -1;
if(L->data == NULL) {
printf("链表不存在！\n");
exit(1);
}
if(i < 1 || i > L->length) {
printf("下标⽆效！\n");
exit(1);
}
for(index = 1; index < i; index++) {
priorNode = priorNode->nextNode;
nextNode = priorNode->nextNode;
}
oldNode = nextNode;
priorNode->nextNode = nextNode->nextNode;
L->length--;
printf("成功删除第%d个位置上的元素%d！\n", i, oldNode->value); free(oldNode);
}
// 11.返回给定元素的前驱节点
LinkedNode* getPriorLinkedElem(LinkedList* L, LinkedNode* e) {
LinkedNode* priorNode = NULL;
LinkedNode* currNode = NULL;
if(L->data == NULL) {
printf("链表不存在！");
return NULL;
}
if(e == L->data->nextNode) {
return L->data->nextNode;
}
priorNode = L->data;
currNode = priorNode->nextNode;
while(currNode->nextNode != NULL) {
if(currNode == e) {
return priorNode;
}
priorNode = currNode;
currNode = priorNode->nextNode;
}
return NULL;
}
c语言struct头文件// 12.返回给定元素的后继节点
LinkedNode* getNextLinkedElem(LinkedList* L, LinkedNode* e) {
LinkedNode* currNode = NULL;
if(L->data == NULL) {
printf("链表不存在！\n");
return NULL;
}
currNode = L->data;
while(currNode->nextNode != NULL) {
if(currNode == e) {
return currNode->nextNode;
}
currNode = currNode->nextNode;
}
return NULL;
}
// 13.遍历链表
void traverseLinkedList(LinkedList* L) {
LinkedNode* currNode = NULL;
currNode = L->data->nextNode;
while(currNode != NULL) {
printf("%-4d", currNode->value);
currNode = currNode->nextNode;
}
printf("\n");
}
testLinkedList() {
// 声明链表对象
LinkedList list;
// 测试节点
LinkedNode* testNode;
// 初始化链表
initLinkedList(&list);
// 销毁链表
// destroyLinkedList(&list);
// 清空链表
clearLinkedList(&list);
// 获取链表长度
printf("当前链表长度：%d\n", getLinkedListSize(&list));
// 判断链表中是否存储着数据
printf("链表中是否存储着数据：%s\n", isLinkedListEmpty(&list) ? "否" : "是");
/
/ 在表尾添加元素
insertElemAtEnd(&list, 1);
insertElemAtEnd(&list, 2);
insertElemAtEnd(&list, 4);
insertElemAtEnd(&list, 5);
insertElemAtEnd(&list, 6);
// 遍历链表中的元素
traverseLinkedList(&list);
// 获取某个位置的元素值
printf("当前链表中第2个元素的值是：%d\n", getLinkedElemAtPos(&list, 2));
// 在某元素前插⼊新元素
insertLinkedElemBefore(&list, 3, 3);
insertLinkedElemBefore(&list, 3, 3);
// 遍历链表中的元素
traverseLinkedList(&list);
// 删除某位置的元素
deleteLinkedElemAtPos(&list, 4);
// 遍历链表中的元素
traverseLinkedList(&list);
// 获取对应值的第⼀个元素
testNode = getLinkedElem(&list, 3);
// 返回某节点的前驱节点
printf("测试节点的前驱节点的值是：%d\n", getPriorLinkedElem(&list, testNode)->value); // 返回某节点的后继节点
printf("测试节点的后继节点的值是：%d\n", getNextLinkedElem(&list, testNode)->value); }
主函数所在的⽂件main.c中的代码：
#include <LinkedList.h>
//主函数
int main() {
testLinkedList(); // 线性表（链式存储）结构的测试
return0;
}
运⾏结果如下：
创建链表成功！
清空链表成功！
当前链表长度：0
链表中是否存储着数据：否
成功在表尾添加元素1
成功在表尾添加元素2
成功在表尾添加元素4
成功在表尾添加元素5
成功在表尾添加元素6
1 2 4 5 6
当前链表中第2个元素的值是：2
在第3个位置插⼊3成功！
在第3个位置插⼊3成功！
1 2 3 3 4 5 6
成功删除第4个位置上的元素3！
1 2 3 4 5 6
测试节点的前驱节点的值是：2
链表分为好⼏种，上⾯介绍的这种链表叫做线性链表，它的特点是：线性存储，只能通过前⼀个节点到后⼀个节点，不能通过后⼀个节点到前⼀个节点；
链表还有其他的⼏种，下⾯来简单介绍：
1、循环链表：
链表的头尾节点相连，形成⼀个环。
实现⽅式：我们只需要将线性链表稍加改造，将尾节点的下⼀个节点的指针指向头结点即可。
2、双向链表：
既可以通过前⼀个节点到后⼀个节点，也可以通过后⼀个节点到前⼀个节点。
实现⽅式：在线性链表的节点数据结构体中，不但要定义指向⼀个节点的指针，也要定义指向前⼀个节点的指针。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论