icp網(wǎng)站備案系統(tǒng)中國最好的營銷策劃公司
鏈表的使用
雖然有這么多的鏈表的結(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;
}