@TOC

一、链表

1.链表的概念

一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针连接次序实现的。

2.链表优点

1.空间上按需所给空间
2.在头部和中间插入时，不需要挪动数据

二、单链表的实现

1.函数的定义和结构体的创建——list.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef  int slistdatatype;
typedef  struct slistnode
{
	slistdatatype  data;
	struct s* next;
}slistnode;

void stackpushback(slistnode**pphead, slistdatatype x);
void slistprint(slistnode* phead);
void stackpopback(slistnode**phead);
void stackpushfront(slistnode** phead, slistdatatype x);
void stackpopfront(slistnode** phead);
slistnode* slistfind(slistnode* phead, slistdatatype x);
void slistinsertafter(slistnode**pphead, slistnode* pos, slistdatatype x);
void slisteraseafter(slistnode**pphead,slistnode*pos);

2.函数的调用——test.c

#include"list.h"
int main()
{
	slistnode* phead = NULL;
	stackpushback(&phead, 1);//尾插
	stackpushback(&phead, 2);
	stackpushback(&phead, 3);
	stackpushback(&phead, 4);
	slistprint(phead);//打印
	stackpopback(&phead);//尾删
	slistprint(phead);
	stackpushfront(&phead,5);//头插
	slistprint(phead);
	stackpopfront(&phead);//头删
	slistprint(phead);
	slistnode* pos1 = slistfind(phead, 2);//查找位置
	slistinsertafter(&phead, pos1, 6);//指定插
	slistprint(phead);
	slistnode*pos2=slistfind(phead,2);
	slisteraseafter(&phead,pos2);//指定删
	slistprint(phead);
	return 0;
}

3.二级指针问题

此时发现传过去的&pehad，接收是二级指针,传址调用才能真正改变主函数中 phead 指针
但比如 打印或者查找位置并没有改变phead指针，所以也就不用传地址了

4.单链表的接口实现

1.尾插

void stackpushback(slistnode** pphead, slistdatatype x)//尾插
{
	slistnode* newnode = (slistnode*)malloc(sizeof(slistnode));
	if (newnode != NULL)
	{
		newnode->data = x;
		newnode->next = NULL;
	}
	if (*pphead == NULL)//为空时
	{
		*pphead = newnode;
	}
	else//不为空时
	{
		slistnode* tail = *pphead;
		while (tail->next != NULL)//遍历到最后一个节点
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

2.尾删

void stackpopback(slistnode** pphead)//尾删
{
	if (*pphead == NULL)//为空
	{
		return;
	}
	else if ((*pphead)->next == NULL)//只有一个节点时
	{
		free(*pphead);
		*pphead = NULL;
	}
	else//正常情况下  要把尾节点free   尾节点的前一个节点的指针置为NULL 
	{
		slistnode* prev = NULL;//prev指向前一个节点
		slistnode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		tail = NULL;
		prev->next = NULL;
	}
}

3.头插

void stackpushfront(slistnode** pphead, slistdatatype x)//头插
{
	slistnode* newnode = (slistnode*)malloc(sizeof(slistnode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->next = *pphead;
	*pphead = newnode;
}

4.头删

void stackpopfront(slistnode** pphead)//头删
{
	if (*pphead == NULL)//若为空
	{
		return;
	}
	else
	{
		slistnode* newnode = (slistnode*)malloc(sizeof(slistnode));
		newnode = (*pphead)->next;//*pphead的后一个节点作为*pphead
		free(*pphead);
		*pphead = NULL;
		*pphead = newnode;
	}
}

5.查找位置

slistnode* slistfind(slistnode* phead, slistdatatype x)//查找位置(返回该位置，不是下标）
{
	slistnode* cur = phead;
	while (cur != NULL)
	{
		if (cur->data == x)
		{
			return cur;//如果找到了则返回该位置
		}
		cur = cur->next;
	}
	return NULL;//没找到直接返回NULL
}

6.指定插

void slistinsertafter(slistnode** pphead, slistnode* pos, slistdatatype x)//指定插
{
	assert(pos);//pos为找到的位置， x是要插入的值
	slistnode* newnode = (slistnode*)malloc(sizeof(slistnode));
	newnode->data = x;
	newnode->next = NULL;
	newnode->next = pos->next;//先将新节点与pos后面的节点连接
	pos->next = newnode;//再将pos与新节点连接
}

这里一定不要先将pos与x先连接，否则会使pos->next找不到2

7.指定删

void slisteraseafter(slistnode** pphead, slistnode* pos)//指定删
{
	assert(pos);//pos有可能传过来NULL
	slistnode* prev = *pphead;
	while (prev->next != pos)//prev为pos的前一个节点  
	{
		prev = prev->next;
	}
	prev->next = pos->next;//将pos的前一个节点与pos的后一个节点连接
	free(pos);
	pos = NULL;
}

8.打印

void slistprint(slistnode* phead)//打印
{
	slistnode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}