資料結構算法代碼實作——靜态單連結清單（四）

線性表的靜态單連結清單存儲結構

//-------線性表的靜态單連結清單存儲結構-------
typedef struct{
    ElemType data;
    int cur;
}component,SLinkList[MAXSIZE];

什麼是靜态連結清單？

對于線性連結清單，也可用一維數組來進行描述。這種描述方法便于在沒有指針類型的進階程式設計語言中使用連結清單結構。
    在如上描述的連結清單中，數組中結構體一個成員存儲資料，另一個成員(遊标cur)存放下一個結點的位置。 
    為了和指針型描述的線性表相差別，稱這種數組為靜态連結清單。注意：連結清單的輸出不是按數組的位序輸出的， 
    而是由數組中的一個指定位置開始根據遊标cur輸出。

    生成靜态連結清單的方法有兩種：一種是在數組中根據需要可以生成多個獨立的靜态連結清單，每個連結清單的頭指針在生成的時候在指定。 
    另一種是一個數組隻能生成一個靜态連結清單，這種情況可以固定連結清單的頭指針，也就是說在初始化連結清單的同時就指定了連結清單的頭指針位置 
    (如數組最後一個下标為頭指針)， 在形參上比上一種方法簡單，因為不用傳入頭指針的位置了， 
    但是缺點是在程式需要使用多個靜态連結清單則要有多個數組，每個數組之間不能互相調劑，空間浪費會較大。

注意：
    在靜态連結清單中，為了辨識數組中那些分量未被使用，解決的方法是：
    将所有空閑結點連結形成一個備用連結清單，數組下标為 0 的單元為備用連結清單的頭結點(這時，靜态連結清單的頭結點就不能再是數組下标為 0 的單元了， 
    需要另外定義)。在靜态數組實際有 2 種連結清單，一個連結清單上連結的是線性表的結點，另一個連結清單(備用連結清單)上連結的是所有沒被使用的結點。
當線性表需要新結點時，把備用連結清單中的首元結點(由L[0].cur 訓示)從備用連結清單中删除，作為新結點，插入線性表。 
當删除線性表中的結點時，被删除的結點插入備用連結清單中，成為備用連結清單的首元結點。之是以從備用連結清單删除結點或向備用連結清單插入結點都在表頭進行，
是因為這樣效率最高。 是以操作備用鍊時需要使用者自定義的Malloc和Free函數。

靜态連結清單的基本操作

我們隻以第一種方法為例：

頭檔案請參考順序表文章
自定義的Malloc和Free函數，從備用鍊申請空間、釋放空間備用鍊回收結點。

//   申請結點和删除結點  都是在備用鍊的表頭後操作
//--------算法2.15  申請結點
int Malloc(SLinkList L){
     int i;
     i =L[].cur;
     if(i){
        L[].cur =L[i].cur;//把備用鍊的第一個結點做申請的結點，在把第二個結點和備用鍊連接配接起來。
     }
     return i;
 }

 //-------算法2.15 删除結點(回收到備用備用鍊中)
 void Free(SLinkList L,int n){
    L[n].cur =L[].cur; //把備連結清單的第一個結點位序 接到删除的結點後。 
    L[].cur =n; //在把删除的結點位序 接到備用鍊的頭結點後
 }

3，基本操作

//-------算法2.14     一個數組可産生多個靜态連結清單
 void InitSpace(SLinkList space) 
 { /* 将一維數組space中各分量鍊成一個備用連結清單，space[0].cur為頭指針。“0”表示空指針 
		此時不需要設定靜态連結清單的頭指針，在初始化的時候在産生，這樣也就可以産生多個靜态連結清單了。
	 */
   int i;
   for(i=0;i
  
   next;
	 }
	 //5
	 L[w].cur =b; //備用連結清單的第一個結點接到連結清單的尾部
	return OK;
	 

/*
   int j,k,i;
   i=L[n].cur; // 此連結清單第一個結點的位置 
   L[n].cur=0; // 連結清單空 
   k=L[0].cur;  備用連結清單第一個結點的位置 
   L[0].cur=i;  把連結清單的結點連到備用連結清單的表頭 
   while(i)  沒到連結清單尾 
   {
     j=i;
     i=L[i].cur;  指向下一個元素 
   
   L[j].cur=k; 備用連結清單的第一個結點接到連結清單的尾部 
   return OK;
	   */
 }

 //3，判斷連結清單是否為空
 /* 判斷數組L中表頭位序為n的連結清單是否空,若是空表傳回TRUE;否則傳回FALSE */
 Status ListEmpty(SLinkList L,int n) { 
   if(L[n].cur==0) 
     return TRUE;
   else
     return FALSE;
 }

 //4，連結清單的長度
 /* 傳回L中表頭位序為n的連結清單的資料元素個數 */
 int ListLength(SLinkList L,int n){ 
   int j=0,i;
   i=L[n].cur; // i指向第一個結點
   while(i) //沒到靜态連結清單尾 
   {
     i=L[i].cur; // 指向下一個元素
     j++;
   }
   return j;
 }

 //5，擷取指定連結清單的第i個位置資料元素值
 /* 用e傳回數組L中表頭位序為n的連結清單的第i個元素的值 */
 Status GetElem(SLinkList L,int n, int i,ElemType *e){ 
   int j,k=n; // k指向表頭結點位序
   if(i<1||i>ListLength(L,n)) // i值不合理
     return ERROR;
   for(j=1;j<=i;j++) //查找第i個結點的位序 
     k=L[k].cur; 
   *e =L[k].data;
   return OK;
 }

 //6，查找結點在數組L中的位序
 /* 在L中表頭位序為n的靜态單連結清單中查找 值為e的元素。
    若找到，則傳回它在數組L中的位序，否則傳回0 */
 int LocateElem(SLinkList L,int n,ElemType e){ 
   int i =L[n].cur; // i指向表中第一個結點
   while(i && L[i].data!=e) // 在表中順依次查找(注意：e不能是字元串)
     i =L[i].cur; //移動指針位序
   return i;
 }

 //7，查找前驅
 /* 初始條件：在L中表頭位序為n的靜态單連結清單已存在 
    操作結果：若cur_e是此單連結清單的資料元素，且不是第一個， 
             則用pre_e傳回它的前驅，否則操作失敗，pre_e無定義 */
 Status PriorElem(SLinkList L,int n,ElemType cur_e,ElemType *pre_e){ 
   int j,i=L[n].cur; // i指向連結清單第一個結點,j記住前驅指針位序
   do// 向後移動結點 
   { 
     j =i;  //記住前驅
     i =L[i].cur;
   }while(i && L[i].data!=cur_e);
   if(i) // 找到該元素  
   {
     *pre_e =L[j].data; //傳回前驅資料
     return OK;
   }
   return ERROR;
 }

 //8，查找後繼
 /* 初始條件：在L中表頭位序為n的靜态單連結清單已存在 
    操作結果：若cur_e是此單連結清單的資料元素，且不是最後一個， 
    則用next_e傳回它的後繼，否則操作失敗，next_e無定義 */
 Status NextElem(SLinkList L,int n,ElemType cur_e,ElemType *next_e){ 
   int i;  //使用靜态連結清單的特點
   i =LocateElem(L,n,cur_e); // 在連結清單中查找值為cur_e的元素在數組L中的位序
   if(i) // 在靜态單連結清單中存在元素cur_e 
   {
     i =L[i].cur; // cur_e的後繼的位序
     if(i) // cur_e有後繼 
     {
       *next_e=L[i].data;
       return OK; // cur_e元素有後繼 
     }
   }
   return ERROR; // L不存在cur_e元素,cur_e元素無後繼 
 }

 //9，插入操作
 /* 在數組L中表頭位序為n的連結清單的第i個元素之前插入新的資料元素e */
 Status ListInsert(SLinkList L,int n,int i,ElemType e){
   int l,j,k =n; // k指向連結清單頭 
   if(i<1||i>ListLength(L,n)+1) //與單連結清單不同的是，需要要先判斷i的合法性。畢竟還是數組，要是先申請了空間
					//i值不合法則浪費了空間，順序表的插入操作也是先判斷i值哦。
     return ERROR;
   j =Malloc(L); // 申請新結點
   //需要關心一下是否還有空間，
   if(j) // 申請成功
   {
     L[j].data=e; // 指派給新結點
     for(l=1;l
   
    ListLength(L,n))
     return ERROR;
   for(j=1;j

 
4,測試上述操作代碼
 


      #include"ch2.h"
#define MAXSIZE 100
typedef int ElemType;
#include"Static_linked.c"

 Status equal(ElemType c1,ElemType c2) 
 {
   if(c1==c2)
     return TRUE;
   else
     return FALSE;
 }

 void visit(ElemType c) /* 與順序表不同 */
 {
   printf("%d ",c);
 }

 void main()
 {
	 SLinkList L;
	 Status i;
	 ElemType e,e1;
	 int j,j1,La,Lb;
	 
	 InitSpace(L); // 建立備用連結清單 ,書中算法2.14
		//利用數組L 生成兩個靜态連結清單La和Lb

	 //1, 測試第一個基本操作（構造單連結清單L）
	 printf("1,測試第一個基本操作（構造靜态連結清單）\n");
	 La=InitList(L); // 初始化連結清單La ,La是頭指針位序
     	Lb=InitList(L); // 初始化連結清單Lb 
	 printf("  成功構造兩個靜态連結清單La和Lb\n");
	 printf("\n");

	 //2, 測試第九個基本操作（插入資料元素）
	 printf("2,測試第九個基本操作（插入資料元素）\n");

	 for(j=1;j<=5;j++){ //在La和Lb表尾後插入資料元素
		ListInsert(L,La,j,j); //與順序表和單連結清單參數都不同
		ListInsert(L,Lb,j,j*2);
	 }
	 printf("  在La的表尾依次插入1～5後：La=");
	 ListTraverse(L,La,visit);
	 printf("  在Lb的表尾依次插入1～10偶數後：Lb=");
	 ListTraverse(L,Lb,visit);
	 printf("\n");

	 //3, 測試第二、三個操作
	 printf("3, 測試第二、三個操作\n");

	 i=ListEmpty(L,La);
	 printf("  La是否空：i=%d(1:是 0:否)\n",i);
	 i=ClearList(L,La);
  	 printf("  清空La後：La="); ListTraverse(L,La,visit);
	 i=ListEmpty(L,La);
	 printf("  La是否空：i=%d(1:是 0:否)\n",i);
	 printf("\n");


	 //4，測試第四個操作
	 printf("4，測試第四個操作(Lb的資料元素個數)\n");

	 printf("  Lb表的長度=%d\n",ListLength(L,Lb));
	 printf("\n");

	 //5, 測試第五個操作
	 printf("5, 測試第五個操作(取得第La表中第3個位置的資料元素)\n");
	
	 i=GetElem(L,Lb,3,&e);
     if(i)
       printf("Lb表的第%d個元素的值為：%d\n",3,e);
     else
       printf("Lb表不存在第%d個元素！\n",3,e);
	 printf("\n");

	 //6,測試第六個操作
	 printf("6,測試第六個操作（LocateElem）\n");
	 
	 j=LocateElem(L,Lb,2);
	 if(j>0)
		 printf("  在Lb表中存在2相同的元素，在數組L的位序是：%d【備用連結清單頭0、La表頭1、Lb表頭2、La表頭的第一個結點3（現在被回收到了備用連結清單了）】\n",j);
	 else
		 printf("  在L表中不存在與2相同的資料元素\n");
	 printf("\n");

	 //7,測試第七、八個操作
	 printf("7,測試第七、八個操作\n");

	 for(j=1;j<=2;j++){ // 測試頭兩個資料
		 GetElem(L,Lb,j,&e1); // 把Lb表第j個資料賦給e1
		 i=PriorElem(L,Lb,e1,&e); // 求e1資料元素的前驅
		 if(i==ERROR)
		   printf("  元素%d無前驅\n",e1);
		 else
		   printf("  元素< %d的前驅為：%d >\n",e1,e);
	   }
	 for(j=ListLength(L,Lb)-1;j<=ListLength(L,Lb);j++){ // 最後兩個資料
		 GetElem(L,Lb,j,&e1); // 把第j個資料賦給e1
		 i=NextElem(L,Lb,e1,&e); // 求e1的後繼
		 if(i==ERROR)
		   printf("  元素%d無後繼\n",e1);
		 else
		   printf("  元素< %d的後繼為：%d >\n",e1,e);
	 }
	 printf("\n");

	 //8,測試第十個操作(删除操作)
	 printf("8,測試第十個操作(删除操作)\n");

	 j1=ListLength(L,Lb);  //注意要把表L的長度先儲存到一個變量中，因為在删除時，表的長度會自減一的。
	 for(j=j1+1;j>=j1;j--){
		 i=ListDelete(L,Lb,j,&e); // 删除第j個資料
		 if(i==ERROR)
		   printf("  删除第%d個資料元素失敗\n",j);
		 else
		   printf("  删除第%d個資料元素值為：%d\n",j,e);
	 }
	 printf("\n");

	 //9,測試第十一個操作
	 printf("9,測試第十一個操作\n");

	 ListTraverse(L,Lb,visit);

 }
           
       



 
5,測試結果圖：
 

         資料結構算法代碼實作——靜态單連結清單（四）
             較複雜的操作算法實作
      
         
教材算法2.17求集合運算（A-B）∪（B-A）。
 
      假設由終端輸入集合元素，先建立表示集合A的靜态連結清單S，而後在輸入集合B的元素的同時查找S表，若存在和B相同的元素，則從S表中删除之， 
否則将此元素插入S表。
           
       
 
代碼實作： 
 

      #include"ch2.h"
#define MAXSIZE 20
typedef char ElemType;
#include"Static_linked.c"
 void visit(ElemType elem)
 {
   printf("%c ",elem);
 }
/*
	算法自然語言描述：
	1，初始化數組space，并把所有的空閑結點生成一個備用鍊(數組位序0為備用連結清單的頭指針)。
	2，申請結點空間，S指向此結點，并作為一個靜态連結清單A的頭指針,移動指針r也指向S
	3，輸入A表的長度m，for循環m次建立表A的資料：先申請結點空間，在輸入資料元素，在把此結點接到表A尾，移動r指向表尾。
	4，把表A尾的cur設定為0
	5，輸入B表的長度n，for循環n次輸入表B的資料b:
			 首先要周遊表A查找是否有該資料元素，并用p指向上一位置結點，k指向待删除結點。
			 如果不存在(k==表尾.cur):則申請結點插入表尾，注意r的位置不變。
			 如果存在：則修改指針域，删除k指向的結點，注意要是删除的是表尾即r，則要移動r的位置。
*/
void difference(SLinkList space,int *S){
	/* 依次輸入集合A和B的元素，在一維數組space中建立表示集合(A-B)∪(B-A) */
   /* 的靜态連結清單，S為其頭指針。假裝置用空間足夠大，space[0].cur為備用空間的頭指針 */
	int r,k,p;
	int m,n,i,j;
	ElemType b;

	//産生備用連結清單
	InitSpace(space); //初始化備用空間

	*S =Malloc(space); //生成S的頭結點
	r =*S; //指向S頭指針

	printf("請輸入集合A元素個數m:");
    scanf("%d%*c",&m); // %*c吃掉回車符 
    printf("請輸入集合A的元素（共%d個）:",m);
	for(j=0;j
   
           
       
測試結果圖： 
 
         資料結構算法代碼實作——靜态單連結清單（四）
            
 
 
注意：用scanf輸入字元時要注意不要使用空格，還需要用%*c來吃掉輸入完成時的Enter鍵(百度學習)。

資料結構算法代碼實作——靜态單連結清單（四）

線性表的靜态單連結清單存儲結構

什麼是靜态連結清單？

靜态連結清單的基本操作

較複雜的操作算法實作

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器