C语言程序设计 清华大学 郑莉 安颖莲
1
第十一讲 数据结构基础
（一）
①,计算机程序程序设计基础,第 10章
②,数据结构,（严蔚敏 等 编著）第 1,2章
C语言程序设计 清华大学 郑莉 安颖莲
2Page
本讲主要内容
基本概念和术语
算法和算法分析
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
单链表算法举例
C语言程序设计 清华大学 郑莉 安颖莲
3Page
“数据结构,的基本概念
,数据结构,在计算机科学中的地位
基本概念和术语
- 数据
对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
- 数据元素
数据的基本单位，一个数据元素可由若干 数据项 组成，数据项是数据的不可分割的最小单位。
- 数据对象
性质相同的数据元素的集合，是数据的一个子集。
- 数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。
四类基本结构,集合、线性结构、树形结构、图状结构或网状结构 。
- 数据类型
是一个值的集合和定义在这个值集上的一组操作的总称。
高级语言中的数据类型可分为两类,原子类型、结构类型 。
C语言程序设计 清华大学 郑莉 安颖莲
4Page
算法和算法分析
算法
- 对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
算法的五个重要特征
- 有穷性、确定性、可行性、零个或多个输入、一个或多个输出。
算法的设计要求
- 正确性、可读性、健壮性、效率与低存储量需求。
C语言程序设计 清华大学 郑莉 安颖莲
5Page
线性表的定义和基本操作
线性表是 n 个数据元素的有限序列。
线性表的基本操作
- 构造一个空线性表
- 销毁一个线性表
- 将一个线性表重置为空表
- 判断线性表是否为空
- 求线性表的元素个数
- 求线性表的第 i个元素的值
- 在线性表中查找第一个满足指定条件的元素
- 求指定元素的前驱
- 求指定元素的后继
- 在线性表的第 i个元素之前插入一个新元素
- 删除线性表的第 i个元素
- 遍历线性表
C语言程序设计 清华大学 郑莉 安颖莲
6
线性表的顺序表示和实现
用一组地址连续的存储单元依次存储线性表的数据元素。通常用一维数组来描述。
特点：
- 逻辑上相邻的两个元素，在物理上也具有相邻的存储位置。
- 可以随机存取任何一个元素。
- 插入和删除时需要移动大量元素。
- 空间不能充分得到利用。
- 表的容量难以扩充。
C语言程序设计 清华大学 郑莉 安颖莲
7
线性表的链式表示和实现
—线性链表
用一组任意的存储单元存储线性表的数据元素。这些存储单元可以连续也可不连续。
元素 ai的存储映象：结点
- 包括：自身信息（数据域），后继元素的位置（指针域）。
typedef struct LNode
{ ElemType data;
struct LNode *next;
}LNode,*LinkList;
结点数据的访问形式
- 设指针 p 为某结点的起始地址数据域,p->data 指针域,p->next
特点：
- 插入、删除元素时不必大量移动数据
- 不能随机存取其中记录
data next
结点的存储结构
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语言程序设计 清华大学 郑莉 安颖莲
9
单链表算法举例
—在第 i 个位置之前插入元素 b
int ListInsert(LinkList la,int i,ElemType b)
{
p=la; j=0;
while(p&&j<i-1)
{ p=p->next; ++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语言程序设计 清华大学 郑莉 安颖莲
10
单链表算法举例
——删除第 i 个元素
int ListDelete (LinkList la,int i )
{
p=la; j=0;
while(p->next && j<i-1)
{ p=p->next; ++j; }
if (!(p->next)|| j>i-1 ) return(0);
q=p->next; p->next=q->next;
free(q);
return(1);
}
C语言程序设计 清华大学 郑莉 安颖莲
11
单链表算法举例
—合并两个有序单链表
LinkList MergeList(LinkList la,LinkList lb)
{
ap=la->next; bp=lb->next;
lc=tp=la;
while ( ap && bp)
{ if (ap->data<=bp->data)
{tp->next=ap; tp=ap; ap=ap->next;}
else {tp->next=bp; tp=bp; bp=bp->next;}
}
tp->next=ap? ap:bp;
free(lb);
return(lc);
}
C语言程序设计 清华大学 郑莉 安颖莲
12
应用举例
· 题目：
- 有两个多项式存放在磁盘文件,padd.dat”中，存放形式为：某项的系数、指数,..,以系数 0或文件结束为多项式结束。求这两个多项式的和，要求升幂排列。
· 分析：
- 数据结构：
用单链表存放多项式，每个结点包括：某一项的系数、
指数、下一结点的地址。
- 算法要点：
从 padd.dat文件中读取数据，建立两个多项式链表，定义两多项式相加函数、输出多项式函数等。
· 程序：
11-1.c
C语言程序设计 清华大学 郑莉 安颖莲
13
应用举例
The first polynomial is:+2X^0 +3X^2 +4X^4
The second polynomial is:+1X^0 +1X^1 -4X^5
The sum of polynomials is:
+3X^0 +1X^1 +3X^2 +4X^4 -4X^5
假设 padd.dat文件中存放两个多项式,内容为：
2 0 3 2 4 4 0 0
1 0 1 1 -4 5 0 0
运行结果：
C语言程序设计 清华大学 郑莉 安颖莲
14
作 业
上机：,C程序设计,
P254 10.8,10.10,10.11,10.12
选做,10.9
1
第十一讲 数据结构基础
（一）
①,计算机程序程序设计基础,第 10章
②,数据结构,（严蔚敏 等 编著）第 1,2章
C语言程序设计 清华大学 郑莉 安颖莲
2Page
本讲主要内容
基本概念和术语
算法和算法分析
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
单链表算法举例
C语言程序设计 清华大学 郑莉 安颖莲
3Page
“数据结构,的基本概念
,数据结构,在计算机科学中的地位
基本概念和术语
- 数据
对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
- 数据元素
数据的基本单位，一个数据元素可由若干 数据项 组成，数据项是数据的不可分割的最小单位。
- 数据对象
性质相同的数据元素的集合，是数据的一个子集。
- 数据结构
是相互之间存在一种或多种特定关系的数据元素的集合。
四类基本结构,集合、线性结构、树形结构、图状结构或网状结构 。
- 数据类型
是一个值的集合和定义在这个值集上的一组操作的总称。
高级语言中的数据类型可分为两类,原子类型、结构类型 。
C语言程序设计 清华大学 郑莉 安颖莲
4Page
算法和算法分析
算法
- 对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。
算法的五个重要特征
- 有穷性、确定性、可行性、零个或多个输入、一个或多个输出。
算法的设计要求
- 正确性、可读性、健壮性、效率与低存储量需求。
C语言程序设计 清华大学 郑莉 安颖莲
5Page
线性表的定义和基本操作
线性表是 n 个数据元素的有限序列。
线性表的基本操作
- 构造一个空线性表
- 销毁一个线性表
- 将一个线性表重置为空表
- 判断线性表是否为空
- 求线性表的元素个数
- 求线性表的第 i个元素的值
- 在线性表中查找第一个满足指定条件的元素
- 求指定元素的前驱
- 求指定元素的后继
- 在线性表的第 i个元素之前插入一个新元素
- 删除线性表的第 i个元素
- 遍历线性表
C语言程序设计 清华大学 郑莉 安颖莲
6
线性表的顺序表示和实现
用一组地址连续的存储单元依次存储线性表的数据元素。通常用一维数组来描述。
特点：
- 逻辑上相邻的两个元素，在物理上也具有相邻的存储位置。
- 可以随机存取任何一个元素。
- 插入和删除时需要移动大量元素。
- 空间不能充分得到利用。
- 表的容量难以扩充。
C语言程序设计 清华大学 郑莉 安颖莲
7
线性表的链式表示和实现
—线性链表
用一组任意的存储单元存储线性表的数据元素。这些存储单元可以连续也可不连续。
元素 ai的存储映象：结点
- 包括：自身信息（数据域），后继元素的位置（指针域）。
typedef struct LNode
{ ElemType data;
struct LNode *next;
}LNode,*LinkList;
结点数据的访问形式
- 设指针 p 为某结点的起始地址数据域,p->data 指针域,p->next
特点：
- 插入、删除元素时不必大量移动数据
- 不能随机存取其中记录
data next
结点的存储结构
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语言程序设计 清华大学 郑莉 安颖莲
9
单链表算法举例
—在第 i 个位置之前插入元素 b
int ListInsert(LinkList la,int i,ElemType b)
{
p=la; j=0;
while(p&&j<i-1)
{ p=p->next; ++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语言程序设计 清华大学 郑莉 安颖莲
10
单链表算法举例
——删除第 i 个元素
int ListDelete (LinkList la,int i )
{
p=la; j=0;
while(p->next && j<i-1)
{ p=p->next; ++j; }
if (!(p->next)|| j>i-1 ) return(0);
q=p->next; p->next=q->next;
free(q);
return(1);
}
C语言程序设计 清华大学 郑莉 安颖莲
11
单链表算法举例
—合并两个有序单链表
LinkList MergeList(LinkList la,LinkList lb)
{
ap=la->next; bp=lb->next;
lc=tp=la;
while ( ap && bp)
{ if (ap->data<=bp->data)
{tp->next=ap; tp=ap; ap=ap->next;}
else {tp->next=bp; tp=bp; bp=bp->next;}
}
tp->next=ap? ap:bp;
free(lb);
return(lc);
}
C语言程序设计 清华大学 郑莉 安颖莲
12
应用举例
· 题目：
- 有两个多项式存放在磁盘文件,padd.dat”中，存放形式为：某项的系数、指数,..,以系数 0或文件结束为多项式结束。求这两个多项式的和，要求升幂排列。
· 分析：
- 数据结构：
用单链表存放多项式，每个结点包括：某一项的系数、
指数、下一结点的地址。
- 算法要点：
从 padd.dat文件中读取数据，建立两个多项式链表，定义两多项式相加函数、输出多项式函数等。
· 程序：
11-1.c
C语言程序设计 清华大学 郑莉 安颖莲
13
应用举例
The first polynomial is:+2X^0 +3X^2 +4X^4
The second polynomial is:+1X^0 +1X^1 -4X^5
The sum of polynomials is:
+3X^0 +1X^1 +3X^2 +4X^4 -4X^5
假设 padd.dat文件中存放两个多项式,内容为：
2 0 3 2 4 4 0 0
1 0 1 1 -4 5 0 0
运行结果：
C语言程序设计 清华大学 郑莉 安颖莲
14
作 业
上机：,C程序设计,
P254 10.8,10.10,10.11,10.12
选做,10.9
