#pragma once
/**
*原理很简单,将数组的元素看成是链表,或者说是数组空间起到了内存池的作用。然后用两个结点表示
*当前使用/空闲的链表
*
*对效率问题上的一些说明
*增:这个无需说,链表直接秒杀。
*删:类里提供的是一个ELEMENT结构,里面包含了用户的数据。如果你想保持常量的效率
*在一些数据接口提供是,也必须用ELEMENT,这样才能记住结点信息。否则你可以单开个你自己数据类型的接口
*但是在删除时,就必须遍历(删除方法见提供的实例)
*ELEMENT类型的快速使用:typedef CListWithArray<int,1000>::ELEMENT CListWithArray_t;
*你维护好CListWithArray_t就行
*提供以下接口
* bool Add(llist_t* e); //返回一个表示是否插入成功的标志。
* llist_t* Erase(); //取的结点的下一个元素,并且原链表中删除
* 将next提供给使用者,无需太多的其他接口,可以满足大部分要求
**/
namespace list_with_array
{
template<typename llist_t, int llist_size=100>
class CListWithArray
{
//variable
public:
struct ELEMENT
{
llist_t element;
ELEMENT* pPre;
ELEMENT* pNext;
};
private:
ELEMENT elementData[llist_size];//数组空间
ELEMENT freeElement; //空余的指针链头
ELEMENT useElement; //当前使用的指针链头
//function
public:
CListWithArray();
bool Add(const llist_t e);
ELEMENT* Erase(ELEMENT *p)
{
return ReleaseElement(p);
}
ELEMENT* GetListHead()
{
return useElement.pNext;
}
/**
*信息的一些监控
**/
int GetSumUseElement()
{
int sum=0;
ELEMENT* p;
for(p=useElement.pNext; p!=NULL; p=p->pNext)
{
++sum;
}
return sum;
}
int GetSumFreeElement()
{
int sum=0;
ELEMENT* p;
for(p=freeElement.pNext; p!=NULL; p=p->pNext)
{
++sum;
}
return sum;
}
private:
/**
*初始链表串,双指针链表
**/
void InitList();
ELEMENT* MallocElement();
ELEMENT* ReleaseElement(ELEMENT *p);
/**
*将一个结点加入到目的链表
**/
void AddNodeToList(ELEMENT* const pNode, ELEMENT* const pDesList)
{
//处理好结点头尾
pNode->pNext = pDesList->pNext;
pNode->pPre = pDesList;
//判断是否已经有元素,以便前置变量的赋值
if( NULL!=pDesList->pNext )
{
pDesList->pNext->pPre = pNode;
}
pDesList->pNext = pNode;
}
};
/**
*这里是大函数体定义
**/
template <typename llist_t, int llist_size>
CListWithArray<llist_t, llist_size>::CListWithArray()
{
InitList();
}
template <typename llist_t, int llist_size>
void CListWithArray<llist_t, llist_size>::InitList()
{
//开始串指针
for(int i=0; i<llist_size-1; ++i)
{
elementData[i].pNext = &elementData[i+1];
}
elementData[llist_size-1].pNext = NULL;
useElement.pNext = NULL;
freeElement.pNext = &elementData[0];
}
template <typename llist_t, int llist_size>
typename CListWithArray<llist_t, llist_size>::ELEMENT* CListWithArray<llist_t, llist_size>::MallocElement()
{
//判断是否有空余元素
if( NULL==freeElement.pNext )
{
return NULL;
}
//从Free链中脱出,头部
ELEMENT* p = freeElement.pNext;
freeElement.pNext = freeElement.pNext->pNext;
//空运的状态
p->pPre = NULL;
p->pNext = NULL;
AddNodeToList(p, &useElement);
return p;
}
template <typename llist_t, int llist_size>
typename CListWithArray<llist_t, llist_size>::ELEMENT* CListWithArray<llist_t, llist_size>::ReleaseElement( ELEMENT *p)
{
ELEMENT *pResult = p->pNext;
//从Use链中脱离
p->pPre->pNext = p->pNext;
//判断是否是尾元素
if( NULL!=p->pNext )
{
p->pNext->pPre = p->pPre;
}
//空运状态
p->pPre = NULL;
p->pNext = NULL;
AddNodeToList(p, &freeElement);
return pResult;
}
template <typename llist_t, int llist_size>
bool CListWithArray<llist_t, llist_size>::Add(const llist_t e)
{
//先从Free指针里取得一个空节点
ELEMENT *p = MallocElement();
if( NULL==p )
{
return false;
}
else
{
p->element = e;
return true;
}
}
};
/*
使用方法
#include "CListWithArray.h"
using namespace std;
using namespace list_with_array;
CListWithArray<int,1000> listTest;
typedef CListWithArray<int,1000>::ELEMENT CListWithArray_t;
void cout_listinfo()
{
cout<<"sum use:"<<listTest.GetSumUseElement()<<endl;
cout<<"sum free:"<<listTest.GetSumFreeElement()<<endl;
cout<<"-------------------"<<endl;
}
void test_del_1()
{
CListWithArray_t *p=listTest.GetListHead();
while( NULL!=p )
{
if( ((p->element)&0x1) == 0 ) //删掉奇数
{
p = listTest.Erase(p); //注意,这里p的信息已经被修改,无需再p->pNext;
continue;
}
p=p->pNext;
}
}
void test_del_2()
{
CListWithArray_t *p=listTest.GetListHead();
while( NULL!=p )
{
if( 1000==p->element || 2000==p->element )
{
p = listTest.Erase(p);
continue;
}
p=p->pNext;
}
}
void test_add_1()
{
for(int i=0; i<1100; ++i)
{
listTest.Add(i);
}
}
void test_add_2()
{
for(int i=0; i<3; ++i)
{
listTest.Add(i*1000);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
cout_listinfo(); //链表最早状态
test_add_1(); //加满链表
cout_listinfo();
test_del_1(); //删除奇数
cout_listinfo();
test_add_2(); //压入个特殊数,0,1000,2000
cout_listinfo();
test_del_2(); //删除1000,2000
cout_listinfo();
return 0;
}
*/
分享到:
相关推荐
C++数据结构——链表,适合初学者,使用数组模拟链表。
纯手写 java 数组模拟链表约瑟夫环问题 有很大更改空间 仅供参考
Java基础-模拟HashMap集合(基于数组和链表) 数组和链表.pdf
练习题-数组双向链表 练习题-数组双向链表. 适用于初学者练习
有些语言不提供指针与对象数据类型,以下代码通过多重数组实现链表结构及其基本操作。 用一个数组空间模拟分配堆。用一个头指针为free的链表来管理自由空间。用栈得push和pop操作来实现释放和分配空间。 三个数组...
自己写的一个小项目。用数组模拟实现java的数据结构,性能还行。和源码思路比较接近。可以看看,有助于初学者了解数据结构与算法。
用java写的一个中国象棋,一定能执行,还有对应的文档,完美完成了课程设计。包含的功能:人人对弈,悔棋操作(用数组模拟链表实现的),重新开始。
【数据结构课程设计】 数组 实现一个支持动态扩容的数组 ... 用链表实现一个链式栈 编程模拟实现一个浏览器的前进、后退功能 队列 用数组实现一个顺序队列 用链表实现一个链式队列 实现一个循环队列 ......
双向的循环链表的C++源代码 实现正逆序遍历,链表归并,插入,删除,查询等基本操作
## 栈* 用数组实现一个顺序栈* 用链表实现一个链式栈* 编程模拟实现一个浏览器的前进、后退功能 ## 队列* 用数组实现一个顺序队列* 用链表实现一个链式队列* 实现一个循环队列 ## 递归* 编程实现斐波那契数列求值f(n...
该程序完成了模拟红四的发牌过程,并对每个用户手里的牌进行了排序 对每个用户手里的牌是以该牌的点数为排序基准的 为防止牌的重复,设置了一个boolean类型的数组,记录某个牌是否已被发出,若被发出,则重新进行选牌,若...
//构造双向链表,实现从控制台输入,插入,删除,求大小size等操作#include “stdafx.h”#include <iostream>using namespace std;//定义双向链表的节点template<class>struct NODE{ NODE* pre; T data; NODE* ...
(2)多个闹铃可用数组或链表存储。 2.3 其他要求 (1)变量、函数命名符合规范。 (2)注释详细:每个变量都要求有注释说明用途;函数有注释说明功能,对参数、返回值也要以注释的形式说明用途;关键的语句段要求有...
文章目录队列队列介绍数组模拟队列思路代码实现问题分析并优化代码代码实现环形队列 队列 队列介绍 对应是一个有序列表,可以用数组或是链表来实现 遵循先入先出的原则,即:先存入队列的数据,要先取出,后存入的要...
出圈问题分别用模拟指针、数组、链表解决
对基本数据结构的模拟,实现arrayList,hashMap,树,队列,栈的基本方法,对于学习数据结构有一定的帮助 LinkedList[] arr = new LinkedList[999]; // 键值对集合! Map底层结构是:数组 + 链表 int size = 0; // ...
第二,大家在很多书上看到的是使用单链表实现队列,我这里将会使用带头结点尾结点的非循环双链表实现,虽然多维护了两个节点和指针域,但是在链表头尾进行插入删除的时候不需要遍历链表了,队列操作变得非常
用链表实现一个链式栈 编程模拟实现一个浏览器的前进、后退功能 2、队列 用数组实现一个顺序队列 用链表实现一个链式队列 实现一个循环队列 3、递归 编程实现斐波那契数列求值f(n)=f(n-1)+f(n-2) 编程实现求阶乘n! ...
本文给出了哈夫曼编码的另一种实现算法,该算法抛开树结构,用一个数组模拟二叉树的创建过程并得到符号的深度, 然后根据这一信息为每个符号分配编码。对于大型文件来说,整个编码、译码过程中需要的空间比传统哈夫曼...
在百忙之中用了4天时间,用MFC给一个计算机院的朋友编写的,与典型的数据库程序不同,该程序的存储完全以数组和链表形式存储在内存中,仅在必要时将信息保存到磁盘的xml文件中。旅店功能包括预约、个人与集体入住、...