数据结构-线性表-静态链表完整可执行代码

迷南。 2022-09-17 10:29 137阅读 0赞

**数据结构-线性表-静态链表完整可执行代码（c语言描述）**

/***************************************************************************
      
        *
     * 静态链表
     * ADT (List)
     * Data
     *   {a1, a2, a3, ..., an}
     * Operation
     *   InitList(*L);               初始化静态链表L.
     *   ListEmpty(L);               静态链表L,返回true,否则返回false.
     *   ClearList(*L);              将单链表L清空.
     *   GetElem(L, i, *e);          将单链表L中第i个位置元素值返回给e.
     *   LocateElem(L, e);           在L查找和e相等的元素,成功返回元素所在的.
     *                               序号,否则,返回0表示失败.
     *   ListInsert(*L, i, e);       在L中第i个位置插入新元素e.
     *   ListDelete(*L, i);          删除L中第i个位置的元素.
     *   ListLength(L);              返回线性表L的元素个数.
     * ENDADT
     *
     * 逻辑结构
     *                    0|a0| m|  ----> 备用链表头指针
     *                    1|a1| 2|
     *                    2|a2| 3|
     *                      .. ..
     *                    i|ai| 0|
     *                      .. ..
     *                max-1|an| 1|  ----> 链表头指针
     *
     * 修改记录：
     *           2012-12-11 重新组织代码,编译调试，修正语法错误.
     */
    
    
    /************************ data   静态链表存储结构定义 *********************/
    
    #define MAXSIZE 1000            /* 假设链表最大的长度为1000 */
    #define OK      1
    #define ERROR   0
    #define TRUE    1
    #define FALSE   0
    
    typedef int ElemType;           /* ElemType 类型根据实际情况而定,现假设为 int */
    typedef int Status;             /* Status 是函数的类型，其值是函数结果状态代码 */
    
    /* 静态链表存储结构 */
    typedef struct{
        ElemType data;
        int cur;                      /* 游标(cursor) 为0 时表示无指向 */
    }Component, StaticLinkList[MAXSIZE];
    
    /***************************** operation 操作 *****************************/
    
    /*
     * 初始条件：静态链表L不存在。
     * 操作结果：将一维数组space中各个分量链成一备用链表
     * 数组第一个元素的游标cur用来存放备用链表第一个节点的下标。
     * 数组最后一个元素的游标cur存放第一个有数值元素的下标，相当
     * 于单链表的头节点。
     */
    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;
    }
    
    /*
     * 初始条件：静态链表L已存在
     * 操作结果：如果静态链表为空，返回true，否则返回false
     */
    Status ListEmpty(StaticLinkList L)
    {
        return (ListLength(L) == 0 ? TRUE : FALSE);
    }
    
    /* 若备用空间链表非空，则返回分配的节点下标，否则返回0 */
    int Malloc_SLL(StaticLinkList space)
    {
        int i = space[0].cur;         /* 当前数组第一元素的cur存的值，
                                       就是要返回第一个备用空闲的下标. */
        
        /* 由于要拿出一个分量来使用了，所以需要
         把它的下一个分量用来做准备 */
        if(space[0].cur)
            space[0].cur = space[i].cur;
        
        return i;
    }
    
    /*
     * 初始条件: 静态链表L已存在
     * 操作结果：将静态链表L元素清空为0，长度置为0
     *           备用链表置为初始状态
     */
    void ClearList(StaticLinkList L)
    {
        int i;
        i = L[MAXSIZE - 1].cur;
        
        while(i){
            L[i].data = 0;
            ListDelete(L,i);
        }
    }
    
    /*
     * 初始条件：静态链表L已存在，1 <= i <= ListLength(L)
     * 操作结果：用e返回L中第i个元素的值
     */
    Status GetElem(StaticLinkList L, int i, ElemType *e)
    {
        int j;
        int k;
        j = L[MAXSIZE - 1].cur;
        k = 1;
        
        while(j && k < i){
            j = L[j].cur;
            k++;
        }
        if(!j || k > i)
            return ERROR;
        
        *e = L[j].data;
        return OK;
    }
    
    /*
     * 初始条件：静态链表L已存在.
     * 操作结果：在L查找和e相等的元素，成功返回元素所在的序号，
     *           否则，返回0表示失败
     */
    Status LocateElem(StaticLinkList L, ElemType e)
    {
        int i = L[MAXSIZE - 1].cur;
        
        while(i){
            if (L[i].data == e)
                return i;
            i = L[i].cur;
        }
        
        return 0;
    }
    
    /*
     * 初始条件: 静态链表L已存在，1 <= i <= ListLength(L)
     * 操作结果：在L中第i个位置之前插入新元素e , L的长度加1
     */
    Status ListInsert(StaticLinkList L, int i, ElemType e)
    {
        int j;
        int k;
        int l;
        
        k = MAXSIZE - 1;                  /* 注意k首先是最后一个元素的下标,即头指针 */
        
        if(i < 1 || i > ListLength(L) + 1)
            return ERROR;
        
        j = Malloc_SLL(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元素之前元素的cur */
            
            return OK;
        }
        
        return ERROR;
    }
    
    /* 将下标为k的空闲节点回收到备用链表,类似头插入法 */
    void Free_SLL(StaticLinkList space, int k)
    {
        space[k].cur = space[0].cur;      /* 把第一个元素cur值赋给要删除的分量的cur */
        space[0].cur = k;                 /* 把要删除的元素的下标赋给头指针cur */
    }
    
    /*
     * 初始条件: 静态链表L已存在，1 <= i <= ListLength(L)
     * 操作结果：删除在L中第i个元素e.
     */
    Status ListDelete(StaticLinkList L, int i)
    {
        int j;
        int k;
        
        if (i < 1 || i > ListLength(L))
            return ERROR;
        
        k = MAXSIZE - 1;
        for(j = 1; j <= i - 1; j++){      /* 找到要删除的元素的前一个位置的下标 */
            k = L[j].cur;
        }
        j = L[k].cur;                     /* 暂存要删除的元素的下标 */
        L[k].cur = L[j].cur;              /* 把要删除的元素的前一个元素的游标改要
                                           删除元素的后继 */
        
        Free_SLL(L, j);
        return OK;
    }
    
    /*
     * 初始条件：静态链表L已经存在.
     * 操作结果：返回L的元素个数.
     */
    int ListLength(StaticLinkList L)
    {
        int j = 0;
        int i = L[MAXSIZE - 1].cur;
        
        while(i){
            i = L[i].cur;
            j++;
        }
        
        return j;
    }
    
    int main()
    {
    //    具体操作...
    //    StaticLinkList L;
    //    InitList(L);
        return 0;
    }