Ⅰ 鏈表的定義
定義 ： 鏈表 是一種物理存儲單元上 非連續、非順序 的存儲結構，由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。
在鏈表的儲存上，每個結點不僅包含所存的元素信息，還包含元素間的 邏輯信息 。
在每個結點除了包含的數據域外，還包明指山含一個 指針域 ，用以指向其後繼結點。
帶頭結點的單鏈表中， 頭指針head 指向頭結點，頭結逗蘆點的值域不含任何信息，從頭結點的後繼結點開始儲存信息。頭指針head 始終 不等於NULL ， head->next 等於NULL的時候，鏈表為空。
不帶頭結點的單鏈表中的 頭指針head 直接指向開始結點，當head等於NULL時，鏈表為空。
雙鏈表就是在單鏈表結點上增添了一個指針域，指向當前節點的 前驅 。
相比於單鏈表，雙鏈表能夠從 終端結點 反向走到 開始結點 。
只需要將單鏈表 最後一個 指針域（ 空指針 ）指向鏈表中的 第一個結點 即可。（如果循環單鏈表帶頭結點，則指向頭結點；不帶頭結點，則指向開始結點）。
循環單鏈表可以實現從 任何一個結點 出發，訪問鏈表中任何結點。（注意：此處應該區分與順序表隨機訪問的特點。循環單鏈表指的是從一個結點出發，而不是知道一個結點從而迅速找到任何一個結點，因此循環單鏈表 不具有 隨機訪問特性。）
帶頭結點 的循環單鏈表，當 head 等於 head->next 時，鏈表為空； 不帶頭結點 的循環單鏈表，當 head 等於 NULL 時，鏈表為空。
雙鏈表 終端節點的next指針 指向鏈表中第一個結點，將鏈表中的第一個結點的 prior指針 指向終端結點。
不帶頭結點 的循環雙鏈激中表， head 等於 NULL ，鏈表為空
帶頭結點 的循環雙鏈表是沒有空指針的，其為空狀態下， head->next 與 head->prior 必然都等於 head ，故一下四種語句都可判斷為空
靜態鏈表藉助 一維數組 表示。
靜態鏈表結點空間來自於一個 結構體數組 （一般鏈表結點空間來自整個內存），數組中每個結點含兩個分量：
注意：靜態鏈表的指針不是通常所說儲存內存地址的指針型變數，而是儲存數組下標的整型變數，其功能類似於指針，故在此稱為指針
順序表儲存空間時一次性分配的，鏈表的是多次分配的
（註： 存儲密度 = 結點值域所佔存儲量/結點結構所佔存儲總量 ）
順序表存儲密度 = 1
鏈表存儲密度 < 1
順序表可以 隨機存取 ，也可以 順序存取
鏈表只能 順序存取
順序表平均需要移動一半元素
鏈表不需要移動元素，僅需 修改指針
Ⅱ 單雙向鏈表原理
雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。
1鏈表操作編輯
雙向鏈表
雙向鏈表
線性表的雙向鏈表存儲結構：
帶頭結點的雙向循環鏈表的基本操作：
銷毀雙向循環鏈表L：
重置鏈表為空表：
驗證是否為空表：
2元素操作編輯
計算表內元素個數
賦值：
查找元素：
查找元素前驅：
查找元素後繼：
查找元素地址：
元素的插入：
元素的刪除：
正序查找：
逆序查找：
3循環鏈表編輯
循環鏈表是一種鏈式存儲結構，它的最後一個結點指向頭結點，形成一個環。因此，從循環鏈表中的任何一個結點出發都能找到任何其他結點。循環鏈表的操作和單鏈表的操作基本一致，差別僅僅在於演算法中的循環條件有所不同。
Ⅲ 雙向循環鏈表的主要優點
雙向鏈表的每個數據結點中都有兩個指針，分別指向直接後繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和後繼結點。一般我們都構造雙向循環鏈表。
單鏈表的缺點是只能往前，不能後退，雖然有循環單鏈表，但後退的成本還是很高的，需要跑一圈。在這個時候呢，雙向鏈表就應運而生了，再加上循環即雙向循環鏈表就更加不錯了。所謂雙向鏈表只不過是添加了一個指向前驅結點的指針，雙向循環鏈表是將最後一個結點的後繼指針指向頭結點。
(3)循環雙鏈表的存儲結構擴展閱讀：
循環鏈表是一種鏈式存儲結構，它的最後一個結點指向頭結點，形成一個環。因此，從循環鏈表中的任何一個結點出發都能找到任何其他結點。循環鏈表的操作和單鏈表的操作基本一致，差別僅僅在於演算法中的循環條件有所不同。
單向鏈表（單鏈表）其特點是鏈表的鏈接方向是單向的，對鏈表的訪問要通過順序讀取從頭部開始。 通過指針連接起來，但是只能單向遍歷的內存塊。由於它是單向的，或者說不可逆的，所以我們可以把它比作人生：小學->中學->大學->工作->養老。
Ⅳ 線性表- 鏈式存儲結構- 循環鏈表
循環鏈表(Circular Linked List)
循環鏈表是一種首尾相接的鏈表
循環鏈表
( )單循環鏈表 ——在單鏈表中 將終端結點的指針域NULL改為指向表頭結點或開始結點即可
( )多重鏈的循環鏈表 ——將表中結點鏈在多個環上
帶頭結點的單循環鏈搏畝表
注意
判斷空鏈表的條件是head==head >胡森next;
僅設尾指針的單循環鏈表
用尾指針rear表示的單循環鏈表對開始結點a 和終端結點a n 查找時間都是O( ) 而表的操作常常是在表的首尾位置上進行 因此 實用中多採用尾指針表示單循環鏈表 帶尾指針的單循環鏈表可見下圖
注意
判斷空鏈表的條件為rear==rear >next;
循環鏈表的特點
循環鏈表的特點是無須增加存儲量 僅對表的鏈接方式稍作改變 即可使得表處理更加方便靈活
【例】在鏈表上實現將兩個線性表(a a … a n )和(b b … b m )連接成一個線性表(a … a n b …b m )的運算
分析 若在單鏈表或頭指針表示的單循環表上做這種鏈接操作 都需要遍歷第一個鏈表 找到結點a n 然後將結點b 鏈到a n的後面 其執行時間是O(n) 若在尾指針表示的單循環鏈表上實現 則只需修基做森改指針 無須遍歷 其執行時間是O( )
相應的演算法如下
LinkList Connect(LinkList A LinkList B)
{//假設A B為非空循環鏈表的尾指針
LinkList p=A >next;//①保存A表的頭結點位置
A >next=B >next >next;//②B表的開始結點鏈接到A表尾
free(B >next);//③釋放B表的頭結點
B >next=p;//④
return B;//返回新循環鏈表的尾指針
}
注意
①循環鏈表中沒有NULL指針 涉及遍歷操作時 其終止條件就不再是像非循環鏈表那樣判別p或p >next是否為空 而是判別它們是否等於某一指定指針 如頭指針或尾指針等
②在單鏈表中 從一已知結點出發 只能訪問到該結點及其後續結點 無法找到該結點之前的其它結點 而在單循環鏈表中 從任一結點出發都可訪問到表中所有結點 這一優點使某些運算在單循環鏈表上易於實現
lishixin/Article/program/sjjg/201311/23305
Ⅳ 如何建立雙向循環鏈表並輸入數據
至少需要一個元素，空的不能能建立數據結構。
1.循環鏈表
循環鏈表是與單鏈表一樣，是一種鏈式的存儲結構，所不同的是，循環鏈表的最後一個結點的指針是指向該循環鏈表的第一個結點或者表頭結點，從而構成一個環形的鏈。循環鏈表的運算與單鏈表的運算基本一致。所不同的有以下幾點：
1)在建立一個循環鏈表時，必須使其最後一個結點的指針指向表頭結點，而不是象單鏈表那樣置為NULL。此種情況還使用於在最後一個結點後插入一個新的結點。
2)在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域值等於表頭指針時，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。
2.雙向鏈表
雙向鏈表其實是單鏈表的改進。
當我們對單鏈表進行操作時，有時你要對某個結點的直接前驅進行操作時，又必須從表頭開始查找。這是由單鏈表結點的結構所限制的。因為單鏈攜銀表每個結點只有一個存儲直接後繼結點地址的鏈域，那麼能不能定義一個既有存儲直接後繼結點地址的鏈域，又有存儲直接前驅結點地址的鏈域的這樣一個雙鏈域結點結構呢？這就是雙向鏈表。
3.雙向循環鏈表常式:
#include <stdio.h>
#include <stdlib.h>
typedef struct tagDbNode
{
int data;
struct tagDbNode * left;
struct tagDbNode * right;
} DbNode, * pdbNode;
//創建結點
pdbNode CreateNode(int data)
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
pnode->data = data;
pnode->left = pnode->right = pnode; //創建新結點時，辯悄宴讓其前驅和後繼指針都指向自身
return pnode;
}
//創建鏈表
pdbNode CreateList(int head) //參數給出表頭結點數據 （表頭結點不作為存放有意義數據的結點）
{
pdbNode pnode = (pdbNode)malloc(sizeof(DbNode));
pnode->data = head;
pnode->left = pnode->right = pnode;
return pnode;
}
//插入新結點,總是在表尾插入; 返回表頭結點
pdbNode InsertNode(pdbNode node, int data) // 參數1是鏈表的表頭結點，參數2是要插入的結點（結
點數據為data）
{
pdbNode pnode = CreateNode(data);
// 從左到右恢復鏈接
node->left->right = pnode;
pnode->right = node;
//運稿 從右到左恢復鏈接
pnode->left = node->left;
node->left = pnode;
return node;
}
//查找結點，成功則返回滿足條件的結點指針，否則返回NULL
pdbNode FindNode(pdbNode node, int data) // 參數1是鏈表的表頭結點，參數2是要查找的結點（其中
結點數據為data）
{
pdbNode pnode = node->right;
while (pnode != node && pnode->data != data)
{
pnode = pnode->right;
}
if (pnode == node) return NULL;
return pnode;
}
//刪除滿足指定條件的結點, 返回表頭結點, 刪除失敗返回NULL（失敗的原因是不存在該結點）
pdbNode DeleteNode(pdbNode node, int data) // 參數1是鏈表的表頭結點，參數2是要刪除的結點（其
中結點數據為data）
{
pdbNode pnode = FindNode(node, data);
if (NULL == pnode) return NULL;
pnode->left->right=pnode->right;
pnode->right->left=pnode->left;
free(pnode);
return node;
}
//獲取鏈表的長度
int GetLength(pdbNode node) // 參數為鏈表的表頭結點
{
int nCount = 0;
pdbNode pnode = node->right;
while (pnode!= node)
{
pnode = pnode->right;
nCount++;
}
return nCount;
}
//順序列印整個鏈表
void PrintList(pdbNode node) // 參數為鏈表的表頭結點
{
pdbNode pnode;
if (NULL == node) return;
pnode= node->right;
while (pnode != node)
{
printf("%d ", pnode->data);
pnode = pnode ->right;
}
printf("\n");
}
//將鏈表反序列印
void ReverPrint(pdbNode node) //參數為鏈表的表頭結點
{
pdbNode pnode;
if (NULL == node) return;
pnode= node->left;
while (pnode != node)
{
printf("%d ", pnode->data);
pnode = pnode->left;
}
printf("\n");
}
//刪除鏈表
void DeleteList(pdbNode node) //參數為鏈表表頭結點
{
pdbNode pnode = node->right;
pdbNode ptmp;
if (NULL == node) return;
while (pnode != node)
{
ptmp = pnode->right;
free(pnode);
pnode = ptmp;
}
free(node);
}
//測試程序
#include <stdio.h>
#include <stdlib.h>
#include "dblist.h"
#define FALSE 0
#define TRUE 1
typedef unsigned int bool;
void main()
{
int nChoose;
int data;
bool bFlag = FALSE;
pdbNode pnode;
pdbNode list = CreateList(0);
while(bFlag == FALSE)
{
printf("Main Menu\n");
printf("1. Insert\n");
printf("2. Delete Node\n");
printf("3. Find\n");
printf("4. Length\n");
printf("5. Positive Print\n");
printf("6. Negative Print\n");
printf("7. Delete List\n");
printf("0. quit\n\n");
scanf("%d", &nChoose);
switch(nChoose)
{
case 1:
printf("Input the data to insert:");
scanf("%d", &data);
list = InsertNode(list, data);
PrintList(list);
printf("\n");
break;
case 2:
printf("Input the data to delete: ");
scanf("%d", &data);
DeleteNode(list, data);
PrintList(list);
printf("\n");
break;
case 3:
printf("Input the data to find: ");
scanf("%d", &data);
pnode = FindNode(list, data);
if (NULL != pnode)
{
printf("Find succeed!\n");
printf("\n");
}
else
{
printf("Find failed!\n");
printf("\n");
}
break;
case 4:
printf("The list's length is %d\n", GetLength(list));
printf("\n");
break;
case 5:
PrintList(list);
printf("\n");
break;
case 6:
ReverPrint(list);
printf("\n");
break;
case 7:
DeleteList(list);
printf("\n");
break;
case 0:
DeleteList(list);
bFlag = TRUE;
}
}
}
Ⅵ 如何實現線性表不同的存儲結構
額，有點麻煩。
1、設計四種線性表：順序存儲結構、單鏈表、循環鏈表、雙向鏈表的數據存儲結構，用戶選擇某種後就新建一個相應的線性表。
2、針對這四種線性表：順序存儲結構、單鏈表、循環鏈表、雙向鏈表，每種都分別設計以下五個（或更多的函數）：初始化線性表、插入數據、刪除數據、查找數據、清空線性表等基本操作。所以至少需要4x5=20個函數！每種結構對應至少5個操作！
3、實際上，可以使用C++的標准模板庫來迅速搞定，之前做實驗我們偷懶用的STL搞的，STL標准模板庫將常用的操作全部封裝了起來，使用非常簡單，比如一個pop()就可以從容器尾部刪除元素，push_back()就是從元素尾部插入元素，更多網路一下就搞懂了。再比如單鏈表可以用容器vector/list來實現，雙向鏈表可以用容器deque來實現，順序就數組了，循環鏈表用容器vector自己配個長度控制變數也可以搞定！
希望以上可以對你有所幫助，望採納~~
Ⅶ C語言二級考試循環鏈表是循環隊列的鏈式存儲結構
循環隊列本身是一種順序存儲結構，而循環列表是一種鏈式存儲結構。兩者之間是平級關系。
線性鏈表是線性表的鏈式存儲結構，包括單鏈表，雙鏈表，循環鏈表等。
隊列的順序存儲結構一般採用循環隊列的形式。
循環隊列的操作是按數組取摸運算的，所以是順序存儲，而循環鏈表本身就是收尾相連的，所以循環鏈表不是循環隊列，兩種不同的存儲結構，雖然實現的功能是一樣的，實現循環兩種方式 順序存儲就是循環隊列，鏈式存儲就是循環鏈表。
(7)循環雙鏈表的存儲結構擴展閱讀：
1、比順序存儲結構的存儲密度小(鏈式存儲結構中每個結點都由數據域與指針域兩部分組成，相比順序存儲結構增加了存儲空間)。
2、邏輯上相鄰的節點物理上不必相鄰。
3、插入、刪除靈活 (不必移動節點，只要改變節點中的指針)。
4、查找節點時鏈式存儲要比順序存儲慢。
5、每個節點是由數據域和指針域組成。
6、由於簇是隨機分配的，這也使數據刪除後覆蓋幾率降低，恢復可能提高。
Ⅷ 雙向循環鏈表為空的條件
雙向循環鏈表為空的判斷條件，這里要分為有頭節點和無頭節點。
有頭節點的雙向循環鏈表，當頭節點的前向指針和後驅指針都指向頭節點時表示此雙向循環鏈表為空。（head->pro==head && head->next==head）
無頭節點的雙向循環鏈表，當head為昌鉛空時，表明此雙向循環無頭結點鏈表為空。（head==NULL）
另外，單向此棗循環鏈表為空的條件是什麼呢？
同樣要分為有頭節點和無頭節點。
有頭節點：head->next==head
無頭節點：head==NULL
總結就是：有頭節點的循環鏈表在任何時候指針都不會為空，當頭節點指向自己時，鏈表為耐扒好空。
無頭結點的循環鏈表head等於空就表示鏈表為空。
Ⅸ 二叉鏈表和循環鏈表分別是不是線性結構
二叉鏈表和循環鏈表不是線性結構，線性結構有：線性表，棧，隊列，雙隊列，串。
非線性結構有：二維數組，多維數組，廣義表，樹(二叉樹等)，圖。
二叉鏈表是樹的二叉鏈表實現方式，以二叉鏈表作為樹的存儲結構。所以二叉鏈表不是線性結構。
循環鏈表是鏈式存貯結構，是表中最後一個結點的指針域指向頭結點，整個鏈表形成一個環，屬於圖。所以不是線性結構。
(9)循環雙鏈表的存儲結構擴展閱讀
循環鏈表的特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。
循環鏈表中沒有NULL指針。涉及遍歷操作時，其終止條件就不再是像非循環鏈表那樣判別p或p->next是否為空，而是判別它們是否等於某一指定指針，如頭指針或尾指針等。
在單鏈表中，從一已知結點出發，只能訪問到該結點及其後續結點，無法找到該結點之前的其它結點。而在單循環鏈表中，從任一結點出發都可訪問到表中所有結點，這一優點使某些運算在單循環鏈表上易於實現。
Ⅹ 循環鏈表和雙向鏈表的區別是是什麼
1、最後一個結點指針指向不同
在建立一個循環鏈表時，必須使其最後一個結點的指針指向表頭結點，而不是像雙向鏈表那樣置為NULL。此種情況還用於在喚宴最後一個結點後插入一個新的結點。
2、判斷鏈域值不同
在判斷是否到表尾時，是判斷該結點鏈域的值是否是表頭結點，當鏈域值等於表頭指針時，說明已到表尾。而非像單鏈表那樣判斷鏈域值是否為NULL。
3、訪問方式：
循環鏈表：可以從任何一個結點開始，順序向後訪問到達任意結點
雙向鏈表：可以從任何結點開始任意向前向後雙向訪問
4、操作：
循環鏈表：只能在當前結點後插入和刪除
雙鏈表：可以在當前結點前面或者後面插入，可以刪除前趨和後繼（包括結點自己）
5、存儲：
循環鏈表存儲密度大於雙鏈表
(10)循環雙鏈表的存儲結構擴展閱讀
線性表的鏈式存儲表示的特點是用一組任意的存儲單元存儲線性表的數據元素（這組存儲單元可以是連續的，也可以是不連續的）。因此，為了表示每個數據元素與其直接後繼數據元素 之間的邏輯關系，對數據元素 來說，除了存儲其本身的信息之外，還需存儲一個指示其直接後繼的信息（即直接後繼的存儲位置）。
由這兩部分信息組成一個"結點"（如概述旁的圖所示），表示線性表中一個數據元素。線性表的鏈式存儲表示，有一個缺點就是要找一個數，必須要從頭開始找起，十分麻煩。
根據情況，也可以自己設計鏈表的其它擴展。但是一般不會在邊上附加數據，因為鏈表的點和邊基本上是一一對應的（除了第一個或者最後一個節點，但是也不會產生特殊情況）。不過有一個特例是如果鏈表支持在鏈表的昌祥一段中把前和後指針反向，反向標記加在邊上可能會更方便。
對於非線性的鏈表，可以參見相關的其他數據結構，例如樹、圖。另外有一種基於多個線性鏈表的數據結構：跳錶，插入、刪除和查找等基本操作的速度可以達到O(nlogn），和平衡二叉樹一樣。
其中存儲數據元素信息的域稱作數據域（設域名為data），存儲直接後繼存儲位置的域稱為指針域（設域名為next）。指針域中存儲的信息又稱做指針或鏈。
由分別表示,，?，的N 個結點依次相鏈構成的鏈表，稱為線性表的鏈式存儲表示，由於此類和迅銀鏈表的每個結點中只包含一個指針域，故又稱單鏈表或線性鏈表。