做平臺的網(wǎng)站有哪些云南seo網(wǎng)絡(luò)優(yōu)化師
1.鏈表的概念及結(jié)構(gòu)
? ? ? ? 鏈表是?種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表
中的指針鏈接次序?qū)崿F(xiàn)的。
2. 順序表帶來的問題
(1)中間/頭部的插?刪除，時間復(fù)雜度為O(N)
(2)增容需要申請新空間，拷?數(shù)據(jù)，釋放舊空間。會有不?的消耗。
(3)增容?般是呈2倍的增?，勢必會有?定的空間浪費(fèi)。例如當(dāng)前容量為100，滿了以后增容到 200，我們再繼續(xù)插?了5個數(shù)據(jù)，后?沒有數(shù)據(jù)插?了，那么就浪費(fèi)了95個數(shù)據(jù)空間。
? Ps：單鏈表的好處就是比順序表結(jié)構(gòu)簡單，節(jié)省內(nèi)存空間，隨時申請內(nèi)存隨時使用。鏈表其實(shí)就是由節(jié)點(diǎn)組成的，節(jié)點(diǎn)中存儲數(shù)據(jù)+指向下一節(jié)點(diǎn)的位置指針。
3.單鏈表實(shí)現(xiàn)頭部、尾部、任意位置增加刪除節(jié)點(diǎn)、銷毀鏈表等操作
//SList.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDataType;//定義節(jié)點(diǎn)中的數(shù)據(jù)類型
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//定義節(jié)點(diǎn)的結(jié)構(gòu)體數(shù)據(jù)，以及下一結(jié)構(gòu)體節(jié)點(diǎn)的（指針）地址，然后重命名為 SLTNodevoid SLTPrint(SLTNode* phead);//打印節(jié)點(diǎn)數(shù)據(jù)void SLTPushBack(SLTNode** pphead);//尾插void SLTPushFront(SLTNode** pphead);//頭插void SLTPopBack(SLTNode** pphead);//尾刪void SLTPopFront(SLTNode** pphead);//頭刪SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//查找void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之前插入數(shù)據(jù)void SLTInsertAfter(SLTNode* pos, SLTDataType x);//在指定位置之后插入數(shù)據(jù)void SLTErase(SLTNode** pphead, SLTNode* pos);//刪除pos(指定位置)節(jié)點(diǎn)void SLTEraseAfter(SLTNode* pos);//刪除pos之后的節(jié)點(diǎn)void SListDesTroy(SLTNode** pphead);//銷毀鏈表//SList.c#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void SLTPrint(SLTNode* phead)//打印節(jié)點(diǎn)數(shù)據(jù)
{while (phead) //從第一個節(jié)點(diǎn)開始遍歷，遇到NULL結(jié)束{printf("%d->", phead->data);phead=phead->next;}printf("NULL\n");
}SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* NEWNode = (SLTNode*)malloc(sizeof(SLTNode)); //內(nèi)存分配時一定要注意寫規(guī)范sizeof(SLTNode)=8不要寫為sizeof(SLTNode*)=4, 大小就不一樣肯定就會報(bào)錯，分配了一個指向 SLTNode 的指針的內(nèi)存，而不是分配一個 SLTNode 本身的內(nèi)存。if (NEWNode == NULL){perror("malloc");exit(1);}NEWNode->data = x;NEWNode->next = NULL;return NEWNode;
}
void SLTPushBack(SLTNode** pphead, SLTDataType x)//尾插
{assert(pphead);if (*pphead==NULL)//*pphead代表指向第一個節(jié)點(diǎn)的指針，如果是“空鏈表”進(jìn)行尾插{*pphead = SLTBuyNode(x);}else //如果是“非空鏈表”進(jìn)行尾插{ SLTNode* ptail = *pphead;while (ptail->next) //從第一個節(jié)點(diǎn)開始遍歷，判斷指向下一個節(jié)點(diǎn)的指針是否為NULL 不能判斷當(dāng)前節(jié)點(diǎn)是否為空while (ptail) 進(jìn)行結(jié)束循環(huán)，這不能代表下一節(jié)點(diǎn)是NULL{ptail = ptail->next;}//此時此刻ptail已經(jīng)是尾節(jié)點(diǎn)了,ptail->next=NULLptail->next = SLTBuyNode(x); }
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)//頭插
{assert(pphead);// *pphead代表指向第一個節(jié)點(diǎn)的指針，如果是“空鏈表”進(jìn)行頭插SLTNode* pur = SLTBuyNode(x);pur->next = *pphead;*pphead = pur;
}void SLTPopBack(SLTNode** pphead)//尾刪
{assert(pphead && *pphead);//鏈表不能為空//如果鏈表只有一個節(jié)點(diǎn) // ->優(yōu)先級高于*所以要加上（）if ((*pphead)->next == NULL) {free(*pphead);*pphead = NULL;}//如果鏈表有多個節(jié)點(diǎn)else{SLTNode* prev = *pphead; //保存末尾的上一個節(jié)點(diǎn)的地址,目的是等釋放末尾節(jié)點(diǎn)后，使上一個節(jié)點(diǎn)的指向地址為NULL（prev->next= NULL;）SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next= NULL;}
}void SLTPopFront(SLTNode** pphead)//頭刪
{assert(pphead && *pphead);//如果鏈表只有一個節(jié)點(diǎn)//if ((*pphead)->next == NULL)//{// free(*pphead);// *pphead = NULL;//}//else//如果鏈表有多個節(jié)點(diǎn)//{// SLTNode* Nextnode = *pphead;// *pphead = Nextnode->next;//}//通用//方案一//SLTNode* Nextnode = *pphead;//*pphead = Nextnode->next;//方案二SLTNode* Nextnode = (*pphead)->next;free(*pphead);*pphead = Nextnode;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//查找
{//assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){printf("找到了！\n");return pcur;//找到了}pcur = pcur->next;}return NULL;//沒找到
}//在指定位置之前插入數(shù)據(jù)
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* pcur = *pphead;SLTNode* newnode = SLTBuyNode(x);//申請一個空間，存儲要插入的節(jié)點(diǎn)if (pos == *pphead){SLTPushFront(pphead, x);//頭插}else{while (pcur->next != pos){pcur = pcur->next;}//pcur->newnode->posnewnode->next = pos;pcur->next = newnode;}
}//在指定位置之后插入數(shù)據(jù)
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);newnode->next = pos->next;pos->next= newnode;
}//刪除pos(指定位置)節(jié)點(diǎn)
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);SLTNode* prev = *pphead;if (*pphead == pos)//執(zhí)行頭刪{SLTPopFront(pphead);}else{while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//刪除pos之后的節(jié)點(diǎn)
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* after = pos->next;pos->next = pos->next->next;free(after);after = NULL;
}//銷毀鏈表
void SListDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* Nextnode = pcur->next;free(pcur);pcur = Nextnode;}*pphead = NULL;
}//SeqList-test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"void SList_test()
{//給節(jié)點(diǎn)里創(chuàng)建數(shù)據(jù)SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));//內(nèi)存分配時一定要注意寫規(guī)范sizeof(SLTNode)=8不要寫為sizeof(SLTNode*)=4, 大小就不一樣肯定 就會報(bào)錯，分配了一個指向 SLTNode 的指針的內(nèi)存，而不是分配一個 SLTNode 本身的內(nèi)存。node4->data = 4;//給節(jié)點(diǎn)之間建立聯(lián)系node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;//調(diào)用鏈表打印SLTNode* plist = node1;//SLTNode* plist = NULL; //SLTPushBack(NULL, 5);//尾插//SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)SLTPushBack(&plist, 5);//尾插SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)SLTPushFront(&plist, 0);//頭插SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)SLTPopBack(&plist);//尾刪SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)SLTPopFront(&plist);//頭刪SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)}void SList_test1()
{SLTNode* plist = NULL; SLTPushBack(&plist, 1);//尾插SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)SLTPushBack(&plist, 2);//尾插SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)SLTPushBack(&plist, 3);//尾插SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)//SLTPushFront(&plist, 0);//頭插//SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)//SLTPopBack(&plist);//尾刪//SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)//SLTPopFront(&plist);//頭刪//SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)//SLTFind(plist,1);//查找//SLTFind(plist, 3);//查找SLTNode* find=SLTFind(plist, 3);//查找位置SLTInsert(&plist, find, 0);//在指定位置之前插入數(shù)據(jù)SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù) 1->2->0->3->NULLfind = SLTFind(plist, 2);//查找位置SLTInsertAfter(find, 4);//在指定位置之后插入數(shù)據(jù)SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù) 1->2->4->0->3->NULLfind = SLTFind(plist, 3);//查找位置SLTErase(&plist, find);//刪除pos(指定位置)節(jié)點(diǎn)SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù) 1->2->4->0->NULLfind = SLTFind(plist, 4);//查找位置SLTEraseAfter(find);SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù) 1->2->4->NULLSListDesTroy(&plist);//銷毀鏈表SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)//SLTPushBack(&plist, 1);//尾插//SLTPrint(plist);//打印節(jié)點(diǎn)數(shù)據(jù)
}int main()
{//SList_test();SList_test1();//printf("%zd %zd", sizeof(SLTNode), sizeof(SLTNode*)); //8, 4return 0;
}