链表.cpp

链表:经典插入方法,指向指针的指针的运用,Unix下面大量使用。

# include <stdio.h>
# include <stdlib.h>
# include <conio.h>
typedef struct node
{
	int data;
	struct node *link;
} LIST,*LINK;
# define SIZE sizeof(LIST)

/*************Creat the list**************/
/*用此方法创建链表元素都将有序*/
LINK creat()
{
	LINK p1=NULL,p2=NULL;
	LINK head=NULL;
	LINK *pprev;
	p1=(LINK)malloc(SIZE);
	printf("please input the number for the data:\n");
	scanf("%d",&p1->data);
	while(p1->data!=0)
	{
		for(pprev=&head;(p2=*pprev)&& p2->data<p1->data;pprev=&p2->link);
			//插入核心，边创建边插入
		if(p2->data==p1->data)
			{
			p2->data=p2->data+p1->data;
			free(p1);
			}
		else
			{
				p1->link=*pprev;
				*pprev=p1;
			}

	p1=(LINK)malloc(SIZE);
	printf("please input the number for the data:\n");
	scanf("%d",&p1->data);
	}
	free(p1);
	return head;
}
/************ typical insert ***********/
/*经典插入方法*/
LINK insert(LINK head ,LINK p1)
{
	LINK p2=NULL;
	LINK *pprev;
	for(pprev=&head;(p2=*pprev)&& p2->data<p1->data;pprev=&p2->link);
		//插入核心语句
	if(p2->data==p1->data)
		p2->data=p2->data+p1->data;
	else
		{
		p1->link=*pprev;
		*pprev=p1;
		}
	return head;
}
/************Print the result**************/
void print(LINK head)
{
	LINK p1=head;
	if(p1==NULL)
		printf("the list is null.\n");
	else
		{
			printf("Now start printting the list.....\n");
			while(p1!=NULL)
			{
				printf("%d  ",p1->data);
				p1=p1->link;
			}
		}
}

void main()
{
	LINK head=NULL;
	LINK p=NULL;
	clrscr();
	head=creat();
	print(head);
    printf("\n");
	p=(LINK)malloc(SIZE);
	printf("please input the number for the data:\n");
	scanf("%d",&p->data);
    head=insert(head,p);
	print(head);
}