线性表——单链表的增删改查（头插法，尾插法，按序号查找，按值查找，某个位置插入元素，某个位置删除元素）

一、链表的特点

二、链表的组成

两部分组成：数据域data和指针域next。最后一个为NULL。

三、代码实现

结构体

typedef int ElemType;
// 定义结构体
typedef struct LNode {
   
	ElemType data; // 数据域
	struct LNode* next; // 定义结构体指针，指向下一个结点。因为从上往下编译，所以不能简写
}LNode,*LinkList;

1.头插法

顾名思义，在头部插入

p.next本身指向a1，若想插入元素，应将q.next指向a1，p.next指向q

// 头插法新建列表
LinkList CreatList1(LinkList& L) {
   
	// 申请一个空间，带头结点的链表
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL; // L->data里边没放东西
	LNode* s;
	int x;
	scanf("%d", &x);
	while (x != 9999) {
   
		// 申请一个新空间给s，强制类型转换
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x; // 将读取的值给新空间的data成员
		s->next = L->next;
		L->next = s;
		scanf("%d", &x); // 新输入
	}
	return L;
}

2.尾插法

尾部插入数字

表尾结点指向插入的元素p->next=q,q成为表尾p=q

// 尾插法新建链表
LinkList CreatList2(LinkList& L) {
   
	// 申请空间，带头结点的链表
	L = (LinkList)malloc(sizeof(LNode));
	LNode* s, * r = L;
	int x;
	scanf("%d", &x);
	while (x != 9999) {
   
		// 给输入的元素申请空间
		s = (LNode*)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;// r指向新的表尾结点
		scanf("%d", &x);
	}
	r->next = NULL; //最后一个尾结点赋值NULL
	return L;

3.按序号查找值

注意一开始指向的头指针为空，因而要指向下一个结点。

// 按序号查找值
LinkList GetElem(LinkList L, ElemType &e) {
   
	if (