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

不带头结点的单链表是线性表的一种链式存储形式，首先来设计它的结构：

typedef int ElemType;
typedef struct Node
{
	ElemType data;
	struct Node* next;
}LNode,*pLinkList;

首先对于单链表进行判空操作：

static void DeterPointNull(pLinkList* list)
{
	assert(list != NULL);
	if (list == NULL)
	{
		printf("list is null,please check!");
		exit(0);
	}
}

当我们要对单链表进行插入节点操作时会出现空间不够的现象，因此我们需要有申请新结点的操作：

static pLinkList ApplyNode(ElemType val, pLinkList point)
{
	pLinkList p = (pLinkList)malloc(sizeof(LNode));
	assert(p != NULL);
	p->data = val;
	p->next = point;
	return p;
}

对单链表进行初始化：

void InitLinkList(pLinkList* list)
{
	DeterPointNull(list);
	*list = NULL;
}

对单链表进行头插：

int InsertHead(pLinkList* list, ElemType val)
{
	DeterPointNull(list);
	*list = ApplyNode(val, *list); 
}

计算单链表的长度：

int GetLength(pLinkList* list)
{
	DeterPointNull(list);
	pLinkList p = *list;
	int len = 0;
	while (p)
	{
		len++;
		p = p->next;
	}
	return len;
}

按位置插入一个结点：

int InsertPos(pLinkList* list, ElemType val, int pos)
{
	DeterPointNull(list);
	if (pos<0 || pos>GetLength(list))
	{
		printf("pos is error,please check!");
		return 0;
	}
	if (pos == 0)
	{
		return InsertHead(list, val);
	}

	pLinkList p = *list;
	while (pos > 1)//找要插入的位置
	{
		p = p->next;
		pos--;
	}
	p->next = ApplyNode(val, p->next);
	return 1;

}

尾插：

int InsertTail(pLinkList* list, ElemType val)
{
	DeterPointNull(list);
	return InsertPos(list, val, GetLength(list));
}

对单链表进行头删：

int DeleteHead(pLinkList* list)
{
	DeterPointNull(list);
	if (*list == NULL)
	{
		printf("list is null,delete fail\n");
		return 0;
	}
	pLinkList p = *list;
	*list = p->next;
	free(p);
	return 1;
}

按位置删除：

int DeletePos(pLinkList* list, int pos)
{
	DeterPointNull(list);
	if (pos < 0 || pos >= GetLength(list))
	{
		printf("pos is error\n");
		return 0;
	}
	if (pos == 0)
	{
		return DeleteHead(list);
	}
	pLinkList p = *list;
	while (pos > 1)
	{
		p = p->next;
		pos--;
	}
	pLinkList q = p->next;
	p->next = q->next;
	return 1;

}

尾删：

int DeleteTail(pLinkList* list)
{
	return DeletePos(list, GetLength(list) - 1);
}

销毁单链表：

void Destroy(pLinkList* list)
{
	DeterPointNull(list);
	pLinkList p = *list;
//	p = p->next;
	while (p)
	{
		DeleteHead(list);
	}
}