鏈式存儲的定義
鏈式存儲為了表示數(shù)據(jù)元素與其直接后繼元素間的邏輯關(guān)系凌摄，數(shù)據(jù)元素除了存儲本身的信息外，還需要存儲直接后繼的信息。相連的數(shù)據(jù)元素之間在存儲空間中不要求連續(xù)狈惫。
鏈式存儲的邏輯結(jié)構(gòu)
基于鏈式存儲結(jié)構(gòu)的線性表中，每個節(jié)點都包含數(shù)據(jù)域和指針域鹦马。數(shù)據(jù)域用于存儲數(shù)據(jù)元素本身胧谈，指針域用于存儲相鄰節(jié)點的地址。
一個完整的鏈表需要由以下幾部分構(gòu)成：
- 頭指針：
一個普通的指針荸频，它的特點是永遠指向鏈表第一個節(jié)點的位置菱肖。很明顯，頭指針用于指明鏈表的位置旭从，便于后期找到鏈表并使用表中的數(shù)據(jù)稳强； - 節(jié)點：
鏈表中的節(jié)點又細分為頭節(jié)點、首元節(jié)點和其他節(jié)點：
頭節(jié)點：
其實就是一個不存任何數(shù)據(jù)的空節(jié)點和悦，通常作為鏈表的第一個節(jié)點退疫。對于鏈表來說，頭節(jié)點不是必須的鸽素，它的作用只是為了方便解決某些實際問題褒繁；
線性表的基本操作方式
LinkList(); //構(gòu)造函數(shù)，初始化線性表
virtual ~LinkList(); //析構(gòu)函數(shù)馍忽。銷毀線性表
void ClearList(); //清空線性表
bool listisEmpty(); //判斷線性表是否為空
int ListLength(); //獲取線性表的長度
bool GetElem(int i,Node *pNode); //獲取指定元素
int LocateElem(Node *pNode); //尋找第一個滿足的數(shù)據(jù)元素的位序
bool PriorElem(Node *pcurrentNode,Node *pPreNode); //獲取指定節(jié)點的前驅(qū)
bool NextElem(Node *pcurrentNode,Node *pNextNode); //后去指定節(jié)點的后驅(qū)
bool ListInsert(int i,Node *pNode); //在指定位置插入節(jié)點
bool ListDelete(int i,Node *pNode); //刪除指定位置的節(jié)點
bool ListInsertHead(Node *pNode); //在頭節(jié)點插入新的節(jié)點
bool ListInsrtTail(Node *pNode); //在尾節(jié)點插入新的節(jié)點
void ListTraverse();
在頭節(jié)點插入新的節(jié)點操作
在鏈表頭節(jié)點插入新節(jié)點存在兩種情況
1棒坏、鏈表本身是空表
- 即鏈表的新節(jié)點的next指針會指向null，然后操作LinkedList對象的頭指針指向新的節(jié)點遭笋，完成鏈表頭節(jié)點插入新節(jié)點動作坝冕。
2、鏈表本身已含其他節(jié)點
- 即鏈表的新節(jié)點的next指針會指向LinkedList對象的頭指針指向的節(jié)點坐梯，然后操作LinkedList對象的頭指針指向新的節(jié)點徽诲，完成鏈表頭節(jié)點插入新節(jié)點動作。
//在鏈表的頭部插入結(jié)點
bool LinkList::ListInsertHead(Node *pNode)
{
Node *temp = m_pList->next; //將頭節(jié)點保存一個新的臨時節(jié)點中
Node *newNode = new Node; //堆中申請內(nèi)存
if(newNode == NULL)
{
return false;
}
newNode->data = pNode->data;
m_pList->next = newNode; //頭節(jié)點指向新申請的節(jié)點
newNode->next = temp; //新申請的節(jié)點指針域
m_iLength++;
return true;
}
在末端插入元素操作
將要插入的節(jié)點放在鏈表中最后一個節(jié)點吵血，因此該節(jié)點的next指針需要指向NULL
//在鏈表的尾部插入結(jié)點
bool LinkList::ListInsrtTail(Node *pNode)
{
Node *currentNode = m_pList;
while(currentNode ->next != NULL) //遍歷最后一個節(jié)點
{
currentNode = currentNode->next;
}
Node *newNode = new Node; //堆中申請內(nèi)存
if(newNode == NULL)
{
return false;
}
//最后一個節(jié)點的next指向新創(chuàng)建的節(jié)點谎替。
newNode->data = pNode->data; //
newNode->next = NULL; //指向空作為最后一個節(jié)點
currentNode->next = newNode;
m_iLength++; //鏈表長度加一
return true;
}
往鏈表中的任意位置插入新節(jié)點操作
插入新節(jié)點操作需遍歷到第i-1個節(jié)點,插入前需要將一個臨時指針副本偏移到指定索引的位置，第i-1個位置的節(jié)點的next指針需要指向新的節(jié)點蹋辅，新的節(jié)點的next指針需要指向原來第i-1個位置的節(jié)點的next指針
//往鏈表中任意位置插入節(jié)點
bool LinkList::ListInsert(int i,Node *pNode)
{
if(i < 0 || i > m_iLength) return false;
Node *currentNode = m_pList;//找到頭結(jié)點并保存到currentNode
for(int j = 0;j<i;j++) //遍歷到第i-1個節(jié)點,因為插入前需要將一個臨時指針副本偏移到指定索引的位置,需要注意的
{
currentNode = currentNode->next;
}
Node *newNode = new Node;
if(newNode == NULL)
{
return false;
}
newNode->data = pNode->data; //賦值
newNode->next = currentNode->next; //原來currentNode的下一個節(jié)點變成了newNode的下一個節(jié)點
currentNode->next = newNode; //再把newNode成為urrentNode的下一個節(jié)點
m_iLength++;
return true;
}
鏈表中刪除節(jié)點
此時與插入節(jié)點操作不同的最大不同的是遍歷到第i個節(jié)點钱贯，因為對于單向鏈表來說,一但我們的遍歷的指針位于第i個節(jié)點時已經(jīng)無法返回到位于i-1位置的節(jié)點，此時我們將位于第i個位置的節(jié)點執(zhí)行delete操作侦另，那么第i-1個位置的節(jié)點與第k+1個位置的節(jié)點本應(yīng)要建立的鏈接關(guān)系已經(jīng)無法建立秩命，那么從第k+1個位置的節(jié)點算起的部分與鏈表就“斷鏈”尉共，造成鏈表內(nèi)存泄漏。
bool LinkList::ListDelete(int i,Node *pNode)
{
if(i < 0 || i >= m_iLength) return false;
Node *currentNode = m_pList;//找到頭結(jié)點并保存到currentNode
Node *currentNodeBefore = NULL;
for(int j = 0;j<=i;j++) //遍歷到第i個節(jié)點
{
currentNodeBefore = currentNode; //臨時指針副本偏移到指定索引的第i個位置
currentNode = currentNode->next; //遍歷操作
}
currentNodeBefore->next = currentNode->next;
pNode->data = currentNode->data;
delete currentNode;
currentNode = NULL;
m_iLength--;
return true;
}
清空鏈表操作
清空鏈表弃锐，我們從頭鏈表的頭部元素一直遍歷到鏈表的末端,遍歷過程中,在每次循環(huán)偏移鏈表的頭指針時,我們需要一個臨時指針變量來緩存前一個節(jié)點然后對其執(zhí)行內(nèi)存釋放操作袄友。
//清空鏈表操作
void LinkList::ClearList()
{
//刪除節(jié)點
Node *currentNode = m_pList->next ;
while( currentNode != NULL)
{
Node *temp = currentNode->next;
delete currentNode;
currentNode = temp;
}
m_pList ->next =NULL;
}
