线性表的链式存储结构与顺序存储

链式存储结构

链式存储结构，又叫链接存储结构。在计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的).它不要求逻辑上相邻的元素在物理位置上也相邻

单链表存储结构

下面用结构指针来描述单链表

typedef struct Node 
{
    ElemType data;      // 数据域
    struct Node* Next   // 指针域
} Node;
typedef struct Node* LinkList;

获得链表第i个数据的算法思路

1.声明一个结点p指向链表第一个结点，初始化j从1开始

2.当j

3.若到链表末尾p为空，则说明第i个元素不存在

4.否则查找成功，返回结点p的数据

下面是实现代码

Status GetElem(linkList L, int i, ElemType *e)
{
    int j;
    LinkList p;    
    p = L->next;
    j = 1;    
    while(p && j<i)
    {
        p = p->next;
        ++j;
    }    
    if(!p || j>i)
    {
        return ERROR;
    }    
    *e = p->data;    
    return OK;
}

单链表第i个数据插入结点的算法思路

1.声明一个结点p指向链表头结点，初始化j从1开始

2.当j

3.若到链表末尾p为空，则说明第i个元素不存在

4.否则查找成功，在系统中生成一个空结点s

5.将数据元素e赋值给s->data

6.执行这两个语句 s->next = p->next ; p->next = s;

下面是实现代码

Status ListInsert(LinkList *L, int i, ElemType e)
{
    int j;
    LinkList p,s;    
    p = *L;
    j = 1;    
    while(p && j<i)  // 用于寻找第i个结点
    {
        p = p->next;
        j++;
    }    
    if(!p || j>i)
    {
        return ERROR;
    }    
    s = (LinkList)malloc(sizeof(Node)); // 申请一个结点长度空间
    s->data = e;    
    s->next = p->next;  // 将原始指向的指针域赋给插入结点的指针域
    p->next = s;   // 插入结点赋给P的指针域    
    return OK;
}

单链表第i个数据删除结点的算法思路

1.声明一个结点p指向第一个结点，初始化j=1

2.当j

3.若到链表末尾p为空，则说明第i个元素不存在

4.否则查找成功，将欲删除结点p->next赋值给q

5.执行这个语句 p->next = q->next ;

6.将q结点中的数据赋值给e，作为返回

下面是实现代码

Status ListDelete(LinkList *L, int i, ElemType *e)
{
    int j;
    LinkList p,q;   
    p = *L;
    j = 1;    
    while(p->next && j<i)  // 用于寻找第i个结点
    {
        p = p->next;
        j++;
    }    
    if(!(p->next) || j>i)
    {
        return ERROR;
    }    
    q = p->next;   // 删除的结点赋给q
    p->next = q->next;  // 将欲删除的下一个结点指向p的指针域    
    *e = q->data;   // 作为返回欲删除的数据
    free(q); // 释放删除的结点    
    return OK;
}

顺序存储结构

顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的结点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。

插入算法的思路：

1.如果插入位置不合理，抛出异常

2.如果线性表长度大于等于数组长度，则抛出异常或动态增加数组容量

3.从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置

4.将要插入元素填入位置i处

5.线性表长+1

下面是实现代码

Status ListInsert(SqList *L, int i, ElemType e)
{
    int k;   
    if(L->length == MAXSIZE)  // 顺序线性表满了
    {
        return ERROR;
    }
    if(i<1 || i>L->length+1)  // 当i不在范围内时
    {
        return ERROR;
    }
    if(i <= L->length)   // 若插入数据位置不在表尾  
    {
        /* 将要插入位置后数据元素向后移动一位 */
        for(K=L->length-1; k >= i-1;k--)
        {
            L->data[k+1] = L->data[k];
        }        
        L->data[i-1] = e;  // 将新元素插入
        L->length++;        
        return OK;
    }
}

删除算法的思路

1.如果删除位置不合理，抛出异常

2.取出删除元素

3.从删除元素位置开始遍历到最后一个元素位置，分别将它们都向前移动一个位置

4.表长-1

下面是实现代码

Status ListDelete(SqList *L, int i, ElemType *e)
{
    int k;   
    if(L->length == 0)  // 判断表长是否为空
    {
        return ERROR;
    }
    if(i<1 || i>L->length)  // 当i不在范围内时
    {
        return ERROR;
    }    
    *e = L->data[i-1]; // 用e返回删除的值    
    if(i < L->length) 
    {
        /* 将删除位置后面的元素全部向前移动 */
        for(K=i; k < L->length;k++)
        {
            L->data[k-1] = L->data[k];
        }        
        L->length--;        
        return OK;
    }
}

线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O(1)。而在插入或删除时，时间复杂度都是O(n)。线性表作为数据结构中的重要组成成员，线性表的逻辑结构简单，便于实现和操作，因此，线性表在实际应用中得到了广泛应用。在本站的数据结构和算法教程中还有对许多的优秀的数据结构全面解析，让我们能够快速掌握各种数据结构。