区块链技术博客
www.b2bchain.cn

《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

这篇文章主要介绍了《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)的讲解,通过具体代码实例进行22514 讲解,并且分析了《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=22514

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

邓俊辉《数据结构》学习笔记-第三章 列表(自用)

  • 1.接口与实现
    • 1.1 ListNode(列表的基本元素)
    • 1.2 List
  • 2.无序列表
    • 2.1 查找(重点!注意语义!)
    • 2.2 插入和构造
      • 2.2.1 插入
      • 2.2.2 基于复制的构造
    • 2.3 删除和析构
      • 2.3.1 删除
      • 2.3.2 析构
    • 2.4 唯一化(考察前驱)
  • 3.有序列表
    • 3.1 唯一化(考察后继)
    • 3.2 查找
  • 4.排序(无序->有序)
    • 4.1 selectionSort选择排序(后缀部分有序)
    • 4.2 insertionSort插入排序(前缀部分有序)

从向量->列表涉及到一个概念静态->动态
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

1.接口与实现

List列表:采用动态储存策略,其中元素称node节点,各节点在逻辑上构成一个线性序列
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

1.1 ListNode(列表的基本元素)

接口
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
模板类

#define Posi(T) ListNode<T>*//列表节点位置  template <class T> struct ListNode{  T data;//数据域  Posi(T) pred;//前驱  Posi(T) succ;//后继  ListNode(){}//针对headre和trailer的构造  ListNode(T e,Posi(T) p=0,Posi(T) s=0):  data(e),pred(p),succ(s){}//默认构造函数  Posi(T) insertAsPred(T const& e);//前插入  Posi(T) insertAsSucc(T const& e);//后插入   };

下图为该ADT的图示:
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

1.2 List

接口
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
模板类

#include "ListNode.h" template<class T> class list{  private:   int _size;//规模   Posi(T) header;Posi(T) tailer;//头尾哨兵  protected:/*...内部函数*/  public:/*...构造函数、析构函数、只读接口、可写接口、遍历接口*/ }

下图为该ADT的图示
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
header头节点tailer尾节点与生俱来且不相同

first首节点last末节点并不生俱来且不一定不相同

以上所展示的列表结构可以按照下面的过程来创建

内部函数 void init()

template <class T> void list<T>::init(){  header=new ListNode<T>;//创建头哨兵节点  tailer=new ListNode<T>;//创建尾哨兵节点  header->succ=tailer;header->pred=0; //互联  tailer->pred=header;tailer->succ=0;//互联  _size=0;//记录规模   } 

2.无序列表

想到上一章学习的向量,我们是否可以模仿它的循秩访问,重载下标操作符呢?貌似可以,但是随着秩越大,访问成本会越来越高,所以舍弃,怎么办?循位置访问!

2.1 查找(重点!注意语义!)

只读接口 Posi(T) find(T const & e,int n,Posi(T) p) const;

//在节点p的n个前驱中,找到等于e的最后者  template <class T> Posi(T) list<T>::find(T const &e,int n,Posi(T) p) const{  while(0<n--) //从右向左   if(e==(p=p->pred)->data) return p;  return 0;  }

只读接口 Posi(T) find(T const & e) const;

全局查找

template <class T>//重载全局查找接口  Posi(T) list<T>::find(T const & e)const{  return find(e,_size,tailer);//这里的tailer即为_size  } 

2.2 插入和构造

2.2.1 插入

可写接口
Posi(T) insertBefore(Posi(T),T const&);
Posi(T) insertAfter (Posi(T),T const&);

template <class T> Posi(T) list<T>::insertBefore(Posi(T) p,T const & e){//e当做p的前驱插入  _size++;  return p->insertAsPred(e); //p是ListNode<T>*,通过解引操作符调用前插入 } template <class T> Posi(T) list<T>::insertAfter(Posi(T) p,T const & e){//e当做p的后继插入  _size++;  return p->insertAsSucc(e);   }

上面的前插入法和后插入法在ListNode.h中实现

template <class T> Posi(T) ListNode<T>::insertAsPred(T const& e){  Posi(T) x=new ListNode(e,pred,this);//创建(耗时100倍)  pred->succ=x;  pred=x;  return x;  } template <class T> Posi(T) ListNode<T>::insertAsSucc(T const& e){  Posi(T) x=new ListNode(e,this,succ);//创建(耗时100倍)  succ->pred=x;  succ=x;  return x;  } 

运用图示可以帮助理解:(该图为前插入)
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

2.2.2 基于复制的构造

list(list const & L) {copyNode(L.first(),L.size);}
list(list const & L,int r,int n) {copyNode(L[r],n);}

内部接口 void copyNode(Posi(T),int)

template <class T> void list<T>::copyNode(Posi(T) p,int n){//从节点p开始复制连续n个节点  init();  while(n--){   insertAsLast(p->data);//这里的insertAsLast相当于insertBefore(tailer)   p=p->succ;  } }

2.3 删除和析构

2.3.1 删除

可写接口 T remove(Posi(T));

template <class T> T list<T>::remove(Posi(T) p){  T e=p->data;//备份,假设T类型可直接赋值  p->pred->succ=p->succ;  p->succ->pred=p->pred;  delete p;  _size--;  return e; //返回删除的数值 }

结合图示理解:
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

2.3.2 析构

~list(){clear();delete header;delete tailer;}

内部接口 int clear();

template <class T> int list<T>::clear(){  int oldsize=_size;  while(0<_size)   remove(header->succ);//反复删除首节点   return oldsize; }

2.4 唯一化(考察前驱)

可写接口 int deduplicate();

template <class T> int list<T>::deduplicate(){  if(_size<2) return 0;//平凡情况  int oldsize=_size;  Posi(T) p=this->first();int r=1;//初始化,p从首节点开始  while(tailer!=(p=p->succ)){   Posi(T) q=find(p->data,r,p);//注意!在p的r个真前驱中查找   q ? remove(q):r++;//若的确存在,则删除之,否则秩递增    /*为什么remove(q)而不是p,以为在循环出会指向p的后继,此时移除后,会发生错误*/  }   return oldsize-_size; }

3.有序列表

3.1 唯一化(考察后继)

先看图示
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
可写接口 int uniquify();

template <class T> int list<T>::uniquify(){  if(_size<2) return 0;//平凡列表  int oldSize=_size;//记录原规模  Posi(T) p=first();Posi(T) q;//p为各区段的起点,q为其后继   while(tailer!=(q=p->succ))   if(p->data!=q->data) p=q;   else remove(q);  return oldSize-_size;  }

3.2 查找

只读接口 Posi(T) search(T const &,int ,Posi(T));

template <class T>//在有序列表内节点p的n个前驱中,找到不大于e的最后者  Posi(T) list<T>::search(T const & e,int n,Posi(T) p) const{  while(n<=n--)//对于p的最近的n个前驱,从右向左   if(((p=p->pred)->data)<=e) break;//逐个比较  return p;   } 

4.排序(无序->有序)

4.1 selectionSort选择排序(后缀部分有序)

图示:后半部分为有序,前半部分无序,在前半部分找最大者和无序部分的尾部交换
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
实现:

//对列表中起始于位置p的连续n个元素做选择排序 template <class T> void list<T>::selectionSort(Posi(T) p,int n){  Posi(T) head=p->pred;Posi(T) tail=p;//待排序区间  for(int i=0;i<n;i++) tail=tail->succ; //初始化[p,tail)区间  while(1<n){  //(或许可以直接交换数据域,因为每次insertBefore和remove操作都会new和delete)   insertBefore(tail,remove(selectMax(head->succ,n)));//将最大者插入有序区间前段    tail=tail->pred;   n--;  } }

内部接口 Posi(T) selectMax(Posi(T),int)

template <class T> Posi(T) list<T>::selectMax(Posi(T) p,int n){  Posi(T) max=p;//最大者暂定为p  for(Posi(T) cur=p;1<n;n--)//后续节点逐一与max比较  //It比较器,前者<后者时,返回true   if(!It((cur=cur->succ)->data,max->data))//若>=max    max=cur;//则更新最大元素位置记录  return max; }//画家算法(油画一层一层叠加,最后显示的是最上层的)

4.2 insertionSort插入排序(前缀部分有序)

怎么插入?类比打牌是摸牌:第一步 比较,第二步a移动,第三步b插入

《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
实现:

//对列表中起始于位置p的连续n个元素做插入排序 template <class T> void list<T>::insertionSort(Posi(T) p,int n){  for(int r=0;r<n;r++){//逐一引入各节点,有序部分S后移   insertAfter(search(p->data,r,p),p->data);//查找+插入   p=p->succ;   remove(p->pred);//转向下一节点   }//n次迭代,每次O(r+1) }//仅需要O(1)的辅助空间,属于就地算法

用逆序对来分析该算法的性能
《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

本文转自互联网,侵权联系删除《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 《数据结构》学习笔记-第三章 列表(逻辑型线性序列call-by-position)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们