数据结构之静态链表的创建（C语言）

柔光的暖阳◎ 2023-02-12 12:24 3阅读 0赞

### 什么是静态链表 ###

首先我们让数组的元素都是由两个数据域组成的，data和cur。也就是说，数组的每个下标都对应一个data和一个cur。数据域data，用来存放元素，cur相当于单链表或中的next指针，存放该元素的后继在数组中的下标，我们把cur称为游标。  
**我们把这种用数组描述的链表叫做静态链表**，这种描述方法还有起名叫做游标实现法。

为了方便插入数据，我们通常会把数组建立的大一些，以便有一些空闲空间编译插入是不至于溢出。

/* 线性表的静态链表存储结构 */
    #define MAXSIZE 1000
    typedef struct 
    {
        
        ElemType data;
        int cur;  /* 游标(Cursor) ，为0时表示无指向 */
    } Component,StaticLinkList[MAXSIZE];

另外我们对数组的第一个元素和最后一个元素作为特殊元素处理，不存数据，我们通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素cur就存放备用链表的第一个结点的下标，而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于链表的头结点的作用。  
![在这里插入图片描述][20200526104106938.png]

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

假设我们已经把数据存入了静态链表，比如分别存放着甲，乙，,等数据  
![在这里插入图片描述][2020052610503978.png]元素甲存有下一级元素乙的游标2，元素乙则存放下一元素丁的下标3，而庚是最后一个元素，所以它的cur设置为0，而最后一个元素的cur则因甲是第一个有值元素而存在有它的下标1.而第一个元素则因空闲空间的第一个元素下标为7，所以的他cur存有7。

### 静态链表的插入操作 ###

静态链表中要解决的是：如何用静态模拟冬天链表结构的存储空间的分配，需要时申请，无用时释放。  
结点的申请和释放分别借用malloc 和 free 函数实现，在静态链表中操作的是数组，不存在像动态链表的结点申请和释放问题。  
为了区分数组中那些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
    int Malloc_SSL(StaticLinkList space) 
    {
         
    	int i = space[0].cur;           		/* 当前数组第一个元素的cur存的值 */
    	                                		/* 就是要返回的第一个备用空闲的下标 */
    	if (space[0]. cur)         
    	    space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
    	                                        /* 所以我们就得把它的下一个 */
    	                                        /* 分量用来做备用 */
    	return i;
    }
    /*  在L中第i个元素之前插入新的数据元素e   */
    Status ListInsert(StaticLinkList L, int i, ElemType e)   
    {
          
        int j, k, l;   
        k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
        if (i < 1 || i > ListLength(L) + 1)   
            return ERROR;   
        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 OK;   
        }   
        return ERROR;   
    }

就这样，我们实现了在数组中，实现不移动元素，缺插入了数据的操作。  
![在这里插入图片描述][20200526112458947.png]

### 静态链表的删除操作 ###

删除元素时，需要使用释放结点的函数free()

/*  删除在L中第i个数据元素   */
    Status ListDelete(StaticLinkList L, int i)   
    {
         
        int j, k;   
        if (i < 1 || i > ListLength(L))   
            return ERROR;   
        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 OK;   
    }

### 总结 ###

静态链表的优点：在插入和删除操作时，只需要需改游标，不需要移动元素，从而改进了顺序存储结构中的插入和删除操作需要移动大量元素的缺点。  
缺点：没有解决连续分配存储空间带来的表长难以确定问题，失去了顺序存储结构随机存取的特性。

### 完整代码 ###

#include "string.h"
    #include "ctype.h"      
    
    #include "stdio.h"    
    #include "stdlib.h"   
    #include "io.h"  
    #include "math.h"  
    #include "time.h"
    
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    
    #define MAXSIZE 1000 /* 存储空间初始分配量 */
    
    typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
    typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为char */
    
    
    Status visit(ElemType c)
    {
        
        printf("%c ",c);
        return OK;
    }
    
    /* 线性表的静态链表存储结构 */
    typedef struct 
    {
        
        ElemType data;
        int cur;  /* 游标(Cursor) ，为0时表示无指向 */
    } Component,StaticLinkList[MAXSIZE];
    
    
    /* 将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，"0"表示空指针 */
    Status InitList(StaticLinkList space) 
    {
        
    	int i;
    	for (i=0; i<MAXSIZE-1; i++)  
    		space[i].cur = i+1;
    	space[MAXSIZE-1].cur = 0; /* 目前静态链表为空，最后一个元素的cur为0 */
    	return OK;
    }
    
    
    /* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
    int Malloc_SSL(StaticLinkList space) 
    {
         
    	int i = space[0].cur;           		/* 当前数组第一个元素的cur存的值 */
    	                                		/* 就是要返回的第一个备用空闲的下标 */
    	if (space[0]. cur)         
    	    space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
    	                                        /* 所以我们就得把它的下一个 */
    	                                        /* 分量用来做备用 */
    	return i;
    }
    
    
    /*  将下标为k的空闲结点回收到备用链表 */
    void Free_SSL(StaticLinkList space, int k) 
    {
          
        space[k].cur = space[0].cur;    /* 把第一个元素的cur值赋给要删除的分量cur */
        space[0].cur = k;               /* 把要删除的分量下标赋值给第一个元素的cur */
    }
    
    /* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
    int ListLength(StaticLinkList L)
    {
        
        int j=0;
        int i=L[MAXSIZE-1].cur;
        while(i)
        {
        
            i=L[i].cur;
            j++;
        }
        return j;
    }
    
    /*  在L中第i个元素之前插入新的数据元素e   */
    Status ListInsert(StaticLinkList L, int i, ElemType e)   
    {
          
        int j, k, l;   
        k = MAXSIZE - 1;   /* 注意k首先是最后一个元素的下标 */
        if (i < 1 || i > ListLength(L) + 1)   
            return ERROR;   
        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 OK;   
        }   
        return ERROR;   
    }
    
    /*  删除在L中第i个数据元素   */
    Status ListDelete(StaticLinkList L, int i)   
    {
         
        int j, k;   
        if (i < 1 || i > ListLength(L))   
            return ERROR;   
        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 OK;   
    } 
    
    Status ListTraverse(StaticLinkList L)
    {
        
        int j=0;
        int i=L[MAXSIZE-1].cur;
        while(i)
        {
        
                visit(L[i].data);
                i=L[i].cur;
                j++;
        }
        return j;
        printf("\n");
        return OK;
    }
    
    
    int main()
    {
        
        StaticLinkList L;
        Status i;
        i=InitList(L);
        printf("初始化L后：L.length=%d\n",ListLength(L));
    
        i=ListInsert(L,1,'F');
        i=ListInsert(L,1,'E');
        i=ListInsert(L,1,'D');
        i=ListInsert(L,1,'B');
        i=ListInsert(L,1,'A');
    
        printf("\n在L的表头依次插入FEDBA后：\nL.data=");
        ListTraverse(L); 
    
        i=ListInsert(L,3,'C');
        printf("\n在L的“B”与“D”之间插入“C”后：\nL.data=");
        ListTraverse(L); 
    
        i=ListDelete(L,1);
        printf("\n在L的删除“A”后：\nL.data=");
        ListTraverse(L); 
    
        printf("\n");
    
        return 0;
    }

[20200526104106938.png]: https://img-blog.csdnimg.cn/20200526104106938.png
[2020052610503978.png]: https://img-blog.csdnimg.cn/2020052610503978.png
[20200526112458947.png]: https://img-blog.csdnimg.cn/20200526112458947.png