程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言入門知識 >> C實現頭插法和尾插法來構建鏈表

C實現頭插法和尾插法來構建鏈表

編輯:C語言入門知識

鏈表的構建其實也就是不斷插入節點的過程。而節點的插入可以分為頭插法和尾插法。頭插法就是在頭結點後插入該節點,始終把該節點作為第一個節點。尾插法就是在鏈表的最後一個節點處插入元素,作為最後一個節點。如果想要了解鏈表的概念和其他鏈表操作,請參考《數據結構與算法之鏈表》《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;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved