C++实现静态链表
本文实例为大家分享了C++实现静态链表的具体代码，供大家参考，具体内容如下
一、动态链表和静态链表区别：
（1）动态链表：
（2）静态链表： 应用：二叉树
二、思路：
1.结点设置：T data；
int link;
2.链表要用一个avil来保存可分配空间的首地址；
3.初始化：引入头结点：elem[0]；
头结点先指向空NULL， 用-1表示；
avil存储空分配的空间的首地址1；
然后让其它可分配空间的结点的link指向坐标大一的结点；
三、实现程序：
#ifndef StaticList_h
#define StaticList_h
const int maxSize = 100; // 静态链表大小
template <class T>
struct SLinkNode {
T data; // 结点数据
int link; // 结点链接指针
};
template <class T>
class StaticList {
public:
void InitList(); // 初始化
int Length(); // 计算静态链表的长度
int Search(T x); // 在静态链表中查找具有给定值的结点
int Locate(int i); // 在静态链表中查找第i个结点
bool Append(T x); // 在静态链表的表尾追加一个新结点
bool Insert(int i, T x); // 在静态链表第i个结点后插入新结点
bool Remove(int i); // 在静态链表中释放第i个结点
bool isEmpty(); // 判链表空否？
private:
SLinkNode<T> elem[maxSize];
int avil; // 当前可分配空间首地址
};
template <class T>
void StaticList<T>::InitList() {
// 初始化
elem[0].link = -1;
avil = 1;
// 当前可分配空间从1开始建立带表头结点的空链表
for(int i = 1; i < maxSize - 1; i++)
elem[i].link = i + 1; // 构成空闲链接表
elem[maxSize-1].link = -1;
}
template <class T>
int StaticList<T>::Length() {
// 计算静态链表的长度
int p = elem[0].link;
int i = 0;
while(p != -1) {
p = elem[p].link;
i++;
}
return i;
}
template <class T>
int StaticList<T>::Search(T x) {
// 在静态链表中查找具有给定值的结点
int p = elem[0].link; // 指针p指向链表第一个结点
while(p != -1) { // 逐个结点检测查找给定的值
if(elem[p].data == x)
break;
else
p = elem[p].link;
}
return p;
}
template <class T>
int StaticList<T>::Locate(int i) {
// 在静态链表中查找第i个结点
if(i < 0) // 参数不合理
return -1;
if(i == 0)
return 0;
int j = 1, p = elem[0].link;
while(p != -1 && j < i) { // 循链查找第i号结点
p = elem[p].link;
j++;
}
return p;
}
template <class T>
bool StaticList<T>::Append(T x) {
// 在静态链表的表尾追加一个新结点
if(avil == -1) // 没有分配到存储空间
return false;
int q = avil; // 分配结点
avil = elem[avil].link; // 指向下一个可分配的结点
elem[q].data = x;
elem[q].link = -1;
int p = 0;
// 查找表尾
while(elem[p].link != -1)
p = elem[p].link;
elem[p].link = q; // 追加
return true;
}
template <class T>
bool StaticList<T>::Insert(int i, T x) {
// 在静态链表第i个结点后插入新结点
int p = Locate(i);
if(p == -1) // 找不到结点
return false;
int q = avil; // 分配结点
avil = elem[avil].link;
elem[q].data = x;
elem[q].link = elem[p].link; // 链入
elem[p].link = q;
return true;
}
template <class T>
bool StaticList<T>::Remove(int i) {
// 在静态链表中释放第i个结点
int p = Locate(i-1);
if(p == -1) // 找不到结点
return false;
int q = elem[p].link; // 第i号结点
elem[p].link = elem[q].link;
elem[q].link = avil; // 释放,让q的link指向原可分配的结点
avil = q; // avil指向q
return true;
}
template <class T>
bool StaticList<T>::isEmpty() {
// 判链表空否？
if(elem[0].link == -1)
return true;
return false;
}
#endif /* StaticList_h */
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。
相关推荐
-
C++实现单链表的构造
单链表的构造,包括最常用函数,setData(),Insert(),Remove(),getData(),Search(). 代码如下: #include <iostream> #include <stdlib.h> using namespace std; template<class T> struct LinkNode{ T data; LinkNode<T> *link; LinkNode(LinkNode<T> *ptr=NULL){l
-
C++利用链表模板类实现简易队列
本文实例为大家分享了C++利用链表模板类实现一个队列的具体代码,供大家参考,具体内容如下 设计思想:MyQueue.h中对模板类进行声明和实现.首先定义结点的结构体,包含数据和指针域两部分.队列类定义中声明和实现了元素入队,出队,打印队首元素和队列等方法. 注意: 1)模板类的声明和定义不能分开(即不能分别放在.h和.cpp文件里). 2)声明新节点时,如果声明的节点是辅助操作的,可以不用new关键字,例如在析构函数中,直接用:Node<T>* temp:定义即可.如果声明一个新节点加入队列,
-
C++使用模板实现单链表（类外实现）
本文实例为大家分享了C++使用模板实现单链表的具体代码,供大家参考,具体内容如下 这一篇可以和上一篇点击打开链接 模板实现单链表进行对比 看类外实现和类内实现的区别 代码: #include <iostream> using namespace std; template<typename T> class CLink { public: class Node; CLink();//无参的构造函数 void InsertHead(T data);//头插 void InsertTa
-
C++实现合并两个排序的链表
本文实例为大家分享了C++合并两个排序的链表,供大家参考,具体内容如下 问题描述 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则. struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; 方法一 class Solution { public: ListNode* Merge(ListNode* pHead1, ListN
-
C++实现链表版本通讯录
本文实例为大家分享了C++实现链表版本通讯录的具体代码,供大家参考,具体内容如下 #include <iostream> #include <string> using namespace std; class Address; class Contact{ private: string name; string sex; string tel; string QQ; string address; string addition; Contact *next; public:
-
C++使用模板实现单链表
本文实例为大家分享了用模板实现单链表,供大家参考,具体内容如下 话不多说 直接上代码 #include <iostream> using namespace std; template<typename E> class CLink; template<typename T> class Node { friend class CLink<T>; public: /* 构造函数和析构函数一般不加类型参数 本类类中除了构造函数和析构函数以外 其它的地方都要加上
-
C++数据结构之链表的创建
C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素进行复制改写(线程非常不安全). 2.通常创建链表都是有next这样的成员变量指向下一个项, 通过定义一个head,last来进行链表创建. 参考函数 TestLinkCreateStupid(). 说明 1.其实很早就知道另一种创建方式, 但是一直没总结. 没
-
C++链表实现通讯录管理系统
用数据结构里面线性结构的链表实现,供大家参考,具体内容如下 文件操作未写 有登录操作,复制源码需要更改登录模块的密码文件存放位置 使用VS2017编译器需要保留开头: #define _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #include "iostream" #include "cstdio" #include "fstream" #include "stdli
-
使用C++实现顺序链表
这是创建的LIst.h头文件 #ifndef LIST_H #define LIST_H class List { public: List(int size); ~List(); void DestroyList(); void ClearList(); bool ListEmpty(); int ListLength(); bool GetElem(int i, int *e); int LocateElem(int *e); bool ListInsert(int i, int *e);
-
C++ 实现静态链表的简单实例
C++ 实现静态链表的简单实例 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标cur. 这种存储结构,仍需要预先分配一个较大的空间,但在作为线性表的插入和删除操作时不需移动元素,仅需修改指针,故仍具有链式存储结构的主要优点. 下图表示了静态链表的一中存储结构: 图中用彩色途上的是两个头结点,不存放数据,分别用来记录第一个备用节点和第一个数据节点的下标. 下面给出静态链表的C++实现代码: 首先给出头文件:StaticList.
-
C语言静态链表和动态链表
1. 静态链表 结构体中的成员可以是各种类型的指针变量,当一个结构体中有一个或多个成员的基类型是本结构体类型时,则称这种结构体为"引用自身的结构体".如: struct link { char ch; struct link *p; } a; p是一个可以指向 struct link 类型变量的指针成员.因此,a.p = &a 是合法的表达式,由此构成的存储结构如图1所示. 图1 引用自身的结构体 例1 一个简单的链表 #include <stdio.h> stru
-
C语言实现静态链表的方法
在动手之前我一直以为静态链表和动态链表没有什么差别,细细一想才发现,原来静态链表之中隐藏着一个非常值得讨论的话题--内存管理. 静态链表的"静态"二字是指内存的来源为静态内存(通常用全局数组).与动态链表不同,在静态链表中节点内存的申请与释放都需要自行维护,由于这里是链表,也很容易想到将空余的节点链接起来形成一个free_list,每次需要时从free_list头部取出一个节点,释放时再将节点加到头部,这样就能够非常容易的实现链表的其他操作. 复制代码 代码如下: // 静态链表 的实
-
用Java实现一个静态链表的方法步骤
什么是静态链表? 对于线性链表,也可用一维数组来进行描述.这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构. 用数组描述的链表,即称为静态链表. 在C语言中,静态链表的表现形式即为结构体数组,结构体变量包括数据域data和游标CUR. 静态链表的节点 数据域:用于存储数据元素的值 游标:即数组下标,表示直接后继元素所在数组中的位置 public class StaticLinkedListNode<T> { public T data; // 数据 public int curs
-
C++实现静态链表
本文实例为大家分享了C++实现静态链表的具体代码,供大家参考,具体内容如下 一.动态链表和静态链表区别: (1)动态链表: (2)静态链表: 应用:二叉树 二.思路: 1.结点设置:T data: int link; 2.链表要用一个avil来保存可分配空间的首地址: 3.初始化:引入头结点:elem[0]: 头结点先指向空NULL, 用-1表示: avil存储空分配的空间的首地址1: 然后让其它可分配空间的结点的link指向坐标大一的结点: 三.实现程序: #ifndef Stat
-
C语言实现静态链表
本文实例为大家分享了C语言实现静态链表的具体代码,供大家参考,具体内容如下 注意事项: 1.这里用k申请空间,i遍历空间. 2.静态链表是利用游标来模拟指针,把固定分配的内存分成备用链表和链表两大块,在利用自制的malloc和free函数申请释放备用空间时,实现离散存储. 3.基本操作和动态链表实际上差不多,不过一个是利用p = p->next一个是使用i = L[i].cur来实现指针的后移. 4.初始化链表时,链表只有最后一个空间的cur是0, 意味是头指针,并没有任何分配的空间.备用链表的
-
Python 实现静态链表案例详解
静态链表和动态链表区别 静态链表和动态链表的共同点是,数据之间"一对一"的逻辑关系都是依靠指针(静态链表中称"游标")来维持. 静态链表 使用静态链表存储数据,需要预先申请足够大的一整块内存空间,也就是说,静态链表存储数据元素的个数从其创建的那一刻就已经确定,后期无法更改. 不仅如此,静态链表是在固定大小的存储空间内随机存储各个数据元素,这就造成了静态链表中需要使用另一条链表(通常称为"备用链表")来记录空间存储空间的位置,以便后期分配给新添加元
-
C++ 实现静态单链表的实例
C++ 实现静态单链表的实例 利用数组实现的静态单链表,与严蔚敏书实现略有不同,不另设回收空间.有任何BUG或错误,希望各位朋友多多反馈~~感激不尽 /* Author : Moyiii * Mail: lc09@vip.qq.com * 静态链表实现,仅作学习之用,当然如果 * 你想拿去用,随你好啦. */ #include <iostream> using namespace std; #define MAX_LIST_SIZE 100 class Node { public: int d
-
JavaScript中数据结构与算法(三)：链表
我们可以看到在javascript概念中的队列与栈都是一种特殊的线性表的结构,也是一种比较简单的基于数组的顺序存储结构.由于javascript的解释器针对数组都做了直接的优化,不会存在在很多编程语言中数组固定长度的问题(当数组填满后再添加就比较困难了,包括添加删除,都是需要把数组中所有的元素全部都变换位置的,javascript的的数组确实直接给优化好了,如push,pop,shift,unshift,split方法等等-) 线性表的顺序存储结构,最大的缺点就是改变其中一个元素的排列时都会引起
-
C语言链表详解及代码分析
C语言链表详解附实例 什么是链表 链表是一种常见的重要的数据结构.它是动态地进行存储分配的一种结构.链表和数组比较,不用事先确定存储空间,而是根据需要开辟内存单元. 下图1是最简单的一种链表(单向链表)的结构 第 0 个结点称为头结点,它存放有第一个结点的首地址,它没有数据,只是一个指针变量.以下的每个结点都分为两个域,一个是数据域,存放各种实际的数据,如学号 num,姓名 name,性别 sex 和成绩 score 等.另一个域为指针域,存放下一结点的首地址.链表中的每一个结点都是同一种结构类