单链表

涉及到链表的 创建、遍历、求长度、插入、删除、查找、排序。

零碎知识点

• typedef

typedef struct Student
{
    int sid;
    char name[100];
    char sex;
}* PSTU, STU;        
//PSTU等价于struct Student *, STU等价于struct Student

int main(void)
{
    STU st;        //struct Student st;
    PSTU ps = &st;    //struct Student* ps = &st;
    ps->sid = 99;
    printf("%d", ps->sid);
    
    return 0;
}

• 确定一个链表所需要的参数
  头指针

• 每一个链表节点的数据类型该如何表示的问题

typedef struct Node      //节点————每一个节点分为两部分，数据域和指针域
{
    int data;    //数据域
    struct Node * pNext;      //指针域————指向的是一个跟它本身数据类型一致、但是是另外一个节点
}NODE, *PNODE;    //NODE 等价于struct Node，PNODE等价于struct Node *

• 插入节点

1.  r = p->pNext; p->pNext = q;  q->pNext = r;
//q->pNext表示的是q指向的那个结构体变量中的pNext成员
2.  q->pNext = p->pNext;  p->pNext = q;

• 删除节点

r = p->pNext;
p->pNext = p->pNext->pNext;
free(r);

程序

/**
 * @version:  
 * @author: @Shiel
 * @date: 2023-10-04 11:13:05
 **/

// 不懂就画图！！！！

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef struct Node
{
    int data;   //数据域
    struct Node * pNext;    //指针域
}NODE, *PNODE;  //NODE等价于struct Node    PNODE等价于struct Node *

PNODE Create_List(void);    //创建链表
void Traverse_List(PNODE pHead);    //遍历链表
bool Is_Empty(PNODE pHead);         //判断链表是否为空
int Length_List(PNODE pHead);       //求链表长度
bool Insert_List(PNODE pHead, int pos, int val);    //在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始
bool Delete_List(PNODE pHead, int pos, int * pVal); //删除链表第pos个节点，并将删除的结点的值存入pVal所指向的变量中,  并且pos的值是从1开始
void Sort_List(PNODE);          //选择排序
void Sort_List_Bubble(PNODE);   //冒泡排序

int main(void)
{
    int val;
    PNODE pHead = NULL;     //等价于 struct Node * pHead = NULL;
    
    pHead = Create_List();  //函数功能：创建一个非循环单链表，并将该链表头节点的地址赋给null
    Traverse_List(pHead);
    
//  Insert_List(pHead, 4, 88);
//  Insert_List(pHead, 5, 55);
    
    if( Delete_List(pHead, 4, &val) )
    {
        printf("删除成功， 删除的元素为：%d\n", val);
    }
    else
        printf("删除失败\n");


    
//  if( Is_Empty(pHead) )
//  {
//      printf("链表为空！\n");
//  }
//  else
//      printf("链表不为空！\n");
    
//  int len = Length_List(pHead);
//  printf("链表的长度是%d\n", len);
    
//  Sort_List(pHead);
//  Traverse_List(pHead);
    
    Sort_List_Bubble(pHead);
    Traverse_List(pHead);
    
    
    /*
    释放链表内存空间:
      首先，从链表的第一个节点开始，依次释放每个节点的内存空间。然后释放头节点的内存空间。这样就确保了整个链表的内存空间都被释放。
      需要注意的是，释放节点内存空间时，应先保存下一个节点的指针，然后再释放当前节点的内存空间。
     */
    PNODE p = pHead->pNext;
    while (p != NULL) {
        PNODE temp = p;
        p = p->pNext;
        free(temp);
    }
    free(pHead);
    
    return 0;
}


PNODE Create_List(void)
{
    int len;    //用来存放有效节点的个数
    int val;    //用来临时存放用户输入的结点的值
    
    //分配了一个不存放有效数据的头节点
    PNODE pHead = (PNODE)malloc(sizeof(NODE));  //返回的是节点本身的数据类型，所以是NODE，不是PNODE
    if(NULL == pHead)
    {
        printf("内存分配失败！\n");
        exit(-1);
    }
    PNODE pTail = pHead;    //定义一个时刻指向尾节点的变量
    pTail->pNext = NULL;    //如果只输入一个数据时满足此情况
    
    printf("请输入需要生成的链表节点个数：len = ");
    scanf("%d", &len);
    
    for(int i=0;i<len;i++)
    {
        printf("请输入第%d个节点的值：", i+1); 
        scanf("%d", &val);
        
        PNODE pNew = (PNODE)malloc(sizeof(Node));   //临时节点
        if(NULL == pNew)
        {
            printf("内存分配失败！\n");
            exit(-1);
        }
        pNew->data = val;       //临时节点存放临时变量
        pTail->pNext = pNew;    //把新的节点挂到尾节点后
        pNew->pNext = NULL;     //新节点的下一个节点就为空了
        pTail = pNew;           //更新尾节点
        
    /*  错误：每个节点都挂在了头结点之后！
        pNew->data = val;
        pHead->pNext = pNew;
        pNew->pNext = NULL;
     */
    }
    
    return pHead;
}

void Traverse_List(PNODE pHead)
{
    PNODE p = pHead->pNext;     //p可能为空
    
    while(NULL != p)
    {
        printf("%d ", p->data);
        p = p->pNext;
    }
    printf("\n");
    
    return;     //表示函数执行完成
}

bool Is_Empty(PNODE pHead)
{
    if(pHead->pNext == NULL)
    {
        return true;
    }
    else
        return false;
}

int Length_List(PNODE pHead)
{
    PNODE p = pHead->pNext;
    int len = 0;
    
    while(p != NULL)
    {
        len++;
        p = p->pNext;
    }
    return len;
}

//提到了C++重载、泛型
void Sort_List(PNODE pHead)
{
    int i, j, t;
    int len = Length_List(pHead);
    PNODE p, q;
    for(i=0, p=pHead->pNext;i<len-1;i++, p=p->pNext)    //i=0：第一个元素的下标；p=pHead->pNext：第一个有效元素的地址
    {
        for(j=i+1, q=p->pNext;j<len;j++, q=q->pNext)
        {
            if(p->data > q->data)       //类似于数组中的：a[i] > a[j]
            {
                t = p->data;            //类似于数组中的：t = a[i];
                p->data = q->data;      //类似于数组中的：a[i] = a[j];
                q->data = t;            //类似于数组中的：a[j] = t;
            }
        }
    }
    return;
}

void Sort_List_Bubble(PNODE pHead)
{
    int i, j, t;
    int len = Length_List(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)
            {
                t = q->data;
                q->data = q->pNext->data;
                q->pNext->data = t;
            }
        }
    }
}

//在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始
bool Insert_List(PNODE pHead, int pos, int val)
{
    int i = 0;
    PNODE p = pHead;
    
    while( NULL!=p && i<pos-1)
    {
        p = p->pNext; 
        i++;
    }
    
    if(i>pos-1 || NULL==p)
    {
        return false;
    }
    
    //如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓
    //分配新的结点
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if(NULL == pNew)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    pNew->data = val;
    
    //将新的结点存入p节点的后面
    PNODE q = p->pNext;
    p->pNext = pNew;
    pNew->pNext = q;
    
    return true;
}

//健壮性非常好
bool Delete_List(PNODE pHead, int pos, int * pVal)
{
    int i = 0;
    PNODE p = pHead;
    
    while( NULL!=p && i<pos-1)
    {
        p = p->pNext;
        i++;
    }
    
    if(i>pos-1 || NULL==p->pNext)
    {
        return false;
    }
    
    //如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的
    PNODE q = p->pNext;
    *pVal = q->data;
    
    //删除p后面的结点
    p->pNext = p->pNext->pNext;
    free(q);        //删除p后面的结点
    q = NULL;
    return true;
}