数据结构之----线性表

线性表分为  顺序存储结构 和  链式存储结构

线性表的顺序存储结构： 线性表的顺序存储结构，指的是用一段地址连续的存储单元依次存储线性表的数据元素。
1，顺序表的结构：
        #define  MAXSIZE  20
        typedef  int  ElemType;
        typedef   struct
        {
               ElemType  data[MAXSIZE];     //数组
               int   length;       //顺序表长度
        }Sqlist;

        顺序表的第  i  个元素的下标为  i+1 

2，顺序表的插入与删除
     //插入数据
     void  Insertion(QList& list, int pos, int data)
     {
         //pos不是下标，从1开始
         if ((pos > list.length) || (pos >= MAX_SIZE))
         {
    
                return;
         }
         int posidx = pos - 1; //位置所对应的下标
         int maxidx = list.length - 1;
         for (int i = maxidx; i >= posidx; i--)
         {
               list.data[i + 1] = list.data[i];
               if (i == posidx)
               {
                    list.data[i] = data;
                }
          }
          list.length++;
    }
    //删除数据
    void  RemovePos(QList& list, int pos)
    {
          //pos不是下标，从1开始
          if ((pos > list.length) || (pos >= MAX_SIZE))
          {
                return;
          }
          int idxpos = pos - 1;
          int idxlen = list.length - 1;
          for (int i = idxpos; i < idxlen; i++)
          {
                list.data[i] = list.data[i + 1];
          }
          list.data[idxlen] = 0;
          list.length--;
     }
3，顺序表的优点和缺点
      时间复杂度为O(1)
      它比较适合元素个数不太变化，而更多是存取数据的应用。

      优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间
                可以快速地存取表中任一位置的元素
      缺点：插入和删除操作需要移动大量元素
                长度变化大难以确定存储空间的容量

二，链表

链表大概有三种：
                 单链表，循环链表，双向链表。

单链表节点：
             struct  LinkNode
             {
                    void*  data;
                    struct   LinkNode*  next;
             };
双向链表节点：
             struct  DulinkNode
             {
                    void*  data;
                    struct  DulinkNode* per;
                    struct  DulinkNode* next;
             }