链表之单链表的实现_按需所取

链表的特点：

        1：空间上按需所取；

        2：物理空间不连续

                        

 链表在物理空间上的不连续，方便增删查改；

单链表包括存储的数据和指向下一个节点的指针

链表基础结构由结构体实现

typedef int LIST;//方便更改类型
typedef  struct SList
{
	LIST data;
	struct SList* next;
}SList;

主要有四个功能：

增删查改；

     1：增加又可分为从头增加、从尾增加、从某个元素前增加；

                                尾增：

void Singlelist()
{
	SLIST* p = NULL;//定义一个标头
	ListData(&p, 1);
	listprint(p);//打印
}
void ListData(SLIST** pphead, LIST x)
{
	SLIST* newnode = (SLIST*)malloc(sizeof(SLIST));//为新节点开辟空间
	if (newnode == NULL)
		return;
	newnode->data = x;
	newnode->next = NULL;//最后一个单链表的指针指向空
	if (*pphead == NULL)//判断链表是否为空
	{
		*pphead = newnode;
	}
	else
	{
		SLIST* replica = *pphead;
		while (replica->next != NULL)
		{
			replica = replica->next;
		}
		replica->next = newnode;//存放下一节点的地址
	}
}

                 头增:

void ListData1(SLIST** pphead, LIST x)//头增
{		
 
	SLIST* newnode = BuyBode(x);
	if (*pphead == NULL)//判断链表是否为空
	{	
		newnode->next = NULL;
		*pphead = newnode;
	}
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
 
 
}

从某个元素后面增加:

                要实现这一点，首先要找到要增加的位置；就需查找；

  查找元素：

SLIST* NodeSeek(SLIST* phead,LIST x)//查找
{
	SLIST* replica = phead;
	while (replica != NULL)
	{
		if (replica->data == x)
			return replica;
		replica = replica->next;
	}
	return NULL;
}

                接着实现在某个元素前面增加节点：

SLIST* pos = NodeSeek(p, 3);
	if (pos)
	{
		InsertNode(&p, pos, 10);
	}
 
void InsertNode(SLIST** pphead,SLIST*pos, LIST x)
{
	if (pos == *pphead)
	{
		ListData1(pphead, x);//当要被插入的位置是第一个元素前时，就相当于头增
	}
	else
	{
		SLIST* newnode = BuyBode(x);
		SLIST* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	}
	
}

以上增查就完成了；

接着来实现删除：

                删除分为从头删除、从尾删除，删除某个位置的值；

                        头删

void HeadDel(SLIST** pphead)//头删
{
	SLIST* next = (*pphead)->next;
	free(*pphead);
	*pphead = next;
}

                尾删

void EndDel(SLIST** pphead)//尾删
{
	if (*pphead == NULL)//如果链表为空
		return;
	else if ((*pphead)->next == NULL)//如果链表只有一个元素
	{
		free(*pphead);
		*pphead = NULL;
	}
 
	else//链表有多个元素
	{
		SLIST* rev = NULL;
		SLIST* replica = *pphead;
		while (replica->next != NULL)//查找最后一个元素
		{
 
			rev = replica;//存放replica前一个元素
			replica = replica->next;
		}
		free(replica);
		rev->next = NULL;
	}
 
}

        删除某个位置的值

pos = NodeSeek(p, 3);//查找元素3的节点
		if (pos)
		{
			DelNode(&p, pos);
		}
void DelNode(SLIST** pphead, SLIST* pos)//删除指定位置元素
{
	if ((*pphead) == pos)
	{
		HeadDel(pphead);
	}
	else
	{
		SLIST* sev = *pphead;
		while (sev->next != pos)
		{
			sev = sev->next;
		}
		sev->next = pos->next;
		free(pos);
	}
}

            本篇文章就再次结束了，不完善的地方可以指出或者自行修改，谢谢大家