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