首页 > 其他分享 >链表

链表

时间：2024-09-13 11:14:32浏览次数：12  
标签：Node list next 链表 printf NULL

1、创建链表-无头结点

#include<stdio.h>
#include<malloc.h>
#include<assert.h>
typedef int ElemType;

//定义链表 
typedef struct ListNode{
    ElemType data;
    struct ListNode* next;
}ListNode;

typedef ListNode* PList; 

//初始化链表，让链表一开始指向为空 
void initList(PList* head){//此处相当于ListNode** plist [二级指针存储一级指针的地址] 
    *head = NULL;
}
 
//创建链表 尾插法[无虚拟头结点] 
void createListByPushBack(PList* head){
    *head = (ListNode*)malloc(sizeof(ListNode));
//    if(*head == NULL){
//        printf("内存空间不足.\n");
//        return;
//    }
    assert(*head != NULL);
    //处理第一个结点
    (*head)->data = 1;
    (*head)->next = NULL;
    
    ListNode* temp = *head; 
    int i = 2;
    for(i;i <= 3;i++){
        ListNode *p = (ListNode*)malloc(sizeof(ListNode));
        assert(p != NULL);
        p->data = i;
        p->next = NULL;
        
        temp->next = p;
        temp = p;
    }
}

//创建链表 头插法[无虚拟头结点]
void createListByPushFront(PList* head){
    *head = (ListNode*)malloc(sizeof(ListNode));
    assert(*head != NULL);
    //处理第一个结点
    (*head)->data = 1;
    (*head)->next = NULL;
    

    int i = 2;
    for(i;i <= 3;i++){
        ListNode *p = (ListNode*)malloc(sizeof(ListNode));
        assert(p != NULL);
        p->data = i;
        p->next = *head;
        
        *head = p;
    }
}


//打印链表
void showList(ListNode* list){
    while(list != NULL){
        printf("%d ",list->data);
        list = list->next;
    }
} 
int main(){
    PList myList;
    initList(&myList);
    createListByPushFront(&myList);
    showList(myList);
//    printf("\n%d",myList->data);
    return 0;
}

 

2、创建链表-有头结点

//初始化链表，让链表一开始指向为空 
void initList(PList* head){//此处相当于ListNode** plist [二级指针存储一级指针的地址] 
    *head = (ListNode*)malloc(sizeof(ListNode));//创建虚拟头结点，该节点不储存数据 
    assert(*head != NULL);
    (*head)->next = NULL;
}
 
//创建链表 尾插法[有虚拟头结点] 
void createListByPushBack(PList* head){
    ListNode* p = *head;
    int i = 1;
    for(i;i <= 3;i++){
        p = p->next  = (ListNode*)malloc(sizeof(ListNode));
        assert(p != NULL);
        p->data = i;
        p->next = NULL;    
    }
}

//创建链表 头插法[无虚拟头结点]
void createListByPushFront(PList* head){
    ListNode* temp = *head;
    int i = 1;
    for(i;i <= 10;i++){
        ListNode *p = (ListNode*)malloc(sizeof(ListNode));
        assert(p != NULL);
        p->data = i;
        p->next = temp->next;
        temp->next = p;
    }
}


//展示链表
void showList(ListNode* list){
    ListNode* temp = list->next; 
    while(temp != NULL){
        printf("%d--> ",temp->data);
        temp = temp->next;
    }
}

 

3、单链表

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

typedef int ElemType;

//单链表节点定义 
typedef struct Node{
    ElemType data;
    struct Node* next;
}Node,*PNode;

//单链表定义 
typedef struct SingleList{
    PNode first;
    PNode last;
    int size;
}List;

//初始化单链表 
void initList(List* list){
    Node* node = (Node*)malloc(sizeof(Node));
    node->next = NULL;//此处最好是置为空 
    list->first = list->last = node;;
    list->size = 0;
}

//尾插法[带有虚拟头结点]
void push_back(List* list,ElemType data){
    Node* pNode = (Node*)malloc(sizeof(Node));
    assert(pNode != NULL);
    pNode->data = data;
    pNode->next = NULL;

    list->last->next = pNode;
    list->last = pNode;
    list->size++; 
}
//头插法[带有虚拟头结点]
void push_front(List* list,ElemType data){
    Node* pNode = (Node*)malloc(sizeof(Node));
    assert(pNode != NULL);
    pNode->data = data;

    //指向第一个节点 
    pNode->next = list->first->next;
    list->first->next = pNode;
    list->size++; 
} 

//打印链表数据
void show_list(List* list){
    PNode p = list->first->next;
    while(p != NULL){
        printf("%d",p->data);
        if(p->next != NULL){
            printf("->");
        }
        p = p->next;
    }
} 

//尾部删除
void pop_back(List* list){
    if(list->size == 0){
        printf("链表长度为0，不可进行删除操作.\n");
        return; 
    }
    PNode p = list->first;
    //p指向最后一个节点的上一个节点 
    while(p->next != list->last){
        p = p->next;
    }
    //释放空间 
    free(list->last);
    //改变单链表的尾指针指向 
    list->last = p;
    list->last->next = NULL;
    list->size--;
}

//头部删除 
void pop_front(List* list){
    if(list->size == 0){
        printf("链表长度为0，不可进行删除操作.\n");
        return; 
    }
    PNode p = list->first->next;
    list->first->next = p->next;
    free(p);
    //注意：如果链表只有一个元素，删除该节点后要修改尾指针!
    if(list->size == 1){
        list->last = list->first; 
    } 
    list->size--;
}

//插入值[默认链表已经从小到大排序好]
void insert_val(List* list,ElemType e){
    Node* pNode = (Node*)malloc(sizeof(Node));
    pNode->data = e;

    PNode p = list->first;
    while(p->next != NULL && p->next->data < e){
        p = p->next; 
    }
    //说明当前插入的位置是最后一个 
    if(p->next == NULL){
        //修改尾指针
        list->last = p; 
    }
    //插入节点 
    pNode->next = p->next;
    p->next = pNode;
    list->size++; 
}

//查找值
Node* find(List list,ElemType e){
    PNode p = list.first->next;
    while(p != NULL){
        if(e == p->data){
            return p;
        }
        p = p->next;
    }
    return NULL;
} 

//单链表长度
int length(List list){
    return list.size; 
} 

//按值删除
void delete_val(List* list,ElemType data){
    Node* node = find(*list,data);
    if(node == NULL){
        printf("删除值不存在链表中.\n");
        return;
    }
    /*
    注意
        这里找到要删除的节点，按之前的思路是要 
        用删除节点的前驱去指向删除节点的后继
        但这里前驱不好寻找，因此更换思路，
        直接用 删除节点的后继 覆盖 要删除节点 
        然后在清楚掉后继节点即可 
    */
    if(node = list->last){
        //删除最后一个节点
        pop_back(list); 
    }else{    
        Node* p = node->next;
        node->data = p->data;
        node->next = p->next;
        free(p);
    }
    list->size--;    
} 

//排序
void sort(List* list){
    if(list->size <= 1){
        return;
    }

    //指向第一个节点 
    Node* p = list->first->next;
    //指向第二个节点 
    Node* q = p->next;

    //断开链表，形成两个链表，后续遍历第二个链表，
    //然后参照按值插入的方式插入数据 
    list->last = p;
    p->next = NULL;

    while(q != NULL){
        p = q;
        q = q->next;
        Node* temp = list->first;
        while(temp->next != NULL && temp->next->data < p->data){
            temp = temp->next;    
        }
        if(temp->next == NULL){
            list->last = p;
        }
        p->next = temp->next;
        temp->next = p;
    }
} 

//逆置链表
void reverse(List* list){
    /*
    逆置思路跟上面差不多
    将链表一分为二，然后将第二个链表元素依次头插到第一个链表即可 
    */ 
    if(list->size <= 0){
        return;
    }
    //指向第一个元素 
    Node* p = list->first->next;
    //指向第二个元素
    Node* q = p->next;
    //链表一分为二 
    list->last = p;
    p->next = NULL; 
    while(q != NULL){
        p = q;
        q = q->next;
        p->next = list->first->next;
        list->first->next = p;

    }
}

//清空链表
void clear(List* list){
    if(list->size == 0){
        return;
    }
    Node* p = list->first->next;
    while(p != NULL){
        list->first->next = p->next;
        free(p);
        p = list->first->next;
    }
    list->last = list->first;
    list->size = 0;
} 

//销毁链表
void destroy(List* list){
    clear(list);
    free(list->first);
    list->first = list->last = NULL;
} 
int main(){
    List list;
    initList(&list);

    int select = 1;
    ElemType item = 0;
    while(select){
        printf("\n");
        printf("***********************************\n");
        printf("* [1] push_back   [2] push_front  *\n");        
        printf("* [3] show_list   [4] pop_back    *\n");
        printf("* [5] pop_front   [6] insert_val  *\n");
        printf("* [7] find        [8] length      *\n");
        printf("* [9] delete_val  [10] sort       *\n");
        printf("* [11] reverse    [12] clear      *\n");
        printf("* [13] destroy    [0] exit_system *\n");
        printf("***********************************\n");
        printf("请选择> ");
        scanf("%d",&select);
        if(!select){
            break;
        }
        PNode p = NULL;
        switch(select){
            case 1:
                printf("请输入要输入的数据(-1结束):>");
                while(scanf("%d",&item),item != -1){
                    push_back(&list,item);
                }
                break;
            case 2:
                printf("请输入要输入的数据(-1结束):>");
                while(scanf("%d",&item),item != -1){
                    push_front(&list,item);
                }
                break;
            case 3:
                show_list(&list);
                break;
            case 4:
                pop_back(&list);
                break;
            case 5:
                pop_front(&list);
                break;
            case 6:
                printf("请输入要插入的数据:>");
                scanf("%d",&item);
                insert_val(&list,item);
                break;
            case 7:

                printf("请输入要查找的数据:>");
                scanf("%d",&item);
                p = find(list,item);
                if(p == NULL){
                    printf("查找的数据不存在.\n");
                }
                break;
            case 8:
                printf("该链表长度为: %d.\n",length(list));
                break;
            case 9:
                printf("请输入要删除的数据:>");
                scanf("%d",&item);
                delete_val(&list,item);
                break;    
            case 10:
                sort(&list);
                break;
            case 11:
                reverse(&list);
                break;
            case 12:
                clear(&list);
                break;
            case 13:
                destroy(&list);
                break; 
        }    
    }
    destroy(&list);
    return 0;
}

 

4、单链表-代码优化

//---头插尾插优化start--------
//创建节点
Node* create_node(ElemType e){
    Node* pNode = (Node*)malloc(sizeof(Node));
    assert(pNode != NULL);
    pNode->data = e;
    pNode->next = NULL;
    return pNode;
} 
//返回第一个节点 
Node* begin(List* list){
    return list->first->next;
}

//返回最后一个 
Node* end(List* list){
    return list->last->next;
}

//针对pos 的前驱进行插入 
void insert(List* list,Node* pos,ElemType e){
    Node* p = list->first;
    while(p->next != pos){
        p = p->next;
    }
    Node* node = create_node(e);
    
    node->next = p->next;
    p->next = node; 
    if(pos == NULL){
        //插入到链表最后的位置 
        list->last = node;
    }
    list->size++;
}

//尾插法[优化]
void push_back_plus(List* list,ElemType data){
    insert(list,end(list),data);
}

//头插法优化
void push_front_plus(List* list,ElemType data){
    insert(list,begin(list),data);
} 
//-------------end-------------

 

1、创建链表-无头结点
    2、创建链表-有头结点
    3、单链表
  c C     复制代码     246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322   #include<stdio.h>   printf("\n"); printf("***********************************\n"); printf("* [1] push_back [2] push_front *\n"); printf("* [3] show_list [4] pop_back *\n"); printf("* [5] pop_front [6] insert_val *\n"); printf("* [7] find [8] length *\n"); printf("* [9] delete_val [10] sort *\n"); printf("* [11] reverse [12] clear *\n"); printf("* [13] destroy [0] exit_system *\n"); printf("***********************************\n"); printf("请选择> "); scanf("%d",&select); if(!select){ break; } PNode p = NULL; switch(select){ case 1: printf("请输入要输入的数据(-1结束):>"); while(scanf("%d",&item),item != -1){ push_back(&list,item); } break; case 2: printf("请输入要输入的数据(-1结束):>"); while(scanf("%d",&item),item != -1){ push_front(&list,item); } break; case 3: show_list(&list); break; case 4: pop_back(&list); break; case 5: pop_front(&list); break; case 6: printf("请输入要插入的数据:>"); scanf("%d",&item); insert_val(&list,item); break; case 7:   printf("请输入要查找的数据:>"); scanf("%d",&item); p = find(list,item); if(p == NULL){ printf("查找的数据不存在.\n"); } break; case 8: printf("该链表长度为: %d.\n",length(list)); break; case 9: printf("请输入要删除的数据:>"); scanf("%d",&item); delete_val(&list,item); break; case 10: sort(&list); break; case 11: reverse(&list); break; case 12: clear(&list); break; case 13: destroy(&list); break; } } destroy(&list); return 0; }       4、单链表-代码优化
  单链表代码优化 C     复制代码     1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46   //---头插尾插优化start-------- //创建节点 Node* create_node(ElemType e){ Node* pNode = (Node*)malloc(sizeof(Node)); assert(pNode != NULL); pNode->data = e; pNode->next = NULL; return pNode; } //返回第一个节点 Node* begin(List* list){ return list->first->next; }   //返回最后一个 Node* end(List* list){ return list->last->next; }   //针对pos 的前驱进行插入 void insert(List* list,Node* pos,ElemType e){ Node* p = list->first; while(p->next != pos){ p = p->next; } Node* node = create_node(e);   node->next = p->next; p->next = node; if(pos == NULL){ //插入到链表最后的位置 list->last = node; } list->size++; }   //尾插法[优化] void push_back_plus(List* list,ElemType data){ insert(list,end(list),data); }   //头插法优化 void push_front_plus(List* list,ElemType data){ insert(list,begin(list),data); } //-------------end-------------

标签：Node,list,next,链表,printf,NULL
From： https://www.cnblogs.com/xpp3/p/18411865

相关文章

  • 华为OD机试真题-寻找链表的中间节点-2024年OD统一考试（E卷）
    最新华为OD机试考点合集：华为OD机试2024年真题题库（E卷+D卷+C卷）_华为od机试题库-CSDN博客   题目描述给定一个单链表QL，请编写程序输出L中间结点保存的数据,如果有两个中间结点，则输出第二个中间结点保存的数据。例如:给定L为1→7→5，则输出应该为7,给定L为1→2→3→4，则输......
  • C语言----使用链表实现的客户管理系统
    实现一个客户信息管理系统，功能包括添加客户、修改客户、删除客户、显示客户列表。学完了C语言和链表没事情干拿出来写一写，检测下学习成果#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructNode{intnum;charname[20];chargender;......
  • 链表的实现
     链表是数据结构中一种基础且重要的数据结构，它允许我们有效地在序列中插入和删除元素，而无需重新分配整个数据结构。与数组相比，链表提供了更高的灵活性，但也可能在访问速度上有所牺牲。现在我将将从基础概念出发，逐步深入链表并详细探讨链表的基本操作及其与数组的性能差异和适......
  • 21.两两交换链表中的节点
    classSolution{publicListNodeswapPairs(ListNodehead){ListNodea=head,b=head;while(a!=null&&a.next!=null){b=a.next;//两两交换inttemp;temp=a.val;a.val=b.val;......
  • LeetCode Hot100刷题记录-142. 环形链表 II
    给定一个链表的头节点head，返回链表开始入环的第一个节点。如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。如果pos是......
  • 141. 环形链表
    题目链接141.环形链表思路快慢指针-经典问题题解链接没想明白？一个视频讲透快慢指针！（Python/Java/C++/Go/JS）关键点whilefastandfast.next:...时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码实现：classSolution:defhasCycle(self,head:Optio......
  • 142. 环形链表 II
    题目链接142.环形链表II思路快慢指针-经典应用：相遇后，移动head及slow直至相遇题解链接没想明白？一个视频讲透！含数学推导（Python/Java/C++/Go/JS）关键点whilefastandfast.next:...&&whilehead!=slow:...时间复杂度\(O(n)\)空间复杂度\(O(1)\)......
  • 2095. 删除链表的中间节点
    题目链接2095.删除链表的中间节点思路快慢指针-找到中间节点-简单扩展题解链接官方题解关键点whilefastandfast.next:...时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码实现：classSolution:defdeleteMiddle(self,head:Optional[ListNode]......
  • 234. 回文链表
    题目链接234.回文链表思路链表综合题：快慢指针+指针翻转题解链接官方题解关键点whilefast.nextandfast.next.next:...时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码实现：classSolution:defisPalindrome(self,head:Optional[ListNode])......
  • 876. 链表的中间结点
    题目链接876.链表的中间结点思路快慢指针-经典应用题题解链接没想明白？一个视频讲透！（Python/Java/C++/Go/JS/Rust）关键点whilefastandfast.next:...时间复杂度\(O(n)\)空间复杂度\(O(1)\)代码实现：classSolution:defmiddleNode(self,head......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99