liangbiao.cpp

分析了链表的基本知识

// liangbiao.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"


// int _tmain(int argc, _TCHAR* argv[])
// {
// 	return 0;
// }

#include <iostream>
using namespace std;

struct node 
{
	int data;
	node *next;
};

node *Creat(void)  //产生一条无序链
{
	node *p1,*p2,*head=0;
	int a;
	cout<<"产生一条无序链，以-1结束";
	cin>>a;
	while(a!=-1)
	{
		p1 = new node;
		p1->data = a;
		if (head==0)
		{
			head = p1;
			p2 = p1;
		} 
		else
		{
			p2->next = p1;
			p2 = p1;
		}
		cin>>a;
	} 
	p2->next = 0;
	return(head);
}

void Print(const node*head)    //输出链上各节点的数据
{
	const node *p = head;
	cout<<"各结点数据为：\n";
	while (p!=0)
	{
		cout<<p->data<<'\t';
		p = p->next;
	}
	cout<<"\n";
}

node *Delete_one_node(node*head,int num)
{
	node *p1,*p2;
	if (head == 0)
	{
		cout<<"链表为空！\n";
		return(0);
	}
	if (head->data==num)
	{
		p1=head;
		head=head->next;
		delete p1;
		cout<<"删除了一个结点"<<num<<"\n";
	} 
	else
	{
		p1 = head;
		p2 = head->next;
		while (p2->data!=num&&p2->data!=0)
		{
			p1 = p2;
			p2 = p2->next;
		}
		if (p2->data == num)
		{
			p1->next = p2->next;
			delete p2;
			cout<<"删除了一个结点！\n";
		}
		else
			cout<<"链上没有找到要删除的结点！";
	}
	return(head);
}

node *Insert(node *head,node*p)
{
	node *p1,*p2;
	if (head == 0)
	{
		p->next = 0;
		return(p);
	}
	if (head->data>=p->data)
	{
		p->next = head;
		return(p);
	}
	p2=p1=head;
	while(p2->next&&p2->data<p->data)
	{
		p1 = p2;
		p2 = p2->next;
	}
	if (p2->data < p->data)
	{
		p2->next = p;
		p->next = 0;
	}

	else
	{
		p->next = p2;
		p1->next = p;
	}
	return(head);
}

node *Create_Sort(void)
{
	node *p1,*head = 0;
	int a;
	cout<<"产生一条排序链，请输入数据，以-1结束：\n";
	cin>>a;
	while (a!=-1)
	{
		p1 = new node;
		p1->data = a;
		head = Insert(head,p1);
		cin>>a;
	}
	return(head);
}


void deletechain(node *h)
{
	node *p1;
	while (h)
	{
		p1=h;
		h=h->next;
		delete p1;
	}
}
void main(void)
{
	node *head;
	int num;
	head = Creat();
	Print(head);
	cout<<"输入要删除的结点上的整数：";
	cin>>num;
	head = Delete_one_node(head,num);
	Print(head);
	deletechain(head);
	head = Create_Sort();
	Print(head);
	deletechain(head);
}