单链表的相关操作

单链表的创建

• 关于带头结点与不带头结点，不带头结点表示指针指向的第一个结点就是要存放数据的结点，而带头结点表示指针指向的第一个结点内数据域不存任何数据，其指向的下一个结点才是存放数据的第一个结点。两者看似无区别，实际上区别很大：

/*不带头结点*/
typedef struct LNode { //定义单链表结点类型 
	ElemType data;	//每个结点存放一个数据元素 
	struct LNode *next;	//指针指向下一个结点 
}LNode,*LinkList;
//初始化一个空的单链表
bool InitLink(LinkList &L) {
	L = NULL;	//空表，暂时没有任何结点 
	return true;
} 
//判断单链表是否为空
bool Empty(LinkList L) {
	if(L == NULL) {
		return true;
	}else {
		return false;
	}
} 
void test01() {
	LinkList L;	//声明一个指向单链表的指针 
	InitLink(L);	//初始一个空表 
} 

/*带头结点*/
typedef struct LNode { //定义单链表结点类型 
	ElemType data;	//每个结点存放一个数据元素 
	struct LNode *next;	//指针指向下一个结点 
}LNode,*LinkList;	//强调为结点和强调为单链表 
//初始化一个空的单链表
bool InitLink(LinkList &L) {
	L = (LNode *)malloc(sizeof(LNode));	//分配一个头结点
	if(L == NULL) {	//内存不足，分配失败 
		return false; 
	}
	L->next = NULL;	//头结点之后暂时还没有结点 
	return true;
} 
//判断单链表是否为空
bool Empty(LinkList L) {
	if(L->next == NULL) {
		return true;
	}else {
		return false;
	}
}
void test02() {
	LinkList L;	//声明一个指向单链表的指针 
	InitLink(L);	//初始一个空表 
} 

单链表的插入

按位序插入

• 对于带头结点插入的分析：
  1. i=1(插在表头)
     1. 程序自上而下执行；
     2. 执行到while循环时，不满足 j<i-1 的条件，不执行循环；
     3. 实现在表头位置插入一个新元素结点；
     4. 最好时间复杂度：O(1)
  2. i=m(m<链表长度，插在表中)
     1. 程序自上而下执行；
     2. 执行到while循环时，直到找到要插入位置的前一个位置结点，否则循环继续执行；
     3. 实现在表中位置插入一个新元素结点；
  3. i=n(插在表尾)
     1. 程序自上而下执行；
     2. 执行到while循环时，直到找到要插入位置的前一个位置结点，否则循环继续执行，此时找到当前链表的最后一个结点；
     3. 实现在表尾位置插入一个新元素结点；
     4. 最坏时间复杂度：O(n)
  4. i=n+1(大于表长)
     1. 程序自上而下执行；
     2. 执行到while循环时，跳出条件不再是因为找到了位置，而是因为此时指针指向了NULL；
     3. 执行if条件判断，发现i-1个结点位置不存在，即i值不合法，无法找到位置就无法插入新元素结点，故直接返回，插入失败；

//在第i个位置插入元素e 
/*带头结点*/ 

bool ListInsert(LinkList &L, int i, ElemType e) {
	if(i < 1) {
		return false;
	}
	
	//未封装
	LNode *p;	//指针P指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;		//L指向头结点，头结点是第0个结点(不存数据) 
	while(p!=NULL && j<i-1) {	//循环找到第 i-1 个结点 
		p = p->next;
		j ++;
	}
	//封装后
	//LNode *p = GetElem(L, i-1); //找到第 i-1 个结点
	
	//未封装
	if(p == NULL) {		//i值不合法 
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;	//将结点s连到P之后 
	p->next = s;		//插入成功 
	return true;
	//封装后
	//return InsertNextNode(p, e);
} 

注意：进行插入时的指针指向顺序不可变，必须先执行s->next = p->next将插入结点与其插入后的后继结点相关联，再执行p->next = s将插入结点与其前驱结点相关联。若顺序颠倒，则会使新插入结点的next指针指向自己，而使插入位置之后的数据全部丢失。

• 对于不带头结点插入的分析：
  1. i=1(插在表头)
     1. 程序自上而下执行；
     2. 插入位置为第一个位置时，需要单列出来，并且需要更改头指针L；
  2. 其余分析与带头结点的分析类似

//在第i个位置插入元素e 
/*不带头结点*/ 

bool ListInsert(LinkList &L, int i, ElemType e) {
	if(i < 1) {
		return false;
	}
	if(i == 1) {
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;	//头结点指向新结点 
		return true;
	}
	LNode *p;	//指针P指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;		//L指向头结点，头结点是第0个结点(不存数据) 
	while(p!=NULL && j<i-1) {	//循环找到第 i-1 个结点 
		p = p->next;
		j ++;
	}
	
	//未封装
	if(p == NULL) {		//i值不合法 
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;	//将结点s连到P之后 
	p->next = s;		//插入成功 
	return true;
	//封装后
	//return InsertNextNode(p, e);
} 

结论：不带头结点写代码更加不方便，更建议使用带头结点的方式

指定结点的后插操作

• 由于单链表指针是向后的，所以某位置之前的元素结点为未知区域，而某位置之后的元素结点为可知区域

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e) {
	if(p == NULL) {
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL) {
		return false;	//内存分配失败 
	}
	s->data = e;	//用结点s保存数据元素e
	s->next = p->next;
	p->next = s;	//将结点s连接到p之后 
	return true; 
} 

• 时间复杂度：O(1)

指定结点的前插操作

• 方式一：在原本后插操作的参数基础上，传入头指针，循环查找p的前驱q，再对q进行后插法，但有可能只进行局部操作，无法获取到他的头指针信息
  • 时间复杂度：O(n)
• 方式二：偷天换日：在指定位置后插入一个新的元素结点，将指定位置的数据值赋值到新插入的元素结点上，再将需要插入的元素数据对原本位置上的元素数据值进行覆盖
  • 时间复杂度：O(1)

//前插操作：在p结点之前插入元素e
bool InsertNextNode(LNode *p, ElemType e) {
	if(p == NULL) {
		return false;
	}
	LNode *s = (LNode *)malloc(sizeof(LNode));
	if(s == NULL) {
		return false;	//内存分配失败 
	}
	s->next = p->next;
	p->next = s;		//将结点s连接到p之后 
	s->data = p->data;	//将p中元素复制到s中 
	p->data = e;		//p中元素覆盖为e 
	return true; 
} 

单链表的删除

按位序删除

• 方式：传入链表的头结点，找到所要删除结点的前驱结点再进行删除
  • 最坏、平均时间复杂度：O(n)
  • 最好时间复杂度：O(1)

bool ListDelete(LinkList &L, int i, ElemType e) {
	if(i < 1) {
		return false;
	}
	
	//未封装
	LNode *p;	//指针P指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;		//L指向头结点，头结点是第0个结点(不存数据) 
	while(p!=NULL && j<i-1) {	//循环找到第 i-1 个结点 
		p = p->next;
		j ++;
	}
	//封装后
	//LNode *p = GetElem(L, i-1); //找到第 i-1 个结点
	
	if(p == NULL) {	//i值不合法 
		return false;
	}
	if(p->next == NULL) {	//第 i-1 个结点之后已无其他结点
		return false; 
	} 
	LNode *q = p->next;		//令q指向被删除结点 
	e = q->data;			//用e返回元素的值 
	p->next = q->next;		//将*q结点从链中断开 
	free(q);				//释放结点的存储空间 
	return true;			//删除成功 
}

指定结点的删除

• 方式一：传入头指针，循环寻找p的前驱结点，再进行删除
  • 时间复杂度：O(n)
• 方式二：偷天换日
  • 时间复杂度：O(1)

//删除指定结点p
bool DeleteNode(LNode *p) {
	if(p == NULL) {	//i值不合法 
		return false;
	}
	LNode *q = p->next;		//令q指向被删除结点 
	p->data = p->next->data;//和后继结点交换数据域 
	p->next = q->next;		//将*q结点从链中断开 
	free(q);				//释放结点的存储空间 
	return true;			//删除成功 
}

极限情况：若要删除的p恰好是最后一个结点，则方式二在执行到p->data = p->next->data会出现空指针错误，所以此方式不适用，只能使用方式一从表头开始依次寻找p的前驱可保证适用所有情况

单链表的查找

按位查找

• 分析：
  1. 正常情况下找到第i结点的数据并返回
  2. 不正常情况，若i<0则返回false；若想要查找的位置i大于表长度，则while因为p==NULL而跳出循环，最终返回null
  3. 只需判断返回值即可知道此次是否查找到相应位置数据元素
• 时间复杂度：O(n)

LNode * GetElem(LinkList L, int i) {
	if(i < 0) {
		return false;
	}
	LNode *p;	//指针P指向当前扫描到的结点 
	int j = 0;	//当前p指向的是第几个结点 
	p = L;		//L指向头结点，头结点是第0个结点(不存数据) 
	while(p!=NULL && j<i) {	//循环找到第i个结点 
		p = p->next;
		j ++;
	}
	return p;
}

按值查找

• 平均时间复杂度：O(n)

LNode * LocatElem(LinkList L, ElemType e) {
	LNode *p = L->next;
	//从第1个结点开始查找数据域为e的结点 
	while(p!=NULL && p->data!=e) {
		p = p->next;
	}
	return p;	//找到后返回该结点指针，否则返回NULL 
}

• 求表的长度
  • 时间复杂度：O(n)

int Length(LinkList L) {
	int len = 0;    //统计表长
	LNode *p = L;
	while(p->next != NULL) {
	    p = p->next;
	    len ++;
	}
	return len;
}

• 带头结点和不带头结点的逻辑区别
  • 普遍性(高内聚)：
    • 对于带头结点的单链表来说，链表的每一个含数据的结点都拥有唯一的后继和唯一的前驱，结构更相似严谨，之后设计的算法执行的操作更具有普遍性；
    • 而对于不带头结点的单链表来说，第一个结点不具有唯一前驱，整体结构与其余结点结构就有相对性的差异，之后设计的算法以及操作就需要将其单列出来讨论，增加代码长度与复杂性；
• 带头结点和不带头结点的代码区别
  • 对于带头结点的单链表来说，由于各结点逻辑上结构都是一样的，故在实现功能时，代码较为固定；
  • 对于不带头结点的单链表来说，需要将第一个结点与其余结点分开讨论，增加代码的复杂性，代码更长更复杂