C++关于链表基础知识
单链表
// 结点的定义
template <class T>
struct Node
{
T data ;
Node <T> *next; //指向下一个node 的类型与本node相同
}
// 最后一个node指针指向Null
生成结点： Node <T> * p = new Node < T>;
为结点赋值: p-> data = 'a';
p- > next = （其他结点的地址）; p -> next = NULL ; (尾结点)
delete p; //释放结点
// 单链表的类实现
template <class T>
class LinkList
{
public : //此处是函数定义
LinkList();
ListList(T a[ ] , int n);
int Lenght();
T Get(int); //俺下标查找
int Loate(T); //按值定位
void insert(T,int); //插入
T delete (int) ; //删除
~LinkList();
private:
Node <T> * first;
}
构造函数的实现一个空链表：
template <class T>
LinkList <T> :: LinkList()
{
first = new Node <T>;
first->next = NULL;
}头插法
初始化头节点（头节点指的是first，首结点代表链表第一个结点）
template <class T>
LinkList <T> :: LinkList (T a[ ] ,int n)
{
//初始化头节点
first = new Node<T>;
first ->next =NULL;
for (int i =0 ; i<n ;i++)
{
//生成新的结点
Node <T> *s = new Node <T>;
s ->data =a [i];
//链接再头节点和首结点之间
s->next = first ->next;
first ->next = s ;
}
}核心代码：
s->next = first ->next;
first ->next = s ;因为对于first ->next的初始化指向是NULL;此处赋值给s->next则表示了s->next指向了NULL
然后将地址s赋值给了first ->next（头节点的地址域）
尾插法
template <class T>
LinkList <T> :: LinkList (T a[ ] ,int n)
{
//初始化头节点
Node<T> *first = new Node<T>;
Node<T> *r = first; //尾结点首先指向first
for (int i =0 ; i<n ;i++)
{
//生成新的结点
Node <T> *s = new Node <T>;
s ->data =a [i];
s ->next =NULL; //由于是尾插，直接指向NULL
//链接在尾结点后面：
r->next = s;
//尾结点后移，由于此时的新的结点s是尾结点
r= s;
}
//这里也可以加一句r->next = NULL;
}析构函数：
template <class T>
LinkList <T> :: ~linkList
{
while (first != NULL) //或者直接while(first)
{
Node <T> *p = first;
first = first->next;
delete p;
}
}
按照值查找：
查找值为x的结点的位置
顺序查找：
template <class T>
int LinkList <T> :: locate (T x) // T类型的x
{
Node<T> *p = first->next ;//首结点后的第一个结点
int j=1;
while(p) //p不为空一直循环,p为NULL的时候即循环到结尾
{
if(p->data ==x ) return j;
p = p->next ;
j++;
}
return 0;
}按照值查找返回结点 ，非模板类实现:
Node * LinkList:: local (int val )
{
Node* p = first;
while (p )
{
if (p ->data == val)
{
return p;
}
p = p -> next;
}
return NULL;
}按下标查找:
template <class T>
T LinkList <T> :: Get (int i){
//初始化
Node<T> * p = first ->next ;
int j =1;
while(j<i && p!=NULL)
{
p= p->next
j++;
}
if(p==NULL || i<1) throw"位置非法";
return p->data ;
}随意位置插入：
思路：
新建结点 Node<T> *s = new Node <T>; s->data = x;
插入 ： s ->next = p->next ; (p->next 的值是ai的地址，将其赋值给新节点地址域)
p->next =s ;
//将值为x的结点插入到位置为i的结点,那么首先要找到i-1 号结点
template <class T>
void LinkList <T> :: Insert (T x , int i)
{
Node <T> * p = first ;
int j = 0 ;
while (p && j<i-1)
{
p = p->next ;
j++;
}
if (p == NULL) throw "插入位置非法"
else {
// 新建结点
Node<T> *s = new Node <T>;
s->data = x;
//插入
s ->next = p->next ;
p->next =s ;
}
}在指定结点后插入：
//在指定的p结点之后插入
template <class T>
void LinkList <T> :: insertAfter (Node<T> * p , T x )
{
Node <T> *s = new Node <T>;
s -> data =x ;
s->next = p->next;
p- next = s ;
}
//在指定的p结点之前插入
//需要先找到p结点的前面一个结点q ,循环来找
template <class T>
void ListList <T> ::insertBefore (Node<T> * p ,T x )
{
Node <T> *q = first ; //从头节点开始找
while (q ->next != p ){ // 找到q结点的条件
q =q->next ;
}
insertAfter (q,x); //在q后插入，等于在p前插入
}
//上述方法时间复杂度是O(n)
//下列实现时间复杂度是O(1)
template <class T>
void LinkList <T> :: insertBefore (Node <T> * p ,T x)
{
Node <T> *s = new Node<T>;
* s = *p ;
p ->next = s; //将原来的p结点当成新插入的结点，把新的结点变为p结点放在后面
p ->data = x; // 等同于前插
}结点删除：
首先需要把ai代表的结点摘除，使用s 表示：
s = p->next ;
p->next = s -> next ;
然后删除结点:
delete s ;
template <class T>
T LinkList <T> :: detele (int i)
{
Node <T> * p = first ;
int j = 0;
while(p && j <i )
{
p = p->next ;
j++ ;
}
if (p->next ==NULL)
throw "删除位置非法"
else {
s = p->next ; //让中间结点（待删除）赋值给s
p->next = s ->next ; // 然后第三结点赋值给第一个结点的地址域
delete s; //删除中间结点
}
}
// 上述操作时间复杂度O(n)
//改成O（1）：
template <class T> //返回T因为一般删除都会返回结点的x值
T LinkList <T> ::delete (Node <T> *p )
{
if(p->next){// p非最后一个结点 ,使用删除后面的一个结点代替删除自己
T x =p ->data ;
p -> data = p ->next ->data ;
Node <T> *q = p ->next ; //表示出来后一个结点
q ->next = p ->next ; //准备将q出链
delete q;
return x ;//一般删除结点都返回其值
else{...正常循环}
}
}
求取链表长度:
template <class T>
int LinkList <T> :: Length(){
Node <T> * p = first ;
int i =0;
while ( p ){
p = p ->next;
i++;
}
return i;
}
//上述时间复杂度 O(N)循环链表：
尾指针地址域指向头节点，上述代码循环条件改为p!= r
双链表：
每个结点有两个指针域，指向前驱和后继
template <class T>
struct DulNode
{
T data;
DulNode <T> * prior, *next ;
}插入操作：
首先更改新结点的指针域
然后动链表
删除操作：
顺序表和链表的对比：
原文地址：https://blog.csdn.net/qq_51365682/article/details/142725219
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！