数据基础结构 2

教案纸（首页）第1页第次课学时授课时间___________教学主题数组的基本概念，数组的存储结构教学要求1、掌握数组的逻辑结构特性，数组抽象数据类型的描述方法。2、掌握数组的顺序存储结构及其特点。3、掌握对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储。4、掌握栈在实际求解问题中的应用方法。教学重点数组的顺序存储结构及其特点；对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储方法。教学难点数组的顺序存储结构及其特点；对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储方法。。教学方法讲授+练习教学手段多媒体、上机实操讲授要点1、数组的逻辑结构特性。2、数组的顺序存储结构及其特点。3、对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页教案纸（续页）第3页教学内容备注与后记5.1数组1、数组的定义数组是所有高级编程语言中都已实现的固有数据类型，因此凡学习过高级程序设计语言的读者对数组都不陌生。但它和其它诸如整数、实数等原子类型不同，它是一种结构类型。换句话说，"数组"是一种数据结构。数组的类型定义

ADTArray{

数据对象：D＝{aj1,j2,...,ji,...jN|=ji0,...,bi-1,i=1,2,..,N,

称N(>0)为数组的维数，bi为数组第i维的长度，

ji为数组元素的第i维下标，aj1,...,jN∈ElemSet}

数据关系：R＝{R1,R2,...,RN}

Ri＝{<aj1,...ji,...jN,aj1,...,ji+1,...,jN>|

0≤jk≤bk-1,1≤k≤N且ki,

0≤ji≤bi-2,

aj,...,j,...,j,aj,...j+1,...,j∈D,i=2,...,N}

基本操作：

InitArray(&A,n,bound1,...,boundn)

操作结果：若维数n和各维长度合法，则构造相应的数组A。

DestroyArray(&A)

初始条件：数组A已经存在。

操作结果：销毁数组A。

Value(A,&e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若各下标不超界，则e赋值为所指定的A的元素值，并返回OK。

Assign(&A,e,index1,...,indexn)

初始条件：A是n维数组，e为元素变量，随后是n个下标值。

操作结果：若下标不超界，则将e的值赋给A中指定下标的元素。

}ADTArray2、数组的存储结构由于数组类型不作插入和删除的操作，因此只需要通过"顺序映象"得到它的存储结构，即借助数据元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

通常有两种映象方法：即"以行(序)为主(序)"的映象方法和"以列(序)为主(序)"的映象方法。

以图示的二维数组为例，"以行为主"的存储结构是对二维数组进行"按行切分"，即将数组中的数据元素"按行依次排放"在存储器中；"以列为主"的存储结构是对二维数组进行"按列切分"，即将数组中的数据元素"按列依次排放"在存储器中。

假设二维数组R[m][n]中每个数据元素占L个存储地址，并以LOC(i,j)表示下标为(i,j)的数据元素的存储地址，则该数组中任何一对下标(i,j)对应的数据元素在"以行为主"的顺序映象中的存储地址为：

LOC(i,j)=LOC(0,0)+(in+j)L

在"以列为主"的顺序映象中的存储地址为：

LOC(i,j)=LOC(0,0)+(jm+i)L

其中LOC(0,0)是二维数组中第一个数据元素（下标为(0,0)）的存储地址，称为数组的"基地址"或"基址"。类似地，假设三维数组R[p][m][n]中每个数据元素占L个存储地址，并以LOC(i,j,k)表示下标为(i,j,k)的数据元素的存储地址，则该数组中任何一对下标(i,j,k)对应的数据元素在"以行为主"的顺序映象中的存储地址为：

LOC(i,j,k)=LOC(0,0,0)+(i×m×n+j×n+k)×L

推广到N维数组，则得到

LOC(j1,j2,...jn,)=LOC+(b2×...×bn×j1＋b3×...×bn×j2＋...＋bn×jn-1+jn)×L

=LOC(0,0,...,0)+()×L

可缩写成

LOC(j1,j2,...jn,)=LOC(0,0,...,0)+

其中Cn=L，Ci-1=bi×Ci,1<i≤N。5.2矩阵的压缩存储结构特殊矩阵的压缩存储方法

如果矩阵中值相同的元素或零元素在矩阵中的分布有一定规律，则称之谓"特殊矩阵"。大致有这样三类特殊矩阵：

1.对称矩阵：若n阶方阵A中的元满足特性

aij=aji1≤i,j≤n

则称为n阶对称矩阵；

2.三角矩阵：若n阶方阵中下(上)三角(不包括对角线)中的元均为常量c或0，则称为上(下)三角矩阵；

3.对角矩阵：若n阶方阵中的非零值元都集中在以主对角线为中心的(由k条对角线组成的)带状区域中，则称为k对角矩阵。

若为对称矩阵中的每一对值相同的元素分配一个存储空间，则可将矩阵中n2个元压缩存储到n(n+1)/2个存储空间中。

假设以一维数组sa[n(n+1)/2]压缩存储n阶对称方阵A，则一维数组中的数据元素和方阵中的元之间存在着下列一一对应的关系：

对于任意给定一对行列号(i,j)，均可在sa中找到方阵的元aij，反之，对于所有的k=0,1,…,n(n+1)/2-1，都能确定sa[k]中的元素在矩阵中的位置(i,j)。

三角矩阵示例

对角矩阵示例

由于特殊矩阵中的非零值元素在矩阵中的分布有着一定的规律，则可将这些非零值元连续存储在一个一维数组中。即矩阵中的任何一个元和它们在一维数组中的位置之间存在着某种"转换关系"，并且这种转换关系可以用数学公式表示之。显然，对于下(上)三角矩阵和对角矩阵也可得到类似对应关系。教学总结：本章节介绍了数组的基本定义，数组的顺序存储结构特点，对称矩阵、上三角矩阵、下三角矩阵和三对角矩阵的压缩存储，重点掌握数组下标的转换。

第次课学时授课时间__________教学主题稀疏矩阵教学要求1、掌握稀疏矩阵的特点。2、掌握稀疏矩阵的两种压缩存储方法。教学重点稀疏矩阵的特点；稀疏矩阵的三元组表示及其基本运算算法设计。教学难点稀疏矩阵的三元组表示及其基本运算算法设计。教学方法讲授教学手段多媒体、板书讲授要点1、稀疏矩阵的特点。2、稀疏矩阵的三元组和十字链表存储结构。作业参考资料教材：数据结构教程（第5版），清华大学出版社，李春葆等2017。参考资料：数据结构（C语言），清华大学出版社，严蔚敏吴伟民编著。注：本页为每次课教案首页石家庄学院教案纸（续页）教学内容备注与后记稀疏矩阵的存储如果矩阵中只有少量的非零值元，并且这些非零值元在矩阵中的分布没有一定规律，则称为随机稀疏矩阵，简称为稀疏矩阵。至于矩阵中究竟含多少个零值元才被称为是稀疏矩阵，目前还没有一个确切的定义，它只是一个凭人的直觉来了解的概念。假设在mn的矩阵中有t个非零值元，令，称§为矩阵的稀疏因子，则通常认定§≤0.05的矩阵为稀疏矩阵。如何存储稀疏矩阵中的非零值元？

由于压缩存储的基本宗旨是只存放矩阵中的非零值元，则在存储非零元的值的同时必须记下它在矩阵中的位置(i,j)，反之，一个三元组(i,j,aij)唯一确定了矩阵A中的一个非零值元,由此可以"其数据元素为上述三元组的线性表"表示稀疏矩阵，并且非零元在三元组线性表中是"以行为主"有序排列的。相应于线性表的两种存储结构可得到稀疏矩阵的不同压缩存储方法。例如表示矩阵

的三元组线性表为：

((1,3,9),(1,5,-7),(3,4,8),(4,1,5),(4,6,2),(5,2,16))元组顺序表

稀疏矩阵的三元组顺序表的结构定义

constMAXTERMS=12500;//假设非零元个数的最大值为12500

typedefstruct{

inti,j;//该非零元的行号和列号

ElemTypee;//该非零元的值

}Triple;//三元组

typedefstruct{

Tripledata[MAXTERMS+1];//非零元三元组表，data[0]未用

introws,cols,terms;//矩阵的行数、列数和非零元的个数

}TSMatrix;//三元组顺序表算法实现，将稀疏矩阵转换为三元组#include<stdio.h>#include<malloc.h>voidmain(){//定义一个二维数组 inta[10][10]; inti,j; intk=0; //构造一个测试二维数组 for(i=0;i<10;i++) for(j=i;j<10;j++){ a[j][i]=a[i][j]=k++; if(j==i){ a[i][j]=0; } }//打印二维数组 printf("原矩阵\n"); for(i=0;i<10;i++){for(j=0;j<10;j++) printf("%3d",a[i][j]); printf("\n"); } printf("\n");//特殊矩阵为一维数组 intn=10; n=n*(n+1)/2;//首尾相加乘以个数除以2 int*b=(int*)malloc(n*sizeof(int)); for(i=0;i<10;i++) for(j=0;j<10;j++) if(j>=i) b[(j+1)*j/2+i]=a[i][j]; printf("转化后矩阵(二维打印)\n"); k=1; for(i=0;i<n;i++){ printf("%3d",b[i]); if(i+1==k*(k+1)/2){//也可根据0换行 k++; printf("\n"); }} printf("\n"); printf("转化后矩阵(一维打印)\n"); for(i=0;i<n;i++) printf("%3d",b[i]); printf("\n\n"); //根据一维矩阵转换为二维矩阵 printf("数据还原\n"); inttemp[10][10]; for(i=0;i<10;i++) for(j=0;j<10;j++) if(i<=j) temp[i][j]=b[j*(j+1)/2+i]; else temp[i][j]=b[i*(i+1)/2+j]; //打印转化后的矩阵 for(i=0;i<10;i++){ for(j=0;j<10;j++) printf("%3d",temp[i][j]);printf("\n"); }}教学总结：本章节主要介绍了稀疏矩阵的特点以及两种压缩存储方式。5.3广义表一、教学目标理解广义表的定义、特点及基本术语；掌握广义表的链式存储结构（头尾表示法、孩子兄弟表示法）的C语言实现；掌握广义表的基本运算（求长度、求深度、遍历、查找元素）的算法设计与代码实现；培养基于链式结构的编程思维和问题解决能力。二、教学重难点重点：广义表的存储结构、求深度/长度的算法、遍历算法；难点：广义表深度的递归求解、复杂广义表的遍历逻辑。三、教学过程（一）广义表的定义1.核心概念广义表（GeneralizedList）简称GList，是线性表的推广，定义为：广义表是n（n≥0）个元素的有限序列，记作LS=(a1,a2,...,an)。其中：ai可以是单个元素（称为原子，Atom），也可以是另一个广义表（称为子表，SubList）；n为广义表的长度，n=0时称为空表；广义表的深度指表中括号的最大嵌套层数（原子深度为0，空表深度为1）。2.示例解析（帮助理解）广义表表示 说明A=()空表，长度0，深度1B=(a,b)原子表，长度2，深度1（元素均为原子）C=(a,(b,c))混合表，长度2（a和子表(b,c)），深度2D=(A,B,C)子表嵌套，长度3（A/B/C均为广义表），深度3（C的深度2+外层1）E=(a,E)递归表（循环表），长度2，深度∞（嵌套无终止）3.核心特点层次性：元素可以是原子或子表，具有嵌套结构；共享性：多个广义表可共享同一个子表（如D共享A/B/C）；递归性：广义表可以包含自身（如E）。（二）广义表的存储结构（C语言实现）广义表的元素类型不统一（原子/子表），因此无法用顺序存储，只能用链式存储。常用两种方式：1.头尾表示法（重点）（1）存储思想广义表可拆分为“表头（Head）”和“表尾（Tail）”：表头：广义表的第一个元素（可以是原子或子表）；表尾：除去表头后剩余元素构成的广义表（一定是子表）。例如：C=(a,(b,c))，表头是a（原子），表尾是((b,c))（子表）。（2）节点结构设计需要两种节点：原子节点、表节点：c运行#include<stdio.h>#include<stdlib.h>#include<string.h>//节点类型枚举typedefenum{ATOM,//原子节点LIST//表节点}NodeType;//广义表节点结构体（头尾表示法）typedefstructGListNode{NodeTypetype;//节点类型：原子/表union{//共用体：原子值或表的头尾指针charatom;//原子节点：存储字符型原子（如'a'、'b'）struct{//表节点：存储表头、表尾指针structGListNode*head;structGListNode*tail;}list;}data;}GListNode,*GList;（3）广义表的创建（字符串解析）输入格式示例：(a,(b,c))，递归创建广义表：c运行//辅助函数：跳过字符串中的空格voidskipSpace(char**str){while(**str=='')(*str)++;}//递归创建广义表（输入字符串如："(a,(b,c))"）intCreateGList(GList*L,char**str){skipSpace(str);if(**str==')'){//空表（如遇到"()"中的')'）(*str)++;*L=NULL;return1;}if(**str=='('){//表节点开始(*str)++;*L=(GListNode*)malloc(sizeof(GListNode));if(!*L)return0;//内存分配失败(*L)->type=LIST;//递归创建表头if(!CreateGList(&((*L)->data.list.head),str))return0;skipSpace(str);if(**str==','){//有表尾，递归创建(*str)++;if(!CreateGList(&((*L)->data.list.tail),str))return0;}else{//无表尾，表尾置空(*L)->data.list.tail=NULL;}skipSpace(str);if(**str==')')(*str)++;//跳过表结束符}elseif((**str>='a'&&**str<='z')||(**str>='A'&&**str<='Z')){//原子节点*L=(GListNode*)malloc(sizeof(GListNode));if(!*L)return0;(*L)->type=ATOM;(*L)->data.atom=**str;(*str)++;}else{return0;//非法字符}return1;}//封装创建函数（对外接口）GListCreateGListFromStr(char*str){GListL=NULL;char*p=str;if(*p=='('){CreateGList(&L,&p);}returnL;}2.孩子兄弟表示法（拓展）（1）存储思想将广义表视为树形结构：每个节点有两个指针：child（指向第一个子元素）、next（指向同一层的下一个兄弟元素）；原子节点无child指针。（2）节点结构设计c运行//广义表节点结构体（孩子兄弟表示法）typedefstructCSNode{NodeTypetype;//节点类型：原子/表union{charatom;structCSNode*child;//表节点的第一个子元素}data;structCSNode*next;//指向兄弟节点}CSNode,*CSGList;（注：创建/运算逻辑类似头尾表示法，核心是“孩子+兄弟”的遍历思路，本节重点讲头尾表示法）（三）广义表的基本运算（C语言实现）基于“头尾表示法”实现核心运算，所有运算均基于递归（适配广义表的嵌套特性）。1.求广义表的长度定义：广义表第一层元素的个数（空表长度为0）；思路：表尾是“除去表头后的剩余元素”，因此长度=1+表尾的长度（递归）。c运行//求广义表的长度（第一层元素个数）intGListLength(GListL){if(L==NULL)return0;//空表长度0if(L->type==ATOM)return1;//单个原子（特殊情况：如广义表是单个原子a）//表节点：长度=1+表尾的长度return1+GListLength(L->data.list.tail);}2.求广义表的深度定义：括号的最大嵌套层数（空表深度1，原子深度0）；思路：深度=max(表头深度，表尾深度)+1（表节点）；原子深度为0。c运行//求广义表的深度（括号最大嵌套层数）intGListDepth(GListL){if(L==NULL)return1;//空表深度1if(L->type==ATOM)return0;//原子深度0//表节点：递归求表头、表尾的深度intdepth_head=GListDepth(L->data.list.head);intdepth_tail=GListDepth(L->data.list.tail);//深度=表头/表尾深度的最大值+1return(depth_head>depth_tail?depth_head:depth_tail)+1;}3.遍历广义表（输出）思路：递归遍历，原子直接输出，表节点输出括号+递归遍历表头/表尾。c运行//遍历并输出广义表voidTraverseGList(GListL){if(L==NULL){//空表printf("()");return;}if(L->type==ATOM){//原子节点printf("%c",L->data.atom);return;}//表节点：输出左括号+遍历表头+遍历表尾printf("(");TraverseGList(L->data.list.head);//遍历表头GListNode*p=L->data.list.tail;while(p!=NULL){//遍历表尾（多个元素用逗号分隔）printf(",");TraverseGList(p->data.list.head);//表尾的表头是下一个元素p=p->data.list.tail;}printf(")");}4.查找元素是否存在思路：递归查找表头，若不存在则查找表尾，原子节点直接比较值。c运行//查找广义表中是否存在指定原子元素intFindGListElem(GListL,charelem){if(L==NULL)return0;//空表，不存在if(L->type==ATOM){//原子节点，直接比较return(L->data.atom==elem)?1:0;}//表节点：递归查找表头+表尾returnFindGListElem(L->data.list.head,elem)||FindGListElem(L->