demo_struct_list_d.cpp

对于一个初涉VC＋＋的人来书

//***************************************************
//*************************************
//**         Struct_List_D.cpp       **
//*************************************
// 输入和创建链表，最后输出显示该链表

# include <iostream.h>
# include <stdlib.h>
# include <conio.h>

//***************************************************
// 声明结构体
struct Student
{
	long number;
	float score;
	Student* next;
};

//***************************************************
// 定义创建链表的函数
Student* Create()
{
	Student* head;   // 链表的头指针

	Student* pS;     // 链表的结点指针
	Student* pEnd;   // 链表的尾指针 

	// 新建一个结点
	pS= new Student; // 动态申请一个结点内存空间
	if(pS==NULL)
	{
		cout<<"Can't allocate more memory,terminating.\n";
		exit(1);
	}

	cout<<"Input number and score of one item:\n";
	cin>>pS->number>>pS->score; // 给节点赋number和score值

	head=NULL; // 开始链表为空

	if(pS->number==0) // 若链表为空
	{
		delete pS;
		return head;
	}

	while(pS->number!=0) // 若链表为非空
	{
		if(head==NULL)
			head=pS;
		else
			pEnd->next=pS; // 给节点赋next值

		pEnd=pS;

		// 新建一个结点
		pS=new Student; // 动态申请一个结点内存空间
		if(pS==NULL)
		{
			cout<<"Can't allocate more memory,terminating.\n";
			exit(1);
		}

		cout<<"Input number and score of one item:\n";
		cin>>pS->number>>pS->score; // 给节点赋number和score值
	}

	pEnd->next=NULL; // 给节点赋next值

	delete pS;

	return head;
}

//***************************************************
// 定义遍历链表的函数
void ShowList(Student* head)
{
	// 若链表是空的 head==NULL
	if(!head) 
	{
		cout<<"The list is null!\n";
		return;
	}

	cout<<"Output the items of list are \n";
	while(head)
	{
		cout<<head->number<<","<<head->score<<endl;
		head=head->next;
	}
	return;
}

//***************************************************
// 定义链表排序的函数
void Sort(Student* head)
{
	cout<<"The list is sorted!\n";

	// 若链表是空的 head==NULL
	if(!head) return;
	// 若链表只有一个结点 head->next==NULL
	if(!head->next) return;

	for(Student* pGuard1=head;pGuard1->next;pGuard1=pGuard1->next)
		for(Student* pGuard2=pGuard1->next;pGuard2;pGuard2=pGuard2->next)
		{
			if(pGuard1->number>pGuard2->number)
			{
				long temp_number;
				float temp_score;

				temp_number=pGuard1->number;
				pGuard1->number=pGuard2->number;
				pGuard2->number=temp_number;

				temp_score=pGuard1->score;
				pGuard1->score=pGuard2->score;
				pGuard2->score=temp_score;
			}
		}
}

//***************************************************
// 定义排序后链表的插入结点的函数
Student* Insert(Student* head,Student* stud)
{
	if(head==NULL) // 空链表时将结点放在head指针下即可
	{
		head=stud;        // 新链首
		stud->next=NULL;  // 新链尾
		return head;
	}

	if(head->number>stud->number) // 结点插入的位置在链首
	{
		stud->next=head;  // 指向原链首结点 
		head=stud;        // 插入结点成为新链首
		return head;
	}

	// 插入位置在链中
	for(Student* pGuard=head;pGuard->next;pGuard=pGuard->next)
	{
		if(pGuard->next->number>stud->number) // 找到插入位置
		{
			stud->next=pGuard->next;
			pGuard->next=stud;
			return head;
		}
	}

	// 插入位置在链尾
	stud->next=pGuard->next;
	pGuard->next=stud;
	return head;
}

//***************************************************
// 主程序创建并遍历链表
void main()
{
	Student* head;

	head=Create();
	ShowList(head);

	Sort(head);
	ShowList(head);

	Student ps;
	ps.number=36;
	ps.score=(float)3.8;

	head=Insert(head,&ps);
	ShowList(head);
}

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