「数据结构」单链表的建立及其基本操作

目录

• 线性表的链表表示
• 单链表的头插法和尾插法
• 单链表的基本操作

一、线性表的链式表示

#define ElemType int //将ElemType指定为int类型

typedef struct LNode {	//定义单链表的节点类型
	ElemType data;	// 数据域
	struct LNode* next;	//指针域
}LNode,*LinkList;
复制代码

二、头插法和尾插法

• 头插法

  1. 每次插入的新结点为当前链表的表头

  2. 结点次序与输入次序相反

代码实现：

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=L->next;
		L->next=s;
		scanf("%d",&x);
	}	
	return L;
}
复制代码

• 尾插法

  1. 每次插入的新结点在表尾结点之后

  2. 结点次序与输入次序相同

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;
		scanf("%d",&x);
	}
	r->next=NULL;
	return L;
}
复制代码

三、单链表的基本操作

注：位序从1开始

• 按序号查找结点值：从单链表的第一个结点出发，找到并返回第i个结点，否则返回最后一个结点指针域null

LNode *GetElem(LinkList &L,int i){
	int j=1;	//计数
	LNode *p=L->next;	// p指向单链表的第一个结点。
	if(i==0){	//i为0时返回头结点
		return L;
	}
	if(i<1){	//i值不合法，返回NULL
		return NULL;
	}
	while(p&&j<i){
		p=p->next;
		j++;
	}
	return p;
}
复制代码

• 按值查找表结点：查找单链表中对于给定一个值e的查找，存在返回该结点，不存在则返回NULL。

LNode *LocateElem(LinkList &L,ElemType e){
	LNode *p=L->next;	//p指向第一个结点。
	while(p&&p->data!=e){
		p=p->next;
	}
	return p;	// 若未找到，p已指向尾结点的NULL域
}
复制代码

• 按位序插入结点：给定一个结点值和位序，将该结点插入到单链表的对应的位序的位置上。插入成功返回true，否则返回false。

bool ListInsert(LinkList &L,int i,ElemType e){
	if(i<1){	// i值不合法，返回false
		return false;
	}
	// 算法思想：扫描单链表至第i-1个位置，再进行插入操作。
	LNode *p;
	int j=0;	//计数
	p=L;
	while(p&&j<i-1){
		p=p->next;
		j++;
	}
	if(!p){	// i值不合法：超过表长度
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	// 注：以下三行代码中有顺序要求。
	s->data=e;
	s->next=p->next;
	p->next=s;
	return true;
} 
复制代码

• 指定结点的前插操作：后插操作太简单，有难度的是前插操作，而对于指定结点的前面部分的链表是神秘的未知区域。则现在就有了两种方式进行前插操作：1. 若给出了链表头指针，可选择遍历到该结点的前一个结点进行插入操作。 2. 若未给出链表头指针，则需要进行“偷天换日”，即进行后插，但是要交换数据域部分

// 以下只给出“偷天换日”的代码
bool ListPriorNode(LNode *p,ElemType e){
	if(!p){	// 所给结点为空返回。
		return false;
	}
	LNode *s=(LNode*)malloc(sizeof(LNode));
	if(!s){		//内存不足，分配空间失败
		return false;
	}
	// 交换数据域，并改变指针指向
	s->data=p->data;
	p->data=e;
	s->next=p->next;
	p->next=s;
	return true;
}
复制代码

• 按位序删除结点：删除单链表的第i个结点，成功返回true，失败返回false。并返回是否带回此次删除的数据值e（依实际要求为准）。

bool ListDelete(LinkList &L,int i,ElemType &e){
	if(i<1){
		return false;
	}
	int j=1;	//计数
	LNode *p=L->next;	// 让p指针指向单链表的第一个节点
	while(p&&j<i){
		p=p->next;
		j++;
	}
	if(!p||!p->next){		// i值超过链表表长或者i为最后一个结点
		return false;	
	}
	LNode *q=p->next;	// 让q指向被删除的结点
	e=q->data;
	p->next=q->next;
	free(q);
	return true;
}
复制代码

• 删除指定结点：与按位序删除一样，返回布尔值，(带回被删除的元素)。但是难度却有所不同，同样的算法思想同 指定结点的前插操作，但是若是最后一个结点，则无法处理，只能用带头指针的一次遍历寻找前驱结点。

bool DeleteNode(LNode *p){
	if(!p){
		return false;
	}
	LNode *q=p->next;
	p->data=q->data;
	p->next=q->next;
	free(q);
	return true;
}
复制代码