链表类的实现

powerwind · 发表于 2006-4-2 19:08

一直想学习数据结构,但常常是只看不做,结果只得个半懂.
近来几天有空就写一点,结果完成了一个链表类.
链表实现了,后面的堆栈和队列就不会困难了.
代码如下:

#include<iostream>
using namespace std;
typedef int ElemType;
//双向链表结构MyLink
typedef struct Link{
ElemType data;
struct Link* prior;
struct Link* next;
}MyLink;
//链表类LinkList
class LinkList
{
protected:
int length; //链表长度
MyLink*head,*tail; //定义表头和表尾指针
public:
LinkList();
LinkList(ElemType e);
~LinkList();
int getLength(){return this->length;} //获得长度
void insert(ElemType e); //插入元素到最后
void insert(ElemType e,int position); //插入元素到指定位置
void print(char ch); //ch指定间隔符,默认换行输出
ElemType getElement(int index); //获取指定索引位置的元素
int search(ElemType e); //搜索指定元素
void clear(); //清空链表
void sort(); //对所有元素进行升序排序
bool isEmpty(); //判断是否为空
void del(int index); //删除指定位置元素
void merge(LinkList&); //合并链表
};
//无参数构造函数
LinkList::LinkList()
{
head=new MyLink;
head->prior=NULL;
head->next=NULL;
tail=head;
length=0;
}
//有一个元素构造函数
LinkList::LinkList(ElemType e)
{
head=new MyLink;
head->prior=NULL;
head->next=new MyLink;
head->next->data=e;
tail=head->next;
tail->next=NULL;
length=1;
}
//析构函数
LinkList::~LinkList()
{
delete head;
}
//增加元素
void LinkList::insert(ElemType e)
{
insert(e,length+1);
}
//在指定位置插入元素
void LinkList::insert(ElemType e,int position)
{
if(position>length+1)return;
else if(position<=0)return;
MyLink*p=new MyLink;
p->data=e;
if (position==1)
{
p->prior=head;
p->next=head->next;
if(head->next!=NULL)head->next->prior=p;
if(head==tail)tail=p; //如果原本为空,新插入元素
head->next=p;
}else if (position==length+1)
{
p->prior=tail;
p->next=NULL;
tail->next=p;
tail=tail->next;
}else
{
MyLink*temp;
if(position>length/2) //根据要插入元素的位置选择
{ //从头部还是尾部开始移动指针
temp=tail;
int i=length-position;
while (i--)temp=temp->prior;
}else
{
temp=head;
while (position--)temp=temp->next;
}
p->prior=temp->prior; //插到temp元素前面
p->next=temp;
temp->prior->next=p;
temp->prior=p;
temp=NULL;
}
p=NULL; //给没用的指针一个NULL值是好习惯
length++; //长度加1
}
//删除元素
void LinkList::del(int index)
{
if(index<=length&&index>0&&length!=0)
{
MyLink*p=head;
int i=index;
if(index==1)
{
p=head->next;
head->next=p->next;
if(p->next!=NULL)p->next->prior=head;
delete p;
}else if(index==length)
{
p=tail;
tail=p->prior;
if(p->prior!=head)p->prior->next=tail;
tail->next=NULL;
delete p;
}
else
{
while(i--)p=p->next;
p->prior->next=p->next;
p->next->prior=p->prior;
delete p;
}
p=NULL;
length--;
}
}
int LinkList::search(ElemType e)
{
MyLink*p=head->next;
for (int i=0;i<length;i++)
{
if(p->data==e)return (i+1);
p=p->next;
}
return 0;
}
//输出所有元素
void LinkList::print(char ch='\n')
{
MyLink*p=head->next;
while (p->next!=NULL)
{
cout<<p->data<<ch;
p=p->next;
}
cout<<p->data<<endl;
}
//清空所有元素
void LinkList::clear()
{
MyLink*q,*p;
p=head->next;
while (p!=NULL)
{
q=p->next;
delete p;
p=q;
}
length=0;
tail=head;
head->next=NULL;
}
//获取指定位置的元素
ElemType LinkList::getElement(int index)
{
if (index>0&&index<=length)
{
if(index==1)return head->next->data;
if(index==length)return tail->data;
MyLink*p=head;
if (index>length/2)
{
int i=length-index;
p=tail;
while (i--)p=p->prior;
}
else while(index--)p=p->next;
return p->data;
}
}
//判断链表是否为空
bool LinkList::isEmpty()
{
return head->next=NULL;
}
//
void LinkList::sort()
{
MyLink*r,*h,*p,*temp;
h=new MyLink;
h->prior=NULL;
h->next=NULL;
p=h;
if (head->next!=NULL&&head->next->next!=NULL)
{
for(int i=length;i>0;i--)
{
r=temp=head->next;
while (r!=NULL)
{
if(r->data<temp->data)temp=r;
r=r->next;
}
p->next=temp;
if(temp->next!=NULL)temp->next->prior=temp->prior;
temp->prior->next=temp->next;
temp->prior=p;
p=temp;
p->next=NULL;
}
tail=p;
head->next=h->next;
h->next->prior=head;
}
delete h;
}
//合并链表
void LinkList::merge(LinkList&link)
{
this->tail->next=link.head->next;
link.head->next->prior=this->tail;
this->length+=link.length;
}

复制代码

写了个main函数测试,基本上没有发现问题.

庐山升龙霸 · 发表于 2006-4-2 20:16

过几天我也写个C#版的出来.

loom · 发表于 2006-4-2 20:31

我之前写过个java版的.呵呵...

		自动登录	找回密码
密码			加入后院

链表类的实现

相关帖子