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

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

C++,链式

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

链表技术领域推演

C++,链式

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

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。

删除元素：

C++,链式

代码实例：

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