SLinkList(静态链表)
// stdafx.h : 標準系統包含文件的包含文件,
// 或是常用但不常更改的項目特定的包含文件
//
#define TRUE 1
#define FLASE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define NULL 0
typedef int Status;
typedef char ElemType;
#define MAXSIZE 1000 //鏈表的最大長度
typedef struct{
ElemType data;
int cur; //注意這里不是指針,而是類似游標的指示器
}component,SLinkList[MAXSIZE];
// 這是使用應用程序向導生成的 VC++
// 應用程序項目的主項目文件。
// 靜態鏈表的表示和實現
#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h" //需要exit所加頭文件
#include "iostream.h"
#include <stdlib.h>
#using <mscorlib.dll>
#include <tchar.h>
using namespace System;
int LocateElem(SLinkList L,ElemType e){
// 這里和下面的space備用鏈表是沒有關系的,就因為第0個和第1個分量的指向不同
// 在靜態單鏈線性表L中查找第1個值為e的元素。
// 若找到,則返回它在L中的位序,否則返回0。
int i;
i=L[0].cur;
while(i && L[i].data==e)
i=L[i].cur;
return i;
} //LocateElem
Status DisplayList(SLinkList L){
// 輸出靜態鏈表L
int i,j;
i=L[1].cur;
j=1;
if(i==0)
cout<<"靜態鏈表為空!"<<endl;
else
while(i){
cout<<"靜態鏈表第"<<j<<"個結點是:"<<L[i].data<<endl;
i=L[i].cur;
j++;
}
return OK;
}
void InitSpace(SLinkList &space){
// 將一維數組space中各分量鏈成一個備用鏈表,space[0].cur為頭指針
// “0”表示空指針
int i;
for(i=0;i<MAXSIZE-1;++i)
space[i].cur=i+1;
space[MAXSIZE-1].cur=0;
} //InitSpace
int Malloc_SL(SLinkList &space){
// 若備用空間鏈表非空,則返回分配的結點下標,否則返回0
// 即把備用鏈表的一個結點釋放出來,但還沒具體鏈接到靜態
// 鏈表中。如果備用鏈表沒有空間的話,返回0(因為此時space[0].cur=0)
int i;
i=space[0].cur;
if(space[0].cur)
space[0].cur=space[i].cur;
return i;
} //Malloc_SL
void Free_SL(SLinkList &space,int k){
// 將下標為k的空閑結點回收到備用鏈表。
// 即把靜態鏈表中要刪除的結點k釋放出來,鏈接到備用鏈表中,
// 但靜態鏈表中k結點的前驅和后繼還沒有處理。最后返回刪除結點k.
space[k].cur=space[0].cur;
space[0].cur=k;
} //Free_SL
void difference(SLinkList &space,int &S){
// 依次輸入集合A和B的元素,在一維數組space中建立表示集合(A-B)∪(B-A)
// 的靜態鏈表,S為其頭指針(靜態鏈表的頭指針)。假設備用空間足夠大,
// space[0].cur為其頭指針(備用鏈表的頭指針)。
// S這個參數的存在是為了可以把頭指針放在鏈表的任何位置,不局限于第一元素位置。
int r;
InitSpace(space); //初始化備用鏈表
S=Malloc_SL(space); //生成S的頭結點,即靜態鏈表的頭指針
r=S; //r指向S的當前最后結點
int m,n;
cout<<"請您輸入集合A的元素個數m=";
cin>>m;
cout<<endl;
int i,j;
for(j=1;j<=m;++j){ //建立集合A的鏈表
i=Malloc_SL(space); //分配結點,欲給靜態鏈表
cin>>(space[i].data); //輸入A的元素值
space[r].cur=i; //插入到靜態鏈表的表尾
r=i; //r指向靜態鏈表的表尾
}//for
space[r].cur=0; //靜態鏈表的表尾指針為空
DisplayList(space); //輸出A的元素
cout<<endl;
cout<<"B的元素個數n=";
cin>>n;
cout<<"下面請逐個輸入B的元素"<<endl;
ElemType b;
int p,k;
for(j=1;j<=n;++j){ //依次輸入B的元素,若不在當前表中,則插入,否則刪除
cin>>b;
p=S;
k=space[S].cur; //k指向集合A的第一個結點
while(k!=space[r].cur && space[k].data!=b){ //在當前靜態鏈表A中查找
p=k;
k=space[k].cur;
}//while
if(k==space[r].cur){ //當前表A中不存在該元素,插入在r所指結點之后,且r的位置不變。
i=Malloc_SL(space);
space[i].data=b;
space[i].cur=space[r].cur;
space[r].cur=i;
}//if
else{ //該元素已在表中,刪除之
space[p].cur=space[k].cur;
Free_SL(space,k);
if(r==k) //若刪除的是靜態鏈表A中r所指結點,則需修改A的尾指針。
r=p;
}//else
}//for
}//difference
// 這是此應用程序的入口點
int _tmain(void)
{
// TODO: 請用您自己的代碼替換下面的示例代碼。
int S=1;
SLinkList space;
difference(space,S);
DisplayList(space);
return 0;
}
/*********************************************************************
這里的靜態鏈表需要注意是的:
1、我現在把靜態鏈表當成是用著的鏈表!!!不包括備用那些結點;
2、初始化時,把整個結構體數組初始化成一個備用鏈表;
3、靜態鏈表和備用鏈表共用原來初始化的空間;
4、當tmain函數中的S=1時,初始化后的空間里,第0個元素和第1個元素的位置數據域
是空的。第0個用來指示備用鏈表第一個元素的位子,第1個則用來指示靜態鏈表
第一個元素的位子,而且在這個思路中一直都是這樣的!(當然你可以采取另一種
方式實現,在此不討論);
5、Malloc_SL操作時,它所做的動作只是從備用鏈表釋放一個結點,但釋放出來的這
個結點還沒具體鏈接到靜態鏈表中;
6、Free_SL操作時,動作只是把靜態鏈表中要刪除的結點釋放出來,鏈接到備用鏈表中,
但靜態鏈表中k結點的前驅和后繼還沒有處理;
7、當你把B中的元素往A插時,B的元素一直順著沒改變以前的A尾插,而不是插在已經插
入元素的后面結點,比方說,依次插m,n兩元素到A,那么先插m,就是:A-m;然后插
n,就是:A-n-m;
8、如果你老是想不明白,那么你就認認真真畫圖!畫圖,再畫圖,不要怕煩!你就明白了
*********************************************************************/
/*********************************************************************
附:
靜態鏈表:由系統在內存中開辟了固定的、互不連續的存儲單元,在程序執行過程中不可
能人為地再產生新的存儲單元,它跟順序結構沒關系
靜態鏈表其實就是用數組來描述的鏈表,一般是用于不設指針類型的語言,很少在C語
言中使用。不是順序結構
difference(SLinkList &space,int &S)中的參數S=1時,有下面:
靜態鏈表是這樣的,在一個數組中有兩個元素是不用的,分別是第0個元素和第1個元
素,第0個用來指示備用空間的第一個元素的位子,第1個則用來指示第一個鏈表元素
的位子,每當從鏈表中刪除一個元素時.則讓該元素成為備用鏈表的第一個結點,也即
讓數組的第0個元素指向刪除的結點,然后讓刪除的結點指向原來的備用鏈表的第1個
結點,插入的話類似
**********************************************************************/
轉載于:https://www.cnblogs.com/yujun543/archive/2012/09/11/2680742.html
總結
以上是生活随笔為你收集整理的SLinkList(静态链表)的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 梦洁股份是做什么的
- 下一篇: 工行5万小额贷款条件