数据结构与算法——单链表

时间：2021-09-07 09:47:35

建立链表（C语言）

typedef struct LNode{  //结点数据类型定义
    ElemType data;     //数据域
    struct LNode *next;//指针域，指向下一个数据元素
}LinkList;

单链表

建立

  • 尾插法
void CreateLinkList(LinkList *&L,ElemType a[],int n)
/*因为要修改到main函数中的链表，所以这里有用到引用（指针引用）*/
{
    LinkList *s,*r;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));     //创建头结点
    r=L;                                        //r始终指向尾结点
    for(i=0;i<n;i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList)); //创建新的结点
        s->data = a[i];                         //将a[i]中的数据存入新的结点
        r->next = s;                            //将s结点插入到r后
        r=s;                                    //保证r始终指向链表的尾结点
    }
    r->next=NULL;                               //尾结点next置空为 NULL
}//时间复杂度O(n),n为数据结点个数
  • 头插法
void CreateLinkList(LinkList *&L,ElemType a[],int n)
/*因为要修改到main函数中的链表，所以这里有用到引用（指针引用）*/
{
    LinkList *s;
    int i;
    L=(LinkList *)malloc(sizeof(LinkList));     
    L->next = NULL;                             //创建头结点,L的next域始终为空
    for(i=0;i<n;i++)
    {
        s=(LinkList *)malloc(sizeof(LinkList)); //创建新的结点
        s->data = a[i];                         //将a[i]中的数据存入新的结点
        s->next = L->next;                      //置空新的结点的next域
        L->next = s;                            //将新的结点插入到链表
    }

}时间复杂度O(n),n为数据结点个数

删除

bool ListDelete(LinkList *&L,int n,int i,ElemType &e)
/*在单链表L中，长度为n，删除第i个结点，并用e返回其数据域的值*/
{
    LinkList *p=L,*q;
    int j=0;
    if(i<1||i>n) return false;
    while(p!=NULL&&j<i-1)           //在单链表中寻找第i-1个结点
    {
        j++;
        p = p->next;
    }
    if(p == NULL) return false;     //没找到第i-1个结点
    else                            //找到第i-1个结点
    {
        q = p->next;                //q指向第i个结点
        if(q == NULL) return false; //不存在则返回false
        e = q->data;                //返回数据域值
        p->next = q->next;          //删除第i个结点
        free(q);                    //释放空间
        return true;
    }
}//时间复杂度O(n),n为数据结点个数

循环链表

  • 意义

单链表在插入和删除的时候需要找到进行操作结点的前驱，而单链表只能从头结点开始循环遍历，如果进行操作的结点靠后，浪费资源；
循环链表中可以从表中的任一结点出发都可以找到其他的结点

  • 实现

循环链表将最后一个结点的指针域指向头结点，整个链表形成一个环 

r->next=L;   //与单链表的不同点在于单链表的结尾是NULL；而循环链表是 L

双向链表

  • 意义

在单链表或循环链表结点中，只有一个指示后继的指针域，因此如果要找到一个结点只能顺指针寻找，要找到该结点的前前驱也要重新顺指针寻找前一个结点

  • 存储表示

在结构类型定义的时候增加一个数据域指向前驱

typedef struct DulNode{
    ElemType data;         //数据域
    struct DulNode *per;   //前向指针域
    struct DulNode *next;  //后向指针域
}DuLinkList;
  • 插入
bool ListInsert_DuL(DuLinkList *&L,int i,ElemType &e)
{
    int j=0;
    DuLinkList *p=L,*s;
    while(j<i && p!=NULL)    //查找第i个结点
    {
        j++;
        p = p->next;
    }
    if (p == NULL)  return false;    //未找到第i个结点
    else                             //找到第i个结点* p，在其前面插入新结点
    {
        s=(DuLinkList *)malloc(sizeof(DuLinkList));   //创建新结点
        s->data = e;       //导入数据到数据域
        s->per = p->per;   //将p的前驱结点放入新结点s的前向指针域
        s->next = p;       //将p放入新结点的后向指针域
        p->per->next = s;  //修改p的前驱结点的后向指针
        p->per = s;        //修改p的前向指针
        return true;
    }
}//时间复杂度O(n),n为数据结点个数
  • 删除
bool ListDelete_DuL(DuLinkList *&L,int i,ElemType &e)
{
    int j=0;
    DuLinkList *p=L,*s;
    while(j<i && !=NULL)//查找第i个结点
    {
        j++;
        p = p->next;
    }
    if(p == NULL) return false;//未找到则返回false
    else
    {
        e = p->data;             //取出p中的数据域
        p->per->next = p->next;  //修改p的前驱结点的反向指针
        p->next->per = n->per;   //修改p的后继结点的前向指针
        free(p);                 //释放p结点
        return true;
    }
}//时间复杂度为O(n),n为数据结点个数

其他相关知识点

  • 单链表只能寻找后继，不能访问前驱
  • 存储密度=结点数据所占空间 / 结点占用的空间总量
  • 在单链表中，插入一个结点必须先找到插入结点的前驱结点
  • 删除时要记得使用free函数： free(LinkList *q);
  • 在进行插入或删除操作时要判断 i 的存在与否
  • 链式存储结构的最大特点就是逻辑上相邻的两个元素在物理位置上不一定相邻
标签：

相关文章