链表的知识总结

链表的知识总结

前言

链表其实也算好理解的一种数据结构，其和顺序表不一样的是数据元素按逻辑次序链接在一起。

在这先说一下顺序表的缺点：

• 插人和删除操作需移动大量元素。

• 不确定容量大小。

• 使储存空间变得碎片化。

这些缺点其实很好理解，插人和删除操作都是一步一步位移完成。数组大小需要我们去声明，事先确定他的大小。如果声明许多的数组，会造成存储空间的“碎片”。因为这些问题的根本在于顺序表是静态存储分配。

现在一起了解一下链表吧。

单链表

单链表(singly linked list)是用组任意的行储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中的任意位置。为了能正确表乐元素之间的逻辑关系每个存储单元在存储数据元素同时，还必须在储其后继元素所在的地址信息。这个地址信息称为指针。

单链表的知识点：

• 数据元素的存储映象，称为结点(node），其中data为数据域，存放数据元素：nxt为指针城，存放该结点的后继结点的地址。如图2-1。

• 在使用单链表时关心的只是数据元素以及数据元素之间的逻辑关系，而不是每个数据元素在存储器中的实际位置。

  其余的知识点有头结点，尾标志，头指针，指针变量这些，在单链表中有很大的作用。

• 接下来进入C++代码实现栈的功能·环节，如有不足，和我一起讨论吧

C++基本操作实现

结点结构

template <class D>
struct Node
{D data;Node<D>*next;
};

其中data为数据域，存放数据元素：nxt为指针域，是不是很简单。

功能概括

template <class D>
class LinkList
{
public:LinkList();//建立只有头结点的空链LinkList (D a[],int n);~LinkList ();int Length();D Get(int i);int Locate(D x);void Insert (int i,D x);D Delete(int i);int Empty ();void PrintList();
private:Node<D>*first;
};

单链表初始化

template <typename D>
LinkList <D>::LinkList()//初始化 
{first=new Node<D>;first->next=NULL;
}

这个是构造函数，无参构造，是需要了解一下C++知识

作用是生成头结点的空链表。

遍历操作

template <typename D>
void LinkList <D>::PrintList()//遍历 
{Node<D>*p=first->next;while(p!=NULL){cout<<p->data<<"t";p=p->next;} cout<<endl;
}

这个遍历操作的工作图和伪代码如下：

求链表长度

template <typename D>
int LinkList <D>::Length()//长度 
{Node<D>*p=first->next;int count = 0;while(p != NULL){p = p->next;count++;}return count;} 

了解一下就行，可以不用太关注。

按位查找

 template <typename D>
D LinkList <D>::Get(int i)//按位查找 
{Node<D>*p=first->next;int count = 1;while(p != NULL && count<i){p = p->next;count++;} if(p == NULL){cout<<"该位置不存在"; } else return p->data;} 

按值查找

 template <typename D>
int LinkList <D>::Locate(D x)//按值查找 
{Node<D>*p=first->next;int count = 1;while(p != NULL ){if(p->data == x) return count;p = p->next;count++;} return 0;} 

插入操作

 template <typename D>
void LinkList <D>::Insert(int i,D x)//插入 
{Node<D>*p=first->next,*s= NULL;int count = 0;while(p != NULL && count < i-1){p = p ->next;count++;}if(p == NULL) throw "插入位置错误";else{s = new Node<D>;s-> data = x;s->next = p->next;p->next = s;} 
}

这个插入操作的工作图和伪代码如下

构造函数

嘿嘿嘿，这有两种方式，我可是看了好久才理解呢，分别是头插法和尾插法，相信我讲的一定好理解。 

一开始有一个结点，然后对其后插入数据，之后的·数据仍是从头结点后面插入就是头插法，数据尾部插入是尾插法。

如图所示

头插法代码

template <typename D>
LinkList <D>::LinkList(D a[],int n)
{first = new Node<D>;first-> next = NULL;for(int i = 0; i < n; i++){Node<D>*s = NULL;s = new Node<D>;s->data = a[i];s->next = first-> next;first-> next = s;} 
}

这里需要注意尾插法，需要·设尾指针指向当前的终端结点。

template <typename D>
LinkList <D>::LinkList(D a[],int n)
{first = new Node<D>;Node<D>*r = first,*s = nullptr;for( int i = 0;i < n;i++){s =new Node<D>;s->data = a[i];r->next = s;r = s;}r->next = nullptr;} 
}

删除操作

template <typename D>
D LinkList <D>::Delete(int i)//删除操作 
{D x;Node<D>* p = first,*q =NULL;int count = 0;while(p != NULL && count < i-1){p = p-> next;count++;}if(p == NULL || p->next == NULL)throw "错误";else{q = p->next;x = q->data;delete q;p->next=q->next;return x;} 
}

析构函数

template <typename D>
LinkList <D>:: ~LinkList(){Node<D>*p = first;while(first != NULL){first = first->next;delete p;p = first;} 
}

链表代入代码：

这是我做的主函数，其用了上面设计的代码,运行结果在后面。

#include<iostream>
using namespace std;
struct Node
{int data;Node *next;
};
class LinkList
{
public:LinkList();//建立只有头结点的空链LinkList (int a[],int n);~LinkList ();int Length();int Get(int i);int Locate(int x);void Insert (int i,int x);int Delete(int i);int Empty ();void PrintList();
private:Node *first;
};
LinkList::LinkList()//初始化 
{first=new Node;first->next=NULL;
}
LinkList ::LinkList(int a[],int n)//创建单链表 
{first = new Node;first-> next = NULL;for(int i = 0; i < n; i++){Node*s = NULL;s = new Node;s->data = a[i];s->next = first-> next;first-> next = s;} 
}
LinkList :: ~LinkList(){//销毁单链表 Node *p = first;while(first != NULL){first = first->next;delete p;p = first;}
}
void LinkList::PrintList()//遍历 
{Node*p=first->next;while(p!=NULL){cout<<p->data<<"t";p=p->next;} cout<<endl;
};
int LinkList ::Get(int i)//按位查找 
{Node *p=first->next;int count = 1;while(p != NULL && count<i){p = p->next;count++;} if(p == NULL){cout<<"该位置不存在"; } else return p->data;} int LinkList ::Delete(int i)//删除操作 
{int x;Node * p = first,*q =NULL;int count = 0;while(p != NULL && count < i-1){p = p-> next;count++;}if(p == NULL || p->next == NULL)throw "错误";else{q = p->next;x = q->data;p->next=q->next;delete q;return x;} 
}void LinkList ::Insert(int i,int x)//插入 
{Node *p=first->next,*s= NULL;int count = 0;while(p != NULL && count < i-1){p = p ->next;count++;}if(p == NULL) throw "插入位置错误";else{s = new Node;s-> data = x;s->next = p->next;p->next = s;} 
}
int main(){int r[5];for(int i =0;i<5;i++){r[i]=2*i+1; }LinkList list(r,5);list.PrintList();//遍历cout<<"第二位数字:"<<list.Get(2)<<endl;//按位查找list.PrintList();cout<<"第二位插入数字100:"<<endl;list.Insert(2,100);//插入list.PrintList();cout<<"第二位数字删除:"<<list.Delete(2)<<endl;//删除 list.PrintList();return 0;
}

呼哧呼哧写了五千多字，其实链表很好理解的，其他还有双链表、循环链表、链栈等，虽然我还没学太懂……

 总的来说，知识在于实践，看了不一定会，动手打一打有助于理解哦_φ(❐_❐✧ 听懂点点赞吧。

 参考文献：数据结构一书。