数据结构 链表笔记

/*
    数据结构 链表的实现即操作 
*/

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

// 单向链表
typedef struct list
{
    int data;  // 链表数据域
    struct list * pNext; 
}None, * pNone;

// 链表的创建 
pNone Create_List();
// 链表的遍历 
void Travel_List(pNone);
// 判断链表是否为空
bool Is_Empty(pNone); 
// 计算链表长度
int Length_List(pNone);
// 链表节点的插入, 形参为链表头地址 在哪个位置前插入 插入的节点的值 
void Insert_List(pNone, int, int);
// 链表节点的删除，形参为链表头地址，需要删除的节点的位置
void Delete_List(pNone, int);
// 链表的排序
void Seq_List(pNone); 
// 链表的销毁
void Destroy_List(pNone); 

int main(void)
{
    pNone pHead = Create_List();
    Travel_List(pHead);
    
    int pos, val;
    printf("请输入需要插入的位置及该的数据！\n");
    scanf("%d %d", &pos, &val);
    Insert_List(pHead, pos, val);
    Travel_List(pHead);
    
    printf("请输入需要删除的位置！\n");
    scanf("%d %d", &pos);
    Delete_List(pHead, pos);
    Travel_List(pHead);
    
    Destroy_List(pHead);
    
    return 0;
}

pNone Create_List(void)
{
    int len;
    printf("请输入您需要的链表长度：");
    scanf("%d", &len);
    pNone pHead = (pNone)malloc(sizeof(None));
    if (NULL == pHead)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    pHead->pNext = NULL;
    pNone pNew, pTemp;
    pNew = pHead;
    for (int i = 0; i < len; ++i)
    {
        pTemp = (pNone)malloc(sizeof(None));
        if (NULL == pTemp)
        {
            printf("动态内存分配失败！\n");
            exit(-1);
        }
        pTemp->pNext = NULL;
        pNew->pNext = pTemp;
        printf("请输入此节点储存的数据：");
        scanf("%d", &pTemp->data);
        printf("\n"); 
        pNew = pNew->pNext;
    }
    
    return pHead; 
}

void Travel_List(pNone pHead)
{
    pNone pTemp;
    while (pHead->pNext != NULL)
    {
        pTemp = pHead->pNext;
        printf("%-5d\n", pTemp->data);
        pHead = pHead->pNext;
    }
    
    return;
}

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

int Length_List(pNone pHead)
{
    int cnt = 0;  // 记录链表长度
    while (NULL != pHead->pNext)
    {
        ++cnt;
        pHead = pHead->pNext;
    }
    
    return cnt;
}

void Insert_List(pNone pHead, int pos, int val)
{
    // 首先要判定被插入的位置是否存在
    pNone pTemp = pHead;
    int i = 0;
    // 说明：此循环结束后pTemp记录的是第pos-1个节点的地址 
    while (NULL != pTemp && i < pos-1)
    {
        pTemp = pTemp->pNext;
        ++i;
    } 
    if (NULL == pTemp || i > pos-1)
    {
        printf("插入失败！\n");
        exit(-1); 
    }
    pNone pNew;
    pNew = (pNone)malloc(sizeof(None));
    if (NULL == pNew)
    {
        printf("动态内存分配失败！\n");
        exit(-1);
    }
    pNew->data = val;
    pNew->pNext = pTemp->pNext;
    pTemp->pNext = pNew;
    
    return;
}

void Delete_List(pNone pHead, int pos)
{
    pNone pTemp = pHead;
    int i = 0;
    while (NULL != pTemp && i < pos-1)
    {
        pTemp = pTemp->pNext;
        ++i;
    }
    if (NULL == pTemp || i > pos-1)
    {
        printf("删除失败！\n");
        exit(-1);
    }
    pNone pTemp1 = pTemp->pNext;
    int val = pTemp1->data;
    pTemp->pNext = pTemp1->pNext; 
    printf("被删除的节点数据为：%d\n", val); 
    
    return;
}

void Seq_List(pNone pHead)
{
    pNone pTemp, pTemp1, pTemp2, pTemp3, pMax, pMax1, pMax2;
    pTemp = pHead;  // 表示要开始用来比较的原节点的前一个节点地址 
    pTemp1 = pTemp->pNext;  // 表示开始用来比较的原节点的地址 
    while (NULL != pTemp1->pNext)
    {
        pMax1 = pTemp;  // 追踪最大值前面的节点  
        pMax = pTemp1;  // 用来追踪最大值的节点 
        pTemp2 = pMax;  // 用于追踪被比较点前一个点的地址 
        pTemp3 = pMax->pNext;  // 用于追踪被比较点 
        while (NULL != pTemp2->pNext)
        {
            if (pMax->amount < pTemp3->amount)
            {
                pMax1 = pTemp2; 
                pMax = pTemp3;
            }
            pTemp2 = pTemp2->pNext;
            if (NULL != pTemp2->pNext)
                pTemp3 = pTemp2->pNext;
        }
        pMax1->pNext = pMax->pNext; 
        pMax->pNext = pTemp1;
        pTemp->pNext = pMax;
        pTemp = pMax;
        pTemp1 = pTemp->pNext;        
    }
    
    return;
}

void Destroy_List(pNone pHead)
{
    pNone pTemp;
    while (pHead != NULL)
    {
        pTemp = pHead->pNext;
        free(pHead);
        pHead = pTemp;    
    }
    
    return;
}