线性构造-线性表

2020-05-05 作者:编程知识要点   |   浏览(181)

标题有没有很标题党的样子?实际上这篇文章改编自我对数据结构链表的笔记,只是我没有想到,当我想要用 Swift 来实现链表的时候,会发生这些有趣的事情。同时还让我对面向协议编程做了一次实践。于是就有了这么一个唬人的标题,因为实际上我想复习的是链表,只是不小心发现了新大陆。我想这就跟 Bug 差不多,当你解决一个 Bug, 就会产生更多的 Bug.程序员的生活就是有趣……

先复习一下链表吧,不然我总感觉不务正业。

参考:浙大数据结构(陈越、何钦铭)课件

编译环境:python v3.5.0, mac osx 10.11.4

  • 定义: 由同类型数据元素构成的有序序列线性结构。
    • 长度: 表中元素的个数
    • 空表: 没有元素的时候
    • 表头: 起始位置
    • 表尾: 结束位置
  • 常用操作
    • 初始化一个空表: List MakeEmpty()
    • 计算长度: int Length
    • 返回某个元素: ElementType FindK(int K, List L)
    • 查找元素位置: int Find(ElementType X, list L)
    • 插入元素: void Insert(ElementType X, int i, List L)
    • 删除某个元素: void Delete(int i, List L)
  • 实现方式
    • 数组
    • 链表

1、线性表及其实现

线性表的表示

<big>例如:</big>表示一个多项式Multinomial
<big>最</big>浪费的表示方法:f(x)=4x5-3x2+1,浪费大量的存储空间(若多项式指数差异很大,即很多存储单元都空着,为0)

  • 数组(计算机内连续的存储单元)表示多项式
  • 其下标表示指数,数组中存放的数值表示系数
![](https://upload-images.jianshu.io/upload_images/2027713-cf86e3ac3a589302.png)

结构数组存储非零项:P1(x)= 9x12+15x8+3x^2

  • 构造结构数组(计算机内连续的存储单元)表示多项式。结构数组中单元列表第一位为系数,第二位为指数。
    class Multinomial(): # 定义多项式结构数组
    def init(self,coef,expon):
    self.coef = coef
    self.expon = expon

    编程知识 1

链表结构存储非零项:P1(x)= 9x12+15x8+3x^2

  • 链表(单元随机存储于计算机中)每个节点存储多项式的非零项
  • 存储单元包含三个小单元用来存储系数、指数、和下一个链表单元的地址。
    class Multinomial():
    def init(self,chef,expon,link):
    self.coef = coef
    self.expon = expon
    self.link = None

    编程知识 2

据说一言不合就丢代码是一个程序员的好习惯。总之对这部分没有兴趣的同学可以跳过她,这只是很普通的链表实现,如果你学过数据结构,你就肯定不会陌生。

有一个很好的问题可以方便的说明引入链表的好处,那就是一元多项式:f(x) = a0编程知识, + a1x + an-1xn-1 + anxn 的表示及运算(两个多项式相加/相减/相乘等),显然我们可以利用数组来解决这个问题,两个多项式相加就是两个数组对应分量相加。但是这引入了一个很严重的问题,如何表示多项式x

什么是线性表

通过上述例子实践,我们可以发想线性表(Linear List)有如下几个特征:

  1. 它是由同类型数据元素构成有序序列的线性结构
  2. 表中元素的个数称为线性表的长度
  3. 线性表没有元素时,称为空表
  4. 表的起始位置称为表头,表的结束位置称为表尾

编程知识 3

#include <stdio.h>#include <stdlib.h>#define Type int// MARK: - 线性表 (链表 ChainList)/// 链表结构typedef struct ChainListNode { Type data; struct ChainListNode *next;} ChainList;/// 创建空链表初始值为 -1ChainList *chainListInit() { ChainList *list = (ChainList *)malloc(sizeof(ChainList)); list->data = -1; list->next = NULL; return list;}/// 计算链表长度int chainListLength(ChainList *list) { ChainList *p = list; int i = 0; while  { p = p->next; i++; } return i;}/// 根据序号查找链表节点,序号从 0 开始ChainList *chainListFindWithIndex(int index, ChainList *list) { ChainList *p = list; int i = 0; while (p != NULL && i < index) { p = p->next; i++; } return p;}/// 根据值查找链表节点ChainList *chainListFindWithData(Type data, ChainList *list) { ChainList *p = list; while (p != NULL && p->data != data) { p = p->next; } return p;}/// 插入: 新建节点; 查找到插入节点的上一个节点; 新节点指向下一个节点; 上一个节点指向新节点。ChainList *chainListInsert(Type data, int index, ChainList *list) { ChainList *p, *n; // 在头结点处插入 if (index == 0) { n = (ChainList *)malloc(sizeof(ChainList)); n->data = data; n->next = list; return n; } // 获取插入位置 p = chainListFindWithIndex(index, list); if (p == NULL) { return NULL; } // 插入 n = (ChainList *)malloc(sizeof(ChainList)); n->data = data; n->next = p->next; p->next = n; return list;}/// 删除节点: 找到前一个节点; 获取删除节点; 前一个节点指向后一个节点; 释放删除节点ChainList *chainListDelete(int index, ChainList *list) { ChainList *p, *d; // 如果列表为空 if (list == NULL) { return NULL; } // 删除头元素 if (index == 0) { p = list->next; free; return p; } // 查找删除元素的上一个位置 p = chainListFindWithIndex(index - 1, list); if (p == NULL) { return NULL; } // 删除 d = p->next; p->next = d->next; free; return list;}
  • 3x2000呢?开这么大的数组明显会造成空间浪费。

线性表的顺式存储(数组)实现

  • List MakeEmpty():初始化一个空的线性表L;
    L = []
  • ElementType FindKth(int K, List L):根据位序K,返回相应的元素;
    element = L[k]
  • int Find(ElementType X, List L):在线性L中查找X的第一次出现的位置;
    def Find(x,list):
    i = 0
    while x != list[i] and i < len(list):
    i += 1
    if i == len(list): # 若果没有找到返回 -1
    return -1
    else: # 找到返回下标
    return i
  • void Insert(ElementType X, int i, List L):在位序i前插入一个元素X;
    L.insert(index,x)
![](https://upload-images.jianshu.io/upload_images/2027713-81c9bfae9decbfad.png)
  • void Delete(int i, List L):删除指定位序i的元素;
    del L[i]
![](https://upload-images.jianshu.io/upload_images/2027713-f1ddafb9668b8b89.png)
  • int Length(List L):返回线性表长度n;
    n = Length(L)

开了那么大篇幅才讲到重点,如果我的职业是编辑的话,估计连睡大街都会被别的小编嫌碍眼。幸运的是,我是个程序员……一步步来是很重要的。

解决上面遗留的问题的一个方法是用结构数组按指数大小有序存储,每一个数组元素维护两个信息:多项式每一项的系数和指数。执行相加操作的时候只需要从头开始比较两个多项式当前对应项的指数即可。但是还是有问题,数组的物理空间是连续的,如果我们的数据超过了程序可分配的最大连续空间,那就杯具了,这很自然的引入了我们的链表:

线性表的链式存储(链表)实现

  • List MakeEmpty():初始化一个空的线性表L;
    class chainList():
    def init(self, value=None, Next=None): # 空表表头
    self.Value = value
    self.Next = next

       L = chainList()
    
  • ElementType FindKth(int K, List L):根据位序K,返回相应的元素;
    def FindKth(k, chain_list):
    index = 0 # 起始序列号为0
    element = chain_list # 将指针指向第一个链表单元
    while index != k and element.Next is not None : # 若找到k,或者到表尾,循环退出
    index += 1
    element = element.Next
    if index == k : # 找到返回元素的值
    return element
    else: # 没有返回 None
    return None

  • int Find(ElementType X, List L):在线性L中查找X的第一次出现的位置;
    def Find(x,chain_list):
    index = 0 # 起始序列号为0
    element = chain_list # 将指针指向第一个链表单元
    while element.Value != x and element.Next is not None: # 若找到x,或者到表尾,循环退出
    index += 1
    element = element.Next
    if element.Value == x : # 找到返回元素的值
    return index
    else: # 没有返回 None
    return None

  • void Insert(ElementType X, int i, List L):在位序i前插入一个元素X;
    def Insert(x,index ,chain_list):
    element= chainList(x) # 生成新节点
    if index == 0 : # 遇到头节点的话则直接插入到头节点前
    element.Next = chain_list
    return element
    elementBefore = FindKth(index-1, chain_list) # 查找序列前一个节点
    if elementBefore is not None:
    temp = elementBefore.Next
    elementBefore.Next = element #将新节点插在index-1节点后
    element.Next = temp # 将原来的index节点插在新节点后
    del temp # 释放内存
    return chain_list # 返回头指针
    else:
    return ‘参数错误'

![](https://upload-images.jianshu.io/upload_images/2027713-40a9a0b5fea152a7.png)
  • void Delete(int i, List L):删除指定位序i的元素;
    def Delete(index,chain_list):
    if index == 0: # 遇到头节点的话则直接删除头节点
    p = chain_list.Next
    del chain_list
    return p
    elementBefore = FindKth(index-1, L) # 查找序列前一个节点
    if elementBefore is not None:
    temp = elementBefore.Next # 将指针指向要删除的节点
    elementBefore.Next = temp.Next #将index-1节点指向index+1节点
    del temp # 释放内存
    return chain_list #返回头指针
    else:
    return ‘参数错误'
![](https://upload-images.jianshu.io/upload_images/2027713-983edbf62cb957e4.png)
  • int Length(List L):返回线性表长度n;
    def Length(chain_list):
    p = chain_list # p 指向第一个节点
    count = 0
    while p.Next is not None: # p不断指向下一个节点
    count += 1
    p = p.Next
    return count

源代码: GitHub
<big>后续内容:

  • 队列
  • 堆栈
  • 线性结构相关算法

我使用泛型协议来定义了链表。并且使用协议扩展来实现关于链表的常用操作。这样只要任意一个类遵从该协议就可以自动获得这些实现而不需要进行额外的操作。(在我第一次感受到这个特性的强大时,内心被满满的 awesome 刷屏。如果你有我的博客的话,可以在上面看到我利用这个特性实现了 Notify 协议,只要在类声明上添加一下这个协议就可以自动获得一些非常建议的消息发送和接收功能。)

链表的存储结构,即每个节点包含系数和指数两个数据域以及一个指针域:

由于语言特性的不同,这个链表跟传统的链表有所不同。你应该通过一个指向头结点的 optional 变量来操作链表,当变量为 nil 时链表为空。

typedef struct PolyNode * Polynomial;
typedef struct PolyNode{
    int coef;
    int expon;
    Polynomial link;
}

我在代码中除了实现该协议,还写了一个遵从该协议的类作为示例,并有它的调用方法。欢迎吐槽。

多项式表示问题给我们的启示就是:

// MARK: - 线性表/* 在这个泛型协议中,我定义了一个准守 Equatable 协议的泛型 Element, 这是为了后面按值查找的时候可以直接使用等号进行判断。但实际上这并不是一种聪明的做法,在进行判断的时候完全可以使用闭包来进行处理,这样就能获取更多的类型支持。这里只是为了能表现泛型类型约束的用法,才就这样做。协议后面的 class 表示这个协议只能被 class 遵从,这种约束是必要的,如果你想使用 struct 类型来实现链表,不是说不可以,但这明显不是一个适用值拷贝场景的地方。*/protocol ChainList: class { associatedtype Element: Equatable var data: Element { get set } var next: Self? { get set } init()}extension ChainList { /// 返回当前节点到链表结尾的长度 var length: Int { var i = 1 var p: Self? = self while p?.next != nil { p = p?.next i += 1 } return i } /// 查找元素 subscript(index: Int) -> Self? { var i = 0 var p: Self? = self while p != nil && i < index { p = p?.next i += 1 } return p } /// 通过值来查找元素 func find(value: Element) -> Self? { var p: Self? = self while p != nil && value != p?.data { p = p?.next } return p } /// 插入元素 @discardableResult func insert(value: Element, to: Int) -> Self? { if to == 0 { let node = Self.init() node.data = value node.next = self return node } if let pre = self[to - 1] { let node = Self.init() node.data = value node.next = pre.next pre.next = node return self } return nil } /// 删除元素 @discardableResult func delete(index: Int) -> Self? { if index == 0 { return self.next } if let pre = self[index - 1] { pre.next = pre.next?.next return self } return nil } }// MARK: - 使用示例/*遗憾的是,由于协议当中使用了 Self 类型,所以遵从这个协议的类不得不设置为 final。也就是无法继承了。*/final class List: ChainList { typealias Element = String var data: List.Element = "" var next: List? required init() { }}var top: List? = List()top?.data = "0"for i in 1 ..< 5 { let _ = top?.insert(value: "", to: i)}if let length = top?.length { for i in 0 ..< length { print(top?[i]?.data) } for _ in 0 ..< length-1 { let _ = top?.delete }}printif let length = top?.length { for i in 0 ..< length { print(top?[i]?.data) }}print/* 打印输出OptionalOptionalOptionalOptionalOptionalTagOptionalDoneProgram ended with exit code: 0 */
  • 同一个问题可以有不同的表示(存储)方法
  • 有一类共性问题:有序线性序列的组织和管理

如果你看到这里了,那说明你居然坚持看完了…… awesome ....我相信你此刻的内心会有一个疑惑,为什么不直接用一个数组呢?Swift 的数组完美的解决了链表所需要解决的问题。是的,之所以这么做,原因只是 because we can ...

线性表(Linear List):由同类型数据元素构成有序序列的线性结构

  • 表中元素个数称为线性表的长度
  • 线性表没有元素时,称为空表
  • 表起始位置称为表头,结束位置称为表尾

线性表基本操作有:

  • List MakeEmpty():初始化一个空线性表
  • ElementType FindeKth(int K, List L):根据位序K,返回相应元素
  • int Find(ElementType X, List L):在线性表L中查找X的第一次出现位置
  • void Insert(ElementType X, int i, List L):在位序i 前插入一个新元素X
  • void Delete(int i, List L):删除指定位序i 的元素
  • int Length(List L): 返回线性表L 的长度n

线性表的顺序存储实现(利用数组的连续存储空间顺序存放线性表的各个元素):

存储结构:

typedef struct{
    ElementType Data[MAXSIZE];
    int Last;
}List;
List L, *PtrL;

访问下标为i 的元素:L.Data[i] 或PtrL->Data[i]

线性表的长度:L.Last+1 或PtrL->Last + 1(Last 表示末尾元素的下标位置)

本文由永利官网发布于编程知识要点,转载请注明出处:线性构造-线性表

关键词: