順序表問題及思考
問題：
- 中間/頭部的插入洗掉，時間復雜度為O(N)
- 增容需要申請新空間，拷貝資料，釋放舊空間，會有不小的消耗，
- 增容一般是呈2倍的增長，勢必會有一定的空間浪費，例如當前容量為100，滿了以后增容到200，
我們再繼續插入了5個資料，后面沒有資料插入了，那么就浪費了95個資料空間，
鏈表的概念及結構
概念：鏈表是一種物理存盤結構上非連續、非順序的存盤結構，資料元素的邏輯順序是通過鏈表中的指標鏈接次序實作的 ，
鏈表是單獨存盤資料通過指標指向下一個地址，
鏈表的分類
帶哨兵位的頭節點不存資料，
總共有八種結構，但我們最常用的有無頭單項非回圈鏈表和有頭雙項回圈鏈表
列印鏈表節點資料
void SListPrint(SLTNode* plist)
{
SLTNode* cur = plist;
while (cur != NULL)
{
printf("%d "cur->data);
cur = cur->next;
}
printf("\n");
}
建立一個新的節點
SLTNode *BuySLTNode(SLTDataType x)
{
SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));
node->data = x;
node->next = NULL;
}
先用Malloc動態開辟空間，然后創建新的節點
尾插
void SListPushBack(SLTNode** plist, SLTDataType x)
{
if (plist == NULL)
{
plist = newnode;
}
else
{
SLTNode* tail = plist;
while (tail->next != NULL)
{
tail = tail->next;
}
SListNode *newnode = BuySLTNode(x);
tail->next = newnode;
}
}
由于我們是對指標進行改變，所以用來接收的是二級指標，
要記得判斷剛開始就是空指標的情況，
頭插
void SListPushFront(SLTNode** pplist, SLTDataType x)
{
SLTNode* newnode = BuySLTNode(x);
newnode->next = *pplist;
*pplist = newnode;
}
由于對一級指標進行改變，所以用來接收的是二級指標，
尾刪
void SListPopBack(SLTNode* plist)
{
if (*pplist == NULL)
{
return;
}
else if ((*pplist)->next == NULL)
{
free(*pplist);
*pplist = NULL;
}
else
{
SLTNode* prev = NULL;
SLTNode* tail = plist;
while (tail->next != NULL)
{
prev = tail;
tail = tail->next;
}
free(tail);
tail = NULL;
prev->next = NULL;
}
}
要分情況，沒有節點，一個節點和多個節點的情況，
頭刪
void SListPopFront(SLTNode ** pplist)
{
if (*pplist == NULL)
{
return;
}
else
{
SLTNode* next = (*pplist)->next;
free(*pplist);
*pplist = next;
}
}
頭刪要記得先保存下一個，再把開頭的free掉，
查找
void SLTNode* SListFinde(SLTNode* plist, SLTDataType x)
{
SLTNode* cur = plist;
while (cur)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
}
任意位置前插入
void SListInsert(SLTNode* plist, SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
if (pos == *pplist)
{
newnode->next = pos;
*pplist = newnode;
}
SLTNode* prev = NULL;
SLTNode* cur = plist;
while (cur != pos)
{
prev = cur;
cur = cur->next;
}
prev->next = newnode;
newnode->next = pos;
}
要注意考慮頭節點的情況，
任意位置后插入
void SListInsertAfter(SLTNode* pos, SLTDataType x)
{
assert(pos);
SLTNode* newnode = BuySLTNode(x);
pos->next = newnode;
newnode->next = pos->next;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/277082.html
標籤：其他
上一篇：Ajax的基礎原理和簡單封裝