【基础】5、链表（三）

2014-02-05 | 阅读：

单向循环链表

一、单向循环链表示例图

多节点

单节点

二、单向循环链表节点的添加与删除

- (void)add:(int)index element:(nonnull id)element {
    [self rangeCheckForAdd:index];
    
    /**
     需要考虑多种情况下的适用性问题：
        1、中间位置
        2、头、尾位置
        3、首次添加
     */
    
    //first -> node0 -> node1 -> node2 -> first
    
    if (index == 0) {
        //分两种情况：_size==0 和 _size !=0
        LCNode * newFirst = [LCNode nodeWithElement:element next:_first];
        LCNode * last =(_size == 0)?newFirst:[self nodeForIndex:_size-1];
        
        last.next = newFirst;
        _first = newFirst;
    }else{
        LCNode * preNode = [self nodeForIndex:index-1];
        preNode.next = [LCNode nodeWithElement:element next:preNode.next];
    }
    _size++;
}

- (nonnull id)remove:(int)index {
   
    [self rangeCheck:index];
    
    /**
     需要考虑多种情况下的适用性问题：
        1、中间位置
        2、头、尾位置
        3、删除的是最后一个节点（此处还需要考虑消除循环引用）
     */
    
    //first -> node0 -> node1 -> node2 -> first
    
    LCNode * node = _first;
    if (index == 0) {
        //分两种情况：_size == 1 和 _size != 1
        if (_size == 1) {
            _first.next = nil;
            _first = nil;
        }else{
            LCNode * newFirst = _first.next;
            LCNode * last = [self nodeForIndex:_size-1];
            
            last.next = newFirst;
            _first = newFirst;
        }
    }else{
        LCNode * preNode = [self nodeForIndex:index-1];
        node = preNode.next;
        preNode.next = node.next;
    }
    
    _size--;
    return node.element;
}

双向循环链表

一、双向循环链表示例图

多节点

单节点

二、双向循环链表节点的添加与删除

- (void)add:(int)index element:(nonnull id)element {
    [self rangeCheckForAdd:index];
    
    if (index == _size) {
        LCNode * oldLast = _last;
        _last = [LCNode nodeWithElement:element next:_first prev:oldLast];
        
        if (oldLast == nil) {//这是链表添加的第一个元素
            _first = _last;
            _first.next = _first;
            _first.prev = _first;
        }else{
            oldLast.next = _last;
            _first.prev = _last;
        }
        
    }else{
        LCNode * next = [self nodeForIndex:index];
        LCNode * prev = next.prev;
        LCNode * node = [LCNode nodeWithElement:element next:next prev:prev];
        next.prev = node;
        prev.next = node;
        
        if (next == _first) {//或者使用 index == 0 判断
            _first = node;
        }
    }
    
    _size++;
}

- (nonnull id)remove:(int)index {
    
   
    [self rangeCheck:index];
    
    LCNode * node =_first;
    if (_size == 1) {
        _first.next = nil;
        _first.prev = nil;
        _first = nil;
    }else{
        node = [self nodeForIndex:index];
        LCNode * prev = node.prev;
        LCNode * next = node.next;
        
        prev.next = next;
        next.prev = prev;
        
        if (node == _first) {//index == 0
            _first = next;
        }
        
        if (node == _last) {//index = size -1
            _last = prev;
        }
    }

    

    _size--;
    return node.element;
}

约瑟夫问题（Josephus Problem）

LCJosephusProblem.h文件

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface LCJosephusProblem : NSObject

/// 约瑟夫问题，返回被kill顺序
/// @param count 人数
/// @param num 被kill的数字
-(NSString*)josephusProblemWithPeopleCount:(int)count number:(int)num;


@end

LCJosephusProblem.m文件

#import "LCJosephusProblem.h"
#import "LCNode.h"
#import "LCBothCycleLinkArray.h"

@interface LCJosephusProblem()
@property(nonatomic,strong)LCBothCycleLinkArray * bothCycleLink;
@property(nonatomic,strong)LCNode * current;
@end


@implementation LCJosephusProblem

/// 约瑟夫问题，返回被kill顺序
/// @param count 人数
/// @param num 被kill的数字
-(NSString*)josephusProblemWithPeopleCount:(int)count number:(int)num{
    
    self.bothCycleLink = [[LCBothCycleLinkArray alloc] init];
    
    
     //构建约瑟夫模型
     for (int i=1; i<=count; i++) {
         [self.bothCycleLink add:@(i)];
     }
     NSLog(@"%@",self);
     
     //
    [self reset];
    NSMutableString * mString = [[NSMutableString alloc] init];
     while (self.current.next != self.current) {
         for (int i=0; i<num-1; i++) {
             [self next];
         }
         LCNode * removeNode = [self remove];
         NSLog(@"%@",removeNode);
         NSNumber * number = removeNode.element;
         [mString appendFormat:@"%d,",number.intValue];
     }
     return mString;
}


///让 current 指向头结点 first
-(void)reset{
    self.current = self.bothCycleLink.first;
}


///让 current 往后走一步，也就是 current = current.next
-(LCNode*)next{
    LCNode * oldCurrent = self.current;
    self.current = _current.next;
    return oldCurrent;
}


///删除 current 指向的节点，删除成功后让 current 指向下一个节点
-(LCNode*)remove{
   LCNode * oldCurrent = [self next];
    [self.bothCycleLink remove:[self.bothCycleLink indexOf:oldCurrent.element]];
    return oldCurrent;
}


@end

静态链表

前面所学习的链表，是依赖于指针（引用）实现的,有些编程语言是没有指针的，比如早期的 BASIC、FORTRAN 语言,没有指针的情况下，如何实现链表？

可以通过数组来模拟链表，称为静态链表

数组的每个元素存放 2 个数据：值、下个元素的索引

数组 0 位置存放的是头结点信息

◼ 思考：如果数组的每个元素只能存放 1 个数据呢？

那就使用 2 个数组，1 个数组存放索引关系，1 个数组存放值

行者常至，为者常成！

JHHK