線性表的鍊式存儲

文章目錄

• 一，連結清單的定義與分類
• 二，單連結清單的插入與删除
• 三，雙向連結清單的插入與删除

一，連結清單的定義與分類

二，單連結清單的插入删除

三，雙向連結清單的插入與删除

一，連結清單的定義與分類

順序存儲表在進行操作的時候特别費時間

為了改變這一缺點，引入了鍊式存儲

單連結清單：

單連結清單的邏輯次序和實體次序不一定一緻 連結清單用一組任意的存儲單元來放線性表的結點 存儲單元可以連續也可非連續

每個線性連結清單的結點隻有一個next指針域，是以為單連結清單

二，單連結清單的插入與删除

插入：

在帶頭結點的單連結清單L中第i個位置前插入一個元素的過程分為三部分

1，查找：
在單連結清單中找到第i-1個結點并由指針pre提示
2，申請：
申請新結點s，将資料域的值置為e
3，插入挂鍊：
通過修改指針域将新結點s挂入單連結清單L
           

主要代碼如下：

s = (Node *) malloc(sizeof(Node))   /申請一個新結點/
s - > data = e 
s - >next = pre - > next  /修改指針，完成插入操作/
pre - > next = s

           

删除：

比如要删除第i個結點，過程分為兩步：

1，查找 通過計數方式找到第i-1個結點并由指針pre訓示

2，删除 删除第i個結點并釋放結點空間 主要

代碼如下：
r = pre -> next
pre -> next= pre-> next -> next
free(r)


           

三，雙向連結清單的插入與删除

為了讓查找删除等操作的時間變得更短，引入了雙向連結清單

每個結點不僅有後繼指針，還有前驅指針，為某些運算提供了很大的便利

結構定義如下：

typedef struct DNode
{   ElemType data ;
    struct DNode * prior, *next;
}DNode , * DoubleList;
           

插入：

主要算法如下：
t->prior=p;
t->next=p->next;
p->next->prior=t;
p->next=t;
           

删除：

主要算法如下：
p->prior->next=p->next;  //p前驅結點的後鍊指向p的後繼結點
p->next->prior=p->prior; //p後繼節點的前鍊指向p的前驅結點
free(p) ；               //釋放*p的空間
                        "前兩行的語句可以颠倒"