先后猿必修课之数据结构,单循环列表

1.将单链表中终端结点的指针端由空指针改为指向头结点,单循环链表,循环链表和单链表的重中之重差别就在于循环的论断标准上
本来是判断p->next是不是为空,以往则是p->next不对等头结点,则循环未终止

原文:先后猿必修课之数据结构,单循环列表。http://www.jianshu.com/p/082eb306d228

美高梅开户网址 1

数据结构与算法-目录
美高梅开户网址,循环链表是另一种样式的链式存贮结构。它的特征是表中最后三个结点的指针域指向头结点,整个链表形成壹个环。

2.指向终点结点的尾指针代表该循环链表

上一章:程序猿必修课之数据结构(四)线性表2

线性表(三)

美高梅开户网址 2

3.创办循环链表关键是头结点指向本人,最终三个终端结点指向头结点

循环链表

对于单链表,由于各种结点只存储了向后的指针,到了链表末尾就终止了向后链的操作,这样,结点就不可以找到它的先辈结点了。

将单链表中终端结点的指针域由空指针改为指向头结点,就使全体单链表形成一个环,那种头尾相接的单链表称为单循环链表,简称循环链表。

循环链表和单链表的重点出入就在于循环的论断标准上,原来是判定 p->next
是不是为空,未来则是判断 p->next 是还是不是等于头结点。

3.13 循环链表

对此单链表,由于各种节点只存储了向后的指针,到了尾标志就为止了向后链的操作,那样,当中某一节点就不能找到它的前驱结点了。

将单链表中终端结点的指针端由空指针改为指向头结点,就使全数单链表形成多个环,那种头尾相接的单链表称为单循环链表,简称循环链表

为了使空链表与非空链表处理一致,大家常见设二个头结点。

循环链表带有头结点的空链表如图:

美高梅开户网址 3

骨子里循环链表和单链表的机要不同就在于循环的判定标准上,原来是判定p->next是或不是为空,未来则是p->next不对等头结点,则循环为终结。

美高梅开户网址 4

美高梅开户网址 5

美高梅开户网址 6

对此单个链表,由于各种结点只存储了向后的指针,到了尾标志就终止了向后链的操作,那样当中某一结点就不能找到它的先辈结点了。

将单链表中终端结点的指针由空指针改为指向头结点,就使任何单链表形成三个环,
那种头尾相接的单链表称为单循环链表,简称循环链表。

循环链表解决了1个很辛劳的难题,怎样从中间多个结点出发,访问到链表的一切结点。

循环链表和单链表的第3差异就是介于循环的判断标准上,原来是判定p->next是还是不是为空,未来则是p->next不对等头结点,则循环未截至。

<?php
class Node{
        public $data;
        public $next;
}
//创建一个链表
$linkList=new Node();
//头结点指向自身
$linkList->next=$linkList;
$temp=$linkList;
for($i=1;$i<=10;$i++){
        $node=new Node();
        $node->data="aaa{$i}";
        //最后一个结点指向头结点
        $node->next=$linkList;
        $temp->next=$node;
        $temp=$node;
}
//循环链表的遍历
function printLoopLink($linkList){
        $p=$linkList;
        //头结点
        $head=$linkList;
        //如果下一个结点是头结点代表结束
        while($p->next!=$head){
                $p=$p->next;
                print_r($p->data."  ");
        }   
}


//循环链表的优势
function printLoopLink3($linkList){
        //循环链表的优势,从第三个结点开始遍历,遍历全部链表
        $p=$linkList->next->next->next;
        $head=$linkList->next->next->next;
        while($p->next!=$head){
                $p=$p->next;
                print_r($p->data."  ");
        }   
}

printLoopLink($linkList);
printLoopLink3($linkList);

尾指针

在单链表中,有了头结点,大家可以用 O(1)
的小时拜访第三个结点,但要访问最后一个结点,却须要 O(n)
时间,因为大家要将单链表全体围观一次。

为了能用 O(1) 的小运由链表指针访问到最后1个结点
,我们须要改造一下以此循环链表,将头指针改为尾指针。

美高梅开户网址 7

尾指针表示链表

从图中得以看来,尾结点用尾指针 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);

3.14 双向链表

我们在单链表中,有了next指针,那就使得大家要摸索下一结点的光阴复杂度为O(1),不过若是大家要寻找的是上一结点的话,那最坏的年华复杂度就是O(n)了,因为我们每一回都要从头起先遍历查找。

双向链表是在单链表的种种结点中,再安装贰个针对其前任结点的指针域。所以在双向链表中的结点都有八个指针域,五个针对性直接后继,另三个针对直接前驱。

美高梅开户网址 8

美高梅开户网址 9

![]()

美高梅开户网址 10

大约总计一下,双向链表相对于单链表来说,要更扑朔迷离一些,终究他多了prior指针,对于插入和删除时,要求丰裕小心。

其它它由于每一个节点都亟需记录两份指针,所以在上空上是要并吞略多一些,可是,由于它可以的对称性,使得对有些节点的内外节点的下操作,带来了有利,可以有效地做实算法的年月质量。大致,就是用空间来换时间

演示程序

  

双向链表

在单链表中,有了 next 指针,我们探寻下三个结点的年月复杂度为
O(1),可是要寻找上3个结点,这最坏的小时复杂度为
O(n),双向链表就击溃了那些毛病。

双向链表是在单链表的各样结点,再添加3个针对性其前任结点的指针域。所以在双向链表中,每一个结点都有五个指针域,三个针对性直接后继结点,另二个针对直接前驱结点。

线性表的双向存储结构

typedef struct DulNode{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode, *DuLinkList;
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

双向链表的操作

与单链表相比较,双向链表可以反向查找数据结构,但在插入和删除时,需求改变多少个指针变量。

假定有3个结点 s,要插入到结点 p 和 p-next之间:

美高梅开户网址 11

双向链表的插入操作.png

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

若要删除1个结点,只须要多少个步骤

p->prior-next = p->next;
p->next-prior = p->prior;
free(p);

线性表复习完了,下一章起始复习栈与队列。

下一章:次第猿必修课之数据结构(六)栈1

CList.cpp
//CList.cpp 
//函数实现

#include"CList.h"

void menu()           //提供选项的菜单函数
{
    printf("***************************************************************\n");
    printf("* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *\n");
    printf("* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*\n");
    printf("* [8] find        [9] del_val    [10] sortList   [11] modify  *\n");
    printf("* [12]clear       [13]destroy    [14] resver     [15]length   *\n");
    printf("* [16] next       [17]prio                                    *\n");
    printf("***************************************************************\n");
}
bool InitList(PList list)
{
    list->head = (PNode)malloc(sizeof(Node)); //初始化一个头结点
    assert(list->head != NULL);               //断言,表达式为真,接着往下执行

    list->head->next = list->head;            //初始化head和tail指针,使其都指向头节点
    list->tail = list->head;

    list->size = 0;                           //长度初始化为0
    return true;
}

void Create_t(PList list,ElemType x)     //尾插法
{
    PNode s = (PNode)malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;                         //填充数据域
    list->tail->next = s;                //tail指向最后一个节点,把新建立的节点链接到链表的最后
    s->next = list->head;                //单循环链表,新节点的next指向头结点           
    list->tail = s;                      //改变尾指针的指向
    list->size++;
} 
void showList(PList list)            //链表显示函数
{
    if(1>list->size)
    {
        printf("--链表为空\n");
        return ;
    }
    PNode p = list->head->next;
    while(list->head != p)           //逐个遍历链表
    {
        printf("%d ",p->data);
        p=p->next;
    }
    printf("\n");
}
void Create_h(PList list,ElemType x)  //头插法
{
    PNode s = (PNode)malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;                             //填充数据域
    s->next = list->head->next;              //新节点指向第一个节点           
    list->head->next = s;                    //头节点的next指向新节点s
    if(list->size == 0)                      //如果是第一次头插,需改变尾指针和尾节点的next指向,之后都不改变
    {
        list->tail = s;
        list->tail->next = list->head;        
    }
    list->size++;        //插入一个,长度加1
}

void del_back(PList list)    //尾删
{
    if(0==list->size)
        return;
    PNode p = list->head;
    while(list->head != p->next->next)      //找到倒数第二个节点
    {
        p = p->next;
    }                      
    p->next = list->head;                   //把最后一个节点分离
    free(list->tail);                       //释放最后一个节点
    list->tail = p;                         //尾指针指向原来的倒数第二个节点(现在倒数第一)
    printf("--尾节点已删除\n");
    list->size--;
}

void del_front(PList list)   //头删
{
    if(0==list->size)
        return;
    else
    {
        PNode p = list->head->next;
        if(1==list->size) 
        {                                    //只有一个节点,若删去,需改变尾指针
            list->tail = list->head;
            list->head->next = list->head;
        }
        else
        {                
            list->head->next = p->next;      //头指针指向第二个节点    
        }
        free(p);                             //释放第一个节点
    }                            
    printf("--头节点已删除\n");
    list->size--;
}


void show_tail(PList list)     //为测试尾指针是否正确改变,需显示最后一个节点
{
    printf("--链表的尾节点是:》%d \n",list->tail->data);
}

void sortList(PList list)      // 对无序链表进行从小到大排序
{
    if(2>list->size)
        return ;
    PNode p = list->head->next;
    PNode q = p->next;
    for(int i = 0;i<list->size-1;i++,p = list->head->next,q = p->next)      //n个数比较n-1趟
    {
        for(int j = 0;j<list->size-1-i;j++,p=q,q=q->next)   //第i趟比较n-i次
        {
            if(p->data > q->data)        //如果前面的数大于后面,则交换
            {
                p->data = p->data + q->data;
                q->data = p->data - q->data;
                p->data = p->data - q->data;
            }
        }
    }
}

void insert_val(PList list,ElemType x)   //链表有序的前提下,给一个值插入
{
    PNode p = list->head->next,q = list->head;
    while(list->head != p)               //找到能插入的位置,会在p、q之间
    {   
        if(x<p->data)
            break;
        q = p;
        p = p->next;
    }
    PNode s = (PNode)malloc(sizeof(Node)); //初始化新节点
    s->data = x;
    q->next = s;              //把新节点插入到链表中(在p,q之间插入)
    s->next = p;
    if(list->head == p)       //如果新节点的值最大,即尾插,需改变尾指针和尾节点的next指向
    {
        list->tail = s;
        list->tail->next=list->head;
    }
    list->size++;
}

PNode find(PList list,ElemType x)       //返回要查找元素的前面一个的地址
{
    PNode p = list->head;
    while(list->tail != p && list->head != p->next && x != p->next->data)
    {
        p = p->next;                   //循环结束,p指向x的前面一个元素
    }                      
    if(list->head == p->next)          //如果p指向最后一个元素,说明没有找到
    {
        printf("--没找到!\n");
        return NULL;
    }
    return p;
}

void del_val(PList list,ElemType x)     //删除指定的值x
{
    if(0 == list->size)
        return ;
    PNode p = find(list,x);
    PNode q = NULL;
    if(NULL != p)
    {
        q = p->next;               //q指向要删除的节点  
        if(q == list->tail)        //若删除最后一个节点,需改变尾指针
        {
            p->next = list->head;
            list->tail = p;
        }
        else
        {
            p->next = q->next;
        }
        free(q);                  //释放要删除的节点
        list->size--;
        printf("--%d已删除!\n",x);
    }
    return ;
}

void modify(PList list,ElemType x1,ElemType x2)    //把原有的x1修改成x2
{
    PNode p = find(list,x1);
    if(NULL != p)
        p->next->data = x2;
    else
        return ;
}

void clear(PList list)       //删除链表的所有节点,但不删除头结点
{
    PNode p = list->head->next;
    PNode q = p;
    while(list->head != p)      
    {
        p = p->next;         //p依次后移,跟屁虫q依次释放节点
        free(q);
        q = p;
    }
    list->tail = list->head;   //修改尾指针和链表长度
    list->head->next = list->head;
    list->size = 0;
    printf("--链表已被清空!\n");
}

void destroy(PList list)   //摧毁链表,包括所有节点和头结点
{
    clear(list);
    free(list->head);
    list->head = NULL;
    list->tail = NULL;
    printf("--链表已被摧毁!\n");
}

PNode prev(PList list,PNode p)     //返回p指向的前面一个节点
{
    if(p != list->head)
    {
        PNode q = list->head->next;
        while(q != list->head && q->next != p)  //依次往后移,知道尾指针的前面一个节点
            q=q->next;
        if(q->next == p)
            return q;
    }
    return NULL;
}
void reserve(PList list)   //逆置链表 
{
    PNode s = (PNode)malloc(sizeof(Node));       //建立一个节点
    s->next = list->tail;
    PNode p = list->tail;
    while(list->tail != list->head->next)        //把原链表的尾节点到第一个节点依次连接到新节点上
    {
        list->tail = prev(list,list->tail);
        list->tail->next = list->head;
        p->next = list->tail;
        p=p->next;
    }
    p->next = s;              //p指向第一个节点,即新链表的最后一个节点,尾指针的next指向头结点s,链表结束
    free(list->head);         //释放原来的头结点
    list->head = s;           //把s变成新的头指针
}

int length(PList list)     //求链表的长度
{
    return list->size;
}

ElemType next(PList list,ElemType x)      //返回x的后继
{
    PNode p = find(list,x);  
    if(NULL == p) 
        return -1;
    if(p->next == list->tail)           //因为是单循环链表,尾节点的下一个元素是第一个节点
    {
        return list->head->next->data;    
    }
    p=p->next;
    return p->next->data;
}
ElemType prio(PList list,ElemType x)         //返回x的前驱
{
    PNode p = find(list,x);
    if(NULL != p)
    {
        if(p == list->head || p == list->tail)
        {
            return list->tail->data;
        }
        return p->data;
    }
    return -1;
}
main.cpp
//main.cpp 
//测试函数
#include "CList.h"

int main()
{
    List mylist;
    InitList(&mylist);
    ElemType item = 0;
    int pos = 0;
    int chose = 1;
    PNode p = NULL;
    while(chose)
    {
        menu();
        printf("给出想要操作的序号:\n");
        scanf("%d",&chose);
        switch(chose)
        {
        case 0:
            destroy(&mylist);
            chose = 0;
            break;
        case 1:
            printf("输入要尾插的数据[-1结束]:\n");
            while(scanf("%d",&item),item!=-1)
            {
                Create_t(&mylist,item);
            }
            break;
        case 2:
            printf("输入要头插的数据:\n");
            while(scanf("%d",&item),item!=-1)
            {
                Create_h(&mylist,item);
            }
            break;
        case 3:
            showList(&mylist);
            break;
        case 4:
            del_back(&mylist);
            break;
        case 5:
            del_front(&mylist);
            break;
        case 6:
            printf("给出要插入的数:\n");
            scanf("%d",&item);
            insert_val(&mylist,item);
            break;
        case 7:
            show_tail(&mylist);
            break;
        case 8:
            printf("输入要查找的数:\n");
            scanf("%d",&item);
            p = find(&mylist,item);
            if(NULL!=p)
                printf("%d\n",p->next->data);
            break;
        case 9:
            printf("输入要删除的数:\n");
            scanf("%d",&item);
            del_val(&mylist,item);
            break;
        case 10:
            sortList(&mylist);
            break;
        case 11:
            printf("输入要修改的数和修改后的数\n");
            scanf("%d %d",&item,&pos);
            modify(&mylist,item,pos);
            break;
        case 12:
            clear(&mylist);
            break;            
        case 13:
            destroy(&mylist);
            break;
        case 14:
            reserve(&mylist);
            break;
        case 15:
            printf("链表长度为:%d\n",length(&mylist));
            break;
        case 16:
            printf("输入想要找哪个一数的后继:\n");
            scanf("%d",&item);
            printf("%d 的后继是:%d\n",item,next(&mylist,item));
            break;
        case 17:
            printf("输入想要找哪个一数的前驱:\n");
            scanf("%d",&item);
            printf("%d 的前驱是:%d\n",item,prio(&mylist,item));
            break;
        default:
            printf("重新输入\n");
            break;
        }   
    }
    return 0;
}

运作测试:

***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
1
输入要尾插的数据[-1结束]:
5 6  9 2 8 2 6 -1
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
3
5 6 9 2 8 2 6
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
8
输入要查找的数:
2
2
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
7
--链表的尾节点是:》6
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
10
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
3
2 2 5 6 6 8 9
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
14
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
3
9 8 6 6 5 2 2
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
16
输入想要找哪个一数的后继:
8
8 的后继是:6
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
12
--链表已被清空!
***************************************************************
* [0] quit_system [1] Create_t   [2] Create_h    [3] showList *
* [4] del_back    [5] del_front  [6] insert_val  [7] show_tail*
* [8] find        [9] del_val    [10] sortList   [11] modify  *
* [12]clear       [13]destroy    [14] resver     [15]length   *
* [16] next       [17]prio                                    *
***************************************************************
给出想要操作的序号:
3
--链表为空

发表评论

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

网站地图xml地图