当前位置:首页 >> 其它课程 >>

chap2-1-线性表


第 二 章 线 性 结 构

目 录
第 1 节 第 2 节 线性表 栈

第 3 节
第 4 节 第 5 节

队列
串 多维数组

1

第 二 章 线 性 结 构

第 1 节 线性表
一、线性表的定义和运算 二、

顺序存储线性表

三、线性链表
四、顺序表和链表的比较 五、小结

2

2.1 线 性 表
第 一、线性表的定义和运算 二 章 1.线性表的概念 线性表的逻辑结构是具有相同类型的n个数据元素的有 线 限序列: L=(D,R) 其中R为D上的一个二元关系 性 D ={ a ,a ,…,a } 1 2 n 结 构 R ={ < ai, ai+1 >| 0≤i<n ,ai∈D}

有序对

ai(i=1,...,n)是属于某数据对象的元素,
n为线性表的长度(n≥0),n=0的表称为空表。

NO3

2.1 线 性 表
2.线性表的结构特点 第 二 章 线 性 结 构

(1)所有数据元素ai在同一个线性表中必须是相同的数据类型; (2)在线性表中必存在惟一的一个称为“头”的元素; (3)在线性表中必存在惟一的一个称为“尾”的元素; (4)除“头”外,每个元素都有且只有一个前驱元素;

(5)除“尾”外,每个元素都有且只有一个后继元素。

NO4

2.1 线 性 表
3. 线性表的基本操作 第 二 章 线性表的建立、读取、插入、删除、查找、排序等。

线 4. 线性表的存储方式 性 结 (1)顺序存储---顺序表 构 ai与ai+1存放地址连续

(2)链式存储---链表 ai与ai+1存放地址不一定连续。

NO5

2.1 线 性 表
二、顺序存储线性表 第 二 章 线 性 结 构 1.顺序存储结构(顺序表)

?用一组地址连续的存储单元依次存放线性表的数据元素, 称为线性表的顺序存储结构。
? 地址计算:设每个元素占L个单元,线性表在内存中的首 地址为:addr(a1)=b,则线性表中第i个元素的存储地址 为:addr(ai)=addr(a1)+(i-1)*L=b+(i-1)*L

NO6

二、顺序存储线性表 第 二 章 线 性 结 构 ? 特点: (1)逻辑上相邻的数据元素在物理上也相邻; (2)是顺序存储结构、随机存取数据元素。 这种存储结构只要知道元素的序号,就很容易找 到第i个数据元素,且无论序号i为何值,找到第i个 元素所需时间相同。

NO7

第 二 章 线 性 结 构

二、顺序存储线性表 ? 表示方式: (1)数组类型表示:数组中的分量下标即为元素在线性表中 的序号。 这里需要声明:C语言中,数组下标从0开始。 #define MAX 100 //常量定义 datatype data[MAX]; int length;

length为顺序 表当前长度
datatype为抽象数据类型,可 用int, float, double, char 或结构 体类型代替。 如:typedef int datatype;

NO8

数组下标 0 1

内存 a1 a2

元素序号 1 2

#define MAX 100 typedef int datatype; datatype data[MAX]; int n;
例 typedef struct student { int num; char name[20]; int age ; float score; }datatype; datatype class1[MAX]; int n;

n-1

an

n
备 用 空 间

MAX-1

数据元素不是简单类型时, 可定义结构体数组

NO9

二、顺序存储线性表

2 * 1 线 性 表
NO10

? 表示方式: (2)将length与data封装在一起,单独定义一种顺序表 类型—用结构体建立
例 #define MAX 100 用变量方式定义两个顺序 表p和q SeqList p , q ; p. length =2; p.data[0]=91; p.data[1]=82; q. length =10; q.data[0]=93; q.data[1]=78; ……

typedef struct { int data[MAX]; int length; }SeqList;
SeqList即为顺序表类型,可 用该类型建立很多顺序表。

二、顺序存储线性表

2 * 1 线 性 表
NO11

? 表示方式: (2)将length与data封装在一起,单独定义一种顺序表 类型—用结构体定义
用指针方式定义一个顺序表s: SeqList *s ; /* s为指向某个顺序表的指针 */ s= (SeqList *)malloc(sizeof(SeqList)); /*动态申请内存*/ (*s) . length = 10; /* 顺序表的表长用(*s) . n 或s->n 表示*/ s->data[0] = 87; s->data[9] = 91;
表中数据元素的存储空间为s ->data[0] ~ s ->data[ s-> length -1 ]

2. 顺序表的操作 2 * 1 线 性 表
NO12

? 建立顺序表
1)问题描述:建立一个线性表(a1,a2 ,...,an),长 度为n。 2)建立过程:先输入线性表长度n的值,然后依据n值 输入n个数据元素,创建出一个顺序表。

?调用主程序
2 * 1 线 性 表
NO13

// 在主函数中调用顺序表建立函数和输出函数 #define MAX 100 #include “stdio.h” #include “alloc.h” typedef struct { int data[MAX]; int length; }SeqList; 放置建立和输出两个函数 void main() { SeqList *q; q=(SeqList *)malloc(sizeof(SeqList)); CreatSList( q ); PrintList( q ); }

? 建立顺序表
2 * 1 线 性 表
NO14

3)算法描述 void CreatSList(SeqList *p ) //创建顺序表函数 { int n,k; scanf(“%d”,&n); // 读取一个整数n if( n>0 && n<MAX ) //若n值有效,输入n个数据元素 { for(k=0;k<n;k++) { printf(“输入第%d个元素”,k); scanf( “%d”,&(*p).data[k]); } (*p).length = n ; // 将表长设置为n } else printf(“表长输入错误”); }

? 输出顺序表
2 * 1 线 性 表
NO15

算法描述 void PrintList(SeqList *p) // 输出顺序表函数 { int k; if ( p->length > 0 ) { printf("the List is:\n"); for (k=0;k<p->length;k++) printf("%5d",p->data[k]); } }

2. 顺序表的操作
? 插入 2 * 1 线 性 表
NO16

1)问题描述:有线性表(a1,a2 ,...,an),长度为n, 要在第i-1与第i个元素之间插入一个新元素。 2)插入过程:先将第i至第n个元素依次向后移动一个 位置,然后将新元素插入在第i个位置上,线性表的长 度变为n+1。

数组下标 2 * 1 线 性 表
NO17

内存 元素序号 a1 a2 1 2

数组下标

内存 元素序号 a1 a2 1 2

0

0
1

1

i-1 i

ai i ai+1 i+1

i-1 i

x
ai ai+1

i i+1

n-1 n

an

n n+1

n-1 n

an-1 n n+1 an

? 顺序表插入操作 3)算法描述 int InsertSList(SeqList *L ,int i,datatype x) { int j; 2 if(L->length==MAX) //若表满,无法插入 1 {printf("表满");return 0 ;} if ( i<0 || i> L->length+1 )//插入位置非法 线 {printf("\nCan't insert!\n") ;return 0 ;} 性 for (j= L->length;j>=i;j--) 表 L->data[j]=L->data[j-1]; //后移 L->data[i-1]=x; //在i位置处插入x L->length ++; //表长加1 return 1 ; //插入成功,返回 1 }

NO18

*

2. 顺序表的操作 ? 删除 2 * 1 线 性 表
NO19

1)问题描述:有线性表(a1,a2 ,...,an),长度为n,

要将第i个元素删除。
2)删除过程:将第i+1至第n个元素依次向前移动一个 位置,线性表的长度变为n-1。

2. 顺序表的操作 ? 删除 2 * 1 线 性 表 a1 a2 将第i个元素删除

a1

a2

….. ai-1

ai

ai+1

alength

a1 a2

0 1 i-1 i n-1



…..

ai ai+1
…..
length

….. ai-1

aai i+1

ai+1 length … a… a

an

NO20

? 顺序表删除操作

2 *

1
线 性 表

3)算法描述 int DeleteSList(SeqList *L,int i) { int j; if (i<=0 || i> (*L).length ) //删除位置非法 {printf("\nCan't delete!\n"); return 0;} else { for (j=i;j< (*L).length;j++) (*L). data[j-1]= (*L). data[j];//前移 (*L).length--; //表长减1 return 1; //删除成功,返回1 } }

NO21

? 顺序表求逆

(数据结构首尾倒置)

2 * 1 线 性 表
NO22

算法描述 void Revers(SeqList *L) { int i,j; i=0 ; //第一个元素位置 j=L->length-1 ; //最后元素对应位置 while ( i<j ) { Swap( L->data[i], L->data[j]); //交换两个元素 i++; j--; } }

3.运算的时间分析
2 *

1
线 性 表

? 在插入和删除运算中,时间主要消耗在移动元 素上,所需移动的元素个数与线性表的长度n和被 插入或删除的元素在线性表中的位置有关: 在第i个位置插入一新元素需移动 n-i个元素
插入位置= 0
a1

1
a2



i-1
ai


ai+1

n-1

n

….. ai-1

… an

NO23

2 *

1
线 性 表

3.运算的时间分析 ? 我们来求平均性能。设pi是将一个元素插入 在第i个位置的概率,则在长度为n的线性表中 插入一个元素所需的平均移动次数为:
Ein ?

?
i ?0

n

pi ( n ? i )

在等概率情况下,pi=1/(n+1),则有:

Ein

n 1 n ? (n i)  ? 2 n ? 1 i ?0

NO24

3.运算的时间分析
? 同理,删除时有: 2 *

删除位置= 0
a1

1
a2



i-1
ai


ai+1

n-1

1
线 性 表

….. ai-1

… an

Ede ?

?q
i ?1
n

n

i

(n ? i )

在等概率情况下,qi=1/n,则有:
Ede 1 ? n n ?1 ? (n ? i ) ? 2 i ?1

NO25

3.运算的时间分析 ? 从上述分析可以看出:无论是插入或删除一
2 * 1 线 性 表
NO26

个元素,平均需要移动表中一半的元素,这在 表长n较大时是相当可观的,因此这种存储结构 仅适用于不经常进行插入和删除运算以及表中

元素相对稳定的场合。

4. 顺序表的优缺点
2 * 1 线 性 表
NO27

? 顺序存储结构的优点 1)可以随机存取表中任何一个元素; 2)无须为表示表中元素间的逻辑关系而增加额外的存储空 间。 ? 顺序存储结构的缺点 1)插入和删除时需移动大量的元素; 2)要求存放元素的存储单元连续; 3)多个大小不一的线性表同时存在时会造成空间浪费; 4)线性表的容量不易扩充。

2 *

1
线 性 表

三、线性链表 1. 非顺序存储结构——链式存储结构 将线性表的元素放到一个具有头指针的链表 中,链表中每个结点包含数据域和指针域。 数据域存放数据,指针域存放后继结点的地 址,最后一个结点的指针域为空。逻辑上相邻的 数据元素在内存中的物理存储空间不一定相邻。

NO28

三、线性链表
2 * 1 线 性 表 上图的线性表为: ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG
NO29

三、线性链表
2 * 1 线 线性链表表示法: 性 表
NO30

三、线性链表
2 * 1 线 性 表
NO31

2. 链表的种类 ? 单链表 ? 循环链表 ? 双向链表

三、线性链表
2 * 1 线 性 表
NO33

? 单链表 1)每个元素包含两个域:数据域(data)和指针域(next), 数据域用来存放元素的值,指针域用来存放后继元素的 存储地址。 2)指示链表中第一个结点的指针称为头指针(head),最 后一个结点没有后继结点,它的指针域为空(记为NULL或 ∧)。 例如:

三、线性链表
? 单链表 3)表示方法
2 * c语言定义一种节点类型: LNode是结点类型,

1
线 性 表

typedef struct Node { datatype data; struct Node *next; } LNode , *Linklist;

LinkList是指向LNode类型 结点的指针类型。

若有 LNode L; L为结点类型的变量 L.data=x; L.next=NULL; 若有 LNode *L; L为存储某个结点的地址的指针变量, L= (LNode *) malloc(sizeof(LNode)); L->data=x; L->next=NULL;

NO34

三、线性链表
?单链表 3)表示方法 c语言定义一种节点类型:

2 *

typedef struct Node { datatype data; struct Node *next; } LNode , *LinkList;

1
线 性 表

为了增强程序的可读性,通常将标识一个链表的头指针说明 为LinkList类型的变量,例如: LinkList L; 当L有定义 时,值要么为NULL,表示一个空表; 要么为第一个结点的 地址,即链表的头指针。将操作中用到指向某结点的指针变 量说明为:LNode *指针变量; 例如:LNode *q; q= (LNode *) malloc(sizeof(LNode)); 申请一块LNode类型的存储单元的操作,并将其地址赋值给 变量q。

NO35

指针与结点的常见运算
p 2 * p

1
线 性 表

s

q

1)指针赋值:s=p;q=p->next;
p

p

2)指针移动:p=p->next;

NO36

指针与结点的常见操作
p
2 * p

1
线 性 表

s

s p
head

3)后插:s->next=p->next;p->next=s;
head

q

p

s

s

4)前插:q=head; while(q->next!=p) q=q->next; q->next=s;s->next=p;
NO37

3.单链表的基本操作 ? 建立单链表 链表中的每个结点是运行时系统根据需要而 生成的,建立单链表要从空表开始,每读入一个 数据元素则申请一个结点,然后插入链表中。 向链表中插入一个结点的方式有两种: (1)头插法:每次新加入的结点都插在链的头部。 (2)尾插法:每次新加入的结点都插在链的尾部。

2 *

1
线 性 表

NO38

建立单链表
2 * 1 线 性 表
NO39

L null (1)头插法: LinkList Hcreatlist() P { LNode *P,*L=NULL; L a1 int x; P scanf(“%d”,&x); L a2 while(x!= Flag ) { P=(LNode *)malloc(sizeof(LNode)); P->data=x; p->next=L; L=P; scanf(“%d”,&x); } 特点:建立简单,但链表中的顺序 return L; } 与读入的顺序相反。
Flag的值要根据具 体问题来决定

2 * 1 线 性 表
NO40

问题:第一个结 点插入时要单独 H a1 ai ∧ 判断 (2)尾插法:每次新加入的结点都插在链的尾部。 LNode *H=NULL,*T,*S;//S为新加入节点,T为尾节点 …… If (H==NULL) H=S; T->next=S; S->next=NULL; T=S; else T->next=S

T

S T

解决办法:加入一个头结点,只是它的数据域中不存放 线性表的元素,它的指针域指向线性表的第一个元素。 当表空时只有一个头结点,它的指针域为空,如下图: head ^
head ^ (空表)

T H
2 * 1 线 性 表
NO41

S T a1 ∧

S T ai ∧

(2)尾插法:带头结点算法 LinkList CreatList() { LNode *H,*T,*S; int x; H=(LNode *)malloc(sizeof(LNode)); T=H; scanf(“%d”,&x); while( x!=Flag ) { S= (LNode *)malloc(sizeof(LNode)); S->data=x; S->next=NULL; T->next=S; T=S; scanf(“%d”,&x); } return H; }

3.单线性链表的基本操作
? 求链表的长度 1)问题描述:根据头指针统计出链表中的节点个数。
2 * 2)算法描述

1
线 性 表 h 头结点 p

int LengthList( LinkList H) { LNode *p=H; int i=0; while (p->next!=NULL) { i++; p=p->next;} return i; }
a1 a2 …... an ^

p

p

p

NO42

3.单线性链表的基本操作
? 查找链表中指定的结点 1)两类查找:按序号查找或按内容查找 2)查找过程:根据头指针找到第一个结点检查是否是指 定结点,若不是根据其next域检查下一结点,以此类推。 3)算法描述 ( 按内容查找 ) LNode *SearchX(LinkList H,datatype x)

2 *

1
线 性 表

{ LNode *p=H->next; while(p!=NULL && p->data != x)p=p->next; return p; }
H 头结点 a1 a2

…...

an ^

p

p

p

NO43

3.单线性链表的基本操作
2 * 1 线 性 表
NO44

? 插入运算 (前插/后插) 1)问题描述:在头指针为head的链表中,在值为a的结点前 面插入一个值为x的结点。若链表为空,则x成为其头结点; 若表中无a元素,则将x插入链表末尾。 q
Head


x

a



^

s s->next=q->next;

q->next=s;

2)算法描述

2 * 1 线 性 表

LNode *GetListNode(int x) { LNode *s=(LNode *)malloc(NODESIZE); if (s){ s->data=x; s->next=NULL; } return(s);} int InsertList(LNode *H,int a,int x) {LNode *s, *q = H ; s=GetListNode(x); if (!s) return 0; if (H ==NULL) {H =s; return 1;} //表为空时 while(q->next!=NULL&&q->next->data!=a) //找到a前驱 q=q->next; q s->next=q->next; //插入 q->next=s; a H ┄ ┄ ^ return 1; } q 插入运算

q q

s
NO45

x

3.单线性链表的基本操作
2 * 1 线 性 head 表
NO46

? 删除运算 1)问题描述:在头指针为head的链表中, 必须找到a的 将值为a的结点删除。
q

前驱结点
a
p





^

p=q->next;
2)算法描述

q->next=p->next;

free(p);

链表删除结点操作
2 *

1
线 性 表

int DeleteList(LNode *head,int a) { LNode *p, *q=head; while (q->next!=NULL && q->next->data!=a) q=q->next; if (q->next!=NULL)//找到,删除 { p=q->next; q->next=p->next; free(p); return 1; //返回成功 } else return 0; //返回失败 }

NO47

注意
2 * 1 线 性 表
NO48

(1)单链表的前插法和删除一个结点时,必须 记住其前驱结点。 (2)单链表是随机存储,顺序访问方式,若访 问尾结点时,需遍历整个链表才能找到。 思考:若只知道中间某个结 点,如何修改单链表结构, 才能访问到所有的节点?

? 循环链表
2 * 1 线 性 表 特点:表中最后一个结点的指针域不为空,而是指向表头, 整个链表形成一个环。与一般链表不同之处在于只要给定 循环链表中任一结点的地址,就可以查遍表中所有的结点, 而不必从头指针开始。如下图:

H

a1

a2

a3

…..

an

思考:如何判断 已到了尾结点?

NO49

? 循环链表
2 * 1 线 性 表

思考:循环链表与

判断尾结点的方式有三种: 单链表类似同样找 前驱结点不便。再 (1)if (P->next==H) 如何改进? (2)令头结点H的域赋一个标志值flag if ( p->next->data==flag) (3)增加一个指针Tail,令Tail指向链表的尾结点。 If ( p == Tail) 在建立链表时,每插入一个新的结点(后插法)S,都 要令 Tail=S; S->next=H;

H

a1

a2

a3

…..

an

循环链表的插入、删除操作与单链表类似

NO50

? 双向链表
2 * 1 线 性 表
NO51

特点:表中每个结点有两个指针域:一个指向直接后继, 一个指向直接前驱,那么从表中任一结点都可以 随意向前或向后查找。但在作插入、删除运算时, 需同时修改两个方向上的指针。如下图:

head before data 一个结点 next

4.线性表的应用:应用最广的数据结构。
2 *

1
线 性 表

· 高级语言中的数组 · 计算机的文件系统 · 计算机的目录系统 · 电话号码查询系统 (可以采用顺序表或单链表结构) · 各种事务处理 (各种表格均可以采用顺序表和线性链表结构)

NO52

5.
2 * 1 线 性 表
NO53

应用实例——一元多项式相加

? 问题描述 一个一元多项式可以表示为:

Pn ( x) ? P0 ? P x ? ...? Pi x ? ...? Pn x 1
i

n

其中每一项由系数Pi及x的指数i组成。若多项 式按升幂排列,则它由n+1个系数唯一确定,因 此可以用一个线性表P表示:

P ? ( P , P ,...,P ,...,P ) 0 1 i n
其指数i隐藏在系数Pi的序号内。

5. 应用实例——一元多项式相加
2 * 1 线 性 表
NO54

? 问题分析 1)存储结构:多项式相加时,常要合并同类项,由此就要改 变多项式的系数和指数,而且在实际问题中,时常会出现多 项式的次数很高但又存在大量零系数的项,因此宜采用链式 存储结构。 2)结点结构:每一个非零项构成链表中的一个结点,结点由 两个数据域和一个指针域构成,如图:pi a e next 3)链表结构:采用带头结点的线 系数 指数 性链表表示多项式A(x)、B(x), 相加后结果在线性链表C(x)中。

A(x)=4x80+7x60+9x5+5
B(x)=2x80-7x60+3x12

5. 应用实例——一元多项式相加
? 问题分析 4)运算过程:设指针ha、hb分别为多项式链表A(x)、B(x) 2 的头指针,指针p、q的初始位置分别指向A(x)、B(x)中的 过程为:比较p、q所指结点中的指数项。 1 第一项。 若:p->e > q->e,那么p所指的结点为C(x)中的一项,令p 线 指针后移一个结点; 性 若:p->e < q->e,则q所指的结点为C(x)中的一项,将q结 表 点插入p结点之前,并令q指针后移一个结点; 若:p->e = = q->e,则将两个结点中的系数相加,当和不 为零时,修改p结点中的系数,释放q结点;否则,删去p结 点,同时释放p、q结点。 这种方法实际上是将B(x)加到A(x)中,最后形成C(x),因 此C(x)中的结点不需要重新生成。

NO55

*

算 法 描 述 ( 一 元 多 项 式 加 法 )
La

EXPNODE *AddPoly(EXPNODE *ha,EXPNODE *hb) { p=ha->next; q=hb->next; ct=ha; hc=ha; while (p!=NULL && q!=NULL) { if? 算法描述(一元多项式加法) (p->e > q->e){ ct=p; p=p->next; } if (p->e < q->e) { u=q->next; q->next=p; ct->next=q;ct=q;q=u;} if (p->e==q->e) { sum=p->a+q->a; if (sum!=0){ p->a=sum; ct=p; } else{ ct->next=p->next; free(p); } p=ct->next; u=q; q=q->next; free(u); } } if (q!=NULL) ct->next=q; free(hb); return(hc); }
-1 4 80 -7 60

?
NO56
Lb

-9

5

-5

0

^

-1

2 80

-7

60

3

12 ^

6、链式存储结构特点
2 *

(1)插入、删除灵活方便,不需要移动结点,只要 改变结点中指针域的值即可。

1
线 性 表

(2)适合于线性表是动态变化的,不进行频繁查找 操作、但经常进行插入删除时使用。
(3)链表的查找只能从头指针开始顺序查找。 (4)指针占用额外存储空间

NO57

四、顺序表和链表的比较
2 * 1 线 性 表
NO58

? 线性表的长度是否固定 顺序表的存储空间是静态分配的,执行期间上下 界固定,适用于表长固定的场合; 链表的存储空间是在执行过程中动态分配的,适 用于表长不固定的场合。 ? 线性表的主要操作是什么 顺序表是连续存放的,适用于频繁查找操作的表。 链表适用于经常进行插入和删除的表。 ? 采用的算法语言:链表要求指针类型变量。

五、小结
2 * 1 线 性 表
NO59

1、理解线性表 2、掌握顺序和链式存储结构

3、熟悉线性表的基本操作(会读/写算法)
4、了解循环链表、双向链表的概念

2 * 1 线 性 表
NO60

六、作业与实验
? 教材第50页习题中的 一 ~ 三题

? 实验:
第50页习题中四题的 4 (2)(3)

L

2

5 P

7

3 R

8 ^ S

练习: 对单链表分别执行下列各程序段,画出结果示意图. (1) L=P->next; (2) R->data=P->data; (3) R->data=P->next ->data; (4) P->next ->next ->next ->data=P->data; (5) T=P; while(T!=NULL) {T->data=(T->data)*2; T=T->next; }
NO61

L

2

5

7

3

P

R

8 ^ S

练习: 对单链表分别执行下列各程序段,画出结果示意图. (6)T=P; while(T-> next!=NULL) { T->data=(T->data)*2; T=T->next; } (7) P=( LNode *)malloc(sizeof(LNode )); P->data=10; R->next =P; P->next =S;
NO62

L

2

5 P

7

3 R

8 ^ S

练习: 对单链表分别执行下列各程序段,画出结果示意图. (8) T=L; T-> next =P-> next; free(P); (9) S-> next =L;

NO63

L

2

5 P

7

3 R

8 ^ S

(1) L=P-> next;

L

2

5
P

7
L

3
R

8 S

^

NO64

L

2

5 P

7

3 R

8 ^ S

(2) R->data=P->data; 2 5 7 5 8 S ^

P

R

NO65

L

2

5 P

7

3 R

8 ^ S

(3) R->data=P->next ->data; 2 5 P 7 7 R 8

^

S

NO66

L

2

5 P

7

3 R

8 ^ S

(4) P->next ->next ->next ->data=P->data;
2 5 7 3 5 ^ S

P

R

NO67

L
(5)

2

5
P

7

3
R

8 ^ S

T=P; while(T!=NULL) { T->data=(T->data)*2; T=T->next; } 10 P 14 6 R 16 ^ S

L

2

NO68

L

2

5 P

7

3 R

8 ^ S

(6) T=P; while(T-> next!=NULL) { T->data=(T->data)*2; T=T->next; } L 2 10 14 P

6 R

8 ^ S

NO69

L

2

5

7

3

P R (7) P=(LNode*)malloc(sizeof(LNode)); P->data=10; R->next =P; P->next =S;

8 ^ S

NO70

L

2

5

7

3

P R (7) P=(LNode *)malloc(sizeof(LNode)); P->data=10; P R->next=P; P->next=S;
L 2 5 P 7 3 R

8 ^ S

8 ^ S

NO71

L

2

5

7

3

P R (7) P=(LNode *)malloc(sizeof(LNode)); P->data=10; 10 P R->next=P; P->next=S;
L 2 5 P 7 3 R

8 ^ S

8 ^ S

NO72

L

2

5

7

3

P

R

8 ^ S

(7) P=(LNode *)malloc(sizeof(LNode)); P->data=10; 10 P R->next=P; P->next=S; L 2 5 7 3 R 8 ^ S

NO73

L

2

5

7

3

P R (7) P=(LNode *)malloc(sizeof(LNode)); P->data=10; 10 P R->next=P; P->next=S;

8 ^ S

L

2

5

7

3 R

8 ^ S

NO74

L

2

5

7

3

P
(8) T=L; T->next=P->next; free(P); L 2 T P 5 7

R

8 ^ S

3

R

8 ^ S

NO75

L

2

5 P

7

3 R

8 ^ S

(9) S->next=L;

L

2

5 P

7

3 R

8 S

如果 S->next= =L 则S所指向的结点为尾结点.

NO76

一、判断题
1.线性表的逻辑顺序与存储顺序总是一致的。 2.顺序存储的线性表可以按序号随机存取。 3.顺序表的插入和删除操作不需要付出很大的 时间代价,因为每次操作平均只有近一半的元 素需要移动。 4.线性表中的元素可以是各种各样的,但同一 线性表中的数据元素具有相同的特性,因此是 属于同一数据对象。
NO77

一、判断题
5.在线性表的顺序存储结构中,逻辑上相邻的两个元素 在物理位置上并不一定紧邻。 6.在线性表的链式存储结构中,逻辑上相邻的元素在物 理位置上不一定相邻。 7.线性表的链式存储结构优于顺序存储结构。 8.在线性表的顺序存储结构中,插入和删除时,移动元 素的个数与该元素的位置有关。 9.线性表的链式存储结构是用一组任意的存储单元来存 储线性表中数据元素的。 10.在单链表中,要取得某个元素,只要知道该元素的 指针即可,因此,单链表是随机存取的存储结构。
NO78

三、填空题
1.带头结点的单链表H为空的条件是 __________________。 2.非空单循环链表L中*p是尾结点的条件 是__________________。 3.在一个单链表中p所指结点之后插入一 个由指针s所指结点,应执行 s->next=_____;和p->next=______的操作。
NO79

三、填空题
4.在一个单链表中p所指结点之前插入一个由指 针s所指结点,可执行以下操作: s->next=________; p->next=s; t=p->data; p->data=___________; s->data=___________; 5.在顺序表中做插入操作时首先检查________。
NO80

四、算法设计题
2、已知带有头结点的循环链表中头指针为head,试写出 删除并释放数据域值为x的所有结点的C函数。 3、设A=(a1,a2,…,ai ,…,an),B=(b1,b2,…, bi ,…,bn)是两个给定的线性表,它们的结点个数 分别是n和m,且结点值都是整数。 若n=m,且ai = bi (0≤i<n=), 则A=B。 若n<m,且ai = bi (0≤i<n=),则A<B。 若存在一个j,j<m,j<n,且ai = bi ( 0≤i<j=),则aj < bj,则A<B;否则A>B。 试编写一个比较A和B的函数C,该函数返回-1或0或1, 以此分别表示A<B或A=B或A>B。
NO81

编程题
对给定的单链表L,编写一个删除L中 值为x的节点的直接前驱节点算法。

NO82

大作业题
试编制一个简单的火车票销售系统, 可完成售票、退票和查询车票剩余情况等 功能。每张车票包含车次和座位信息。 [基本要求]在售票、退票和查询车票剩余情 况等环节中,都必须显示出车票的信息, 即车次和座位情况。为简单起见,在此假 设所有出售的车票均为同一车次的车票。 退票时,必须是车站售出的车票列车票才 能退(这里已同一车次的为例),否则视 为无效票,不能办理退票业务。
NO83


相关文章:
数据结构
chapt1编译原理 59页 5财富值 一片槐树叶课件 14页 免费如要投诉违规内容,请到...线性表 2.1 线性表的逻辑结构及基本运算 1.线性表简单的定义 n 个数据元素...
概率统计(1-1)(b)
chapt2 线性表() 46页 2财富值如要投诉违规内容,请到百度文库投诉中心;如要...= {1, 2,3, 4,5, 6} , A = {1,3,5} , B = {1, 2,3, 4}...
chapt2习题
Chapt2-2 11页 1下载券 chapt2-5 21页 免费 Chapt2_1[1] 26页 2下载券 chapt2-3 25页 1下载券 chapt2-4 暂无评价 52页 免费 chapt2 线性表() ...
28043chap1--chap3分章练习
28043chap1--chap3分章练习_财会/金融考试_资格考试/认证_教育专区。第...、名词解释 1.儿童观 2.教育观 3.学前教育价值观 4.学前教育目的观 5....
线性002完
DS002.1 线性表 (I) 23页 免费 chap002线性表习题讲解 32页 2财富值 DS002...第章 矩 阵 【大纲内容】矩阵的概念;矩阵的线性运算;矩阵的乘法;方阵的幂;...
数据结构实验(总)
chap3-ans 20页 10财富值 第二章 JSP元素 71页 免费 JSP元素 23页 2财富...第2章 2.1 顺序表 2.1.1(去相同)将 A、B 线性表输出,且 B 表连接在...
洪梅镇教育评估细则
chap 1a 暂无评价 30页 免费 解峪乡人大在转型跨越...第2线性表作业 2页 免费如要投诉违规内容,请到百度...1、语文合格率达标 评比分值 得分 总分 负责人 ...
chapt2
Chapt2-2 11页 1财富值 chapt2-5 21页 免费 Chapt2_1[1] 26页 5财富值 chapt2 线性表() 28页 2财富值 chapt2-3 25页 2财富值 chapt2-4 暂无评...
chapt2
Chapt2-2 11页 1财富值 chapt2-5 21页 免费 Chapt2_1[1] 26页 5财富值 chapt2 线性表() 28页 2财富值 chapt2-3 25页 2财富值 chapt2-4 暂无评...
第9章 查找
47页 免费 查找 31页 免费 DS chap9 查找 172页 1财富值如要投诉违规内容,...(2)散列表存储中解决碰撞的基本方法有哪些?其基本思想是什么? (3)用线性探查...
更多相关标签:
实验1 线性表及其应用 | 第2章 线性表 自测卷 | 光学工程 chap1 1.wmv | 线性表 | 线性表的顺序存储结构 | 线性表和链表的区别 | 数据结构线性表 | 线性表的链式存储结构 |