单链表操作算法.txt

单链表的一些简单算法。

        单链表操作算法 
 
下面三个程序都是用来实现单链表的定义和操作，每个程序均由头文件、实现文件和主文件。第一个程序中的单链表结点为结构类型，结点的值为整型；第二个程序中的单链表结点同样为结构类型，结点的值为student结构类型；第三个程序中的单链表采用类的定义，操作函数为类中的成员函数，单链表中每个结点的值为整型。
程序1:
//头文件linklist1.h

//定义ElemType为int
typedef int ElemType;

//单链表中结点的类型
struct LNode {
ElemType data; //值域
LNode* next; //指针域
};

//初始化单链表
void InitList(LNode*& HL);
//清空单链表
void ClearList(LNode*& HL);
//求单链表长度
int ListSize(LNode* HL); 
//检查单链表是否为空
bool ListEmpty(LNode* HL);
//返回单链表中指定序号的结点值
ElemType GetElem(LNode* HL, int pos);
//遍历单链表
void TraverseList(LNode* HL);
//从单链表中查找元素
bool FindList(LNode* HL, ElemType& item);
//更新单链表中的给定元素
bool UpdateList(LNode* HL, const ElemType& item);
//向单链表插入元素
void InsertList(LNode*& HL, const ElemType& item, int mark);
//从单链表中删除元素
bool DeleteList(LNode*& HL, ElemType& item, int mark);
//对单链表进行有序输出
void OrderOutputList(LNode* HL, int mark);

//实现文件linklist1.cpp

#include<iostream.h>
#include<stdlib.h>
#include"linklist1.h"

//初始化单链表
void InitList(LNode*& HL)
{
HL=NULL; 
}

//清空单链表
void ClearList(LNode*& HL)
{
LNode *cp, *np; 
cp=HL; 
while(cp!=NULL) 
{
np=cp->next; 
delete cp; 
cp=np; 
}
HL=NULL; 
}

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

//检查线性表是否为空
bool ListEmpty(LNode* HL)
{
return (HL==NULL);
}

//返回单链表中指定序号的结点值
ElemType GetElem(LNode* HL, int pos)
{
if(pos<1) {
cerr<<"pos is out range!"<<endl;
exit(1);
}
LNode* p=HL;
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 TraverseList(LNode* HL)
{
LNode* p=HL;
while(p!=NULL) {
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

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

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

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

//主文件linkmain1.cpp

#include<iomanip.h>
#include"linklist1.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中的所有元素依次有序插入到一个新单链表b中
LNode* b;
InitList(b);
for(LNode* p=a; p; p=p->next)
InsertList(b, p->data, 0);
//输出单链表b
TraverseList(b);
//从单链表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;
if(DeleteList(a,x,0)) cout<<"Delete success!"<<endl;
else cout<<"Delete fail!"<<endl;
//输出单链表a
TraverseList(a);
}

程序2:
//头文件linklist2.h

//定义学生记录
struct student { 
char name[10]; //姓名
short grade; //分数
};

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

//单链表中结点的类型
struct LNode {
ElemType data; //值域
LNode* next; //指针域
};

//初始化单链表
void InitList(LNode*& HL);
//清空单链表
void ClearList(LNode*& HL);
//求单链表长度
int ListSize(LNode* HL); 
//检查单链表是否为空
bool ListEmpty(LNode* HL);
//返回单链表中指定序号的结点值
ElemType GetElem(LNode* HL, int pos);
//遍历单链表
void TraverseList(LNode* HL);
//从单链表中查找元素
bool FindList(LNode* HL, ElemType& item);
//更新单链表中的给定元素
bool UpdateList(LNode* HL, const ElemType& item);
//向单链表插入元素
void InsertList(LNode*& HL, const ElemType& item, int mark);
//从单链表中删除元素
bool DeleteList(LNode*& HL, ElemType& item, int mark);
//对单链表进行有序输出
void OrderOutputList(LNode* HL, int mark);
//比较两个元素是否相等
bool operator==(const ElemType& r1, const ElemType& r2);
//比较两个元素的大小
bool operator<(const ElemType& r1, const ElemType& r2);
//输出一个元素
ostream& operator<<(ostream& ostr, const ElemType& r);
//输入一个元素
istream& operator>>(istream& istr, ElemType& r);

//实现文件linklist2.cpp

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

#include"linklist2.h"

//初始化单链表
void InitList(LNode*& HL)
{
HL=NULL; 
}

//清空单链表
void ClearList(LNode*& HL)
{
LNode *cp, *np; 
cp=HL; 
while(cp!=NULL) 
{
np=cp->next; 
delete cp; 
cp=np; 
}
HL=NULL; 
}

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

//检查单链表是否为空
bool ListEmpty(LNode* HL)
{
return (HL==NULL);
}

//返回单链表中指定序号的结点值
ElemType GetElem(LNode* HL, int pos)
{
if(pos<1) {
cerr<<"pos is out range!"<<endl;
exit(1);
}
LNode* p=HL;
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 TraverseList(LNode* HL)
{
LNode* p=HL;
while(p!=NULL) {
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}

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

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

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