#include <iostream>
using namespace std;
#define MAXSIZE 100
template<class T>
struct Node //结构体定义
{
T data;
Node<T> *next;
};
template<class T>
class LinkList
{
public:
LinkList(T a[], int n);
~LinkList();
int Length();
T Get(int i);
int Locate(T x);
void Insert(int i,T x);
void Motify(int i,T x);
T Delete(int i);
void PrintList();
private:
Node<T> *first;
};
/********************************功能函数部分*********************************/
template<class T> //构造函数，头插法建立单链表
LinkList<T>::LinkList(T a[],int n)
{
int flag=3;
first=new Node<T>;
int i;
Node<T> *s;
loop:
printf("输入插入的方式1头插入 2尾插入:");
scanf("%d", &flag);
switch(flag)
{
case 1:
first->next=NULL;
for( i=0;i<n;i++)
{
s=new Node<T>;s->data=a[i];
s->next=first->next;
first->next=s;
}
break;
case 2:
Node<T> *r;
r=first; //尾指针初始化
for ( i=0; i<n; i++)
{
s=new Node<T>; s->data=a[i]; //为每个数组元素建立一个结点
r->next=s; r=s; //插入到终端结点之后
}
r->next=NULL; //单链表建立完毕，将终端结点的指针域置空
break;
default:
printf("请确认后再次输入!\n");
goto loop;
break;
}
}
template <class T>
LinkList<T>:: ~LinkList()
{
}
template <class T>
T LinkList<T>::Get(int i) //按位查询
{
Node<T> *p; int j;
p=first->next; j=1; //或p=first; j=0;
while (p && j<i)
{
p=p->next; //工作指针p后移
j++;
}
if (!p) throw "位置";
else
cout<<"\t\t结点i的值为:"<<p->data;
return p->data;
}
template <class T>
int LinkList<T>::Locate(T x) //按值查询
{
Node<T> *p; int j;
p=first->next; j=1;
if(p&&p->next){
while(p->data!=x)
{
p=p->next;
j++;
}
cout<<"\t\t数值x的结点位置为:"<<j;
return j;
}
else throw "位置";
}
template <class T>
void LinkList<T>::Insert(int i, T x) //插入函数
{
Node<T> *p; int j;
p=first ; j=0; //工作指针p初始化
while (p && j<i-1)
{
p=p->next; //工作指针p后移
j++;
}
if (!p) throw "位置";
else {
Node<T> *s;
s=new Node<T>;
s->data=x; //向内存申请一个结点s，其数据域为x
s->next=p->next; //将结点s插入到结点p之后
p->next=s;
}
}
template <class T> //求长度函数
int LinkList<T>::Length( )
{
Node <T> *p = first->next;
int i = 0;
while(p)
{
p = p->next;
i++;
}
cout<<i;
return i;
}
template <class T> //删除函数
T LinkList<T>::Delete(int i)
{
Node<T> *p; int j;
p=first ; j=0; //工作指针p初始化
while (p && j<i-1) //查找第i-1个结点
{
p=p->next;
j++;
}
if (!p || !p->next) throw "位置"; //结点p不存在或结点p的后继结点不存在
else {
Node<T> *q; int x;
q=p->next; x=q->data; //暂存被删结点
p->next=q->next; //摘链
delete q;
return x;
}
}
template <class T>
void LinkList<T>::Motify(int i,T x)// 修改函数。。。,,,,
{
Node<T> *p;int j;
p=first;
for(j=0;j<i;j++)
{p=p->next;}
cout<<"\t\t原来这个结点的x值为:"<<p->data<<endl;
p->data=x;
cout<<"\t\t现在这个结点的x值为:"<<p->data<<endl;
}
template <class T> //输出函数。。
void LinkList<T>::PrintList( )
{
Node<T> *p;
p=first->next;
cout<<"\t\t\t";
while (p)
{
cout<<p->data<<" ";
p=p->next;
}
}
/******************************主函数部分**************************************/
int main()
{
int n,r[MAXSIZE],flag=1,select;
cout<<"\t\t\t 单链表初始化(头插法)"<<endl<<endl;
cout<<"\t\t\t请输入数组的长度：";
cin>>n;
cout<<"\t\t\t请输入数据:";
for(int i=0;i<n;i++)
cin>>r[i];
LinkList<int> a(r,n); //模板类的定义方法；
cout<<"\t\t\t你所输入的单链表如下:"<<endl;
a.PrintList();
cout<<endl<<endl;
cout<<"********************************************************************************"<<endl;
cout<<"*********************************单链表操作菜单*********************************"<<endl;
cout<<endl;
cout<<"\t\t\t1.在第i个结点插入数值元素x"<<endl;
cout<<"\t\t\t2.删除第i个结点上的数值"<<endl;
cout<<"\t\t\t3.修改第i个结点上的数值x"<<endl;
cout<<"\t\t\t4.查询第i个结点上的数值x"<<endl;
cout<<"\t\t\t5.查询数值x的位置i"<<endl;
cout<<"\t\t\t6.求单链表的结点数n:"<<endl;
cout<<"\t\t\t7.退出程序"<<endl;
while (flag)
{
cout<<"\t\t\t请选择操作(1-7): ";
cin>>select;
switch(select)
{
case 1:
int i,x;
cout<<"\t\t请输入需要插入的位置i和数值x:";
cin>>i>>x;
a.Insert(i,x);
cout<<"\t\t现在的单链表为:";
a.PrintList();
cout<<endl;
break;
case 2:
//int i;
cout<<"\t\t请输入需要删除的结点的位置i:";
cin>>i;
a.Delete(i);
cout<<"\t\t现在的单链表为:";
a.PrintList();
cout<<endl;
break;
case 3:
cout<<"\t\t请输入需要修改结点的位置i和数值x:";
cin>>i>>x;
a.Motify(i,x);
cout<<"\t\t现在的单链表为:";
a.PrintList();
cout<<endl;
break;
case 4:
cout<<"\t\t请输入结点的位置i:";
cin>>i;
a.Get(i);
cout<<endl;
break;
case 5:
cout<<"\t\t请输入数值x:";
cin>>x;
a.Locate(x);
cout<<endl;
break;
case 6:
cout<<"\t\t此单链表的结点个数为:";
a.Length();
cout<<endl;
break;
case 7:
flag=0;
break;
}
}
return 0;
}
线性表的链式存储.rar
(4.12 KB)
2010-10-12 12:25
