数据结构术语

结构是指数据间的关系

数据结构是指 相互之间存在某种特定关系的数据元素的集合

数据结构包括三方面
	数据的逻辑结构
	数据的存储结构
	数据的运算
一个算法的设计取决于选定的逻辑结构，算法的实现依赖于采用的存储结构
	
线性 一对一
树状 一对多
网状 多对多

数据结构是一个二元组 (D,R), D是数据元素的有限集, R是D上关系的有限集

数据结构的5个重要特性 (算法的特征)
有穷性
确定性
可行性
输入, 输出

算法要求
可读性 健壮性 效率与储存需求

时间复杂度排序
O(1) < O(log₂n) < O(n) < O(n*log₂n ) < O(n2)< O(n3)…<O(2n)<O(3n)<…<O(n!)

顺序线性表

0.线性表类型定义

同一性
有穷性
有序性

1. 顺序表定义

• 定义

typedef struct
{
	char data[max]; //数据(数组)
	int length;   //长度
}sqlist,L  //结构体名

• 读取数据(点操作)

读取表里面的数据
int A;
A = sqlist.data[i];

读取表长
int lenght;
length = sqlist.length;

2. 顺序表相关操作

• 初始化

  void initList(SqList &L){
  	L.length = 0;
  }

• 插入数据

  //L为结构体, i为插入位置, e为插入元素
  int sqLiistInsert(sqlist &L, int i, char e){
      //处理特殊情况
      if(i<1||i>L.length){
          return -1;
      }
      //判断是否满
      if(L.length>=L.size){
          ......
      }
      //具体插入操作
      char *p, *q;
      q = &(L.elem[i-1]); //将q赋值为第i个元素的位置(因为是获取的地址,不是值), 从第i个元素开始就要向后移动一位
      //for循环中, p为最后一个元素的位置, 依次将最后一个元素, 倒数第二个元素...向后移动一位, 直到插入元素i的位置
      for(p = &(L.data[L.length-1]), p>=q; p--){
          *(p+1) = *p; //元素依次向后移动一位
      }
      
      //将新元素赋值到i的位置
      *q = e;
      
      //长度加一
      L.length++;
      return 0;
  }

  //其他移动方法
  for(i = L.length - 1, i >= p, i--){
      L.data[i+1] = L.data[i];
  }
  L.data[p] = e;

  ​ 插入时间复杂度

  平均 n/2, 最坏 n

• 删除数据

  //i为删除元素的位置, y为返回删除元素
  int delete(Sqlist &L, int x, int *y){
  	int j;
      //删除位置错误
      if(x<1 || x>Llength){
          return -1;
      }
      else{
          *y = L.data[i-1];
          //j为要删除的位置, 将后面的元素依次向前移动一位
          for(j=x; j<=Length-1; j++){
              L.data[j-1] = L.data[j];
          }
          L.length--;
      }
  }

  删除时间复杂度

  (n-1)/2

• 按值查找

  int finddata(Sqlist &L, int e){
      int i;
      for(i =0; i < L.length; i++){
          if(e == L.data[i])
              return 0;
      }
      return -1;
  }

• 无序表合并

  void mergelist(list la, list lb, list &lc){
      initlist(lc)//初始化
      int i = 1, j = 1, k = 0;
      la_len = listlength(la);
      lb_len = listlength(lb);
      
      for(i = 1; i < lb_len; i++){
          e = listget(lb,i) //获取lb中的元素
          if(!listlocal(la, e)){ //在la中无此元素
              listinsert(la,++la_len, e)//插入元素
          }
      }
  }

• 缺点

  1. 插入和删除操作时需要移动大量元素。
  2. 要给长度变化较大的线性表预先分配空间，利用率不好。
  3. 表的容量难以扩充

链表

特点: 用一组任意的存储单元存储线性表的数据元素（可连续可不连续）

单链表

定义

typedef struct Lnode
{
	int data;
	Struct Lnode *next;
}Lnode,*linklist;

取用data

Lnode S;
int b;
b = S -> data;

取第i个元素

Linklist ListGet(linklist L,int i)  //取第i个元素
{
    p=L->next;
    j=1;
    While(p&&j<i){
        p=p->next;++j;    //指针后移
    }    
    If(!p||j>i)
        return error;
   	e=p->data;
    Return OK;
}

插入

Linklist listinsert_L(linklist L,int i, elemtype e){
	p = L;                //p指针指向头结点，（方便从头查找第i位）
    j = 0;  
    While(p&&j<i-1){
        p = p->next;
        ++j;
    }      //查找第i-1个结点
    if (!p||j>i-1) 
        return error;        //若i不合法
    s = (linklist)malloc(sizeof(Lnode)); 
    s->data = e;    //生成新结点
    s->next = p->next;  //讲p的next赋值给s的next
    p->next = s;          //p的next变为s
    Return ok;
}

删除

与插入不同的部分
q = p->next;       //q为要删除的节点
p->next = q->next;       //将q的next赋值给p的next
e = q->data;
free(q);  

插入删除时间复杂度

O(n)

尾插法

Linklist linklistcreate(){
    Linklist L；
    L=(Lnode*)malloc(sizeof(Lnode));  //生成头结点L
    L->next=NULL; 
    r=L;          //尾指针r赋初值
    scanf(&x);
    while(x!=flag){
        s=(Lnode*)malloc(sizeof(Lnode));   //生成新结点
        S->data=x; //新结点赋值
        s->next=NULL; 
        r->next=s;  //结点连入链表中，尾插！
        r=s;       //r始终指向最后一个结点
        Scanf(&x);
    }
    Return L;
}

头插法

Linklist linklistcreate()//头插
{
Linklist L；
L=(Lnode*)malloc(sizeof(Lnode));  //*生成头结点L
L->next=NULL;   
scanf(&x);
while(x!=flag)
{s=(Lnode*)malloc(sizeof(Lnode));   //生成新结点
S->data=x;                  //新结点赋值
s->next=NULL; 
s->next=L->next;  //两根链的改变，将新结点加入链表中
L->next=s;      
scanf(&x);
}
return L;
}

合并

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc)
{ 
    pa=La->next;
    pb=Lb->next;
 	Lc=pc=La;//用La的头结点作为Lc的头结点
  	while(pa&&pb)
    {
        if(pa->data <= pb->data)//先插入较小的值
         {
            pc->next=pa;
            pc=pa;
            pa=pa->next;//继续将pa的下一个节点赋值给pc
        }
      	else
      	{
           	pc->next=pb;
            pc=pb;
            pb=pb->next;
        }
    }
  	pc->next=pa?pa:pb;//插入剩余段
  	free(Lb);//释放Lb的头结点
}

循环链表

循环条件不是P或P->next是否为空，而是P->next=H

只剩两个个元素

q=L->next;
p->data=q->data;
L->next=q->next;
free(q);

不是最后两个元素

q=p->next;
p->data=q->data;
p->next=q->next;
free(q);

合并循环链表

LinkList   merge(LinkList LA, LinkList LB)  //合并两个循环链表的首尾连接起来  
{      
    linklist *p,  *q; 
    p=LA;   
    q=LB; 
    while(p->next! =LA) 
        p=p->next;       // 找到表LA的表尾
    while(q->next! =LB) 
        q=q->next;       // 找到表LB的表尾
    q->next=LA;  
    // 修改表LB 的尾指针， 使之指向表LA 的头结点 
    p->next=LB->next; 
    // 修改表LA的尾指针， 使之指向表LB 中的第一个结点
    free(LB);  
    return(LA); 
} 

双向链表

插入

s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;

栈和队列