线性表—顺序存储

小咪咪 2021-11-18 01:24 367阅读 0赞

1、定义：

顺序存储结构就是用一段地址连续的存储单元存储元素  
其结构特点：逻辑上相邻的数据元素在物理上也相邻。

2、实现方式：

使用数组实现。实质就是对数组元素进行插入、删除等操作。

3、时间效率：

\*在顺序表中插入和删除一个数据元素的时间复杂度为O(n)  
\*其余操作的时间复杂度都为O(1)

4、优缺点：

优点：

\*算法简单，空间单元利用率高  
\*可以快速存取表中任一位置的元素

缺点：

\*插入和删除操作需要大量移动元素  
\*需要预先确定数据元素的最大个数  
\*造成存储空间“碎片”

5、代码  
list.h

#ifndef LIST_H_INCLUDED
    #define LIST_H_INCLUDED
    
    #include <stdio.h>
    
    #define ERROR 0
    #define TRUE 1
    #define MAXSIZE 20
    
    typedef int Status;
    typedef int DataType;
    typedef struct
    { 
        DataType Mylist[MAXSIZE];
        int len;
    }SeqList;
    
    void ListInitiate(SeqList *L);        //初始化线性表
    int GetListLength(SeqList L);         //获取线性表长度
    Status CleanList(SeqList *L);         //清空线性表
    Status ListDeleteElem(SeqList *L, int index);               //删除元素
    Status ListInsert(SeqList *L, int index, DataType elem);    //插入元素
    Status GetListElem(SeqList *L, int index, DataType *elem);  //获取元素
    
    #endif // LIST_H_INCLUDED

list.c

#include "list.h"
    
    //初始化线性表
    void ListInitiate(SeqList *L)
    { 
        L->len = 0;
    }
    
    //获取线性表长度
    int GetListLength(SeqList L)
    { 
        return L.len;
    }
    
    //插入元素
    Status ListInsert(SeqList *L, int index, DataType elem)
    { 
        if (L->len == MAXSIZE)
        { 
            printf("线性表已满，无法插入！");
        }
        if (index >= MAXSIZE || index < 0 || index > L->len + 1)
        { 
            printf("%s", "Index is Error!");
            return ERROR;
        }
        for (int i = L->len; i > index - 1; i--)
        { 
            L->Mylist[i] = L->Mylist[i - 1];
        }
        L->Mylist[index - 1] = elem;
        L->len++;
    
        return TRUE;
    }
    
    //删除元素
    Status ListDeleteElem(SeqList *L, int index)
    { 
        if(index == 0 || index >= MAXSIZE || index < 0 || index > L->len)
        { 
            printf("%s", "Index is Error!");
            return ERROR;
        }
    
        for (int i = index - 1; i < L->len; i++)
        { 
            L->Mylist[i] = L->Mylist[i + 1];
        }
        L->len--;
    
        return TRUE;
    }
    
    //获取元素
    Status GetListElem(SeqList *L, int index, DataType *elem)
    { 
        if (index < 0 || index == 0 || index > L->len)
        { 
            printf("%s", "Index is Error!");
            return ERROR;
        }
        *elem = L->Mylist[index - 1];
    
        return TRUE;
    }
    
    //清空线性表
    Status CleanList(SeqList *L)
    { 
        for (int i = 0; i < L->len; i++)
        { 
            L->Mylist[i] = 0;
            L->len--;
        }
    
        return TRUE;
    }

main.c

#include <stdlib.h>
    #include "list.h"
    
    int main()
    { 
        SeqList L;
        ListInitiate(&L);
    
        for (int i = 1; i <= 10; i++)
        { 
            ListInsert(&L, i, i);
        }
    
        printf("线性表数据为:\n");
        int x;
        for (int i = 1; i <= 10; i++)
        { 
            GetListElem(&L, i, &x);
            printf("%d ", x);
        }
        printf("\n");
    
        printf("删除第四个元素后线性表数据为:\n");
        ListDeleteElem(&L, 4);
        for (int i = 1; i <= L.len; i++)
        { 
            GetListElem(&L, i, &x);
            printf("%d ", x);
        }
        printf("\n");
    
        printf("在第四个元素插入100，线性表数据为:\n");
        ListInsert(&L, 4, 100);
        for (int i = 1; i <= L.len; i++)
        { 
            GetListElem(&L, i, &x);
            printf("%d ", x);
        }
    
        printf("\n");
        return 0;
    }

6、运行结果：  
![在这里插入图片描述][20190731141915635.png]

[20190731141915635.png]: /images/20211116/5acde5219c5c4d66876f5c458e7de06c.png