> 文档中心 > 阅读《数据结构—Java语言描述》一书:打卡第四天

阅读《数据结构—Java语言描述》一书:打卡第四天


  • 💂 个人网站: 路遥叶子
  • 🤟 版权: 本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主
  • 💬 如果文章对你有帮助、欢迎关注、点赞、收藏(一键三连)和订阅专栏哦
  • 💅 想寻找共同成长的小伙伴,请点击【Java全栈开发社区

目录

第二章:线性表​

 ​ (一) 循环链表

        1.定义​

         2.算法:循环链表合并​

 ​ (二) 双向链表

         1.定义​

         2. 双向链表的结点类​

         3.算法:插入​

        3. 算法: 删除 ​

​(三) 双向循环链表

(四) 每日一练

章节仅是博主阅读书籍的总结和理解,若有不对或欠妥的地方,还请各位大佬批评指正!!!

 如果觉得文章对您有帮助,就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来,让我们一起加油学习。博主会不断推出更多优质文章哟


第二章:线性表

  (一) 循环链表

        1.定义

               循环链表也称为环形链表,其结构与单链表相似,只是将单链表的首尾相连。将最后一个结点的后继指针指向第一个结点。

                非空循环列表

                 空循环列表

 // p结点是尾结点
p.next = head;

         2.算法:循环链表合并

                分析:

                 核心算法

/* 变量    a尾: taila    a头:taila.next    b尾:tailb    b头:tailb.next*/// 先将b尾指向a的头,需要定义p记录b尾原来的值// 再将a的尾指向b的头Node p = tailb.next;     //记录b尾的指向,也就是b头tailb.next = taila.next; //b尾指向a头taila.next = p.next;     //a尾执行b头

  (二) 双向链表

         1.定义

                一个结点由两个指针域,一个指针域指向前驱结点,另一个指针域指向后继结点,这种链表称为双向链表

                        数据域 :data

                        前驱结点指针域:prior

                        后继结点指针域:next

 

         2. 双向链表的结点类

package data.linear_table.node;//双向链表的结点类public class DuLNode {    public Object data ;    //存放结点值的数据域    public DuLNode prior ;  //存放指向前驱结点的指针域    public DuLNode next ;  //存放指向后继结点的指针域    //无参时的构造函数    public DuLNode() { this(null);    }    //构造数据域值为data的新结点    public DuLNode(Object data){ this.data = data ; this.prior = null ; this.next = null ;    }}

         3.算法:插入

                需求:向结点p前面插入新结点s

                 算法核心

/* 变量结点a:p.prior*/p.prior.next = s;//结点a指向结点ss.prior = p.prior;// 结点s指向结点ap.prior = s;//结点p指向结点ss.next = p;//结点s执行结点p//注意:必须先处理结点a,否则无法获得结点a

        3. 算法: 删除

                需求:删除p结点

                核心算法

// a.next = bp.prior.next = p.next;// b.prior = ap.next.prior = p.prior

(三) 双向循环链表

        双向链表与单链表一样,只要首尾相连,即可构成双向循环链表

         线性表接口

package data.linear_table;//线性表接口public interface IList {    public void clear() ;  //清空    public boolean isEmpty();  //判断是否为空    public int length();   // 表的长度    public Object get(int i) throws Exception; //获取元素的值    public void insert(int i , Object x) throws Exception; //在指定位置,插入指定元素    public void remove(int i ) throws Exception; //删除指定元素    public int indexOf(Object x) ;  //查找指定元素第一次出现的位置    public void display() ;  //输出元素的值}

        双向链表的结点类

package data.linear_table.node;//双向链表的结点类public class DuLNode {    public Object data ;    //存放结点值的数据域    public DuLNode prior ;  //存放指向前驱结点的指针域    public DuLNode next ;  //存放指向后继结点的指针域    //无参时的构造函数    public DuLNode() { this(null);    }    //构造数据域值为data的新结点    public DuLNode(Object data){ this.data = data ; this.prior = null ; this.next = null ;    }}

        双向循环链表类

package data.linear_table.linked_list;import data.linear_table.IList;import data.linear_table.node.DuLNode;import java.util.Scanner;//双向链表类public class DuLinkList implements IList {    public DuLNode head ;    //双向循环链表的头结点    //双向链表的构造函数,构造只含1个头结点的双向循环链表    public DuLinkList () { head = new DuLNode();   //初始化头结点 head.prior = head ;     //初始化结点的前驱和后继 head.next = head ;    }    //从表尾到表头逆向创建双向循环链表,其中n为链表的结点个数    //尾插法    public DuLinkList(int n) throws Exception { this() ; Scanner sc = new Scanner(System.in);    //构造用于输入的对象 for (int j = 0 ; j < n ; j++ ) {     insert(0,sc.next()); //生成新结点,插入到表头 }    }    //插入结点    @Override    public void insert(int i, Object x) throws Exception { DuLNode p = head.next;      //初始化, p 指向首结点, j为计数器 int j = 0 ; while (!p.equals(head) && j < i ) {     //寻找插入位置     p = p.next ;    //指向后继结点     j ++ ;   // 计数器值增1 } if (j != i && !p.equals(head)) {     throw new Exception("位置不合法");  //抛出异常 } DuLNode s = new DuLNode(x);  //生成新结点s p.prior.next = s ;    //将新结点s插入到第i个结点的p前面 s.prior = p.prior ; s.next = p ; p.prior = s ;    }    //删除结点    @Override    public void remove(int i) throws Exception { DuLNode p = head.next;      //初始化, p 指向首结点, j为计数器 int j = 0 ; while (!p.equals(head) && j < i ) {     //寻找插入位置     p = p.next ;    //指向后继结点     j ++ ;   // 计数器值增1 } if (j != i ) {     throw new Exception("删除位置不合理");  //抛出异常 } //修改指针,使第i个结点p从链表中脱离出来 p.prior.next = p.next ; p.next.prior = p.prior ;    }    //输出    @Override    public void display() { DuLNode node = head.next;//取出带头结点的双向循环链表的首结点 while (!node.equals(head)) {     System.out.print(node.data +" ");     //输出结点的数据域值     node = node.next ; } System.out.println();   //换行    }}

(四) 每日一练

17. 线性表是有 n 个( )的有限序列。C

A.数据表

B.字符

C.数据元素 

D.数据项

-------------------------------------------------------

18. 线性表是一个( )。A

A.有限序列,可以为空 

B.有限序列,不可以为空

C.无限序列,可以为空

D.无限序列,不可以为空

-------------------------------------------------------

19. 以下( )是一个线性表。B

A.由 n 个实数组成的集合

B.由 100 个字符组成的序列

C.由所有整数组成的序列

D.所有奇数组成的序列

-------------------------------------------------------

20. 在线性表中,除了开始元素外,每个元素( )。A

A.只有唯一的前驱元素

B.只有唯一的后即元素字符

C.有多个前驱元素

D.有多个后继元素

-------------------------------------------------------

21. 顺序表的最大有优点是( )。A

A.存储密度大  存储密度是1

B.插入运算方便

C.删除运算方便

D.可以方便地用于各种逻辑的存储表示   顺序存储

-------------------------------------------------------

22. 对于顺序表,访问编号为 i 的元素的时间复杂度为( )。B

A. O(n)

B. O(1)

C.O(nlog2n)

D.O(log2n)

-------------------------------------------------------

23. 对于顺序表,在编号为 i 处插入一个新元素的间复杂度为( )。A

A. O(n)

B. O(1)

C.O(nlog2n)

D.O(log2n)

-------------------------------------------------------

24. 采用顺序查找法对长度为 n 的线性表进行查找(不采用表尾设监视哨的方法),最坏的

情况下要进行( )次元素间的比较。B

A.n+2

B.n

C.n-1

D.n/2

-------------------------------------------------------

25. 带头结点的单向链表的头指针为 head,该链表为空的判定条件是( )的值为真。C

A.head = = NULL

B.head.getNext()= =head

C.head.getNext()= = NULL

D.head = =head.getNext()

-------------------------------------------------------

26. 非空的单向循环链表的尾结点满足( )(设头指针为 head,指针 p 指向尾结点)。C

A.p.getNext()= =NULL

B.p= =NULL

C.p.getNext()= =head 

D.p= =head

-------------------------------------------------------

27. 链表所具备的特点是( )。D

A.可以随机访问任一结点

B.占用连续的存储空间

C.可以通过下标对链表进行直接访问

D.插入删除元素的操作不需要移动元素结点

-------------------------------------------------------

28. 设链表中的结点是 Node 类型的类,且有 Node p;为了申请一个新结点,并由 p 指向该

结点,可用以下 Java 语句( )。 A

A. p=new Node();

B. p=new Node(*);

C.p=(NODE )malloc(sizeof(p));

D.p=(NODE *)malloc(sizeof(p));

-------------------------------------------------------

29. 设顺序存储的线性表长度为 n,对于插入操作,设插入位置是等概率的,则插入一个元

素平均移动元素的次数为( )。A P34

A.n/2

B.n

C.n-1

D.n-i+1

-------------------------------------------------------

30. 设顺序存储的线性表长度为 n,对于删除操作,设删除位置是等概率的,则删除一个元

素平均移动元素的次数为( )。A  P35

A.(n-1)/2 

B.n

C.2n

D.n-i

-------------------------------------------------------

31. 设顺序存储的线性表长度为 n,要删除第 i(0<=i<=n-1)个元素,按课本的算法,当 i=

( )时,移动元素的次数为 3。 C

A.3 (第n位置,下标为n-1,移动0步)

B.n/2 (第n-1位置,下标为n-2,移动1步)

C.n-4  (第n-2位置,下标为n-3,移动2步)

D.4 (第n-3位置,下标为n-4,移动3步)

-------------------------------------------------------

32. 设顺序存储的线性长度为 n,要在第 i(0<=i<=n)个元素之前插入一个新元素,按课本

的算法当 i= ( )时,移动元素次数为 2。 D

A.n/2 (n-1元素的前面插入新元素,表示n元素位置为空,且需要移动1次。)

B.n (n-2元素的前面插入新元素,表示n和n-1都是空,且需要移动2次)

C.1

D.n-2

-------------------------------------------------------

33. 设有一个长度为 n 的顺序表,要删除第 i(0<=i<=n-1)个元素,按照课本算法,需移动

元素的个数为( )。C

A.n-i+1 i=n-1 -->0

B.n-i i=n-2 -->1

C.n-i-1 i=0 -->n-1

D.i

-------------------------------------------------------

34. 下述各线性结构中可以随机访问的是( )。 D

A. 单向链表

B. 双向链表

C. 单向循环链表

D. 顺序表

35. 线性表采用链式存储时,其地址( )。C

A.一定是不连续的

B.必须是连续的

C.可以连续也可以不连续

D.部分地址必须是连续的

-------------------------------------------------------

36. 在一个单链表中,p、q 分别指向表中两个相邻的结点,且 q 所指结点是 p 所指结点的

直接后继,现要删除 q 所指结点,可用的语句是( )。C

A.p=q.getNext();

B.p.setNext(q);

C.p.setNext(q.getNext());        p.next = q.next;

D.q.setNext(NULL);

-------------------------------------------------------

37. 在一个单链表中 p 所指结点之后插入一个 s 所指的结点时,可执行( )。D

A.p.setNext(s); s.setNext(p.getNext());

B.p,setNext(s.getNext());

C.p=s.getNext();

D.s.setNext(p.getNext()); p.setNext(s); s.next = p.next;     p.next = s;

-------------------------------------------------------

38. 按照教材算法,在一个长度为 n 的顺序表中为了删除位序号为 5 的元素,从前到后依次

移动了 15 个元素。则原顺序表的长度为( )。A

A. 21  6 + 15 = 21

B. 20

C. 19

D. 25

-------------------------------------------------------

39. 针对线性表,在存储后如果最常用的操作是第 i 个结点及其前驱,则采用( )存

储方式最节省时间。C

A.单链表 读取的时间复杂度O(n)

B.双链表   读取的时间复杂度O(n)

C.顺序表   读取的时间复杂度O(1)

D.单循环链表 读取的时间复杂度O(n)

-------------------------------------------------------

40. 假设在顺序表中,每一个数据元素所占的存储单元的数目为 4,且第一个数据元素的存

储地址为 100,则位序号是 7 的数据元素的存储地址是:( )。D

A.106

B.107

C.124

D.128 100 + 4*7 = 128

 -----------------------------------------------------------------------------------------------

章节仅是博主阅读书籍的总结和理解,若有不对或欠妥的地方,还请各位大佬批评指正!!!

 如果觉得文章对您有帮助,就拿起你的小手赶紧给博主点赞、评论、收藏一下吧~~~ 赶紧动起来,让我们一起加油学习博主会不断推出更多优质文章哟