欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C实现头插法和尾插法来构建链表

程序员文章站 2022-04-12 20:15:46
链表的构建其实也就是不断插入节点的过程。而节点的插入可以分为头插法和尾插法。头插法就是在头结点后插入该节点,始终把该节点作为第一个节点。尾插法就是在链表的最后一个节点处插入元素,作...

链表的构建其实也就是不断插入节点的过程。而节点的插入可以分为头插法和尾插法。头插法就是在头结点后插入该节点,始终把该节点作为第一个节点。尾插法就是在链表的最后一个节点处插入元素,作为最后一个节点。如果想要了解链表的概念和其他链表操作,请参考《数据结构与算法之链表》《C语言实现链表的基本操作》两篇文章。

//
//  main.c
//  HeadInsertAndTailInsert
//
//  Created by chenyufeng on 16/2/25.
//  Copyright © 2016年 chenyufengweb. All rights reserved.
//

/**
 *  分别使用头插法和尾插法建立单链表
 */

#include 
#include "stdlib.h"
#include "string.h"

typedef int elemType;
//构造节点
typedef struct ListNode{
    int element;
    struct ListNode *next;
}Node;

//初始化链表
void initList(Node *pNode){

    pNode = NULL;
    printf("%s函数执行,头结点初始化完成\n",__FUNCTION__);
}

//打印链表
void printList(Node *pNode){
    if (pNode == NULL) {
        printf("%s函数执行,链表为空,打印失败\n",__FUNCTION__);
    }else{
        while (pNode != NULL) {
            printf("%d ",pNode->element);
            pNode = pNode->next;
        }
        printf("\n");
    }
}

//头插法
Node *HeadInsert(Node *pNode){

    Node *pInsert;
    pInsert = (Node*)malloc(sizeof(Node));
    if (pInsert == NULL) {
        printf("%s函数执行,内存分配失败,建立链表失败\n",__FUNCTION__);
        return NULL;
    }

    memset(pInsert, 0, sizeof(Node));
    scanf("%d",&(pInsert->element));
    pInsert->next = NULL;

    if (pInsert->element <= 0) {
        printf("%s函数执行,输入数据有误,建立链表失败\n",__FUNCTION__);
        return NULL;
    }

    while (pInsert->element > 0) {

        if (pNode == NULL) {
            pNode = pInsert;
        }else{
            //注意下面语句的顺序,否则可能造成链断裂
            pInsert->next = pNode;
            pNode = pInsert;
        }

        pInsert = (Node*)malloc(sizeof(Node));
        if (pInsert == NULL) {
            printf("%s函数执行,内存分配失败,建立链表失败\n",__FUNCTION__);
            return NULL;
        }

        memset(pInsert, 0, sizeof(Node));
        scanf("%d",&(pInsert->element));
        pInsert->next = NULL;
    }

    printf("%s函数执行,头插法建立链表成功\n",__FUNCTION__);

    return pNode;
}

//尾插法
Node *TailInsert(Node *pNode){

    Node *pInsert; //要插入的节点
    Node *pMove; //遍历链表的节点
    pInsert = (Node*)malloc(sizeof(Node));
    if (pInsert == NULL) {
        printf("%s函数执行,内存分配失败,建立链表失败\n",__FUNCTION__);
        return NULL;
    }

    memset(pInsert, 0, sizeof(Node));
    scanf("%d",&(pInsert->element));
    pInsert->next = NULL;

    if (pInsert->element <= 0) {
        printf("%s函数执行,输入数据有误,建立链表失败\n",__FUNCTION__);
        return NULL;
    }

    pMove = pNode;
    while (pInsert->element > 0) {
        if (pNode == NULL) {
            //注意不要忘了修改pMove指针的指向,初始pMove一定要指向头节点
            pNode = pInsert;
            pMove = pNode;
        }else{
            //遍历找到最后一个节点
            while (pMove->next != NULL) {
                pMove = pMove->next;
            }
            pMove->next = pInsert;
        }

        pInsert = (Node*)malloc(sizeof(Node));
        if (pInsert == NULL) {
            printf("%s函数执行,内存分配失败,建立链表失败\n",__FUNCTION__);
            return NULL;
        }

        memset(pInsert, 0, sizeof(Node));
        scanf("%d",&(pInsert->element));
        pInsert->next = NULL;
    }

    printf("%s函数执行,尾插法建立链表成功\n",__FUNCTION__);

    return pNode;
}

int main(int argc, const char * argv[]) {

    Node *pList;

    initList(pList);
    printList(pList);

    //头插法建立链表
    pList = HeadInsert(pList);
    printList(pList);

    //尾插法建立链表
    pList = TailInsert(pList);
    printList(pList);

    return 0;
}