链表概述

  • 包含单链表,双链表,循环单链表,实际应用中的功能不同,但实现方式都差不多。
  • 链表中的数据是以结点来表示的,每个结点由数据域和指针域构成。

其中DATA为自定义的数据类型,NEXT为指向下一个链表结点的指针,通过访问NEXT,可以引导我们去访问链表的下一个结点。

  • 头指针与头结点的异同
    • 头结点:放在第一个元素结点之前,数据域一般无意义。头结点是为了在对第一个元素结点前插入和删除时,操作和其他结点一样,避免分开讨论。且有头结点的话,空表时也存在一个头结点,因此空表和非空表的处理才能一样,不用分开讨论。
    • 头指针:是指向第一个结点的指针(有头结点则指向头结点,没头结点则指向首结点)。是链表的必要元素,不论链表是否为空,头指针均不能为空。第一个元素结点就是通过头指针去找到的——只需要头指针,通过头指针我们可以推算出链表其他所有信息。
  • 链表的插入和删除的时间复杂度都是O(1)查找的时间复杂度是O(N),因为不具有随机存储特性。
  • 频繁改动——用链表,频繁查找——用顺序表

定义单链表结构体

typedef struct LNode
{
    int data;
    struct LNode * next;
}LinkNode;

这里的typedef和定义顺序表时有些不太一样,定义顺序表:

typedef struct
{
int * data; //存数组第一个元素的地址
int listSize; //数组最大长度
int length; //有效长度
}SqList;

要搞清楚为什么写得不一样就需明白typedef的本质

typedef小结:

typedef主要是用来给变量定义一个新的别名。 比如:开头写typedef int a,b ,代码中就可以用a、b来代替int

struct 和struct node都是一种数据类型,所以都可以用typedef定义别名。这两个的本质都是一样的,那为什么定义链表要加LNode呢?因为顺序表有没有结构体类型名字无所谓,但链表的指针域指向的结点类型是它本身,而struct 是关键字,不能写struct * next,所以需要给struct加一个结构体类型名LNode,写成struct LNode * next,其实就是给结构体加个类型名防止调用的时候混淆,本质都是用typedef 变量 别名。

扩展:定义链表最后LinkNode后可以加一个*pNode,写成LinkNode,*pNode,*pNode相当于struct LNode * 以及LinkNode * 的别名,因为要找下一个结点要频繁写这个指针变量 struct LNode * ,所以也可以给它起一个别名。

单链表

因为一般常见的链表都有头结点,所以下面的情况均按有头结点写的

1.建立单链表(把一个数组里的元素赋值给单链表)

法一:头插法(常用)

void CreateListF(LinkNode *&L,ElemType a[],int n)   //a[]为数组,n为要从数组传进去的个数
{
    LinkNode * s;   //定义一个空结点,用于下面循环赋值。
    L = (LinkNode *) malloc(sizeof(LinkNode));
    L->next = NULL; //创建头结点,指针域赋为空
    for(int i=0;i<n;i++)
    {
        s = (LinkNode *) malloc(sizeof(LinkNode));  //每次循环都定义一个新结点来存放数
        s->data = a[i];
        s->next = L->next;
        L->next = s;
    }
}

法二:尾插法

void CreateListR(LinkNode *&L,ElemType a[],int n)
{
    LinkNode *s,*r;     //s用于循环建立新的结点,r用于指向尾结点,来标志尾插法插入位置
    L = (LinkNode *) malloc(sizeof(LinkNode));  //创建一个头结点
    r = L ; //给r结点分配空间
    for(int i=0;i<n;i++)
    {
        s = (LinkNode *) malloc(sizeof(LinkNode));
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
}

2.销毁链表

释放链表L的空间,即逐一释放全部结点

注:销毁时需定义两个结点,一个存要删的结点,一个存要删的下一个结点

void  DestroyList(LinkNode *&L)
{
    //定义指针pre用于遍历删除所有结点,定义指针p为pre的后一个结点,防止pre释放后找不到下一个结点
    LinkNode *pre = L;    
    LinkNode *p = L->next; 
    while(p != NULL)    //扫描整个链表
    {
        free(pre);
        pre = p;
        p = pre->next;
        }
    free(L);
}

3.判断是否为空

只需要判断头结点L的指针域是否为空。

注:可能容易想到定义一个整数n作为计数器,但是直接看头结点的指针域是不是空即可

bool ListEmpty(LinkNode *L)
{
    return(L->next==NULL);
}

4.求链表长度

定义一个n作为计数器遍历链表即可

int ListLength(LinkNode *L)
{
    int n = 0;    //计数器
    LinkNode *p = L;    //p指向头结点
    while(p->next != NULL)
    {
        n++;
        p = p->next;
    }
    return n;
}

5.遍历输出线性表

跟上面写得一样,先p指向头结点,然后遍历条件p->next != NULL

void DispList(LinkNode *L)
{
    LinkNode *p = L->next;    //区别1:p指向首结点
    while(p != NULL)          //区别2
    {
        printf("%d ",p->data);
        p = p->next;
    }
    printf("\n");
}

6.按索引查找获取元素值

遍历前i-1个,找到第i个。

注:不要漏了超出范围情况(p==NULL)的判断

bool GetElem(LinkNode *L, int i, ElemType &e)    //i表示第几个结点,e表示获取的值
{
    LinkNode *p = L;    //p指向头结点
    for(int j=0;j<i;j++)
        p = p->next;
    if(p == NULL)   //p遍历到最后都没找到,说明i超过链表长度
        return false;
    else
    {
        e = p->data;
        return true;
    }
}

7.按元素值查找获取索引

int LocateElem(LinkNode *L, ElemType e)   //e为要查找的值
{
    int i = 1;   //要返回的逻辑序号
    LinkNode *p = L->next;  //p指向首结点
    while(p != NULL && p->data != e)
    {
        p = p->next;
        i++;
    }
    if(p == NULL)
        return 0;
    else
        return i;
}

8.插入结点

步骤:给新结点分配空间,遍历到要插入的位置,插入(s->next=p->next;p->next = s; 顺序一定不能反)

bool LisInsert(LinkNode *L, int i, ElemType e)   //i为位置,e为插入的内容
{
    LinkNode *p = L;
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode)); //要插入的新结点
    s->data = e;
    for(int j=0;j<i;j++)
        p->next;
    if(p == NULL)   //说明i超过了链表长度
        return false;
    else            //只要找到第i-1个结点了,插入新结点即可
    {
        s->next = p->next;
        p->next = s;
        return true;
    }
}

9.删除结点

bool ListDelete(LinkNode *L, int i, ElemType &e)
{
    int j=0;
    LinkNode *p = L;
    LinkNode *q;
    if(i<0)
        return false;
    while(j<i-1 && p!=NULL)    //找到逻辑序号第i个元素的位置
        {
            j++;
            p = p->next;
        }
    if(p==NULL)
        return false;
    else
    {
        q=p->next;
        e = q->data;
        p->next = q->next;
        free(q);
        return true;
    }
}

扩:单链表原地逆置

方法一:循环改变所有的指针域(自己想的)

代码:

void reverse(LinkNode *&L) {
    LinkNode *p = L->next->next, *q;
    L->next->next = NULL;
    while (p != NULL) {
        q = p->next;        
        p->next = L->next;  
        L->next = p;
        p = q;
    }
}

方法二:类似头插法(课件)

代码:

void reverse(LinkNode *&L) {
    LinkNode *p=L->next,*q;
    L->next=NULL;
    while  (p!=NULL) {
        q=p->next;		//临时保存p的后继结点
        p->next=L->next;	//将p结点插入表头(头插法)
        L->next=p;
        p=q;
    }
}

图解:

假如初始链表:

第一次while循环后:

第二次while循环后:

最后:

循环单链表

循环单链表是单链表的尾结点指针域指向一个结点。

循环单链表用于:求解一些循环问题(如约瑟夫环);只在首尾插入元素(单链表在尾部操作需遍历整个链表,或者设头尾两个指针,循环单链表只要设一个尾指针即可)。

注:只有尾指针的循环单链表在头结点插入删除、以及尾结点插入的时间复杂度都是O(1),但在尾结点删除的时间复杂度是O(n),因为删除要找到它的前驱结点,无法用尾指针直接找到尾结点的前驱结点,还是要遍历整个链表。

循环单链表在定义结构体跟单链表完全一样。

初始化时,区别在于:单链表是L->next = NULL,而循环单链表是L->next = L

几个基本运算也和单链表类似,只需要把原本循环的判断条件 p和NULL 的关系换成 p和L 的关系即可。例如:遍历输出时的循环条件 while(p != NULL) 换成 while(p != L) 即可。

循环双向链表

双向链表改进了单链表寻找一个结点的前驱结点时需遍历整个链表的不足,但是每个结点都要维护prior和next两个指针。

只带首指针或尾指针的循环双链表是在链表首尾结点插入删除最好的结构,时间复杂度均为O(1)。

1.定义循环双链表结构体

typedef struct DNode {		
    ElemType data;			
    struct DNode *prior, *next;	//后继与前驱结点指针
} DLinkNode;

2.循环双链表初始化

void initDList ( DLinkNode *&L ) {
//建立循环双链表的头结点, 并形成空表
    L = (DLinkNode*) malloc(sizeof (DLinkNode));
    L->next = L;
    L->prior = L;
}

3.循环双链表插入结点

bool ListInsert(DLinkNode *&L, int i, ElemType e) {
    DLinkNode *p=L,*s;	 //p指向头结点
    int j=0;		
    while (j<i-1 && p->next != L) {  //查找第i-1个结点
        j++; 
        p=p->next;
    }
    if (j<i-1)		    //未找到第i-1个结点
        return false;	//返回false
    else {		        //找到第i-1个结点p,在其后插入新结点s
        s=(DLinkNode *)malloc(sizeof(DLinkNode));
        s->data=e;			//创建新结点s
        s->next=p->next;	//在p之后插入s结点
        p->next->prior=s;	
        s->prior=p;
        p->next=s;
        return true;
    }
}

4.循环双链表删除结点

bool ListDelete (DLinkNode *&L, int i, DataType& x) {
//在带头结点的循环双链表中删除第i个结点。
//被删元素的值通过引用参数x返回。
    DLinkNode *p = L;
    int j = 0;
    while (j < i && p->next != L) {//定位第i个结点
        j++; p = p->next;
    }
    if (j<i)	//不存在第i个结点
        return false;
    p->prior->next = p->next;
    p->next->prior = p->prior;
    x = p->data;  
    free (p); 
    return true;
}