解析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; } 

@H_301_52@

返回第三个位置的。
移动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 

@H_301_52@

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,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,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; } 

@H_301_52@

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,(linkListNode *)&s3,(linkListNode *)&s4,(linkListNode *)&s5,(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; } 

@H_301_52@

优点：

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

缺点：

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

工程详情：Github

总结

以上是内存溢出为你收集整理的解析C++的线性表链式存储设计与相关的API实现全部内容，希望文章能够帮你解决解析C++的线性表链式存储设计与相关的API实现所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。