存档-----------
#include <iostream.h>
typedef char ElemType;
#include "LinkList.h"
void main()
{
LinkList h;
ElemType e;
int i=;
int t=;
cout<<"(1)初始化单链表h\n";
InitList(h);
cout<<"(2)单链表为"<<(ListEmpty(h)?"空":"非空")<<endl;
cout<<"(3)依次输入字母序列，以'#'结束"<<endl;
cin>>e;
i=;
while(e!='#')
{
ListInsert(h,i,e);
i++;
cin>>e;
}
cout<<"(4)输出单链表h:";
PrintList(h);
cout<<"(5)单链表h的长度="<<ListLength(h)<<endl;
cout<<"(5)单链表h为"<<(ListEmpty(h)?"空":"非空")<<endl;
cout<<"(6)测试GetElem(L,i,e)函数，请输入i的值"<<endl;
cin>>i;
t=GetElem(h,i,e);
if(t)
cout<<"(6)单链表h的第"<<i<<"个元素="<<e<<endl;
else
cout<<"(6)单链表h的第"<<i<<"个元素不存在\n";
cout<<"(7)测试LocateElem(L,e)函数，请输入e的值"<<endl;
cin>>e;
t=LocateElem(h,e);
if(t)
cout<<"(7)元素"<<e<<"的位置="<<t<<endl;
else
cout<<"(7)元素"<<e<<"不存在\n";
cout<<"(8)测试ListInsert(L,i,e)函数，请输入i的值和e的值"<<endl;
cout<<"请输入i的值:";
cin>>i;
cout<<"请输入e的值:";
cin>>e;
cout<<"(8)在第"<<i<<"个元素位置上插入"<<e<<"元素:";
t=ListInsert(h,i,e);
if(t)
cout<<"成功!\n";
else
cout<<"失败!\n";
cout<<"(9)输出单链表h:";
PrintList(h);
cout<<"(10)测试ListDelete(L,i,e)函数，请输入i的值"<<endl;
cin>>i;
cout<<"(10)删除h的第"<<i<<"个元素:";
t=ListDelete(h,i,e);
if(t)
cout<<"成功!\n";
else
cout<<"失败!\n";
cout<<"(11)输出单链表h:";
PrintList(h);
cout<<"(12)释放单链表h\n";
DestoryList(h);
}
typedef struct LNode//定义单链表结点类型
{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
int InitList(LinkList &L)
{
//初始化只含有头结点的空的单链表
L=new LNode;//创建头结点
if(L==NULL)
{
cout<<"结点分配失败\n";
return ;
}
L->next=NULL;
return ;
}
void ClearList(LinkList &L)
{
//清空单链表，仅保留头结点
LinkList p;
while(L->next)
{
p=L->next;
L->next=p->next;
delete p;
}
}
int ListLength(LinkList L)
{
//返回单链表的长度
LinkList p=L;
int i=;
while(p->next!=NULL)//数到最后一个结点为止
{
i++;
p=p->next;
}
return i;
}
void PrintList(LinkList L)
{
//顺序输出单链表中的各元素
LinkList p=L->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
bool ListEmpty(LinkList L)
{
//判断是否为空链表
if(L->next==NULL)
return true;
else
return false;
}
int GetElem(LinkList L,int i,ElemType &e)
{
//用e返回单链表L中第i个元素的值
if(i<)
return ;
LinkList p=L->next;
int j=;
while(j<i&&p!=NULL)
{
p=p->next;
j++;
}
if(p==NULL)//j<i,但p为空指针了，即i超出了[1...n]范围了
return ;
else
{
e=p->data;
return ;
}
}
int LocateElem(LinkList L,ElemType e)
{
//返回e元素在单链表L中的位序，若不存在，返回0
LinkList p=L->next;
int n=;
while(p!=NULL&&p->data!=e)
{
p=p->next;
n++;
}
if(p==NULL)//直到最后也没找到等于元素e的结点
return ;
else
return n;
}
int ListInsert(LinkList &L,int i,ElemType e)
{
//在单链表L的第i个数据元素之前插入数据元素e
if(i<)
return ;
int j=;//在1号位置插入时，i-1号位置是0号位置
LinkList p=L,s;
while(j<i-&&p!=NULL)//寻找第i-1个结点
{
p=p->next;
j++;
}
if(p==NULL)//未找到第i-1个结点，即i超出了[1..n+1]时
return ;
else//找到第i-1个结点p
{
s=new LNode;//创建新结点s
if(s==NULL)
{
cout<<"结点分配失败\n";
return ;
}
s->data=e;
s->next=p->next;//将s插入到p之后
p->next=s;
return ;
}
}
int ListDelete(LinkList &L,int i,ElemType &e)
{
//删除单链表L中第i个结点，并用e返回其值
if(i<)
return ;
LinkList p=L,q;
int j=;
while(j<i-&&(p->next)!=NULL)//寻找第i-1个结点，且第i-1号元素不是最后一个元素
{
p=p->next;
j++;
}
if((p->next)==NULL)//未找到第i-1个结点，即i超出了[1..n]
return ;
else//找到第i-1个结点p
{
q=p->next;//q指向要删除的结点
p->next=q->next;//从单链表中删除q结点
e=q->data;
delete q;//释放q结点
return ;
}
}
void DestoryList(LinkList &L)
{
//销毁单链表
LinkList p;
while(L)
{
p=L;
L=L->next;
delete p;
}
L=NULL;
}
运行结果如下：
