线性表

• 具有n个相同类型元素的有限序列（n>=0）

1.png

a1是首节点 an是尾节点

常见的线性表

• 数组
• 链表
• 栈
• 队列
• 哈希表(散列表)

数组

• 一种顺序存储的线性表，所有元素的内存地址都是连续得的

var array : [Int] = [11,22,33]

截屏2022-03-19 下午9.18.41.png

• 在大多数编程语言中数组是无法动态修改的

swift实现一个动态数组

• 先定义一个错误处理

//定义一个错误处理
struct arrayError:Error {
    
    enum numError:Int{
        case errorOne = -1
        case errorTwo = -2
    }
    
    let size : Int
    let kind : numError
    
    var localizedDescription : String
    {
        if kind == numError.errorOne
        {
            return "index out of boundds : the max size is\(size)"   
        }
        if kind == numError.errorTwo
        {
            return "not found"
        }
        return "other error"
    }
    
}

新建一个arrayList类 大致需要下面这些成员变量和方法

private var size : Int = 0
    //存储任意类型Any
    private var elements : [Any]
    //默认容量
    private let common : Int = 10
    
    public init(arrayCapaticy:Int)
    {

    }
    
    public init()
    {
       
        
    }
    
    public func totalSize()->Int{
        
    }

    public func isEmpty() -> Bool {
        
    }

    public func containsEle(element : Int) -> Bool {
     
    }

    public func add(element :Any){

       
    }

    public func getElement(index:Int) throws -> Any {

    }

    public func setElement(index:Int,element:Int) throws -> Any {
   
    }

    /**
     
     指定位置增加元素
     */
    public func addElementIndex(index:Int,element:Any) throws
    {
    
    }
    
    func clearElements() {
    
    }
    
    /**
     
     打印字符串 1，2，3...
     */
    func toString() -> String
    {
      
    }
    
    
    private func ensureCapacity(capacity: Int)
    {
      
        
    }

• 初始化

    //初始化一个数组容纳量为arrayCapaticy 小于common取common
    public init(arrayCapaticy:Int)
    {
        let capaticy = (arrayCapaticy < common) ? common : arrayCapaticy
        elements = Array(repeating: 0, count: capaticy)
    }
    
    public init()
    {
        elements = Array(arrayLiteral: common)
    }

• func addElementIndex指定位置添加元素

 /**
     
     指定位置增加元素
     */
    public func addElementIndex(index:Int,element:Any) throws
    {
        //允许等于size
        if index<0 || index > size {
            throw(arrayError(size: size, kind: arrayError.numError.errorOne))
        }
        //保证容量
        ensureCapacity(capacity: size + 1)
        // 1 2  3
        // 1 x  2   3
        //int 往后挪执行的次数
//        let int : Int = size - index
//        var total : Int = size
//        for _ in 0..<int {
//            elements[total] = elements[total-1]
//            total = total - 1
//        }
        var inttest : Int = size - 1
        while inttest >= index {
            elements[inttest + 1] = elements[inttest]
            inttest = inttest - 1
        }
        //插入的值
        elements[index] = element
        size = size + 1
    }

• 移除指定位置某个元素

    public func removeElementOfindex(index:Int) throws{
        if index<0 || index >= size {
            throw(arrayError(size: size, kind: arrayError.numError.errorOne))
        }
        // 1 2  3  4
        // 1 3  4
        var int : Int = index + 1
        while int <= size - 1 {
            elements[int - 1] = elements[int]
            int = int + 1
        }
        
        size = size - 1
        //清空最后一个元素
        var element : Any? = elements[size]
        if element is baseClass {
            element = nil
        }

    }

• 获取元素所在得到索引

 public func indexOfElement(elemennt:Any) -> Int {
        if size == 0 {
            return arrayError.numError.errorTwo.rawValue
        }
        var index : Int = 0
        
        if elemennt is baseClass
        {
            for _ in 0...(size - 1) {
                
                let els :baseClass = elements[index] as! baseClass
                var inEls :baseClass
                inEls = elemennt as!baseClass
                if els.string == inEls.string
                {
                    return index
                }
                index = index + 1
            }
            
        }else{
   
            for item2 in elements{
                switch item2{
                case let someInt as Int:
                    if someInt == elemennt as?Int {
                        return index
                    }
                case let someDouble as Double:
                    if someDouble == elemennt as?Double {
                        return index
                    }
                default:
                    print("1")
                }
                index = index + 1
            }
        }
        //返回-2
        return arrayError.numError.errorTwo.rawValue
    }

• 确保容量

  private func ensureCapacity(capacity: Int)
    {
        let oldCapacity = elements.count
        if oldCapacity >= capacity {
            return
        }
        //位运算扩容至2倍
        let newCapacity = oldCapacity << 2
        var newArray : [Any]
        
        newArray = Array(repeating: 0, count: newCapacity)
        
        print("旧容量\(oldCapacity) 新容量\(newCapacity)")
        var int : Int = 0
        for _ in 0..<elements.count {
            newArray[int] = elements[int]
            int = int + 1
        }
        elements = newArray
        
    }

• other 将数组打印成字符串

    /**
     
     打印字符串 1，2，3...
     */
    func toString() -> String
    {
        if size <= 0 {
            return "no datas"
        }
        var string : String = ""
        var int : Int = 0
        for _ in 0...(size - 1) {
            if int != 0 {
                string = "\(string),"
            }
            
            let per : Any = elements[int]
            if per is baseClass {
                string = "\(string)\((per as! baseClass).toString())"
            }else{
                string = "\(string)\(per)"
            }
            int = int + 1
        }
        return string
    }

• 清空所有元素

    func clearElements() {
        var int : Int = 0;
        for _ in 0..<elements.count {
            var object : Any? = elements[int]
            if  object is  baseClass{
                object = nil
            }
            int += 1
        }
        size = 0
    }

end