数据结构-----【链表:基础】

链表基础

1、链表的理论基础

1）基础：

链表：通过指针串联在一起的线性结构，每个节点由两部分组成，一个是数据域，一个是指针域（存放指向下一个节点的指针），最后一个指针域指向null(空指针的意思)。

链表的入口节点称为链表的头结点也就是head。

2)链表类型：

链表包括单链表、双链表、循环链表：

单链表：指针域只能指向节点的下一个节点。

双链表：既可以向前查询也可以向后查询。

循环链表：链表首尾相连，循环链表可以解决约瑟夫环的问题。

3）链表的存储方式：

​ 数组在内存中是连续分布的，但是链表在内存中并不是连续分布的，链表通过指针域的指针连接在内存中的各个节点。例如：这个链表起始节点为2， 终止节点为7， 各个节点分布在内存的不同地址空间上，通过指针串联在一起。

4）链表的定义：

这个单向链表中，正是因为我们定义了节点的构造函数，指明了可以把x丢给val，才可以在初始化的时候直接赋值。

//单链表
struct ListNode{int val;//数据ListNode* next;//指向下一个节点的指针ListNode(int x):val(x),next(NULL){} //节点构造函数
};
//为什么要自己写构造函数呢？c++可以自己生成构造函数
//通过自己定义构造函数初始化节点
ListNode* head = new ListNode(5);
//使用默认构造函数初始化节点，不能直接给变量赋值!!
ListNode* head = new ListNode;
head->val = 5;

5）链表的操作：

链表中要注意的就是是否更改原来指针！由项目引发的思考：不得不引入值传递和指针传递：

**传递值：**如果传递的是基本数据类型或结构体（而不是指针），则函数内对形参的修改不会影响外部的实际参数。

#include <stdio.h>void modifyValue(int x) {x = x + 1;  // 修改的是 x 的副本，不会影响外部的实际参数
}int main() {int a = 5;modifyValue(a);printf("%d\n", a);  // 输出 5，a 没有被修改return 0;
}

**传递指针：**如果传递的是指针，函数内对指针所指向的数据的修改会影响到外部的实际参数。但修改指针本身的值不会影响外部的指针。

#include <stdio.h>void modifyPointer(int* ptr) {*ptr = *ptr + 1;  // 修改指针所指向的数据，会影响外部的实际参数ptr ++;      // 修改指针本身的值，不会影响外部的实际参数
}int main() {int b = 10;int* p = &b;modifyPointer(p);printf("%d\n", *p);  // 输出 11，p 所指向的数据被修改return 0;
}

• 递值时，函数内的修改不会影响外部的实际参数。

• 传递指针时，函数内对指针所指向的数据的修改会影响外部的实际参数，但修改指针本身的值不会影响外部的指针。

1.打印链表

为了保险起见，还是可以在函数里面用临时变量保存链表值：

void SlistPrint(ListNode *phead){ListNode *cur = phead;while(!cur){printf("%d->", cur->data);cur = cur-> next;}printf("NULL\n");
}

2.清空链表：

好家伙不传入**pehead就要报错：

//一个结点的定义
typedef struct ListNode{int val;ListNode* next;//ListNode(int x):val(x),next(NULL){};//重构函数
}ListNode;//因为要改变外部链表头的值，所以要传入**
//pphead 表示一个 ListNode 结构体的对象，而不是一个指针。在你的 SListClear 函数中，*pphead = NULL; 尝试将一个结构体对象设置为 NULL，这是不合法的。
//如果你的目的是通过函数清空链表并将外部传递的链表头指针设置为 NULL，你应该使用指向指针的指针，即 ListNode** pphead，并在函数内部通过解引用两次来修改外部传递的链表头指针的值。
void SListClear(ListNode **pphead)//**PPhead指向指针的指针
{ListNode *cur = *pphead;while(!cur){ListNode* temp = cur->next;free(cur);cur = temp;}*pphead = NULL;
}int main(){ListNode* head = (ListNode*)malloc(sizeof(ListNode));head->val = 1;head->next = (ListNode*)malloc(sizeof(ListNode));head->next->val = 2;head->next->next = NULL;SListClear(&head);//注意这里是&相当于 **head// 在这里 head 已经被设置为 NULL，链表被清空if (head == NULL) {printf("List is empty\n");}system("pause"); return 0;
}

3.创建结点：

typedef struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(NULL){};//重构函数 C++可以直接写重构函数
}ListNode;//等效于直接 ListNode* node = new ListNode(val);
ListNode* CreateListNode(int x){ListNode* NewNode = (ListNode*)malloc(sizeof(ListNode));ListNode->val = x;ListNode->next = NULL;return NewNode;
}

3.删除节点：

比如删除D节点：

首先将C节点的next指针指向E，然后再手动释放D节点（py有自己的内存回收机制，不用手动释放，但是c/c++最好手动释放）

特别注意：因为单链表的只能指向下一个节点，删除某个节点的时候指针是在这个节点前一个节点的位置的。

typedef struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(NULL){};
}ListNode;ListNode* delete(ListNode * node){if(node->next!=NULL && node->next->next!=NULL){node->next = node->next->next;}return node;
}

4、添加节点：

​ 在C和D中添加节点，让C的指针域指向F，再把F的指针域指向D。（添加不需要释放内存）

​ 链表的增添和删除都是O（1）操作，也不会影响到其他的节点，但是查找的时间复杂度可能是O(n)(一个一个next指针进行查找)。

typedef struct ListNode{int val;ListNode* next;ListNode(int x):val(x),next(NULL){};
}ListNode;ListNode* add(ListNode * node,int val){ListNode* tmp = new ListNode(val);temp->next = node->next;node->next = temp;return node;
}

4.数组和链表的对比