单链表——之二

世界属于帽皇！！！！！ 😎😎😋😋😊😍🥰😘🥵🥵

我很难想象精神状态正常的推子观众会做出“不爱有马加奈”这种选择。萝莉前辈丰富的可爱表情和小女友一般的心理活动可以说是所有角色中最有感觉的，没有之一。 🥵🥵
看推子不爱帽皇，就像四大名著不看红楼梦，说明这个人文学造诣和自我修养不足，他整个人的层次就卡在这里了，只能度过一个相对失败的人生。 😎😎

世界属于帽皇！！！！！ 😎😎😋😋😊😍🥰😘🥵🥵

---

参考：线性表_数据结构(二)线性表 从GitHub上找的
version：1.0——单链表 | Akari的小站

---

这次的相比第一次修改了不少，主要是把 删除和插入 中的那一步操作抽象出来了，变成 FindOrder了。

完整程序如下：

/**
 * @brief:
 * @version:
 * @author: @Akari
 * @date: 2023-12-27 19:25:57
 *
 * 数据结构（二） 线性表_数据结构(二)线性表-CSDN博客
  https://blog.csdn.net/liyuanyue2017/article/details/83244310
 **/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node{
    int data;
    struct Node * pNext;
}NODE, * PNODE;

PNODE List_Init();
void List_Traverse(PNODE pHead);
bool List_Insert(PNODE pHead, int pos, int val);
bool List_Delete(PNODE pHead, int pos, int * pVal);
int List_Length(PNODE pHead);
PNODE List_FindValue(PNODE pHead, int val);	// 找到了就返回那个节点的地址，想干什么就干什么
PNODE List_FindOrder(PNODE pHead, int pos);	// 其实也可以当成 bool 看待，依然可以用在 if 判断里
void List_Sort(PNODE pHead);


int main(void)
{
    int pVal;
    PNODE pHead = NULL;
    
    pHead = List_Init();
    List_Traverse(pHead);
    
    List_Insert(pHead, 1, 34);
    List_Insert(pHead, 2, 14);
    List_Insert(pHead, 1, 94);
    List_Insert(pHead, 3, -4);
    List_Insert(pHead, 4, 4);
    List_Traverse(pHead);
    printf("当前链表的长度是：%d\n\n", List_Length(pHead));
    
    if ( List_Delete(pHead, 3, &pVal) ){
        printf("删除成功！删除的元素是：%d\n\n", pVal);
    }
    List_Traverse(pHead);
    printf("当前链表的长度是：%d\n\n", List_Length(pHead));
    
    if ( List_FindValue(pHead, 33) ){   // 可以当成 bool 来进行判断
        printf("是\n\n");
    }
    else
        printf("否\n\n");
    
    
    List_Sort(pHead);
    List_Traverse(pHead);
    
    return 0;
}

PNODE List_Init(){
    PNODE pHead = (PNODE)malloc(sizeof(NODE));
    
    if ( pHead == NULL ){
        exit(-1);
    }
    PNODE pTail = pHead;
    pTail->pNext = NULL;
    
    int n, i;
    printf("输入要创建的链表长度：");
    scanf("%d", &n);
    for ( i = 0; i < n ; i++ ){
        printf("第 %d 个节点的值：", i +1 );
        int val;
        scanf("%d", &val);
        
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->data = val;
        pTail->pNext = pNew;
        pTail = pNew;
        pTail->pNext = NULL;
    }
    
    return pHead;
}

void List_Traverse(PNODE pHead){
    PNODE q;
    int len, j;
    
    len = List_Length(pHead);
    for ( j = 0, q = pHead->pNext; j < len; j++, q = q->pNext ){
        printf("%d ", q->data);
    }
    printf("\n");
}

int List_Length(PNODE pHead){
    PNODE pNew = pHead->pNext;
    int length = 0;
    
    while ( pNew != NULL ){
        length++;
        pNew = pNew->pNext;
    }
    
    return length;
}

bool List_Insert(PNODE pHead, int pos, int val){
    PNODE q;    // 先不分配，因为可能pos不合法
    
    if ( pos == 1 ){
        q = (PNODE)malloc(sizeof(NODE));
        q->data = val;
        q->pNext = pHead->pNext;
        pHead->pNext = q;
        
        return true;
    }
    
    q = List_FindOrder(pHead, pos - 1); // 找第i-1个，方便后续删除
    if ( !q ){
        printf("结点不存在，插入失败！\n");
        return false;
    }
    else{
        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        pNew->data = val;
        
        pNew->pNext = q->pNext;
        q->pNext = pNew;
        
        return true;
    }
}

bool List_Delete(PNODE pHead, int pos, int * pVal){
    PNODE p;
    
    if ( pos == 1 ){
        p = pHead->pNext;
        *pVal = p->data;    // 保存被删除的数据
        pHead->pNext = p->pNext;
        free(p);
        
        return true;
    }
    
    p = List_FindOrder(pHead, pos - 1);
    if ( !p || !p->pNext ){	    // 第 i-1 个或第 i 个结点不存在
        printf("结点不存在，删除失败！\n");
        return false;
    }
    else{
        PNODE q = p->pNext;
        *pVal = q->data;    // 先保存
        p->pNext = q->pNext;
        free(q);
        
        return true;
    }
}

PNODE List_FindOrder(PNODE pHead, int pos){
    int i = 1;
    PNODE p = pHead->pNext;
    
    while ( i < pos &&  NULL != p ){
        i++;
        p = p->pNext;
    }
    
    if ( i == pos )
        return p;
    else
        return NULL;
    
}

PNODE List_FindValue(PNODE pHead, int val){
    PNODE p = pHead->pNext;
    
    while ( NULL !=  p && p->data != val ){	// p不能为空
        p = p->pNext;
    }
    // 找到了，返回 p
    // 未找到，返回 NULL，此时 p 等于 NULL
    return p;
}

// 冒泡排序
void List_Sort(PNODE pHead){
    int i, j, len = List_Length(pHead);
    PNODE p, q;
    
    
    for ( i = 0, p = pHead->pNext; i < len - 1; i++, p = p->pNext )
        for ( j = 0, q = pHead->pNext; j < len - 1 - i; j++, q = q->pNext )
            if ( q->data > q->pNext->data ){
                int t = q->data;
                q->data = q->pNext->data;
                q->pNext->data = t;
            }
}