程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> 關於C >> C語言實現單鏈表(帶頭結點)的基本操作

C語言實現單鏈表(帶頭結點)的基本操作

編輯:關於C

我在之前一篇博客《C語言實現單鏈表(不帶頭結點)的基本操作》中具體實現了不帶頭結點的單鏈表的11種操作:如計算鏈表長度、初始化、創建鏈表、清空鏈表等等。但是在實際使用中,帶頭結點的單鏈表往往比不帶頭結點的單鏈表用的更多,使用也更為方便。因為不用單獨考慮第一個節點的情況了,第一個節點和其他後續節點的處理全都一樣了,簡化操作。這篇博客將會來實現帶頭結點的單鏈表的11種操作。

(1)定義帶頭結點單鏈表的節點類型

typedef int elemType;
typedef struct NodeList{

    int element;
    struct NodeList *next;
}Node;

(2)初始化帶頭結點的單鏈表【這個很關鍵】
//1.初始化帶頭結點的單鏈表
void InitialList(Node **pNode){

    //個人建議每一次malloc分配內存空間後,都要進行判斷分配是否成功,也即判斷是否為空;
    //此時的這個pNode就是一個頭結點;
    //初始化成功後,其實相當於是一個正常的鏈表了;
    *pNode = (Node *)malloc(sizeof(Node));
    if (*pNode == NULL) {
        printf("%s函數執行,內存分配失敗,初始化單鏈表失敗",__FUNCTION__);
    }else{

        (*pNode)->next = NULL;
        printf("%s函數執行,帶頭結點的單鏈表初始化完成\n",__FUNCTION__);
    }
}

(3)尾插法創建帶頭結點的單鏈表

 

//2.創建帶頭結點的單鏈表
void CreateList(Node *pNode){

    /**
     *  就算一開始輸入的數字小於等於0,帶頭結點的單鏈表都是會創建成功的,只是這個單鏈表為空而已,也就是裡面除了頭結點就沒有其他節點了。
     */
    Node *pInsert;
    Node *pMove;
    pInsert = (Node *)malloc(sizeof(Node));//需要檢測分配內存是否成功 pInsert == NULL  ?
    memset(pInsert, 0, sizeof(Node));
    pInsert->next = NULL;

    scanf("%d",&(pInsert->element));
    pMove = pNode;
    while (pInsert->element > 0) {

        pMove->next = pInsert;
        pMove = pInsert;

        pInsert = (Node *)malloc(sizeof(Node)); //需要檢測分配內存是否成功 pInsert == NULL  ?
        memset(pInsert, 0, sizeof(Node));
        pInsert->next = NULL;

        scanf("%d",&(pInsert->element));
    }

    printf("%s函數執行,帶頭結點的單鏈表創建成功\n",__FUNCTION__);
}

(4)打印帶頭結點的單鏈表

//3.打印帶頭結點的單鏈表
void PrintList(Node *pNode){
    /**
     *  注意這裡,如果單鏈表為空(只有一個頭結點),我也讓它打印(打印成功)。只是裡面沒有元素,打出來是空的而已,所以在控制台上就是一行空的;
     */
        Node *pMove;
        pMove = pNode->next;
        while (pMove != NULL) {
            printf("%d ",pMove->element);
            pMove = pMove->next;
        }

        printf("\n%s函數執行,打印帶頭結點的單鏈表成功\n",__FUNCTION__);
}

(5)清空鏈表
//4.清除線性表中的所有元素,即釋放所有節點(除了頭結點),使之成為一個空表
void ClearList(Node *pNode){

    Node *pMove;
    pMove = pNode->next;
    while (pMove != NULL) {

        pNode->next = pMove->next;
        free(pMove);
        pMove = pNode->next;
    }

    printf("%s函數執行,清空帶頭結點的鏈表成功\n",__FUNCTION__);
}

(6)計算鏈表長度
//5.返回帶頭結點的單鏈表的長度
int SizeList(Node *pNode){
    /**
     *  當只有一個頭結點的時候,size = 0;頭節點不計算到鏈表長度中。
     */
    int i = 0;
    Node *pMove;
    pMove = pNode->next;
    while (pMove != NULL) {
        i++;
        pMove = pMove->next;
    }

    printf("%s函數執行,帶頭結點的單鏈表的長度為:%d\n",__FUNCTION__,i);

    return i;
}
(7)判斷鏈表是否為空
//6.判斷帶頭結點的單鏈表是否為空,為空則返回1,否則返回0
int IsEmptyList(Node *pNode){
    /**
     *  當只有一個頭結點的時候,該鏈表就為空
     */
    if (pNode->next == NULL) {
        printf("%s函數執行,帶頭結點的鏈表為空\n",__FUNCTION__);
        return 1;
    }

    printf("%s函數執行,帶頭結點的鏈表非空\n",__FUNCTION__);

    return 0;
}

(8)查找鏈表某個位置元素

//7.返回單鏈表中第pos個結點中的元素,若返回-1,表示沒有找到
int GetElement(Node *pNode,int pos){

    int i = 1;

    Node *pMove;
    pMove = pNode->next;

    while (pMove != NULL) {
        if (i == pos) {

            printf("%s函數執行,pos=%d位置的值是%d\n",__FUNCTION__,pos,pMove->element);
            return pMove->element;
        }

        i++;
        pMove = pMove->next;
    }

    printf("%s函數執行,在pos=%d位置沒有找到值\n",__FUNCTION__,pos);
    return -1;
}

(9)返回某元素在鏈表中的內存地址
//8.從單鏈表中查找具有給定值x的第一個元素,若查找成功則返回該結點data域的存儲地址,否則返回NULL
elemType* GetElemAddr(Node *pNode,int x){

    Node *pMove;
    pMove = pNode->next;

    while (pMove != NULL) {
        if (pMove->element == x) {
            printf("%s函數執行,查找到x=%d的內存地址為:0x%x\n",__FUNCTION__,x,&(pMove->element));
            return &(pMove->element);
        }
        pMove = pMove->next;
    }

    printf("%s函數執行,在帶頭結點的單鏈表中沒有找到x=%d的值,無法獲得內存地址\n",__FUNCTION__,x);

    return NULL;
}

(10)修改某個節點的值
//9.把單鏈表中第pos個結點的值修改為x的值
Node* ModifyElem(Node *pNode,int pos,int x){

    int i = 1;
    Node *pMove;
    pMove = pNode->next;
    while (pMove != NULL) {
        if (i == pos) {
            pMove->element = x;
            printf("%s函數執行,把pos=%d位置的值改為%d成功\n",__FUNCTION__,pos,x);
            return pNode;
        }
        i++;
        pMove = pMove->next;
    }
    printf("%s函數執行,鏈表為空或者輸入pos值非法,修改值失敗\n",__FUNCTION__);

    return pNode;
}

(11)表頭插入一個節點
//10.向單鏈表的表頭插入一個元素
Node *InsertHeadList(Node *pNode,int x){

    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->element = x;

    pInsert->next = pNode->next;
    pNode->next = pInsert;

    printf("%s函數執行,在表頭插入元素%d成功\n",__FUNCTION__,x);
    return pNode;
}

(12)表尾插入一個節點
// 11.向單鏈表的末尾添加一個元素
Node *InsertTailList(Node *pNode,int x){

    Node *pMove;
    Node *pInsert;
    pInsert = (Node *)malloc(sizeof(Node));
    memset(pInsert, 0, sizeof(Node));
    pInsert->element = x;
    pInsert->next = NULL;

    pMove = pNode;
    while (pMove->next != NULL) {
        pMove = pMove->next;
    }
    pMove->next = pInsert;

    printf("%s函數執行,在表尾插入元素%d成功\n",__FUNCTION__,x);

    return pNode;
}

(13)測試函數

 

 

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

    Node *pList;

    InitialList(&pList);

    CreateList(pList);
    PrintList(pList);

    SizeList(pList);

    IsEmptyList(pList);

    GetElement(pList, 3);

    GetElemAddr(pList, 5);

    ModifyElem(pList, 2, 111);
    PrintList(pList);

    InsertHeadList(pList,1234);
    PrintList(pList);
    SizeList(pList);

    InsertTailList(pList,9999);
    PrintList(pList);
    SizeList(pList);

    ClearList(pList);
    PrintList(pList);

    return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved