单链表概述

一张图简单解释下单链表的结果，对头节点，头指针，首节点混肴的同学可以再看看
这里写图片描述

以下是单链表的头文件和相关操作，这门课很抽象，我个人认为只在脑海中去理解很难做到，因为指针指来指去是个人都会晕，建议大家用笔在纸上画出来，更容易理解
比如单链表的尾插法，在纸上一画瞬间理解了

代码实现

linklist.h如下：

#include <stdio.h>
#include <malloc.h>

typedef int ElemType;
typedef struct Node{
	ElemType data;
	struct Node *next;
}LinkList;

LinkList.cpp如下：

#include "linklist.h"
#include <stddef.h>

void headInit(LinkList * &ls, int msg[], int n);//头插法
void tailInit(LinkList * &ls, int msg[], int n);//尾插法
void printLinkList(LinkList *ls);//输出链表
void destory(LinkList *&ls);//销毁链表
int getLength(LinkList *ls);//获取长度
bool getElementByIndex(LinkList *ls, int pos, ElemType &e);//通过下标获取元素
int getElementIndex(LinkList *ls,ElemType e);//获取元素的下标
bool insert(LinkList *&ls,int pos, ElemType e);
bool deleteElement(LinkList *&ls, int pos, ElemType &e);

/**
 * 相比于顺序表，单链表不需要连续的空间，没有冗余的空间，而且不用扩容，插入和删除操作效率高
 * 但是其他操作复杂
 */
int main()
{
	LinkList * ls;

	ElemType arr1[] = {1,2,3,4,5};
	headInit(ls,arr1,5);
	printLinkList(ls);

	ElemType arr2[] = {6,7,8,9,10};
	tailInit(ls,arr2,5);
	printLinkList(ls);

	printf("\n单链表的长度是:%d\n",getLength(ls));

	ElemType e;
	if(getElementByIndex(ls,5,e)){
		printf("第%d个元素的值是:%d\n",5,e);
	}

	int pos = getElementIndex(ls,10);
	if(pos){
		printf("%d的位置是:%d\n",10,pos);
	}

	e = 11;
	if(insert(ls,6,11)){
		printf("%d插入成功\n",e);
	}
	printLinkList(ls);

	if(deleteElement(ls,5,e)){
		printf("\n要删除的第%d个元素是%d,已删除成功\n",5,e);
	}
	printLinkList(ls);
	destory(ls);
    return 0;
}

/*
	头插法
*/
void headInit(LinkList * &ls, ElemType msg[], int n) {
	int i;
	LinkList *node;
	ls = (LinkList*)malloc(sizeof(LinkList));
	ls->next = NULL;
	for (i = 0; i < n; i++){
		//产生一个新节点
		node = (LinkList*)malloc(sizeof(LinkList));
		node->data = msg[i];
		//把该节点插到头节点的后面，画图
		node->next = ls->next;
		ls->next = node;
	}
}
/*
	尾插法:定义一个尾指针指向尾节点，因为每次都在尾节点后面插，就把尾节点当作头节点去插
*/
void tailInit(LinkList * &ls, int msg[], int n) {
	ls = (LinkList*)malloc(sizeof(LinkList));
	ls->next = NULL;
	int i;
	LinkList *node,*tail = ls; //尾指针最初也指向头节点
	for (i = 0; i < n; i++){
		node = (LinkList*)malloc(sizeof(LinkList));
		node->data = msg[i];
		tail->next = node;
		tail = node; //尾指针指向新插入的节点，即尾节点
	}
	//一开始没加这句，导致tail->next成为野指针,导致一直输出
	tail->next = NULL;
}

//打印
void printLinkList(LinkList *ls) {
	LinkList *p = ls->next;
	while (p != NULL) {
		printf("%d\t", p->data);
		p = p->next;
	}
}

/**
 * 链表的消耗要把每一个节点都free
 */
void destory(LinkList *&ls){
	LinkList * head = ls, * p = ls->next;
	while(p!=NULL){
		free(head);
		head = p;
		p = p->next;
	}
	//销毁最后一个
	free(head);
}

//判断是否是空表
bool isEmpty(LinkList *ls){
	return (ls->next == NULL);
}

//求表长
int getLength(LinkList *ls){
	LinkList * p = ls;
	int i = 0;
	while(p->next != NULL){
		i++;
		p = p->next;
	}
	return i;
}

//获取第i个节点
bool getElementByIndex(LinkList *ls, int pos, ElemType &e){
	int i = 0;
	LinkList * p = ls;
	while(i<pos && p!=NULL){
		p = p->next;
		i++;
	}
	//循环结束后要么i<pos不成立，也就是找到了，要么ls==NULL，也就是到表尾了
	if(p == NULL){
		printf("不存在第%d个元素\n",pos);
		return false;
	}else{
		e = p->data;
		return true;
	}
}

//获取元素下标
int getElementIndex(LinkList *ls,ElemType e){
	//用pos记录下标
	int pos = 1;
	LinkList *p = ls->next;
	while(p != NULL && p->data != e){
		p = p->next;
		pos++;
	}
	//对循环结束后的条件进行判断
	if(p == NULL){
		return 0;
	}else{
		return pos;
	}
}

/**
 * 单链表的插入需要记录前一个节点,所以找到pos-1即可
 */
bool insert(LinkList *&ls,int pos, ElemType e){
	int i = 0;
	LinkList * p = ls; //不要直接用ls
	//pos-1,假如在第5个位置插入，就找出第四个节点，让它指向e
	while(i < pos-1 && p != NULL){
		i++;
		p = p->next;
	}
	if(p==NULL){
		return false;
	}else{
		//为插入的节点分配空间
		LinkList * node = (LinkList *) malloc (sizeof(LinkList));
		node->data = e;

		//插入
		node->next = p->next;
		p->next = node;
		return true;
	}
}

//删除同样也要找到pos-1个节点
bool deleteElement(LinkList *&ls, int pos, ElemType &e){
	int i = 0;
	LinkList * p = ls , *temp;
	while(i < pos-1 && p!=NULL){
		p = p->next;
		i++;
	}
	if(p==NULL){
		return false;
	}else{
		//删除节点，记得先把地址用temp保存起来，用于free
		temp = p->next;
		e = temp->data;
		p->next = temp->next;
		free(temp);
		return true;
	}
}

输出结果

5	4	3	2	1	6	7	8	9	10	
单链表的长度是:5
第5个元素的值是:10
10的位置是:5
11插入成功
6	7	8	9	10	11	
要删除的第5个元素是10,已删除成功
6	7	8	9	11