[郝斌]数据结构C语句—链表

2023-11-03 16:28:04

链表是线性结构的离散存储方式。

定义：n个节点离散分配，彼此通过指针相连，每个节点只有一个前驱节点，每个节点只有一个后续节点，首节点没有前驱节点，尾节点没有后续节点。

专业术语：

  1. 首节点（第一个有效节点，首节点的数据类型和头节点是一样的）

  2. 尾节点（最后一个有效节点）

  3. 头节点（在首节点之前，不存储有效数据、目的是为了方便对链表进行操作）、

  4. 头指针（指向头节点的指针变量）

  5. 尾指针（指向尾节点的指针变量）

只需要一个参数，头指针，通过头指针可以推算出链表的所有信息，就可以通过这一个参数使用函数对链表进行操作。

链表节点定义的方式，链表结构体中包含的指针域类型和节点类型相同，指向一个链表节点的整体。

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

分类：

单链表，双链表（每一个节点有两个指针域）

循环链表（能通过任何一个节点找到其他所有的节点），非循环链表

下面进行算法实现：遍历，查找，清空，销毁，求长度，排序，删除节点，插入节点。

p->pNext 表示p所指向结构体变量中的pNext成员变量。

/*在指针p指向的链表节点后面插入指针q指向的链表节点的两种方式*/
//方法1
    r = p -> pNext;
    p -> pNext = q;
    q -> pNext = r;
//方法2
    q -> pNext = p -> pNext;
    p -> pNext = q;

删除指针p指向的链表节点之后的下一个链表节点，也就是把指针p指向的链表节点中的指针域指向下下一个节点，但是注意删除的节点要及时释放，否则会导致内存泄漏，C语言不会自动释放。。

//错误的写法
    p -> pNext = p -> pNext -> pNext;
//错误的写法，释放了p指针指向的链表节点的下一个节点之后，下下一个节点同样找不到了。
    free(p->pNext);
//正确的写法，先将需要释放的节点保存一下，删除操作之后再释放。
    r = p->pNext;
    p -> pNext = r->pNext;
    free (r);

我们对链表进行相应功能函数的实现：

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

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

PNODE create_list(void);
void show_list(PNODE phead);
bool is_emptylist(PNODE phead);
int length_list(PNODE phead);//节点个数统计
bool append_list(PNODE phead, int val);//追加
bool insert_list(PNODE phead, int val, int port);//插入
bool delete_list(PNODE phead, int* returnVal, int port);
void sort_list(PNODE phead, bool mode);

int main(void)
{
    PNODE pNode = NULL;
    int lengNum = 0;
//    int returnNum =0; 
/*关于指针的使用，直接初始化一个int值而不是int *去接受被删除的值 。*/
    pNode = create_list();
    show_list(pNode);
    if( is_emptylist(pNode) )
    {
        printf("链表为空！\n");
    }
    else
    {
        printf("链表不为空！\n");
        lengNum = length_list(pNode);
        printf("the Number of the link is %d \n", lengNum);
    }
/*
    if(insert_list(pNode, 88, 3))
    {
        printf("插入成功！\n");
    }
    else
    {
        printf("插入失败！\n");
    }
    */
    //delete_list(pNode, &returnNum, 3);
    sort_list(pNode, 0);
    show_list (pNode);
    sort_list(pNode, 1);
    show_list (pNode);
    //printf("the delete number is %d \n", returnNum);

//    append_list(pNode, 7);

    return 0;
}

PNODE create_list(void)
{
    int nodeNum = 0;
    int fornum = 0;
    int val = 0;
    /*   pNew 每次循环分配空间作为新的链表节点*/
    /*   pTail 一直指向链表的最后一个节点，初始化时pTail的指针域赋NULL*/
    PNODE phead = (PNODE)malloc(sizeof(NODE));
    if(phead == NULL)
    {
        printf("链表头申请失败! \n");
        return 0;
    }

    PNODE pTail = phead;
    pTail ->pNext = NULL;

    printf("please enter the number of Node: ");
    scanf(" %d", &nodeNum);

    for(fornum = 1; fornum <= nodeNum; fornum++)
    {
        printf("please enter the data of this node %d :", fornum);
        scanf(" %d", &val);

        PNODE pNew = (PNODE)malloc(sizeof(NODE));
        if(pNew == NULL)
        {
            printf("新链表节点申请失败! \n");
            return 0;
        }
        pTail ->pNext = pNew;
        pNew ->data = val;
        pNew ->pNext = NULL;

        pTail = pNew;
    }

    return phead;
}

void show_list(PNODE phead)
{
    PNODE pShow = phead ->pNext;
    int nodenum = 1;
    while(pShow != NULL)
    {
        printf("The data of Node %d is: %d \n", nodenum, pShow->data);
        pShow = pShow ->pNext;
        nodenum ++;
    }
    printf("\n");
}

bool is_emptylist(PNODE phead)
{
    PNODE pShow = phead ->pNext;
    if(pShow == NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

int length_list(PNODE phead)
{
    PNODE pShow = phead ->pNext;
    int lengthNum = 0;
    while(pShow != NULL)
    {
        lengthNum ++;
        pShow= pShow->pNext;
    }
    return lengthNum;
}

bool insert_list(PNODE phead, int val, int port)
{
    /*插入操作要考虑插入到第一个节点之前的情况，一开始要指向头节点*/
    PNODE pShow = phead;
    #if 0
    int nodeNum = 0;
    int i = 0;
    if(is_emptylist(phead))
    {
        printf("链表为空！\n");
        return false;
    }
    nodeNum = length_list(phead);
    if(nodeNum < port-1)
    {
        printf("参数错误！\n");
        return false;
    }
    while(i < port-1 )
    {
        pShow = pShow->pNext;
        i ++;
    }

    PNODE pNew = (PNODE)malloc(sizeof(NODE));

    pNew ->pNext = pShow ->pNext;
    pShow ->pNext = pNew;
    pNew ->data = val;
    #endif // 0

    #if 1
    /*******郝斌版本
     *这种方式是不需要判断列表为空，也不需要求出列表长度
     ******/
    PNODE pSwap = NULL;
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
     int j = 0;

     while ((pShow != NULL) && (j < port -1))
     {
         pShow = pShow->pNext;
         j++;
     }
     if(j > port -1|| pShow==NULL)
     {
         return false;
     }

     pSwap = pShow ->pNext;
     pShow ->pNext = pNew;
     pNew -> pNext = pSwap;
     pNew ->data = val;
    #endif // 1

    return true;
}

bool append_list(PNODE phead, int val)
{
    PNODE pShow = phead;
    PNODE pTail = NULL;
    PNODE pNew = (PNODE)malloc(sizeof(NODE));
    if (pNew == NULL)
    {
        printf("append_list 新节点申请失败！\n");
        return false;
    }

    while (pShow != NULL)
    {
        pTail = pShow;
        pShow = pShow ->pNext;
    }

    pTail ->pNext = pNew;
    pNew->data = val;
    pNew->pNext = NULL;

    return true;
}

bool delete_list(PNODE phead, int *returnVal, int port)
{
    PNODE pShow = phead ->pNext;
    int fornum = 1;
    PNODE pDeleteNode = NULL;

    while( (pShow != NULL) &&(fornum < port-1 ) )
    {
        pShow = pShow->pNext;
        fornum ++;
    }

    if ((fornum > port - 1) || (pShow->pNext == NULL)) /*将指针指向将要删除的节点的前一个节点，判断目标节点pShow->pNext是不是空节点*/
    {
        return false;
    }

    pDeleteNode = pShow->pNext;
    *returnVal = pDeleteNode ->data;

    pShow ->pNext = pDeleteNode ->pNext;
    free(pDeleteNode);
    pDeleteNode = NULL;
    return true;

}
void sort_list(PNODE phead, bool mode)
{
    int nodeNum = length_list(phead);

    int i = 0;
    int j = 0;
    int swapNum = 0;
    PNODE pnode = NULL;
    PNODE qnode = NULL;

    if(mode == 0)/* 从小到大排列 */
    {
        for(i = 0, pnode = phead ->pNext; i < nodeNum - 1; i++, pnode = pnode ->pNext)
        {
            for(j = i + 1, qnode = pnode ->pNext; j < nodeNum; j++, qnode = qnode ->pNext)
            {
                if((pnode->data) > (qnode ->data))
                {
                    swapNum = pnode->data;
                    pnode ->data = qnode ->data;
                    qnode ->data = swapNum;
                }
            }
        }
    }
    else if(mode == 1) /*从大到小排列*/
    {
         for(i = 0, pnode = phead ->pNext; i < nodeNum - 1; i++, pnode = pnode ->pNext)
        {
            for(j = i + 1, qnode = pnode ->pNext; j < nodeNum; j++, qnode = qnode ->pNext)
            {
                if((pnode->data) < (qnode ->data))
                {
                    swapNum = pnode->data;
                    pnode ->data = qnode ->data;
                    qnode ->data = swapNum;
                }
            }
        }
    }
    return;
}

注意排序函数中使用了逗号运算符，其作用是将若干表达式连接起来。它的优先级是所有运算符中最低的，结合方向是自左至右。 逗号表达式： 一般形式：表达式1，表达式2，表达式3，......表达式n ​ 求解过程：先计算表达式1的值，再计算表达式2的值，......一直计算到表达式n的值。最后整个表达式的值是表达式n的值。

在for循环中使用逗号表达式注意第二个条件，循环执行判断条件中慎用逗号运算符，表达式顺序的不同会导致不同的判定结果。

上一篇：【数据结构-C】双向循环链表基本操作及图解分析


下一篇：基础数据结构-单链表（不带头结点）