All posts

重学链表

最近又重学了一遍链表,记得大一学链表时也是很迷,指来指去没指明白哈哈哈。这一次学也是通透多了。

单链表

基本概念

定义

typedef struct Lnode{
    int data ;
    struct Lnode *next ;
}Lnode , *Linklist ;
  • 结构体内两个元素data 、next
  • data是int型,可修改为其他,例如char、double
  • next是类型为struct Lnode的指针,可指向struct Lnode这种结构体,在链表中next指向下一个结点,例如1号结点的next = 2号结点的地址
  • Lnode是struct Lnode的别名 , Linklist 是struct Lnode *的别名

声明一个链表

Linklist HEAD = new Lnode ;
HEAD->next = NULL ;
  • Linklist HEAD与Lnode *HEAD等价,但我们一般用Linklist HEAD来定义链表(定义链表头结点,链表头结点即代表该链表)。用Lnode *p定义一个结点
  • Linklist HEAD = new Lnode ;为头结点(头指针)分配一个大小为Lnode的空间。
  • 目前链表为空,头指针指向NULL.HEAD->next表示HEAD下一个结点地址。
  • 头指针HEAD不能严格算一个结点,HEAD->data未定义。

加入结点

Lnode *p = new Lnode ;//第一个结点p
cin >> p->data ; //输入该结点存储的数据data
HEAD->next = p ;
p->next = NULL ;
  • 再加一个结点
Lnode *q = new Lnode ;//第二个结点q
cin >> q->data ;
p->next = q ;
q->next = NULL ;
  • 注意最后一个结点的next应该指向NULL,否则q->next这个野指针无穷无尽。
链表示意图.jpg

常用函数操作

  • 初始化链表(初始化头指针)
void InitList(Linklist &HEAD){
    //调用InitList前得先声明HEAD,例如 Linklist linkedlist_1 ,linkedlist_1即是该链表的名称(用头指针来代表链表名称,类似于用地址a来代表数组)
    HEAD = new Lnode ; //为HEAD声明一块Lnode大小的空间
    HEAD->next = NULL ;
}
  • 判断链表是否为空
int IsEmpty(Linklist &HEAD){
    if(HEAD->next) return 0 ;//非空
    return 1 ; //为空
}
  • 销毁链表
void DestroyList(Linklist &HEAD){
    Lnode *p ;
    while(HEAD){
        p = HEAD ;
        HEAD = HEAD->next  ;
        delete p ;
    }
}
  • 清空链表
void ClearList(Linklist &HEAD){
    Lnode *p , *q ;
    p = HEAD ->next ;
    HEAD->next = NULL ;
    while(p){
        q = p->next ;
        delete p ;
        p = q ;
    }
}

tips:清空链表不释放头指针空间

  • 获取链表长度
int GetLength(Linklist &HEAD){
    Lnode *p = HEAD->next ;
    int length = 0 ;
    while(p){
        length++ ;
        p = p->next ;
    }
    return length ;
}
  • 根据索引获取链表元素
int GetElem(Linklist &HEAD , int i){
    if(i < 0 || i >= GetLength(HEAD))   {cout << "the index is invalid" << endl ; return 0 ;}
    Lnode *p = HEAD->next ;
    int j = 0 ;
    while(j != i){
        j++ ;
        p = p->next ;
    }
    return p->data ;
}
  • 根据值确定结点索引
int LocateElem(Linklist &HEAD , int value){
    Lnode *p = HEAD->next ;
    int i = 0 ;
    while(p){
        if(value == p->data)    return i ;
        p = p->next ;
        i++ ;
    }
    cout << value << "not in this linkedlist" << endl ;
    return -1 ;
}
  • 插入结点
void ListInsert(Linklist &HEAD , int i , int data){
    if(i < 0 || i > GetLength(HEAD))    {cout << "the index is invalid" << endl ; exit(0) ;}
    Lnode *p = HEAD ;
    int j = -1 ;
    while(p && (j!=i-1)){
        p = p->next ;
        j++ ;
    }
    Lnode *s = new Lnode ;
    s->data = data ;
    s->next = HEAD->next ;
    HEAD->next = s ;
    cout << "Insert " << data << " in the index " << '[' << i << "] successfully !" << endl ;
}

tips: 此处p = HEAD从HEAD开始,j=-1 j从-1开始,是为了i=0的特殊情况。

  • 删除元素
void DeleteElem(Linklist &L , int i){
    if(i < 0 || i >= GetLength(L))  {cout << "the index i is invalid" << endl ; exit(0) ;}
    Lnode *p = L ;
    int j = -1 ;
    while(p && (j!=i-1)){
        p = p->next ;
        j++ ;
    }
    Lnode *s = p->next ;
    p->next = s->next ;
    delete s ;

}
  • 打印链表所有元素
void PrintList(Linklist &L){
    Lnode *p = L->next ;
    while(p){
        cout << p->data << "  " ;
        p = p->next ;
    }
    cout << endl ;
}
  • 头插法创建链表
void CreateList_H(Linklist &L , int n){
    //insert the nodes from the head of linkedlist
    L = new Lnode ;
    L->next = NULL ;
    for(int i = n - 1 ; i >= 0 ; i--){
        Lnode *p = new Lnode ;
        cin >> p->data ;
        p->next = L->next ;
        L->next = p ;
    }
}
  • 尾插法创建链表
void CreateList_T(Linklist &L , int n ){
    //Insert elements from the tail of linkedlist
    L = new Lnode ;
    L->next = NULL ;
    Lnode *T = L ;
    for(int i = 0 ; i < n ; i++){
        Lnode *p = new Lnode ;
        cin >> p->data ;
        T->next = p ;
        T = T->next ;
        p->next = NULL ;
    }

双向链表

#include<iostream>
using namespace std ;
typedef struct DoubleLinkedList
{
    int data ;
    struct DoubleLinkedList *prior , *next ;
}DLNode , *DLList;
void InitDLList (DLList &HEAD){
    HEAD = new DLNode ;
    HEAD->next = NULL ;
    HEAD->prior = NULL ;
}
void CreateList_DL(DLList &HEAD , int n){
    for(int i = 0 ; i < n ; i++){
        DLNode *p = new DLNode ;
        cin >> p->data ;
        p->next = HEAD->next ;

        if(HEAD->next){
            HEAD->next->prior = p ;
        }
        //i = 0 时,插入第一个元素时,HEAD->next 为NULL, NULL是没有的,即NULL->prior是访问不到的,segmentation fault
        //因此当HEAD->next不为NULL时,才会执行HEAD->next->prior = p 
        //当HEAD->next 为NULL,也就是创建第一个结点时,不要让(也没法让)NULL->prior = p 

        HEAD->next = p ;
        p->prior = HEAD ;
    }
}
int GetLength_DL(DLList &HEAD){
    int length = 0 ;
    DLNode *p = HEAD->next;
    while(p){
        length++ ;
        p = p->next ;
    }
    return length ;
}
void PrintList_DL(DLList &HEAD){
    DLNode *p = HEAD->next ;
    for(int i = 0 ; i < GetLength_DL(HEAD) ; i++){
        cout << p->data << "  " ;
        p = p->next ;
    }
    cout << endl ;
}
void InsertList_DL(DLList &HEAD , int i , int data){
    if( i < 0 || i > GetLength_DL(HEAD))    {cout << "the index is invalid" << endl ; exit(0) ;}
    DLNode *p = HEAD ;
    for(int j = 0 ; j < i ; j++){
        p = p->next ;
    }
    DLNode *s = new DLNode ;
    s->data = data ;
    s->next = p->next ;
    if(p->next){
        p->next->prior = s ;
    }
    p->next = s ;
    s->prior = p ;

}
void DeleteElem_DL(DLList &HEAD  , int i){
    if(i < 0 || i >= GetLength_DL(HEAD))    {cout << "the index is invalid " << endl ; exit(0) ;}
    DLNode *p = HEAD->next ;
    while(i--){
        p = p->next ;
    }
    p->prior->next = p->next ;
    p->next->prior = p->prior ;
    delete p ;
}
int main(){
    DLList HEAD ;
    InitDLList(HEAD) ;
    CreateList_DL(HEAD , 6) ;
    PrintList_DL(HEAD) ;
    InsertList_DL(HEAD , 2 , 821) ;
    PrintList_DL(HEAD) ;
    DeleteElem_DL(HEAD , 1) ;
    PrintList_DL(HEAD) ;
    return 0 ;
}