当前位置:首页 > 数据结构与算法 > 正文内容

单链表

admin12个月前 (10-07)数据结构与算法250

单链表存储一个直接后继的地址,用一组任意的存储单元存储线性表中的元素。

数据域(数据元素)+指针域(指示后继元素存储位置) = 结点,如下图:a和b是两个结点,其中a的指针域保存了指向b的地址。

image.png

以结点的序列表示线性表 称为链表

以线性表中第一个数据元素a1的存储地址作为线性表的地址,称作线性表的头指针。

有时候为了操作方便,在第一个结点之前虚加一个“头结点”,并用链表的头指针指向头结点,称为带带头结点的单链表。

单链表查找指定位置上的数据:

从头结点开始,顺着链表各个结点的next指针一直找到对应的位置,返回对应的数据。

单链表的插入操作:

插入元素首先找到要插入位置的前一个结点a,然后建立新结点,将新结点的指针域指向a结点的next结点,在将a结点的next结点指向新结点。

image.png

单链表删除指定位置上的数据:

先找到要删除结点的前一个元素a,然后将a的next指针指向要删除结点的next位置,最后时放掉结点。

image.png

其它操作不详述,下面是代码:

这里用了头结点,指向第一个结点,头结点中的数据用来存放整个链表结点的个数,可能与网上其它的代码不是很一样,但是思想是一致的。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

//定义链表的节点
struct Node
{
    int data;
    struct Node *next;
};

typedef struct Node Node;
//链表的头,指点第一个结点(如果有的话),存储的内容是链表元素的个数
typedef struct Node *LinkList;

//初始化单链表
void InitialList(LinkList *L);
//单链表添加元素
void PushElement(LinkList *L, int pos, int elem);
//创建结点
Node *CreateNode(int elem);
//在首部插入结点
void PushFront(LinkList *L, int elem);
//删除首部的元素
void PopFront(LinkList *L);
//在尾部插入结点
void PushBack(LinkList *L, int Elem);
//删除尾部的元素
void PopBack(LinkList *L);
//查找某个位置的元素
int FindElemAtPos(LinkList *L, int pos);
//删除指定位置的元素
void PopElement(LinkList *L, int pos);
//输出所有元素
void viewlist(LinkList *L);

int main()
{
    LinkList L;
    InitialList(&L);
    PushFront(&L, 100);
    PushFront(&L, 200);
    PushElement(&L, 1, 300);
    PushBack(&L, 500);

    for (int i = 0; i < 10; i++)
    {
        PushFront(&L, i);
    }

    viewlist(&L);
    printf("\nThe element at pos 11 is %d\n", FindElemAtPos(&L, 11));

    printf("\nPop the element at pos 6:\n");
    PopElement(&L, 6);
    viewlist(&L);

    printf("\nPop the front element:\n");
    PopFront(&L);
    viewlist(&L);

    printf("\nDelete the element at back:\n");
    PopBack(&L);
    viewlist(&L);

    printf("\nThe number of elements is %d\n", (*L).data);
    system("pause");
    return 0;
}

void InitialList(LinkList *L)
{
    (*L) = (Node *)malloc(sizeof(Node));
    (*L)->data = 0;
    (*L)->next = NULL;
}

void PushElement(LinkList *L, int pos, int elem)
{
    int temppos = 0;
    Node *p = (*L);

    while (temppos != (pos - 1))
    {
        p = p->next;
        temppos++;
    }
    Node *newNode = CreateNode(elem);
    newNode->next = p->next;
    p->next = newNode;

    (*L)->data++;
}

Node *CreateNode(int elem)
{
    Node *p = (Node *)malloc(sizeof(Node));
    p->data = elem;
    p->next = NULL;
    return p;
}

void PushFront(LinkList *L, int elem)
{
    Node *newNode = CreateNode(elem);
    newNode->next = (*L)->next;
    (*L)->next = newNode;
    (*L)->data++;
}

void PopFront(LinkList *L)
{
    Node *P = (*L)->next;
    (*L)->next = P->next;
    free(P);
    (*L)->data--;
}

void PushBack(LinkList *L, int Elem)
{
    Node *newNode = CreateNode(Elem);
    Node *tempNode = (*L);
    while (tempNode->next != NULL)
    {
        tempNode = tempNode->next;
    }
    tempNode->next = newNode;

    (*L)->data++;
}
void PopBack(LinkList *L)
{
    Node *tempNode = (*L);

    if (tempNode->next == NULL)
    {
        return;
    }

    while (tempNode->next->next != NULL)
    {
        tempNode = tempNode->next;
    }
    free(tempNode->next);
    tempNode->next = NULL;
    (*L)->data--;
}

void viewlist(LinkList *L) 
{
    Node *p;
    if ((*L)->next == NULL)
    {
        printf("\nlist is empty");
    }
    else
    {
        p = (*L)->next;
        while (p != NULL)
        {
            printf("%d ", p->data);
            p = p->next;
        }
    }
}

int FindElemAtPos(LinkList *L, int pos)
{
    int temppos = 0;
    Node *p = (*L);

    while (temppos != pos)
    {
        p = p->next;
        temppos++;
    }
    return p->data;
}

void PopElement(LinkList *L, int pos)
{
    Node *p = (*L);
    int temppos = 0;
    while (temppos != (pos - 1))
    {
        p = p->next;
        temppos++;
    }
    Node *atpos = p->next;
    p->next = atpos->next;
    free(atpos);

    (*L)->data--;
}

20201008更

想到一个问题,网上搜到的资料说链表的插入时间复杂度是O(1),但是真的是O(1)吗,在第n个位置插入元素时首先要定位到n-1个结点,这是个查找的过程,复杂度是O(n),只是插入的过程是常数时间,但是如果要插入好多元素呢,这时候的差别就体现出来了,关于这个问题知乎有相似的问题:https://www.zhihu.com/question/51545092


版权声明:本文由cyhu's essay发布,如需转载请注明出处。

本文链接:https://lovedm.club/?id=93

相关文章

中缀表达式转后缀表达式

中缀表达式转后缀表达式

转换过程如下:1、运算数:直接输出;2、左括号:压入堆栈;3、右括号:将栈顶的运算符弹出并输出,直到遇到左括号(出栈,不输出);4、运算符:若优先级大于栈顶运算符时,则把它压栈;若优先级小于等于栈顶运...

C# 二叉树

C# 二叉树

这里实现了二叉树的创建与插入结点,前中后序遍历的递归实现以及前序遍历的非递归实现,层序遍历的非递归实现。插入结点时采用二叉排序树的方式,没有处理有相同结点时的情况,按下面代码中插入结点时,构成的二叉树...

线性表

线性表

线性表(linear list)是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号,其具体含义在不同的情况下一般不同。1.集合中必存在唯一的一个“第一元素”。...

线性表的顺序结构(顺序表)

线性表的顺序结构(顺序表)

顺序表,线性表的一种,其存储时需要开辟一块足够大的连续的空间,数据之间的存放是相连的,中间没有空隙。顺序表的初始化:需要指定顺序表的大小,这个大小要足够大,还要将元素个数初始化为0。按照位置查找元素:...

数据结构

数据结构

数据结构:逻辑结构:反映数据元素之间的逻辑关系。包括:集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系。线性结构:数据结构中的元素存在一对一的相互关系。树形结构:数据结构中的...

二分查找

二分查找

使用二分法对数组进行元素的搜索,返回查找的元素索引,当然使用二分搜索的前提是数组已经完成排序。原始数组有10个元素,要搜索的元素是11。整个排序过程如下:首先原始数组如下:第一次两个指针位置如下:低指...