link.c

关于链表的数据类型定义和基本运算：新建链表

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

struct Link
{	int data;
	struct Link *next;
};
struct Link *head;			/*建立一个指向链表头的全局变量*/

struct Link *CreateNode(int nodeNumbers);
struct Link *InsertNode(struct Link *head, int tData );
void DispLink(struct Link *head);
struct Link *DelNode(struct Link *head, long num);
void DeleteMemory(struct Link *head);

void main()
{	int i=0;
	struct Link *pr;
	char c;
	head = NULL;/*开始时是空链表*/
	while(1)/*循环实现建立链表*/
	{	printf("\nPlease press 'y' to insert one new node,press 'n' to finish:");
		c = getchar();
		/* 如果键入既不是' y '，又不是'n'则循环继续进行 */
		if ((c!='y'||c!='Y')&&(c!='n'||c!='N'))
		{   
			puts("you must input 'y' or 'n'");
			continue;		
		}
		if ((c=='n'||c=='N'))
			break;		/* 如果键入的是'n'循环退出 */
	    if (i==0)/* 如果是第一个节点,将新节点链至头节点后*/
	    {   head=CreateNode(i); 
			pr = head;//使用pr跟踪当前节点的前一个节点
		}
		else/* 不是第一个节点，将新建节点接到链表的结尾pr处 */
		{	pr->next = CreateNode(i);  
			pr = pr->next;//使用pr跟踪当前节点的前一个节点
		}
	    	i++;
	}
	DispLink(head);
	DeleteMemory(head);
}

/*  函数功能：建立一个新的节点，并为该节点赋初值
	函数的参数：整型变量nodeNumbers，表示建立的节点个数
	函数的返回值：为指向该节点的指针
*/
struct Link *CreateNode(int nodeNumbers)
{
	struct Link *p;
/* 动态申请一段内存 */
	p = (struct Link *)malloc(sizeof(struct Link));  
	if(p == NULL)          /* 如果返回空指针，申请失败，打印错误信息，退出程序 */
	{	printf("No enough memory to alloc");
		exit(0);						/*结束程序运行*/
	}
    /*为新建节点赋值*/
	p->next = NULL;					  	/* 新建的节点指针域赋空指针 */
	p->data = nodeNumbers * 10;	       	/* 为新建的节点数据区赋值 */
    /*返回指向新建节点的指针*/
	printf("\nCreate a new node!");
	return p;       
}

/*	函数功能：在链表中插入一个节点
 	函数参数：结构体指针变量head，表示指向链表头指针
			整型变量tData，表示插入的节点的数据区的内容
 	返回参数：指向链表头指针
*/
struct Link *InsertNode(struct Link *head, int tData )
{
	struct Link *pr,*p;

	/* 申请一段内存，建立一个新的节点*/
	p = (struct Link *)malloc(sizeof(struct Link));	
	if (p == NULL)    			/*如果申请失败，则退出程序 */
	{	printf("Can`t enough memory to alloc");
		exit(0);			   								 
	}
	pr = head;
    /*为新节点赋值*/
	p->next = NULL;			  	/* 新的节点的指针域赋为空地值 */
	p->data = tData*10;			/* 新的节点数据区域赋值 */
	/*插入相应位置*/
if (head == NULL) /* 如果链表原为空的，新节点作为头节点 */
	{	head = p;
  	}
	else 
	{	/* 找要插入的位置，pr指向插入位置的前一个节点。
设链表已经按由小到大排完序*/
		while (pr->data < tData*10 && pr->next != NULL)
       	{	pr = pr->next;	 
		}
		/*插入到头节点的后边*/
if (pr == head)       		/*如果是在第一个节点前插入新节点*/
		{
			p->next = head;
			head = p;
			return head;		   	/* 返回头节点指针 */
		}
		/*插入到链表尾部，pr指向尾部*/
if (pr->next == NULL)	   	/*如果是在表尾插入新节点*/
		{
			pr->next = p;		               
		}
	/*插入到链表中间pr节点的后边*/
else              			/*如果是在链表中间插入新节点*/
		{
			p->next = pr->next;		/* 插入到链表中间位置 */
			pr->next = p;
		}
	}
	return head;					/* 返回头节点指针 */
}








/* 	函数的功能：显示所有已经建立好的节点的节点号，和该节点中数据项内容
	函数的参数：结构体指针变量head，表示指向链表的头指针
	函数的返回值：无
*/
void DispLink(struct Link *head)
{	struct Link *p;
	int j=1;
	p = head;
	do{
		printf("\n%5d%10d\n",j,p->data);
		p = p->next;
		j++;
	}while(p!=NULL);
}

/*	函数功能：从head指向的链表中删除第一个含有数据成员num的节点
 	输入参数：结构体指针变量head，表示指向链表头指针
    		     长整型变量num，表示要查找的节点中包含的数据成员的数值
 	返回参数：指向链表头指针
*/
struct Link *DelNode(struct Link *head, long num)
{
	struct Link *p,*pr;
	if (head == NULL)
	{
		printf("\nNo Linked Table");/* 如果head为空，意味着没有链表存在 */
		return(head);
	}
	p = head;
    /*如果没找到数据为num的节点，且链表还没有结束，则继续移动节点，
	  直到找到或者到链表的结尾为止*/	
	while (num != p -> data && p -> next != NULL) 		
	{				            		
		pr = p;
		p = p->next;
	}/*找到后pr指向要删除节点的前一个节点，p指向要删除的节点*/
	/*找到，则删除*/
if (num == p->data)           /* 发现了节点，准备删除 */
	{				     		
		if (p == head)   /*如果发现的是第一个节点，将第二个节点的地址赋予head */
			head = p -> next;  			
		
		else   /*如果发现的是中间节点，则将上个节点的指针指向本节点的下一个节点*/
			pr -> next = p->next;	  									  		
		free(p);			/*删除节点后应将其动态分配的内存释放掉*/
		printf("delete the node");
	}
	else 
    {/*没找到给出提示*/
		printf("\nNot found the Node");
    }
	return head;
}

void DeleteMemory(struct Link *head)
{
	struct Link *p = head, *pr = NULL;

	while (p != NULL)           	/*若不是表尾，则释放节点占用的内存*/
	{	
		pr = p;                  	/*在pr中保存当前节点的指针*/
		p = p->next;            	/*让p指向下一个节点*/
		free(pr);                	/*释放pr指向的当前节点占用的内存*/
	}            
}