单向链表

#include "stdafx.h"
#include <malloc.h>
#include <stdlib.h>


typedef struct Node
{
	int data;				//数据存储
	struct Node * pNext;	//链表的指针，指向下一个节点
}NODE,* PNODE;				//NODE 等价于struct Node PNODE等价于struct Node*

PNODE create_list(void);//创建一个链表元素
void traverse_list(PNODE);//对链表的元素便利输出
bool is_empty(PNODE pHead);//判断链表是否为空
int  length_list(PNODE pHead);//求链表的长度
void sort_list(PNODE pHead);//对链表的数据进行排序
bool insert_list(PNODE pHead,int pos, int value);//链表在pos位置添加一个节点元素
bool delete_list(PNODE pHead,int pos, int* pValue);//链表中删除pos位置的节点

int main(void) 
{
	PNODE pHead = NULL;
	pHead = create_list();
	traverse_list(pHead);

	//sort_list(pHead);
	//traverse_list(pHead);

	insert_list(pHead,4,44);
	traverse_list(pHead);
	int v;
	delete_list(pHead,1,&v);
	traverse_list(pHead);


	/*int length = length_list(pHead);
	printf("链表的长度是：%d\n",length);
	*/


	/*
	if(is_empty(pHead)) 
	{
		printf("链表不为空！\n");
	}
	else
	{
		printf("链表为空！\n");
	}
	*/

	return 0;
}

PNODE create_list(void)
{
	int len;		//有效节点个数
	int i;
	int val;		//节点的值

	PNODE pHead = (PNODE) malloc(sizeof(NODE));
	if(pHead==NULL) 
	{
		printf("程序分配节点失败，终止运行\n");
		exit(-1);
	}
	PNODE pTail = pHead;
	pTail ->pNext = NULL;

	printf("请输入您要生成链表节点的个数： len = ");
	scanf("%d",&len);

	for(i=0;i<len;++i) 
	{
		printf("请输入第%d节点的值：val = ",i+1);
		scanf("%d",&val);
		PNODE pNew = (PNODE) malloc(sizeof(NODE));
		if(pNew==NULL) 
		{
			printf("程序分配节点失败，终止运行\n");
			exit(-1);
		}
		pNew ->data = val;
		pNew ->pNext = NULL;
		pTail ->pNext = pNew;
		pTail = pNew;
	}
	return pHead;
}

void traverse_list(PNODE pHead)
{
	PNODE p = pHead ->pNext;
	while(NULL!= p) 
	{
		printf("%d " , p->data);
		p = p->pNext;
	}
	printf("\n");
	return ;
}

bool is_empty(PNODE pHead)
{
	if(NULL != pHead->pNext) 
	{
		return true;	
	}
	else
	{
		return false;
	}
}


int  length_list(PNODE pHead)
{
	PNODE p = pHead ->pNext;
	int length = 0;
	while(NULL!= p) 
	{
		++length;
		p = p->pNext;
	}
	return length;
}

void sort_list(PNODE pHead)
{
	int i, j, temp;
	int length = length_list(pHead);

	PNODE p,q;
	for(i=0,p=pHead->pNext; i<length-1; p=p->pNext,i++) 
	{
		for(j=i+1,q=p->pNext;j<length;j++,q=q->pNext)
		{
			if(p->data > q->data) 
			{
				temp = p->data;
				p->data = q->data;
				q->data = temp;
			}
		}
	}
	return ;

}

bool insert_list(PNODE pHead,int pos, int value)
{
	int i =0;
	PNODE p = pHead;
	while(NULL!=p && i<pos-1)
	{
		p = p->pNext;
		++i;	
	}

	if(NULL ==p || i>pos-1)
	{
		return false;
	}

	PNODE pNew = (PNODE) malloc(sizeof(NODE));
	if(pNew==NULL) 
	{
		printf("程序分配节点失败，终止运行\n");
		exit(-1);
	}
	pNew ->data = value;
	PNODE q = p->pNext;
	p->pNext = pNew;
	pNew->pNext = q;
	return true;

}

bool delete_list(PNODE pHead,int pos, int* pValue)
{
	int i =0;
	PNODE p = pHead;
	while(NULL!=p->pNext && i<pos-1)
	{
		p = p->pNext;
		++i;	
	}

	if(NULL ==p->pNext || i>pos-1)
	{
		return false;
	}

	PNODE q = p->pNext;
	*pValue = q->data;
	p->pNext = p->pNext->pNext;
	free(q);
	q = NULL;
}

 

   刚开始学习数据结构，记录一下自己不熟练的C，写的链表单向链表功能，记录一下，以后可以复习