DataStructure

by MarkfuGod

Contiguous List(linear Construct)

$$ \begin{gather} 线性关系：结构中数据元素之间存在着一对一的关系 \\ 用指针来实现链式的存储结构（既有数值的内容，也有下一个数据的地址）\\ \end{gather} $$

$$ 抽象数据类型(ADT):Abstract\_Data\_Type $$

ADT List{
  数据对象：D = {a_i|a_i \in Elemset, i = 1,2,3...,n};
  数据关系：R = {<a_i-1,a_i>| a_i-1,a_i \in D(i = 2,3,...,n)}
  基本操作:
  InitList(&L);
 DestroyList(&L);
  ListInsert(&L,i,e);//i在1到i+1的位置，在i之前插入新的数据元素e，L长度加一
  ListDelete(&L,i,&e);//i在1到n的位置，删除第i个数据元素，并e返回其值，L长度-1
  ListTraverse(&L,visited());//对线性表中每个元素调用visited();
  ListEmpty(L);
  ListLength(L);
  GetElem(L,i,&e);//用e返回L中第i个数据元素的值
  LocateElem(L,e,compare())；//返回L中第一个与e满足compare()的数据元素的位置序号
  PriorElem(L,cur_e,&pre_e);//cur就是current，pre_e返回的是他的前驱(注意cur不是一第一个，否则失败)
  NextElem(L,cur_e, &next_e);
  ... etc//FIXME: 等待补充;
}ADT List

Initialization

$$ \begin{gather} Loc(a_{i+1}) = Loc(a_i) + l\\ 常用：Loc(a_i)=Loc(a_1)+(i-1)\times l \\优点：找地址十分方便，只需进行一次运算，时间复杂度为O(1); \\任意元素可以随机存取,地址连续，依次存放，类型相同::数组 \\线性表表长可变，而数组长度不可以动态定 \end{gather} $$

#define List_Init_Size 100
typedef struct{
  ElemType elem[List_Init_Size];
  int length;
}SqList;

类c语言操作的补充

typedef struct{
  ELemType data[];//ELemType:可以是char，float
  //typedef chae Elemtype
  int length;
}
typedef struct {
  ElemType *data;//想想上学期讲指针的那时候，可以用data存储数据的首地址，之后开辟空间
  int length;
}SqList;//不要忘了加载 stdlib.h!
 /*---------------------------------------------------------*/
  #c++的动态存储分配
  new 类型名T(初值列表) int *p1 = new int; or int *p1 = new int(10);
   成功：T类型的指针，指向新分配的内存；
   失败：NULL；
  delete 指针P delete p1;
   释放P所指向的内存，P必须是new操作的返回值；

#c++参数传递
   &:取地址， *：看地址
   引用类型作为参数：给一个对象提供替代的名字
/*--------如下---------------*/
 int i = 5;
 int &j = i;\\相当于直接对同个地址所在的值进行操作，j相当于也指向i的地址
 i = 7;
 cout << i << j ; \\ 会输出i=7，j=7；
/***********************************/
int main(){
    int a, b;
    swap_t(a,b);
    cout << a << b;
}
int swap_t(int& a, int& b) {
    int t;
    t = a;
    a = b;
    b = t;
}

说明

From——Markfugod