鏈表的使用

雖然有這么多的鏈表的結(jié)構(gòu)，但是我們實(shí)際中最常?還是兩種結(jié)構(gòu)： 單鏈表 和 雙向帶頭循環(huán)鏈表 1. ?頭單向?循環(huán)鏈表：結(jié)構(gòu)簡單，?般不會(huì)單獨(dú)?來存數(shù)據(jù)。實(shí)際中更多是作為其他數(shù)據(jù)結(jié) 構(gòu)的?結(jié)構(gòu)，如哈希桶、圖的鄰接表等等。另外這種結(jié)構(gòu)在筆試?試中出現(xiàn)很多。 2. 帶頭雙向循環(huán)鏈表：結(jié)構(gòu)最復(fù)雜，?般?在單獨(dú)存儲(chǔ)數(shù)據(jù)。實(shí)際中使?的鏈表數(shù)據(jù)結(jié)構(gòu)，都 是帶頭雙向循環(huán)鏈表。另外這個(gè)結(jié)構(gòu)雖然結(jié)構(gòu)復(fù)雜，但是使?代碼實(shí)現(xiàn)以后會(huì)發(fā)現(xiàn)結(jié)構(gòu)會(huì)帶 來很多優(yōu)勢，實(shí)現(xiàn)反?簡單了，后?我們代碼實(shí)現(xiàn)了就知道了。

補(bǔ)充說明：

1、鏈?zhǔn)綑C(jī)構(gòu)在邏輯上是連續(xù)的，在物理結(jié)構(gòu)上不?定連續(xù)

2、節(jié)點(diǎn)?般是從堆上申請的 3、從堆上申請來的空間，是按照?定策略分配出來的，每次申請的空間可能連續(xù)，可能不連續(xù)

SList.h

#pragma once
#define  _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
//定義鏈表節(jié)點(diǎn)的結(jié)構(gòu)
typedef int SLDataType;
typedef struct SListNode{int data;//要保存的數(shù)據(jù)struct SListNode* next;
}SLNode;
//創(chuàng)建節(jié)點(diǎn)組成鏈表并打印鏈表
void SLPrint(SLNode* phead);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushFront(SLNode** pphead, SLDataType x);
//尾刪
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);
//在指定位置之前插入數(shù)據(jù)
void SLInit(SLNode** pphead, SLNode* pos, SLDataType x);
//在指定位置之后插入數(shù)據(jù)
void SLInit(SLNode* pos, SLDataType x);
//找節(jié)點(diǎn)(考慮第一個(gè)參數(shù)為一級(jí)指針還是二級(jí)指針)
//因?yàn)椴桓淖冾^節(jié)點(diǎn)，所以可以傳一級(jí)指針
//但由于代碼一致性原則(保持接口一致性)，應(yīng)該傳二級(jí)指針
void SLFind(SLNode** pphead, SLDataType x);
//刪除pos結(jié)點(diǎn)
void SLErase(SLNode** pphead, SLNode* pos);
//刪除pos之后的結(jié)點(diǎn)
void SLEraseAfter(SLNode** pphead, SLNode* pos);
//銷毀鏈表
void SLDesTory(SLNode** pphead);

SList.c

#define  _CRT_SECURE_NO_WARNINGS 
#include "SList.h"
void SLPrint(SLNode* phead) {//循環(huán)打印、SLNode* pcur = phead;while (pcur) {printf("%d ->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}SLNode* SLBuyNode(SLDataType x) {SLNode* node = (SLNode*)malloc(sizeof(SLNode));node->data = x;node->next = NULL;return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x) {assert(pphead);SLNode* node = SLBuyNode(x);if (*pphead = NULL) {*pphead = node;return;}//鏈表不為空，找尾(定義一個(gè)臨時(shí)變量pcur)SLNode* pcur= *pphead;while (pcur->next) {pcur = pcur->next;}pcur->next = node;
}
void SLPushFront(SLNode** pphead, SLDataType x) {assert(pphead);SLNode* node = SLBuyNode(x);//新節(jié)點(diǎn)跟頭結(jié)點(diǎn)連接起來node->next = *pphead;//plist//讓新的節(jié)點(diǎn)成為頭結(jié)點(diǎn)*pphead = node;
}
void SLPopBack(SLNode** pphead) {assert(pphead);//第一個(gè)節(jié)點(diǎn)不能為空assert(*pphead);//只有一個(gè)節(jié)點(diǎn)的情況if ((*pphead)->next==NULL) {//直接刪除頭結(jié)點(diǎn)free(*pphead);pphead = NULL;return;}//有多個(gè)結(jié)點(diǎn)的情況//找到尾結(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)SLNode* prev = NULL;SLNode* ptail = *pphead;while (ptail->next != NULL) {prev = ptail;ptail = ptail->next;}//prev的next指針不在指向ptail，而是指向ptail的下一個(gè)節(jié)點(diǎn)prev->next = ptail->next;free(ptail);ptail = NULL;
}
void SLPopFront(SLNode** pphead) {assert(pphead);assert(*pphead);SLNode* del = *pphead;*pphead = (*pphead)->next;free(del);del = NULL;
}
void SLInit(SLNode** pphead, SLNode* pos, SLDataType x) {assert(pphead);SLNode* node = SLBuyNode(x);//處理沒有結(jié)點(diǎn)的情況(約定鏈表不能為空+pos也不能為空)assert(pos);assert(*pphead);//處理只有一個(gè)結(jié)點(diǎn)+pos指向第一個(gè)結(jié)點(diǎn)(pos即為第一個(gè)結(jié)點(diǎn))if ((*pphead)->next == NULL||pos==*pphead) {node->next = *pphead;*pphead = node;return;}//找pos的前一個(gè)節(jié)點(diǎn)SLNode* prev = *pphead;while (prev->next != NULL) {prev = prev->next;}prev->next = pos;pos->next = node;
}
//查找第一個(gè)為x的節(jié)點(diǎn)
void SLFind(SLNode** pphead, SLDataType x) {SLNode* pcur = *pphead;while (pcur) {if (pcur->data == x) {return pcur;}pcur = pcur->next;}return NULL;
}
//刪除pos結(jié)點(diǎn)
void SLErase(SLNode** pphead, SLNode* pos) {assert(pphead);assert(*pphead);assert(pos);if (pos == *pphead) {*pphead = (*pphead)->next;free(pos);return;}//找pos的前一個(gè)節(jié)點(diǎn)SLNode* prev = *pphead;while (prev->next!=pos) {prev = prev->next;}prev->next = pos->next;free(pos);pos=NULL;
}
//刪除pos之后的結(jié)點(diǎn)
void SLEraseAfter(SLNode** pphead, SLNode* pos) {assert(pos && pos->next);SLNode* del = pos->next;free(del);del = NULL;
}
//銷毀鏈表
void SLDesTory(SLNode** pphead) {assert(pphead);SLNode* pcur = *pphead;//循環(huán)刪除while (pcur) {SLNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

test.c

#define  _CRT_SECURE_NO_WARNINGS 
//int removeElement(int* nums, int numsSize, int val) {
//	int src, dst;
//	while (src < numsSize) {
//		if (nums[src] == val) {
//			src++;
//		}
//		else {
//			nums[dst] = nums[src];
//			src++;
//			dst++;
//		}
//	}
//	return dst;
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
//	int l1 = m - 1, l2 = n - 1;
//	int l3 = m + n - 1;
//	while (l1 >= 0 && l2 >= 0) {
//		if (nums1[l1] > nums2[l2]) {
//			nums1[l3--] = nums1[l1--];
//		}
//		else {
//			nums1[l3--] = nums2[l2--];
//		}
//	}
//	while (l2 >= 0) {
//		nums1[l3--] = nums2[l2--];
//	}
//}
#include"SList.h"
void slttest() {SLNode* node1 = (SLNode*)malloc(sizeof(SLNode));node1->data = 1;SLNode* node2 = (SLNode*)malloc(sizeof(SLNode));node2->data = 2;SLNode* node3 = (SLNode*)malloc(sizeof(SLNode));node3->data = 3;SLNode* node4 = (SLNode*)malloc(sizeof(SLNode));node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLNode* plist = node1;SLPrint(plist);
}
int main() {slttest();return 0;
}