链表的存储及操作

  • a1_244305
    了解作者
  • 885.1KB
    文件大小
  • rar
    文件格式
  • 0
    收藏次数
  • VIP专享
    资源类型
  • 0
    下载次数
  • 2022-04-07 08:01
    上传日期
是对链表的实现及操作,可以在作业中用到并且对链表存储有更深的了解
链表.rar
  • 链表
  • Debug
  • vc60.pdb
    108KB
  • List.obj
    269KB
  • vc60.idb
    73KB
  • List.exe
    540.1KB
  • List.pch
    1.9MB
  • List.ilk
    775.7KB
  • List.pdb
    1MB
  • List.cpp
    7.2KB
  • List.dsp
    3.3KB
  • List.plg
    1.1KB
  • List.dsw
    533B
  • List.opt
    47.5KB
  • List.ncb
    41KB
内容介绍
#include<iostream> using namespace std; #include<stdlib.h> const int endData=0; class List;//向前引用,先申明List //定义链表节点类 class LinkNode{ friend class List;//申明List类为友元类 public: int data;//数据元素域 LinkNode * link;//链指针域 LinkNode(LinkNode * ptr=NULL){link=ptr;}//构造函数 LinkNode(int item,LinkNode * ptr=NULL){//构造函数 data = item;link = ptr; } ~LinkNode(){}; }; //List类定义 class List{ private: LinkNode * first;//链表头指针 public: List(){first = new LinkNode();}//带头节点构造函数 List(const int &x){first = new LinkNode(x);}//不带头节点构造函数 ~List(){makeEmpty();delete first;}//析构函数 void makeEmpty();//置空链表 int Length()const;//求链表的长度 LinkNode * getHead(){return first;}//返回头节点 LinkNode * Find(int x);//寻找数据x在节点的位置 LinkNode * Locate(int i);//搜索第i个元素的地址 int getData(int i);//返回i位的数据 void setData(int i,int &x);//设置第i位的值为x bool inSert(int i,int &x);//将数据x插入第i个节点 bool remove(int i,int &x);//删除第i个节点的数据x bool isEmpty()const{return first->link==NULL?true:false;}//判断链表是否为空 bool isFull()const{return false;}//判断表满否?不满返回false void inPut();//输入数据 void outPut();//输出数据 }; //定义链表置空函数 void List::makeEmpty(){ LinkNode * p;//再申明一个节点p while(first->link != NULL){ //逐个后移,一个一个删除 p = first->link; first->link = p->link;} delete p;//删除节点 }; //定义求链表长度函数,附加头节点 int List::Length()const{ LinkNode * p = first->link; int count = 1; while(p->link!=NULL)//寻找链尾,并计数 {p=p->link;count++;} return count; } //定义搜索函数Find LinkNode * List::Find(int x){ LinkNode *p=first->link; while(p!=NULL) if(p->data==x) break;//寻链找含x的节点 else p=p->link; return p; } //定义定位函数Locate LinkNode *List::Locate(int i){ //定位函数,返回第i个元素的地址 if(i<0)return NULL;//i不合理 LinkNode *p=first; int k=0; while(p!=NULL&&k<i)//寻找第i个节点 {p=p->link;k++;} return p; } //定义获取数据函数getData int List::getData(int i){ //取出链表中第i个元素 if(i<0)return NULL; LinkNode *p=Locate(i);//先定位第i个元素 if(p==NULL)return NULL; else return p->data;//返回第i个元素的值 } //定义设置值函数setData void List::setData(int i,int &x){ //给链表中第i个元素赋值 if(i<0)return; LinkNode * p=Locate(i);//p指向第i个节点 if(p==NULL)return; else p->data=x;//替换值 } //定义插入函数 bool List::inSert(int i,int &x){ LinkNode *p=Locate(i-1);//插在第i个节点之前 if(p==NULL)return false;//插入不成功 LinkNode *newNode=new LinkNode(x); if(newNode==NULL){cerr<<"存储分配错误!"<<endl;exit(1);} newNode->link=p->link;//链接在p之前 p->link=newNode; return true;//插入成功 } //定义删除函数 bool List::remove(int i,int &x){ //删除第i个节点 LinkNode *p=Locate(i-1); if(p==NULL||p->link==NULL)return false;//删除不成功 LinkNode *newNode=p->link; p->link=newNode->link; x=newNode->data;//取出被删除节点的数据值 delete newNode; return true;//删除成功 } //定义输入函数 void List::inPut(){ LinkNode *p; int x; first=new LinkNode();//first指向头指针 if(first==NULL){//内存分配错误 cerr<<"存储分配错误!"<<endl; exit(1); } cout<<"输入整型数据,以0号键结束"<<endl; cin>>x; while(x!=endData){//循环输入 p=new LinkNode(x); if(p==NULL){ cerr<<"存储分配错误!"<<endl; } p->link=first->link; first->link=p; cin>>x; } } //定义输出函数 void List::outPut(){ LinkNode *p=first->link; while(p!=NULL){ cout<<p->data<<endl; p=p->link; } } //定义集合的并 void Union(List *L1,List *L2){ //定义节点存放L2的头结点地址 LinkNode *p2; p2=L2->getHead();//p2指向L2的头结点 int n=L1->Length(); while(p2!=NULL){ p2=p2->link; if(p2==NULL)//如果为空,退出循环 break; if(L1->Find(p2->data)==NULL)//在L1中寻找P2的数据 L1->inSert(1,p2->data);//如果没找到在L1首节点处插入数据 } cout<<"合并后数据为:"<<endl; L1->outPut();//输出合并后的链表数据 } //定义集合的交 void Intersection(List *L1,List *L2){ LinkNode *p1; List *L3=new List();//定义一个L3存放交集的链表 int x; p1=L1->getHead();//p1指向L1的头结点 p1=p1->link;//p1指向L1首节点 while(p1!=NULL){ x=p1->data;//保存p1的数据 if(L2->Find(x)!=NULL){//在L2中寻找p1的数据 L3->inSert(1,x);//将一样的数据放到L3中 } p1=p1->link; } cout<<"交集后数据为:"<<endl; L3->outPut();//输出合并后的链表数据 } //定义两个有序链表的合并 void MergeList(List *L1,List *L2){ LinkNode *p1,*p2;//定义两个新结点,分别指向L1,L2 List *L3=new List();//定义一个存放合并后的链表 int k=1;//定义在L3中插入数据的位置 p1=L1->getHead();p1=p1->link;//p1,p2指向首结点 p2=L2->getHead();p2=p2->link; if(p1->data<=p2->data) {L3->inSert(k,p1->data);k++;p1=p1->link;} else {L3->inSert(k,p2->data);k++;p2=p2->link;} while(p1!=NULL){L3->inSert(k++,p1->data);p1=p1->link;} while(p2!=NULL){L3->inSert(k++,p2->data);p2=p2->link;} cout<<"排序后为:"<<endl; L3->outPut(); } //定义主函数 int main(){ List *L1=new List();//创建对象L1 List *L2=new List();//创建对象L2 while(true){ cout<<"选项:"<<endl;//界面 cout<<"1.数据插入"<<endl; cout<<"2.数据删除"<<endl; cout<<"3.数据查找"<<endl; cout<<"4.两个链表的并"<<endl; cout<<"5.两个链表的交"<<endl; cout<<"6.两个非降序链表合并"<<endl; cout<<"输入你的选择:"<<endl; int n;//定义选项n cin>>n; switch(n) { case 1:{ L1->inPut();//输入 cout<<"输入L1数据为:"<<endl; L1->outPut();//输出比较 cout<<"输入要插入的位置和数据:"<<endl;//插入数据 int i,x1; cin>>i>>x1; cout<<"第"<<i<<"个插入"<<x1<<endl; L1->inSert(i,x1); cout<<"插入后数据为:"<<endl; L1->outPut(); break; } case 2:{ L1->inPut();//输入 cout<<"输入L1数据为:"<<endl; L1->outPut();//输出比较 cout<<"输入要删除的位置和数据:"<<endl;//删除数据 int j,r; cin>>j>>r; L1->remove(j,r); cout<<"删除后数据为:"<<endl; L1->outPut(); break; } case 3:{ L1->inPut();//输入 cout<<"输入L1数据为:"<<endl; L1->outPut();//输出比较 cout<<"输入要查找的数据:"<<endl;//查找数据 int f; cin>>f; if(L1->Find(f)!=NULL) {cout<<"地址为:"<<L1->Find(f)<<endl;} else cout<<"查找的数据不存在"<<endl; break; } case 4:{ cout<<"输入两个集合:"<<endl;//输入两个集合 cout<<"输入L1数据为:"<<endl; L1->inPut(); cout<<"输入L2数据为:"<<endl; L2->inPut(); Union(L1,L2);//求两个集合的并集 break; } case 5:{ cout<<"输入两个集合:"<<endl;//输入两个集合 cout<<"输入L1数据为:"<<endl; L1->inPut(); cout<<"输入L2数据为:"<<endl; L2->inPut(); Intersection(L1,L2);//求两个集合的交集 break; } case 6:{ cout<<"输入两个非降序集合:"<<endl;//输入两个集合 cout<<"输入L1数据为:"<<endl; L1->inPut(); cout<<"输入L2数据为:"<<endl; L1->outPut(); //求两个非降序集合的并集,并排序 L2->inPut();//输入 L2->outPut();//输出比较 MergeList(L1,L2); break; } default: cout<<"输入选项不正确:"<<endl; } } return 0; }
评论
    相关推荐