C语言程序设计 清华大学郑莉安颖莲 第十一饼数据结构基础 ①《计算机程序程序设计基础》第10章 ②《数据结构》(严蔚敏等编著)第1、2章
C语言程序设计 清华大学 郑莉 安颖莲 1 第十一讲 数据结构基础 （一） ①《计算机程序程序设计基础》第10章 ②《数据结构》（严蔚敏 等 编著）第1、2章
C语言程序设计 清华大学郑莉安颖莲 本讲主要内容 基本概念和术语 犷法和算法分析 ·线性表的类型定义 线性表的顺序表示和奥现 线性表的链式表尔和奥现 单链表算法举例
C语言程序设计 清华大学 郑莉 安颖莲 Page 2 本讲主要内容 • 基本概念和术语 • 算法和算法分析 • 线性表的类型定义 • 线性表的顺序表示和实现 • 线性表的链式表示和实现 • 单链表算法举例
C语言程序设计 清华大学郑莉安颖莲 “数据结构”的基本概念 “数据结构”在计算机科学中的地位 基本概念和术语 数据 对客观事物的符号表示,在计算机科学中是指所有能输入到计算机中 并被计算机程序处理的符号的总称。 数据元素 数据的基本单位,一个数据元素可由若干数据项组成,数据项是 数据的不可分割的最小单位。 数据对象 性质相同的数据元素的集合,是数据的一个子集。 数据结构 是相互之间存在一种或多种特定关系的数据元素的集合 四类基本结构:集合、线性结构、树形结构、图状结构或网状结构。 数据类型 是一个值的集合和定义在这个值集上的一组操作的总称。 高级语言中的数据类型可分为两类:原子类型、结构类型。Page3
C语言程序设计 清华大学 郑莉 安颖莲 Page 3 “数据结构”的基本概念 • “数据结构”在计算机科学中的地位 • 基本概念和术语 - 数据 • 对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中 并被计算机程序处理的符号的总称。 - 数据元素 • 数据的基本单位，一个数据元素可由若干数据项组成，数据项是 数据的不可分割的最小单位。 - 数据对象 • 性质相同的数据元素的集合，是数据的一个子集。 - 数据结构 • 是相互之间存在一种或多种特定关系的数据元素的集合。 • 四类基本结构：集合、线性结构、树形结构、图状结构或网状结构。 - 数据类型 • 是一个值的集合和定义在这个值集上的一组操作的总称。 • 高级语言中的数据类型可分为两类：原子类型、结构类型
C语言程序设计 清华大学郑莉安颖莲 算法和算法分析 算法 对特定问题求解步骤的一种描述,它是指令的有限 序列,其中每一条指令表示一个或多个操作 ·算法的五个重要特征 有穷性、确定性、可行性、零个或多个输入、一个 或多个输出。 算法的设计要求 正确性、可读性、健壮性、效率与低存储量需求。 Page 4
C语言程序设计 清华大学 郑莉 安颖莲 Page 4 算法和算法分析 • 算法 - 对特定问题求解步骤的一种描述，它是指令的有限 序列，其中每一条指令表示一个或多个操作。 • 算法的五个重要特征 - 有穷性、确定性、可行性、零个或多个输入、一个 或多个输出。 • 算法的设计要求 - 正确性、可读性、健壮性、效率与低存储量需求
C语言程序设计 清华大学郑莉安颖莲 线性表的定义和基本操作 线性表是n个数据元素的有限序列。 线性表的基本操作 构造一个空线性表 销毁一个线性表 将一个线性表重置为空表 判断线性表是否为空 求线性表的元素个数 求线性表的第个元素的值 在线性表中查找第一个满足指定条件的元素 求指定元素的前驱 求指定元素的后继 在线性表的第个元素之前插入一个新元素 删除线性表的第i个元素 遍历线性表
C语言程序设计 清华大学 郑莉 安颖莲 Page 5 线性表的定义和基本操作 • 线性表是 n 个数据元素的有限序列。 • 线性表的基本操作 - 构造一个空线性表 - 销毁一个线性表 - 将一个线性表重置为空表 - 判断线性表是否为空 - 求线性表的元素个数 - 求线性表的第i个元素的值 - 在线性表中查找第一个满足指定条件的元素 - 求指定元素的前驱 - 求指定元素的后继 - 在线性表的第i个元素之前插入一个新元素 - 删除线性表的第i个元素 - 遍历线性表
C语言程序设计 清华大学郑莉安颖莲 线性衰的顺序表示和实现 用一组地址连续的存储单元依次存储线性表的 数据元素。通常用一维数组来描述。 特点: 逻辑上相邻的两个元素,在物理上也具有相邻的存 储位置 可以随机存取任何一个元素。 插入和删除时需要移动大量元素。 空间不能充分得到利用 表的容量难以扩充
C语言程序设计 清华大学 郑莉 安颖莲 6 线性表的顺序表示和实现 • 用一组地址连续的存储单元依次存储线性表的 数据元素。通常用一维数组来描述。 • 特点： - 逻辑上相邻的两个元素，在物理上也具有相邻的存 储位置。 - 可以随机存取任何一个元素。 - 插入和删除时需要移动大量元素。 - 空间不能充分得到利用。 - 表的容量难以扩充
C语言程序设计 学莉安颖莲 线性表的链式表示和现 线性链表 用一组任意的存储单元存储线性表的数据元素。这 些存储单元可以连续也可不连续。 元素a的存储映象:结点 包括:自身信息(数据域),后继元素的位置(指针域)。 typedef struct LNode i Elem Type data data next struct LNode next } LNode,米 inklist; 结点的存储结构 结点数据的访问形式 设指针p为某结点的起始地址 数据域:p->data指针域:p->next 特点: 插入、删除元素时不必大量移动数据 不能随机存取其中记录
C语言程序设计 清华大学 郑莉 安颖莲 7 线性表的链式表示和实现 —线性链表 • 用一组任意的存储单元存储线性表的数据元素。这 些存储单元可以连续也可不连续。 • 元素ai的存储映象：结点 - 包括：自身信息（数据域），后继元素的位置（指针域）。 typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; • 结点数据的访问形式 - 设指针 p 为某结点的起始地址 数据域：p->data 指针域：p->next • 特点： - 插入、删除元素时不必大量移动数据 - 不能随机存取其中记录 data next 结点的存储结构
C语言程序设计 清华大学郑莉安颖莲 单链衰算法举例 建立链表 LinkList CreateList LinkList la, int n) 1a=(LinkList)malloc(sizeof (Lnode)) la->next=NULL for(i=n: i>0:-1 I p=( LinkList)malloc(sizeof (LNnde)) scanf (&p->data) p->next=la->next: la->next=p return (la)
C语言程序设计 清华大学 郑莉 安颖莲 8 单链表算法举例 ——建立链表 LinkList CreateList(LinkList la, int n) { la=(LinkList)malloc(sizeof(LNode)) la->next=NULL; for(i=n; i>0; --i) { p=(LinkList)malloc(sizeof(LNnde)); scanf(&p->data); p->next=la->next; la->next=p; } return (la); }
C语言程序设计 清华大学郑莉安颖莲 单链表犷法举例 一在第i个位量之前插入元素b int ListInsert (LinkList la, int i, ElemType b) p=1a;j=0; while(p&&jnext:++j if (!pl j>1-1) return(o) S=(LinkList) malloc (sizeof (Lnode)) s->data=b s->next=p->next p->next=s return(1)
C语言程序设计 清华大学 郑莉 安颖莲 9 单链表算法举例 —在第 i 个位置之前插入元素 b int ListInsert(LinkList la, int i,ElemType b) { p=la; j=0; while(p&&jnext; ++j;} if (!p||j>i-1) return(0); s=(LinkList) malloc (sizeof(Lnode)); s->data=b; s->next=p->next; p->next=s; return (1); }
C语言程序设计 清华大学郑莉安颖莲 单链表算法举例 删除第1个元素 int ListDelete ( LinkList la, int i) p=1a;j=0; while(p->next & jnext; ++j; if (!(p->next) j>1-1) return(o) g=p->next: p->next=g->next free(g) return (1)
C语言程序设计 清华大学 郑莉 安颖莲 10 单链表算法举例 ——删除第 i 个元素 int ListDelete (LinkList la, int i ) { p=la; j=0; while(p->next && jnext; ++j; } if (!(p->next)|| j>i-1 ) return(0); q=p->next; p->next=q->next; free(q); return(1); }