Data Structure Notes

引言

笔记

笔记中所有代码将采用 c/cpp 代码编写与测试。

线性表

顺序表

顺序表结构体定义

• 线性表顺序存储类型描述（静态分配）

  # define MAX_SIZE 50
  
  typedef struct SqList{
      ElemType data[MAX_SIZE];
      int length;
  };

• 动态分配

  # define INIT_SIZE = 100
  
  typedef struct SeqList{
      ElemType *data;
      int max_size, length;
  };

顺序表基本操作

• 插入操作

  bool InsertList(SqList &L, int i, ElemType e)
  {
      if(i < 1 || i > L.length + 1)
          return false;
      if(L.length >= max_size)
          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
  }

• 删除指定位置的元素并返回元素的值

  bool DeleteList(SqList &L, int i, ElemType &e)
  {
      if(i < 1 || i > L.length)
          return false;
      e = L.data[i-1];
      for(int j = i; j < L.length; ++j)
          L.data[j-1] = L.data[j];
      L.length--;
      return true;
  }

• 按值查找

  int LocateElem(SqList L, ElemType e)
  {
      for(int i = 0; i < L.length; ++i)
          if(L.data[i] == e)
              return i+1;
      return 0;
  }

链表

栈和队列

串

树与二叉树

图

查找

排序

感谢