11-数据结构_链表相关操作

深藏阁楼爱情的钟 2021-12-12 21:31 251阅读 0赞

// 动态创建非循环单链表, 并返回头指针  
PNODE createList(void);  
// 遍历链表  
void traverseList(PNODE pHead);  
// 是否为空  
bool isEmpty(PNODE pHead);  
// 链表长度  
int listSize(PNODE pHead);  
// 插入一个元素, pos-位置(首结点为索引为1), value-插入结点的值  
bool insert(PNODE pHead, int pos, int value);  
// 删除一个元素, pValue-删除节点的数据域  
bool delete(PNODE pHead, int pos, int \* pValue);  
// 排序, 冒泡 升序,  
void sort(PNODE pHead);  
// 排序, 快排 降序,

void sort\_2(PNODE pHead);

完整程序

05-node.c

#include <stdio.h>  // print / scanf
    #include <malloc.h> // malloc
    #include <stdlib.h> // exit
    #include <stdbool.h>// bool
    
    typedef struct Node
    {
        int data;   // 数据域
        struct Node * pNext; // 指针域
    } NODE, * PNODE; 
    // NODE <==> struct Node, PNODE<==>struct Node *
    
    // 动态创建非循环单链表, 并返回头指针
    PNODE createList(void);
    // 遍历链表
    void traverseList(PNODE pHead);
    // 是否为空
    bool isEmpty(PNODE pHead);
    // 链表长度
    int listSize(PNODE pHead);
    // 插入一个元素, pos-位置(首结点为索引为1), value-插入结点的值 
    bool insert(PNODE pHead, int pos, int value);
    // 删除一个元素, pValue-删除节点的数据域
    bool delete(PNODE pHead, int pos, int * pValue);
    // 排序, 冒泡 升序, 
    void sort(PNODE pHead);
    // 排序, 快排 降序, 
    void sort_2(PNODE pHead);
    
    int main(void)
    {
        PNODE pHead = NULL; // <==> struct Node * pHead;
    
        // 创建一个非循环单链表
        pHead = createList();
        
        // 是否为空链表
        if (isEmpty(pHead))
        {
            printf("链表为空? YES\n");
        }
        else 
        {
            printf("链表为空? NO\n");
        }
        
    
        // 链表的长度
        printf("链表的长度? %d\n", listSize(pHead));
    
        // 遍历链表
        traverseList(pHead);     
        
        // 插入
    /*
        int pos, value;
        printf("请输入插入的位置和值\n");
        printf("pos = ");
        scanf("%d", &pos);
        printf("value = ");
        scanf("%d", &value);
    
        insert(pHead, pos, value);
        traverseList(pHead);
    */
        // 删除
    /**/
        int pos, value;
        printf("请输入删除结点的位置\n");
        printf("pos = ");
        scanf("%d", &pos);
    
        delete(pHead, pos, &value);
        printf("删除结点的值 value = %d\n", value);
    
        traverseList(pHead);
    
    
        // 排序- 升序
        sort(pHead);
    
        // 排序- 降序
        sort_2(pHead);
    
        traverseList(pHead);
    
        return 0;
    }
    
    PNODE createList(void)
    {
        int length; // 链表长度, 即结点个数
        printf("结点个数 length = ");
        scanf("%d", &length);
    
        // 头指针.
        PNODE pHead = (PNODE) malloc( sizeof(NODE) );
        if ( NULL == pHead)
        {
            printf("动态内存分配失败!!");
            exit(-1);
        }    
    
        // 尾指针
        PNODE pTail = pHead;
        pTail->pNext = NULL;
    
        // 给结点赋值
        int i;
        int value;  // 数据域 临时变量
        for (i = 0; i < length; ++i)
        {
            printf("请输入第 %2d 个结点的值: ", i+1);
            scanf("%d", &value);
    
            PNODE pNewNode = (PNODE) malloc(sizeof(NODE));  // 新结点分配内存
            pNewNode->data = value; // 给新结点赋值
            // 将新结点 挂到末尾
            pTail->pNext = pNewNode;    
            pNewNode->pNext = NULL; // 尾结点 指针域为空
    
            pTail = pNewNode;   // 新添加的结点 作为 尾结点.
    
        }
    
        return pHead;
    }
    
    void traverseList(PNODE pHead)
    {   
        PNODE pNode = pHead->pNext; // 指向首结点
        printf("遍历: ");
        while (NULL != pNode)
        {
            printf("%3d", pNode->data);
            pNode = pNode->pNext;   // 移向下一个结点
        }
    
        printf("\n");
        return;
    }
    
    bool isEmpty(PNODE pHead)
    {
        if ( NULL == pHead || NULL == pHead->pNext)
        {
            return true;
        }
        return false;
    }
    
    int listSize(PNODE pHead)
    {
        int count = 0;  // 计数器,
    
        PNODE pNode = pHead->pNext; // 指向首结点
    
        while (NULL != pNode)
        {
            ++count;
            pNode = pNode->pNext;
        }
        
        return count;
    }
    
    bool insert(PNODE pHead, int pos, int value)
    {
        if (pos < 1 || pos > listSize(pHead))
        {
            printf("非法位置, 0 < pos < %d \n", listSize(pHead)+1);
            return false;
        }
        
        // 定位到指定位置结点 的 前一个节点
        PNODE pNode = pHead; // 指向头结点, 索引为0
        int count = 0;
        while (count < pos - 1)
        {
            pNode = pNode->pNext;
            ++count;
        }
    
        // 新建结点
        PNODE pNew = (PNODE) malloc( sizeof(NODE) );
        pNew->data = value;
    
        // 插入
        pNew->pNext = pNode->pNext;
        pNode->pNext = pNew;
    
        return true;
    }
    
    bool delete(PNODE pHead, int pos, int * pValue)
    {
        if (pos < 1 || pos > listSize(pHead))
        {
            printf("非法位置, 0 < pos < %d \n", listSize(pHead)+1);
            return false;
        }
    
        int count = 0; // 计算器
        PNODE pNode = pHead; // 指向头结点
    
        // 定位到 指定位置结点 的前一个结点
        for (; count < pos - 1; ++count)
        {
            pNode = pNode->pNext;
        }
    
        // 删除 该结点
        PNODE pTemp = pNode->pNext; // pTemp指向的结点为要删除的节点
        pNode->pNext = pTemp->pNext;
    
        // 返回 删除的结点的值
        *pValue = pTemp->data;
    
        // 释放内存
        free(pTemp); 
    
        return true;
    }
    
    void sort(PNODE pHead)
    {
        int i, j;
        int length = listSize(pHead);
        int temp;
        PNODE pNode = NULL;
    
        for (i = 0; i < length - 1; ++i)
        {
            pNode = pHead->pNext;   // 指向首结点
            for (j = 0; j < length - 1 - i; ++j)
            {
                if (pNode->data > pNode->pNext->data)
                {
                    temp = pNode->data;
                    pNode->data = pNode->pNext->data;
                    pNode->pNext->data = temp;
                }
                pNode = pNode->pNext;   
            }
        }
    
        return;
    }
    
    void sort_2(PNODE pHead)
    {
        int i, j;
        int length = listSize(pHead);
        int temp;
        PNODE pLeft, pRight;
    
        pLeft = pHead;
    
        for (i =0; i < length -1; ++i)
        {
            pLeft = pLeft->pNext;
            pRight = pLeft->pNext;
    
            for (j = i + 1; j < length; ++j)
            {
                if (pLeft->data < pRight->data)
                {
                    temp = pLeft->data;
                    pLeft->data = pRight->data;
                    pRight->data =temp;
                }
                pRight = pRight->pNext;
            }
        }
    
        return;
    }