数据结构之线性表

基本概念

线性表(List):由零个或多个数据元素组成的有限序列。

特征:

1.线性表是一个序列。

2.0个元素构成的线性表是空表。

3.线性表中的第一个元素无前驱,最后一个元素无后继,其他元素有且只有一个前驱和后继。

4.线性表是有长度的,其长度就是元素个数,且线性表的元素个数是有限的,也就是说,线性表的长度是有限的。

线性表抽象数据类型

基于线性表的特征,线性表可以做如下操作:

  •  InitList(*L);//初始化操作,建立一个空的线性表
  •  ListEmpty(L);//若线性表为空,返回true,否则返回false
  •  ClearList(*L);//清空线性表
  •  GetElem(L,i,*e);//查找线性表中的第i个位置的元素值,并赋值给e
  •  LocateElem(L,e);//查找线性表L中与给定值e相等的元素,如果查找成功,则返回第一个相同的元素在L  //中的下标;否则,返回0表示失败
  •  ListInsert(*L,i,e);//在线性表L的第i个位置插入元素e
  •  ListDelete(*L,i,*e);//删除线性表L中第i个位置元素,并用e返回其值
  •  ListLength();//返回线性表L的长度

线性表和线性表可以进行叠加操作,线性表La和线性表Lb的并集操作,结果保存在La中的伪代码如下:

//实现线性表La和线性表Lb的并集操作,结果保存在La中  
    void UnionList(*La,Lb)  
{  
    //计算Lb长度  
    int lblength = ListLength(Lb);  
    //计算La长度  
    int laLength = ListLength(La);  
    int i ;  
    //便利Lb中所有元素,判断其是否在La中,若不在,则插入La中  
    for (i=0;i<length;i++)  
    {  
        ElemType temp = GetElem(Lb,i,*e);  
        if (LocateElem(La,temp)==0)  
        {  
            ListInsert(La,++laLength,temp);  
        }  
    }  
}  

线性表的存储结构

根据其字面意思,线性表是顺序存储的,用一段地址连续的存储单元依次存储线性表的数据元素。

如:

#define MAXSIZE 20;//存储空间初始分配量为20  
typedef int ElemType;//数据类型为int  
type struct  
{  
    ElemType data[MAXSIZE];//数组存储数据元素  
    intlength;//线性表长度  
}; 

关于线性表地址长度的计算

由于顺序存储结构是按照顺序存储的,所以每个数据元素的地址都可以根据第一个元素的地址推算出来。其计算公司LOC(ai) = LOC(a1)+ (i-1)*c

线性表的基本操作

线性表基本操作包含基本的CRUD操作。

插入操作

插入操作算法的思路是: 1.如果插入位置不合理,抛出异常。 2.如果线性表长度大于等于数组长度,则抛出异常或者增加数组长度。

例如:在线性表L的第i个位置插入元素e 

int ListInsert(Sqlist *L, int i, ElemType e)  {  
    //插入位置错误,返回0  
    if (i < 0 || i > L.Length)  
    {  
        return 0;  
    }  
  
    //线性表的长度大于等于数组的最大长度,返回0  
    if (L.Length >= MAXSIZE)  
    {  
        return 0;  
    }  
  
    int j = L.Length -1;  
    //从第i个元素到最后一个元素,每个元素后移一位  
    while (j >= i)  
     {  
         L.data[j+1] = L.data[j];  
         j--;  
     }  
  
    //第i个元素的位置放入e  
    L.data[i] = e;  
  
    //线性表长度加1  
    L.Length ++;   
}  

删除操作

删除操作的思路是: 1.如果删除位置不合理,抛出异常 2.取出删除元素 3.从删除位置开始遍历到最后一个元素,分别将她们都向前移动一个位置 4.表长减1

例如:我们要删除一个线性表的某一个元素

int ListDelete(SqList *L,int i,ElemType *e)  {  
    //如果删除的位置不对,则返回0  
    if (i < 0 || i > L.Length -1)  
    {  
        return 0;  
    }  
      
    *e = L.data[i-1];  
  
    for (j = i-1;i <L.Length-2;j++ )  
    {  
        L.data[j] = L.data[j+1];  
    }  
  
    L.Length --;  
    return 1;   
}  

查询操作

查询操作是比较简单的,例如:我们要在线性表中查询某个元素的位置。

int GetElem(SqList L,int i, ElemType * e)  
{  
    //线性表长度等于0或者获取元素位置错误返回0  
    if (L.Length == 0 || i < 0 || i > L.Length)  
    {  
        return 0;  
    }  
  
    返回第i个元素  
    *e = L.data[i-1];  
    return 1;  
}  

线性表的缺点

顺序表需要预分配一定长度的存储空间,不能动态增长,插入或删除比较麻烦。基于线性表的缺点,有了链式存储线性表。链式存储的特点:

typedef struct Node  
{  
    ElemType data;  
    struct Node *next;  
} Node;  
typedef struct Node *LinkList;  

线性表查询

算法思路是: 1.声明一个节点p指向链表第一个节点,初始化j从1开始 2.当j< i时,就遍历链表,让P的指针向后移动,不断指向下一个节点,j累加1 3.若到链表末尾p为空,则说明第i个元素不存在 4.否则查找成功,返回节点p的数据

int GetElem(LinkList L,int i,ElemType *e)  
{  
    int j;  
    LinkList p;  
    p = L->next;//p指向链表第一个节点  
    while (p && j < i )  
    {  
        p = p->next;  
        j++;  
    }  
  
    if(!p || count > i)  
        return 0;  
       
    *e = p->data;  
    return 1;  
}  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java学习

面试题18(以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是?)

以下关于集合类 ArrayList 、 LinkedList 、 HashMap 描述错误的是? A)HashMap实现Map接口,它允许任何类型的键和值对象,...

30750
来自专栏weixuqin 的专栏

数据结构学习笔记(线性表)

31150
来自专栏开发之途

Java集合框架源码解析之HashSet

12840
来自专栏LanceToBigData

Java集合源码分析(一)ArrayList

前言   在前面的学习集合中只是介绍了集合的相关用法,我们想要更深入的去了解集合那就要通过我们去分析它的源码来了解它。希望对集合有一个更进一步的理解!   既然...

27860
来自专栏与神兽党一起成长

说一说java.util.Arrays.ArrayList

java.util.Arrays.ArrayList(下文:Arrays.ArrayList)是java.util.Arrays的私有静态内部类,他实现的接口,...

12230
来自专栏小灰灰

JDK容器学习之LinkedHashMap(二):迭代遍历的实现方式

LinkedHashMap 如何保障有序的遍历 前一篇《JDK容器学习之LinkedHashMap (一):底层存储结构分析》 中介绍了LinkedHashM...

37570
来自专栏张俊红

数据结构—线性表

本篇开始,又会开始一个新的系列,数据结构,数据结构在算法或者是编程中的重要性不言而喻,所以学好数据结构还是很有必要的。本篇主要介绍数据结构的第一个结构——线性表...

14030
来自专栏十月梦想

ES6新的数据结构Set

Set一种新的数据结构,在之前数据的集合分为数组(Array)和对象(Object),ES6出现新的Set数据结构,和Map,这里先介绍一下Set.

19850
来自专栏余林丰

Java迭代器Iterator

 之前我们实现了迭代器模式,很多编程语言实际上已经内置了迭代器类,比如Java就为我们实现了迭代器Iterator。我们首先来看Iterator中的源码。 通过...

265100
来自专栏LeetCode

leetCode 77&39. Combinations & Combination Sum

Given two integers n and k, return all possible combinations of k numbers out of...

12500

扫码关注云+社区

领取腾讯云代金券