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

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

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

链表技术领域推演

链表链式存储_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

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c++
， 线性表
链式存储
线性表的链式存储结构、线性表链式存储、线性表的链式存储、线性表链式存储结构、线性表的链式存储代码，以便于您获取更多的相关知识。

时间： 2024-09-15 02:19:13

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

设计模式中的备忘录模式解析及相关C++实例应用_C 语言

备忘录模式旨在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态.这样以后就可将该对象恢复到原先保存的状态.在命令模式中,备忘录模式经常还经常被用来维护可以撤销(Undo)操作的状态. 类图: Originator:负责创建一个备忘录Memento,用以记录当前时刻它的内部状态,并可使用备忘录恢复内部状态.Originator可根据需要决定Memento存储Originator的哪些内部状态. Memento:负责存储Originator对象的内部状态,并可防止Origin

C语言线性表的顺序表示与实现实例详解_C 语言

1.概述 通常来说顺序表是在计算机的内存中以数组的形式保存的线性表,是用一组地址连续的存储单元依次存储数据元素的线性数据结构.线性表采用顺序存储的方式存储就称之为顺序表.顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中. 将表中元素一个接一个的存入一组连续的存储单元中,这种存储结构就是顺序结构. 采用顺序存储结构的线性表简称为" 顺序表".顺序表的存储特点是:只要确定了起始位置,表中任一元素的地址都通过下列公式得到:LOC(ai)=LOC(a1)+(i-1)*L 1≤

错误:sem_union的存储大小未知问题的解决方法_C 语言

今天在编译代码的时候提示 错误: 'sem_union'的存储大小未知 问题原因:在新版2.6内核中关于union sem_union 这个联合体已经被注释了,需要自己写这个联合体. 解决方案:在C文件中先定义: union semun { int val; struct semid_ds *buf; unsigned short *array; }sem_union; 随后编译时它就能找到预先定义好的sem_union联合体了. Linux下编译时出现的错误及解决方法 (1)由于是Linux新

举例解析设计模式中的工厂方法模式在C++编程中的运用_C 语言

工厂方法模式不同于简单工厂模式的地方在于工厂方法模式把对象的创建过程放到里子类里.这样工厂父对象和产品父对象一样,可以是抽象类或者接口,只定义相应的规范或操作,不涉及具体的创建或实现细节. 其类图如下: 实例代码为: #pragma once class IProduct { public: IProduct(void); virtual ~IProduct(void); }; #pragma once #include "iproduct.h" class IPad : public

C语言中自动隐式转换与类型强制转换实例分析_C 语言

本文通过一个C程序实例对C语言中自动隐式转换与类型强制转换的注意点进行深入分析,详情如下: 先看一个C程序: #include<stdlib.h> #include<stdio.h> #include<conio.h> double proc(int q){ int n; double sum,t;//本例的关键就在这几个变量的类型上 sum = 2.0; while(sum<=q){ t=sum; //sum = sum+(n+1)/n;//自动隐式转换 sum

C语言 存储类详解及示例代码_C 语言

C 存储类 存储类定义 C 程序中变量/函数的范围(可见性)和生命周期.这些说明符放置在它们所修饰的类型之前.下面列出 C 程序中可用的存储类: auto register static extern auto 存储类 auto 存储类是所有局部变量默认的存储类. { int mount; auto int month; } 上面的实例定义了两个带有相同存储类的变量,auto 只能用在函数内,即 auto 只能修饰局部变量. register 存储类 register 存储类用于定义存储在寄存器

解析设计模式中的Prototype原型模式及在C++中的使用_C 语言

原型模式的意图是用原型实例指定创建对象的种类,并且通过拷贝这些原型创建新的对象. 适用性 当要实例化的类是在运行时刻指定时,例如,通过动态装载:或者 为了避免创建一个与产品类层次平行的工厂类层次时:或者 当一个类的实例只能有几个不同状态组合中的一种时.建立相应数目的原型并克隆它们可能比每次用合适的状态手工实例化该类更方便一些. 关于这个模式,突然想到了小时候看的<西游记>,齐天大圣孙悟空再发飙的时候可以通过自己头上的 3 根毛立马复制出来成千上万的孙悟空,对付小妖怪很管用(数量最重要). 原型

解析内存对齐 Data alignment: Straighten up and fly right的详解_C 语言

    为了速度和正确性,请对齐你的数据.     概述:对于所有直接操作内存的程序员来说,数据对齐都是很重要的问题.数据对齐对你的程序的表现甚至能否正常运行都会产生影响.就像本文章阐述的一样,理解了对齐的本质还能够解释一些处理器的"奇怪的"行为.   内存存取粒度    程序员通常倾向于认为内存就像一个字节数组.在C及其衍生语言中,char * 用来指代"一块内存",甚至在JAVA中也有byte[]类型来指代物理内存.   Figure 1. 程序员是如何看内存的

解析C++中的for循环以及基于范围的for语句使用_C 语言

for循环语句 重复执行语句,直到条件变为 false. 语法 for ( init-expression ; cond-expression ; loop-expression ) statement; 备注 使用 for 语句可构建必须执行指定次数的循环. for 语句包括三个可选部分,如下表所示. for 循环元素 下面的示例将显示使用 for 语句的不同方法. #include <iostream> using namespace std; int main() { // The co