5.1链表的思路理解
顺序表：空间是连续的，先申请再使用
链表：来一个数据申请一块空间
5.2链表的创建
5.2.1结构体理解
typedef int data_t;
typedef struct node {
data_t data; //存放一个数据 (普通变量)
struct node * next; //存放下一个节点的起始地址 指针的数据类型是指向的这块空
间决定的
}listnode, * linklist;5.2.2创建函数的实现
5.2.2.1 逻辑分析
前提：头结点不放数据 最后一个元素写成NULL(比较特殊)
1. 申请空间
2. data不需要赋值
3. next = NULL 指针初始化指向NULL 不能随便指 否则可能会变成野指针
5.2.2.2 代码实现
linklist list_create() {
linklist H;
H = (linklist)malloc(sizeof(listnode));
if (H == NULL) { // 注意 此处是两个等号 “ == ”
printf("malloc failed\n");
return H;
}
H->data = 0; //可写可不写
H->next = NULL;
return H;
}
5.3链表的头插法
5.3.1 逻辑分析
1、申请空间
2、data赋值
3、连指针（切记防丢）
5.3.2代码实现
int list_tail_insert(linklist H, data_t value) {
linklist p;
if (H == NULL) {
printf("H is NULL\n");
return -1;
}
//1 new node p
if ((p = (linklist)malloc(sizeof(listnode))) == NULL) {
printf("malloc failed\n");
return -1; // 函数的返回类型是int 所以不能返回NULL 应该返回-1
}
//data赋值
p->data = value;
//链接指针
p->next = H->next;
H->next = p;
return 0;
}5.4链表的打印
5.4.1 逻辑分析
如何遍历链表？
5.4.2代码实现
int list_show(linklist H) {
linklist p;
if (H == NULL) {
printf("H is NULL\n");
return -1;
}
p = H;
while (p->next != NULL) {// 不为空才能打印结点
printf("%d ", p->next->data);
//p->data第一个节点是不存放数据的 如果想打印数据 那就得写成p->next->data
p = p->next;//p往后移动 直到最后一个数据为NULL 就不去打印了 退出
}
puts("");
return 0;
}5.5链表的头删法
5.5.1逻辑分析
1. 判断是否为空
2. 保存要删除的节点
3. 链接指针 p = H->next; H->next = p->next;
4. free要删除的节点
5.5.2代码实现
int list_delete(linklist H) {
linklist q;
if (H == NULL) { //判断链表存不存在
printf("H is NULL\n");
return -1;
}
if (H->next == NULL) { // 链表是否为空
printf("list is empty\n");
return -1;
}
//3 update list
q = H->next;
H->next = q->next; //H->next = H->next->next;
//4 free
printf("free:%d\n", q->data); //可以打印一下删除的值
free(q);
q = NULL;
return 0;
}5.6链表的按位置插入
5.6.1逻辑分析
1. 找到插入位置的前一个节点地址 先找位置 a3 因为a4的话你怎么表示a3的地址 (单向链表)
2. 申请空间
3. data赋值
4. 连指针（切记防丢） 先链接后面再前面
5.6.2代码实现
linklist list_get(linklist H, int pos) {
linklist p;
int i;
if (H == NULL) { //判断表是否存在
printf("H is NULL\n");
return NULL;
}
if (pos == -1) { //等于-1 错误 因为下标没有从-1开始数的
return H;
}
if (pos < -1) { // 小于-1 也有问题
printf("pos is invalid\n");
return NULL;
}
// 大于-1 就去找位置
p = H;
i = -1; //最开始的时候从-1开始
while (i < pos) {
p = p->next; // 往后移动一下
if (p == NULL) { //当链表比较短的时候 插入的位置比较大的时候 退出
printf("pos is invalid\n");
return NULL;
}
i++; //正常情况下 i++ 往后走 找到pos这个位置之后 跳出循环 返回p
}
return p;
}
int list_insert(linklist H, data_t value, int pos) {
linklist p;
linklist q;
if (H == NULL) { //判断表是否存在
printf("H is NULL\n");
return -1;
}
//1 locate node p (pos-1) pos是插入的位置
p = list_get(H, pos-1); //找到前一个位置 怎么去获得p呢？ 调用list_get
if (p == NULL) { //如果等于NULL 说明没有获取成功 否则成功
return -1;
}
//2 new node q 获取成功之后首先去开辟一段空间
if ((q = (linklist)malloc(sizeof(listnode))) == NULL) {
printf("malloc failed\n");
return -1;
}
q->data = value; //赋值
q->next = NULL; //可以省略
//3 insert
q->next = p->next;
p->next = q; // 现在就是连进去了
return 0;
}5.7链表的按位置删除
5.7.1逻辑分析
1. 判断链表是否存在
2. 判断是否为空
3. 找到要删除节点的前一个节点
4. 保存要删除的节点 5. 链接指针 q = p->next; p->next = q->next; 6. free要删
除的节点
5.7.2代码实现
int list_delete(linklist H, int pos) {
linklist p;
linklist q;
//1
if (H == NULL) {
printf("H is NULL\n");
return -1;
}
if (H->next == NULL) {
printf("List is empty\n");
return -1;
}
//2 locate prior
p = list_get(H, pos-1); // 找到删除结点的位置 pos-1就是前一个结点的位置
if (p == NULL) // 位置输入的不合适 就返回
return -1;
if (p->next == NULL) { // 如果删除的结点是NULL 的时候 就不能删除了
printf("delete pos is invalid\n");
return -1;
}
//3 update list
q = p->next; // 保存结点的地址
p->next = q->next;//p->next = p->next->next; // 连接指针的那一步
//4 free
printf("free:%d\n", q->data);
free(q); // 释放 就是说这个q的地址我不使用了 可以分给别人了 但是q里面的值还存在
q = NULL; // 指针指向NULL 就是把值清掉
return 0;
}5.8拓展练习
5.8.1链表的反转
需求：3 ->4 ->5-> 6-> 7 1 头插法 拿个3头插 拿个4 ......循环拿
结果：7 ->6-> 5-> 4-> 3
思路：
1 判断表是否存在
2 判断结点的个数 如果只有一个有效结点 就不需要反转了
3
5.8.1.1逻辑分析
5.8.1.2代码实现
int list_reverse(linklist H) {
//定义两个指针 一个标记剩下的结点 一个指针标记要往下拿拿个结点
linklist p;
linklist q;
if (H == NULL) { //判断链表是否存在
printf("H is NULL\n");
return -1;
}
if (H->next == NULL || H->next->next == NULL) { //判断只有一个节点的时候就不需要
反转了
return 0;
}
p = H->next->next; //标记的是剩下的结点
H->next->next = NULL; //拿出来的是前两个结点
while (p != NULL) {
q = p; // q保存一下p 也就是头插的这个节点
p = p->next; // 然后往后移动一下 p将后面的结点标记起来
q->next = H->next; // 这个时候直接头插就行了 连接
H->next = q; // 连接
}
return 0;
}
5.8.2 两个有序链表合并
5.8.2.1逻辑分析
5.8.2.2代码实现
linklist list_merge(linklist H1, linklist H2) {
linklist p, q;
if (H1 == NULL){
printf("H1 is NULL\n");
return -1;
}
if (H2 == NULL){
printf("H1 is NULL\n");
return -1;
}
p = H1->next;//拿的最小的结点
q = H2->next;
while(p != NULL && q != NULL)
{
if (p->data <= q->data)
{
H1->next = p;
p = p->next;
H1 = H1->next;
}
else
{
H1->next = q;
q = q->next;
H1 = H1->next;
}
}
if(p != NULL)// 判断这个链表的值全部小于L2链表 这样的情况直接去连接
{
H1->next = p;
}
if(q != NULL)
{
H1->next = q;
}
//根据需求释放，如果后面其他函数还用，就不要释放
free(H2);
H2 = NULL;
return r;
}需求：2 6 3 7 4 9 5
结果：2 3 4 5 6 7 9
思路就是：
依次拿数据 第一个是2 然后拿6 此时去判断两个数大小 再去排序 排好之后拿第三个数；然后再依次比较
表中的数据，在插入到合适的位置，最后保证遍历出来的是有序链表
5.8.3.2代码实现
int list_order(linklist H){
linklist p,q,r;// 一个标记拿出来的结点 一个存放剩余的结点 r始终从头开始遍历一遍
int t;
if(H == NULL){
printf("H is NULL");
return -1;
}
p = H->next;
H->next = NULL;
while(p != NULL)
{
q = p;
p = p->next;
r = H;//代表指向结点的开始
while(r->next && r->next->data < q->data){
r = r->next;
}
q->next = r->next; //插入结点
r->next = q;
}
return 0;
}