链表的常见操作

拼搏现实的明天。 2022-05-27 13:46 145阅读 0赞

###### 这两天一直在看郝斌的数据结构课程，之前上课大多是是理论，但是实际用代码实现还是比较困难，跟着郝斌老师重新温习了一遍链表的课程，受益匪浅，虽然郝斌老师实现所用代码和教材上的代码稍有区别，但是大致思想相同，而且有的部分感觉郝斌老师的方法更加优秀，所以对他上课时代码进行了重现，完成了链表的常见操作，具体代码如下： ######

#include <stdio.h>
    #include <stdlib.h>
    typedef struct Node{
        int data;
        struct Node* pNext;
    } Node,*PNode;
    PNode create_list(void);//创建链表
    void traverse_list(PNode);//遍历链表
    void is_empty(PNode);//判断链表是否为空
    int length_list(PNode);//判断链表的长度
    void insert_list(PNode,int,int*);//插入节点
    void delete_list(PNode,int,int*);//删除节点
    void sort_list(PNode);//对链表进行排序
    
    int main() {
        PNode pHead = NULL;
        int val;
        int pos;
        pHead = create_list();
        traverse_list(pHead);
        int len = length_list(pHead);
        printf("链表的长度为%d\n",len);
        printf("请输入要插入的位置以及数值:\n");
        scanf("%d %d",&pos,&val);
        insert_list(pHead, pos, &val);
        traverse_list(pHead);
        printf("请输入要删除的位置!\n");
        scanf("%d",&pos);
        delete_list(pHead, pos, &val);
        traverse_list(pHead);
        sort_list(pHead);
        printf("排序后的链表数据如下:");
        traverse_list(pHead);
        return 0;
    }
    
    PNode create_list(void){
        int len;
        int i;
        int val;
    
        PNode pHead = (PNode)malloc(sizeof(Node));
        if(pHead == NULL){
            printf("分配内存失败!\n");
            exit(-1);
        }
        PNode pTail = pHead;//这里是创建一个指向尾节点的变量
        pTail->pNext = NULL;
    
        printf("请输入要生成的链表的节点数:\n");
        scanf("%d",&len);
    
        for(i=0;i<len;i++){
            printf("请输入第%d个节点的值:\n",i+1);
            scanf("%d",&val);
    
            PNode pNew = (PNode)malloc(sizeof(Node));
            if(pNew == NULL){
                printf("分配内存失败!\n");
            }
            pNew->data = val;
            pTail->pNext = pNew;
            pNew->pNext = NULL;
            pTail = pNew;
        }
        return pHead;
    
    }
    
    void traverse_list(PNode pHead){
        PNode p = pHead->pNext;
        printf("链表中的数据为:");
        while (p != NULL) {
            printf("%d ",p->data);
            p = p->pNext;
        }
        printf("\n");
        return;
    }
    
    void is_empty(PNode pHead){
        if(pHead->pNext == NULL){
            printf("该链表为空!\n");
            return;
        }else{
            printf("该链表不为空!\n");
            return;
        }
    }
    
    int length_list(PNode pHead){
        PNode p = pHead->pNext;
        int len = 0;
        while (p != NULL) {
            p = p->pNext;
            len++;
        }
        return len;
    }
    
    void insert_list(PNode pHead,int pos,int* val){
        PNode p = pHead;
        int i = 0;
        while (p != NULL && i<pos-1) {
       //使指针最后指向需要插入的节点的前一个节点
            p = p->pNext;
            i++;
        }
        if(i>pos-1 || p==NULL){
       //当该节点为空，则说明该节点为尾节点的下一个节点，即输入不合法
            printf("输入不正确!\n");
        }else{
            PNode pNew = (PNode)malloc(sizeof(Node));
            if(pNew == NULL){
                printf("动态分配内存失败!\n");
                exit(-1);
            }else{
                pNew->data = *val;
                pNew-> pNext = p->pNext;
                p->pNext = pNew;
            }
        }
        return;
    }
    
    void delete_list(PNode pHead,int pos,int* val){
        PNode p = pHead;
        int i = 0;
        while (p->pNext != NULL && i<pos-1) {
            p = p->pNext;
            i++;
        }
        if (i>pos-1 || p->pNext == NULL){
            printf("输入不正确!\n");
            exit(-1);
        }else{
            PNode q = p->pNext;
            *val = p->pNext->data;
            p->pNext = p->pNext->pNext;
            free(q);
            q = NULL;//将q中的野指针赋值为空
            printf("删除成功，删除的节点值为%d",*val);
        }
        return;       
    }
    
    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)
        {
            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;
    }

###### 注：在这个代码的插入以及删除时使用的while以及if判断语句极为巧妙，使得不合法输入都可避免，简化了代码还提高了代码的健壮性，我思考了很久才大致理解了其思路，这个后期复习时需要重点的温习一下。 ######