数据结构（不带头结点的单链表）

数据结构

单链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据
在写单链表的时候，需要对结构体有一定的了解（这里就不做过多的结构体介绍）

不带头结点的单链表

头结点一般在栈区或者数据区开辟且头结点不存储有效数据，但不带头结点的单链表是以一个指针来存储第一个结点的位置，相当于带头结点单链表的头结点只存储地址而不存储目前的结点个数

一、创建不带头结点的单链表
不带头结点的单链表通过结构体创建

typedef int ElemType;

typedef struct LNode
{
	ElemType  data;
	LNode *next;
}LNode,*LinkList;

二、单链表所实现的功能（不带头结点的单链表）
1.计算结点数

static int GetLinkList_Length(LinkList head)       //计算结点数
{
	LinkList p = head;
	int length = 0;
	while(p!=NULL)
	{
		length++;
		p = p->next;
	}
	return length;
}

2.找目标结点的前一个

static LinkList FindPrior(LinkList head,int pos)       //找目标结点的前一个
{
	LinkList p = head;
	while(pos-1)
	{
		p = p->next;
		pos--;
	}
	return p;
}

3.单链表创建结点并赋值

static LinkList ApplyNode(ElemType val,LinkList next)     //创建节点及赋值
{
	LinkList p = (LinkList)malloc(sizeof(LNode));
	if(p == NULL)  return NULL;
	p->data = val;
	p->next = next;
	return p;
}

4.单链表初始化

void Init_LinkList(LinkList *head)           //初始化
{
	if(head == NULL) exit(0);
	*head = NULL;
}

5.插入
（1）位置插

int InsertLinkList_Pos(LinkList *head,ElemType val,int pos)     //位置插
{
	if(head == NULL)  exit(0);
	if(pos<0||pos>GetLinkList_Length(*head))  return false;
	if(pos == 0)
	{
		if(InsertLinkList_Head(head,val))  return true;
	}
	LinkList p = FindPrior(*head,pos);
	LinkList q = ApplyNode(val,p->next);
	p->next = q;
	return true;
}

（2）头插

int InsertLinkList_Head(LinkList *head,ElemType val)        //头插
{
	assert(head!=NULL);
	if(head == NULL)  exit(0);
	LinkList q = ApplyNode(val,*head);
	*head = q;
	return true;
}

（3）尾插

int InsertLinkList_Tail(LinkList *head,ElemType val)        //尾插
{
	if(head == NULL)  exit(0);
	return InsertLinkList_Pos(head,val,GetLinkList_Length(*head));
}

6.删除
（1）位置删

int DeletLinkList_Pos(LinkList *head,int pos)        //位置删
{
	if(head == NULL)  exit(0);
	if(pos<0||pos>=GetLinkList_Length(*head))  return false;
	if(pos == 0)
	{
		return DeletLinkList_Head(head);
	}
	LinkList p = FindPrior(*head,pos);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	return true;
}

（2）头删

int DeletLinkList_Head(LinkList *head)        //头删
{
	if(head == NULL||*head == NULL)  return false;
	LinkList p = *head;
	*head = p->next;
	free(p);
	return true;
}

（3）尾删

int DeletLinkList_Tail(LinkList *head)       //尾删
{
	if(head == NULL)  exit(0);
	return DeletLinkList_Pos(head,GetLinkList_Length(*head)-1);
}

7.打印

void Show_LinkList(LinkList head)        //打印
{
	if(head == NULL)  return ;
	LinkList p = head;
	while(p!=NULL)
	{
		printf("%d  ",p->data);
		p = p->next;
	}
	printf("\n");
}

8.清空单链表

int Clear_LinkList(LinkList *head)       //清空
{
	if(head == NULL)  return true;
	while(*head != NULL)
	{
		DeletLinkList_Head(head);
	}
	return true;
}

9.销毁单链表

int Destroy_LinkList(LinkList *head)          //销毁
{
	if(head == NULL)  return false;
	return Clear_LinkList(head);
}

总代码：

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

typedef int ElemType;

typedef struct LNode
{
	ElemType  data;
	LNode *next;
}LNode,*LinkList;

static int GetLinkList_Length(LinkList head)       //计算结点数
{
	LinkList p = head;
	int length = 0;
	while(p!=NULL)
	{
		length++;
		p = p->next;
	}
	return length;
}

static LinkList ApplyNode(ElemType val,LinkList next)     //创建节点及赋值
{
	LinkList p = (LinkList)malloc(sizeof(LNode));
	if(p == NULL)  return NULL;
	p->data = val;
	p->next = next;
	return p;
}

static LinkList FindPrior(LinkList head,int pos)       //找目标结点的前一个
{
	LinkList p = head;
	while(pos-1)
	{
		p = p->next;
		pos--;
	}
	return p;
}

void Init_LinkList(LinkList *head)           //初始化
{
	if(head == NULL) exit(0);
	*head = NULL;
}

int InsertLinkList_Head(LinkList *head,ElemType val)        //头插
{
	assert(head!=NULL);
	if(head == NULL)  exit(0);
	LinkList q = ApplyNode(val,*head);
	*head = q;
	return true;
}

int InsertLinkList_Pos(LinkList *head,ElemType val,int pos)     //位置插
{
	if(head == NULL)  exit(0);
	if(pos<0||pos>GetLinkList_Length(*head))  return false;
	if(pos == 0)
	{
		if(InsertLinkList_Head(head,val))  return true;
	}
	LinkList p = FindPrior(*head,pos);
	LinkList q = ApplyNode(val,p->next);
	p->next = q;
	return true;
}

int InsertLinkList_Tail(LinkList *head,ElemType val)        //尾插
{
	if(head == NULL)  exit(0);
	return InsertLinkList_Pos(head,val,GetLinkList_Length(*head));
}


int DeletLinkList_Head(LinkList *head)        //头删
{
	if(head == NULL||*head == NULL)  return false;
	LinkList p = *head;
	*head = p->next;
	free(p);
	return true;
}

int DeletLinkList_Pos(LinkList *head,int pos)        //位置删
{
	if(head == NULL)  exit(0);
	if(pos<0||pos>=GetLinkList_Length(*head))  return false;
	if(pos == 0)
	{
		return DeletLinkList_Head(head);
	}
	LinkList p = FindPrior(*head,pos);
	LinkList q = p->next;
	p->next = q->next;
	free(q);
	return true;
}

int DeletLinkList_Tail(LinkList *head)       //尾删
{
	if(head == NULL)  exit(0);
	return DeletLinkList_Pos(head,GetLinkList_Length(*head)-1);
}

int Clear_LinkList(LinkList *head)       //清空
{
	if(head == NULL)  return true;
	while(*head != NULL)
	{
		DeletLinkList_Head(head);
	}
	return true;
}

int Destroy_LinkList(LinkList *head)          //销毁
{
	if(head == NULL)  return false;
	return Clear_LinkList(head);
}

void Show_LinkList(LinkList head)        //打印
{
	if(head == NULL)  return ;
	LinkList p = head;
	while(p!=NULL)
	{
		printf("%d  ",p->data);
		p = p->next;
	}
	printf("\n");
}

int main()
{
	//以下为测试内容
	LinkList list;
	Init_LinkList(&list);
	for(int i=0;i<10;i++)
	{
		InsertLinkList_Head(&list,i);
	}
	InsertLinkList_Pos(&list,200,0);
	InsertLinkList_Tail(&list,100);
	Show_LinkList(list);

	DeletLinkList_Head(&list);
	DeletLinkList_Tail(&list);
	DeletLinkList_Pos(&list,9);
	Show_LinkList(list);

	//Clear_LinkList(&list);
	Destroy_LinkList(&list);
	Show_LinkList(list);
	return 0;
}