一、单链表

1.单链表的定义

如图所示每个节点包含两个域:数据域和指针域。数据域存储数据元素，指针域存储下一个节点的地址，因此指针指向的类型也是节点类型。每个指针都指向下一个节点，都是朝一个方向的，这样的链表称为单向链表或单链表。

eg1: 若线性表采用链式存储，则表中各元素的存储地址（不一定是连续的）

2.单链表的操作

（1）创建（插入）

创建单链表分为头插法和尾插法两种，头插法是指每次把新节点插到头节点之后，其创建的单链表和数据输入顺序正好相反，因此也称为逆序建表。尾插法是指每次把新节点链接到链表的尾部，其创建的单链表和数据输入顺序一致，因此也称为正序建表。

头插法：

尾插法：

eg1: 在一个单链表中，已知q结点是p结点的前驱结点，若在q和p之间插入S结点则执行（C）

（2）查找

在一个单链表中查找是否存在元素e，可以定义一个p指针，指向第一个元素节点，比较p指向节点的数据域是否等于e。如果相等，查找成功，返回true;如果不等，则p指向p的下一个节点，继续比较，如果p为空，查找失败，返回false

eg: 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需比较（D）个结点

（3）删除

删除一个节点，实际上是把这个节点跳过去。根据单向链表向后操作的特性，要想跳过第i个节点，就必须先找到第i-1个节点，否则是无法跳过去的

eg：构造一个空的带表头结点的单链线性表L，并逆位序（头插法）输入n个元素的值；访问单链表L的第i个元素并打印输出；在单链表L的第i个元素之前插入新的元素e；在单链表表L中删除第i个元素，并用e返回其值；打印输出链表长度。

代码如下：

#include <stdio.h>
#include <stdlib.h>

//定义链表结点结构体
typedef struct LNode{
	int data;  //数据域
	struct LNode *next;  //指针域
}LNode,*LinkList;

//构造一个空的带表头结点的单链线性表L，并逆位序（头插法）输入n个元素的值
void CreateList(LinkList *L,int n){
	*L = (LinkList)malloc(sizeof(LNode));  //创建头节点,并返回头结点的指针
	(*L)->next = NULL;  //初始化头结点的next指针为NULL
	LinkList p;  //定义指向链表结点的指针
	int i;
	for(i = n;i>0;--i){  //循环n次，创建n个结点
		p  =(LinkList)malloc(sizeof(LNode));  //创建新结点
		scanf("%d",&p->data);  //输入数据
		p->next = (*L)->next;  //将新数据插入到表头，next指向当前头结点的下一个结点
		(*L)->next = p;  //头结点的next指向新结点
	}
}

//访问单链表L的第i个元素并打印输出
int GetElem(LinkList L,int i){
	LNode *p = L->next;  //从头结点的下一结点开始查找
	int j = 1;  //从1开始计数
	while(p&&j<i){  //遍历链表，直到找到第i个元素
		 p = p->next;
		 j++;
	}
	if(!p||j>i){  //未找到则退出程序
		printf("第%d个元素不存在\n",i);
		exit(1);
	}else{
		return p->data;  //找到则返回第i个元素的值
	}
}

//在单链表L的第i个元素之前插入新的元素e
void ListInsert(LinkList L,int i,int e){
	LinkList p = L;  //定义指向链表的指针，初始化为头结点
	int j = 0;  //计数器，初始值为0
	while(p&&j<i-1){  //遍历链表，寻找第i-1个节点
		p = p->next;
		j++;
	}
	if(!p||j>i-1){  //如果未找到第i-1个节点，表示插入位置无效，退出程序
		exit(1);
	}else{
		LinkList s = (LinkList)malloc(sizeof(LNode));  //创建一个新节点
		s->data = e;  //新节点数据域赋值为e
		s->next = p->next;  //新节点的next指向第i个节点
		p->next = s;  //第i-1个节点的next指向新节点
	}
}

//在单链表表L中删除第i个元素，并用e返回其值
int ListDelete(LinkList L,int i,int *e){
	LinkList p = L;  // 定义指向链表的指针，初始化为头节点
	int j = 0;  // 计数器，初始值为0
	while(p->next&&j<i-1){  // 遍历链表，寻找第i-1个节点
		p = p->next;
		j++;
	}
	if(!(p->next)||j>i-1){  // 如果未找到第i-1个节点，表示删除位置无效，退出程序
		exit(1);
	}else{
		LinkList q = p->next;  // 找到第i个节点
		*e = q->data;  // 返回删除节点的值
		p->next = q->next;  // 将第i-1个节点的next指向第i+1个节点
		free(q);  // 释放被删除节点的内存
		return 1;  // 返回1表示删除成功
	}
}

//打印输出链表长度
int ListLength(LinkList L){
	LNode *p = L;  //从头结点开始遍历链表
	int count = 0;  //计数器
	while(p->next){  //遍历链表直到末尾
		p = p->next;
		count++;  //每经过一个节点，计数器加一
	}
	return count;  //返回链表长度
}

//打印链表
void PrintList(LinkList L){
	LNode *p = L->next;  //从头结点的下一个节点开始遍历
	while(p){  //遍历链表直到末尾
		printf("%d",p->data);  //输出当前节点的data值
        p = p->next;  //移动到下一个节点
	}
	printf("");  //换行
}

int main(){
	LinkList L;
	int n,i,e;
	printf("请输入链表的长度：");
	scanf("%d",&n);
	CreateList(&L,n);  //创建链表
	printf("链表创建成功，内容为：");
	PrintList(L);
	
	//访问第i个元素
	printf("请输入要访问的元素位置：");
	scanf("%d",&i);
	int elem = GetElem(L,i);
	printf("第%d个元素为：%d",i,elem);
	
	//插入新元素
	printf("请输入要插入的位置和新元素值：");
	scanf("%d %d",&i,&e);
	ListInsert(L,i,e);
	printf("插入新元素后链表内容为：");
	PrintList(L);
	
	//删除第i个元素
	printf("请输入要删除的元素位置：");
	scanf("%d",&i);
	if(ListDelete(L,i,&e)){
		printf("删除成功，删除的元素是： %d",e);
		printf("删除后链表内容为：");
		PrintList(L);
	}
	
	//打印链表长度
	int length = ListLength(L);
	printf("链表长度为：%d",length);
	return 0;
}