Tasks.Data_Structure

数据结构 第一次课堂作业

题目

第二章练习题 11

有一个线性表 (a1, a2, ... , an) ，其中 n>=2 ，采用带头结点的单链表储存，头指针为 L ，每个结点存放线性表中的一个元素，结点类型为 (data, next) ， 现查找某个元素值等于 x 的结点指针，若不存在这样的结点返回 NULL 。分别写出下面3种情况的查找语句，要求消耗时间尽量少。

1. 线性表中的元素无序。
2. 线性表中的元素按递增有序。
3. 线性表中的元素按递减有序。

第二章练习题 13

一个线性表 (a1, a2, ... ,an) (n>3) 采用带头结点的单链表 L 储存，设计一个高效算法求中间位置元素。 (n 为奇数时对应 n/2 的元素， n 为偶数时对应 (n+1)/2 的元素。)

例 (补充)

假设有一个带头结点的单链表 L=(a1, b1, a2, b2, ... , an, bn) 。设计一个算法将其拆分成两个带头结点的单链表L1和L2: L1=(a1, a2, ... ,an) , L2=(bn, bn-1, ... ,b1) 要求L1使用L的头结点。

思考题

假设有一个带头结点的单链表 L ,每个结点值由单个数字、小写字母和大写字母构成。设计一个算法将其拆分成3个带头结点的单链表L1、L2和L3, L1 包含 L 中的所有数字结点，L2 包含 L 中的所有小写字母结点，L3 包含 L 中的所有大写字母结点。 该算法如何设计?

提交

1. 将作业打包为压缩文件，如 zip 格式。
2. 压缩文件命名为你的学号， 如 2018302114514.zip 。
3. 将压缩文件以附件形式发送到邮箱 DS_Task1 # superexercisebook.com
4. 如果一切顺利，你将会收到一个投递成功回执。