// 单链表.cpp -- 最基本的单链表C++
// Singly-linked list node
template <class Elem> class Link
{
public:
Elem element; // value for this node
Link *next; // pointer to next node in list
Link(const Elem& elemval, Link* nextval = NULL)
{ element = elemval; next = nextval;}
Link (Link* nextval = NULL)
{ next = nextval;}
};
// Linked list implementation
template <class Elem> class LList: public Link<Elem>
{
private:
Link <Elem>* head; // Pointer to list header
Link <Elem>* tail; // Pointer to last Elem in list
Link <Elem>* fence; // Last element on left side
int leftcnt; // Size of left partition
int rightcnt; // Size of right partition
void init() // Intialization routine
{
fence = tail = head = new Link <Elem>;
leftcnt = rightcnt = 0;
}
void removeall() // return nodes to free store
{
while(head != NULL)
{
fence = head;
head = head -> next;
delete fence;
}
}
public:
LList(int size = DefaultListSize) { init();}
~LList() {removeall();} // Destructor
void clear() {removeall(); init();}
bool insert(const Elem&);
bool append(const elem&);
bool remove(Elem&);
void setStart()
{ fence = head; rightcnt += leftcnt; leftcnt = 0; }
void setEnd()
{ fence = tail; leftcnt += rightcnt; rightcnt = 0;}
void prev();
void next();
{
if (fence != tail) // don't move fence if right empty
{
fence = fence -> next;
rightcnt--;
leftcnt++;
}
}
int leftLength()const {return leftcnt;}
int rightLength()const {return rightcnt;}
bool setPos(int pos);
bool getValue(Elem& it) const
{
if {rightLength() == 0) return false;
// 当带了表结头,要先指向下一个元素取值。
// 如果带了表结头后,取值不是还是0,1,2,3...所以就要看具体的功能来写
it = fence -> next -> element;
return true;
}
void print() const;
};
template <class Elem> // Insert at front of right partition
bool LList <Elem>::insert(const Elem& item)
{
fence -> next = new Link <Elem> (item, fence -> next);
if (tail == fence) tail = fence -> next; // new tail
rightcnt++;
return true;
}
template <class Elem> // Append Elem to end of the list
bool LList <Elem>::append(const Elem& item)
{
tail = tail -> next = new Link<Elem>(item, NULL);
rightcnt++;
return true;
}
// Remove and return first Elem in right partition
template <class Elem> bool LList<Elem>::remove(Elem& it)
{
if (fence -> next == NULL) return false; // Empty right
it = fence -> next -> element; // Remember value
Link<Elem>* ltemp = fence -> next; // Remember link node
fence -> next = ltemp -> next; // Remove from list
if (tail == ltemp) tail = fence; // Reset tail
delete ltemp;
rightcnt--;
return true;
}
// Move fence one step left; no change if left is empty
template <class Elem> void LList<Elem>::setPos(int pos)
{
if ((pos < 0) || (pos > rightcnt + leftcnt)) return false;
fence = head;
for (int i = 0; i < pos; i++) fence = fence -> next;
return true;
}
// Set the size of left partition to pos
template <class Elem> bool LList<Elem>::setPos(int pos)
{
if ((pos < 0) || (pos > rightcnt + leftcnt)) return false;
fence = head;
for(int = 0; i < pos; i++) fence = fence -> next;
return true;
}
template <class elem> void LList<Elem>::print() const
{
Link<Elem>* temp = head;
cout << " < ";
while(temp != fence)
{
cout << temp -> next -> element << " ";
temp = temp -> next;
}
cout << " | ";
while(temp -> next != NULL)
{
cout << temp -> next -> element << " ";
temp = temp -> next;
}
cout << ">\n";
}
分享到:
相关推荐
单链表C++代码实现、插入、删除结点等,还有有关单链表的练习作业题
用C++模板方式实现自定义单链表,交流学习用
线性表(单链表 C++语言编写的) 本文将详细介绍线性表的概念、单链表的实现、C++语言的应用及相关知识点。 一、线性表的概念 线性表是数据结构中的一种,指的是元素之间存在着一对一的关系,且每个元素都只有一...
首先,我们来看单链表的基本结构。在C++中,可以定义一个结构体来表示链表的节点,如下: ```cpp struct ListNode { int data; // 节点的数据部分 ListNode* next; // 指向下一个节点的指针 }; ``` 创建单链表...
c++代码实现单链表逆置输出c++代码实现单链表逆置输出c++代码实现单链表逆置输出c++代码实现单链表逆置输出c++代码实现单链表逆置输出c++代码实现单链表逆置输出c++代码实现单链表逆置输出c++代码实现单链表逆置输出...
非循环单链表是一种基本的数据结构,常用于计算机科学中的数据组织和操作。在C++中,我们可以使用对象导向编程的思想来实现非循环单链表。这个实现通常涉及定义一个节点类(Node)来存储数据和指向下一个节点的指针...
总结来说,这段C++代码演示了如何通过迭代方式反转一个单链表。这种算法的时间复杂度是O(n),其中n是链表的长度,因为它只遍历一次链表。空间复杂度为O(1),因为我们仅使用了常数个额外的指针变量。理解这个过程对于...
c++实现的单链表数据结构,供大家学习数据结构与算法使用
c++单链表的基本操作
数据结构上机实验课题之一,要求实现单链表的插入排序等功能。
C++单链表的实现,包含Create(),Print(const node *head),Delete(node *head,int num)等简单的函数
单链表是计算机科学中一种基础的数据结构,它在C++编程中有着广泛的应用。单链表由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。这种数据结构允许动态地添加、删除和修改元素,因为它的...
在C++编程中,单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和指向下一个节点的指针。带头结点的单链表在链表的开始处添加了一个特殊的节点,称为头结点,它的数据部分通常不存储实际...
根据给定的文件信息,我们可以总结出以下关于C++单链表实现的关键知识点: ### 1. 序列列表(SeqList)类定义 #### 类模板定义 ```cpp template class SeqList { // 类成员声明 }; ``` - `template <class T>`:...
本文将详细阐述如何使用C++来实现单链表的基本操作,包括创建、遍历、插入、删除、判断空、计算长度以及查找节点。 首先,我们从创建单链表开始。单链表是由一系列节点组成的数据结构,每个节点包含一个数据元素和...
在C++中实现单链表,我们需要定义一个结构体或类来表示链表节点,并提供相应的操作方法。 首先,我们需要定义链表节点的结构体。节点通常包含两个部分:数据域(存储元素)和指针域(指向下一个节点): ```cpp ...
本主题聚焦于如何使用C++模板实现单链表,并基于此实现多项式的加、减、乘等基本运算。下面将详细介绍这两个知识点。 **1. C++模板** C++模板是一种泛型编程工具,它允许我们编写可以处理不同数据类型的代码。模板...
单链表的基本操作包括: 1. 初始化:创建空链表或带有初始节点的链表。 2. 插入节点:在链表的开头、结尾或特定位置插入新节点。 3. 删除节点:根据给定的值或位置移除节点。 4. 查找节点:在链表中搜索特定值的节点...
在本课程实验中,我们将深入探讨使用C++编程语言实现单链表这一数据结构的相关知识点。单链表是一种常见的线性数据结构,它由一系列节点组成,每个节点包含数据元素和一个指向下一个节点的指针。这个实验的目标是...
1、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ,首先需要在单链表中寻找到第i-1个结点并用指针p指示,然后申请一个由指针s 指示的结点空间,并置x为其数据域值,...