您所在位置：主题：请高手帮忙 单链表操作的分析和流程图怎么写 谢谢
geniusshadow
[专家分：0] 发布于 2006-10-24 20:31:00
单链表操作算法
下面三个程序都是用来实现单链表的定义和操作，每个程序均由头文件、实现文件和主文件。第一个程序中的单链表结点为结构类型，结点的值为整型；第二个程序中的单链表结点同样为结构类型，结点的值为student结构类型；第三个程序中的单链表采用类的定义，操作函数为类中的成员函数，单链表中每个结点的值为整型。
程序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();
}
下面三个程序都是用来实现单链表的定义和操作，每个程序均由头文件、实现文件和主文件。第一个程序中的单链表结点为结构类型，结点的值为整型；第二个程序中的单链表结点同样为结构类型，结点的值为student结构类型；第三个程序中的单链表采用类的定义，操作函数为类中的成员函数，单链表中每个结点的值为整型。
程序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();
}