解析C++的線性表鏈式存儲設計與相關的API實現

2020-01-26 14:41:12

字體：大中小

來源：轉載

供稿：網友

基本概念
鏈式存儲定義：
為了表示每個數據元素與其直接后繼元素之間的邏輯關系，每個元素除了存儲本身的信息外，還需要存儲指示其直接后繼的信息。

2016314160729026.jpg (411×342) 2016314160800178.jpg (952×421)

表頭結點：
鏈表中的第一個結點，包含指向第一個數據元素的指針以及鏈表自身的一些信息。
數據結點：
鏈表中代表數據元素的結點，包含指向下一個數據元素的指針和數據元素的信息。
尾結點：
鏈表中的最后一個數據結點，其下一元素指針為空，表示無后繼。

鏈表技術領域推演

2016314160930644.jpg (975×592)

鏈表鏈式存儲_api實現分析：
在C語言中可以用結構體來定義鏈表中的指針域，鏈表中的表頭結點也可以用結構體實現；

2016314160951696.jpg (663×300)

2016314161848712.jpg (804×483)

帶頭結點、位置從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。

刪除元素：

2016314162023550.jpg (527×244)

代碼實例：

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

優點：