以下是本人学习中写的一个简单的链表和棧以及队列的实现,由于时间问题没有注释,但命名都很直观.
#include <iostream>
using namespace std;
#include <string>
typedef double T;
/*
单向链表类
*/
class List
{
struct Node
{
T data;
Node* next;
Node(const T& t=T()):data(t),next(NULL){}
};
Node* head;
public :
List():head(NULL){}
void clear()
{
while(head!=NULL)
{
Node* q=head->next;
delete head;
head=q;
}
}
~List()
{
clear();
}
void insert_front(const T& t)
{
Node* p=new Node(t);
p->next=head;
head=p;
}
void insert_back(const T& t)
{
Node* p=new Node(t);
Node* q=head;
if(head==NULL)
head=p;
else{
while(q->next!=NULL)
q=q->next;
q->next=p;
}
}
void travel()
{
Node* p=head;
while(p!=NULL)
{
cout<<p->data<<' ';
p=p->next;
}
cout<<endl;
}
int size()
{
int cnt=0;
Node* p=head;
while(p!=NULL)
{
cnt++;
p=p->next;
}
return cnt;
}
T getHead()
{
if(head==NULL)
throw "no head !";
return head->data;
}
T getTail()
{
if(head==NULL) throw "no tail !";
Node* p=head;
while(p->next!=NULL)
{
p=p->next;
}
return p->data;
}
bool empty()
{
return head==NULL;
}
int find(const T& t)
{
Node* p=head;
int pos=0;
while(p!=NULL)
{
if(p->data==t)
return pos;
p=p->next;
pos++;
}
return -1;
}
bool update(const T& o,const T& n)
{
int pos=find(0);
if(pos==-1)
return false;
Node* p=getPointer(pos);
p->data=n;
return true;
}
private :
Node* getPointer(int pos)
{
Node* p=head;
for(int i=0;i<pos;i++)
{
p=p->next;
}
return p;
}
public :
bool erase(const T& t)
{
int pos=find(t);
if(pos==-1)
return false;
if(pos==0)
{
Node* q=head->next;
delete head;
head=q;
}else{
Node* pre=getPointer(pos-1);
Node* cur=pre->next;
pre->next=cur->next;
delete cur;
}
return true;
}
};
/*
栈类
*/
class Stack
{
List l;
public :
void push(const T& t)
{
l.insert_front(t);
}
void pop()
{
l.erase(l.getHead());
}
T top()
{
return l.getHead();
}
bool empty()
{
return l.empty();
}
int size()
{
return l.size();
}
void clear()
{
l.clear();
}
};
/*
队列类
*/
class Queue
{
List l;
public :
void push(const T& t)
{
l.insert_back(t);
}
void pop()
{
l.erase(l.getHead());
}
T front()
{
return l.getHead();
}
T back()
{
return l.getTail();
}
bool empty()
{
return l.empty();
}
int size()
{
return l.size();
}
void clear()
{
l.clear();
}
};
void main()
{
//自己的测试代码
}
很多不足之处正在慢慢探索学习中。
分享到:
相关推荐
假定一个单向循环链表来表示队列
顺序表、链表、栈、队列、树、Hashmap等数据结构;排序、二分法查找、树遍历等常见算法实现...单向链表 双向链表 单向循环链表 栈 队列 FIFO队列 LIFO队列 优先队列(Priority Queue) 双端队列(double-ended queue)
假定一个单向循环链表来表示队列(即循环链队),该队列只设一个队尾指针,不设队首指针,试编写下列各种运算的算法: 1) 向循环链队插入一个元素值为x的结点。 2) 从循环链队中删除一个结点。 3) 访问队列
主要介绍了Python单向链表和双向链表原理与用法,结合实例形式详细分析了单向链表与双向链表的概念、原理以及创建、添加、删除等相关操作技巧,需要的朋友可以参考下
单向链表的数据结构及其相关算法:单向链表结构包含两个要素,即头结点head和链表大小size,具体操作包括: 链表的增删 链表是否为空 链表的大小 链表的打印输出 删除链表重复节点 链表倒数第K个元素 链表的反转 ...
C语言 表、栈和队列详解 表ADT 形如A1,A2,A3…An的表,这个表的大小为n,而大小为0的表称为空表,非空表中,Ai+1后继Ai,Ai-1前驱Ai,表ADT的相关操有PrintList打印表中的元素;CreateEmpty创建一个空表;Find...
二、 实验要求 1、 定义栈的存储结构。 2、 编写程序实现双向栈的基本操作:1)初始化;2)判断栈是否为空;3)判断栈是否已满;4)入栈;5)出栈;...4、 程序运行界面良好,使用菜单实现每个基本操作。
假定一个单向循环链表来表示队列(即循环链队),该队列只设一个队尾指针rear,不设队首指针,试编写下列各种运算的算法: 向循环链队插入一个元素值为x的结点; 从循环链队中删除一个结点; 输出队列中所有元素;
4-09 单向循环链表遍历和求长度 4-10 单向循环链表添加元素 4-11 单向循环链表删除元素 4-12 单向循环链表删除元素复习及链表扩展 4-13 双向链表及添加元素 4-14 双向链表删除元素 五、排序与搜索 5-01 排序...
C实现一个链表类【代码】,作者 tr0217 (尧思齐 齐尧),是一个通用的C链接表,可以在TC2.0、vc6.0和gcc5.4.3中编译成功,释放链表所占用的资源,在链表使用结束后必须调用,本链表为单向链表,非常有效。...
5、编写在非递减有序链表中插入一个元素使链表元素仍有序的函数,并利用该函数建立一个非递减有序单向链表。 6、利用算法5建立两个非递减有序单向链表,然后合并成一个非递增链表。 7、利用算法5建立两个非递减有序...
java 算法:包括数组,哈希表,队列,栈,链表(双端,单向,双向),二叉树(普通二叉树,哈夫曼树,二叉查找树,平衡二叉树,二叉线索树),图这些数据结构的实现以及多种排序算法和其他一些算法的实现(递归,二...
队列和堆栈都是使用单向链表实现的。 安装 像安装任何其他软件包一样安装: go get github.com/fabioberger/data-structures 将要使用的数据结构添加到项目的导入中: import "github....
//链表节点类型 //不安全的遍历 #define list_for_each(head, pos) for(pos=head->next; pos!=head; pos=pos->next) //安全的遍历 #define list_for_each_safe(head, pos, n) for(pos=head->next, n=pos->next; ...
单向链表 双向链表 循环链表 静态链表 栈(Stack) 队列(Queue) 双端队列(Deque) 循环队列 哈希表(HashTable) 树形数据结构 二叉树(BinaryTree)、二叉搜索树(BinarySearchTree、BST) 平衡二叉搜索树...
介绍链表以及使用示例。链表是一种线性数据结构,由一系列节点组成,每个节点包含数据域和指向下一个节点的指针域。这种结构允许动态地插入...链表常用于实现队列、栈等高级数据结构,适用于需要频繁插入和删除的场景。
7、线性表中的每个结点最多只有一个前驱和一个后继。( ) 8、线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存储。( ) 9、栈和队列逻辑上都是线性表。( ) 10、单链表从任何一个结点...
1.把数据存储到计算机中,...设有一个头指针为head的单向链表,p指向表中某一个结点,且有p->next= =NULL,通过操作p->next=head ,就可使该单向链表构造成单向循环链表。 8.循环队列的最大存储空间为MaxSize,队头指针