顺序表

线性表 （线性结构）

• 特点

  1. 存在唯⼀的首数据元素
  2. 存在唯一的尾数据元素
  3. 除首数据元素外，每个数据元素均有一个前驱
  4. 除尾数据元素外，每个数据元素均有一个后驱

• 常用运算

  一般有以下几种常用运算：

  1. 检索。检索就是在数据结构里查找满足一定条件的节点。
  2. 插入。往数据结构中增加新的节点。
  3. 删除。把指定的结点从数据结构中去掉。
  4. 更新。改变指定节点的一个或多个字段的值。

• 顺序存储

​ 线性表的顺序存储是一组地址连续的存储单元依次存储线性表的数据元素，特点是, 逻辑上相邻的数据元素,其物理次序也是相邻的,只要确定了起始位置，表中任一元素的地址都可以根据索引乘单个元素存储单元的长度获取。

1. 顺序表的结构定义

   #define maxlen 100 //定义顺序表中元素个数最多有几个
   #define true 1
   #define false 0
   
   typedef int ElementType;
   typedef int bool;
   
   typedef struct
   {
   ElementType *data; //ElementType是元素的类型 依具体情况而定
   int listLength; //便于时刻了解顺序表里元素的个数
   }ContiguousList; //顺序表的名称
   

   2. 构造一个空的顺序线性表

      bool InitList(ContiguousList *L){
         L->data =  malloc(sizeof(ElementType) *maxlen);   //开辟空间
         if (!L->data) //若开辟失败
         { 
             return false;
         }
         L->length = 0; //初始化长度
         return true;
      }
      

   3. 销毁顺序线性表L

      bool destroyList(ContiguousList *L){
       free(L->data);//销毁数据空间
       L->data = NULL;//指向NULL
       L->length = 0;//重置长度
       free(L);//释放L
       return true;
      }
      

   4. 将L重置为空表

      bool ClearList(ContiguousList *L){
       L->length = 0;//操作结果：将L重置为空表
       return true;
      }
      

   5. 判断是否为空表

      bool ListEmpty(ContiguousList L)
      {
          if(L.length==0)
              return true;
          else
              return false;
      }
      

   6. 返回L中数据元素个数

      int ListLength(ContiguousList L)
      {
          return L.length;
      }
      

   7. 在第i个位置插入 e

      //插入  非空，避免越界
      bool ListInsert(ContiguousList *L,int i, ElementType e){
       if (i < 1 || i>L->length + 1) return false;
       if (L->length == maxlen) return false;
       if (i <= L->length)
       {
           for (int j = L->length - 1; j>= i-1; j--)
           {
               L->data[j+1] = L->data[j];
           }
       }
       L->data[i-1] = e;
       ++L->length;
      
       return true;
      }
      

   8. 用e返回L中第i个元素的值

      bool GetElem(ContiguousList L,int i, ElementType *e){
          //判断i值是否合理
          if(i<1 || i > L.length) return  false;
          //data[i-1]单元存储第i个数据元素.
          *e = L.data[i-1];
          
          return true;
      }
      

   9. 删除第i个元素

      bool ListDelete(ContiguousList *L,int i){
       if (L->length == 0) return false;
       if (i < 1 || i>L->length + 1) return false;
       for (int j = i; j < L->length; j++)
       {
           L->data[j-1] = L->data[j];
       }
       L->length--;
       return true;
      }
      

   10. 获取cur_e的前驱 pre_e

       bool PriorElem(ContiguousList L,ElemType cur_e,ElemType* pre_e)
       {
           int i = 2;
           ElemType *p = L.data + 1;
           while(i<=L.length && *p!=cur_e)
           {
                   p++;
                   i++;
           }
           if(i>L.length) return false;
           else
           {
                   *pre_e = *--p;
                   return true;
           }
       }