数据结构(c++ )线性表（二）链接存储及其实现

预备知识： 1.0 c++ 2.0 指针 3.0 结构体

1.0 单链表

1.1 单链表的定义

单链表是用一组任意的存储单元来存放线性表的元素。存储单元可以连续，也可以不连续

为了正确的表示元素之间的逻辑关系，每个存储单元除了存储元素外 ，还需要存储后继元素的位置，这个地址信息用指针表示，称为指针；这两个元素组成了数据元素的存储映像，称为结点 也就是说节点有两个部分组成的

数据域指针域

1.2 单链表结点c++实现

struct Node{ //Node 可以自己随便起名 int data;//这是数据域 Node *next;//这是指针域 }

1.3 单链表的构造

为了避免其他对单链表的操作造成的bug,我们需要在构造单链表的时候构建一个头结点 怎么理解这个头结点呢，我是这么理解的就是不给他的数据域赋值，同时其他的操作不针对头结点，仅仅是个标识

下面的代码介绍单链表的增删查，具体说明在注释中解释

#include <iostream> using namespace std; struct Node{ int data; Node *next; }; class LinkList{ public: LinkList(){ first = new Node; //申请一个Node类型的结点/存储空间 //因为是作为头结点，所以不需要给数据域赋值 first->next = NULL; //建立一个只有头结点的空链表 所以next指向NULL } //头插法给链表赋初值 LinkList(int a[],int n){ //数组形参数作为给单链表赋值 first = new Node; first->next = NULL; //立一个只有头结点的空链表 for(int i = 0;i < n;i++ ){ Node *s = new Node; s->data = a[i]; //赋值 s->next = first->next; //每个新建的结点都要链接之前头结点所指向的结点 first->next = s; //头插法，每个元素结点都插在头结点后 } } //尾插法给单链表赋初值 void AddFromLast(int a[],int n){ Node *p = first; //设立工作指针，使他始终指向单链表的尾部 for(int i = 0;i < n;i++){ Node *s = new Node; //申请新的结点 p->next = s; //原链表的尾部next指针执行新的结点 s->data = a[i]; //赋值 p = s; //尾指针后移 } p->next = NULL; //尾指针的next指向空 } void AddData(int a,int position){ Node *s =new Node; //申请Node类型的空间 Node *p; //工作指针 p = first; s->data = a; int count = 0; //下面这个循环的结果就是工作指针p指向了第position-1个结点 while(count != position-1){ p = p->next; count++; } //开始执行插入 s->next = p->next; //先让s->next值向第position 个结点，顺序不能乱 p->next = s; //第position-1个结点的next指向新添加的结点 //给结点赋值 s->data = a; } //析构函数 单链表的空间是用new申请的，只能用delete删除 ~LinkList(){ while(first->next != NULL){ Node *p = first; first = first->next; delete p; } } //删除指定的结点 int DeleteData(int i){ Node *p = first; Node *r; int count = 0; while(count != i-1){ p = p->next; count++; } r = p->next; p->next = r->next; int x = r->data; delete r; return x; } //遍历所有的数据 void ShowAll(){ Node *p =first->next; while(p != NULL){ cout<<p->data<<endl; p = p->next; } } //按位查找 int SelectByPosition(int position){ Node *p = first; int count = 0; while(count != position){ p = p->next; count++; } return p->data; } private: Node *first;//头指针 }; int main(){ int a[10] = {1,2,3,4,5,6,7,8,9,0}; LinkList link(a,10); link.ShowAll(); cout<<endl; link.AddData(111,5); link.ShowAll(); cout<<endl; link.DeleteData(5); link.ShowAll(); cout<<endl; link.AddFromLast(a,10); link.ShowAll(); cout<<endl; cout<<link.SelectByPosition(5); cout<<endl; }

结果：

---

接下来我们进行性能分析

单链表的查找的时间复杂度为O(n)但链表的插入式删除算法都需要查找位置，所以时间复杂度也是O(n)

2.0线性表的顺序存储结构与连接存储结构性能的比较

取第i个位置的元素 顺序存储的时间复杂度是O(1) 链接存储是O(n)插入和删除操作链接存储在给出指定位置的指针后，时间复杂度是O(1) 而顺序存储是O(n)一般来说如果操作经常与元素在线性表中的位置相关或者频繁进行查找的时候，适合用顺序存储结构，如果频繁进行删除，插入，则适合用链接的存储结构