链表的概念以及结构
概念:链表是一种物理存储结构上不连续的、非顺序的存储结构,数据元素的顺序是通过节点中的指针来实现的。
结构:(此处指单向非循环链表)链表中每个节点的存储元素一般包含两部分,数据和下一个节点的地址。
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {}
};
![链表结构示意图]
遍历打印链表
在链表中访问元素需要通过每个节点中存放的下一个元素地址,才能找到下一个节点的位置。具体代码实现如下:
// 遍历链表
void SListPrint(SListNode* phead) {
SListNode* cur = phead; // 创建一个指针来指向头结点的位置
while(cur) {
printf("%d->", cur->val); // 打印当前节点的数据
cur = cur->next; // 将指针指向下一个节点
}
}
申请节点
链表中每一个节点都是动态开辟出来的,所以要新增一个节点之前要先申请一个节点,每个节点的大小为该结构体的大小,开辟成功之后,该节点数据部分存放输入的值,地址(next)置为 NULL。
C 语言代码展示如下(这部分主要是为了了解具体实现步骤):
// 申请节点
SListNode* SListBuyNode(SListNodeDataType x) {
SListNode* newnode = (SListNode*)malloc(sizeof(SListNode)); // 申请地址空间
if (newnode == NULL) { // 判断是否成功
perror("malloc:");
exit(-1);
}
newnode->data = x;
newnode->next = NULL;
return newnode;
}
用 C++ 则更为简洁且更加安全,代码如下:
struct {
val;
ListNode* next;
( x) : (x), () {};
};
ListNode* newNode = (newValue);

