2023-03-02  阅读(344)
原文作者:返回主页亦小海 原文地址:https://www.cnblogs.com/lisen10

1. 线性表的定义

  • 线性表L是n(n≥0)个具有相同属性的数据元素a1,a2,a3,…,an组成的有限序列,其中序列中元素的个数n称为线性表的长度。
  • 当n=0时称为空表,即不含有任何元素。
  • 常常将非空的线性表L(n>0)记作:L=(a1,a2,…an)
  • 其中ai-1为ai的直接前驱,ai+1为ai的直接后继。a1为表头元素,an为表尾元素。
  • 线性表(Linear list)是最简单且最常用的一种数据结构,其逻辑结构为线性结构。
  • 线性表具有下列特点:

    存在唯一的一个没有前驱的(头)数据元素;

     存在唯一的一个没有后继的(尾)数据元素;

    每个数据元素(除表头元素)均有一个直接前驱;

    每个数据元素(除表尾元素)均有一个直接后继;

    表中数据元素的类型是相同的

2. 线性表的基本运算

数据结构的运算是定义在逻辑结构层次上的,而运算的具体实现则是建立在存储结构上的。

(1)初始化线性表L:InitList(L)

(2)求线性表L的长度:GetLength(L)

(3)按序号取元素:GetNode(L,i)

(4)按值查找:LocateList(L,e)

(5)插入新元素:InsertList(L,i,e)

(6)在线性表中删除元素:DeleteList(L,i)

(7)把已有线性表置为空表:ClearList(L)

3. 线性表的实现

  • 顺序表在具体实现时,一般用高级语言中的数组来对应连续的存储空间。设最多可存储MaxLen个元素,在C语言中可用数组data[MaxLen]来存储数据元素,为保存线性表的长度需定义一个整型变量length。
  • 线性表的第l,2,…,n个元素分别存放在此数组下标为0,1,…,length-1数组元素中,如下图所示

202303022154166261.png

c语言示例:

    #include<stdio.h>
    
    # define MaxLen 100
    
    typedef struct
    {
        int no;
        int score;
    }DataType;
    
    typedef struct
    {
        DataType data[MaxLen];  // 定义存储表元素的数组
        int length;
    }SeqList;
    
    // 顺序表的初始化
    void InitList(SeqList *p){ p->length=0; }
    
    // 顺序表的创建
    void CreatList(SeqList *p){
        int i = 0;
        DataType x;
        printf("请输入学号和成绩,以学号-1为结束:\n");
        scanf("%d",&x.no);
        while(x.no!=-1)
        {
            scanf("%d",&x.score);
            p->data[i]=x;
            scanf("%d",&x.no);
            i++;
        }
        p->length=i;
    }
    
    // 顺序表中插入元素
    void InsertList(SeqList *p, int i, DataType x){
        for(int j=p->length-1; j>i-1; j--){
            p->data[j+1] = p->data[j];
        }
        p->data[i-1] = x;
        p->length++;
    }
    
    // 按序号顺序表中元素
    DataType GetNode(SeqList *L, int i){
        if(i<1 || i>L->length) printf("position error\n");
        return L->data[i-1];
    }
    
    // 在顺序表中查找元素
    int LocateList(SeqList *p, int no)
    {
        int i = 0;
        while(i<p->length && p->data[i].no != no)
            i++;
    
        if(i<p->length)  return i+1;  //第i+1个元素,i从0开始
        else return -1;
    }
    
    // 修改第i个元素
    void EditList(SeqList *p,int i,DataType e)
    {
        if(i<1 || i>p->length)     
        { 
           printf("position error\n");
        }
        p->data[i-1]=e;
    }
    
    // 删除第i个元素
    void DeleteList(SeqList *L,int i) 
    {
        if(i<1 || i>L->length)     
        { 
           printf("position error\n");
        }
       for(int j=i;j<=L->length-1;j++)
          //向前移动元素
          L->data[j-1]=L->data[j];  
       L->length--; 
    }
    
    void PrintList(SeqList *p)
    {
        int i;
        for(i=0;i<p->length;i++)
            printf("[%d,%d]\n",p->data[i].no,p->data[i].score);
        printf("\n");
    }
    
    void main(){
        SeqList L;
        DataType e;
    
        InitList(&L);
    //创建
        CreatList(&L);
        PrintList(&L);
    //插入
        e.no=9;  e.score=80;
        InsertList(&L,L.length+1,e);
        printf("插入后:\n");
        PrintList(&L);
    //查询
        int i=LocateList(&L,3);
        if (i>0)
            printf("学号为3的成绩: %d \n",GetNode(&L,i).score);
        else
            printf("Can't find the elem.\n");
    //修改
        e.no=3;  e.score=65;
        int m=LocateList(&L,3);
        EditList(&L,m,e);
        printf("修改后:\n");
        PrintList(&L);
    //删除
        int k=LocateList(&L,2);
        DeleteList(&L,k);
        printf("删除学号为2的记录后:\n");
        PrintList(&L);
    }

202303022154171152.png

4. 线性表的顺序存储结构的特点

优点:顺序表中的任意数据元素的存储地址可由公式直接导出,因此顺序表可以“随机存取”其中的任意元素。

不足:

  • 需预先分配相应的存储空间。预分配空间过小,存储空间不便于扩充;预分配空间过大,容易造成空间浪费。
  • 插入与删除运算的效率很低,插入、删除操作时需移动大量数据。
阅读全文
  • 点赞