数据结构-单链表

#include <stdio.h>
#include <stdlib.h>
//设计节点结构
typedef struct Node
{
	int data;
	struct Node *pNext;
}NODE, *pNODE;
//创建单向链表
pNODE create_Linklist(void);
//打印单向链表
void show_Linklistshow_Linklist(pNODE pHead);
//判断单向链表是否为空
int isEmpty_Linklist(pNODE pHead);
//计算单向链表的长度
int getLength_Linklist(pNODE pHead);
//向单向链表插入节点
int insert_Linklist(pNODE pHead, int pos, int data);
//从单向链表删除节点
int delete_Linklist(pNODE pHead, int pos);
//删除整个链表，释放内存
void free_Linklist(pNODE *ppHead);
//创建单向链表
pNODE create_Linklist(void)
{
	int i, length, data;
	pNODE p_new = NULL, pTail = NULL;
	//创建头节点，头结点是第0个节点，后面的节点从1开始计数
	pNODE pHead = (pNODE)malloc(sizeof(NODE));
	if (NULL == pHead)
	{
		printf("内存分配失败！\n");
		exit(EXIT_FAILURE);
	}
	pHead->data = 0;
	pHead->pNext = NULL;
	pTail = pHead;
	printf("请输入要创建链表的长度：");
	scanf("%d", &length);
	for (i=0; i<length; i++)
	{
		p_new = (pNODE)malloc(sizeof(NODE));
		if (NULL == p_new)
		{
			printf("内存分配失败！\n");
			exit(EXIT_FAILURE);
		}
		printf("请输入第%d个节点的值：", i+1);
		scanf("%d", &data);
		p_new->data = data;
		p_new->pNext = NULL;
		pTail->pNext = p_new;
		pTail = p_new;
	}
	return pHead;
}
//打印单向链表，不打印头结点的值。
void show_Linklist(pNODE pHead)
{
	pNODE pt = pHead->pNext;
	printf("打印链表：");
	while (pt)
	{
		printf("%d ", pt->data);
		pt = pt->pNext;
	}
	putchar('\n');
}
//判断链表是否为空
int isEmpty_Linklist(pNODE pHead)
{
	if (pHead->pNext == NULL)
		return 1;
	else
		return 0;
}
//计算单向链表长度
int getLength_Linklist(pNODE pHead)
{
    int length = 0;
    pNODE pt = pHead->pNext;
    while (pt)
    {
        length++;
        pt = pt->pNext;
    }
    return length;
}
//向单向链表插入一个节点,位置从1开始，到链表长度加1结束。
int insert_Linklist(pNODE pHead, int pos, int data)
{
	pNODE pt = NULL, p_new = NULL;
	if (pos > 0 && pos < getLength_Linklist(pHead) + 2)
	{
		p_new = (pNODE)malloc(sizeof(NODE));
		if (NULL == p_new)
		{
			printf("内存分配失败！\n");
			exit(EXIT_FAILURE);
		}
		p_new->data = data;
		while (1)
		{
			pos--;
			if (0 == pos)
				break;
			pHead  = pHead->pNext;
		}
		pt = pHead->pNext;
		pHead->pNext = p_new;
		p_new->pNext = pt;
		return 1;
	}
	else
		return 0;
}
//从单向链表中删除一个节点，位置从1开始，到链表长度结束。
int delete_Linklist(pNODE pHead, int pos)
{
	pNODE pt = NULL;
	if (pos > 0 && pos < getLength_Linklist(pHead) + 1)
	{
		while (1)
		{
			pos--;
			if (0 == pos)
				break;
			pHead = pHead->pNext;
		}
		pt = pHead->pNext->pNext;
		free(pHead->pNext);
		pHead->pNext = pt;
		return 1;
	}
	else
		return 0;
}
//删除整个单向链表，释放内存。
void free_Linklist(pNODE *ppHead)
{
    pNODE pt = NULL;
    while (*ppHead != NULL)
    {
        pt = (*ppHead)->pNext;
        free(*ppHead);
        *ppHead = pt;
    }
}
int main(void)
{
	int flag = 0, length = 0;
	int position = 0, value = 0;
	pNODE head = NULL;
	head = create_Linklist();
	flag = isEmpty_Linklist(head);
	if (flag)
		printf("单向链表为空！\n");
	else
	{
		length = getLength_Linklist(head);
		printf("单向链表的长度为：%d\n", length);
		show_Linklist(head);
	}
	printf("请输入要插入节点的位置和元素值(两个数用空格隔开)：");
	scanf("%d %d", &position, &value);
	flag = insert_Linklist(head, position, value);
	if (flag)
	{
		printf("插入节点成功！\n");
		show_Linklist(head);
	}
	else
		printf("插入节点失败！\n");
	flag = isEmpty_Linklist(head);
	if (flag)
		printf("单向链表为空，不能进行删除操作！\n");
	else
	{
		printf("请输入要删除节点的位置：");
		scanf("%d", &position);
		flag = delete_Linklist(head, position);
		if (flag)
		{
			printf("删除节点成功！\n");
			show_Linklist(head);
		}
		else
			printf("删除节点失败！\n");
	}
	free_Linklist(&head);
	if (NULL == head)
		printf("已成功删除单向链表，释放内存完成！\n");
	else
		printf("删除单向链表失败，释放内存未完成！\n");
	return 0;
}