西安交通大学计算机软件,3_西安交通大学：计算机软件基础_ppt_大学课件预览

计算机软件基础

The software basic

of computer

主讲：赵英良

西安交通大学

计算机教学实验中心

第 3单元

线性数据结构

(二)

停止放映

第 2 页

第 2单元内容概要(一)

一、数据结构

1。基本概念：数据、数据元素、数据项、数据结构、

数据结构的形式化描述方法。

2。数据的逻辑结构：

逻辑结构的类别(集合、线性、树、图)

3。数据的物理结构及类别(顺序、链式、索引、散

列)

4。算法的描述及评价

( 1)算法的概念：

( 2)算法的特性：有限、确定、可行、输入、输出

( 3)设计算法的要求：正确、可读、健壮、效率

( 4)算法的评价：时间复杂性、空间复杂性

停止放映

第 3 页

第 2单元内容概要(二)

? 二、顺序表

1。线性表及相关概念和特征

线性表、长度、空表、前驱、后继、

均匀性、有序性、形式化定义

2。顺序表

概念、特征、描述(数组,last)

3。顺序表的操作

( 1)判空、判满、判合法 ( 2)插入( 3)删除

? 4。顺序表的优缺点及适用场合

– 数据连续存放、随机存取

– 逻辑上相邻，物理上也相邻

– 存储结构简单、易实现

– 插入、删除操作不便

– 存储密度大，空间利用率高

停止放映

第 4 页

第 2单元内容概要(三)

? 三、链表

? 1。单链表

? 结点、指针域、数据域、头指针、头结点。

? 2。单链表的描述

? 3。单链表的操作

? ( 1)指针操作、

? 指针说明、分配存储空间、判空、判满、释放

空间

? ( 2)查找操作 ( 3)插入 ( 4)删除

? 4。单链表的特点及适用场合

? 5。单循环链表、双向链表、双向循环链表

描述、建立、判空、查找、插入、删除

停止放映

第 5 页

本单元内容

? 栈、队列、数组、串的,

– 有关概念

– 逻辑结构及特点

– 存储结构

– 有关操作

? 涉及章节,第 1章的

1.3 栈和队列 (P32~P46)

1.4 串和数组 (P47~P55)

停止放映

第 6 页

一、栈

1。栈及相关概念

堆栈 (Stack)

– 栈是允许在同一端进行插入和删除操作的

特殊线性表。

– 允许进行插入和删除操作的一端称为栈顶

(top)，另一端为栈底 (bottom)；栈底固定，

而栈顶浮动；

– 栈中元素个数为零时称为空栈。

– 栈结构也称为后进先出表( LIFO)。

栈、栈顶、栈底、空栈

后进先出表栈底固定，而栈顶浮动

停止放映

第 7 页

栈有关概念

栈顶指针

在栈操作过程中，有一个专门的栈指针(习惯

上称它为 TOP)，指出栈顶元素所在的位置。

栈空的条件,top = -1

栈满的条件,top = MAXSIZE-1

栈上溢

栈空间是有限的，若栈已满，再进行入栈操作

时，就要产生上溢。

栈下溢

若栈空，再要执行出栈操作，则会发生下溢。

停止放映

第 8 页

2、栈的基本运算

? Setnull( Stack) 置栈为空；

? Empty( Stack) 判定栈是否为空；

? Push( Stack,x) 进栈操作，在栈顶插入元素；

? Pop( Stack) 出栈操作，删除栈顶元素；

? Gettop( Stack) 取栈顶元素

停止放映

第 9 页

例 1-10

有三个元素的进栈序列是 1,2,3。写出可

能的出栈序列。

出栈序列操作序列

1 2 3 s x s x s x

1 3 2 s x s s x x

2 1 3 s s x x s x

2 3 1 s s x s x x

3 2 1 s s s x x x

停止放映

第 10 页

3、栈的顺序存储结构

? ( 1) 栈的顺序存储结构, 实际上是一维

数组。

? ( 2) 顺序栈, 栈的顺序存储结构称为顺

序栈。

? 栈的操作只能在一端进行；即栈顶位置随

进栈和出栈而变化。

? ( 3) 顺序栈的 C语言描述 (初始化, 定义 )：

#define MAXSIZE n

int stack[MAXSIZE];

int top = -1;

停止放映

第 11 页

栈操作举例

a1 a2 …… a n

栈底栈顶

MAXSIZE

TOP

top=-1

A B C2.

(空栈 ) top=2 (A,B,C进栈)

A B3.

top=1 (C出栈)

4,A B C D E F

top=MAXSIZE-1

(栈满)

停止放映

第 12 页

(4) 算法 1-8 进栈算法

? 算法步骤,

– step1

判别栈满否，若满，则显示栈溢

出信息，停止执行；否则，执行

step 2；

– Step2

栈顶指针 top上移 (加 1)；

– Step3

在 top所指的位置插入元素 x。

停止放映

第 13 页

算法 1-8 进栈算法程序

push( int x)

{ if( top = = MAXSIZE -1) /* 判满? */

{ printf(, 栈上溢！ \n”) ;

exit ( 1) ;

}

else /* 不满，则可以进栈 */

{

top + +； /* 栈指针加 1 */

stack [ top ] = x ； /* 元素 x进栈 */

}

示例

停止放映

第 14 页

(5) 算法 1-9 出栈算法

? 算法步骤,

– step1 判别栈是否为空；若空，则输出

栈下溢信息，并停止执行；否则，

执行 step2；

– step2 弹出(删除)栈顶元素；

– step3 栈顶指针 top下移 (减 1)。

– step4 返回出栈元素

停止放映

第 15 页

算法 1-9 出栈算法程序

pop( )

{ int x;

if( top = = -1) /* 判空 */

{ printf(,栈下溢 \n”);

exit(1);

}

else /* 出栈 */

{ x = stack [ top ]；

top - - ； /* 栈顶指针减 1*/

}

return x ；

} 示例

int

停止放映

第 16 页

4、多栈共享问题

? 如何充分利用栈空间，这是解决存储空间紧张这样一个

实际矛盾所要考虑的问题。

? 作为一种策略，就是多栈共享一个栈空间。具体作法是：

– 对两栈共享情况来说,将两个栈底分别设在两端，

两个栈顶指针 top1和 top2相对中间位置动态移动，

两个栈之间的分界线是不定的。

top1 =-1 top2=MAXSIZE

空栈

top1 top2

栈 1、栈 2均有若干元素

top1 top2

栈满的情况

停止放映

第 17 页

5、栈的链式存储结构

? 由前面介绍的链表结构可知，链结构

操作灵活。对栈结构也是一样的。

? 顺序栈最多可用于 2个栈的共享，对

于更多的栈就难于表达了。

? 对于最大空间需要量事先不知的情况，

就不能使用顺序栈了。这时，就需要

采用链栈。

链栈：栈的链式存储结构

停止放映

第 18 页

链栈存储结构

? (1) 链栈存储结构的 C语言描述：

struct snode {

int data;

struct snode *link;

};

typedeef struct snode SNODE ;

? 链栈为空的条件：

top = NULL

? 链栈为满的条件,

t = NULL

t 为申请的结点,为 NULL表示失败,

停止放映

第 19 页

链栈示意图

^ 栈底

top 栈顶

…...

停止放映

第 20 页

(2) 算法 1-10 进栈操作

算法 1-10操作步骤,

? step1 申请一个链栈结点,若

t=NULL,则表示链满 ;否则,执行

step2 ;

? step2 在 top所指结点之前插入

新结点,并将 top指向新申请的结

点 t。

停止放映

第 21 页

算法 1-10 进栈操作程序

push(SNODE *top,int x)

{ SNODE *t;

t=(SNODE * )malloc(sizeof(SNODE));

if(t = = NULL )

{

pprintf(“内存中已无可用空间 \n”);

exit(1);

}

else

{ t -> data = x;

t -> link = top; top= t;

}

停止放映

第 22 页

(3) 算法 1-11 出栈操作

算法 1-11操作步骤,

? step1 若链栈为空，则输出栈溢出信息；

否则，执行 step 2。

? step2 (保存 top)并使 top 指向被删除结点

的后继结点,删除 top所指结点，。

? step 3 释放被删除结点的存储空间。返回

出栈元素值

停止放映

第 23 页

算法 1-11 出栈操作程序

int pop (SNODE * top)

{ SNODE *p; int x;

if( top = = NULL )

{ printf(“栈溢出 \n”)；

exit(1);

}

else

{ p = top；

top = top-> link ；

x = p-> data ；

free(p) ;

}

return x;

}

停止放映

第 24 页

6.栈的应用

? ( 1) 举例 1 表达式计算

? 计算表达式，首先要正确地定义运算规则：

– 先乘除、后加减

– 从左到右

– 先括号内，再括号外

? 为了让计算机能识别表达式，规定：

– 表达式由操作数( Operand)和操作符

( Operator)和定界符( Delimiter)组成。

例如,#3*( 7-2) #；

– 实际处理表达式是用两个栈结构 OPTR(算符)

和 OPND(操作数)加运算规则组成；

四

则

运

算

停止放映

第 25 页

计算表达式算法步骤

? Step1 初始化，清空 OPTR和 OPND，将左定界符

压 OPTR栈；

? Step2 循环输入表达式中的每个字符

– 若输入操作数，则进 OPND栈

– 若是算符，则和 OPTR栈顶元素进行比较，按规则进行

相应操作

– 操作服从优先关系表

? Q1

? Q1=Q2 Q1出 OPTR栈，脱括号，再读一个元素

? Q1>Q2 Q1出 OPTR栈，从 OPND中取两个数运算

? 结果入栈 OPND

? Step3 直到出现右定界符为止。

? 举例，计算,3*( 7-2)

输入,3*( 7-2) #

停止放映

第 26 页

计算表达式的处理步骤

步骤 OPTR栈 OPND栈输入字符主要操作

1 # 3 PUSH( OPND,3)

2 # 3 * PUSH( OPTR，‘ *’)

3 # * 3 ( PUSH( OPTR，‘(’)

4 #*( 3 7 PUSH( OPND,7)

5 #*( 37 - PUSH( OPTR，‘ -?)

6 #*( - 37 2 PUSH( OPND,2)

7 #*( - 372 ) Operate( 7，‘ -?,2)

8 #*( 35 POP( OPTR)

9 #* 35 # Operate( 3，‘ *’,5)

10 # 15 RETURN( GETTOP( OPND))

停止放映

第 27 页

举例 2(递归过程实现)

( 2)递归规程的实现

计算 5的阶乘( 5！ =5X4X3X2X1)

int f(n){

if ( n = = 1) return (1);

else return ( n * f(n-1));

}

f(1)

f(2)

f(3)

f(4)

f(5)

top

1 f(1)=1

2*f(1) f(2)=2*f(1)

3*f(2) f(3)=3*f(2)

4*f(3) f(4)=4*f(3)

5*f(4) f(5)=5*f(4)

停止放映

第 28 页

(３)举例３ N阶 Hanoi塔问题

? 假设有 A,B,C三座塔。在 X塔上插有 n个直

径大小不同、以小到大编号为 1,2,…, n

的圆盘。现要求将 A轴上的 n个圆盘移至 C塔

上，并按同样顺序叠排。移动圆盘的规则为：

1)每次只能移动一个圆盘；

2)圆盘可以插在 A,B,C的任意一个上；

3)任何时刻都不能将较大的圆盘压在较小

的圆盘之上。

移动方法：先将 (n-1)个圆盘从Ａ移到Ｂ，将

第 n个原盘从Ａ移到Ｃ，再将( n-1)个圆盘

从Ｂ移到Ｃ

停止放映

第 29 页

Hanoi问题的实现程序 (主要部分 )

void f(int n,int a1,int b1,int c1)

{

if(n==1) /* there is only one element,a1->c1 */

{

pop(a1); push(c1);

}

else

{ f(n-1,a1,c1,b1); /* (n-1) from a1 to b1 */

pop(a1); /* the last one from a1 to c1 */

push(c1);

f(n-1,b1,a1,c1); /* last, (n-1) from b1 to c1 */

}

停止放映

第 30 页

二、队列

? １。队列的基本概念

? 队列是一种特殊的线性表，它只允许在表的前

端( front)进行删除操作，而在表的后端

( rear)进行插入操作。

? 进行插入操作的端称为队尾,进行删除操作的

端称为队头。

? 队列中没有元素时，称为空队列。

? 队列具有先进先出( FIFO)的特点。

a1 a2 … a n 入队插入出队删除

front rear

传送带

停止放映

第 31 页

2、队列的操作

Setnull( Q) 清空队列

Empty( Q) 判别队列是否为空；空，取,T.;

非空,取值为,F.。

Addqueue( Q) 插入操作

Delqueue( Q) 删除操作

Frontqueue( Q)取队头元素

停止放映

第 32 页

3、队列的顺序存储结构

(1)描述

C语言中顺序存储结构采用一维数组结构，

描述如下：

#define MAXSIZE n

int queue[MAXSIZE]；

int front,rear;

(２)约定

front为队头指针,指示队头元素的的前

一个位置 ;

rear 为队尾指针,指示队尾元素的位置。

停止放映

第 33 页

(３)基本操作

初始时, front=-1; rear=-1;

front= =rear 队空

X入队操作, rear=rear+1;

queue[rear]=x;

出队操作, front=front+1;

x=queue[front];

return x;

队空, front= =rear;

队满,rear= =(MAXSIZE-1);?

初始化、入队、出队、队空？、队满？

停止放映

第 34 页

举例：顺序队列的入队、出队操作

( A)空队列

( B) A,B,C,D,E入队

( C) A,B,C出队

A B C D E

front rear

D E

front rear

入队时,rear在变

出队时,front在变

停止放映

第 35 页

举例、顺序队列的入队、出队操作

( D) F,G,H入队

(B) D,E,F,G,H出队，出现假, 溢出,

注,一方面队列中是空的，另一方面又出现溢出。

显然，这是逻辑设计上的问题。

front

front rear

D E F G H

rear

停止放映

第 36 页

4,循环队列

? (１)循环队列的概念

? 如果使当 rear = MAXSIZE 时，即超过队列末端时，

令 rear = 0；从而使队列的首尾相连接，只有当

队列中真正没有空位置时，才产生溢出。

? 设定 queue[0]接在 queue[MAXSIZE-1]之后,使得

if ( rear > MAXSIZE-1 )

rear = 0 ;

else

rear＝ rear + 1;

这样构成循环队列。

停止放映

第 37 页

(2)循环队列的指针移动

( 1) 队头指针

front = (front+1)% MAXSIZE；

等价于,

if( (front+1) >=MAXSIZE)

front = 0 ;

else

front ＝ front + 1;

( 2)队尾指针

rear = (rear+1) % MAXSIZE ；

等价于,

if ( (rear+1) >=MAXSIZE )

rear = 0;

else

rear＝ rear + 1;

循环队列在指针移动处理时与一般队列不同：

？ ( front+1) %MAXSIZE 与 front%MAXSIZE+1

相同吗？

停止放映

第 38 页

(3)循环队列队空、队满条件

? 队空条件

front ＝ = rear ；

? 队满条件

? (队头和队尾间有一空闲

? 单元时认为已满 )

front ＝ = ( rear＋１) % MAXSIZE

rear

front

2 3

MAXSIZE,..

2 3 4

...

reari+1front

...

MAXSIZE

a2 a3

ai+1

停止放映

第 39 页

(４) 循环队列入队操作

数据结构定义,

#define MAXSIZE n

int queue[MAXSIZE]；

int front,rear；

算法 1-12描述,

step1 判别队列是否已满 ;

step2 队尾指针后移一个位置,将新

结点元素值存入当前结点单元。

停止放映

第 40 页

循环队列入队操作程序

addqueue(int x)

{ if (front = = ( rear＋１) % MAXIZE)

{ printf(“循环队列已满 \n”);

exit(1);

}

else

{ rear = ( rear＋１) % MAXSIZE;

queue[rear] = x ;

}

停止放映

第 41 页

(５)循环队列出队操作

循环队列出队操作

算法 1-13描述,

step1 判别队列是否为空 ;若空,

则显示队列 ‘ 下溢 ’ ;

step2 队头指针后移一个位置。

Step3 返回该位置上的元素,

停止放映

第 42 页

循环队列出队操作程序

Int delqueue( )

{ int y;

if ( front = = rear )

{ printf(, 循环队列已空 \n”) ;

y = -1 ；

}

else

{ front = (front+1) % MAXSIZE；

y = queue[front] ；

}

return y ；

}

停止放映

第 43 页

5、队列的链式存储结构

? (1)概念

? 用带头结点的单链表作为队列的存储结构，称

为队列的链式存储结构。

? (２)存储结构的 C语言描述，

struct qnode {

int data ；

struct qnode * next；

} ；

typedef struct qnode QNODE ；

QNODE *front,*rear；／＊队头队尾＊／

data next

数据域指针域

停止放映

第 44 页

(３)链队列为空的表示

链队列为空,

Queue.front = Queue.rear

表示形式：

非空队列,

front

rear ^

front

rear ^..,ana2a1

链队满的条件为,T = NULL。 T 为新创建的结点,

停止放映

第 45 页

(４)链队列的入队操作

算法 1-14描述,

step1 申请建立一个新结点 T;

step2 判别 T是否为空 ;若空,表示

队列已满 ;

step3 非空,将 T插入链中,修改

rear指针。

停止放映

第 46 页

链队列的入队操作

addqueue(int x)

{ QNODE *t;

t = (QNODE*)malloc(sizeof(QNODE));

if ( t = = NULL)

{ printf(, 内存无可用空间 \n”);

exit(1);

}

else

{ rear -> next = t; rear = t;

t ->data = x;

t ->next = NULL ;

}

停止放映

第 47 页

(５)链队列的出队操作

出队操作要考虑两种情况 ;

? 当队列长度为 1时,除了修改队头指针外,还要

修改队尾指针。

? 当队列长度大于 1时,只修改队头指针即可。

an ^frontrearQueue

Queu

front

rear ^ an ^

Queue

front

rear

front

a1 an ^

a2,..

a2 ^,.,an ^

停止放映

第 48 页

链队列的出队操作

算法 1-15描述,

step1 判别队列是否为空 ;若空,则显示

队列 ‘ 下溢 ’ ;

step2 非空,则判别队长度是否为 1;

step2.1 不为 1,修改头指针 ;

step2.2 为 1,则修改头、尾指针；

step3 释放 T。

停止放映

第 49 页

链队列的出队操作的程序

delqueue( )

{ int x;

QNODE *t;

if ( front = = rear)

{ printf(“链队列已空 \n”); exit(1) ; }

else

{ t = front->next; front->next = t->next;

if (t->next = = NULL ) rear = front;

free(t);

}

停止放映

第 50 页

6、队列的应用

?OS(Operating System)中

的各种排队器,

? 缓冲区中的循环使用技术,

? 离散事件模拟,

停止放映

第 51 页

三、串

? １。什么是串

? 串是字符的有限序列，它是由单个字符

组成的特殊线性表；记为：

String=?a1 a2 a3 … an?

? n是串的长度,n?0; n为 0表示空串。

? 串中任意个连续字符组成的字符子序列

称为子串。

? 当 2个串的长度相等，且各对应位置上

的字符都相同时，称两个子串是相等的。

停止放映

第 52 页

2、串的基本操作

? LENGTH( S) 求串 S的长度。

? SUBSTR( S,start,len)

从串 S中的 start位置开始,求 len个字符的子串。

DATE=?20?+SUBSTR( ’ 03/07/00?,7,2) +?年 ‘

? CONCAT( S1,S2) 联接 S1和 S2，组成一个新串

S=CONCAT( ’ Str?,’ ing?)

? INDEX( S1,S2) 确定 S2在 S1中的位置。

? REPLACE( S1,S2,S3)

用串 S3替换串 S1中所有与串 S2相等且不重叠的

子串。

停止放映

第 53 页

3.串的存储结构

(1)串的顺序存储结构

有些计算机采用的字编址方式,即数组元素的分量

占 4个字节。由此产生紧缩和非紧缩存储区别。

? 紧缩存储

一个字的存储单元中存放 4个字符；特点：

– 节省空间

– 需要二次寻址，牺牲了 CPU时间。

? 非紧缩存储

一个字的存储单元中只存放 1个字符。特点：

– 寻址快

– 浪费空间，存储密度低。

停止放映

第 54 页

(2)串的链表存储结构

链式存储结构的特点：

? 插入、删除操作效率高；

? 存储空间的利用率低；

– 对于紧缩存储存储利用率是 50%

( data 域 4个字节，指针域也 4个字节)；

– 对于非紧缩存储存储利用率是 12.5%

( 8个字节只存放一个字符)。

( 与顺序存储结构类似也有紧缩和非紧缩存

储结构的区别) 。

停止放映

第 55 页

字符串的链式存储举例

程序

停止放映

第 56 页

指针链接情况

变量与指针

内存映像

停止放映

第 57 页

(３)堆存储结构

? 串的顺序存储和链表存储各有利弊，在实际应用

中常采用一种动态存储结构，称其为堆结构。

? 定义一个很大的连续空间和相应的指针结构。指

针用来指示串在堆中的位置；

? 例如，设有 a=?BEI?,b=? JING?,c=??，

d=?SHANGHAI?；

串名串长起始地址

a 3 1

b 5 4

c 0 9

d 8 9

B E I J I N G S H

A N G H A I

停止放映

第 58 页

四、数组( Array)

? 1.数组的定义

? 数组是相同类型数据元素的有限集合；

? 数组中的各个分量称为数组元素；

? 每个数组元素值可以用数组名和一个下

标值唯一的确定；

数组是有限个数组元素的集合。

数组中所有元素有相同的特性。

每个数组元素由数组名和下标组成。

每组有定义的下标值有一个与该下标值对应的

数组元素值。

停止放映

第 59 页

2、数组的逻辑结构的形式定义

? 二维数组

2_Array=(D,R)

D 是某种数据类型的有限元素集合,且

D={ aij|i=c1,d1,j=c2,d2,aij ?D0 }

R是行、列关系的有限集合，且

R={ ROW, COL }，又

ROW={ |c1?i?d1,c2?j?d2-1,aij,aij+1 ? D0 }

COL={ < aij,ai+1j>|c1?i?d1-1,c2?j?d2,aij,ai+1j ? D0 }

ci 是第 i维的下界

dj 是第 j维的上界

两维数组的元素个数为, (d1-c1+1)*(d2-c2+1)

停止放映

第 60 页

3.数组元素之间的关系

二维数组 m行 n列可以看作是 m个或 n个一维数组,

Amxn = ((a11a12… a1n),(a21a22… a2n),..

(am1am2… amn))

或, a11 a12 a1n

a21 a22 a2n

Amxn =

am1 am2 amn

......,..,..

停止放映

第 61 页

4、数组的操作

数组有两种基本的操作：

– 给定下标，存取相应的数组元素；

– 给定下标，修改相应数组元素的值。

停止放映

第 62 页

5、数组的顺序存储结构

? 数组元素是连续存放的，因此只

能采用顺序存储结构。

? 无论几维数组,在计算机中都是

按一维数组来存放。数组存放通

常采用两种方式：

– 按行优先顺序 (pascal C)

– 按列优先顺序 (Fortran)

停止放映

第 63 页

按行优先顺序存储结构

按行优先顺序存放是将数组看作若干个行向量。

例如,二维数组 Amxn，可以看作 m个行向量，每个行

向量 n个元素。数组中的每个元素由元素的两个下

标表达式唯一的确定。

地址计算公式,

LOC( aij) =LOC( a11) +(( i-1) *n+( j-1)) *L

其中,L 是每个元素所占的存储单元。

停止放映

第 64 页

二维数组按行优先存储举例

有二维数组如下：

a11 a12 a13 a14

A3x4 = a21 a22 a23 a24 =

a31 a32 a33 a34

1 2 3 4 5 6 7 8 9 10 11 12

(( a11,a12,a13,a14)，( a21,a22,a23,a24)，( a31,a32,a33,a34))

LOC( a23) = LOC( a11) +( 2-1) x4+( 3-1) = 7

LOC( a34) = 1 + ( 3-1) x 4 + ( 4-1) = 12

LOC( a14) = 1 + ( 1-1) x 4 + ( 4-1) = 4

停止放映

第 65 页

按列优先顺序存储结构

按列优先顺序存放是将数组看作若干个列向量。

例如,二维数组 Amxn，可以看作 n个列向量，

每个列向量 m个元素。数组中的每个元素由元

素的两个下标表达式唯一的确定。

地址计算公式：

LOC( aij) =LOC( a11) +(( j-1) *m+( i-1)) *L

其中,L 是每个元素所占的存储单元。

停止放映

第 66 页

二维数组按列优先存储举例

有二维数组如下：

a11 a12 a13 a14

A3x4 = a21 a22 a23 a24 =

a31 a32 a33 a34

1 2 3 4 5 6 7 8 9 10 11 12

(( a11,a21,a31)，( a12,a22,a32)，( a13,a23,a33)，( a14,a24,a34))

LOC( a23) = LOC( a11) +( 3-1) x 3 +( 2-1) = 8

LOC( a34) = 1 + ( 4-1) x 3 + ( 3-1) = 12

LOC( a14) = 1 + ( 4-1) x 3 + ( 1-1) = 10

停止放映

第 67 页

６、数组的压缩存储

实际工程问题中推导出的数组常常是高阶、

含大量零元素的矩阵,或者是些有规律

排列的元素。为了节省存储空间，通常

是对这类矩阵进行压缩存储。

压缩的含义是,

– 相同值的多个元素占用一个存储单元；

– 零元素不分配存储单元。

停止放映

第 68 页

能够采用压缩存储的矩阵

? 对称矩阵存储主对角线以上(下)的元素；

? 上(下)三角矩阵只存储三角阵元素；

? 带状矩阵只存储带状元素；

? 稀疏矩阵只存储非零元素；

? 大量相同元素矩阵存储某元素和重复个数。

停止放映

第 69 页

对称矩阵的压缩存储

对称矩阵的元素满足：

aij = aji 1 ? i, j ? n

因此将 n*n 个元素压缩存放到 n( n+1) /2

个单元的一维数组 S(( n+1) *n/2)中。

(按行存放) aij的地址为：

i( i-1) /2+j 当 i?j

LOC( aij) =

j( j-1) /2+i 当 i

停止放映

第 70 页

对称矩阵的压缩存储举例

设有 A3x3矩阵,

a11

A3x3 = a21 a22

a31 a32 a33

存于一维数组 S[6]

S[6]=( a11,a21,a22,a31,a32,a33 )

1 2 3 4 5 6

LOC(a31)=3(3-1)/2+1= 4

LOC(a22)=2(2-2)/2+2= 3

LOC(a21)=2(2-1)/2+1= 2

停止放映

第 71 页

作业、思考题

1,思考题：

1) 试写出“在带头结点的单循环链表中求表长的算法”。

2) 假设一单循环链表的长度大于 1，且表中即无头结点也

无头指针。已知 S为指向链表中某结点的指针。试写出

删除表中结点 S 的算法。

3) 假设以数组 sequ[m-1]存放循环队列的元素，设变量

rear和 quelen分别为指示队尾元素位置和队中元素个

数，试写出入队和出队算法。

2,第 1章作业：

8,10,11,16

3,作业要求：

– 作业命名方式为,学号,章数 _序号

00103001_ch01.doc

答疑时间：周五晚,7:00— 9:00

网上答疑,http://202.117.35.170/bbs/bbs.asp

西安交通大学计算机软件,3_西安交通大学：计算机软件基础_ppt_大学课件预览_高等教育资讯网...

相关文章

将midi转为json后转为str进行压缩长度而后在转为json

家用洗地机值得入手吗?洗地机口碑榜

html家电分类,电器有哪些种类？家用电器都有哪些类型？

深度剖析家用洗地机的方案设计

CleanMate吸尘器机器人_Cleanmate拖地机器人全自动擦地机家用智能扫地机电动拖把...

扫地机器人什么牌子的好费电吗_哪种家用扫地机器人最好扫地机器人十大品牌排名...

解决IDEA项目external libraries依赖包消失的问题

【Quartus FPGA】EMIF DDR3 IP 仿真记录