博客

**

说明

参考资料《大话数据结构》，3.12，静态链表。

原文把数组建立的较大，个人建立的较小，导致测试时出现一些问题，

现将 原代码 补充完善以自用。

因个人定义的差异，下文出的原代码与书籍中的所给代码略有差异，仅是将数据类型名、变量名修改为自己定义的，主体过程未变。

定义

用数组来模拟单链表

typedef int ElemType;

#define SIZE 10       // 原文将 SIZE 设置的较大，为1000.在此仅设为 10
typedef struct Info
{
    ElemType data;
    int cur; // 游标，为 0  时表示无指向
} SNode, StaticList[SIZE];

上图要点

• 数组的 第一个 和 最后一个 元素不用来存储数据。即 数组大小设为 SIZE 时，数组最多存储 SIZE-2 个元素。
• 未被使用的数组元素作为备用链表，相当于空闲可用空间
• 数组 第一个 元素的 cur ，用来存放备用链表的第一个结点的下标，相当于存储空闲空间中第一个可插入结点的位置。
• 数组最后一个元素的 cur 存放第一个有数值的元素的下标，相当于存放单链表的第一个数据结点的位置
• 
  当整个链表为空时，数组最后一个元素的 cur 为 0
  
  .
• 
  当数组满时，数组第一个元素的 cur 为 SIZE-1
  
  。数组满时，1~SIZE-2 共 SIZE-2 个元素被存储在数组内，故 第一个元素的 cur 为 SIZE-1，即指向数组最后一个元素

初始化实现代码

/* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
bool InitList(StaticList L)
{
    int i;
    for (i = 0; i < SIZE - 1; i++)
        L[i].cur = i + 1;
    L[SIZE - 1].cur = 0;   /* 目前静态链表为空，最后一个元素的cur为0 */
    return true;
}

插入操作

因模仿的单链表，因此，欲在第 i 个位置插入元素，则需先定位到第 i -1 个位置。删除操作同理。

原代码

/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticList L) 
{ 
	int i = L[0].cur;           		/* 当前数组第一个元素的cur存的值 */
	                                		/* 就是要返回的第一个备用空闲的下标 */
	if (L[0]. cur)         
	    L[0]. cur = L[i].cur;       /* 由于要拿出一个分量来使用了， */
	                                        /* 所以我们就得把它的下一个 */
	                                        /* 分量用来做备用 */
	return i;
}

若数组设置的较大，则基本不用考虑数组元素达到 SIZE-2 而导致的插入失败情况。因自己将数组设置的较小，导致测试时出现问题，故对原代码进行了修改，如下

修改后的代码

int Malloc_SLL(StaticList L)
{
    int i = L[0].cur;
    if (L[0].cur == SIZE-1){ // 数组设置的较小时，容易导致数组插入元素很快达到 SIZE-2 个。
    						// 故在申请数组空闲空间前，先检查数组元素是否已满 
    	cout<<"The static list is full, malloc failed!!!"<<endl;
    	return 0;
	}else{
	L[0].cur = L[i].cur;
	return i;
	}     
}

插入操作的原代码

/*  在L中第i个元素之前插入新的数据元素e   */
bool ListInsert(StaticList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = SIZE - 1;   /* 注意k首先是最后一个元素的下标 */
    if (i < 1 || i > ListLength(L) + 1)   
        return false;   
    j = Malloc_SSL(L);   /* 获得空闲分量的下标 */
    if (j)   
    {   
		L[j].data = e;   /* 将数据赋值给此分量的data */
		for(l = 1; l <= i - 1; l++)   /* 找到第i个元素之前的位置 */
		   k = L[k].cur;           
		L[j].cur = L[k].cur;    /* 把第i个元素之前的cur赋值给新元素的cur */
		L[k].cur = j;           /* 把新元素的下标赋值给第i个元素之前元素的ur */
		return true;   
    }   
    return false;   
}

修改后的代码

bool InsertList(StaticList L, int i, ElemType e)
{
    int j, k, l;
    k = SIZE - 1;
    if (i < 1 || i > ListLength(L) + 1)
    {
        cout << "Invalid i:" << i<<" --> ";
        cout<<"Insert failed!"<<endl; 
        return false;
    }
    j = Malloc_SLL(L);  // 申请成功，则返回空闲元素的数组下标，范围 1`SIZE-2；申请失败则返回 0
    if (j)
    {
    	// 申请成功
        L[j].data = e;
        for (l = 1; l <= i - 1; l++)
            k = L[k].cur;
        L[j].cur = L[k].cur;
        L[k].cur = j;
        return true;
    }
    // 申请失败
    cout<<"Insert "<<e<<" failed!!!"<<endl; 
    return false;
}

ListLength()

/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticList L)
{
    int j = 0;
    int i = L[SIZE - 1].cur;
    while (i)
    {
        i = L[i].cur;
        j++;
    }
    return j;
}

删除操作

原代码

/*  删除在L中第i个数据元素   */
bool ListDelete(StaticList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return false;   
    k = MAXSIZE - 1;   
    for (j = 1; j <= i - 1; j++)   
        k = L[k].cur;   
    j = L[k].cur;   
    L[k].cur = L[j].cur;   
    Free_SSL(L, j);   
    return true;   
}

修改后代码

bool DeleteList(StaticList L, int i)
{
    int j, k;
    k = SIZE - 1;
    if (L[k].cur == 0)
    {
        cout << "the list is empty" << endl;
        return false;
    }
    if (i < 1 || i > ListLength(L))
    {
        cout << "Invalid i" << endl;
        return false;
    }
    for (j = 1; j <= i - 1; j++)
        k = L[k].cur;
    j = L[k].cur;
    L[k].cur = L[j].cur;
    Free_SLL(L, j);
    return true;
}

原代码

此处未作修改

/*  将下标为k的空闲结点回收到备用链表 */
void Free_SSL(StaticList space, int k) 
{  
    space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
    space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
}

遍历操作

bool ListTraverse(StaticList L)
{
    int j = 0;
    int i = L[SIZE - 1].cur;
    while (i)
    {
        cout << L[i].data << " ";
        i = L[i].cur;
        j++;
    }
    cout << endl;
    return true;
}