软件工程师面试宝典（第三版）——单链表的基本操作：建立，求长度，输出，排序，插入，删除，逆置

程序员面试宝典（第三版）——单链表的基本操作：建立，求长度，输出，排序，插入，删除，逆置

编程实现一个单链表的建立，求单链表的长度，打印输出单链表，对单链表进行排序，插入元素，删除元素，对单链表进行逆置。

我是借鉴参考资料，然后自己写规范，对函数都进行了调用，每一次调用，都有输出单链表。程序完整，已调试运行。

源程序：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<conio.h>
using namespace std;
typedef struct student
{
	int data;
	struct student *next;
}node;
//建立单链表
node *creat()
{
	node *head,*p,*s;
	int x,cycle=1;
	head=(node*)malloc(sizeof(node));
	p=head;
	cout<<"请输入单链表的数据，以0作为结束标识："<<endl;
	while(cycle)
	{	
		cin>>x;
		if(x!=0)//以0为标识
		{
			s=(node *)malloc(sizeof(node));
			s->data=x;
			p->next=s;
			p=s;
		}
		else cycle=0;
	}
	head=head->next;
	p->next=NULL;
	cout<<endl;
	return (head);
}
 //求单链表的长度
int length(node *head)
{
	int n=0;
	node *p;
	p=head;
	while(p!=NULL)
	{
		p=p->next;
		n++;
	}
	return(n);
}
//输出单链表
void print(node *head)
{
	node *p;int n;
	n=length(head);
	cout<<"现在，长度为"<<n<<"的单链表更新为:"<<endl;
	p=head;
	if(head!=NULL)
	{
		while(p!=NULL)
		{
			cout<<p->data<<'\t';
			p=p->next;
		}
	}
	printf("\n");
}
//删除单链表中的某个元素
node *del(node *head,int num)
{
	node *p1,*p2;
	p1=head;
	while(num!=p1->data&&p1->next!=NULL)
	{
		p2=p1;
		p1=p1->next;
	}
	if(num==p1->data)
	{
		if(p1==head)
		{
			head=p1->next;
			free(p1);
		}
		else
			p2->next=p1->next;
	}
	else
		cout<<num<<"没有在单链表中找到！"<<endl;//printf("\n%d 没有在单链表中找到！",num);
	return head;
}
//在单链表中插入一个元素
node *insert(node *head,int num)
{
	node *p0,*p1,*p2;
	p1=head;
	p0=(node *)malloc(sizeof(node));
	p0->data=num;
	while(p0->data>p1->data&&p1->next!=NULL)
	{
		p2=p1;p1=p1->next;
	}
	if(p0->data<=p1->data)
	{
		if(head==p1)
		{
			p0->next=p1;
			head=p0;
		}
		else
		{
			p2->next=p0;
			p0->next=p1;
		}
	}
	else
	{
		p1->next=p0;
		p0->next=NULL;
	}
	return head;
}
//对单链表从小到大排序：
node *sort(node *head)
{
	node *p;
	int n;int temp;
	n=length(head);
	if(head==NULL||head->next==NULL)
		return head;
	p=head;
	for(int j=1;j<n;++j)
	{
		p=head;
		for(int i=0;i<n-j;++i)
		{
			if(p->data>p->next->data)
			{
				temp=p->data;
				p->data=p->next->data;
				p->next->data=temp;
			}
			p=p->next;
		}
	}
	return head;
}
//对单链表进行逆置
node *reverse(node *head)
{
	node *p1,*p2,*p3;
	
	if(head==NULL||head->next==NULL)
		return head;
	p1=head,p2=p1->next;
	while(p2)
	{
		p3=p2->next;
		p2->next=p1;
		p1=p2;
		p2=p3;
	}
	head->next=NULL;
	head=p1;
	return head;
}
int main()
{
	node *head;
	int n,del_num,insert_num;

	head=creat();
	print(head);

	cout<<"\n单链表的长度: ";
	n=length(head);
	cout<<n<<endl;
	
	cout<<"\n请对单链表排序:";
	head=sort(head);
	print(head);

	cout<<"\n请输入单链表中要删除的数据: ";
	cin>>del_num;
	head=del(head,del_num);
	print(head);

	cout<<"\n请输入单链表中要插入的数据:";
	cin>>insert_num;
	head=insert(head,insert_num);
	print(head);

	cout<<"\n请对单链表进行逆置:";
	head=reverse(head);
	print(head);

	return 0;
}

运行结果：

总结：单链表的基本操作，包括建立单链表，对单链表求长度，打印输出单链表，对单链表进行排序，删除元素，插入元素，对单链表逆置。这些操作都是程序员必须掌握的，虽然它是一种相对简单的数据结构，但是能够做到熟练掌握运用也是需要花时间的。