第2章基本数据结构及运算 数据处理:数据如何组织,以便提高处理速度,节省存贮空间一一关键问题 研究内容 1.逻辑结构:数据元素间的关系。 2.物理结构/存贮结构:各数据元素在计算机中的存贮关系 3.运算:对各种数据结构的操作 21数据结构的基本概念 数据处理:对数据元素进行运算:包括插入、删除、查找、更新等,也包括分析。 建立数学模型固然好,但有时难以表示成模型,感兴趣的是数据元素之间的关系。为了提高处理效率,应 如何组织他们,即如何表示数据元素 书上通过实例说明数据采用不同表示方法对处理效率的影响 数据结构是一门研究数据如何组织、存储和运篡的一般方法的学科。 212什么是数据结构 数据:描述客观事务的数字符以及所有能输入计算机中并被程序识别和处理的符号的集合,计算机处理的 对象。 ∫数值性数据:工程,科学计算和商业 非数值性数据:字符串,文字,图形和语音 数据元素 Data elemen):数据的基本单位 个数据元素可由若干数据项( ata Item)组成 数据项:数据的最小单位。 书名作者名分类出版年月 数据元素亦称点或己录 数据项亦称字度或越 数据对象 Data object):是性质相同的数据元素的集合,是数据的一个子集 数据结构 Data structure):是相互之间存在一种或多种特定关系的数据元素的集合 1.数据的逻辑结构 数据结构可描述为 Group=(D,R) D:有限个数据元素的集合:R有限个结点间关系的集合 例题见书 图形表示:见书
1 第 2 章基本数据结构及运算 数据处理：数据如何组织，以便提高处理速度，节省存贮空间——关键问题。 研究内容： 1． 逻辑结构：数据元素间的关系。 2． 物理结构/存贮结构：各数据元素在计算机中的存贮关系。 3． 运算：对各种数据结构的操作。 2.1 数据结构的基本概念 数据处理：对数据元素进行运算：包括插入、删除、查找、更新等，也包括分析。 建立数学模型固然好，但有时难以表示成模型，感兴趣的是数据元素之间的关系。为了提高处理效率，应 如何组织他们，即如何表示数据元素。 书上通过实例说明数据采用不同表示方法对处理效率的影响。 数据结构是一门研究数据如何组织、存储和运算的一般方法的学科。 2.1.2 什么是数据结构 数据：描述客观事务的数字符以及所有能输入计算机中并被程序识别和处理的符号的集合，计算机处理的 对象。 非数值性数据： 字符串，文字，图形和语音 数值性数据：工程，科学计算和商业 数据元素(Data Element) ：数据的基本单位。 一个数据元素可由若干数据项(Data Item)组成。 数据项：数据的最小单位。 数据元素亦称结点或记录 数据项亦称字段或域 数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。 数据结构(Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。 1． 数据的逻辑结构 数据结构可描述为 Group=（D，R） D：有限个数据元素的集合；R 有限个结点间关系的集合 例题见书 图形表示：见书
2.数据的存贮结构 14线性数据结构与非线性数据结构 线性表 A.线性结构了栈 队列 数据的逻辑结构 数组 据 B.非线性结构树形结构 构的三个方面 图形结构 A顺序存储 2、数据的存储结构B链式存储 C索引 3、数据的运算:检索、排序、插入、删除、修改等 A.线性结构(一对一) 特性:1有且只有一个根结点 2每个结点最多一个前件,最多一个后件。(第一个数据元素无前件,最后一个无后件,其它有 且仅有一个前驱和一个后继。 例:(A,B,C 例 学生成缋表 成缚 9861109 卓 100 9861107 如忠 95 Q61103 B.非线性结构树形结构(一对多 学校 系别 计算机系 数学系 物理系 专业计算机应用计算机软件数学 理论物理应用物理 班级91…95991…9959 995991 学生张力……李场…… 赵壮………王芳
2 2． 数据的存贮结构 2.1.4 线性数据结构与非线性数据结构 A. 线性结构（一对一） 特性：1.有且只有一个根结点 2.每个结点最多一个前件，最多一个后件。（第一个数据元素无前件，最后一个无后件，其它 有 且仅有一个前驱和一个后继。） 例：（A , B , C , ·······，X ,Y , Z） 例： 学 生 成 绩 表 B．非线性结构:树形结构（一对多） 1．数据的逻辑结构 2、数据的存储结构 3、数据的运算：检索、排序、插入、删除、修改等。 A．线性结构 B．非线性结构 A 顺序存储 B 链式存储 C 索引 线性表 栈 队列 树形结构 图形结构 数 据 结 构 的 三 个 方 面 数组 9861103 胡孝臣 86 9861107 刘忠赏 95 9861109 张卓 100 学号 姓名 成绩
B.非线性结构图形结构(多对多) D={1,2,3,4} R={(1,2),(1,3),(1,4),(2,3) (3,4),(2,4)} 数据的存储结构 A.顺序存储 顺序存储结构常用于线性数据结构,将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 顺序存储结构的三个弱点: 1.插入或删除操作时,需移动大量元素 2.长度变化较大时,需按最大空间分配 3表的容量难以扩充 B链式存储 每个节点都由两部分组成:数据域和指针域 数据域存放元素本身的数据,指针域存放指针。 数据元素之间逻辑上的联系由指针来体现 链式存储结构特点 1比顺序存储结构的存储密度小(每个节点都由数据域和指针域组成)。 2逻辑上相邻的节点物理上不必相邻 3插入、删除灵活(不必移动节点,只要改变节点中的指针) 22线性表及其存贮结构 线性表逻辑结构 n个数据元素的有限序列(al,a2,a3,an) n为线性表的长度(n≥0),n=0的表称为空表 特性: 数据元素呈线性关系 所有数据元素ai在同一个线性表中须是相同的数据类型 ·线性表的基本运算: (1)插入:在两个确定的元素之间插入一个新的元素 (2)删除:删除线性表中某个元素; (3)修改:按某种要求查找元素,需要时,还可找到元素进行值的更新 l顺序存储结构及插入删除运算 线性表的顺序存储结构,可用C语言中的一维数组来描述
3 B．非线性结构:图形结构（多对多） D={ 1 , 2 , 3 , 4} R={(1,2) , (1,3) , (1,4) , (2,3) (3,4) , (2,4) } 2、数据的存储结构 A. 顺序存储 顺序存储结构常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。 顺序存储结构的三个弱点： 1.插入或删除操作时，需移动大量元素。 2.长度变化较大时，需按最大空间分配。 3.表的容量难以扩充。 B.链式存储 每个节点都由两部分组成：数据域和指针域。 数据域存放元素本身的数据，指针域存放指针。 数据元素之间逻辑上的联系由指针来体现。 链式存储结构特点： 1.比顺序存储结构的存储密度小 (每个节点都由数据域和指针域组成)。 2.逻辑上相邻的节点物理上不必相邻。 3.插入、删除灵活(不必移动节点，只要改变节点中的指针)。 2.2 线性表及其存贮结构 • 线性表逻辑结构 – n 个数据元素的有限序列:(a1, a2 ,a3,…an) n 为线性表的长度(n≥0)，n=0 的表称为空表 • 特性： – 数据元素呈线性关系. – 所有数据元素 ai 在同一个线性表中须是相同的数据类型 • 线性表的基本运算： (1)插入：在两个确定的元素之间插入一个新的元素； (2)删除：删除线性表中某个元素； (3)修改：按某种要求查找元素，需要时，还可找到元素进行值的更新； 1.顺序存储结构及插入删除运算 .线性表的顺序存储结构 ,可用 C 语言中的一维数组来描述. 1 4 2 3
# define LiStInitsize100线性表存储空间的初始分配量 type Elem Type *elem;∥数组指钍表示存储空间基址 当前长度 int listsize∥当前分配的存储容量(以 sizeof( Elem Type)为单位) Status ListInsert sq (Sqlist &v, int i, Elem Typex) ∥在线性表V中第i个元素之前插入x,i的合法值为1≤isⅤ Length+1 if(i<1‖i>Ⅴ length+1) return ERROR,/i值不合法 if( V length>Ⅴ listsize) return OVERFLoW,∥无存储空间 q=&Ⅴelem[-1l,/下行注:插入位置后的元素依次右移 for(p=&Velem[V length-1]; p>=q:--p *q=x,∥插入x ++ V length;,∥表长加1 return oK Status List Delete sq Elem Type x)( if (i<l l i>V length return ERROR: P=&velem[i-1 P q=Ⅴelem+Ⅴ length-1; for(++pp<=q;++p)*(p-1)=*p 2链式存储结构及插入删除运算 特点:用一组任意的存储单元可以是连续的也可以是不连续的)存放线性表的数据元素。 存储地址 数据域 指针域 头指针H WANG NLL ZHAO ZHENG ZHOU 上图为(ZHAO,QIAN,SUN,L,ZHOU,wU, ZHENG,wNG)
4 #define LISTINITSIZE 100 //线性表存储空间的初始分配量 typedef struct{ ElemType *elem；//数组指针表示存储空间基址 int length； //当前长度 int listsize //当前分配的存储容量（以 sizeof（ElemType）为单位） }Sqlist Status ListInsert_sq（Sqlist V，int i , ElemType x） { //在线性表 V 中第 i 个元素之前插入 x， i 的合法值为 1 iV.Length+1 if（i<1‖i>V.length+1）return ERROR; //i 值不合法 if(V.length>V.listsize) return OVERFLOW; //无存储空间 q=V.elem[i-1]; //下行注：插入位置后的元素依次右移 for(p=V.elem[V.length-1]; p>=q; − −p) (p+1)= p; q=x; // 插入 x ++V.length; //表长加 1 return OK; } Status ListDelete_sq（Sqlist V，int i , ElemType x）{ if（i<1‖i>V.length）return ERROR; P=V.elem[i-1]; x =P; q= V.elem+ V.length−1 ; for(++p;p<=q;++p) *(p−1)=*p − −V.length; return OK; } 2.链式存储结构及插入删除运算 特点：用一组任意的存储单元(可以是连续的,也可以是不连续的)存放线性表的数据元素。 上图为(ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG)
线性表的线性链表存储结构,存储从头指针开始进行。 ZHAO (1)线性表的单链式存储结构 线性表的链式存储结构可用C语言中的“结构指针来描述 Typedef Elem Type data struct Lnode *next 3 Lnode, "linklist 单链表的插入运算 ListInsert L(LinkList &L, int i, Elem Type x)t p=L;j=0; while( p&&j<i-1) (p=p->next; ++j; if(!p I i>i-1)return ERRO s(struct LNode ")malloc(sizeof(struct LNode)) s->data=x; S->next=p->next; p->nexts return OK: 单链表的删除运算 List Delete L(LinkList &L, int i, Elem Type x)i p=L;j=0; while( p->next & j<i-1) i p=p->next; ++j; if(!(p->next) I ii-1)return ERROR gp->next; p-nextq->next; free(q); return OK: (2)循环链表P64
5 线性表的线性链表存储结构，存储从头指针开始进行。 （1）线性表的单链式存储结构 线性表的链式存储结构可用 C 语言中的“结构指针”来描述 Typedef struct Lnode { Elem Type data； struct Lnode *next； } Lnode，*linklist； 单链表的插入运算 ListInsert_L(LinkList &L,int i, ElemType x){ p=L; j=0; while( p&&j<i-1) {p=p->next; ++j;} if( ! p j>i-1) return ERROR; s=(struct LNode *)malloc(sizeof(struct LNode)); s->data=x; s->next=p->next; p->next=s; return OK; } 单链表的删除运算 ListDelete_L(LinkList &L，int i, ElemType x){ p=L; j=0; while( p->next && j<i-1) { p=p->next; ++j; } if( ! (p->next) j>i-1) return ERROR; q=p->next ; p->next=q->next; free(q); return OK; } （2） 循环链表 P64