【数据结构】顺序表和单链表的定义与一些基本操作_顺序表和单链表的类型声明

一、单链表的定义

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以节点来表示的，每个结点的构成：date( 数据元素) + next(下个元素存储位置)

二、单链表的实现

struct LNode{                //定义单链表结点类型
    ElemType data;           //每个节点的数据域
    struct LNode *next;      //指向下一个节点的指针
};

不带头结点的单链表的创建及初始化：

#include <stdio.h>
#include <stdbool.h>
 
typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
bool InitList1(LinkList L) {	   //初始化不带头结点的单链表
	L = NULL;
	return true;
}
 
bool InitList2(LinkList L) {	   //初始化带头结点的单链表
	L = (LinkList)malloc(sizeof(LNode));
	if (L == NULL)
		return false;
	L->next = NULL;
	return true;
}
int main(){
	LinkList L;
	InitList1(&L);
	InitList2(&L);
	return 0;
}

 tips：虽然单链表的初始化对于头结点可有可无，但在实际解决问题时建议带头结点，写代码会更方便

三、单链表的基本操作

3.1、单链表的插入

①、带头结点的单链表

​​typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
bool ListInsert(LinkList L, int i, int e) {
	if (i < 1)			//i值不合法的情况
		return false;
	LNode* p = L;       //p从头结点指向扫描到的结点
	int j = 0;			//当前p指向的第j个结点
	while (p != NULL && j < i - 1)	//让p指向插入位序的前一个数据项
	{
		p = p->next;		
		j++;
	}
	if (p == NULL)		//i值超出链表容量的情况
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

在ListInsert函数中，我们首先对i的值进行判断，当i小于1，即i的值不合法，则返回false，再声明LNode型的指针p指向L的头结点，再声明j=0，通过循环来表示p当前指向第j个结点，当循环结束时，p指向i的前一个结点，这时需要判断p是否超出链表容量，下面用malloc函数开辟链表中一个结点大小的空间，再让s的数据域为e，s的next指针指向p的next指针，p的next指针指向s，这样就成功插入了一个结点

 ②、不带头结点的单链表

前面我们提到过，我们创建单链表时尽量选择添加头结点，如果没有头结点，那么在插入结点的时候就需要考虑i=1的特殊情况，因为没有头结点作为引入

​​typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
bool ListInsert(LinkList L, int i, int e) {
	if (i < 1)			//i值不合法的情况
		return false;
	if (i == 1)
	{
 
		LNode* s = (LNode*)malloc(sizeof(LNode));
		s->data = e;
		s->next = L;
		L = s;
		return true;
	}
	LNode* p = L;       //p从头结点指向扫描到的结点
	int j = 1;			//当前p指向的第j个结点
	while (p != NULL && j < i - 1)	//让p指向插入位序的前一个数据项
	{
		p = p->next;
		j++;
	}
	if (p == NULL)		//i值超出链表容量的情况
		return false;
	LNode* s = (LNode*)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return true;
}

3.2、单链表的删除

①、带头结点的链表

​​typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
bool ListDelete(LinkList L, int i, int e) {
	if (i < 1)			//i值不合法的情况
		return false;
	}
	LNode* p = L;       //p从头结点指向扫描到的结点
	int j = 0;			//当前p指向的第j个结点
	while (p != NULL && j < i - 1)	//让p指向插入位序的前一个数据项
	{
		p = p->next;
		j++;
	}
	if (p == NULL)		//i值超出链表容量的情况
		return false;
	LNode* q = p->next;		//q指向被删除的结点
	e=q->data;				//e存储被删除结点的数据
	p->next = q->next;		//被删除的结点的前一个结点指向被删除的结点的下一个结点
	free(q);				//释放节点的空间
	return true;
}

②、不带头结点的链表

​​typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
bool ListDelete(LinkList L, int i, int e) {
	if (i < 1)			//i值不合法的情况
		return false;
	if (i == 1) {
		LNode* q = L;
		e = L->data;
		L = L->next;
		free(q);
	}
 
	LNode* p = L;       //p从头结点指向扫描到的结点
	int j = 1;			//当前p指向的第j个结点
	while (p != NULL && j < i - 1)	//让p指向插入位序的前一个数据项
	{
		p = p->next;
		j++;
	}
	if (p == NULL)		//i值超出链表容量的情况
		return false;
	LNode* q = p->next;		//q指向被删除的结点
	e=q->data;				//e存储被删除结点的数据
	p->next = q->next;		//被删除的结点的前一个结点指向被删除的结点的下一个结点
	free(q);				//释放节点的空间
	return true;
}

3.3、单链表的查找

①、按位查找

//按位查找，返回第i个​​元素(带头结点)
typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
LNode* GetElem (LinkList L, int i) {
	if (i < 0)			//i值不合法的情况
		return NULL;
	LNode* p = L;       //p从头结点指向扫描到的结点
	int j = 0;			//当前p指向的第j个结点
	while (p != NULL && j < i)	//循环找到第i个结点
	{
		p = p->next;
		j++;
	}
	if (p == NULL)		//i值超出链表容量的情况
		return NULL;
	return p;
}

②、按值查找

//按值查找，返回第i个​​元素(带头结点)
typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
LNode* LocateElem (LinkList L, int e) {
	LNode* p = L;       //p从头结点指向扫描到的结点
	int j = 0;			//当前p指向的第j个结点
	while (p != NULL && p->data!=e)	//让p指向插入位序的前一个数据项
	{
		p = p->next;
	}
	if (p == NULL)		//超出链表容量的情况
		return NULL;
	return p;
}

3.4、单链表的建立

①、头插法

typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
LNode* LinkList_TailInsert (LinkList L) {   //头插法建立单链表
	int x;			//设置数据域的初始值
	L = (LNode*)malloc(sizeof(LNode));		//建立头结点
	L->next = NULL;
	LNode* s=L;
	scanf("%d", &x);
	while (x != 666)		//循环结束的条件
	{
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		s->next = L->next;
		L->next = s;
		scanf("%d", &x);
	}
	return L;
}

②、尾插法

typedef struct LNode {		//定义单链表结点类型
	int data;				//单链表数据域
	struct LNode* next;		//单链表指针域
}LNode, * LinkList;
 
 
LNode* LinkList_TailInsert (LinkList L) {   //尾插法建立单链表
	int x;			//设置数据域的初始值
	L = (LNode*)malloc(sizeof(LNode));		//建立头结点
	LNode* s, * r=L;
	scanf("%d", &x);
	while (x != 666)		//循环结束的条件
	{
		s = (LNode*)malloc(sizeof(LNode));
		r->next = s;
		s->data = x;
		r = s;
		scanf("%d", &x);
	}
	r->next = NULL;
	return L;
}