線性表
- 具有
n個相同類型元素的有限序列（n>=0）
1.png
a1是首節(jié)點 an是尾節(jié)點
常見的線性表
- 數(shù)組
- 鏈表
- 棧
- 隊列
- 哈希表(散列表)
數(shù)組
- 一種順序存儲的線性表夏志，所有元素的內(nèi)存地址都是連續(xù)得的
var array : [Int] = [11,22,33]
截屏2022-03-19 下午9.18.41.png
- 在大多數(shù)編程語言中數(shù)組是無法動態(tài)修改的
swift實現(xiàn)一個動態(tài)數(shù)組
- 先定義一個錯誤處理
//定義一個錯誤處理
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)
{
}
- 初始化
//初始化一個數(shù)組容納量為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 往后挪執(zhí)行的次數(shù)
// 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 將數(shù)組打印成字符串
/**
打印字符串 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
