关于数据结构:线性表

1. 定义和定义时留神的细节
线性表：（1）个数无限（2)都为数据元素且类型雷同（3）是一种逻辑构造（程序表和链表才是存储构造）

操作定义时，&L 和 L: 带 & 意味着在操作中会对 L 进行扭转，即把参数批改带回来，所以须要带 &.

2. 程序表的定义

#define InitSize 10
typedef struct{Elemtype *data;....... 指向程序表元素的指针（Elemtype 是示意指针指向的元素的类型，如果是单链表就是 struct LNode)，通过 InitList 中的 malloc 函数使它指向数组的起始地址
    int MaxSize;
    int length;
}Sqlist;
=
struct{
 Elemtype *data;
    int MaxSize;
    int length;
}
typedef struct Sqlist;

void InitList(Sqlist &L)
{L.data=(Elemtype *)malloc(InitSize*sizeof(int));
   L.length=0;
   L.MaxSize=InitSize;
}

3. 程序表的特点
（1）存储密度大，每个元素只存储数据
（2）随机拜访，第 i 个元素：data[i-1]
(3) 拓展容量不便
（4）插入，删除不变

4. 程序表的增删查的工夫复杂度（每个元素被的概率乘以均匀次数）
插入：O(n)
删除：O(n)
按值查找：O(n)

5. 单链表的定义和判断

typedef struct LNode{
  Elemtype data;
  struct LNode *next;.... 指向 LNode 的指针
}LNode,*LinkList;
=
struct LNode{
  Elemtype data;
  struct LNode *next;.... 指向 LNode 的指针
}
 
typedef struct LNode LNode;
typedef struct LNode* LinkList;

初始化：bool InitList(LinkList &L){.... 带头节点
L=(LNode*)malloc(sizeof(LNode));
L-next=null;
}

留神：LNode * p 示意指向一个节点的指针，用来示意一个节点；LinkList p 更多的示意一个单链表的头节点，通常用来定义一个单链表。

判断空表：
带头节点：L-next==null;
不带：L==null;

6. 单链表的建设

头插法(单链表逆置）LinkList List_HeadInsert(LinkList &L){
LNode *s;
int x;
InitList(L);
scanf("%d",&x);
while(x != 999){s=(LNode *)malloc(sizeof(LNode));
    s-data=x;
    s-next=L-next;
    L-next=s;
    scanf("%d",&x);
}
return L;
}

尾插法
LinkList List_TailInsert(LinkList &L){
LNode *s,*r=L;
int x;
InitList(L);
scanf("%d",&x);
while(x != 999){s=(LNode *)malloc(sizeof(LNode));
    s-data=x;
    r-next=s;
    r=s;
    scanf("%d",&x);
}
r-next=null;
return L;
}

7. 双链表的建设

typedef struct DNode{
  Elemtype data;
  struct DNode *prior,*next;.... 指向 LNode 的指针
}DNode,*DLinkList;

bool InitDlinkList(DLinkList &L){L=(DNode*)malloc(sizeof(DNode));
  if(L==Null)
      return false;
  L-prior=null;
  L-next=null;
  return true;
} 

8. 双链表的插入

s-next=p-next;
p-next-prior=s;
s-prior=p;
p-next=s;
必须先实现插入节点 s 左边的操作再执行右边的操作

不可随机存取，按位按值查找只能遍历

9. 循环链表
循环单链表：尾指向头；
循环双链表：尾指向头，头指向尾；

10. 动态链表
调配一片集中的区域来存放数据
增删操作不须要大量挪动元素
查找只能从头节点开始，容量不能扭转
实用场合：（1）不反对指针的低级语言（2）数据元素固定不变的场合

11. 总结
（1）程序表：反对随机存取，大片空间调配不便

链表：调配简略，不可随机存取

（2）弹性，增删，表长难于预估：链表

 查，表长能够预估：程序表

（3）两者逻辑构造雷同，但存储构造不同