c语言实现单链表数据结构及其基本操作

 带头结点单链表。分三个文件，分别为头文件，测试文件，源代码文件。

给出了单链表的部分操作，每个操作都有对应的注释说明该函数功能。

test.c  文件中，对输入数据是否合法进行了检测，但是并未实现输入数据不合法时应该采取的措施。

测试文件  通过一个菜单来测试单链表功能。

list.h:

/*  单链表类型的头文件  */  #ifndef LIST_H_#define LIST_H_ struct Node;									//先声明，就可以在下面使用，而不必因定义在后面而产生冲突 /*  一般类型定义  */  typedef int ElementType;                        //抽象数据类型  typedef struct Node * PtrToNode;typedef PtrToNode List;typedef PtrToNode Position;/*  特定于程序的声明  */   struct Node {    ElementType element;  	Position	next;};/*  函数原型  */  List MakeEmpty ( List l );int IsEmpty ( List L );int IsLast ( Position p, List l );Position Find ( ElementType x, List l );void Delete ( ElementType x, List l );Position FindPRevious ( ElementType x, List l );void Insert ( ElementType x, List l, Position p );void DeleteList ( List l );Position Header ( List l );Position First ( List l );Position Last ( List l );Position Advance ( Position p );ElementType Retrieve ( Position p );void PushFront ( ElementType x, List l );void PopFront ( List l );void PushBack ( ElementType x, List l );void PopBack ( List l );#endiftest.c:
/*  单链表  */  #include <stdio.h>  #include <windows.h>  #include "list.h"struct Node;void Menu ( void );								//菜单  void PrintList ( List l );						//打印单链表int main ( void )  {      List l;	int choice;  	ElementType x;  	l = NULL;	choice = 0;	x = 0;      Menu (  );      scanf ( "%d", &choice );        while ( 0 != choice )      {          switch ( choice )          {          case 1: if ( NULL == ( l = MakeEmpty ( l ) ) )	//如若不接受返回值，则外面 l 未改变。因为 MakeEmpty 中形参 不影响 实参值，开辟的空间反而找不到了!重点!!				{				printf ( "初始化失败！/n" );				}				else				{					printf ( "初始化成功!/n" );				}                break;          case 2: if ( 1 == IsEmpty ( l ) )				{					printf ( "单链表为空!/n" );				}				else				{					printf ( "单链表不为空！/n" );				}                break;  		case 3: {					Position p;					p = Last ( l );					if ( NULL == p )					{						printf ( "0.链表中没有结点，当前位置是链表末尾!/n" );						break;					}					if ( 1 == IsLast ( p , l ) )					{						printf ( "1.当前位置是链表末尾！/n" );					}					if ( 0 == IsLast ( l, l ) )					{						printf ( "2.当前位置不是链表末尾！/n" );					}  				  break;  				}		case 4:	printf ( "请输入需要查找的元素: " );				if ( 1 == scanf ( "%d", &x ) )				{					Position tmp;					tmp = Find ( x ,l );					if ( NULL == tmp )					{						printf ( "元素%d不存在！/n", x );					}					else					{						printf ( "找到了元素%d！/n", ( Retrieve ( tmp ) ) );					}				}				else				{					printf ( "输入数据不合法，查找失败！/n" );				}				break;        case 5: printf ( "请输入需要删除的元素: " );				if ( 1 == scanf ( "%d", &x ) )				{					Delete ( x, l );					printf ( "删除成功！/n" );				}				else				{					printf ( "输入数据不合法，删除失败！/n" );				}				break;        case 6: printf ( "请输入需要插入的元素: " );//此处实现为头插				if ( 1 == scanf ( "%d", &x ) )				{					Insert ( x, l, l );					printf ( "插入成功！/n" );				}				else				{					printf ( "输入数据不合法，插入失败！/n" );				}                break;          case 7: DeleteList ( l );				printf ( "删除单链表成功！/n" );				l = NULL;				break;        case 8: printf ( "请输入需要插入的元素: " );				if ( 1 == scanf ( "%d", &x ) )				{					PushFront ( x, l );					printf ( "插入成功！/n" );				}				else				{					printf ( "输入数据不合法，插入失败！/n" );				}                break;          case 9: PopFront ( l );							printf ( "删除成功！/n" );                break;          case 10: printf ( "请输入需要插入的元素: " );				 if ( 1 == scanf ( "%d", &x ) )				 {					 PushBack ( x, l );				 	 printf ( "插入成功！/n" );				 }				 else				 {					 printf ( "输入数据不合法，插入失败！/n" );			 	 }                 break;          case 11: PopBack ( l );				 printf ( "删除成功！/n" );                 break;          case 12: PrintList ( l );				 break;        default: printf ( "放弃吧！/n" );                                       break;          }               Menu ( );          scanf ( "%d", &choice );      }        system ( "pause" );        return 0;    }      void Menu ( void )                              //菜单  {      printf ( "***************************************************************/n" );      printf ( "  1.初始化					2.是否为空/n" );      printf ( "  3.当前位置是否是链表末尾			4.查找元素/n" );      printf ( "  5.删除元素					6.插入元素/n" );      printf ( "  7.删除链表					8.头插数据/n" );      printf ( "  9.头删数据					10.尾插数据/n" );      printf ( "  11.尾删数据					12.打印/n" );      printf ( "***************************************************************/n" );  }    void PrintList ( List l )						//打印单链表{  	Position p;	p = l -> next;	while ( NULL != p )	{		printf ( "%d -> ", ( p -> element ) );		p = p -> next;	}	printf ( "/n" );}    
list.c:
/*  list.c  -- 支持单链表操作的函数  */  #include <stdio.h>  #include <stdlib.h>#include "list.h"  /*  接口函数  */  /*  把单链表初始化为空单链表  */				//必须先初始化再使用链表（未初始化链表下列函数可能出错.）List MakeEmpty ( List l )						//传进来的 l 是一个指向单链表这种数据结构的指针，但不一定已经开辟了这种结构的空间使指针去指向{	if ( NULL != l )							//结合 收藏夹 -> c语言,  理解为什么将指针free( )后需置NULL	{		DeleteList ( l );	}	l = ( List )malloc ( sizeof ( struct Node ) );//malloc 完一定要检查是否 开辟空间成功！	if ( NULL == l )	{		printf ( "开辟空间失败！" );		return NULL;	}	l -> element = 0;	l -> next = NULL;	return l;}/*  检查单链表是否为空  */  int IsEmpty ( List l )  {  	return ( NULL == l -> next );}   /*  检查当前位置是否是链表的末尾  */			//将只有头结点情况视为链表末尾int IsLast ( Position p, List l ){	return ( NULL == p -> next );}/*  在单链表中查找元素x  */Position Find ( ElementType x, List l ){	Position p;	p = l -> next;								//声明和定义分开.	while ( ( NULL != p ) && ( x != p -> element ) )	{		p = p -> next;	}	return p;}/*  在单链表中删除元素x  */						//元素不存在，函数不做任何处理void Delete ( ElementType x, List l )			//使用到了 FindPrevious( )函数{	Position p;	Position tmpCell;		p = FindPrevious ( x, l );	if ( !( IsLast ( p, l ) ) )	{		tmpCell = p -> next;		p -> next = p -> next -> next;			//注意!是赋值给p的next域,而不是p!			free ( tmpCell );						//free( )掉指针后,最好将指针置NULL.		tmpCell = NULL;	}}/*  在单链表中找出元素x的前驱位置  */			//辅助Find函数实现，不提供测试代码(若Find函数执行成功，则此函数正确)Position FindPrevious ( ElementType x, List l ){	Position p;	p = l;										//在外面申请头节点，所以l不可能为空	while ( ( NULL != p -> next ) && ( x != p -> next -> element ) )	{		p = p -> next;	}	return p;									//返回的不是next域！也永远不可能是!}/*  在单链表中插入元素x  *//*  插入到当前位置的后面  */void Insert ( ElementType x, List l, Position p ){	Position tmpCell;							//只是创建了一个指针，还需要malloc出结构体的大小.5.	tmpCell = ( List )malloc ( sizeof ( struct Node ) );//struct Node 只是一个类型， sizeof( sturct Node )才是它的大小. 才能使用malloc.	if ( NULL == tmpCell )						//因为系统资源问题，所以malloc申请空间可能会失败，养成malloc后检查申请是否成功的习惯6.	{		printf ( "申请空间失败" );	}	else	{	tmpCell -> element = x;	tmpCell -> next = p -> next;	p -> next = tmpCell;	}}/*  删除单链表  */void DeleteList ( List l )						//删除单链表后再使用单链表必须先初始化.{	Position p;	Position tmp;	p = l -> next;								//l 的next 域存放地址给p  free l 后，这个p所保存地址依然在和 l 无关。 lnext域只是之前用来保存它	free ( l );									//此处通过指针l释放l指向的头结点，而不是释放指针l，指针l依然存在.	l = NULL;									//记得，你在此处改变l的值，外面l值依旧没改变。   所以，这种错误不要再犯了！  	while ( NULL != p )	{		tmp = p -> next;			free ( p );								//此处释放的是p,不是p的next域（不要释放下一个节点）		p = tmp;	}}/*  返回链表头结点  */							//不提供测试用例Position Header ( List l ){	return l;}/*  返回链表第一个结点  */						//不提供测试用例Position First ( List l ){	return ( l -> next );}/*  返回链表的最后一个结点  */					//不提供测试用例Position Last ( List l ){	Position p = l;	if ( NULL == l -> next )					//将头节点后那个结点视为第一个结点，所以只有头结点时，视为没有结点.	{		return NULL;	}	else	{		while ( NULL != p -> next )		{			p = p -> next;		}	}	return p;}/*  返回位置p的下一个位置  */					//不提供测试用例Position Advance ( Position p ){	return ( p -> next ); }/*  返回位置p处的元素  */						//不提供测试用例ElementType Retrieve ( Position p ){	return ( p -> element );}/////*  在单链表头部插入元素x  */					//版本1//void PushFront ( ElementType x, List l )		//使用到了 Header( )函数 与 Insert( )函数//{//	Insert ( x, l, Header ( l ) );//}/*  在单链表头部插入元素x  */					//版本2void PushFront ( ElementType x, List l ){	Position tmp;								//不需要再定义一个多余的变量保存 l -> next.	tmp = ( List )malloc ( sizeof ( struct Node ) );	if ( NULL == tmp )	{		printf ( "申请空间失败，插入不成功！" );//抽象数据类型中别加多余东西( 换行符 ).	}	else	{		tmp -> element = x;		tmp -> next = l -> next;		l -> next = tmp;	}}/*  删除单链表第一个结点  */void PopFront ( List l )		{	if ( NULL == l -> next )	{		;	}	else	{		Position tmp;		tmp = l -> next;						//注意此处释放 l的next域中值才是释放了第一个结点，而不是释放第一个结点next域（第二个结点）.		l -> next = tmp -> next;				free ( tmp );							//释放的next域只是下一个结点，不是这个结点，也不是释放了next.		tmp = NULL;	}}/*  在单链表尾部插入元素x  */void PushBack ( ElementType x, List l )			//使用 Header( )函数{	Position p;	Position tmp;	p = Header ( l );	while ( NULL != p -> next )	{		p = p -> next;	}	tmp = ( List )malloc ( sizeof ( struct Node ) );	if ( NULL == tmp )	{		printf ( "申请空间失败，插入失败" );	}	else	{		tmp -> element = x;		tmp -> next = NULL;		p -> next = tmp;	}}/*  删除单链表最后一个结点  */void PopBack ( List l ){	if ( NULL == l -> next )	{		;	}	else	{		Position p;		p = l;		while ( NULL != p -> next -> next  )		{			p = p -> next;		}		free ( p -> next );		p -> next = NULL;	}}