使用C語言對單向連結清單的操作

<span style="font-size:24px;">//以下所有代碼都經過實際上機測試，如果有不合适的地方，請指正，謝謝</span>

<span style="font-size:24px;">
</span>

<span style="font-size:24px;">#include <stdio.h>
#include <stdlib.h>
#include <mem.h>
typedef struct ListNode
    {
        int value;
        struct ListNode *pnext;
    }ListNode;
/* 1.初始化線性表，即置單連結清單的表頭指針為空 */
void initLIST(ListNode **pnode) //此處如果傳入listnode* 類型的參數，則在初始化的時候就會
                                //使pnode 的副本的值置為NULL，而不是傳入值的本身；
{
    *pnode = NULL;
    printf("連結清單初始化成功");
}
/* 2.建立線性表，此函數輸入負數終止讀取資料*/
ListNode *createList(ListNode *head) //傳入頭結點指針，傳回建立完成後的頭結點指針
{
    ListNode *p1,*p2;
    p1 = p2 = (ListNode*)malloc(sizeof(ListNode));//向系統申請一個新節點
    if(p1 == NULL ||p2 == NULL)
    {
        printf("記憶體申請失敗！");
        return 0;
    }
    memset(p1,0,sizeof(ListNode)); //把新節點的内容置為0
    printf("請輸入需要存儲節點的值,輸入負數停止：");
    scanf("%d",&p1->value);
    p1 ->pnext = NULL;
    while(p1->value > 0)
    {
        if(head == NULL) //如果表頭為空，則接入表頭
        {
            head = p1;
        }
        else //不為空則接入表尾
        {
            p2->pnext = p1;
        }
        p2 = p1;
        p1 = (ListNode *)malloc(sizeof(ListNode));
        if(p1 == NULL)
        {
            printf("記憶體申請失敗！");
            return 0;
        }
        memset(p1,0,sizeof(ListNode));
        printf("請輸入需要存儲節點的值,輸入負數停止：");
        scanf("%d",&p1->value);
        p1->pnext = NULL;
    }
    printf("連結清單建立成功！");
    return head;
}
/*3.從頭到尾列印一個連結清單，傳回值是為了判斷是否列印成功,也可以不添加*/
int printList(ListNode *head)
{
    int num = 0;
    if(head == NULL)
    {
        printf("連結清單為空！");
        return 0;
    }
    while(head != NULL)
    {
        printf("%d ",head->value);
        head = head->pnext;
        num++;
    }
    printf("共列印了%d個數字\n",num);
    return num;
}
/*4.在連結清單末尾插入一個節點*/
 //如果需要在新的連結清單中插入一個節點，插入點就是頭結點，需要修改節點的指針
 //是以傳入的值必須為指向指針的指針
 //不能為頭結點的副本
int addNode_Last(ListNode **head,int value) //傳回值代表插入的個數
{
    ListNode *Node = NULL;
    ListNode *pNode;
    Node = (ListNode *)malloc(sizeof(ListNode));
    if(Node == NULL)
    {
         printf("記憶體申請失敗！");
         return 0;
    }
    Node->value = value;
    Node->pnext = NULL; //把新節點的下一個指針置為空
    if(*head == NULL) //判斷頭結點是否為空，如果為空，則插入點為頭結點
    {
        *head = Node;
    }
    else
    {
        pNode = *head;          //找到尾節點，并添加新節點

        while(pNode->pnext != NULL)
        {
            pNode = pNode->pnext;
        }
        pNode->pnext = Node;
    }
    return 1;
}
/*5.在連結清單中找到某個節點并删除*/
int deleteNode(ListNode **head,int key)//傳回值表示删除節點的個數
{
    if(head == NULL && *head == NULL)
        return -1;
    ListNode *beDeleted = NULL;//記錄要删除的節點
    if((*head)->value == key)  //如果要删除的節點為頭結點
    {
        beDeleted = *head;
        *head = (*head)->pnext;
        free(beDeleted);       //釋放删除節點的記憶體
    }
    else
    {
        ListNode *pNode = *head;
        while((pNode->pnext) != NULL && (pNode->pnext)->value != key)
        {
            pNode = pNode->pnext;
        }
        if(pNode->pnext == NULL)
        {
            printf("沒有找到該節點！");
            return 0;
        }
        if(pNode->pnext->value == key)
        {
            beDeleted = pNode->pnext;
            pNode->pnext = beDeleted->pnext;
            free(beDeleted);
            printf("節點已經删除！");
        }
    }
    return 1;
}
/*6.反向周遊連結清單（基于遞歸）*/
//（1.）遞歸本質上也是棧，但是如果使用棧，在C語言中必須自己建構，
// 是以使用遞歸，但本功能理論上使用顯式棧更加安全，因為遞歸深度太大會導緻棧溢出
//（2.）本功能還有一個解法，那就是把所有節點指針反轉再順序周遊，但一般不允許這樣做
void PrintList_revers(ListNode *head)
{
    if(head != NULL)
    {
        if(head->pnext != NULL)
        {
            PrintList_revers(head->pnext);
        }
        printf("%d ",head->value);
    }
}

/*7.反向周遊連結清單（基于遞歸）*/
//（1.）遞歸本質上也是棧，但是如果使用棧，在C語言中必須自己建構，
// 是以使用遞歸，但本功能理論上使用顯式棧更加安全，因為遞歸深度太大會導緻棧溢出
//（2.）本功能還有一個解法，那就是把所有節點指針反轉再順序周遊，但一般不允許這樣做，（請參照<span style="font-family: Arial, Helvetica, sans-serif;">第十個操作</span><span style="font-family: Arial, Helvetica, sans-serif;">）</span>
void PrintList_revers(ListNode *head)
{
    if(head != NULL)
    {
        if(head->pnext != NULL)
        {
            PrintList_revers(head->pnext);
        }
        printf("%d ",head->value);
    }
}
/*
8.在o(1)的時間内删除一個節點，前提是調用者确定這個節點在連結清單中，
  否則如果需要周遊判斷的話，那樣時間效率就是o(n)了，
  這個算法的主要思想就是如果得到了需要删除的節點，
  那麼直接使用下一個節點覆寫需要删除的節點，把下一個節點删除，
  這樣的話就不需要周遊查找了，
  如果要删除的節點為尾節點，那麼還是需要從頭開始周遊連結清單，查找前一個節點
  因為如果需要删除的連結清單隻有一個節點，既是是頭節點，又是尾節點，
  那麼就需要修改頭結點的值，是以在傳入頭節點時是傳入一個指向指針的指針。
*/
void deleteNode_o1(ListNode **listHead, ListNode *toBeDeleted)
{
    if(listHead == NULL || toBeDeleted == NULL)
        return;
    if(toBeDeleted ->pnext != NULL) //如果傳入的節點不是尾節點
    {
        ListNode *pNext = toBeDeleted->pnext;
        toBeDeleted->value = pNext->value;
        toBeDeleted->pnext = pNext->pnext;
        free(pNext);
        pNext = NULL;
    }
    else if(*listHead == toBeDeleted)//如果連結清單隻有一個節點，
    {                                //删除的節點既是頭結點，也是尾節點
        free(*listHead);
        *listHead = NULL;
        toBeDeleted = NULL;
    }
    else //如果連結清單有多個節點，但是傳入的節點是尾節點
    {
        ListNode *preNode = *listHead;
        while(preNode->pnext != toBeDeleted)
        {
            preNode = preNode->pnext;
        }
        preNode->pnext = NULL;
        free(toBeDeleted);
        toBeDeleted = NULL;
    }


}
/*9.求連結清單中倒數第K個節點*/
/*
思路：
定義兩個指針，第一個指針先走K-1步，然後第二個指針開始一起走，
當第一個指針走到尾節點的時候，第二個指針剛好是倒數第K個。
*/
ListNode *FindKthToTail(ListNode *listHead, unsigned int k)
{
    if(listHead == NULL || k == 0)
        return;
    ListNode *pAhead = listHead;
    ListNode *pBehind = listHead;
    int i;
    for(i = 0; i < k-1; i++)
    {
        if(pAhead->pnext != NULL)
        {
            pAhead = pAhead->pnext;
        }
        else
            return NULL;
    }
    while(pAhead->pnext != NULL)
    {
        pAhead = pAhead->pnext;
        pBehind = pBehind->pnext;
    }
    return pBehind;
}
/*10.反轉一個連結清單，并傳回頭節點,使用修改指針的方法*/
/*
思路：
    定義三個指針，分别指向目前節點，前一個節點和下一個節點
    然後進行循環
*/
ListNode *ReversList(ListNode *listHead)
{
    ListNode *preNode = NULL;
    ListNode *headNode = listHead;
    ListNode *nextNode = NULL;
    while (headNode != NULL)
    {
        nextNode = headNode->pnext;
        headNode->pnext = preNode;
        preNode = headNode;
        if(nextNode == NULL)
            break;
        headNode = nextNode;
    }
    return headNode;
}
/*11.合并兩個排序的連結清單，并傳回新連結清單的頭結點*/
ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    if(pHead2 == NULL)
        return pHead1;
    ListNode *newListHead = NULL;
    if(pHead1->value < pHead2->value)
    {
        newListHead = pHead1;
        newListHead->pnext = Merge(pHead1->pnext,pHead2);
    }
    else
    {
        newListHead = pHead2;
        newListHead->pnext = Merge(pHead1,pHead2->pnext);
    }
    return newListHead;
}

int main()
{
    ListNode *ListHead = NULL;
    initLIST(&ListHead);
    ListHead = createList(ListHead);
    printList(ListHead);
    /*
    addNode_Last(&ListHead,21);
    printList(ListHead);
    deleteNode(&ListHead,21);
    printList(ListHead);
    */
    PrintList_revers(ListHead);
    return 0;
}
</span>

使用C語言對單向連結清單的操作

繼續閱讀

C語言-----初階指針詳解

輸出蛇形矩陣 C語言輸出蛇形矩陣

1.54寸TFT ST7789液晶屏圖檔如何取模

三子棋——年輕人的第一款小遊戲前言正文總結

DOG（4）：解析器的部分實作細節先來說說parser一些可能迷惑的地方結果如何傳回?pcd其實是一回事最後的一點說明

NYOJ 269--VF

二叉樹三種周遊(先序，中序，後序)----超詳細引入先序周遊後序周遊中序周遊總結

UVA 110 Meta-Loopless Sorts

CRC32和CRC8校驗代碼，C語言版

241 Different Ways to Add Parentheses（C代碼版）

C語言：初學者必定看懂的注釋！！！猴子吃桃問題。猴子第一天摘下若幹個桃子，每天都吃了前一天剩下的一半零一個，到第10天早上想再吃的時候，就剩下一個桃子. 求第一天共摘多少個桃子。

[轉]九大排序算法——C語言實作及詳解

while 循環、do- while 循環和 for 循環之間的那點事C語言自學之三種循環比較

結構體：typedef與struct的差別

hdu7108哈希