數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn))

這篇具有很好參考價值的文章主要介紹了數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn))。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

1. 線性表的鏈式表示: 鏈表

1.1 順序表的優(yōu)缺點

在介紹鏈表之前, 先回顧一下順序表的優(yōu)缺點
數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

順序表的優(yōu)點:

存儲密度高: 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間.
隨機訪問: 通過首地址和元素序號可以在時間 $O (1)$ 內(nèi)找到指定的元素.
命中率高：CPU每次取一定大小空間放入緩存，連續(xù)的空間命中率高

順序表的缺點:

順序表邏輯上相鄰的元素物理上也相鄰, 插入和刪除操作需要移動大量元素,時間復雜度為 $O (N)$ .
當線性表長度變化較大時, 難以確定存儲空間的容量
造成存儲空間的"碎片"

1.2 鏈表的概念

為了避免順序表插入和刪除的線性開銷, 我們允許表可以不連續(xù)存儲, 否則表的部分或全部需要整體移動.
數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

鏈表由一系列不必在內(nèi)存中相連的結構組成.

每個結構均含有表元素和指向包含該元素后繼元的結構的指針.我們稱為 next 指針.最后一個單元的 next 指針指向 NULL ;該值由C定義并且不能與其他指針混淆.ANSI C 規(guī)定 NULL 為 0

如果 P 被聲明為一個指向一個結構的指針, 那么存儲在 P中的值就被解釋為主存中的一個位置, 在該位置能夠找到一個結構.

該結構的一個域可以通過 P->FieldName 訪問, 其中 FieldName 是我們想要考察的域的名字.

以下是表的具體表示, 即物理存儲結構. 這個表含有 5 個結構, 內(nèi)存分給它們的位置分別是 1000, 800, 712, 992 和 692.

第一個結構的指針含有值 800, 它提供了第二個結構所在的位置. 其余每個結構也都有一個指針用于類似的目的. 通過指針值, 可以訪問到下一結構體的位置. 為了訪問該表, 需要知道該表的第一個單元.

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

1.3 鏈表的優(yōu)缺點

由此可以分析出單鏈表的優(yōu)缺點:

鏈表的優(yōu)點

更加合理使用空間: 按需申請空間, 不用則釋放空間
元素的插入和刪除效率更高, 只需要 $O (1)$ 的時間
不存在空間浪費

鏈表的缺點

訪問速度慢: 查找某一元素需要從頭開始依次查找, 消耗 $O (N)$ 的時間
存儲密度低: 每個元素還需要額外空間存放指針空間, 用于將表中數(shù)據(jù)鏈接起來

1.4 鏈表的結構

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

邏輯結構: 便于理解想象出來的, 實際不存在, 一般用箭頭表示, 實際箭頭不存在
物理結構: 主存中實際的存儲方式, 不一定是處在連續(xù)存儲的空間

2. 單鏈表的定義

2.1 單鏈表的結構體

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

typedef int SLTDateType;

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

為了后續(xù)代碼便于復用, 使用 typedef 將數(shù)據(jù)類型和結構體類型重命名

每一個單鏈表結點包含兩個域: 數(shù)據(jù)域data 和指針域next
struct SListNode* next實現(xiàn)結構體指向結構體

2.2 接口函數(shù)

// 動態(tài)申請一個結點
SListNode* BuySListNode(SLTDataType x);
// 單鏈表打印
void SListPrint(SListNode* pHead);
// 單鏈表尾插
void SListPushBack(SListNode** ppHead, SLTDataType x);
// 單鏈表頭插
void SListPushFront(SListNode** ppHead, SLTDataType x);
// 單鏈表尾刪
void SListPopBack(SListNode** pHead);
// 單鏈表頭刪
void SListPopFront(SListNode** pHead);
// 單鏈表查找
SListNode* SListFind(SListNode* pHead, SLTDataType x);
// 單鏈表在 pos 位置之前插入
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType x);
// 單鏈表在 pos 位置上刪除
void SListErase(SListNode** ppHead, SListNode* pos);
// 單鏈表在 pos 位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
// 單鏈表在 pos 位置之后刪除
void SListEraseAfter(SListNode* pos);
// 單鏈表的銷毀
void SListDestroy(SListNode** ppHead);

3. 接口函數(shù)的實現(xiàn)

3.1 動態(tài)申請一個結點 (BuySListNode)

單鏈表插入元素必然要新向內(nèi)存動態(tài)申請一個結點的空間, 這個操作可以直接封裝成一個函數(shù), 便于后續(xù)創(chuàng)建結點使用.

SList.h

SListNode* BuySListNode(SLTDataType x);

SList.c

// 動態(tài)申請一個結點
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));

    if (newNode == NULL)
    {
        perror("BuySListNode:");
        exit(-1);
    }

    newNode->data = x;
    newNode->next = NULL;

    return newNode;
}

test.c

void SListTest1()
{
    SListNode* newNode = BuySListNode(3);
    free(newNode);
}

int main(void)
{
    SListTest1();

    return 0;
}

通過調試,創(chuàng)建結點成功:

3.2 單鏈表打印 (SListPrint)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

通過plist的地址訪問到第一個結點, 打印該結點的數(shù)據(jù)值, 同時訪問下一結點直至該結點是空指針.

在訪問鏈表的時候, 最好使用一個臨時指針來訪問, 避免后續(xù)增刪元素的時候對鏈表首地址進行修改

SList.h

void SListPrint(SListNode* pHead);

SList.c

// 單鏈表打印
void SListPrint(SListNode* pHead)
{
   SListNode* cur = pHead;  //定義一個局部變量指針用來訪問鏈表

   //從頭依次訪問鏈表, cur不為空進入循環(huán)
   while(cur != NULL)
   {
        printf("%d -> ", cur->data);    //打印結構的數(shù)據(jù)域
        cur = cur->next;    //使cur指向下一結點
   }

   printf("NULL\n");
}

test.c
后續(xù)其他功能測試都會用到, 這里就先不測試了

3.3 單鏈表尾插 (SListPushBack)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

創(chuàng)建一個新結點, 讓原最后一個結點指向新結點, 同時新結點指向空指針.

SList.h

void SListPushBack(SListNode** ppHead, SLTDateType x);

涉及對結構體指針的修改, 需要用到二級指針.雖然是尾插,但如果該鏈表沒有一個元素, 就需要將新結點的地址賦值給實參pList;想要函數(shù)修改指針的值,就需要形參是二級指針,也就是函數(shù)需要傳址調用.

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

SList.c

// 單鏈表尾插
void SListPushBack(SListNode** ppHead, SLTDateType x);
{
    SListNode* newNode = BuySListNode(x);   //創(chuàng)建一個新結點

    if(*ppHead == NULL)    //沒有結點, 直接將新結點的地址賦值
    {
        *ppHead = newNode;  //修改結構體指針, 需要用到二級指針
    }
    else    //有結點, 依次訪問直到最后一個元素
    {
        SListNode* tail = *ppHead;  //tail 用于訪問鏈表
        while (tail->next != NULL)
        {
            tail = tail->next;  
        }

        tail->next = newNode;   //修改結構體, 只要用到一級指針
    }
}

首先創(chuàng)建一個新結點newNode

接著判斷鏈表是否為空,若為空,則直接使用二級指針將新結點的地址賦值給實參pList

若鏈表不為空,則只需要修改結構體的內(nèi)容,用到一級指針即可.當訪問到該結點的next為空時,進行尾插操作.

test.c

void SListTest1()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);
    SListDestroy(&pList);
}

int main(void)
{
    SListTest1();

    return 0;
}

測試運行結果如下:

3.4 單鏈表頭插 (SListPushFront)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

修改pList,讓pList指向新結點,同時新結點的next指向原鏈表第一個結點

SList.h

void SListPushFront(SListNode** ppHead, SLTDateType x);

同樣這里需要修改實參pList的值,函數(shù)的形參需要傳入二級指針.

SList.c

// 單鏈表的頭插
void SListPushFront(SListNode** ppHead, SLTDateType x)
{
    SListNode* newNode = BuySListNode(x);   //創(chuàng)建新結點

    newNode->next = *ppHead;    //新結點指向原鏈表第一個結點
    *ppHead = newNode;          //更新頭結點
}

首先創(chuàng)建新結點newNode

隨后先將新結點指向原頭結點, 再更頭結點的值.
注意這兩步不可顛倒,否則頭結點的地址就丟失了

test.c

void SListTest1()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListPushFront(&pList, -1);
    SListPushFront(&pList, -2);
    SListPushFront(&pList, -3);
    SListPushFront(&pList, -4);
    SListPushFront(&pList, -5);
    SListPushFront(&pList, -6);

    SListPrint(pList);
    SListDestroy(&pList);
}

int main(void)
{
    SListTest1();

    return 0;
}

測試結果如下:

3.5 單鏈表尾刪 (SListPopBack)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

注意分三種情況

SList.h

void SListPopBack(SListNode** ppHead);

同樣有修改結構體指針的情況,需要用到二級指針

SList.c

// 單鏈表的尾刪
void SListPopBack(SListNode** ppHead)
{
    assert(*ppHead);    //沒有結點的情況

    if ((*ppHead)->next == NULL)  //只有一個結點的情況
    {
        free(*ppHead);
        *ppHead = NULL; //修改實參的值需要用到二級指針
    }
    else    //有兩個結點以上的情況
    {
        SListNode* tail = *ppHead;   //tail用來訪問結構體成員

        while (tail->next->next != NULL) //需要修改倒數(shù)第二個結點的值, 則訪問到倒數(shù)第二個結點即停止
        {
            tail = tail->next;
        }

        free(tail->next);  //先釋放最后一個結點的空間
        tail->next = NULL;  //倒數(shù)第二個結點指向NULL
    }
}

若鏈表為空,沒有結點,程序直接結束

若只有一個結點,則需要用到二級指針來修改實參pList的值為NULL,同時釋放頭結點空間

若有兩個及以上結點,只用修改結構體.若要修改倒數(shù)第二個結點的值,則只要訪問到倒數(shù)第二個結點就可以了.這是單向鏈表,不可返回訪問

test.c

void SListTest2()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListPopBack(&pList);
    SListPopBack(&pList);

    SListPrint(pList);

    SListPopBack(&pList);
    SListPopBack(&pList);
    SListPopBack(&pList);

    SListPrint(pList);  

    SListPopBack(&pList);       //一個結點

    SListPrint(pList);

    SListPopBack(&pList);       //沒有結點

    SListPrint(pList);
    SListDestroy(&pList);
}

int main(void)
{
    SListTest2();

    return 0;
}

測試運行結果如下:

3.6 單鏈表頭刪 (SListPopFront)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

單鏈表頭刪則只有兩種情況,若鏈表為空直接終止程序.鏈表不為空,使pList指向頭結點指向的空間.

SList.h

void SListPopFront(SListNode** ppHead);

同樣有修改結構體指針的情況,需要用到二級指針

SList.c

// 單鏈表頭刪
void SListPopFront(SListNode** ppHead)
{
    assert(*ppHead);    //鏈表為空

    //鏈表非空
    SListNode* newNode = (*ppHead)->next;   //記錄新的頭結點
    free(*ppHead);      //釋放原頭結點空間
    *ppHead = newNode;  //更新頭結點
}

首先判斷鏈表是否為空,若鏈表為空程序直接結束

接著先記錄新的頭結點,釋放原頭結點空間后,更新頭結點.
同樣兩個操作不可顛倒,否則原頭結點失去位置,造成內(nèi)存泄漏

test.c

void SListTest3()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListPopFront(&pList);
    SListPopFront(&pList);

    SListPrint(pList);

    SListPopFront(&pList);
    SListPopFront(&pList);
    SListPopFront(&pList);

    SListPrint(pList);  

    SListPopFront(&pList);      

    SListPrint(pList);

    SListPopFront(&pList);       //沒有結點

    SListPrint(pList);
    SListDestroy(&pList);
}

int main(void)
{
    SListTest3();

    return 0;
}

測試運行結果如下:

3.7 單鏈表查找 (SListFind)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

從頭依次訪問每一個結點,并與要查找的值進行比較,若找到則直接返回該結點的地址,若找不到則返回空指針.

SList.h

SListNode* SListFind(SListNode* pHead, SLTDateType x);

SList.c

// 單鏈表查找
SListNode* SListFind(SListNode* pHead, SLTDateType x)
{
    SListNode* cur = pHead; //cur訪問每個結點

    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }

    return NULL;
}

test.c

void SListTest4()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListNode* pos;
    pos = SListFind(pList, 3);
    SListPrint(pos);

    pos = SListFind(pList, 6);
    SListPrint(pos);

    pos = SListFind(pList, 8);
    SListPrint(pos);
    SListDestroy(&pList);
}

int main(void)
{
    SListTest4();

    return 0;
}

測試運行結果如下:

3.8 單鏈表在 pos 位置之前插入 (SListInsert)

將pos位置的之前插入分為兩種情況: pos 指向頭結點和其他情況
數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

SList.h

void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType x);

涉及對實參 pList 的修改需要用到二級指針

SList.c

// 單鏈表在 pos 位置之前插入
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType x)
{
	assert(ppHead);
	assert(pos);
	
	SListNode* newNode = BuySListNode(x);	//創(chuàng)建新結點
	
	if (*ppHead == pos)	//如果pos指向第一個結點
	{
		//頭插
		newNode->next = *ppHead;
		*ppHead = newNode;
	}
	else
	{
		SListNode* prev = *ppHead;	//prev用于訪問到pos前一個結點的位置
		
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		
		//插入
		newNode->next = pos;
		prev->next = newNode;
	}
}

首先確保 ppHead 和 pos 值合法

創(chuàng)建新結點后, 判斷 pos 是否指向頭結點, 若指向頭結點, 直接頭插操作就可以了, 注意要使用二級指針以修改實參 pList 的值

若 pos 不指向頭結點, 因為要涉及對 pos 指向結點的前一個結點進行修改, 所以定義 prev 順序訪問單鏈表直至訪問到 pos 指向結點的前一個結點. 這時進行插入操作, 直接修改 newNode 和 prev 的 next 即可

test.c

void SListTest5()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);
	
	SListNode* pos;
	pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListInsert(&pList, pos, -1);
	}
	SListPrint(pList);

	pos = SListFind(pList, 5);
	if (pos != NULL)
	{
		SListInsert(&pList, pos, -5);
	}
	SListPrint(pList);

	pos = SListFind(pList, 10);
	if (pos != NULL)
	{
		SListInsert(&pList, pos, -10);
	}
	SListPrint(pList);
	SListDestroy(&pList);
	
}

int main(void)
{
    SListTest5();

    return 0;
}

測試運行結果如下:

3.9 單鏈表在 pos 位置上刪除 (SListErase)

單鏈表在 pos 位置上刪除, 也是有兩種情況: 刪除的是頭結點和刪除的不是頭結點

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

SList.h

void SListErase(SListNode** ppHead, SListNode* pos);

涉及對實參 pList 的修改需要用到二級指針

SList.c

// 單鏈表在 pos 位置上刪除
void SListErase(SListNode** ppHead, SListNode* pos)
{	
	assert(ppHead);
	assert(pos);

	if (*ppHead == pos)	//如果 pos 指向第一個結點
	{				
		*ppHead = pos->next;
		free(pos);		//釋放空間
	}
	else	//有兩個及以上結點
	{
		SListNode* prev = *ppHead;	//prev 訪問到pos之前的一個結點
		
		while (prev->next != pos)
		{	
			prev = prev->next;
		}
		
		//刪除
		prev->next = pos->next;
		free(pos);
	}
}

首先確保 ppHead 和 pos 的值合法

接著判斷 pos 是否指向頭結點, 如果指向頭結點, 則按照頭刪的方式進行刪除結點

如果 pos 不指向頭結點, 因為需要修改 pos 前面的結點的數(shù)據(jù), 所以定義了變量 prev, 順序訪問單鏈表直至訪問到 pos 位置結點的前一個結點, 直接 prev->next = pos->next

test.c

void SListTest6()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	SListPrint(pList);

	SListNode* pos;
	pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListErase(&pList, pos);
	}
	SListPrint(pList);

	pos = SListFind(pList, 5);
	if (pos != NULL)
	{
		SListErase(&pList, pos);;
	}
	SListPrint(pList);

	pos = SListFind(pList, 10);
	if (pos != NULL)
	{
		SListErase(&pList, pos);
	}
	SListPrint(pList);
	SListDestroy(&pList);
}

int main(void)
{
    SListTest6();

    return 0;
}

測試運行結果如下:

3.10 單鏈表在 pos 位置之后插入 (SListInsertAfter)

直接插入即可, 時間復雜度相比 SListInsert 要少很多
數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

SList.h

void SListInsertAfter(SListNode* pos, SLTDataType x);

SList.c

// 單鏈表在 pos 位置后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);	//確保插入位置合法
	
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

確保 pos 的值合法

注意 newNode->next = pos->next; 和 pos->next = newNode;的順序不可以顛倒, 否則會出現(xiàn) newNode 指向自己的情況

test.c

void SListTest7()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);	
	SListPushBack(&pList, 2);	
	SListPushBack(&pList, 3);	
	SListPushBack(&pList, 4);	
	SListPushBack(&pList, 5);	
	SListPushBack(&pList, 6);	
	SListPrint(pList);
	
	SListNode* pos;
	pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListInsertAfter(pos, -1);
	}
	SListPrint(pList);	
	
	pos = SListFind(pList, 6);
	if (pos != NULL)
	{
 		SListInsertAfter(pos, -6);
	}
	SListPrint(pList);

	pos = SListFind(pList, 10);
	if (pos != NULL)
	{
		SListInsertAfter(pos, -10);
	}
	SListPrint(pList);
    SListDestroy(&pList);
}

int main(void)
{
    SListTest7();

    return 0;
}

測試運行結果如下:

3.11 單鏈表在 pos 位置之后刪除 (SListEraseAfter)

直接改變 pos 位置結點的指向即可, pos 不可指向鏈表結尾

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn)),數(shù)據(jù)結構,數(shù)據(jù)結構

SList.h

void SListEraseAfter(SListNode* pos);

SList.c

// 單鏈表在 pos 位置之后刪除
void SListEraseAfter(SListNode* pos)
{
	assert(pos);	//確保刪除位置合法
	assert(pos->next);
	
	SListNode* deleteNode = pos->next;
	pos->next = deleteNode->next;
	free(deleteNode);
}

確保 pos 和 pos->next 合法

將要刪除的結點命名為 deleteNode, 隨后直接修改 pos 位置的 next, 并釋放空間即可

test.c

void SListTest7()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);	
	SListPushBack(&pList, 2);	
	SListPushBack(&pList, 3);	
	SListPushBack(&pList, 4);	
	SListPushBack(&pList, 5);	
	SListPushBack(&pList, 6);	
	SListPrint(pList);
	
	SListNode* pos;
    pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListEraseAfter(pos);
	}
	SListPrint(pList);

	pos = SListFind(pList, 4);
	if (pos != NULL)
	{
		SListEraseAfter(pos);
	}
	SListPrint(pList);

	pos = SListFind(pList, 6);
	if (pos != NULL)
	{
		SListEraseAfter(pos);
	}
	SListPrint(pList); 
    SListDestroy(&pList);
}

int main(void)
{
    SListTest7();

    return 0;
}

測試運行結果如下:

3.12 單鏈表銷毀 (SListDestroy)

SList.h

void SListDestroy(SListNode** ppHead);

涉及對實參 pList 的修改需要用到二級指針

SList.c

// 單鏈表銷毀
void SListDestroy(SListNode** ppHead)
{
	assert(ppHead);
	
	SListNode* cur = *ppHead;
	
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	
	*ppHead = NULL;
}

順序訪問鏈表并依次釋放結點空間

由此可以看出: 單鏈表更多的還是頭插和頭刪是最便利的, 在后面的復雜數(shù)據(jù)結構中會用到單鏈表, 算法相關筆試題也是單鏈表居多(單鏈表的坑比較多!)

4. 完整代碼

SList.h

#pragma once

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int SLTDataType;
//單鏈表結點結構體
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SListNode;

//動態(tài)申請一個結點
SListNode* BuySListNode(SLTDataType x);
//單鏈表打印
void SListPrint(SListNode* pHead);
//單鏈表尾插
void SListPushBack(SListNode** ppHead, SLTDataType x);
//單鏈表頭插
void SListPushFront(SListNode** ppHead, SLTDataType x);
//單鏈表尾刪
void SListPopBack(SListNode** pHead);
//單鏈表頭刪
void SListPopFront(SListNode** pHead);
//單鏈表查找
SListNode* SListFind(SListNode* pHead, SLTDataType x);
//單鏈表在 pos 位置之前插入
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType x);
//單鏈表在 pos 位置上刪除
void SListErase(SListNode** ppHead, SListNode* pos);
//單鏈表在 pos 位置之后插入
void SListInsertAfter(SListNode* pos, SLTDataType x);
//單鏈表在 pos 位置之后刪除
void SListEraseAfter(SListNode* pos);
//單鏈表的銷毀
void SListDestroy(SListNode** ppHead);

SList.c

#include "SList.h"

// 動態(tài)申請一個結點
SListNode* BuySListNode(SLTDataType x)
{
    SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));

    if (newNode == NULL)
    {
        perror("BuySListNode:");
        exit(-1);
    }

    newNode->data = x;
    newNode->next = NULL;

	return newNode;
}

// 單鏈表打印
void SListPrint(SListNode* pHead)
{
   SListNode* cur = pHead;  //定義一個局部變量指針用來訪問鏈表

   //從頭依次訪問鏈表, cur不為空進入循環(huán)
   while(cur != NULL)
   {
        printf("%d -> ", cur->data);    //打印結構的數(shù)據(jù)域
        cur = cur->next;    //使cur指向下一結點
   }

   printf("NULL\n");
}

// 單鏈表尾插
void SListPushBack(SListNode** ppHead, SLTDataType x)
{
	assert(ppHead);

    SListNode* newNode = BuySListNode(x);   //創(chuàng)建一個新結點

    if(*ppHead == NULL)    //沒有結點, 直接將新結點的地址賦值
    {
        *ppHead = newNode;  //修改結構體指針, 需要用到二級指針
    }
    else    //有結點, 依次訪問直到最后一個元素
    {
        SListNode* tail = *ppHead;  //tail 用于訪問鏈表
        while (tail->next != NULL)
        {
            tail = tail->next;  
        }

        tail->next = newNode;   //修改結構體, 只要用到一級指針
    }
}

// 單鏈表的頭插
void SListPushFront(SListNode** ppHead, SLTDataType x)
{
    SListNode* newNode = BuySListNode(x);   //創(chuàng)建新結點

    newNode->next = *ppHead;    //新結點指向原鏈表第一個結點
    *ppHead = newNode;          //更新頭結點
}

// 單鏈表的尾刪
void SListPopBack(SListNode** ppHead)
{
	assert(ppHead);
    assert(*ppHead);    //沒有結點的情況

    if ((*ppHead)->next == NULL)  //只有一個結點的情況
    {
        free(*ppHead);
        *ppHead = NULL; //修改實參的值需要用到二級指針
    }
    else    //有兩個結點以上的情況
    {
        SListNode* tail = *ppHead;   //tail用來訪問結構體成員

        while (tail->next->next != NULL) //需要修改倒數(shù)第二個結點的值, 則訪問到倒數(shù)第二個結點即停止
        {
            tail = tail->next;
        }

        free(tail->next);  //先釋放最后一個結點的空間
        tail->next = NULL;  //倒數(shù)第二個結點指向NULL
    }
}

// 單鏈表頭刪
void SListPopFront(SListNode** ppHead)
{	
	assert(ppHead);
    assert(*ppHead);    //鏈表為空

    //鏈表非空
    SListNode* newNode = (*ppHead)->next;   //記錄新的頭結點
    free(*ppHead);      //釋放原頭結點空間
    *ppHead = newNode;  //更新頭結點
}

// 單鏈表查找
SListNode* SListFind(SListNode* pHead, SLTDataType x) 
{
    SListNode* cur = pHead; //cur訪問每個結點

    while (cur != NULL)
    {
        if (cur->data == x)
        {
            return cur;
        }
        cur = cur->next;
    }

    return NULL;
}

// 指定位置前插
void SListInsert(SListNode** ppHead, SListNode* pos, SLTDataType x)
{
	assert(ppHead);
	assert(pos);
	
	SListNode* newNode = BuySListNode(x);	//創(chuàng)建新結點
	
	if (*ppHead == pos)	//如果pos指向第一個結點
	{
		//頭插
		newNode->next = *ppHead;
		*ppHead = newNode;
	}
	else
	{
		SListNode* prev = *ppHead;	//prev用于訪問到pos前一個結點的位置
		
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		
		//插入
		newNode->next = pos;
		prev->next = newNode;
	}
}

// 單鏈表在 pos 位置上刪除
void SListErase(SListNode** ppHead, SListNode* pos)
{	
	assert(ppHead);
	assert(pos);

	if (*ppHead == pos)	//如果 pos 指向第一個結點
	{				
		*ppHead = pos->next;
		free(pos);		//釋放空間
	}
	else	//有兩個及以上結點
	{
		SListNode* prev = *ppHead;	//prev 訪問到pos之前的一個結點
		
		while (prev->next != pos)
		{	
			prev = prev->next;
		}
		
		//刪除
		prev->next = pos->next;
		free(pos);
	}
}

// 單鏈表銷毀
void SListDestroy(SListNode** ppHead)
{
	assert(ppHead);
	
	SListNode* cur = *ppHead;
	
	while (cur != NULL)
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	
	*ppHead = NULL;
}

// 單鏈表在 pos 位置后插入
void SListInsertAfter(SListNode* pos, SLTDataType x)
{
	assert(pos);	//確保插入位置合法
	
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}		 

// 單鏈表在 pos 位置之后刪除
void SListEraseAfter(SListNode* pos)
{
	assert(pos);	//確保刪除位置合法
	assert(pos->next);
	
	SListNode* deleteNode = pos->next;
	pos->next = deleteNode->next;
	free(deleteNode);
}

test.c

#include "SList.h"

void SListTest1()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	
	SListPrint(pList);
	
	SListPushFront(&pList, -1);
	SListPushFront(&pList, -2);
	SListPushFront(&pList, -3);
	SListPushFront(&pList, -4);
	SListPushFront(&pList, -5);
	SListPushFront(&pList, -6);
	
	SListPrint(pList);

	SListDestroy(&pList);
}

void SListTest2()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListPopBack(&pList);
    SListPopBack(&pList);

    SListPrint(pList);

    SListPopBack(&pList);
    SListPopBack(&pList);
    SListPopBack(&pList);

    SListPrint(pList);

    SListPopBack(&pList);

    SListPrint(pList);
	
	SListPopBack(&pList);
	
	SListPrint(pList);
	SListDestroy(&pList);
}

void SListTest3()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListPopFront(&pList);
    SListPopFront(&pList);

    SListPrint(pList);

    SListPopFront(&pList);
    SListPopFront(&pList);
    SListPopFront(&pList);

    SListPrint(pList);  

    SListPopFront(&pList);      

    SListPrint(pList);

    SListPopFront(&pList);       //沒有結點

    SListPrint(pList);
	SListDestroy(&pList);
}

void SListTest4()
{
    SListNode* pList = NULL;

    SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);

    SListNode* pos;
    pos = SListFind(pList, 3);
    SListPrint(pos);

    pos = SListFind(pList, 6);
    SListPrint(pos);

    pos = SListFind(pList, 8);
    SListPrint(pos);
	SListDestroy(&pList);
}

void SListTest5()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);
    SListPushBack(&pList, 2);
    SListPushBack(&pList, 3);
    SListPushBack(&pList, 4);
    SListPushBack(&pList, 5);
    SListPushBack(&pList, 6);

    SListPrint(pList);
	
	SListNode* pos;
	pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListInsert(&pList, pos, -1);
	}
	SListPrint(pList);

	pos = SListFind(pList, 5);
	if (pos != NULL)
	{
		SListInsert(&pList, pos, -5);
	}
	SListPrint(pList);

	pos = SListFind(pList, 10);
	if (pos != NULL)
	{
		SListInsert(&pList, pos, -10);
	}
	SListPrint(pList);
	SListDestroy(&pList);
	
}

void SListTest6()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);
	SListPushBack(&pList, 2);
	SListPushBack(&pList, 3);
	SListPushBack(&pList, 4);
	SListPushBack(&pList, 5);
	SListPushBack(&pList, 6);
	SListPrint(pList);

	SListNode* pos;
	pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListErase(&pList, pos);
	}
	SListPrint(pList);

	pos = SListFind(pList, 5);
	if (pos != NULL)
	{
		SListErase(&pList, pos);;
	}
	SListPrint(pList);

	pos = SListFind(pList, 10);
	if (pos != NULL)
	{
		SListErase(&pList, pos);
	}
	SListPrint(pList);
	SListDestroy(&pList);
}

void SListTest7()
{
	SListNode* pList = NULL;
	
	SListPushBack(&pList, 1);	
	SListPushBack(&pList, 2);	
	SListPushBack(&pList, 3);	
	SListPushBack(&pList, 4);	
	SListPushBack(&pList, 5);	
	SListPushBack(&pList, 6);	
	SListPrint(pList);
	
	SListNode* pos;
	pos = SListFind(pList, 1);
	if (pos != NULL)
	{
		SListInsertAfter(pos, -1);
	}
	SListPrint(pList);	
	
	pos = SListFind(pList, 6);
	if (pos != NULL)
	{
 		SListInsertAfter(pos, -6);
	}
	SListPrint(pList);

	pos = SListFind(pList, 10);
	if (pos != NULL)
	{
		SListInsertAfter(pos, -10);
	}
	SListPrint(pList);
	
	pos = SListFind(pList, -1);
	if (pos != NULL)
	{
		SListEraseAfter(pos);
	}
	SListPrint(pList);

	pos = SListFind(pList, 5);
	if (pos != NULL)
	{
		SListEraseAfter(pos);
	}
	SListPrint(pList);

	pos = SListFind(pList, -6);
	if (pos != NULL)
	{
		SListEraseAfter(pos);
	}
	SListPrint(pList); 
	SListDestroy(&pList);
}

int main(void)
{
	//SListTest1();
	//SListTest2();
	//SListTest3();
	//SListTest4();
	//SListTest5();
	//SListTest6();
	SListTest7();


	return 0;
}

本章完.文章來源地址http://www.zghlxwxcb.cn/news/detail-623270.html

到了這里，關于數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn))的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！

国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

Toy模板網(wǎng)

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn))

1. 線性表的鏈式表示: 鏈表

1.1 順序表的優(yōu)缺點

1.2 鏈表的概念

1.3 鏈表的優(yōu)缺點

1.4 鏈表的結構

2. 單鏈表的定義

2.1 單鏈表的結構體

2.2 接口函數(shù)

3. 接口函數(shù)的實現(xiàn)

3.1 動態(tài)申請一個結點 (BuySListNode)

3.2 單鏈表打印 (SListPrint)

3.3 單鏈表尾插 (SListPushBack)

3.4 單鏈表頭插 (SListPushFront)

3.5 單鏈表尾刪 (SListPopBack)

3.6 單鏈表頭刪 (SListPopFront)

3.7 單鏈表查找 (SListFind)

3.8 單鏈表在 pos 位置之前插入 (SListInsert)

3.9 單鏈表在 pos 位置上刪除 (SListErase)

3.10 單鏈表在 pos 位置之后插入 (SListInsertAfter)

3.11 單鏈表在 pos 位置之后刪除 (SListEraseAfter)

3.12 單鏈表銷毀 (SListDestroy)

4. 完整代碼

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

微信掃一掃打賞

支付寶掃一掃領取紅包，優(yōu)惠每天領

二維碼1

二維碼2

數(shù)據(jù)結構: 線性表(無哨兵位單鏈表實現(xiàn))

1. 線性表的鏈式表示: 鏈表

1.1 順序表的優(yōu)缺點

1.2 鏈表的概念

1.3 鏈表的優(yōu)缺點

1.4 鏈表的結構

2. 單鏈表的定義

2.1 單鏈表的結構體

2.2 接口函數(shù)

3. 接口函數(shù)的實現(xiàn)

3.1 動態(tài)申請一個結點 (BuySListNode)

3.2 單鏈表打印 (SListPrint)

3.3 單鏈表尾插 (SListPushBack)

3.4 單鏈表頭插 (SListPushFront)

3.5 單鏈表尾刪 (SListPopBack)

3.6 單鏈表頭刪 (SListPopFront)

3.7 單鏈表查找 (SListFind)

3.8 單鏈表在 pos 位置之前插入 (SListInsert)

3.9 單鏈表在 pos 位置上刪除 (SListErase)

3.10 單鏈表在 pos 位置之后插入 (SListInsertAfter)

3.11 單鏈表在 pos 位置之后刪除 (SListEraseAfter)

3.12 單鏈表銷毀 (SListDestroy)

4. 完整代碼

相關文章

覺得文章有用就打賞一下文章作者

支付寶掃一掃打賞

微信掃一掃打賞

支付寶掃一掃領取紅包，優(yōu)惠每天領

二維碼1

二維碼2

支付寶掃一掃領取紅包，優(yōu)惠每天領