线性表
个人信息：就读于燕大本科软件project专业 眼下大三;
本人博客：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;
}
版权声明：本文博主原创文章。博客，未经同意不得转载。