线性表
个人信息:就读于燕大本科软件工程专业 目前大三;
本人博客:google搜索“cqs_2012”即可;
个人爱好:酷爱数据结构和算法,希望将来从事算法工作为人民作出自己的贡献;
博客时间:2014-5-15;
编程语言:C++ ;
编程坏境:Windows 7 专业版 x64;
编程工具:vs2008;
制图工具:office 2010 powerpoint;
硬件信息:7G-3 笔记本;
线性表分为链表和顺序表
链表按有无头结点分为有头结点链表和无头结点链表,按是否循环分为循环链表和非循环链表,按是否双向分为单向链表和双向链表
1。不带头结点非循环单链表
2.带头结点非循环单链表(头结点的值域是没有意义的)
3.不带头结点循环单链表
4.带头结点循环单链表(尾节点的下一个节点指向第一个值域有意义的节点)
5.不带头结点非循环双向链表
6.不带头结点循环双向链表
7.带头结点循环双向链表
8.带头结点非循环双向链表
顺序表(地址是连续的)
代码(前几天大二妹子交C++上机作业,把俺要去年的程序,很抱歉了,C++本是大二写学期的课,俺本想三年毕业的,故先修了大二的一部分课程,包括C++,于是把大一写过的C++上机实验代码给她了,当时来时给的实验成绩100分,现在看看以前自己写过的代码虽然风格和规范不太好,但是实现的功能还是不错的,毕竟当时写了一整天呢,当时一把辛酸累呀,今天共享给大家了,思路还行,循环控制的很好,大家可以自己去试一下我的程序,内容包括 自己构建的 双向链表,栈,队列)
#include<iostream> #include<cmath> #include<string> #include<new> using namespace std; class Node //节点类 { string s; public: Node *front,*next; Node(string n) { s=n; cout<<"已经为节点赋值为"<<n<<endl; } string get() { return s; } void change(string n) { s=n; } }; Node *operator+(Node *n1,Node &n2) // 运算符+的重载函数 { n2.next=n1; n1->front=&n2; n1=&n2; return n1; } Node *operator-(Node *n1,Node &n2) // 运算符-的重载函数 { n1->next=&n2; n2.front=n1; return &n2; } class List //链表类 { public: Node *Listhead,*Listrear; List() { Listhead=NULL; Listrear=NULL; } Node *GetHead(); Node *GetTail(); void RemoveHead(); void RemoveTail(); void AddHead(); void AddHead(int n); void AddTail(); void AddTail(int n); void Removeall(); void GetNext(string s); void GetPre(string s); void GetAt(int n); void SetAt(int n); void InsertBefore(int n); void InsertAfter(int n); void RemoveAt(int n); int Find(string s); void FindIndex(int); void display(); int GetCount(); int IsEmpty(); void Display(); }; class Stack:public List { public: void Push(); string Pop(); int StackEmpty(); void DestroyStack(); }; void Stack::DestroyStack() { Removeall(); cout<<"栈已空"<<endl; } class Queue:public List { public: void EnQueue(); string DeQueue(); int QueueEmpty(); void DestroyQueue(); }; void Queue::DestroyQueue() { Removeall(); cout<<"队列已空"<<endl; } void Queue::EnQueue() { AddTail(); cout<<Listrear->get()<<"进队"<<endl; } string Queue::DeQueue() { string ss;ss=Listhead->get(); cout<<ss<<"出队"<<endl; RemoveHead(); return ss; } int Queue::QueueEmpty() { if(IsEmpty()) { cout<<"队空"<<endl; return 1; } else { cout<<"队不空"<<endl; return 0; } } void Stack::Push() { AddHead(); cout<<Listhead->get()<<"进桟"<<endl; } string Stack::Pop() { string ss;ss=Listhead->get(); cout<<ss<<"出桟"<<endl; RemoveHead(); return ss; } int Stack::StackEmpty() { if(IsEmpty()) { cout<<"栈空"<<endl; return 1; } else { cout<<"栈不空"<<endl; return 0; } } Node *List::GetHead()//返回头指针 { if(Listhead==NULL) { cout<<"链表已空"<<endl; // return NULL; } else return Listhead; } Node *List::GetTail()// 返回尾指针 { if(Listrear==NULL) { cout<<"链表已空"<<endl; // return NULL; } else return Listrear; } void List::RemoveHead()// 删除头结点 { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p,*p2; p=Listhead; if(p->next==NULL) { delete p; cout<<"头节点已经删除"<<endl; Listhead=NULL;Listrear=NULL; } else { Listhead=p->next; p2=p->next; p2->front=NULL; delete p; cout<<"头节点已经删除"<<endl;} } } void List::RemoveTail() // 删除尾节点 { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p; p=Listrear; Listrear=p->front; Listrear->next=NULL; delete p; cout<<"尾节点已经删除"<<endl; } } void List::AddHead()// 增加头结点 { string c; cout<<"请输入这个节点的元素(字符串格式)"<<endl; cin>>c; cout<<endl; Node *p;p=new Node(c); p->front=p->next=NULL; if (Listhead==NULL&&Listrear==NULL) Listhead=Listrear=p; else Listhead=Listhead+(*p); } void List::AddHead(int n)// void AddHead()的重载函数 { int i; for(i=0;i<n;i++) { string c; cout<<"请输入这个节点的元素(字符串格式)"<<endl; cin>>c; cout<<endl; Node *p;p=new Node(c); p->front=p->next=NULL; if (Listhead==NULL) Listhead=Listrear=p; else Listhead=Listhead+(*p); } } void List::AddTail() { string c; cout<<"请输入这个节点的元素(字符串格式)"<<endl; cin>>c; cout<<endl; Node *p;p=new Node(c); p->front=p->next=NULL; if (Listhead==NULL&&Listrear==NULL) Listhead=Listrear=p; else Listrear=Listrear-(*p); } void List::AddTail(int n)// void AddTail()的重载函数 { int i; for(i=0;i<n;i++) { string c; cout<<"请输入这个节点的元素(字符串格式)"<<endl; cin>>c; cout<<endl; Node *p;p=new Node(c); p->front=p->next=NULL; if (Listhead==NULL) Listhead=Listrear=p; else Listrear=Listrear-(*p); } } void List::Removeall() { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead; for(;p1!=NULL;) { p2=p1->next; delete p1; p1=p2; } Listhead=NULL;Listrear=NULL; cout<<"链表全部清空"<<endl; } } void List::GetNext(string s) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead; for(;p1!=NULL;) { p2=p1->next; if(s==p1->get()) if(p2==NULL) { cout<<"下一个元素为空"<<endl; break;} else {cout<<"下一个元素为"<<p2->get()<<endl; break;} else p1=p2; } if(p1==NULL)cout<<"你刚才输入的字符串不存在"<<endl; } } void List::GetPre(string s) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listrear; for(;p1!=NULL;) { p2=p1->front; if(s==p1->get()) if(p2==NULL) { cout<<"前一个元素为空"<<endl; break;} else {cout<<"前一个元素为"<<p2->get()<<endl; break;} else p1=p2; } if(p1==NULL)cout<<"你刚才输入的字符串不存在"<<endl; } } void List::GetAt(int n) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead;int i; for(i=1;i<n;i++) p1=p1->next; cout<<p1->get(); } } void List::SetAt(int n) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead;int i; for(i=1;i<n;i++) p1=p1->next; cout<<"请输入元素"<<endl; string s;cin>>s; p1->change(s); cout<<"插入成功"<<endl; } } void List::InsertBefore(int n) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead;int i; for(i=1;i<n;i++) p1=p1->next; cout<<"请输入元素"<<endl; string s;cin>>s; p2=new Node(s) ; p2->next=p1; p2->front=p1->front; p1->front->next=p2; p1->front=p2; cout<<"插入成功"<<endl; } } void List::InsertAfter(int n) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead;int i; for(i=1;i<n+1;i++) p1=p1->next; cout<<"请输入元素"<<endl; string s;cin>>s; p2=new Node(s) ; p2->next=p1; p2->front=p1->front; p1->front->next=p2; p1->front=p2; cout<<"插入成功"<<endl; } } void List::RemoveAt(int n) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead;int i; for(i=1;i<n;i++) p1=p1->next; p1->front->next=p1->next; p1->next->front=p1->front; cout<<p1->get()<<"已经删除"<<endl; delete p1; } } int List::Find(string s) { if (Listhead==NULL&&Listrear==NULL) {cout<<"链表已空"<<endl;return 0;} else { Node *p1,*p2;p1=Listhead;int i=1; for(;p1!=NULL;i++) { p2=p1->next; if(s==p1->get()) { cout<<"你要查找的元素在链表中的位置是第"<<i<<endl; return 1; } p1=p2; } if (p1==NULL) return 0; } } void List::FindIndex(int n) { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead;int i; for(i=1;i<n;i++) p1=p1->next; cout<<p1->get()<<endl; } } int List::GetCount() { if (Listhead==NULL&&Listrear==NULL) {cout<<"链表已空"<<endl;return 0;} else { Node *p1,*p2;p1=Listhead;int i=0; for(;p1!=NULL;i++) { p2=p1->next; p1=p2; } cout<<"链表总长度为"<<i<<endl;return 1; } } int List::IsEmpty() { if (Listhead==NULL&&Listrear==NULL) {cout<<"链表已空"<<endl;return 1;} else {cout<<"链表不空"<<endl;return 0;} } void List::Display() { if (Listhead==NULL&&Listrear==NULL) cout<<"链表已空"<<endl; else { Node *p1,*p2;p1=Listhead; for(;p1!=NULL;) { p2=p1->next; cout<<p1->get()<<endl; p1=p2; } } } int m() { int m1; cout<<"请输入你想插入头结点的个数"<<endl; cin>>m1; return m1; } string s1() { string s; cout<<"请输入你查找依据的字符串"<<endl; cin>>s; return s; } int Locate1() { int n; cout<<"请输入你要查找的元素在链表中的序号"<<endl; cin>>n; return n; } int Locate2() { int n; cout<<"请输入你要删除的元素在链表中的序号"<<endl; cin>>n; return n; } int Locate3() { int n; cout<<"请输入你要插入的元素在链表中哪个节点前,请输入序号"<<endl; cin>>n; return n; } int Locate4() { int n; cout<<"请输入你要插入的元素在链表中哪个节点后,请输入序号"<<endl; cin>>n; return n; } int Repeat1() { int a; cout<<"如果你想构造一个双向链表,并进行相关操作,请输入1,否则输入0"<<endl; cin>>a; cout<<endl; if(a) { List *L1; L1=new List;string s; cout<<"第一个节点的元素初始化为"<<endl;cin>>s; Node* p=new Node (s); L1->Listhead=L1->Listrear=p;p->front=p->next=NULL; int i=1; while(i) { cout<<"如果你想进行以下操作,请输入其前边的标号"<<endl; cout<<"0.不进行任何操作"<<endl; cout<<"1.得到链表头结点指针"<<endl; cout<<"2.得到链表尾节点指针"<<endl; cout<<"3.删除头结点"<<endl; cout<<"4.删除尾节点"<<endl; cout<<"5.增加头结点"<<endl; cout<<"6.增加n个头结点"<<endl; cout<<"7.增加尾节点"<<endl; cout<<"8.增加n个尾节点"<<endl; cout<<"9.删除所有节点"<<endl; cout<<"10.得到前一个节点的元素 "<<endl; cout<<"11.得到下一个节点的元素"<<endl; cout<<"12.得到一个给定位置的元素"<<endl; cout<<"13.在一个给定的位置插入元素"<<endl; cout<<"14.删除一个给定位置的元素 "<<endl; cout<<"15.在一个给定的位置前插入一个元素"<<endl; cout<<"16.在一个给定的位置后插入一个元素 "<<endl; cout<<"17.在链表中查找你给出的元素的位置"<<endl; cout<<"18.给定位置,输出他的元素"<<endl; cout<<"19.返回这个链表元素的个数"<<endl; cout<<"20.判断这个链表是否为空"<<endl; cout<<"21.输出链表"<<endl; cin>>i; cout<<endl; switch(i) { case 0:break; case 1:cout<<L1->GetHead()<<endl; break; //得到链表头结点指针 case 2:cout<<L1->GetTail()<<endl; break; //得到链表尾节点指针 case 3:L1->RemoveHead();break; //删除头结点 case 4: L1->RemoveTail(); break; //删除尾节点 case 5: L1->AddHead();break; //增加头结点 case 6:L1->AddHead(m());break; //增加N个头结点 case 7: L1->AddTail();break; //增加尾节点 case 8:L1->AddTail(m());break; //增加n个尾节点 case 9:L1->Removeall();break; //删除所有节点 case 10:L1->GetPre(s1());break; //得到前一个节点的元素 case 11:L1->GetNext(s1());break; //得到下一个节点的元素 case 12:L1->GetAt(Locate1()); break; //得到一个给定位置的元素 case 13:L1->SetAt(Locate1()); break; //在一个给定的位置插入元素 case 14:L1->RemoveAt(Locate2());break; //删除一个给定位置的元素 case 15:L1->InsertBefore(Locate3());break; //在一个给定的位置前插入一个元素 case 16:L1->InsertAfter(Locate4()); break; //在一个给定的位置后插入一个元素 case 17:L1->Find(s1()); break; //找到参数元素的位置 case 18:L1->FindIndex(Locate1());break; //给定位置,输出他的元素 case 19:L1->GetCount(); break; //返回这个链表元素的个数 case 20:L1->IsEmpty();break; //判断这个链表是否为空 case 21:L1->Display();break; //输出链表 } cout<<"如果你想继续对这个链表进行操作,请输入1,否则输入0"<<endl; cin>>i; } L1->Removeall(); } int n; cout<<"如果你想继续使用另一个链表,请输入1,否则输入0"<<endl; cin>>n; cout<<endl; if(n)Repeat1(); else return 0; } int Repeat2() { int a; cout<<"如果你想构造一个栈,并进行相关操作,请输入1,否则输入0"<<endl; cin>>a; cout<<endl; if(a) { Stack *S1; S1=new Stack; cout<<"请输入第一个进桟的元素"<<endl; S1->Push(); int i=1; while(i) { cout<<"如果你想进行以下操作,请输入其前边的标号"<<endl; cout<<"0.不进行任何操作"<<endl; cout<<"1.给出元素并进桟"<<endl; cout<<"2.从栈中删除一个元素"<<endl; cout<<"3.判断栈是否为空"<<endl; cout<<"4.清空栈"<<endl; cin>>i; switch(i) { case 0:break; case 1:S1->Push();break; case 2:S1->Pop();break; case 3:S1->StackEmpty();break; case 4:S1->DestroyStack();break; }//switch cout<<"如果你想继续对这个栈进行操作,请输入1,否则输入0"<<endl; cin>>i; }//while S1->DestroyStack(); }//if int n; cout<<"如果你想继续使用另一个栈,请输入1,否则输入0"<<endl; cin>>n; cout<<endl; if(n)Repeat2(); else return 0; } int Repeat3() { int a; cout<<"如果你想构造一个队,并进行相关操作,请输入1,否则输入0"<<endl; cin>>a; cout<<endl; if(a) { Queue *Q1; Q1=new Queue; cout<<"请输入第一个进队的元素"<<endl; Q1->EnQueue(); int i=1; while(i) { cout<<"如果你想进行以下操作,请输入其前边的标号"<<endl; cout<<"0.不进行任何操作"<<endl; cout<<"1.给出元素并进队"<<endl; cout<<"2.从队中删除一个元素"<<endl; cout<<"3.判断队是否为空"<<endl; cout<<"4.清空队"<<endl; cin>>i; switch(i) { case 0:break; case 1:Q1->EnQueue();break; case 2:Q1->DeQueue();break; case 3:Q1->QueueEmpty();break; case 4:Q1->DestroyQueue();break; }//switch cout<<"如果你想继续对这个队进行操作,请输入1,否则输入0"<<endl; cin>>i; }//while Q1->DestroyQueue(); }//if int n; cout<<"如果你想继续使用另一个队,请输入1,否则输入0"<<endl; cin>>n; cout<<endl; if(n)Repeat2(); else return 0; } int main() // 主函数 { int Repeat3(); int Repeat2(); int Repeat1();//声明重复函数 int j=1; while(j) { cout<<"如果你想进行以下操作,请输入其前边的标号"<<endl; cout<<"1.对双向链表进行操作"<<endl; cout<<"2.对栈进行操作"<<endl; cout<<"3.对队列进行操作"<<endl; cin>>j; switch(j) { case 1:Repeat1();break; case 2:Repeat2();break; case 3:Repeat3();break; } cout<<"如果你想继续使用本程序,请输入1,否则输入0"<<endl; cin>>j; } system("pause"); return 0; }
原文:http://blog.csdn.net/cqs_2012/article/details/27955791