当前位置：文档之家 › 数据结构第2章

数据结构第2章

  • 格式：ppt
  • 大小：340.00 KB
  • 文档页数：85

下载文档原格式

  / 85

合集下载

数据结构第二章课后答案

数据结构第二章课后答案

数据结构第二章课后答案数据结构第二章课后答案1. 线性表1.1 数组实现线性表Q1. 请说明线性表的定义，并结合数组实现线性表的特点进行解释。

线性表是由n(n≥0)个数据元素构成的有序序列，其中n表示线性表的长度。

数组实现线性表的特点是使用一组具有相同数据类型的连续存储空间存储线性表中的元素，通过下标访问和操作元素。

A1. 线性表的定义指出，线性表是由若干个数据元素组成的有序序列。

具体地，在数组实现线性表中，我们将元素存储在一组连续的内存空间中，通过下标访问和操作元素。

由于数组的存储空间具有连续性，这样的实现方式可以在O(1)的时间复杂度下进行元素的访问和修改操作。

1.2 链表实现线性表Q2. 请说明链表实现线性表的特点，并与数组实现进行比较。

链表实现线性表的特点是通过指针将线性表中的元素按照节点的形式连接起来，每个节点包含了存储的元素和指向下一个节点的指针。

与数组实现相比，链表的插入和删除操作更为高效，但是访问某个位置的元素需要从头开始遍历，时间复杂度较大。

A2. 链表实现线性表的特点是通过使用节点和指针将线性表中的元素连接起来。

每个节点中包含了一个存储的元素和指向下一个节点的指针。

链表的插入和删除操作的时间复杂度为O(1)，因为只需要改变指针的指向即可。

但是，访问某个位置的元素需要从头开始遍历链表，所以时间复杂度为O(n)。

2. 栈和队列2.1 栈的定义和基本操作Q3. 请给出栈的定义和基本操作。

栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作，该端称为栈顶。

栈的基本操作包括入栈(push)和出栈(pop)，分别用于将元素压入栈和将栈顶元素弹出。

A3. 栈是一种特殊的线性表，它只能在表的一端进行插入和删除操作。

这个特定的一端称为栈顶，而另一端称为栈底。

栈的基本操作包括入栈(push)和出栈(pop)。

入栈操作将一个元素压入栈顶，出栈操作将栈顶元素弹出。

2.2 队列的定义和基本操作Q4. 请给出队列的定义和基本操作。

数据结构--第二章考试题库(含答案)

数据结构--第二章考试题库(含答案)

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

数据结构第二章习题(1)

数据结构第二章习题(1)


B. 单链表
C. 双链表
D. 单循环链表
3.具有线性结构的数据结构是（ ）。
A. 图
B. 树
C. 广义表
D. 栈
4.在一个长度为 n 的顺序表中，在第 i 个元素之前插入一个新元素时，需向后移动（ ）
个元素。
A. n-i
B. n-i+1
C. n-i-1
5.非空的循环单链表 head 的尾结点 p 满足（ ）。
A. n-i
B. n-i+1
C. n-i-1
D. i+1
10.线性表是n个（ ）的有限序列。
A. 表元素
B. 字符 C. 数据元素 D. 数据项
11.从表中任一结点出发，都能扫描整个表的是（ ）。
A. 单链表
B. 顺序表
C. 循环链表
D. 静态链表
12.在具有n个结点的单链表上查找值为x的元素时，其时间复杂度为（ ）。
A. q->next=s->next；s->next=p； B. s->next=p；q->next=s->next；
C. p->next=s->next；s->next=q； D. s->next=q；p->next=s->next； 24.在以下的叙述中，正确的是（ ）。
A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
A. p->next=p->next->next;
B. p=p->next;p->next=p->next->next;
C. p =p->next;
数据结构李春葆 第2章 线性表

数据结构李春葆 第2章 线性表


2.2.1 线性表的顺序存储—顺序表
线性表的顺序存储结构：把线性表中的所有元素按照 其逻辑顺序依次存储到从计算机存储器中指定存储位臵开 始的一块连续的存储空间中。 这样,线性表中第一个元素的存储位臵就是指定的存储 位臵，第i+1个元素（1≤i≤n-1）的存储位臵紧接在第i个元 素的存储位臵的后面。 线性表 逻辑结构 顺序表 存储结构
回true，否则返回false。
bool ListEmpty(SqList *L) {
return(L->length==0);
}
本算法的时间复杂度为O(1)。
（4）求线性表的长度ListLength(L)
该运算返回顺序表 L 的长度。实际上只需返回 length成员 的值即可。
int ListLength(SqList *L)
（ 3 ）判线性表是否为空表 ListEmpty(L) ：若 L 为空表， 则返回真，否则返回假。 （ 4 ）求线性表的长度 ListLength(L) ：返回 L 中元素个数。 （ 5）输出线性表 DispList(L): 当线性表 L不为空时，顺序 显示L中各节点的值域。 （6）求线性表L中指定位臵的某个数据元素 GetElem(L,i,&e) ：用 e 返回 L 中第 i （ 1≤i≤ListLength(L) ）个 元素的值。
void unionList(List LA,List LB,List &LC) { int lena,i; ElemType e; InitList(LC); for (i=1;i<=ListLength(LA);i++) //将LA的所有元素插入到Lc中 { GetElem(LA,i,e); ListInsert(LC,i,e); } lena=ListLength(LA); //求线性表LA的长度 for (i=1;i<=ListLength(LB);i++) { GetElem(LB,i,e); //取LB中第i个数据元素赋给e if (!LocateElem(LA,e)) //LA中不存在和e相同者,插入到LC中 ListInsert(LC,++lena,e); } }
吉林大学数据结构_第二章 线性表

吉林大学数据结构_第二章 线性表


如何找指定位置的结点？
• 与顺序表不同，单链表无法直接访问指定 位置的结点，而是需要从哨位结点开始， 沿着next指针逐个结点计数，直至到达指定 位置。
操作
• • • • 存取 查找 删除 插入
存取算法
算法Find(k.item) /*将链表中第k个结点的字段值赋给item*/ F1. [k合法？] IF (k<1) THEN (PRINT “存取位置不合法”. RETURN.) F2. [初始化] p←head. i ←0. F3. [找第k个结点] WHILE (p ≠NULL AND i<k) DO (p←next(p). i ←i+1.) IF p=NULL THEN (PRINT “无此结点”. RETURN. ) item←data(p). ▍ 存取算法的时间复杂性分析。P30
插入算法
算法Insert(k,item) /*在链表中第k个结点后插入字段值为item的结点*/ I1.[k合法？] IF (k<0) THEN (PRINT “插入不合法”. RETURN) I2.[初始化] p←head. i ←0. I3.[p指向第k个结点] WHILE (p ≠NULL AND i<k) DO (p←next(p). i ←i+1.) IF p=NULL THEN (PRINT “插入不合法”. RETURN. ) I4.[插入] s<= AVAIL. data(s) ←item. next(s) ←next(p). next(p) ←s. ▍
删除算法
算法Delete(k.item) /*删除链表中第k个结点并将其字段值赋给item*/ D1.[k合法？] IF (k<1) THEN (PRINT “删除不合法”. RETURN.) D2.[初始化] p←head. i ←0. D3.[找第k-1结点] WHILE (p ≠NULL AND i<k-1) DO (p←next(p). i ←i+1.) IF p=NULL THEN (PRINT “无此结点”. RETURN. ) D4.[删除] q ← next(p). next(p) ← next(q) . item←data(q). AVAIL<=q.▍
《数据结构》课程课件第二章线性表

《数据结构》课程课件第二章线性表


Step2：数据域赋值
插入后： Step3：插入（连接）
X q
(1)式和(2)式的顺序颠倒，可以吗？
4、插入元素（在第i个元素之前插入元素e）
为什么时间复杂度不再是O(1)？
第i－1个元素
第i个元素
p
s
新插入元素
5、删除p所指元素的后继元素
P
删除前：
P->next P->next->next
删除：
五、线性表ADT的应用举例
Void mergelist(list La，list Lb,list &Lc)
{ //已知线性表La和Lb中的数据元素按值非递减排列
//归并La和Lb得到新的线性表Lc，Lc中的元素也按值非递减排列
例: 将两个各有n个元素的有序表归并成一个有序表， 其最小的比较次数是（ ）。 A、n B、2n-1 C、2n D、n-1
三、线性表的ADT
四、线性表的分类
五、线性表ADT的应用举例
例1：已知有线性表L，要求删除所有X的出现
五、线性表ADT的应用举例
例2: 已知有两个分别有序的线性表（从小到大），要 求合并两个线性表，且合并后仍然有序。——归并 方法1: 合并，再排序O((m+n)2)
方法2： 归并，利用分别有序的特点O((m+n))
二、线性表上常见的运算
8、删除 Delete(L,i):删除线性表的第i个元素 删除前 a1 a2 … ai-1 ai ai+1 … an 删除后 a1 a2 … ai-1 ai+1 … an 9、判断是否为空 Empty(L):线性表空,则返回TRUE, 否则FALSE 10、输出线性表 Print(L):输出线性表的各个元素 11、其它操作 复制、分解、合并、分类等
数据结构第二章作业及答案

数据结构第二章作业及答案


8
解答(续):
(2) 插入操作基本步骤: 1) 若i不合法或表L已满，算法结束并返回 ERROR；否则转2) 2) 将第i个元素及之后的所有元素均后移一个位置 3) 将新元素写入空出的位置； 4) 表长+1
9
解答(续):
插入操作算法(算法2.4 )：
Status ListInsert_Sq(SqList &L, int i , ElemType e) { //在顺序线性表L中第i个位置之前插入新的元素e, // i的合法值为1≤i≤ListLength_Sq(L)+1 if (i<1||i>L.length+1)return ERROR; //i值不合法 if (L.length>=L.listsize) { //当前存储空间已满，重新分配空间 newbase=(ElemType*)realloc(L. elem, (L.listsize+LISTINCREMENT)*sizeof (ElemType)); if (!newbase)exit(OVERFLOW); //存储分配失败 L. elem=newbase; //新基址 L.listsize+=LISTINCREMENT; //增加存储容量 } q=&(L.elem[i-1]); //q为插入位置 for (p=&(L. elem[L.length-1]); p>=q ; --p) *(p+1) = *p; //插入位置及之后的元素右移 *q=e; //插入e ++L.length; //表长增1 return OK; }//ListInsert_Sq
15
4．若某线性表最常用的操作是存取任一指定序号的元素和在最 后进行插入和删除运算，则利用（ ）存储方式最节省时间。 A．顺序表 B．双向链表 C．带头结点的双向循环链表 1 D．循环链表
数据结构第2章典型例题解析

数据结构第2章典型例题解析

第2章线性表典型例题解析一、选择题1．线性表是具有n个（n≥0）的有限序列。

A．表元素B．字符C．数据元素D．数据项【分析】线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列,通常记为（a1,a2，…，a n），其中n为表长，n=0时称为空表.【答案】C2．顺序存储结构的优点是.A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示【分析】顺序存储结构是采用一组地址连续的存储单元来依次存放数据元素，数据元素的逻辑顺序和物理次序一致。

因此,其存储密度大。

【答案】A3．带头结点的单链表head为空的判断条件是.A．head==NULL B．head—〉next==NULLC．head->next==head D．head!=NULL【分析】链表为空时，头结点的指针域为空。

【答案】B4．若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用存储方式最节省运算时间。

A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表【分析】根据题意要求，该线性表的存储应能够很方便地找到线性表的第一个元素和最后一个元素，A和B都能很方便地通过头指针找到线性表的第一个元素，却要经过所有元素才能找到最后一个元素；选项C双链表若存为双向循环链表，则能很方便地找到线性表的第一个元素和最后一个元素，但存储效率要低些，插入和删除操作也略微复杂；选项D可通过尾指针直接找到线性表的最后一个元素，通过线性表的最后一个元素的循环指针就能很方便地找到第一个元素。

【答案】D5．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用存储方式最节省时间。

A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表【分析】某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算。

因此不需要移动线性表种元素的位置。

根据题意要求,该线性表的存储应能够很方便地找到线性表的任一指定序号的元素和最后一个元素,顺序表是由地址连续的向量实现的，因此具有按序号随机访问的特点.链表需要通过指针才能找到线性表的莫以指定序号的元素,需要一定的时间开销。

数据结构 第2章 线性表

数据结构 第2章 线性表

插入删除不再需要移动元素 而是需要修改元素间的关系
123456
1 3
2 5
4
6
8
整理ppt
06/03/2021
线性表链式结构的存储示意
假设我们有一个线性表(a1,a2,…,an)
数据信息
结点
指针
……
ai 0500
数据域 指针域
图a：链表中的相邻元素
……
ai+1 0800
地址0500
头指针
第一个结点
12
整理ppt
06/03/2021
实现读取单链表第i个元素的代码
/* 初始条件：链式线性表L已存在，0 < i < ListLength(L)+1 */ /* 操作结果：用 e 返回 L 中第 i 个数据元素的值 */
1. Status GetElem (LinkList L, int i, ElemType *e)
2. { /* 参数 L 是待操作的链表，其实也是头结点 */
3.
int j;
4.
Node *p;
/* 声明一结点指针p */
5.
p = L->next;
/* 让p指向链表L的第一个结点 */
6.
j = 1;
/* j为计数器 */
7.
while (p && j<i) /* p不为空或者计数器j还没有等于i时，循环继续 */
8.
{
9.
p = p->next; /* 让p指向下一个结点 */
10.
++j;
11.
}
12. if (!p || j>i)
13.
《数据结构C语言版》----第02章

《数据结构C语言版》----第02章

int ListLength(SLNode *head) { SLNode *p = head; int size = 0; while(p->next != NULL) { p = p->next; size ++; } return size; }
p size=0
head
a0
a1
(a)
...
a n 1 ∧
3.顺序表操作的效率分析
时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时间复 杂度的基本操作(最深层语句频度) T(n)= O(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置i. 若i=size，则根本无需移动（特别快）； 若i=0，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次 数才合理。
(3)带头结点单链表和不带头结点单链表的比较
1).在带头结点单链表第一个数据元素前插入结点
p head s p head data next a0 x
∧
a1
…
an-1
∧
(a) 插入前
data next a0
∧
a1
…
an-1
∧
s
x
(b) 插入后
2).删除带头结点单链表第一个数据元素结点
p data next head
（5）取数据元素ListGet(L,
i, x)
int ListGet(SeqList L, int i, DataType *x) { if(i < 0 || i > L.size-1) { printf("参数i不合法! \n"); return 0; } else { *x = L.list[i]; return 1; } }
数据结构 第2章习题答案

数据结构 第2章习题答案

第2章习题答案一、填空1. 【严题集2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。

2. 线性表中结点的集合是有限的，结点间的关系是一对一的。

3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。

4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。

5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。

6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。

8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。

二、判断正误（在正确的说法后面打勾，反之打叉）（×）1. 链表的每个结点中都恰好包含一个指针。

答：错误。

链表中的结点可含多个指针域，分别存放多个指针。

例如，双向链表中的结点可以含有两个指针域，分别存放指向其直接前趋和直接后继结点的指针。

（×）2. 链表的物理存储结构具有同链表一样的顺序。

错，链表的存储结构特点是无序，而链表的示意图有序。

（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。

错，链表的结点不会移动，只是指针内容改变。

（×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。

（×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

错，正好说反了。

顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜”（×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

数据结构第二章参考答案

数据结构第二章参考答案习题21. 填空题（1）在一个单链表中，已知每个结点包含data和next两个域，q所指结点是p所指结点的直接前驱，若在q和p之间插入s所指结点，则执行（___________）和（___________）操作。

答案：q->next = s; s->next = p; 或 s->next=q->next; q->next = s; （2）表长为n的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（___________），删除一个元素需要移动元素的平均个数为（___________）。

答案：n/2 (n-1)/2（3）表长为0的线性表称为（___________）。

答案：空表（4）动态内存管理是操作系统的基本功能之一，其作用是响应用户程序对内存的（___________）和（___________）请求。

答案：申请释放（5）顺序表多采用（___________）实现的，是一种随机存取结构，对表中任意结点存取操作的时间复杂度为（___________）。

而查找链表中的结节，需要从头指针起顺着链扫描才能得到，平均时间复杂度为（___________）。

因此，若线性表的操作主要是进行查找，很少进行插入或删除操作时，采用（___________）表比较合适。

答案：数组 O(1) O(n) 顺序（6）在链表某个位置上进行插入和删除操作，只需要修改（___________）即可，而无须移动大量元素，操作的时间复杂度为（___________）。

而在顺序表中进行插入和删除操作，往往要移动大量元素，平均移动元素的数目为（___________），平均时间复杂度为（___________）。

因此，若对线性表进行频繁的插入和删除操作时，采用（___________）表相对合适。

若插入和删除主要发生在表头和表尾，则采用（___________）表更为合适。

数据结构导论 第2章 线性表

线性表(linear list) 第二章 线性表
线性表是一种线性结构，线性结构的特点是数据元 素之间是一种线性关系，数据元素“一个接一个的 排列”。 线性结构是n（n>=0）个结点的有穷序列。对于 n>0的线性结构表示成： (a1，a2，… ai-1，ai，ai+1，…an) a1称为起始结点 an称为终端结点 起始结点， 终端结点; 起始结点 终端结点 ai-1 称为 ai 的直接前趋 i+1 称为 ai 的直接后继 直接前趋，a 直接后继。 直接前趋 直接后继
4．查找（定位） locate(L,x)： ．查找（定位） ：
依次将顺序表L中的每个元素与给定的值x进行比 较。若找到则返回其序号（下标+1），否则返回0。 int locate (sqlist L, datatype x) { int i; for ( i=0; i<st; i++) if (L.data[i]==x) return (i+1); return(0); }
void insert (sqlist *L, datatype x, int i ) { if (i<1 || i>L->last+1) error (“插入位置错误”); else if (L->last==maxsize) error (“溢出”); else { for (j=L->last-1; j>=i-1; j--) //往后移动元素 //往后移动元素 L->data[j+1]=L->data[j]; L->data[i-1]=x; //插入x L->last++; //修改表长 } }
常见的线性表的基本运算有以下几个： 常见的线性表的基本运算有以下几个：

数据结构第2章线性表A

15
在线性表的第i个位臵前插入一个元素的示意图如下：
1 2 3 4 插入25 5 12 1
12
13 21
13
21 24 28 30 42 77
2
3 4 5 6 7 8
24
25
6
7 8
28
30 42 77
9
16
3)删除
删除线性表的第i个位臵上的元素
实现步骤： 将第i+1 至第n 位的元素向前移动一个位臵； 表长减1。 注意：事先需要判断，删除位臵i 是否合法? 应当符合条件：1≤i≤n 或 i=[1, n] 核心语句： for ( j=i+1; j<=n; j++ )
18
2.2.3 顺序表的运算效率分析
时间效率分析:
算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位臵.

讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素， 则向后移动元素的次数f(n)为: f(n) = n – i + 1
例2 分析学生情况登记表是什么结构。
学号 姓名 性别 年龄 班级
0406010402
0406010405 0406010406 0406010410 0406010413 ：
陈杰
邓博 管杰 黄腾达 李荣智 ： ： ：
2004级计软04-1班
2004级计软04-1班 2004级计软04-1班 2004级计软04-1班 2004级计软04-1班 ：
InitList( &L ); DestoryList( &L ); //建空表，初始化 //撤销表，释放内存

数据结构第二章习题

数据结构第二章习题第2章线性表一、单选题1．线性表是具有n个_________的有限序列。

a、表元素B.字符C.数据元素D.数据项2。

线性表格是。

a．一个有限序列，可以为空b．一个有限序列，不可以为空c．一个无限序列，可以为空d．一个无限序列，不可以为空3．线性表采用链表存储时，其地址_________。

a、 U4。

列表中不连续的部分必须是U4。

a．可随机访问任一结点b．插入删除不需要移动元素c．不必事先估计存储空间d．所需空间与其长度成正比5．设线性表有n个元素，以下操作中，_________在顺序表上实现比在链表上实现效率更高。

a、输出I（1≤ 我≤ n） th元素值b．交换第1个元素与第2个元素的值c．顺序输出这n个元素的值d、输出与线性表中给定值x相等的元素序列号6．设线性表中有2n个元素，以下操作中，_________在单链表上实现要比在顺序表上实现效率更高。

a．删除指定的元素b、在最后一个元素后插入新元素。

C.按顺序输出前k个元素d．交换第i个元素和第2n-i-1个元素的值(i=0,1…,n-1)7.如果最常见的操作是获取第i个节点及其前体，请使用___________________。

a．单链表b．双链表c、与单链表相比，双链表的优点之一是。

a．插入和删除操作更简单b．可以进行随机访问c．可以省略表头指针或表尾指针d．访问前后相邻结点更灵活9．带头结点的单链表l为空的判定条件是_________。

a、 l==nullb.l->next==nullc.l->next==ld.l！=无效的10．在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是_________。

a、 o（1）b.o（n）c.o（n2）d.o（nlog2n）11．在一个长度为n(n>1)的带头结点的单链表h上，另设有尾指针r（指向尾结点），执行_________操作与链表的长度有关。

数据结构算法(第二章)

∥算法2.1: 将所有在线性表Lb中但不在La中的数据元素插入到La中void union(List &La, List Lb){La_len=ListLength(La)；Lb_len=ListLength(Lb)；for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e)；if(!LocateElem(La,e,equal)) ListInsert(La，++La_len,e);}}∥union∥算法2.2: 已知线性表La和Lb中的数据元素按值非递减排列。

∥归并La和Lb得到新的线性表Lc ,Lc的数据元素也接值非递减排列。

void MergeList(ListLa,List Lb, List &Lc){InitList(Lc);i=j=1; k=0;La_len=ListLength(La); Lb_len=ListLengtb(Lb);while((i<=La_len)&&(j<=Lb_len)){∥La和Lb均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if (ai<=bj) { ListInsert(Lc, ++k, ai); ++i; }else{ListInsert(Lc, ++k, bj); ++j;}}while(i<=La_len){GetElem(La, i++, ai); ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj);}}∥MergeList∥算法 2.3:构造一个空的线性表L。

Status InitList_Sq(SqList &L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem) exit(OVERFLOW);L.length=0；L.listsize=LIST_INIT_SIZE;return oK;}∥InitList_Sq∥算法2.4：在顺序线性表L中第i个位置之前插入新的元素e,∥i的合法值为1≤i≤ListLength_ Sq(L)+1Status ListInsert_ Sq(SqList &L, int i, ElemType e){if(i<1|| i>L.length+1) return ERROR;if (L.length>=L.listsize){newbase= (ElemType *)realloc(L.elem, (L.listsize+ LISTINCREMENT)* sizeof(ElemType));if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMENT；}q=& (L.elem[i-l])；for(p=&(L.elem[L.length-l]);p>=q；--p)*(p+1)=*p;*q=e;++L.length;return OK;}∥Listlnsert_ Sq∥算法2.5：在顺序线性表L中删除第i个元素，并用e返回其值∥i的合法值为1≤i≤ListLength_ Sq(L)Status ListDelete_ Sq(SqList &L, int i,ElemType &e){if((i<1)|(1> L.length)) return ERROR;p=&(L.elem[i-l]);e=*p；q=L.elem+L.length -1；for(++p;p<=q;++p) *(p一1）=*p；--L.length;Return OK;}//ListDelete_Sq算法2.6：在顺序线性表L中查找第1个值与e满足compare()的元素的位序，//若找到，则返回其在L中的位序，否则返回0LocateElem_Sq(SqList_L, ElemType e, Status(*compare)(ElemType,ElemType)){；L.elem;while(i<=L.length&&!(*compare)(*p++，e)) ++i;if(i<=L.length) return i;else return0；}∥LocateElem_Sq∥算法2.7：已知顺序线性表La和Lb的元素按值非递减排列∥归并La和Lb得到新的顺序线性表Lc ,Lc的元素也按值非递减排列void MergeList_ Sq(SqList La, SqList Lb, SqList &Lc){pa=La.elem; pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType* )malloc(Lc.listsize* sizeof(ElemType));if(!Lc.elem) exit(OVERFLOW)；pa_last=La.elem+La.length-l;pb_last=Lb.elem+Lb.length-l;while (pa<=pa_last&&pb<=pb_last){*pc++=*pa++;while (pa<=pa_ last) *pc++=*pa++；while (pb<=pb_ last) *pc++=*pb++；}∥MergeList_Sq∥算法2.8：L为带头绪点的单链表的头指针。

第2章 数据结构与算法

数据结构与算法1.1 基本概念信息--------》数据1.11 数据结构的基本概念数据：数据就是计算机化的信息，数据元素（结点记录表目）是数据的基本单位，一个数据元素由多个数据项组成，数据项是有独立含义的数据的最小单位。

数据结构：数据的逻辑结构线性结构非线性结构数据的储存结构数据的运算包括：检索，插入，删除，更新，排序等。

1.12主要的数据存储方式（1）顺序存储结构结点中只有自身信息字段，没有链接信息字段可以通过计算确定数据结构中第I个结点的位置删除，插入运算会引起大量的结点移动（2）链式存储结构结点中除了自身信息外，还有表示连接信息的指针字段，用指针来体现数据之间逻辑上的联系逻辑上相邻的结点物理上不必相邻插入，删除操作灵活方便，不必移动结点，只要改变结点中指针值即可1.13算法的设计与分析算法采用由粗到细，由抽象到具体的逐步求精的方法算法分析:主要分析算法所占用的计算机资源，即时间代价和空间代价两个方面。

1.2线性表线性表是最简单，最常用的数据结构。

线性表的逻辑结构为n个数据元素的有序序列。

线性表的储存结构多样其中：顺序储存结构的线性表称为顺序表（一维数组）链式储存结构的线性表称为链表散列方法储存的线性表称为散列表线性表根据其上的运算集合不同可以分为：栈和队列1.21 顺序表和一维数组用顺序方式储存的线性表成为一维数组。

用存储单元的邻接性体现线性表元素间的一维顺序关系，对线性表进行插入和删除操作时，可能需要移动大量的结点。

1.22 链表（1）线性链表（单链表）头指针--→头结点--→结点（2）双链表设置两个指针，其中Llink指向前驱结点，Rlink指向后继结点。

（3）可利用空间表作用是管理可用于链表插入的结点，当链表插入需要一个结点时，从可利用空间表删除第一个结点，用这个结点去做链表插入；当从链表中删除一个结点的时候，就把这个结点插入到可利用空间表第一个结点的前面。

1.23 栈栈是限定仅在一端进行插入和删除的线性表。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

抽象数据类型定义 ：
ADT LinearList{
数据元素：D={ai| ai∈D0, i=1,2,…，n n≥0 ，D0为某一数据对象} 关系：Ｓ＝｛<ai,ai+1> | ai, ai+1∈D0，i=1,2, …,n-1｝ 基本操作：
（1）InitList（L） （2）DestroyList(L) （3）ClearList(L)
{ LC->elem[k]= LB->elem[j]; j++; k++; }
LC->last=LA->last+LB->last;
21
}
2019/8/31
顺序存储结构的优点和缺点
优点：
1.无需为表示结点间的逻辑关系而增加额外的存储空间；
2.可方便地随机存取表中的任一元素。
缺点：
1.插入或删除运算不方便，除表尾的位置外，在表的其 它位置上进行插入或删除操作都必须移动大量的结 点，其效率较低；
if(L->last>=maxsize-1)
{ printf(“表已满无法插入”)； return(ERROR); } for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置*/
L->elem[k+1]=L->elem[k];
L->elem[i-1]=e; /*在C语言中数组第i个元素的下标为i-1*/
1. 按序号查找GetData(L,i)：要求查找线性表L中第i 个数据元素，其结果是L.elem[i-1]或L->elem[i-1]。
2. 按内容查找Locate（L,e）: 要求查找线性表L中与 给定值e相等的数据元素，其结果是：若在表L中找 到与e相等的元素，则返回该元素在表中的序号；若 找不到，则返回一个“空序号”，如-1。
else
{
LC->elem[k]=LB->elem[j]; j++; k++; }
while(i<=LA->last) /*当表LA长则将表LA余下的元素赋给表LC*/
{ LC->elem[k]= LA->elem[i]; i++; k++; }
while(j<=LB->last) /*当表LB长则将表LB余下的元素赋给表LC*/
loc(ai) =loc(a1)+(i-1)×k
8
2019/8/31
顺序存储结构示意图
存储地址
Loc(a1) Loc(a1)+(2-1)k
…
loc(a1)+(i-1)k
…
loc(a1)+(n-1)k
...
loc(a1)+(maxlen-1)k
内存空间状态
a1 a2
…
ai
…
an
9
逻辑地址
1 2
…
i
…
n
空闲
2019/8/31
顺序存储结构的C语言定义
#define maxsize=线性表可能达到的最大长度； typedef struct {
ElemType elem[maxsize]； /* 线性表占用的数组空间*/ int last； /*记录线性表中最后一个元素在数组elem[ ]
中的位置（下标值），空表置为-1*/ } SeqList；
D B C H F A G E
指针域
43 13
1 NULL 37
7 19 25
26
2019/8/31
带头结点的单链表示意图
有时为了操作的方便，还可以在单链表的第一个 结点之前附设一个头结点。
带头结点的空单链表
H
∧
带头结点的单链表
H
a1
a2
…
an ∧
27
2019/8/31
单链表的存储结构描述
循环链表和双链表。
23
2019/8/31
链表
2.3.1 单链表 2.3.2 单链表上的基本运算 2.3.3 循环链表 2.3.4 双向链表 *2.3.5 静态链表 2.3.6 顺序表和链表的比较
24
2019/8/31
2.3.1 单链表
结点（Node）为了正确地表示结点间的逻辑关系，必 须在存储线性表的每个数据元素值的同时，存储指示 其后继结点的地址（或位置）信息，这两部分信息组 成的存储映象叫做结点（Node）。
线性表的定义
线性表(Linear List)是由n (n≥0)个类型相同的 数据元 素 a1,a2,…，an组成 的有限 序 列 ，记做 （a1,a2,…，ai-1，ai，ai+1， …，an）。 数据元素之间是一对一的关系，即每个数据 元素最多有一个直接前驱和一个直接后继。 线性表的逻辑结构图为：
L->last++;
return(OK);
}
16
2019/8/31
删除操作
线性表的删除运算是指将表的第i(1≤i≤n)个 元素删去，使长度为n的线性表 (e1，…,ei-1，ei， ei+1，…，en)，变成长度为n-1的线性表 (e1，…,ei-1， ei+1，…，en)。 算法思路示意 算法实现
c1 ∧
7
2019/8/31
顺序存储结构的定义
线性表的顺序存储是指用一组地址连续的存 储单元依次存储线性表中的各个元素，使得线性 表中在逻辑结构上相邻的数据元素存储在相邻的 物理存储单元中，即通过数据元素物理存储的相 邻关系来反映数据元素之间逻辑上的相邻关系。 采用顺序存储结构的线性表通常称为顺序表。
假设线性表中每个元素占k个单元，第一个元素 的地址为loc(a1)，则第k个元素的地址为：
2.由于顺序表要求占用连续的存储空间，存储分配只能 预先进行静态分配。因此当表长变化较大时，难以 确定合适的存储规模。
22
2019/8/31
2.3 线性表的链式存储
链表定义： 采用链式存储结构的线性表称为链表 。
现在我们从两个角度来讨论链表： 1.从实现角度看，链表可分为动态链表和静态
链表； 2.从链接方式的角度看，链表可分为单链表、
4 9 15 28 30 30 42 51 62
移动元素 4 9 15
28 30 30 42 51 62
插入元素 4 9 15 21 28 30 30 42 51 62
15
2019/8/31
插入运算
int InsList(SeqList *L,int i,ElemType e)
{ int k;
if( (i<1) || (i>L->last+2) ) /*首先判断插入位置是否合法*/ { printf(“插入位置i值不合法”)；return(ERROR); }
if (i<=st) return(i); /*若找到值为e的元素，则返回其序号*/
else return(-1); /*若没找到，则返回空序号*/
}
13
2019/8/31
插入操作
线性表的插入运算是指在表的第i (1≤i≤n+1) 个位置，插入一个新元素e，使长度为n的线性表 (e1，…，ei-1，ei，…，en) 变成长度为n+1的线 性表（e1，…,ei-1，e，ei，…，en）。
线性表的查找运算算法描述为：
12
2019/8/31
线性表的查找运算
int Locate(SeqList L，ElemType e) { i=0 ; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/
while ((i<=st)&&(L.elem[i]!=e) ) i++; /*顺序扫描表，直到找到值为key的元素,或扫描到表尾而没找到*/
for(k=i;i<=L->last;k++)
L->elem[k-1]= L->elem[k]; /*将后面的元素依次前移*/
L->last--;
return(OK);
}
19
2019/8/31
合并算法
已知 ：有两个顺序表LA和LB，其元素均为非递减有序排列，编写 一个算法，将它们合并成一个顺序表LC，要求LC也是非递减有序 排列。
注意区分元素的序号和数组的下标，如a1的序号为1，而 其对应的数组下标为0。
10
2019/8/31
2.2.2 线性表顺序存储结构的基本运算
线性表的基本运算：
1. 查找操作 2. 插入操作 3. 删除操作 4. 顺序表合并算法
线性表顺序存储结构的优缺点分析
11
2019/8/31
查找操作
线性表的两种基本查找运算
线性表的插入运算算法。
14
2019/8/31
插入算法示意图
已知：线性表 (4,9,15,28,30,30,42,51,62)，需在第4个元素之前插 入一个元素“21”。则需要将第9个位置到第4个位置的元素依次后 移一个位置，然后将“21”插入到第4个位置，
序号 1 2 3 4 5 6 7 8 9 10
算法思想 ：设表LC是一个空表，为使LC也是非递减有序排列，可 设两个指针i、j分别指向表LA和LB中的元素，若 LA.elem[i]>LB.elem[j]，则当前先将LB.elem[j]插入到表LC中，若 LA.elem[i]≤LB.elem[j] ，当前先将LA.elem[i]插入到表LC中，如此 进行下去，直到其中一个表被扫描完毕，然后再将未扫描完的表中 剩余的所有元素放到表LC中。
算法应用示例：
1. 求单链表的长度 2. 求两个集合的差