单链表操作算法.txt

单链表的一些简单算法。

else { 
LNode* cp; 
LNode* ap; 
ap=NULL; cp=HL;
while(cp!=NULL) {
if(item<cp->data) break;
else {ap=cp; cp=cp->next;}
}
if(ap==NULL) {newptr->next=HL; HL=newptr;}
else {newptr->next=cp; ap->next=newptr;}
}
}

//从单链表中删除元素
bool DeleteList(LNode*& HL, ElemType& item, int mark)
{
if(HL==NULL) return false;
//删除表头结点
if(mark>0) {
LNode* p=HL;
item=HL->data;
HL=HL->next;
delete p;
return true;
}
//删除表尾结点
else if(mark<0) {
LNode *cp=HL, *ap=NULL;
while(cp->next!=NULL) {
ap=cp; cp=cp->next;
}
if(ap==NULL) HL=NULL;
else ap->next=cp->next; 
item=cp->data;
delete cp;
return true;
}
//删除值为item结点
else {
LNode *cp=HL, *ap=NULL;
while(cp!=NULL)
if(cp->data==item) break;
else {ap=cp; cp=cp->next;}
if(cp==NULL) return false;
else {
if(ap==NULL) HL=HL->next;
else ap->next=cp->next;
item=cp->data;
delete cp;
return true;
}
}
}
//对单链表进行有序输出
void OrderOutputList(LNode* HL, int mark)
{
if(HL==NULL) {cout<<"链表为空!"<<endl; return;}
//建立新的单链有序表的表头结点
LNode* head=new LNode; //head为新建有序表的表头指针
head->data=HL->data; head->next=NULL;
//根据HL单链表生成head单链有序表
for(LNode* p=HL->next; p; p=p->next) {
LNode* q=new LNode;
q->data=p->data;
LNode *cp=head, *ap=NULL;
//为向head单链表插入q结点而顺序查找合适位置
while(cp) {
if(mark==1) {
if(q->data<cp->data) break;
else {ap=cp; cp=cp->next;}
}
else {
if(cp->data<q->data) break;
else {ap=cp; cp=cp->next;}
}
}
//把q结点插入head有序单链表中
if(ap==NULL) {q->next=head; head=q;}
else {
q->next=cp; ap->next=q;
}
}
//遍历head有序单链表
TraverseList(head); 
//清除head有序单链表
ClearList(head); 
}

//比较两个元素是否相等
bool operator==(const ElemType& r1, const ElemType& r2)
{
return strcmp(r1.name, r2.name)==0;
}

//比较两个元素的大小
bool operator<(const ElemType& r1, const ElemType& r2)
{
return strcmp(r1.name, r2.name)==-1;
}

//输出一个元素
ostream& operator<<(ostream& ostr, const ElemType& r)
{
ostr.setf(ios::left);
ostr<<setw(10)<<r.name<<setw(5)<<r.grade<<" ";
return ostr;
}

//输入一个元素
istream& operator>>(istream& istr, ElemType& r)
{
istr>>r.name>>r.grade;
return istr;
}

//主文件linkmain2.cpp

#include<iomanip.h>
#include"linklist2.h"

void main()
{
LNode* a;
InitList(a);
int i;
ElemType x;
//依次向单链表a表尾插入5个学生记录
cout<<"从键盘输入5个学生记录:";
for(i=0; i<5; i++) {
cin>>x;
InsertList(a,x,-1);
}
//依次向单链表a表头插入2个学生记录
cout<<"从键盘输入2个学生记录:";
cin>>x; InsertList(a,x,1);
cin>>x; InsertList(a,x,1);
//按不同次序遍历输出单链表a
TraverseList(a);
OrderOutputList(a,1);
OrderOutputList(a,0);
//从单链表a中查找一个给定姓名的记录
cout<<"从键盘上输入一个待查学生的姓名:";
cin>>x.name;
if(FindList(a,x)) cout<<x<<" 查找成功!"<<endl;
else cout<<"查找失败!"<<endl;
//从单链表a中更新一个给定姓名的记录
cout<<"从键盘上输入一个待更新学生的记录:";
cin>>x;
if(UpdateList(a,x)) cout<<"更新成功!"<<endl;
else cout<<"更新失败!"<<endl;
TraverseList(a);
//从单链表a中分别删除表头、表尾、给定值结点
if(DeleteList(a,x,1)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
if(DeleteList(a,x,-1)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
cout<<"从键盘上输入一个待删除学生的姓名:";
cin>>x.name;
if(DeleteList(a,x,0)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
//输出单链表a
TraverseList(a);
}

程序3:
//头文件linklist3.h

//定义ElemType为int类型
typedef int ElemType;

//单链表中结点的类型
struct LNode {
ElemType data; //值域
LNode* next; //指针域
};
struct LinkList {
LNode* head;
public:
//构造函数
LinkList() {head=NULL;}
//复制构造函数
LinkList(LinkList& HL);
//析构函数
~LinkList();
//求单链表长度
int ListSize(); 
//检查单链表是否为空
bool ListEmpty();
//返回单链表中指定序号的结点值
ElemType GetElem(int pos);
//遍历单链表
void TraverseList();
//从单链表中查找元素
bool FindList(ElemType& item);
//更新单链表中的给定元素
bool UpdateList(const ElemType& item);
//向单链表插入元素
void InsertList(const ElemType& item, int mark);
//从单链表中删除元素
bool DeleteList(ElemType& item, int mark);
//对单链表进行有序输出
void OrderOutputList(int mark);
};

//实现文件linklist3.cpp

#include<iomanip.h>
#include<stdlib.h>

#include"linklist3.h"

//复制构造函数
LinkList::LinkList(LinkList& HL)
{
if(HL.head==NULL) {head=NULL; return;}
head=new LNode; 
head->data=HL.head->data;
LNode *p, *q=head;
for(p=HL.head->next; p; p=p->next) {
q=q->next=new LNode;
q->data=p->data;
}
q->next=NULL;
}

//析构函数
LinkList::~LinkList()
{
LNode *cp, *np; 
cp=head; 
while(cp!=NULL) 
{
np=cp->next; 
delete cp; 
cp=np; 
}
head=NULL; 
}

//求单链表长度
int LinkList::ListSize() 
{
LNode* p=head;
int i=0;
while(p!=NULL) {
i++;
p=p->next;
}
return i;
}

//检查单链表是否为空
bool LinkList::ListEmpty()
{
return (head==NULL);
}

//返回单链表中指定序号的结点值
ElemType LinkList::GetElem(int pos)
{
if(pos<1) {
cerr<<"pos is out range!"<<endl;
exit(1);
}
LNode* p=head;
int i=0;
while(p!=NULL) {
i++;
if(i==pos) break;
p=p->next;
}
if(p!=NULL)
return p->data;
else {
cerr<<"pos is out range!"<<endl;
exit(1);
}
}

//遍历单链表
void LinkList::TraverseList()
{
LNode* p=head;
while(p!=NULL) {
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

//从单链表中查找元素
bool LinkList::FindList(ElemType& item)
{
LNode* p=head;
while(p!=NULL) 
if(p->data==item) {
item=p->data;
return true;
}
else
p=p->next;
return false;
}

//更新单链表中的给定元素
bool LinkList::UpdateList(const ElemType& item)
{
LNode* p=head;
while(p!=NULL) //查找元素 
if(p->data==item)
break;
else
p=p->next;
if(p==NULL) 
return false;
else { //更新元素
p->data=item;
return true;
}
}

//向单链表插入元素
void LinkList::InsertList(const ElemType& item, int mark)
{
//建立一个值为item的新结点
LNode* newptr;
newptr=new LNode; 
newptr->data=item; 
//向表头插入结点
if(mark>0) { 
newptr->next=head; head=newptr;
}
//向表尾插入结点
else if(mark<0) { 
if(head==NULL) {newptr->next=NULL; head=newptr;}
else {
LNode* p=head;
while(p->next!=NULL) 
p=p->next;
p->next=newptr; newptr->next=NULL;
}
}
//插入到合适位置
else { 
LNode* cp; 
LNode* ap; 
ap=NULL; cp=head;
while(cp!=NULL) {
if(item<cp->data) break;
else {ap=cp; cp=cp->next;}
}
if(ap==NULL) {newptr->next=head; head=newptr;}
else {newptr->next=cp; ap->next=newptr;}
}
}

//从单链表中删除元素
bool LinkList::DeleteList(ElemType& item, int mark)
{
if(head==NULL) return false;
//删除表头结点
if(mark>0) {
LNode* p=head;
item=head->data;
head=head->next;
delete p;
return true;
}
//删除表尾结点
else if(mark<0) {
LNode *cp=head, *ap=NULL;
while(cp->next!=NULL) {
ap=cp; cp=cp->next;
}
if(ap==NULL) head=NULL;
else ap->next=cp->next; 
item=cp->data;
delete cp;
return true;
}
//删除值为item结点
else {
LNode *cp=head, *ap=NULL;
while(cp!=NULL)
if(cp->data==item) break;
else {ap=cp; cp=cp->next;}
if(cp==NULL) return false;
else {
if(ap==NULL) head=head->next;
else ap->next=cp->next;
item=cp->data;
delete cp;
return true;
}
}
}

//对单链表进行有序输出
void LinkList::OrderOutputList(int mark)
{
if(head==NULL) {cout<<"链表为空!"<<endl; return;}
//建立新的单链有序表的表头结点
LinkList x;
x.head=new LNode; //x.head为新建有序表的表头指针
x.head->data=head->data; x.head->next=NULL;
//根据head单链表生成x.head单链有序表
for(LNode* p=head->next; p; p=p->next) {
LNode* q=new LNode;
q->data=p->data;
LNode *cp=x.head, *ap=NULL;
//为向x单链表插入q结点而顺序查找合适位置
while(cp) {
if(mark==1) {
if(q->data<cp->data) break;
else {ap=cp; cp=cp->next;}
}
else {
if(cp->data<q->data) break;
else {ap=cp; cp=cp->next;}
}
}
//把q结点插入h有序单链表中
if(ap==NULL) {q->next=x.head; x.head=q;}
else {
q->next=cp; ap->next=q;
}
}
//遍历x有序单链表
x.TraverseList(); 
}

//主文件linkmain3.cpp

#include<iomanip.h>
#include"linklist3.h"

void main()
{
LinkList a;
int i;
ElemType x;
//依次向单链表a表尾插入5个整数结点
cout<<"从键盘输入5个整数:";
for(i=0; i<5; i++) {
cin>>x;
a.InsertList(x,-1);
}
//依次向单链表a表头插入2个整数结点
cout<<"从键盘输入2个整数";
cin>>x; a.InsertList(x,1);
cin>>x; a.InsertList(x,1);
//按不同次序遍历输出单链表a
a.TraverseList();
a.OrderOutputList(1);
a.OrderOutputList(0);
//从单链表a中查找一个给定的整数
cout<<"从键盘上输入一个待查整数:";
cin>>x;
if(a.FindList(x)) cout<<x<<" 查找成功!"<<endl;
else cout<<"查找失败!"<<endl;
//把单链表a中的所有元素依次有序插入到一个新单链表b中
LinkList b;
int k=a.ListSize();
for(i=1; i<=k; i++) 
b.InsertList(a.GetElem(i),0);
//输出单链表b
b.TraverseList();
//从单链表a中分别删除表头、表尾、给定值结点
if(a.DeleteList(x,1)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
if(a.DeleteList(x,-1)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
cout<<"从键盘上输入一个待删除的整数:";
cin>>x;
if(a.DeleteList(x,0)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
//输出单链表a
a.TraverseList();
}