菜单

次第猿必修课之数据结构(五)线性表3

2019年1月29日 - 金沙编程资讯

  

尾指针

在单链表中,有了头结点,大家可以用 O(1)
的年月拜访第四个结点,但要访问最后一个结点,却须求 O(n)
时间,因为大家要将单链表全部扫描三遍。

为了能用 O(1) 的光阴由链表指针访问到结尾一个结点
,我们须求改造一下那个循环链表,将头指针改为尾指针。

图片 1

尾指针表示链表

从图中得以看出,尾结点用尾指针 rear 提醒,则查找终端结点的时刻是 O(1),
而开端结点就是 rear->next->next,其时间复杂度也为 O(1)。

比如:有八个循环链表,它们的尾指针分别是 rearA 和
rearB,将四个循环链表合并成一个表。

p = rearA->next;
/* 将 B 表的第一个结点(不是头结点)赋值给 rearA->next */
rearA->next = rearB->next-next;
/* 将原 A 表的头结点赋值给 rearB->next */
rearB->next = p;
free(p);

图片 2

以身作则程序

1.将单链表中终端结点的指针端由空指针改为指向头结点,单循环链表,循环链表和单链表的显要差异就在于循环的判断标准上
本来是判断p->next是或不是为空,现在则是p->next不等于头结点,则循环未竣事

双向链表

在单链表中,有了 next 指针,我们寻找下一个结点的时日复杂度为
O(1),但是要物色上一个结点,那最坏的日子复杂度为
O(n),双向链表就摆平了那一个毛病。

双向链表是在单链表的每个结点,再添加一个针对性其前任结点的指针域。所以在双向链表中,每个结点都有多少个指针域,一个对准直接后继结点,另一个针对性直接四驱结点。

线性表的双向存储结构

typedef struct DulNode{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode, *DuLinkList;

3.14 双向链表

大家在单链表中,有了next指针,那就使得我们要物色下一结点的时间复杂度为O(1),不过即使大家要摸索的是上一结点的话,那最坏的时日复杂度就是O(n)了,因为我们每一回都要从头初始遍历查找。

双向链表是在单链表的各类结点中,再设置一个针对性其前任结点的指针域。所以在双向链表中的结点都有五个指针域,一个对准直接后继,另一个对准直接后驱。

图片 3

图片 4

![]()

图片 5

概括总计一下,双向链表相对于单链表来说,要更扑朔迷离一些,毕竟她多了prior指针,对于插入和删除时,须要非凡小心。

其余它由于各类节点都必要记录两份指针,所以在半空上是要占有略多一点,然而,由于它杰出的对称性,使得对某个节点的内外节点的下操作,带来了便宜,能够使得地压实算法的年月品质。简单,就是用空间来换时间

CList.h
//CList.h 
//结构体定义以及函数声明


#ifndef CLIST_H
#define CLIST_H

#include <stdio.h>
#include <assert.h>
#include <malloc.h>
#include <iostream>

typedef  int ElemType;

typedef struct Node
{
    ElemType data;
    struct Node *next;
}Node, *PNode;

typedef struct List
{
    PNode head;
    PNode tail;
    int size;
}List,*PList;

bool InitList(PList list);
void Create_t(PList list,ElemType x);             //尾插
void Create_h(PList list,ElemType x);             //头插
void del_back(PList list);                        //尾删
void del_front(PList list);                       //头删
void sortList(PList list);                        //排序
void insert_val(PList list,ElemType x);           //按值插
PNode find(PList list,ElemType x);
void del_val(PList list,ElemType x);
void modify(PList list,ElemType x1,ElemType x2);
void clear(PList list);
void destroy(PList list);
void reserve(PList list);
int length(PList list);
void menu();
void showList(PList list);
void show_tail(PList list);
ElemType next(PList list,ElemType x);
ElemType prio(PList list,ElemType x);
PNode prev(PList list,PNode p);

#endif

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图