第一章-线性表（有时间补充含有头结点和不含有头结点的链表插入删除操作）

定义：具有相同数据类型的n（n>=0）个数据元素的有限序列.
线性表是一种逻辑结构，表示元素之间的一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。

顺序表

定义：线性表的顺序存储，它是用一组地址连续的存储单元依此存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。逻辑顺序与物理顺序相同。

存储结构体（静态）

#define MaxSize 50           //定义线性表的最大长度
typedef struct{
	ElemType data[MAxSize];  //顺序表的元素
	int length;              //顺序表的当前长度
}Sqlist;                     //顺序表的类型定义

存储结构体（动态）

#define InitSize 100     //表长度的初始定义
typedef struct{
	ElemType *data;      //指示动态分配数组的指针
	int MAxSize,length;  //数组的最大容量和当前个数
}SeqList;                //动态分配数组顺序表的类型定义

动态分配并不是链式存储，它同样属于顺序存储结构，物理结构没有变化，依然是随机存取方式，只是分配的空间大小可以在运行时动态决定。

特点

• 随机访问，通过首地址和元素序号可在时间O(1)内找到指定的元素；
• 存储密度高，每个节点只存储数据元素；
• 插入和删除需要移动大量元素。

插入操作

bool ListInsert( Sqlist &L,int i,ElemType e ){
	if( i < 1 || i > L.length + 1)       //判断i的范围是否有效
		return false;
	if( L.length >= MaxSize )            //当前存储空间已满，不能插入
		return false;
	for( int j = L.length; j >= i; j--)  //将第i个元素及之后的元素后移
		L.data[j] = L.data[j-1];
	L.data[i-1] = e;                     //在位置i处放入e
	L.length++;                          //线性表长度加1
	return ture;
}

平均时间复杂度为O(n)

删除操作

bool ListDelete(SqList &L,int i,ElemType &e){
	if(i<1||i>L.length)          //判断i的范围是否有效
		return false;
	e = L.data[i-1];             //将被删除的元素赋值给e
	for(int j=i;j<L.length;j++)  //将第i个元素后的元素前移
		L.data[j-1] = L.data[j];
	L.length--;                  //线性表长度减1
	return true;
}

平均时间复杂度为O(n)

查找操作

int LocateElem(SqList L,ElemType e){
	inty i;
	for(i=0;i<L.length;i++)
		if(L.data[i]==e)
			return i+1;  //下标为i的元素值等于e，返回其位序i+1
	return 0;            //退出循环，说明查找失败
}

平均时间复杂度为O(n)

线性表的链式表示

单链表

定义：线性表的链式存储，通过一组任意的存储单元来存储线性表中的数据元素。

存储结构体

typedef struct LNode{    //定义单链表结点类型
	ElemType data;       //数据域
	struct LNode *next;  //指针域
}LNode,*LinkList;

头结点的优点：

• 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的 操作和在表的其他位置上的操作一致，无须进行特殊处理。
• 无论链表是否为空，其头指针都指向头结点的非空指针（空表中头结点的指针域为空）， 因此空表和非空表的处理也就得到了统一。

头插法建立单链表（存在头指针）

生成链表中的节点次序和输入数据的顺序一致

LinkList List_HeadInsert(LinkList &L){      //逆向建立单链表
	LNode *s;
	int x;
	L = (LinkList)malloc(sizeof(LNode));    //创建头节点
	L->next = NULL;                         //初始为空链表
	scanf("%d",&x);                         //输入节点的值
	while(x!=9999){                         //输入9999表示结束
		s = (LNode*)malloc(sizeof(LNode));  //创建新的节点
		s->data = x;
		s->next = s;                        //将新节点插入表中，L为头指针
		scanf("%d",&x);
	}
	return L;
}

平均时间复杂度O(n)

尾插法建立单链表

生成链表中的节点次序和输入数据的顺序一致

LinkList List_TailInsert(LinkList &L){  //正向建立单链表
	int x;                              //设元素类型为整型
	L = (LinkList)malloc(sizeof(LNode));
	LNode *s,*r = L;                    //r为表尾指针
	scanf("%d",&x);                     //输入结点的值
	while(x!=9999){                     //输入9999表示结束
		s = (LNode *)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;                          //r指向新的表尾节点
		scanf("%d,&x);
	}
	r->next = NULL;                     //尾结点指针置空
	return L;
}

平均时间复杂度O(n)

按序号查找结点

LNode *GetElem(LinkList L,int i){
	int j=1;             //计数，初始为1
	LNode *p = L->next;  //第一个结点指针赋给p
	if(i==0) return L;   //若i等于0，则返回头结点
	if(i<1) return NULL; //若i无效，则返回头结点
	while(p&&j<i){       //从第1个节点开始找，查找第i个结点
		p=p->next;
		j++;
	}
	return p;            //返回第i个结点的指针，若i大于表长，则返回NULL
}

平均时间复杂度O(n)

双链表

由于单链表只有一个指向后继的指针，使得单链表只能从头结点依次顺序向后遍历则导致访问前驱节点只能从头遍历，时间复杂度为O(n)，为了克服这个缺点，从而引入双链表，双链表每个节点存在两个指针prior和next，分别指向前驱节点和后继节点。

存储结构体

typedef struct DNode{           //定义双链表节点类型
	ElemType data;              //数据域
	struct DNode *prior,*next;  //前驱和后继指针
}DNode,*DLinkList;

注意：进行插入删除操作需要同时改变前驱指针和后继指针

循环单链表和循环双链表

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL,而改为指向头结点, 从而整个链表形成一个环。
对循环单链表设置尾指针效率会更高
循环双链表为空时，头结点的前驱和后继都是本身

静态链表

静态链表借助数组来描述线性表的链式存储结构（指针是结点的相对地址（数组下标），也称为游标）

存储结构体

#define MaxSize 50  //静态链表的最大长度
typedef struct {    //静态链表结构类型的定义
	ElemType data;  //存储数据元素
	int next;       //下一个元素的数组下标
}SLinkList[MaxSize];

顺序存储和链式存储的比较

• 存取（读写方式）
  • 顺序存储：可以顺序存取，也可以随机存取；
  • 链式存储：只能从表头顺序存取元素。
• 逻辑结构与物理结构
  • 顺序存储：逻辑上相邻的元素，对应的物理存储位置也相邻 ；
  • 链式存储：逻 辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。
• 查找、插入和删除操作
  • 顺序存储：
    • 按值查找：
      • 无序：时间复杂度O(n)
      • 有序：最快时间复杂度O(log(n))
    • 按序号查找：随机访问 O(1)
    • 插入、删除：平均需要移动半个表长的元素
  • 链式存储：存储密度不大，平均时间复杂度O(n) ，插入删除只需要修改相关节点的指针域。
• 空间分配：
  • 顺序存储
    • 静态：预先分配预先大量空间 ，容易造成内存溢出；
    • 动态：需要移动大量元素，操作效率降低
  • 链式存储：操作灵活高效

如何选取存储结构

1. 基于存储考虑：难以估计存储规模或者长度，选择链式存储；
2. 基于运算考虑：根据序号查找选择顺序存储，插入删除操作选择链式存储；
3. 基于环境考虑：顺序存储比较稳定，但如果需要频繁进行插入删除等操作更改元素选择链式存储（动态性较强）