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

3/8/2017来源:ASP.NET技巧人气:1787

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

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

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 );


#endif
test.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  */					//版本2
void 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;
	}
}