link2.cpp

单链表的实现方法

//程序名：link2.cpp
//      程序功能：带表头结点单向链表类的实现（包括单向链表插入，删除和查找操作的实现）
//          作者：william
//          日期：2006.10.1
//          版本：1.1
//      修改内容：在该版本是在link1.cpp的基础上修改了让链表带有连头结点
//      修改日期：2006.10.2
//      修改作者：william
//
//
//

#include<stdio.h>
#include<iostream.h>

typedef int DataType;      //为本程序定义所使用的具体数据类型

struct LinkNode {           //定义单向链表的结点结构
	DataType data;
	struct LinkNode *next;
};

class Link{         //  定义单向链表类

public:
     
    Link(void);    // 定义构造函数，初始化为带表头结点的空链
    int Insert(int i ,DataType x);    //插入
    int Delete(int i);    //删除
    void TailCreate(int n);   //尾插入建立单向链表
    void HeadCreate(int n);   //头插入建立单向链表
    void Print();    // 输出整个单向链表中的数据
    ~Link(void);   //析构函数

private:
	struct LinkNode *head;    // 链头结点

};

//////////////////////////////////////////////////////////////////////////////
//  构造函数
//  函数功能：将链头指针初始化为带表头结点的空链
//函数参数：无
//参数返回值：无

Link::Link(void)
{
  head=new LinkNode;  // // head is the attribute of link class
  head->next=NULL;
}

//////////////////////////////////////////////////////////////////////////////
// 析构函数
// 函数功能：将链表所有结点的空间释放(包括表头结点)
//函数参数：无
//参数返回值：无

Link::~Link(void)
{
 struct LinkNode *p;
 
 while(head!=NULL)
 {
	 p=head;
	 head=head->next;
	 delete p;
 }
}

//////////////////////////////////////////////////////////////////////////////
//  插入函数
//  函数功能：将一个新值插入到某个位置的结点之后上,如果超过总结点个数，则做尾插入
//函数参数：
//       i 表示插入位置
//       x 表示待插入的元素值      
//参数返回值：
//     1： 表示插入成功
//     0：表示插入失败     
int Link::Insert(int i ,DataType x)
{
 struct LinkNode *temp;
 struct LinkNode *p,*q;  // head is the attribute of link class
 

 if ( i<=0) 
  {
	cout<<"\n the position is error\n\n";
    return 0;   // error
  }
  
  int j=1;
  q=head; p=head->next; //q从表头结点开始走,p则从链表的第一结点开始
  while(j <i && p!=NULL)     
  {
     q=p; p=p->next;
	 j++;
  }
  temp=new LinkNode;
  temp->data=x;
  temp->next=p;
  q->next=temp;
  return 1;  // ok
}

//////////////////////////////////////////////////////////////////////////////
//  删除函数
//  函数功能：将链表中某个位置上的结点删除
//函数参数：
//       i 表示删除位置
//参数返回值：
//     1： 表示删除成功
//     0：表示删除失败     
int Link::Delete(int i)
{
 struct LinkNode *q,*p;
 
 int j=1;

 if ( i<=0) 
  {
	cout<<"\n the position is error\n\n";
    return 0;   // error
  }
  
  q=head; p=head->next;
  while(j <i && p!=NULL)
  {
     q=p;
	 p=p->next;
	 j++;
  }
  if (p==NULL)
  {
	  cout<<"the position is our of range\n\n";
	  return 0;  // error
  }
  q->next=p->next;
  delete p;
  return 1; // ok
}

//////////////////////////////////////////////////////////////////////////////
//  尾插入建立链表函数
//  函数功能：用尾插入建立链表方法生成一个具有n个结点的链表
//函数参数：
//       n 表示结点个数
//参数返回值：无
void Link::TailCreate(int n)
{
  struct LinkNode *R,*p;
  R=head;
  for(int i=0;i<n;i++)
  {
	  p=new LinkNode;
	  cin>>p->data;
	  p->next=NULL;
	  R->next=p;
	  R=p;
  };
}

//////////////////////////////////////////////////////////////////////////////
//  头插入建立链表函数
//  函数功能：用头插入建立链表方法生成一个具有n个结点的链表
//函数参数：
//       n 表示结点个数
//参数返回值：无

void Link::HeadCreate(int n)
{
  struct LinkNode *p, *h=NULL;
  for(int i=0;i<n;i++)
  {
	  p=new LinkNode;
	  cin>>p->data;
	  p->next=h;
	  h=p;
  };
  head->next=p;   // head is the attribute of link class  因为带表头结点
}


//////////////////////////////////////////////////////////////////////////////
//  链表输出函数
//  函数功能：从头到尾的将链表中的所有结点一个一个输出来（不包括表头结点）
//函数参数：无
//参数返回值：无

void Link::Print(void)
{
 struct LinkNode *p=head->next;   //跳过表头结点，表头结点的值不能输出
 cout<<"\n The data in the link are:\n";
 while ( p!=NULL)
 {
	 cout<<p->data<<"   ";   
	 p=p->next;
 }
 cout<<"\n\n\n";
}


//////////////////////////////////////////////////////////////////////////////
//  主函数
//参数返回值：无

void main()
{
	Link link1;  // link1 object   
	int finished=0;
    int choice , n ,pos;
	DataType x;

	while ( !finished )
    {
		cout<<"*********Menu*********\n";
		cout<<"1:Created by insert in head\n";
        cout<<"2:Created by insert in tail\n";
		cout<<"3:Insert\n";
		cout<<"4:Delete\n";
		cout<<"5:display all\n";
		cout<<"6:exit\n";
		cout<<"Please choose a choice(1-6):";
		cin>>choice;
		switch(choice)
		{
		case 1:
			   cout<<"\nplease enter the number of nodes(insert in head):";   //调用头插入建立链表
			   cin>>n;
			   link1.HeadCreate(n);
			   link1.Print();
               break; 
        case 2:
		       cout<<"\nplease enter the number of nodes(insert in tail):";    //调用尾插入建立链表
			   cin>>n;
			   link1.TailCreate(n);
			   link1.Print();
               break;      
		case 3:
               cout<<"\nplease enter the position to insert:";     //调用链表插入函数
			   cin>>pos;
			   cout<<"\n please enter the data to insert\n";
			   cin>>x;
			   if ( link1.Insert(pos,x)==1)  // ok
				    link1.Print();
               break; 
		case 4:
               cout<<"\nplease enter the position to delete:";     //调用链表删除函数
			   cin>>pos;
			   if ( link1.Delete(pos)==1 )
			      link1.Print();   //ok
               break; 
       case 5:
			  link1.Print();      //调用链表输出函数
			  break;
		case 6:
			   finished=1;     //结束程序
			   break;
		}  // switch
	} // while 
}// main