数据结构与算法C语言版---链表

由于编者水平有限,如有错误,请多多包涵。

/*
	File name: LinkendList.cpp
	Description: 有头链表的创建，遍历，查找，删除，添加，排序。
	Author: Yang_Jiang
	Date: 2018年10月10日
	Compiler：Visual Studio 2008
*/

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

typedef struct Student
{
	int id; // 数据域
	struct Student* pNext;  //指针域
}NODE,*PNODE; 

//NODE 等价于 struct Student
//PNODE 等价于 struct Student*


//函数声明
PNODE create_list(int ); //创建链表  PNODE返回该链表头结点
void traverse_list(PNODE ); // 遍历该链表
bool find_list(PNODE , int); //查找该链表中数据 true：找到数据 false：链表为空或未找到数据
int length_list(PNODE ); //判断该链表长度
bool delete_list(PNODE , int); //删除该链表中的数据 true:删除成功 false：链表为空或删除失败
bool empty_list(PNODE ); //判断链表是否为空   true：空 false：非空
void insert_list(PNODE , int val ); //插入节点 根据id大小 如果链表为空默认插在头结点后面，否则按从小到大顺序插入
void sort_list(PNODE);//对链表进行排序 --- 冒泡排序法

int main()
{

	PNODE pHead = create_list(30); //创建链表 长度为0（只有头结点）
	sort_list(pHead);
	traverse_list(pHead);

	//find_list(pHead,31); //查找 true 数据存在 false 链表为空或数据不存在
	
	//delete_list(pHead,1); //删除 true 删除成功 false 链表为空或数据不存在
	
	//insert_list(pHead,0); //没有数据的时候默认插入在头结点后面
	//insert_list(pHead,0);
	//insert_list(pHead,2);
	//insert_list(pHead,1);
	
	//traverse_list(pHead);  //遍历

	return 0;
}


//创建链表
PNODE create_list(int len)
{
	PNODE pHead = (PNODE) malloc(sizeof(NODE));
	if(NULL == pHead)
	{
		exit(-1); //动态内存分配失败，程序终止！
	}
	
	PNODE head = pHead;
	head->pNext = NULL;

	for(int i=0; i<len; i++)
	{
		PNODE pNew = (PNODE) malloc(sizeof(NODE));
		if(NULL == pNew)
		{
			exit(-1); //动态内存分配失败，程序终止！
		}
		
		pNew->id = i + 1;
		head->pNext = pNew;
		pNew->pNext = NULL;
		
		head = pNew; //直接指向最后一个节点 ，每一次循环直接挂到最后一个节点后边。

		/*
			挂载到节点后面：
			
			如果实在理解不了head = pNew; 那么直接做一个循环，每次遍历到最后个节点挂载上去
			数据量多的话，效率会下降。

			while( head->pNext != NULL )
			{
				head = head->pNext; //遍历到最后一个节点
			}
			pNew->id = i + 1;
			head->pNext = pNew; //挂载到最后一个节点后面
		    
			result : 1,2,3,4,5,6,7.....29,30
		*/
		
		/*
			挂载到节点前面：
			
			pNew->id = i + 1;
			pNew->next = head->next; // 把头节点的第一个有效的数据 挂载到新来的节点后边
			head->next = pNew; //把挂载好的数据 挂在头节点的后边
			
			result : 30,29,28,27,26,25......2,1
		*/


	}

	return pHead;
}

//判断链表是否为空
bool empty_list(PNODE pHead)
{
	if(pHead->pNext == NULL)
	{
		return true; //为空
	}
	
	return false; //不为空
}

//求链表长度
int length_list(PNODE pHead)
{
	if( empty_list(pHead) ) //链表为空
	{
		return 0; 
	}
	else
	{	
		int count = 0; //计数
		PNODE head = pHead->pNext;
		
		while( head != NULL)
		{
			count ++;
			head = head->pNext;
		}
		return count;
	}
}


//遍历链表
void traverse_list(PNODE pHead)
{
	PNODE head = pHead->pNext; //头结点不包含有效数据，首节点才包含有效数据
	
	if( empty_list(pHead) ) //判断链表是否为空
	{
		printf("空链表\n");
	}
	else
	{
		while( head != NULL ) //只要不为空
		{
			printf("%d\t", head->id);
			head = head->pNext; //指向下一个元素
		}

	}
}

//查找数据
bool find_list(PNODE pHead, int val)
{
	if( empty_list(pHead) ) //链表为空 
	{
		return false;
	}
	else
	{
		PNODE head = pHead->pNext;

		while( head != NULL )
		{
			if(head->id == val )
			{
				printf("该数据存在%d\n" , val);
				return true;
			}
			head = head->pNext;
		}

		return false; //如果遍历完了还没找到该数据

	}
	
}

//删除数据
bool delete_list(PNODE pHead, int val)
{
	if( empty_list(pHead) )
	{
		return false; //链表为空 无法删除
	}
	else
	{
		PNODE pre = pHead; // 前一个节点
		PNODE cur = pHead->pNext; //当前节点
		
		while( cur != NULL)
		{
			if(cur->id == val)
			{
				pre->pNext = cur->pNext; //等价于 pre->pNext = pre->pNext->pNext		
				printf("删除成功,您删除的数据是%d\n" ,cur->id);
				free(cur); //必须得释放，否则会造成内存泄漏。
				cur = NULL;
				
				return true; //删除成功
			}
			pre = cur; 
			cur = cur->pNext;
		}
	
		return false; //没找到数据 删除失败
	}
}

void insert_list(PNODE pHead, int val)
{
	
	PNODE pre = pHead;     //前一个节点
	PNODE cur = pHead->pNext; //当前节点

	if( empty_list(pHead) ) //如果链表为空
	{
		printf("该链表为空，数据直接插入在首节点\n");
		
		PNODE pNew = (PNODE) malloc(sizeof(NODE));
		if(NULL == pNew)
		{
			exit(-1);
		}
		pNew->id = val;
		pNew->pNext = NULL;
		
		pHead->pNext = pNew; //如果链表为空直接挂在有效节点后面 cur 等价于 pHead->next;
	}
	else
	{
		while( cur != NULL)
		{
			if(cur->id > val) //如果当前的值小于 用户传进来的值 
			{
				break;  //表示找到要插入的位置 直接终止循环
			}
			pre = cur;
			cur = cur->pNext;
		}
		
		PNODE pNew = (PNODE) malloc(sizeof(NODE));
		if(NULL == pNew)
		{
			exit(-1); //动态内存分配失败,程序终止！
		}
		pNew->id = val;
		pNew->pNext = NULL;
		
		
		pNew->pNext = cur;// cur 等价于 pHead->next(当前节点); 
		pre->pNext = pNew;// pre 等价于 pHead(上一个节点);
		printf("插入成功！\n");
	}
	
}

void sort_list(PNODE pHead)
{
	int len = length_list(pHead); //求出链表长度
	
	int i,j,t;
	
	PNODE p;
	PNODE q;

	for(i=0,p=pHead->pNext; i<len-1; i++,p=p->pNext )
	{	
		//或 for(j=0,q=p->pNext; j<len-1-i; j++,q=q->pNext)
		for(j=i+1,q=p->pNext; j<len; j++, q=q->pNext)
		{
			if(p->id < q->id) // 类似于 i > j
			{
				t = p->id; // 类似于 t = i;
				p->id = q->id; //类似于 i = j;
				q->id = t; //类似于 j = t;
			}
		
		}
		
	}

}



/*
	总结
		注释已经写的足够详细。
		本程序在Visual Studio 2008编译通过，文件是.cpp文件，代码的写法有点不规范，既有C语言
		语法也包含了C++语法
*/