数据结构2——线性表

Posted by DD on 2020-06-06

2. 线性表

2.1 线性表的定义&基本操作

  • 线性表:是具有相同数据类型的n(n≥0)个数据元素的有限 序列,其中n为表长,当n = 0时线性表是一个空表。若用L命名线性表,则其一般表示为 L = (a1, a2, … , ai, ai+1, … , an)
  • 线性表的特点:
    • 表中元素个数有限
    • 表中元素具有逻辑上的顺序性,在序列中哥哥元素排序有其先后次序
    • 表中元素都是数据元素,每个元素都是单个元素
    • 表中元素的数据类型都相同,这意味着每隔元素占有相同大小的存储空间
    • 表中元素具有抽象性,即讨论元素间一对一的逻辑关系,而不考虑元素究竟表示的内容
    • 线性表是一种逻辑结构,表示元素之间一对一相邻的关系
  • 线性表的九种基本操作:
    • InitList(&L):初始化表。构造一个空的线性表。
    • DestroyList(&L):销毁操作。销毁线性表,并释放线性表L所占的内存空间。
    • LocateElem(L, e):按值查找操作。在表L中查找具有给定关键字值的元素。
    • GetElem(L, i):按位查找操作。获取表L中第i个位置上的元素的值。
    • ListInsert(&L, i, e):插入操作。在表L中的第i个位置上插入指定元素e。
    • ListDelete(&L, i, &e):删除操作。删除表L中第i个位置的元素,并用e返回删除元素的值。
    • PrintList(L):输出操作。按前后顺序输出线性表L的所有元素值。
    • Empty(L):判空操作。若L为空表,则返回True,否则返回False。
    • Length(L):求表长。返回线性表L的长度,即L中数据元素的个数。

      Tips:
      ①对数据的操作(分析思路) —— 创销、增删改查
      ②C语言函数的定义 —— <返回值类型> 函数名 (<参数1类型> 参数1,<参数2类型> 参数2,……)
      ③实际开发中,可根据实际需求定义其他的基本操作
      ④函数名和参数的形式、命名都可改变(Reference:严蔚敏版《数据结构》)
      ⑤什么时候要传入参数的引用“&” —— 对参数的修改结果需要“带回来”——C++

2.2 顺序表

  • 顺序表的定义:
    • 线性表的顺序存储又称为顺序表,顺序表是指一组地址连续存储的存储单元依次存放线性表的元素,从而使得逻辑上相邻的两个元素在物理位置上也相邻。
顺序表 内存地址
a1 LOC(A)
a2 LOC(A)+sizeof(ElemType)
a3 LOC(A)+2*sizeof(ElemType)
... ...
an LOC(A)+(n-1)*sizeof(ElemType)
  • 数组静态分配:
    #define MaxSize 10 //定义最大长度
    typedef struct
    {
       ElemType data[MaxSize]; //
       int length;     //顺序表当前长度
    }SqList;    //顺序表的类型定义(静态分配方式)
    
  • 数组动态分配:
    #define MaxSize 50
    typedef struct
    {
       ElemType * data;
       int length;
    }SqList;
    
  • 顺序表基本操作:

    • 插入操作:

      bool ListInsert(SqList &L, int i, ElemType e)
      {
          if (i<1 || i>L.length+1)  //判断插入数据位置是否合法
              return false;
          if (L.length >= MaxSize)
              return false;
          for (int j=L.length; j>=i; j--)  
          {
              L.data[j] = L.data[j-1];   //把每一个数据元素往后移一位
          }
          L.data[i-1] = e;    //赋值
          L.length++; //顺序表长度增加
      
          return true;
      }
      //最好时间复杂度O(1)
      //平均时间复杂度O(n)
      //最坏时间复杂度O(n)
      
    • 删除操作:

      bool ListDelete(SqList &L, int i, ElemType &e)
      {
          if (i<1 || i>L.length+1)  //判断删除数据位置是否合法
              return false;
          e = L.data[i-1];    //保存删除的数据
          for (int j=i; j<L.length; j++)  
          {
              L.data[j-1] = L.data[j];   //把每一个数据元素往前移一位
          }
          L.length--; //顺序表长度减1
      
          return true;
      }
      //最好时间复杂度O(1)
      //平均时间复杂度O(n)
      //最坏时间复杂度O(n)
      
    • 按值查找操作:

      int LocateElem(SqList L, ElemType e)    //参数:查找的表,查找的参数
      {
          int i;
          for (i=0; i<L.length; i++)
          {
              if(L.data[i] == e)  //判断此时位置元素的值是否与需要查询的值相等
                  return i+1; //返回物理地址
          }
      
          return 0;   //表示没有查找到
          }
      //最好时间复杂度O(1)
      //平均时间复杂度O(n)
      //最坏时间复杂度O(n)
      

2.3 单链表:

地址 单链表 指针域
addr0 a1 addr4
addr4 a2 addr6
addr6 a3 addr9
... ... ...
addr an null
  • 单链表的定义:

    • 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。
    • 优点:链表的第一个位置和其它位置的操作统一,空表和非空表的操作统一。
      typedef struct LNode
      {
      ElemType data;
      struct LNode *next;
      }LNode, *LinkList;
      
  • 单链表的基本操作:

    • 头插法建立单链表:

      LinkList List_HeadInsert(LinkList &L)   //当我们对传入的参数修改时,往往需要传入一个引用类型的变量
      {
          LNode *s;   //插入的节点
          int x;  //插入的数据,数据可以任意类型
      
          L = (LinkList)malloc(sizeof(LNode));    //初始化头结点,用malloc函数分配节点大小的空间
          L->next = NULL;
          scanf("%d", &x);
          while(x != 9999)
          {
              s = (LNode*)malloc(sizeof(LNode));  //初始化新节点
              s->data = x;    //赋值
              s->next = L->next;  //将新节点的next指针指向头结点
              L->nest = s;    
              scanf("%d", &x);
          }
          return L;
      }
      //最坏时间复杂度O(n)
      
    • 尾插法建立单链表:
      LinkList List_TailInsert(LinkList &L)
      {
          int x;  //所插入的数据
          L = (LinkList)malloc(sizeof(LNode));    //初始化头结点
          LNode *s, *r = L;   //s:插入节点指针,r:尾结点指针,初始化为头结点
          scanf("%d", &x);
          while(x != '\n')
          {
              s = (LNode*)malloc(sizeof(LNode));  //初始化插入节点
              s->data = x;    
              r->next = s;    //将原先最后一个节点指针指向新节点
              r = s;  //将尾指针指向插入节点
              scanf("%d", &x);
          }
          r->next = NULL; //最后一个节点指向为空
          return L;   //返回单链表
      }
      //最坏时间复杂度:O(n)
      
    • 按序号查找操作:
      LNode *GetElem(LinkList L, int i)   //查找的表以及查找的序号
      {
          int j = 1;
          LNode *p = L->next;
          if (i == 0) //表示头结点,直接返回L
          {
              return L;
          }
          if (i < 1)  //不合法,返回空
          {
              return NULL;
          }
          while(p && j<i) //遍历链表当前节点不能为空,当前遍历是否到了寻找的位置        
          {
              p = p->next;
              j++;
          }
          return p;
      }
      //最坏时间复杂度:O(n)
      
    • 按值查找操作:
      LNode *LicateElem(LinkList L, ElemType e)
      {
          LNode *p = L->next;
          while(p!=NULL && p->data!=e)    //当前节点是否为空且当前节点的值不为查找的值
          {
              p = p->next;
          }
          return p;
      }
      //最坏时间复杂度O(n)
      
    • 插入节点: