[数据结构与算法]单链表(一些基本操作）

目录

1.单链表的定义。

2.定义一个为L的单链表。

3.交换第k个节点，和第k+1个节点的值。

4.如果有LNode *p,*s,若p指向其中一个节点（该节点不为空），s指向一个新的节点，要求：

(1).在p后面插入节点s。

(2).在p节点前插入s。

第一种方法：

第二种方法：

?5.求单链表的长度

6.按下标取单链表中的某个元素。

7.按值查找操作。

8.插入元素

9.删除操作

10.建立单链表

(1).头插法

(2).尾插法

?

1.单链表的定义。

typedef struct LNode{
    int data; 
    struct LNode *next;
}LNode,*LinkList;

2.定义一个为L的单链表。

LNode *L;//或者LinkList L;

3.交换第k个节点，和第k+1个节点的值。

bool change(LinkList L,int k)
{
    LNode *p=L;//让p指向头节点

    int j=0; //计数器，帮助找到第k个节点

    while(p->next!=NULL&&j<k)//遍历链表，直到找到第k个节点
    {
        p=p->next;
        j++;
    }

    if(!(p->next)&&j>k) //需要保证p的后继节点存在
        return false;
    
    //交换k和k+1节点的值
    int x=p->data;
    p->data=p->next->data;
    p->next->data=x;

    return true;
}

4.如果有LNode *p,*s,若p指向其中一个节点（该节点不为空），s指向一个新的节点，要求：

(1).在p后面插入节点s。

s->next=p->next;
p->next=s;

(2).在p节点前插入s。

第一种方法：

遍历找到p前面的节点。

void insert()
{
    LNode *q=L;
    while(q->next!=p) q=q->next;
    s->next=q->next;//或者s->next=p;
    q->next=s;
}

时间复杂度为O(n),空间复杂度为O(1)。

第二种方法：

假设原来的序列是x，y，p指向y，需要在y前面插入一个节点s，此时顺序为x，s，y，如y后面插入节点s?，那么此时的顺序为x，y，s，我们发现只要交换y和s节点的数据域即可。

void insert()
{
    //在p后面插入节点
    s->next=p->next;
    p->next=s;
    
    //交换节点p和s的数据域,此时s就是p后面的一个节点
    int x=p->data;
    p->data=p->next->data;
    p->next->data=x;
    
}

时间复杂度为O(1),空间复杂度为O(1)。

?5.求单链表的长度

遍历链表即可。

int Listlength(LinkList L)
{
    int j=0;
    LNode *p=L;
    while(p->next!=NULL)
    {
        j++;
        p=p->next;
    }
    return j;
}

6.按下标取单链表中的某个元素。

遍历找到下标。

bool GetElem(LinkList L,int i,int &e)//因为需要把值传回去，加&
{
    LNode *p=L;
    int j=0;
    while(p&&j<i)
    {
        p=p->next;
        j++;
    }
    if(!p||j>i) return false;
    e=p->data;
    return true;
}
//时间复杂度O(n)

7.按值查找操作。

该操作需要依次用单链表中的元素与所给数据进行比较。

具体方法：设置一个指针p依次指示每个节点，比较e和p所指节点的值，如果p->data==e,表示查找成功，返回该元素的地址；否则继续进行搜索，直到表尾；如果没有找到，表示查找失败，返回NULL

LNode &LocateElem(LinkList L,int e)
{
    LNode *p;
    p=L->next;
    while(p!=NULL&&p->data!=e)
        p=p->next;
    if(!p) return NULL:
    return p->next;
}

8.插入元素

//基本操作
s=new LNode;
s->data=e;
s->next=p->next;
p->next=s;

完整代码：

bool ListInsert(LinkList &L,int i,int e)//在i之前插入一个节点
{
    LNode *p=L;
    int j=0;

    while(p&&j<i-1)//找到i-1节点
    {
        p=p->next;
        ++j;
    }

    if(!p||j>i-1) //参数不合法，i小于1或者大于表长+1
        return false;

    s=new LNode; //创建新节点

    if(!s) exit(-2);//创建失败

    s->data=e;
    s->next=p->next;
    p->next=s;

    return true;
}

9.删除操作

假设删除第i个节点后面的节点，假设p指向第i个节点，那么之间p->next=p->next->next;

bool ListDete(LinkList &L,int i,int &e)
{
    LNode *p=L;
    int j=0;
    while(p->next&&j<i-1)//寻找i-1个节点，并令p指向该结点
    {
        p=p-next;
        ++j;
    }
    
    if(!(p->next)||j>i-1) return false;
    
    LNode q=p->next;
    p->next=q->next;
    e=q->data;
    delete q;    //释放空间

    return true;
}

10.建立单链表

(1).头插法

顺序相反，如果插入顺序是x,y,z,在单链表中是z，y，x。

void GreateList(LinkList &L,int n)
{
    L=(LNode *)malloc(sizeof(LNode));
    L->next=NULL;
    for(int i=0;i<n;i++)
    {
        p=new LNode;
        cin>>p->data;
        p->next=L->next;
        L->next=p;
    }
}

(2).尾插法

顺序相同。

void GreateList(LinkList &L,int n)
{
    L=new LNode;
    LNode r=L;
    for(int i=0;i<n;i++)
    {
        p=new LNode;
        cin>>p->data;
        r->next=p;
        r=p;
    }
    r->next=NULL;//将尾结点置空
}