單鏈表的基本操作---插入，刪除，交，並，相鄰元素的交換等

来源:http://www.cnblogs.com/xinlovedai/archive/2016/12/23/6216130.html
-Advertisement-
Play Games

這個鏈表是帶有表頭的單鏈表。實現鏈表的一些規範操作，初始化，插入，刪除等。包括兩個頭文件list.h，fatal.h，庫函數list.c，測試函數testlist.c。頭文件放的都是函數聲明，庫函數list.c放的的函數的定義。 頭文件list.h 頭文件fatal.h： 庫函數list.c： 測試 ...


這個鏈表是帶有表頭的單鏈表。實現鏈表的一些規範操作，初始化，插入，刪除等。包括兩個頭文件list.h，fatal.h，庫函數list.c，測試函數testlist.c。頭文件放的都是函數聲明，庫函數list.c放的的函數的定義。

頭文件list.h

 1 typedef int ElementType;
 2 #ifndef _List_H//如果沒有編譯過
 3 struct Node;
 4 typedef struct Node *PtrToNode;
 5 typedef PtrToNode List;
 6 typedef PtrToNode Position;
 7 
 8 List MakeEmpty(List L);
 9 void DeleteList(List L);
10 int IsEmpty(List L);
11 int IsLast(Position P, List L);
12 Position Find(ElementType X, List L);
13 void Delete(ElementType X, List L);
14 Position FindPrevious(ElementType X, List L);
15 void Insert(ElementType X, List L,Position P);
16 Position Header(List L);
17 Position First(List L);
18 Position Advance(Position P);
19 ElementType Retrieve(Position P);
20 void PrintList(const List L);
21 void PrintLots(List L, List P);
22 void SwapWithNext(Position BeforeP, List L);
23 List IntersectList(List L, List P);
24 List UnionList(Position L, Position P);
25 #endif // !_List_H

頭文件fatal.h：

1 #include<stdio.h>
2 #include<stdlib.h>
3 #define Error(Str) FatalError(Str)
4 #define FatalError(Str) fprintf(stderr,"%s\n",Str),exit(1);

 

庫函數list.c：

//引用頭文件
#include "list.h"
#include<stdlib.h>
#include "fatal.h"

//結構體定義
struct Node
{
    ElementType Element;
    Position Next;
};

//初始化鏈表
List MakeEmpty(List L)
{
    if (L != NULL)
        DeleteList(L);//如果鏈表非空，則刪除鏈表
    L = malloc(sizeof(struct Node));
    if (L == NULL)
        FatalError("Out of memory!");
    L->Next = NULL;
    return L;
}

//刪除鏈表
void DeleteList(List L)
{
    Position P, Temp;
    P = L->Next;
    L->Next = NULL;
    while (P != NULL)
    {
        Temp = P->Next;
        free(P);
        P = Temp;
    }
}

//判斷鏈表是否為空
int IsEmpty(List L)
{
    return L->Next==NULL;
}
 
//判斷當前指針P是否指向鏈表最後一個元素
int IsLast(Position P, List L)
{
    return P->Next==NULL;
}

//return Position of X in L;NULL if not found
Position Find(ElementType X, List L)
{
    Position P;
    P = L->Next;
    while (P != NULL && P->Element != X)
        P = P->Next;    
    return P;
}

//刪除鏈表中的元素X，若返回NULL，說明在鏈表中沒找到元素X
void Delete(ElementType X, List L)
{
    Position P, TempCell;
    P = FindPrevious(X, L);
    if (!IsLast(P, L))//當P不是尾針，說明找到了
    {
        TempCell = P->Next;
        P->Next = TempCell->Next;
        free(TempCell);
        TempCell = NULL;
    }

}


//如果返回的P指向最後一個元素，說明沒有找到，1==IsLast(P,L)
Position FindPrevious(ElementType X, List L)
{
    Position P;
    P = L;
    while (P->Next != NULL&&P->Next->Element != X)
        P = P->Next;
    return P;
}

//插入元素X到位置P後面
void Insert(ElementType X, List L, Position P)
{
    Position  TmpCell;
    TmpCell = malloc(sizeof(struct Node));
    if (TmpCell == NULL)
        FatalError("Out of Space!!!");
    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

//獲取鏈表頭
Position Header(List L)
{
    return L;
}

//獲取鏈表第一個元素的位置
Position First(List L)
{
    return L->Next;
}

//獲取位置P的下一個位置
Position Advance(Position P)
{
    return P->Next;
}

//提取位置P處結構裡面的值
ElementType Retrieve(Position P)
{
    return P->Element;
}

//列印鏈表
void PrintList(const List L)
{
    Position P=Header(L);
    if (IsEmpty(L))
        printf("Empty list\n");
    else
    {
        do
        {
            P = Advance(P);
            printf("%d ", Retrieve(P));
        } while (!IsLast(P, L));
        printf("\n");
    }
}


//列印鏈表L中那些由P所指定的位置上的元素。例如P=1，3，4，6，將L
//中的第1，第3，第4，第6個元素列印出來
void PrintLots(List L, List P)
{
    int count = 1;
    Position Lpos, Ppos;
    Lpos = First(L);
    Ppos = First(P);
    while (Lpos != NULL&&Ppos != NULL)
    {
        if ( Ppos->Element == count++)
        {
            printf("%d ", Ppos->Element);
            Ppos = Advance(Ppos);
        }
        Lpos = Advance(Lpos);
    }


}


//通過只調整指針來交換兩個相鄰的元素，BeforeP是要調換兩個元素的前一
//個指針
void SwapWithNext(Position BeforeP, List L)
{
    Position P, AfterP;
    if (BeforeP != NULL)
    {
        P = Advance(BeforeP);
        if (P != NULL)
        {
            AfterP = Advance(P);
            if (AfterP != NULL)
            {
                P->Next = AfterP->Next;
                BeforeP->Next = AfterP;
                AfterP->Next = P;
            }
        }
    }
}

//求兩個鏈表的交集
List IntersectList(List L1, List L2)
{
    List ResultList;
    Position L1Pos, L2Pos, ResultPos;
    ResultList = MakeEmpty(NULL);
    L1Pos = First(L1);
    L2Pos = First(L2);
    ResultPos = Header(ResultList);
    while (L1Pos!=NULL&&L2Pos!=NULL)
    {
        if (L1Pos->Element < L2Pos->Element)
            L1Pos = Advance(L1Pos);
        else if (L1Pos->Element > L2Pos->Element)
            L2Pos = Advance(L2Pos);
        else
        {
            Insert(L1Pos->Element, ResultList, ResultPos);
            ResultPos= Advance(ResultPos);
            L1Pos = Advance(L1Pos);
            L2Pos = Advance(L2Pos);
        }
    }
    return ResultList;
}

//求兩個鏈表的並集
List UnionList(Position L1, Position L2)
{
    List ResultList;
    ElementType InsertElement;
    Position L1Pos, L2Pos, ResultPos;
    ResultList = MakeEmpty(NULL);
    L1Pos = First(L1);
    L2Pos = First(L2);
    ResultPos = Header(ResultList);
    while (L1Pos != NULL&&L2Pos != NULL)
    {
        if (L1Pos->Element < L2Pos->Element)
        {
            InsertElement = L1Pos->Element;
            L1Pos = Advance(L1Pos);
        }
        else if (L1Pos->Element > L2Pos->Element)
        {
            InsertElement = L2Pos->Element;
            L2Pos = Advance(L2Pos);
        }
        else
        {
            InsertElement = L1Pos->Element;
            L1Pos = Advance(L1Pos);
            L2Pos = Advance(L2Pos);
        }
        Insert(InsertElement, ResultList, ResultPos);
        ResultPos = Advance(ResultPos);
    }
    while (L1Pos != NULL)
    {
        Insert(L1Pos->Element, ResultList, ResultPos);
        ResultPos = Advance(ResultPos);
        L1Pos = Advance(L1Pos);
    }
    while (L2Pos != NULL)
    {
        Insert(L2Pos->Element, ResultList, ResultPos);
        ResultPos = Advance(ResultPos);
        L2Pos = Advance(L2Pos);
    }
    return ResultList;
}

 測試函數testlist.c

 1 #include<stdlib.h>
 2 #include "list.h"
 3 main()
 4 {
 5     List L,L1;
 6     Position P,P1;
 7     int i;
 8     L = MakeEmpty(NULL);
 9     P = Header(L);
10     PrintList(L);
11 
12     L1 = MakeEmpty(NULL);
13     P1 = Header(L1);
14     PrintList(L1);
15 
16 
17     for (i = 0; i < 50; i+=2)
18     {
19         Insert(i, L, P);
20         //PrintList(L);
21         P = Advance(P);
22     }
23     PrintList(L);
24     printf("\n");
25     for (i = 1; i < 100; i+=3)
26     {
27         Insert(i, L1, P1);
28         //PrintList(L);
29         P1 = Advance(P1);
30     }
31     PrintList(L1);
32     printf("\n");
33 
34     PrintList(IntersectList(L, L1));
35     printf("\n");
36     PrintList(UnionList(L, L1));
37     //PrintLots(L, L1);
38 
39     //SwapWithNext(L, L);//換頭兩個元素
40 
41     //for (i = 0; i < 10; i += 2)
42     //    Delete(i, L);
43     //for (i = 0; i < 10; i++)
44     //{
45     //    if ((i % 2 == 0) == (Find(i, L) != NULL))
46     //        printf("Find fails\n");
47     //}
48     //printf("Finished deletions\n");
49     //PrintList(L);
50     DeleteList(L);
51     DeleteList(L1);
52     return 0;
53 }

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • EC筆記：第3部分：15、對原始資源的訪問
    使用對象來管理資源，可以避免因個人疏忽帶來的一些低級錯誤，但是不是每件事都是稱心如意的。 一些函數依然使用原始的資源對象，那麼我們就需要為這些函數提供一個介面，讓他們可以獲取到原始對象。 繼續拿13節的智能指針說事，先上代碼： //SFAutoPtr.h #pragma once template ... ...
  • Java集合框架之List介面
    在上一篇Java集合框架之Collection介面中我們知道List介面是Collection介面的子介面，List介面對Collection進行了簡單的擴充，List介面中的元素的特點為有序，可重覆，允許null值，因為List繼承了Collection介面，所以繼承自Collection介面中的 ...
  • Python 3 利用 subprocess 實現管道( pipe )交互操作讀/寫通信
    這裡我們用Windows下的shell來舉例： 為了方便你理解，我們用一個很簡單的一段代碼來說明： 可以看見我們利用Popen實例化了一個p，創建了子程式cmd.exe，然後我們給他的的Stdin（標準輸入流）Stdout（標準輸出流）; 同時使用了subprocess.PIPE 作為參數，這個是一 ...
  • [APUE]文件和目錄
    一、APUE這一章中的各種晦澀名詞 我在讀這一章時遇到了各種ID，根據名字完全不清楚什麼意思，幸好看到了這篇文章，http://blog.csdn.net/ccjjnn19890720/article/details/6990656，總結一下 每一個進程其實對應了6個以上的ID，它們分別是：實際用戶 ...
  • 無表頭單鏈表的總結----動態建立鏈表
    1 #include "head.h" 2 struct Student *creat() 3 { 4 struct Student *head, *p1, *p2;// 先開闢三個結構體指針，*head,（作為返回的頭指針） 5 p1 = p2 =(struct Student *) malloc... ...
  • 變數 、緩衝值 、編碼
    變數 、緩衝值 、編碼 --道心 變數 聲明變數 eg: #!/usr/bin/env python # -*- coding: utf-8 -*- name = "DaoXin" 上述代碼聲明瞭一個變數，變數名為： name，變數name的值為："DaoXin" 變數的作用：昵稱，其代指記憶體里某個 ...
  • 數組實現多項式的加減乘運算
    "fatal.h"//頭文件 1 #include<stdio.h> 2 #include<stdlib.h> 3 #define Error(Str) FatalError(Str) 4 #define FatalError(Str) fprintf(stderr,"%s\n",Str),exit ...
  • 深度理解CSS樣式表，內有彩蛋....
    樣式表的幾點常用：background-color： 背景顏色 background-image：url 設置圖片背景 background-repeat平鋪 repeat-x 橫向平鋪 background-position：center 背景居中 background-position：righ ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類