null数 据 结 构 数 据 结 构 （C语言版）作者：黎剑兵 第 一 章 绪 论 第 一 章 绪 论 [学习内容]
常用术语
算法评价
时间复杂度与空间复杂度的分析
[重点]了解逻辑结构 物理结构和数据的运算三方面相关概念及相互关系
[难点] 时间复杂度的分析方法
[掌握] 用类C语言的表示方法会用类C编写程序null计算机科技 是 一门研究用计算机进行信息表示和处理的科学。
主要涉及两方面的问题：信息的表示和信息的处理
信息的表示和组织直接关系到处理信息的程序 的效率，随着计算机的应用领域的扩大。信息量的增加，信息范围的拓宽，使系统程序和应用程序的规模的日趋增大，结构也日趋增大。因此，为了编写出一个“好”的程序，必须分析 处理的对象的特征及个对象之间的存在的关系。这就是本课程所要研究的问题。
第 一 章 绪 论null计算机程序 是 对信息进行加工处理。这些信息之间大多数情况下往往具有重要的结构关系。这就是数据结构的内容。那么，什么是数据结构呢？
第 一 章 绪 论null1.地位第 一 章 绪 论null1.地位第 一 章 绪 论数据结构
Data Structurenull数据模型 问题 实现 2.主要内容 第 一 章 绪 论null(1)要对所加工的对象进行逻辑组织
(2)如何把加工对象存储到计算机中去？
(3)数据运算
数据模型 问题 实现 2.主要内容 第 一 章 绪 论null数据结构 是一门研究非数值 计算的程序设 计问题中计算机的 操作对象以及它们之间的关系和 操作等等的学科。
3. 学科定义<1-1> 什么是数据结构null数据元素(data element) 数据基本单位，也称节或孩子，可由若干个数据项组成。数据项是数据最小单位
数据(data) 是对客观事物的 表示，指所有能输入到计算机并被计算机程序处理的符号的总称。
数据对象( data object)性质相同的数据元素的集合
数据结构 数据元素之间的相互关系<1-2> 基本概念和术语null
1) 集合<1-2> 基本概念和术语数据间的四种典型结构：2）线形3）树形4）图或网络：null 1) 集合
<1-2> 基本概念和术语四种典型结构：null 2）线形：
四种典型结构<1-2> 基本概念和术语null 3）树形：
四种典型结构：<1-2> 基本概念和术语null4）图或网络：
四种典型结构：<1-2> 基本概念和术语null（6）物理结构(存储结构)： DE及关系在计算机中的表示。
DE存储称为节点
关系存储：a. 顺序存储 b. 链式存储
<1-2> 基本概念和术语（5）逻辑结构：从具体问题抽象出的数学模型。体现逻辑关系。null（7）DS广义定义：
DE 的逻 辑 结 构
DE 的物 理 结 构
DE 的 抽 象 运 算
（8）基本操作
加工型：插入 删除 更新 排序
引用型：查找
<1-2> 基本概念和术语null<1-2> 基本概念和术语null算法是对特定问题求解步骤的一种描述，是指令的有限序列。
特性：
有穷性 确定性 可行性 输入 输出
<1-3> 算法和算法分析一、算法定义null二、算法的描述与分析
描述：类C语言
要求
正确性： a. 语法 b. n个输入
c. 一组典型的苛刻的输入 d. 所有输入
可读性
健壮性
效率与存贮量
<1-3> 算法和算法分析null分析标准
a 、时间复杂度 ：算法中基本操作重复执行的次数(频度)。
T(o)=O(f(n))
时间复杂度分为平均时间复杂度和最坏时间复杂度
复杂度的值取规模函数最高阶
<1-3> 算法和算法分析null分析标准
a 、时间复杂度 ：算法中基本操作重复执行的次数。
T(o)=O(f(n))
时间复杂度分为平均时间复杂度和最坏时间复杂度
复杂度的值取规模函数最高阶
<1-3> 算法和算法分析b 、空间复杂度： 算法所需存贮空间
S(n)=O(f(n))null<1-3> 算法和算法分析例：分析下列语句段的时间复杂度
m = 0; 1
for( k=0;k
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
下面问题算法，并分析最坏情况时间复杂性:
在数组 A[1..n]中查找值为 K的元素，若找到输出其位置 i ( 0< i 0) ListDelete (A，k); //若在线性表A
//中找到则将其删除
} }
§2.1 线性表的类型定义基本运算基本运算[例]2.2 利用线性表的基本运算，编写将线性表A和B中公共元素生成线性表C的算法
§2.1 线性表的类型定义[解] 先始化线性表C，然后依次检查线性表A中的每个元素，看它是否在线性表B中；若在线性表B中，则将其插入到线性表C中.nullvoid celem(sqlist A，sqlist B，sqlist &C){
int i，k，j=1； ElemType x；
InitList(C)；
for (i=1；i<=Getlen(A)；i++) {
x=GetElem(A,i); //依次获取线性表A中的元素，
//存放在x中
k=LocateElem(B，x); //在线性表B中查x
if (k>0) {Insert(C,x,j);j++; } //若在线性表B中
}} //找到，将其插入C
§2.1 线性表的类型定义null一、 线性表的顺序存储（顺序表）
定义：把线性表中所有元素按其逻辑顺序依次存储到指定位置开始的连续空间中。即用一组地址连续的存储单元存放一个线性表
特点：
实现逻辑上相邻—物理地址相邻
实现随机存取
实现：
（一维）数组
§2.2 线性表的顺序存储和实现null线性表的顺序存储结构示意图
§2.2 线性表的顺序存储和实现ElemType类型的数组list[MaxSize]存储线性表
A= (a1 , a2 , … , ai , ai+1 , … , an)
元素地址计算方法 第i个元素的存储位置为：list+(i-1)*sizeof(ElemType)null元素地址计算方法 ： lLOC(ai)=LOC(a1)+(i-1)*L
lLOC(ai+1)=LOC(ai)+L
其中：
uL一个元素占用的存储单元个数
uLOC(ai)—线性表第i个元素的地址
§2.2 线性表的顺序存储和实现nulla2§2.2 线性表的顺序存储和实现nulltypedef struct card{
int num;
char name[20];
char author[10];
char publisher[30];
float price;
}DATATYPE;
§2.2 线性表的顺序存储和实现线性表的顺序存储示例（图书资料）null
可以定义为静态数组或变量
DATATYPE library[M];
或动态申请和释放内存
DATATYPE *pData；
pData=(DATATYPE*)malloc(sizeof(DATATYPE));
free(pData )；§2.2 线性表的顺序存储和实现线性表的顺序存储示例（图书资料）null插入一个元素
定义：线性表的插入是指在第i 个元素之前插入一个新的数据元素x，使长度为n的线性表
( a1, a2 , …, ai-1, ai, …an)
变成长度为n+1的线性表
(a1, a2, …, ai-1, x, ai, … an )
§2.2 线性表的顺序存储和实现nullint sxbcr(int i,int x,int v[],int *p){
int j,n; n=*p;
if((i<1) || (i>n+1))
return (0);
else { for(j=n;j>=i;j--)
v[j]=v[j-1];
v[j]=x; *p=++n;
return (1);
}
}
§2.2 线性表的顺序存储和实现插入一个元素算法null§2.2 线性表的顺序存储和实现插入一个元素图示1null§2.2 线性表的顺序存储和实现插入一个元素图示2xnull插入算法时间复杂度T(n)
Pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：
§2.2 线性表的顺序存储和实现向线性表中表头插入一个元素向线性表中表头插入一个元素InsertFront(List* L,const ElemType& item){
if(L->size = = MaxSize){
printf(“List overflow!” );
return; }
for(i = L->size – 1; i >= 0; i-- )
L->list[i+1] = L->list[i];
L->list[0] = item;
L->size ++;
}
§2.2 线性表的顺序存储和实现向线性表中满足条件的位置插入一个元素向线性表中满足条件的位置插入一个元素void Insert(List* L,const ElemType item){
if(L->size = = MaxSize){
printf( “List overflow!”);
return;}
for(i=0; isize; i++)
if(item < L->list[i]) break;
for(j = L->size –1; j>=i ; j--)
L->list[j+1] = L->list[j];
L->list[i] = item;
L->size ++ ;}
§2.2 线性表的顺序存储和实现向线性表中的末尾添加一个元素向线性表中的末尾添加一个元素void InsertRear(List* L, ElemType item){
if(L->size = = MaxSize){
printf( “List overflow!” );
return;
}
L->list[L.size] = item;
L->size ++;
}
§2.2 线性表的顺序存储和实现null删 除 一 个 元 素
定义：线性表的删除是指将第i（1i n）个元素删除，使长度为n的线性表变成长度为n-1的线性表 需将第i+1至第n共（n-i）个元素前移 §2.2 线性表的顺序存储和实现删 除 一 个 元 素算法删 除 一 个 元 素算法int sxbsc(int i, int v[], int *p)
{ int j,n; n=*p;
if((i<1) || (i>n))
return (0);
for(j=i;jsize = = 0){
printf( “L is an empty list!” );
return 0; }
for(i = 0; i< L->size; i++)
if(L->list[i] = = item) break ;
§2.2 线性表的顺序存储和实现从线性表中删除等于给定值的元素2 从线性表中删除等于给定值的元素2 if(i = = L->size){
printf( “Deleted element is not exist!” );
return 0;}
for(int j = i+1; jsize; j++)
L->list[j-1] = L.list;
L->size -- ;
return 1; }
§2.2 线性表的顺序存储和实现null[例] 已知线性表(ao，a1，…，an-1)按顺序存
储，且每个元素都是均不相等的 整数。设计
把所有奇数移到所有的偶数前边的算法(要求
时间最少，辅助空间最少)。§2.2 线性表的顺序存储和实现 [解] 从左向右找到偶数A.data[i]，从右向左找到奇数A.data[j]，将两 者交换；循环这个过程直到i大于j为止nullvoid move(sqlist A){
int i=0,j=A.len-l,k; ElemType temp;
while (i<=j) {
while (A.data[i]%2==1) i++;
while (A.data[j]%2==0) j--;
if(idata表示p指向结点的数据域
(*p).next/p->next表示p指向结点的指针域
生成一个LNode型新结点：
p=(LNode *)malloc(sizeof(LNode));
系统回收p结点：free(p)
§ 2.3 线性表的链式存储结构null头结点：在单链表第一个结点前附设的一个结点。
头结点指针域为空表示线性表为空
§ 2.3 线性表的链式存储结构nullStatus ListSearch_L(LinkList L,int i, datatype *e){
P = L->next;j = 1;
While(p!=NULL && jnext; j++;}
if(p==NULL) return ERROR;
*e = p->data;
return OK；
}
§ 2.3 线性表的链式存储结构在带头节点的单链表中查找第 i 个结点null在带头节点的单链表中第 i 个结点处插入新元素 x
§ 2.3 线性表的链式存储结构nullStatus ListInsert_L ( LinkList L, ElemType x, const int i ) {
p=L;j=0;
while (p&&j< i-1){p=p->next;j++;}//找第i-1个结点
if ((p= =NULL )|| (j > i-1)){
printf( “无效的插入位置!\n”);return ERROR;}
//创建新结点,数据为x,指针为NULL
s=(LinkList )malloc(sizeof(LNode));
s ->data = x;s->next = p->next; p->next = s;
return OK;}
§ 2.3 线性表的链式存储结构null删除元素 ：
§ 2.3 线性表的链式存储结构null删除元素 ：§ 2.3 线性表的链式存储结构Status ListDelete_L (LinkList L,int I,ElemType *e){
P = L; j= 0;
While(p->next&&jnext; ++ j;
}
if(!(p->next)||j> i-1) return ERROR;//删除位置不合理
q = p->next; p->next = q->next; //删除并释放结点
*e = q-> data ;free(q);
return OK;
}//ListDelete_L
null § 2.3 线性表的链式存储结构两个有序单链表合并为一个有序单链表(非递减)MergeList_L(Linklist La,LinkList Lb,LinkList Lc){
pa = La->next; pb = Lb->next;
Lc = pc = La;
While (pa && pb){
If(pa->data <= pb->data){
pc->next = pa;pc = pa; pa = pa->next;
}
else{pc->next = pb;pc = pb; pb= pb->next;}
}
pc->next = pa?pa:pb;
free(Lb);
}
null单链表特点
它是一种动态结构，整个存储空间为多个链表共用
不需预先分配空间
指针占用额外存储空间
不能随机存取，查找速度慢§ 2.3 线性表的链式存储结构单链表具有单向性的缺点null循环链表:表中最后一个结点的指针指向表头结点，使链表构成环状
特点：从表中任一结点出发均可找到表中其他结点，提高查找效率
§ 2.3 线性表的链式存储结构null§ 2.3 线性表的链式存储结构循环链表操作与单链表基本一致,循环条件不同
单链表:
p或p->next=NULL
循环链:
p或p->next=H 2.3.3双向链表（double linked list )2.3.3双向链表（double linked list )结点定义
typedef struct node{
datatype data;
struct node *prior,*next;
}DLNode,*DLinkLIst
§ 2.3 线性表的链式存储结构指向前驱结点 数据 指向后继结点 null空双向循环链表：非空双向循环链表：L§ 2.3 线性表的链式存储结构双向链表图例nullp->prior->next= p= p->next->proir;§ 2.3 线性表的链式存储结构双向链表图例在给定结点p前插入一个新结点在给定结点p前插入一个新结点§ 2.3 线性表的链式存储结构在给定结点p前插入一个新结点 在给定结点p前插入一个新结点 S=(DLinklist)malloc(sizeof(DLNode));
s->data = x;
s->prior = p->prior; ①
s->next = p;②
p->prior->next = s;③
p->prior = s; ④§ 2.3 线性表的链式存储结构删除给定结点p删除给定结点p p->prior->next=p->next;p->next->prior=p->prior;§ 2.3 线性表的链式存储结构删除给定结点p动画演示 删除给定结点p动画演示 p->prior->next=p->next;p->next->prior=p->prior;§ 2.3 线性表的链式存储结构删除给定结点 p 算法 删除给定结点 p 算法 p->prior->next = p->next;
p->next->prior = p->prior;
free(p); 就这么简单！§ 2.3 线性表的链式存储结构null§3 存储结构的选用顺序与链式存储结构的选用应考虑因素：
（1）存储空间
（2）运算时间
（3）程序设计语言null习题与练习 二1.描述以下三个概念的区别：
头结点、头指针和开始结点
2.从尾指针出发能访问到链表上所有结点的链表有 。
3.假设有两个按元素值递增的线性表 A、B，编写算法将两表合并为一个按元素值递减的线性表C。（分别以顺序、链式实现）
null习题与练习 二 4.设线性表存放在向量 A[MAXSIZE]的前elenum个分量中，且递增有序。试写一算法，将 x 插入线性表适当位置上，以保持线性表的有序性，并且分析算法的时间复杂性。
5.以链式存储结构实现上题。
null习题与练习 二 6.在双向链表上实现线性表的下列基本运算：
(1) 初始化
(2) 定位
(3) 插入
(4) 删除第三章 栈与队列第三章 栈与队列【学习内容】
栈的抽象数据类型、顺序表示、链表表示及相应操作 (特别注意栈空和栈满的条件）
队列的定义、特性
队列的抽象数据类型、顺序表示、链表表示及相应操作 （特别是循环队列中队头与队尾指针的变化情况）
栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。§ 3.1 栈（stack）§ 3.1 栈（stack）§ 3.1.1 定义
通常称插入、删除的这一端（如表尾）为栈顶(Top)，另一端（表头）为栈底(Bottom)。当表中没有元素时称为空栈
特点：先进后出（FILO）或后进先出（LIFO）
第 三 章 栈 与 队列 null例：假设栈S=(a1，a2，a3，…an)
则a1称为栈底元素，an为栈顶元素。
进栈 top+1;新元素插入elements[top]位置
出栈 top-1;栈中元素按a1，a2，a3，…an的次序进栈，退栈按后进先出的原则进行的,因此按an ……a3 a2 a1的次序出栈 3.1 栈 （stack）null（1）建立一个空栈 IniStack(&s)
（2 ）判断一个栈是否为空 StackEmpty(&s)
（3）进栈 Push(&s,x)
（4）出栈 Pop(&s,&e)
（5）获得栈顶元素值 GetTop(s,&e)
3.1 栈 （stack）栈的主要操作：null进栈：top+1;新元素插入elements[top]位置
出栈：top-1栈s=(a1,a2,……,an)3.1 栈 （stack）栈的图示 null3.1 栈 （stack） 栈和线性表类似，也有两种（顺序、链式）实现方法null存储结构定义
#define MAXSIZE 6
typedef struct{
datatype elements[MAXSIZE];
int top;
}SqStack;3.1 栈 （stack）一、栈的顺序存储 null栈顶指针top
指示栈顶元素在顺序栈中的位置
top=-1,栈空，此时出栈，则下溢（underflow）
top= MAXSIZE-1,栈满，此时入栈，则上溢（overflow）
3.1 栈 （stack）栈的顺序存储 null3.1 栈 （stack）顺序栈进、出栈图示 栈顶指针top,指向实际栈顶
后的空位置，初值为-1进栈A出栈栈满BCDEF设数组维数为M
top=-1,栈空，此时出栈，则下溢（underflow)
top=M-1,栈满，此时入栈，则上溢（overflow)栈空nullStatus Push(SqStack *S,datatype e){
If(S->top >= MAXSIZE-1) /*上溢*/
return ERROR;
S->top ++; S->elements[S->top] = e;
return OK;
}
3.1 栈 （stack） 进栈算法nullStatus Pops (SqStack *S,datatype *e){
If (S->top == -1) /*下溢*/
return ERROR;
S->top --; *e = S->elements[S->top+1];
return OK;
}
3.1 栈 （stack） 出栈算法二、链栈（单链表） 二、链栈（单链表） 3.1 栈 （stack）typedef struct node
{ int data;
struct node *link;
}LinkList;结点定义链栈的特点链栈的特点链表的存储结构与链接存储的栈完全相同，只是链头指针就是栈顶指针。初始时为NULL
链式栈无栈满问题，空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作3.1 栈 （stack）null进栈等同于不带头结点单链表的头插法
Status Push(LinkList * S,datatype e ){
p = (LinkList *)malloc(sizeof(Linklist));
p->data = e;
p->next = S->top;
S->top = p;
return OK;}
3.1 栈 （stack）链栈的进栈算法null出栈等同于删除第一个结点
Status Pop(LinkList * S,datatype *e ){
If(S->top==NULL) return ERROR;/*下溢*/
p = S->top;
S->top = p->next;
*e = p->data;
free(p);
return OK;
}
3.1 栈 （stack）链栈的出栈算法3.1.3 栈的应用3.1.3 栈的应用(1)“回溯”问题求解
(2) 过程的嵌套和递归调用
3.1 栈 （stack）3.1.3 栈的应用3.1.3 栈的应用1．嵌套调用3.1 栈 （stack）nulls3.1 栈 （stack）嵌套调用过程图示null
递归：函数直接或间接的调用自身的过程
©一个对象部分地包含它自己，或是用它自己给自己定义
©一个过程直接地或间接地调用自己
©利用前面运算来求得答案的过程
实现：建立递归工作栈
优点：递归函数结构清晰，程序易读，正确性易证明
缺点：速度慢，空间大效率低3.1 栈 （stack）2．递归调用null递归算法的一般形式
3.1 栈 （stack）void p (参数表) {
if （递归结束条件）
可直接求解步骤；-----基本项
else p（较小的参数）；------归纳项
} null3.1 栈 （stack）例：求n! = 1， n=0
n*(n-1)！ n>0int Factorial(int n){
if (n==0) return 1;
return n*Factorial(n-1);
} null例 ：递归的执行情况分析 3.1 栈 （stack）null例 递归的执行情况分析void print(Int w)
{ int i;
if ( w!=0)
{ print(w-1);
for(i=1;i<=w;++i)
printf(“%3d,”,w);
printf(“/n”);
}
} 3.1 栈 （stack）运行结果：
1，
2，2，
3，3，3，null上例图示分析
3.1 栈 （stack）null3、括号的匹配检验 3.1 栈 （stack）假设表达式中有多种扩号，可以用栈来进行扩号匹配检验，具体做法为：
非括号字符跳过不理；碰上左扩号，入栈；碰上右扩号，出栈，并且检查出栈元素是否与当前右扩号相匹配，若匹配继续检查，否则匹配失败。请同学们下去自己编程序试试。null一、队列定义
队列是限定只能在表的一端进插入，在表的另一端进行删除的线性表
队尾(rear)——允许插入的一端
队头(front)——允许删除的一端
队列特点：先进先出(FIFO) 3.2 队列（QUEUE）null假设队列S=(a1，a2，a3，…an)，
则a1称为队首元素，an为队尾元素。
队中元素按a1，a2，a3，…an的次序入队，出队按先进先出的原则进行的,因此a1，a2，a3，…an的次序出队
front 和rear的初始值地队列初始化时均应置为-1。
3.2 队列（QUEUE）队列定义null入队时将rear+1, 新元素插入elements[rear]位置.
出队时，将加front+1, 删去元素3.2 队列（QUEUE）a1 a2 a3…………………….an 入队出队frontrear队列Q=(a1,a2,……,an)队列定义null3.2 队列（QUEUE）双端队列null（1）建立一个空队列 InitQueue(&Q)
（2）进队 EnQueue(&Q,e)
（3）出队 DeQueue(&Q,&e)
（4）判断一个队列是否为空
QueueEmpty(Q)
（5）获得队头元素值 GetHead(Q,&e )
3.2 队列（QUEUE）队列的主要操作null•结点定义
typedef struct node
{ int data;
struct node *next;
}Qnode,*QueuePtr;
3.2 队列（QUEUE）二、链队列null3.2 队列（QUEUE）链队列图示null入队不用考虑队满,但出队要考虑队空 队空条件为 front == rear3.2 队列（QUEUE）链队列图示null3.2 队列（QUEUE）链队列入队算法p = (QueuePtr)malloc(sizeof(Qnode));
p->data = x;
p->next = NULL;
Q->rear->next = p;
Q->rear = p; null3.2 队列（QUEUE）链队列出队算法if(Empty(Q)) return ERROR;
else{ s = Q->front->next;/*指向被删结点*/
if(s->next == NULL){
Q->front->Next = Null;
Q->rear = Q->front;}
Else Q->front->next = s->next;
*e = s->data;
free(s);
return OK;}null三、循环队列--队列的顺序表示和实现3.2 队列（QUEUE）J1J2J3设两个指针front,rear,约定：
rear指示队尾元素；
front指示队头元素前一位置
初值front=rear=-1空队列条件：front==rear
入队列：sq[++rear]=x;
出队列：x=sq[++front];null设数组维数为M，则：
当front=-1,rear=M-1时，再有元素入队发生溢出—真溢出
当front>-1,rear=M-1时，再有元素入队发生溢出—假溢出
解决
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
:
队首固定，每次出队剩余元素向下移动 ——浪费时间
循环队列
3.2 队列（QUEUE）存在问题null循环队列
基本思想：存储队列的数组被当作首尾相接的表处理；让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0。 3.2 队列（QUEUE）实现：利用“模”运算
入队： rear=(rear+1)%M; sq[rear]=x;
出队： front=(front+1)%M; x=sq[front];
队满、队空判定条件null……rearfrontmaxSize-1入队: rear=(rear+1) % MaxSize;
elements[rear]=item
出队：front=(front+1)%MaxSize; 队空：rear = front;
队满：(rear+1) % maxSize=front;012……front012rear队列初始化：front = rear = 0;存储队列的数组被当作首尾相接的表处理。
队头、队尾指针加1时从MaxSize -1直接进到0，可用语言的取模(余数)运算实现。3.2 队列（QUEUE）null3.2 队列（QUEUE）初始状态解决方案：
1.另外设一个标志以区别队空、队满
2.少用一个元素空间：
队空：front==rear
队满：(rear+1)%M==front循环队列出入队图示队空：front==rear
队满：front==rear
null队空 rear = front;
队满 (rear+1) % maxSize=front;
入队 rear=(rear+1) % MaxSize;
elements[rear]=item；
出队 front=(front+1)%MaxSize;
3.2 队列（QUEUE）少用一个元素空间解决方案nullvoid en_cycque(int sq[],int front,int rear,int x){
if(((rear+1)%MAXSIZE)==front)
printf("overflow");
else
{ rear=(rear+1)%MAXSIZE;
sq[rear]=x;
}
}3.2 队列（QUEUE）循环队列入队算法null循环队列出队3.2 队列（QUEUE）int del_cycque(int sq[],int front,int rear,int *q){
if(front==rear)
return(0);
else
{ front=(front+1)%MAXSIZE;
*q=sq[front];
return(1);
}
}
null1. 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问： (1) 设有编号为1,2,3,4,5, 6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?
(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出"进栈"或"出栈"的序列)。 第三章 习题与上机实验null第三章 习题与上机实验 2.假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示环形队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(enqueue)和删除(delqueue)元素的操作。 第四章 数 组第四章 数 组
数组的顺序表示和实现
矩阵的压缩存储: 特殊矩阵 稀疏矩阵
【学习内容】null4.1 数组的定义及运算数组的性质 数组元素数目固定
元素类型相同
下标有界且有序 nulleg. [a1,a2,…,]
[（a11,a12,…a1n）,(a21,a22,…,a2n)]
数组图示 4.1 数组的定义及运算null二 维 数 组4.1 数组的定义及运算数组图示 三 维 数 组null定义：
由值和下标构成的有序对，结构中的每一个元素都与一对下标有关。
运算：
①给定一组下标，存取相应DE
②给定一组下标，修改相应DE
4.1 数组的定义及运算null问题：内存是一维的，如何以一维内存存储多维数组
4．2 数组的顺序表示元素数目、关系固定顺序存储 多维数组以一维方式存储，即数组元素还是数组！null4．2 数组的顺序表示LOC ( i ) = LOC ( i -1 ) + l =α+ i*l一维数组的存储null4．2 数组的顺序表示二维数组的存储null5．2 数组的顺序表示行优先 LOC ( i, j ) = a + ( (i – 0) * m + (j - 0)) * l列优先 LOC ( i, j ) = a + ( (j - 0) * n + (i – 0) ) * l例： n维数组 n维数组各维元素个数为 m1, m2, m3, …, mn
下标为 i1, i2, i3, …, in 的数组元素的存储地址： 4．2 数组的顺序表示null 多个值相同的元素只分配一个空间，零元素不分配空间
4．3 矩阵的压缩存储压缩存储null一、特殊矩阵
定义：相同元素/零元素分布有一定规律的矩阵。
1.对角矩阵 4．3 矩阵的压缩存储null 若将以上两矩阵以一维数组B[M]压缩存储,a[i][j] b[k]三对角阵 单对角阵 4．3 矩阵的压缩存储null2. 上（下）三角矩阵 非零元素共n(n+1)/2个，以数组B[n*(n+1)/2]存储非零 DE
4．3 矩阵的压缩存储null下三角 2. 上（下）三角矩阵 上三角 4．3 矩阵的压缩存储null3. 对称矩阵 aij = aji
k= I(I+1)/2+J ;I = max(i,j),J=min(i,j) 4．3 矩阵的压缩存储好东西啊！null二. 稀疏矩阵 Am*n 中非零元素个数远小于零元素个数4．3 矩阵的压缩存储1．三元组表
组成：所有非零元
浙公网安备 33021202002483