mylist.cpp

包括链表的遍历

#include <stdlib.h> //包含malloc( )的头文件
#include <stdio.h>
#include <iostream.h>

struct node //链表节点的结构
{
	int num;
	struct node *next;
};

/******************************************/


void main ( )
{
	struct node *creat(node *head); //函数声明
	void print(node *head);
	void order(node *head);
	struct node *insert(node *head,int value);

	int newnode;
	char choice;
	struct node *head; //定义头指针

	head = NULL;
	head=creat(head);//创建单链表
	cout<<"do you want to insert(y)\(n)?";
	cin>>choice;
	while (choice=='y')
	{
		cout<<"input the number you want to insert:"<<endl;
		cin>>newnode;
		head=insert(head,newnode);
		cout<<"do you want to insert(y)\(n)";
		cin>>choice;
	}
	print(head);//打印单链表
}

struct node* creat(node *head)//函数返回的是与节点相同类型的指针
{
	struct node *p1,*p2;
	p1=p2=(struct node*)malloc(sizeof(struct node));//申请新节点
	printf("input head:\n");
	scanf("%d",&(p1->num));//输入节点的值
	p1->next=NULL;//将新节点的指针置为空
	printf("continue to input:");
	while(p1->num>0)//输入节点的数值大于0
	{
		if(head==NULL)
			head=p1;//空表，接入表头
		else
			
			p2->next=p1;//非空表，接到表尾
		p2=p1;
		p1=(struct node*)malloc(sizeof(struct node));//申请下一个新节点
		scanf("%d",&p1->num);//输入节点的值
		if (p1->num<=0)  //如果输入值《=0，那么将表尾指针指向空
			p2->next=NULL;
	}
	return head;//返回链表的头指针
}
/*******************************************/
void print(node *head)//输出以head为头的链表各节点的值
{
	struct node *temp;
	temp=head;	//取得链表的头指针
	if (head==NULL)
		cout<<"empty"<<endl;
	while(temp!=NULL)//只要是非空表
	{
		printf("%6d,%10d\n",temp->num,temp->next);	//输出链表节点的值
		temp=temp->next;	//跟踪链表增长
	}
} 
/*************************************************/
void order(node *head)
{
	node *p1,*p2;
	node *temphead;
	temphead = head;
	int temp;
	int count=1;
	if (temphead==NULL)
	{
		cout<<"it is empty!"<<endl;
		count=0;
	}
	else
	{
		p1=head;
		if (head->next==NULL)
		{
			count=1;
			cout<<head->num<<endl;
		}
		else
		{
			p2=head->next;
			while (p1->next!=NULL)
			{
				count++;
				if ((p1->num)<(p2->num))
				{
					temp=(p1->num);
					p1->num=p2->num;					
					p2->num=temp;
				}
				p1=p1->next;
				p2=p2->next;
			}
		}
	}
}

struct node *insert(node *head,int value)
{
	node *p1,*p2,*p3;
	p1=(struct node*)malloc(sizeof(struct node));
	p2=(struct node*)malloc(sizeof(struct node));
	p3=(struct node*)malloc(sizeof(struct node));
	p1->num = value;
	p2 = head;
	if (head==NULL)
	{
		head = p1;
		head->next = NULL;
	}
	else
	{
		while (value>(p2->num)&&(p2->next)!=NULL)//当value>当前的值指针的数据部分时，继续向后移
		{											//直到找到小于插入值的位置
			p3 = p2;
			p2=p2->next;
		}
		if (value<=(p2->num))//找到要插入的位置
		{
			if (p2==head)
			{
				head = p1;
				head->next =p2;
			}
			else
			{
				p3->next = p1;
				p1->next = p2;
			}
		}
		else
		{
				p2->next = p1;
				p1->next = NULL;
		}
	}
	return head;
}