您的位置: 首页  >  IT文章  >  数据结构（一）线性表相关知识拾遗

数据结构（一）线性表相关知识拾遗

分类: IT文章 • 2022-05-01 19:16:46

（一）回顾所有的线性表结构

数据结构（一）线性表相关知识拾遗

线性表的这两种存储结构是后面其他数据结构的基础。至关重要

（二）是否需要头结点？

若是我们在初始化链表时，不想直接添加数据，那么我们就需要使用到头结点。
若是我们不想用到头结点，那么我们需要在开始初始化数据的时候就带上数据。
Status InitList(CLinkList* L,int n)
{
    CLinkList rear, q;    //rear是尾结点
    ElemType item;
    rear = q = NULL;
    srand(time(0));

    for (int i = 0; i < n;i++)
    {
        item = rand() % 100;
        printf("%d ", item);
        if (*L==NULL)
        {
            *L = (CLinkList)malloc(sizeof(Node));
            if (!(*L))
                return ERROR;
            (*L)->data = item;
            (*L)->next = *L;    //自己指向自己
            rear = *L;    //设置尾指针位置
        }
        else
        {
            //生成新的节点，根据尾指针添加节点,并实时更新尾指针。注意这里数据插入是尾插法
            q = (CLinkList)malloc(sizeof(Node));
            q->data = item;
            q->next = rear->next;
            rear->next = q;
            rear = q;
        }
    }
    printf("
");
    return OK;
}
例如前面的循环链表，我们若是不需要头结点，那么最好在初始化链表时就带上部分数据 
//初始化带有头结点的链表
Status InitList(LinkList* L)
{
    *L = (LinkList)malloc(sizeof(Node));    //使头指针指向头结点
    if (*L == NULL)    //内存分配失败
        return ERROR;
    (*L)->next = NULL;    //指针域为空
    (*L)->data = 0;    //头结点数据域用来存放链表长度
    return OK;
}
例如前面的单链表，我们使用了头结点，因为我们在初始化链表的时候不去携带有关数据

（三）对于头插法，尾插法，中间插入，思考方法不一样，但是实现代码往往是一致的，思考一下，是不是只考虑简单的中间插入，即可完成上面的多种插入方法？

不要多想，结合前面的线性表链式存储实现，查看其它插入方法，更加简单。
方法无论哪种插入方法，无非都是：
1.获取我们要插入的位置
2.循环去获取我们要插入位置的前一个节点，如A节点
3.我们只需要先将插入的节点的next（这里是游标）指向A节点的原来下一个节点B
4.然后再将A的游标指向这个新的节点即可。
这种思路可以实现头插法，尾插法，中间插入。而中间插入最为容易思考，所以以后可以直接思考这种方法即可。对于删除操作大致相同，不再详说

相关实现代码预览：

数据结构（一）线性表链式存储实现（简单些）

数据结构（一）线性表静态链表（晦涩些）

数据结构（一）线性表循环链表（前两个看看即可，这个可不看）

相关推荐