解析C++的线性表链式存储设计与相关的API实现

基本概念
链式存储定义:
为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息。

表头结点:
链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息。
数据结点:
链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息。
尾结点:
链表中的最后一个数据结点,其下一元素指针为空,表示无后继。

链表技术领域推演

链表链式存储_api实现分析:
在C语言中可以用结构体来定义链表中的指针域,链表中的表头结点也可以用结构体实现;

带头结点、位置从0的单链表;
返回链表中第3个位置处,元素的值。

LinkListNode* LinkList_Get(LinkList* list, int pos)
{
 if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
 return NULL;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header); 

 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 } 

 return cur->next;
}

返回第三个位置的。
移动pos次以后,当前指针指向哪里?
答案:指向位置2,所以需要返回 ret = current->next。
 
备注:循环遍历时
遍历第1次,指向位置0;
遍历第2次,指向位置1;
遍历第3次,指向位置2;
遍历第n次,指向位置n-1。

删除元素:

代码实例:

linklist.h

#ifndef _MYLINKLIST_H_
#define _MYLINKLIST_H_ 

typedef void LinkList; 

typedef struct _tag_LinkListNode
{
 struct _tag_LinkListNode* next;
}LinkListNode; 

LinkList* LinkList_Create(); 

void LinkList_Destroy(LinkList* list); 

void LinkList_Clear(LinkList* list); 

int LinkList_Length(LinkList* list); 

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos); 

LinkListNode* LinkList_Get(LinkList* list, int pos); 

LinkListNode* LinkList_Delete(LinkList* list, int pos); 

#endif

linklist.cpp

#include <iostream>
#include <cstdio>
#include "linklist.h" 

using namespace std; 

typedef void LinkList; 

typedef struct _tag_LinkList
{
 LinkListNode header;
 int length;
}TLinkList; 

LinkList* LinkList_Create()
{
 TLinkList *tmp = NULL; 

 tmp = (TLinkList *)malloc(sizeof(TLinkList));
 if (tmp == NULL) {
 printf("function LinkList_Create() err.\n");
 return NULL;
 }
 memset(tmp, 0, sizeof(TLinkList)); // 初始化为空链表 

 return tmp;
} 

void LinkList_Destroy(LinkList* list)
{
 if (list == NULL) {
 return;
 }
 free(list); 

 return;
} 

void LinkList_Clear(LinkList* list)
{
 if (list == NULL) {
 return;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 tList->header.next = NULL;
 tList->length = 0; 

 return;
} 

int LinkList_Length(LinkList* list)
{
 if (list == NULL) {
 return -1;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list; 

 return tList->length;
} 

int LinkList_Insert(LinkList* list, LinkListNode* node, int pos)
{
 if (list == NULL || node == NULL || pos < 0) {
 return -1;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header); 

 // 对pos的容错处理,如果pos过大,改为最后面
 if (pos > LinkList_Length(list)) {
 pos = LinkList_Length(list);
 } 

 // 移动到需要插入的位置
 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 } 

 // 插入
 node->next = cur->next;
 cur->next = node; 

 ++tList->length; 

 return 0;
} 

LinkListNode* LinkList_Get(LinkList* list, int pos)
{
 if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
 return NULL;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header); 

 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 } 

 return cur->next;
} 

LinkListNode* LinkList_Delete(LinkList* list, int pos)
{
 if (list == NULL || pos < 0 || pos >= LinkList_Length(list)) {
 return NULL;
 }
 TLinkList *tList = NULL;
 tList = (TLinkList *)list;
 LinkListNode *cur = NULL;
 cur = &(tList->header); 

 for (int i = 0; i < pos; ++i) {
 cur = cur->next;
 } 

 LinkListNode *ret = NULL;
 ret = cur->next; 

 // 删除结点
 cur->next = ret->next; 

 --tList->length; 

 return ret;
}

main.cpp

#include <iostream>
#include <cstdio>
#include "linklist.h" 

using namespace std; 

typedef struct _Student
{
 LinkListNode node;
 char name[32];
 int age;
}Student; 

int main()
{
 Student s1, s2, s3, s4, s5, s6;
 s1.age = 21;
 s2.age = 22;
 s3.age = 23;
 s4.age = 24;
 s5.age = 25;
 s6.age = 26; 

 // 创建链表
 Student *list = (Student *)LinkList_Create(); 

 // 插入结点
 LinkList_Insert(list, (LinkListNode *)&s1, 0);
 LinkList_Insert(list, (LinkListNode *)&s2, 0);
 LinkList_Insert(list, (LinkListNode *)&s3, 0);
 LinkList_Insert(list, (LinkListNode *)&s4, 0);
 LinkList_Insert(list, (LinkListNode *)&s5, 0);
 LinkList_Insert(list, (LinkListNode *)&s6, 3); 

 // 遍历链表
 for (int i = 0; i < LinkList_Length(list); ++i) {
 Student *tmp = (Student *)LinkList_Get(list, i);
 if (tmp == NULL) {
 return 0;
 }
 printf("age: %d\n", tmp->age);
 } 

 // 删除链表结点
 while (LinkList_Length(list)) {
 Student *tmp = (Student *)LinkList_Delete(list, 0);
 if (tmp == NULL) {
 return 0;
 }
 printf("age: %d\n", tmp->age);
 } 

 LinkList_Destroy(list); 

 return 0;
}

优点:

  • 无需一次性定制链表的容量;
  • 插入和删除操作无需移动数据元素。

缺点:

  • 数据元素必须保存后继元素的位置信息;
  • 获取指定数据的元素操作需要顺序访问之前的元素。

工程详情:Github

(0)

相关推荐

  • 讲解C++的do while循环和循环语句的嵌套使用方法

    用do-while语句构成循环 do-while语句的特点是先执行循环体,然后判断循环条件是否成立.其一般形式为: do 语句 while (表达式); 它是这样执行的:先执行一次指定的语句(即循环体),然后判别表达式,当表达式的值为非零("真") 时,返回重新执行循环体语句,如此反复,直到表达式的值等于0为止,此时循环结束.可以用下图表示其流程. [例]用do-while语句求1+2+3+-+100. #include <iostream> using namespace

  • C#用链式方法表达循环嵌套

    一.起缘 故事缘于一位朋友的一道题: 朋友四人玩LOL游戏.第一局,分别选择位置:中单,上单,ADC,辅助:第二局新加入的伙伴要选上单,四人可选位置变为:中单,打野,ADC,辅助:要求,第二局四人每人不得选择和第一局相同的位置,请问两局综合考虑有多少种位置选择方式? 对于像我这边不懂游戏的人来讲,看不懂.于是有了这个版本: 有4个人,4只椅子,第一局每人坐一只椅子,第二局去掉第2只椅子,增加第5只椅子,每人坐一只椅子,而且每个人不能与第一局坐相同的椅子.问两局综合考虑,共有多少种可能的情况? 我

  • C++中实现队列类链式存储与栈类链式存储的代码示例

    队列类链式存储 代码: linkqueue.hpp // 队列类 #pragma once #include "linklist.hpp" template <typename T> class LinkQueue { public: LinkQueue(); ~LinkQueue(); public: int clear(); int append(T &t); int retieve(T &t); int header(T &t); int le

  • 用C++实现一个链式栈的实例代码

    自定义一个链式栈,c++语言实现,不足之处,还望指正! 复制代码 代码如下: // MyStack.cpp : 定义控制台应用程序的入口点.//自己构造一个链式栈,具有push(入栈),pop(出栈),top(取得栈顶元素),size(返回栈大小),empty(判断是否为空)等功能#include "stdafx.h"#include <iostream>using namespace std;//构造栈的节点template <class T>struct N

  • smarty的section嵌套循环用法示例

    本文实例讲述了smarty的section嵌套循环用法.分享给大家供大家参考,具体如下: {section name="sec1" loop=$typeList} <TABLE class=left20 height=25 cellSpacing=0 cellPadding=0 width=624 background=images/indexbg.gif border=0> <TBODY> <TR> <TD class=zi align=le

  • 探讨:C++实现链式二叉树(用非递归方式先序,中序,后序遍历二叉树)

    如有不足之处,还望指正! 复制代码 代码如下: // BinaryTree.cpp : 定义控制台应用程序的入口点.//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include "stdafx.h"#include<iostream>#include<string>#include <stack>using namespace std;template<class T>struct BiNode{ T data; 

  • 解析C++的线性表链式存储设计与相关的API实现

    基本概念 链式存储定义: 为了表示每个数据元素与其直接后继元素之间的逻辑关系,每个元素除了存储本身的信息外,还需要存储指示其直接后继的信息. 表头结点: 链表中的第一个结点,包含指向第一个数据元素的指针以及链表自身的一些信息. 数据结点: 链表中代表数据元素的结点,包含指向下一个数据元素的指针和数据元素的信息. 尾结点: 链表中的最后一个数据结点,其下一元素指针为空,表示无后继. 链表技术领域推演 链表链式存储_api实现分析: 在C语言中可以用结构体来定义链表中的指针域,链表中的表头结点也可以

  • C++实现线性表链式存储(单链)

    本文实例为大家分享了C++实现线性表链式存储的具体代码,供大家参考,具体内容如下 实现的功能: 1.定义了三中传入不同参数的构造函数,用于初始化创建不同的链表: 2.能实现增.删.查等基本功能: 存在的问题: 当创建一个已知大小的空链表后,链表中的数据并不为空,见下图: 下面是代码及测试结果: singlelinklist.h #pragma once #include "iostream" #include "exception" #include "s

  • java线性表的存储结构及其代码实现

    Java数据结构学习笔记第一篇: 用程序后在那个的数据大致有四种基本的逻辑结构: 集合:数据元素之间只有"同属于一个集合"的关系 线性结构:数据元素之间存在一个对一个的关系 树形结构:数据元素之间存在一个对多个关系 图形结构或网状结构:数据元素之间存在多个对多个的关系 对于数据不同的逻辑结构,计算机在物理磁盘上通常有两种屋里存储结构 顺序存储结构 链式存储结构 本篇博文主要讲的是线性结构,而线性结构主要是线性表,非线性结构主要是树和图. 线性表的基本特征: 总存在唯一的第一个数据元素

  • Java实现线性表的链式存储

    本文实例为大家分享了Java实现线性表的链式存储,供大家参考,具体内容如下 链表:一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的. package algorithm.datastructure.linklist; import java.util.NoSuchElementException; /* * 链表 * 物理存储上非连续的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现 * * */ public class LinkedLi

  • C语言数据结构之线性表的链式存储结构

    1.什么是线性表的链式存储结构 -链表 存储结点:包括元素本身的信息,还有元素之间的关系逻辑的信息 这个结点有:数据域和指针域 一个指针域:指向后继结点, 单链表 二个指针域: 指向前继结点,还有一个指向后继结点 双链表 2.原理是: s=(LinkNode *)malloc(sizeof(LinkNode));// s->data=e; //这里赋值了 s->next=p->next; // p->next=s; //这里把指针s给到了p 结点a-> 结点b -> 结

  • Hbase列式存储入门教程

    目录 1.逻辑结构 2.物理结构 3.增删改查 4.应用场景 5.参考资料 HBase是一种分布式.可扩展.支持海量数据存储的NoSQL数据库.分布式是因为HBase底层使用HDFS存储数据,可扩展也是基于HDFS的横向扩展能力,作为大数据的存储当然支持海量数据的存储,NoSQL非关系型数据库表结构和关系型数据库(如Mysql)的逻辑结构.物理结构很不一样,性质特点.应用场景也不一样. 1.逻辑结构 1)Name Space 命名空间,类似于关系型数据库的 DatabBase 概念,每个命名空间

  • 简要了解jQuery移动web开发的响应式布局设计

    响应式布局设计是根据用户设备的屏幕分辨率来响应用户设备的一种设计.这意味着,无论用户是在移动.平板还是桌面设备上浏览 Web 页面,设计都将根据该设备的屏幕分辨率显示特定的布局,从而适当地响应设备. 该框架的文档实际上结合使用了 jQuery Mobile 框架和 CSS3 媒体查询来实现自己的响应式设计.对不同屏幕分辨率的反应方式. 没有自定义样式,我们的电网将3列的布局在所有的屏幕宽度: 在我们的自定义样式,我们希望此网格叠加在狭窄的宽度,然后切换到一个标准的3栏布局.在很宽的屏幕宽度,我们

  • JAVA 实现二叉树(链式存储结构)

    二叉树的分类(按存储结构) 树的分类(按存储结构) 顺序存储(用数组表示(静态二叉树))   链式存储 一些特别的二叉根: 完全二叉树,平衡二叉树(AVL),线索二叉树,三叉的(带父亲的指针)    二叉搜索树或者叫二叉 查找树(BST)  所用二叉树如下图所示: 二叉树的Java实现(链式存储结构) class TreeNode { private int key = 0; private String data = null; private boolean isVisted = false

  • C语言 二叉树的链式存储实例

    二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

随机推荐