线性表

• 一·逻辑结构
• • • • 定义
• 二·存储结构
• • 1.顺序存储结构
  • 2.链式存储结构
• 三·插入删除
• • 1.顺序表
  • 2.链式表
• 四·元素移动次数和静态链表
• • 1. 移动次数
  • • • 1.1 插入移动次数
      • 1.2 删除移动次数
  • 2. 静态链表
  • • • 2.1 定义
      • 2.2 实现

一·逻辑结构

定义

线性表是具有相同特性数据元素的有限序列。

二·存储结构

1.顺序存储结构

2.链式存储结构

1. 2种链式存储结构（单链表）
   

2. 2种链表的判空条件
   

3. ex：双链表和循环链表
   双链表：比单链表多一个前驱指针（prior）
   
   

三·插入删除

1.顺序表

插入：插入到目的位置，而不是“见缝插针”！*从后往前，大到小*

//先判断是否合法：
if(p<0 || p>length || length==maxsize)
	return 0;//非法

//从末尾往前遍历，到待插位置p结束，(i+1) = (i)
//元素处理，length++。

删除：*从前往后，小到大*，依次覆盖。

//先判断是否合法：
if(p<0 || p>length-1)
	return 0;
//待删除元素赋值
//从待删除位置p往后遍历，到末尾结束，(i) = (i+1)
//length--

2.链式表

插入：更改指针的指向。*先连后，再连前*
		双链表新节点先连2端节点，再断掉2端间的连接

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

删除：

p->next = s->next;
free(s);

四·元素移动次数和静态链表

1. 移动次数

1.1 插入移动次数

1. 有 n+1 个插入位置
2. 插入位置为 i (0~n) 时，需要移动 n-i 次

1.2 删除移动次数

1. 有 n 个删除位置
2. 删除位置为 i 时，需要移动 n-i-1次

2. 静态链表

2.1 定义

为了简化链表结构，将指针变量改成 int 变量，其所指为下一节点在数组中的位置 。
由于一次性分配空间，所以该链表是静态的。
跟顺序表区分，顺序表内元素是连续的；静态链表中元素虽然物理上连续存储，逻辑可以不连续。

2.2 实现

//节点定义：
typedef struct
{
	int data;
	int next;
}SLNode;

//链表生成：
SLNode Slink[maxsize];
//常用操作：
int p = Ad0;
Slink[p].data;		//p->data
Slink[p].next;		//p->next

//插入：
Slink[q].next = Slink[p].next;
Slink[p].next = q;