線性結構四 鏈式存盤

鏈接方式存盤的線性表簡稱為鏈表 Link List

鏈表的具體存盤表示為：

1）用一組任意的存盤單元來存放

2）鏈表中結點的邏輯次序和物理次序不一定相同，還必須存盤指示其后繼結點的地址資訊

用一組地址任意的存盤單元存放線性表中的資料元素

鏈表是：線性表中資料為（1，3，5，7.8）

單鏈表：data域：存放結點的資料域

  　　　　next域：存放結點的直接后繼的地址（位置）的指標域

所有結點通過指標鏈接而組成單鏈表

NULL：成為空指標

head: 頭指標，存放鏈表的第一個結點地址（每個鏈表都需要有一個頭指標）

 單鏈表的一般圖示法：

單鏈表特點：

起始節點又叫做首結點，沒有前驅，故設頭指標head指向開始結點

鏈表由頭指標唯一確定，單鏈表可以用頭指標的名字來命名，頭指標是head的鏈表可以稱為表head

終端結點又稱尾結點，沒有后繼結點，所以終端結點的指標域為空，NULL

除頭結點之外的結點為表結點

為運算操作方便，頭節點中不存資料哦~

 單鏈表的型別定義：

1 ytpedef struct node{
2 Datatype data; //資料域
3 struct node*next;//指標域，存放該結點的直接后繼結點的地址
4 } Node, *LinkList;

1.初始化

每一個新建的單鏈表都需要進行一個初始化，（一個空的單鏈表是一個頭指標和一個頭結點構成的）

//建立一個空鏈表
LinkList InitiateLinkList(){
LinkList head;  //頭指標
head =malloc (sizeof(node)); //動態構建一節點，它是頭結點
head->next=null;
return head;

現在咱們已經創建了一個新鏈表，接下來創建幾個資料域后如何來算表的長度呢？

：在單鏈表存盤結構中，線性表的長度等于單鏈表所含結點的個數（不含頭結點）

1 //求表長
2 int lengthLinklist (LinkList head){
3 Node *p;
4 p=head;j=0;
5 while(p->next!=null){//p的下一個指標不為空繼續回圈，當p的指標為空跳出回圈
6 p=p->next;//p指向下個結點
7 j++;長度加1
8 }
9 return (j);}

3.讀表元素

步驟；查找第I個結點

1.零計數器J為0

2.令P指向頭節點

3.當下一個結點不空時，并且j<i時，j加1，p指向下一個結點

4.如果j等于i，則p所指結點為要找的第i結點，否則，鏈表中無第i結點

 1 Node *GetlinkList(LinkList head,int i){
 2 Node *p;
 3 p=head->next;
 4 int c=1;
 5 while((c<i)&&(p!=NULL)){
 6 p=p->next;
 7 c++;
 8 }
 9 if(i==c)
10 return (p);
11 else return NULL；}

4.定位

定位運算是對給定表元素的值，找出這個元素的位置，對
于單鏈表，給定一個結點的值，找出這個結點是單鏈表的
第幾個結點，定位運算又稱為按值查找，
具體步驟：
1、令p指向頭結點
2、令i=0
3、當下一個結點不空時， p指向下一個結點,同時i的值加1
4、直到p指向的結點的值為x，回傳i+1的值，
5、如果找不到結點值為x的話，回傳值為0

 1 int LocateLinklist (LinkList head ,Data Type x){
 2 //求表head中第一個值等于x的結點的序號，若不存在這種結點，回傳結果為0
 3 Node *p=head;//p是作業指標
 4 p=p->next;//初始時P指向首結點
 5 int i=0;//i代表 結點的序號，這里初值為
 6 while(p!=null&&p->data!=x){//訪問鏈表
 7 i++;
 8 p=p->next;
 9 }
10 if(p!=null)
11 return i+1;
12 else return 0;}

5.插入

插入運算是將值為x的新結點插入到表的第i個結點
的位置上，即插入到ai-1與ai之間，
具體步驟：
（1）找到ai-1存盤位置p
（2）生成一個資料域為x的新結點*s
（3）令結點*p的指標域指向新結點
（4）新結點的指標域指向結點ai，

 1 void InsertLinklist (LinkList head, DataType x, int i)
 2 //在表head的第i個資料元素結點之前插入一個以x為值的新結點
 3 {
 4 Node *p,*q;
 5 if (i==1) q=head;
 6 else q=GetLinklist (head, i-1); //找第 i-1個資料元素結點
 7 if (q==NULL) //第i-1個結點不存在
 8 exit(“找不到插入的位置”);
 9 else
10 {
11 p=malloc(sizeof (Node) );p->data=https://www.cnblogs.com/X404/p/x; //生成新結點
12 p->next=q->next; //新結點鏈域指向*q的后繼結點
13 q->next=p; //修改*q的鏈域
14 }
15 }

6. 洗掉

演算法步驟
洗掉運算是將表的第i個結點刪去，
（1）找到ai-1的存盤位置p
（2）令p-＞next指向ai的直接后繼結點
（3）釋放結點ai的空間，將其歸還給"存盤池"，

 1 void DeleteLinklist(LinkList head, int i)
 2 //洗掉表head的第i個結點
 3 {
 4 Node *q;
 5 if(i==1) q=head;
 6 else q=GetLinklist(head, i-1); //先找待刪結點的直接前驅
 7 if(q !== NULL && q->next != NULL) //若直接前驅存在且待刪結點存在
 8 {
 9 p=q->next; //p指向待刪結點
10 q->next=p->next; //移出待刪結點
11 free(p); //釋放已移出結點p的空間
12 }
13 else exit (“找不到要洗掉的結點”); //結點不存在
14 }

雙向回圈鏈表

在鏈表中設定兩個指標域，
一個指向后繼結點
一個指向前驅結點
這樣的鏈表叫做雙向鏈表

 雙向鏈表的結構體

雙向回圈鏈表適合應用在需要經常
查找結點的前驅和后繼的場合， 找
前驅和后繼的復雜度均為： O(1)，

1 struct dbnode
2 { DataType data;
3 struct dbnode *prior, *next;
4 };
5 typedef struct dbnode *dbpointer;
6 typedef dbpointer Dlinklist;
7 假設雙向鏈表中p指向某節點
8 則有 p->prior->next 與p->next->prior相等

雙向鏈表中結點的洗掉

設p指向待刪結點， 洗掉*p可通過下述陳述句完成：

1 (1)p->prior->next=p->next; //p前驅結點的后鏈指向p的后繼結點
2 (2)p->next->prior=p->prior; //p后繼結點的前鏈指向p的前驅結點
3 (3)free(p); //釋放*p的空間

（1） 、 （2） 這兩個陳述句的執行順序可以顛倒，

 雙向鏈表中結點的插入

在p所指結點的后面插入一個新結點*t， 需要修改四個指標:
(1)t->prior=p;
(2)t->next=p->next;
(3)p->next->prior=t;
(4)p->next=t;

標籤：其他

上一篇：C#獲取本機局域網ip

下一篇：在storm中，一個supervisor可以對應幾個worker