Go转型——数据结构初级(三)

yinshidaoshi · · 588 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。
**1**.链式线性表 从之前的例题来看,线性表的顺序存储结构如果需要插入和删除i(1<=i<=n)元素,需要移动大量元素,所以我们可以看一下线性表另一种表示方式——链式存储结构。它不要求逻辑上相邻的元素物理位置也相邻,因此,链式存储结构没有顺序线性表的缺点,同样,它也失去了顺序线性表可随机存储的优点。 线性链表的特点是,使用一组任意的存储单元存储线性表的数据元素(遮住存储单元可以是连续的,也可以是不连续的),因此为了表示数据元素a(i)和其直接后继元素a(i+1)之间的逻辑关系,对于数据元素a(i)来说,除了要保存自身存储的数据信息,还需要存储一个指示其直接后继的信息(即直接后继的存储位置),这两部分结合起来组成数据元素a(i)的存储映像,称为**结点**。它包含两个域,其中,包含自身存储的数据信息的域叫做数据域,包含直接后继的存储信息的域叫做**指针域**。指针域中存储的信息叫做指针或链。 n个结点(a(i)的存储映像(1<=i<=n))连接成链表。即为线性表的链式结构,又因为一个结点中只包含一个指针域,故又称为线性链表或单链表。 ![image.png](https://static.studygolang.com/180122/9c7239f32987cf18c82cc67ca1d33c54.png) 用线性链表表示线性表时,数据元素之间的逻辑关系是有结点中的指针指示的。换句话说,指针为数据元素之间的逻辑关系的映像。则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻,由此,这种存储结构为**非顺序映像**或**链式映像**。 ![image.png](https://static.studygolang.com/180122/44d756591898c6208041a6896dd1b951.png) 由上述可见,单链表可由头指针唯一指定,上述单链表头指针为H,它指向表中第一个结点,若H为“空”(L=NULL),所表示的线性表为“空”表,其长度n为“零”。有时,我们在单链表的第一个结点之前附设一个结点,称之为头结点。头结点的数据域可以不存储任何信息,也可以存储如线性表的长度等累的附加信息,头结点的指针域存储指向第一个数据元素的指针(即第一个元素节点的存储位置)。如下图所示: ![image.png](https://static.studygolang.com/180122/44fdf177170abe3baccedad8ea609344.png) 在线性表的顺序存储结构中,由于逻辑上相邻的两个元素在物理位置上也相邻,所以任何元素的存储位置都可以从线性表的起始位置计算得到。但是在单链表中,任意两个元素存储位置之间没有固定的联系。然而,每个元素的存储位置都包含在它直接前驱结点的信息中心。例如,P是指向线性表中第i个数据元素a(i)的指针,则P->Next是第i+1个数据元素(结点a(i+1))的指针。换句话说,如果P->Data=a(i),那么P->Next->Data=a(i+1)。因此在单链表中,取得第i个数据元素必须从头指针出发寻找。因此,单链表是非随机存取的存储结构。 ![image.png](https://static.studygolang.com/180122/d634da155175555a6ebe725bfe9e8452.png) **2**.链式表的插入删除 ![image.png](https://static.studygolang.com/180122/925e04c61048f430d9fc5382d6d757d8.png) 为插入数据元素X,首先要生成数据域为x的结点,然后插入在单链表中,我们需要修改a的指针域,令其指向结点x。而x中的指针域应指向结点b,从而实现3个元素之间的逻辑变化。假设s为指向结点x的指针,则上面指针修改可以用语句概括: `s ->next=p->next; p->next = s` 还是以上图为例,我们添加数据元素X后,又想把他删除,我们应该怎么做?答案是,我们只需修改结点a的指针域,令其指向b即可,语句概括为: `p->next=p ->next->next` 链式线性表插入、删除实现如下如所示: ![image.png](https://static.studygolang.com/180122/f218ef7c1e71112b78095bbdc09a16e3.png) ![image.png](https://static.studygolang.com/180122/e8da17d41ef853e9d4a08ca6eae79720.png) ![image.png](https://static.studygolang.com/180122/a1d61b8571331eb5e429cb55a46dc13d.png) **3**.线性链表的合并 将两个有序列表合并为一个有序列表,例如,我们现在有头指针为La和Lb的单链表分别为有序线性表LA和LB的存储结构,现在将LA和LB合并得到LC。我们应该怎么做。 **4**.静态链表的操作 我们可借用一维数组来描述链表,其类型如下说明: ![image.png](https://static.studygolang.com/180123/5e39d8d153ac69ae3a8f9b63779b0159.png) ![image.png](https://static.studygolang.com/180123/e5e52d4f19b4037a30a715dc2670312b.png) 这种方法适用于没有指针类型的高级编程语言中使用链表,数组中一个分量可以看作是一个结点,第零**分量**可以看作是头结点。我们用游标(也就是指示器cur)来代替指针指示结点在数组中的相对位置,插入和删除操作如下图所示。我们可以看到,这种存储方式要预先分配一个很大的空间,但在做线性表的插入删除时,不需要移动元素,仅需要修改指针(这里的指针指得是游标)。它仍然具有链式存储结构的优点,为了区分指针类型表述的线性链表,我们将其称为**静态链表**。 ![image.png](https://static.studygolang.com/180123/d63bdb92d5fb703a504edbf42f32b15a.png)

有疑问加站长微信联系

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:812540095

588 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传