第三章 基本数据结构及运算
3.1 概述
3.2 线性表
3.3 栈
3.4 队列
3.5 数组
3.6 树与二叉树
3.7 图第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
能输入到计算机中并能被计算机程序处理的符号的集合。
整数 (1,2)、实数 (1.1,1.2)
字符串 (Beijing)、
图形、声音。
第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
计算机管理图书问题在图书馆里有各种卡片：有按书名编排的、
有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
最简单的办法之一是建立一张表，
每一本书的信息在表中占一行，如第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
如何将 0,1,2,3,4,5,6,7,8,9这 10个数存放在计算机中能最快地达到你所需要的目的？
目的不同,最佳 的存储方方法就不同 。
从大到小排列,9,8,7,6,5,4,3,2,1,0
输出偶数,0,2,4,6,8,1,3,5,7,9
数据元素在计算机中的表示第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
对数据结构中的节点进行操作处理
(插入、删除、修改、查找、排序 )
数据,计算机处理的对象数据元素 (Data Element),数据的基本单位一个数据元素可由若干 数据项 (Data Item)组成。
数据项,数据的最小单位。
数据对象 (Data Object)：是性质相同的数据元素的集合。是数据的一个子集。
数据结构 (Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
数据元素亦称 结点 或 记录数据项亦称 字段 或 域数据结构 可描述为 Group=（ D,R）
有限个 数据元素 的集合有限个结点间 关系 的集合数据元素间的关系,前后件关系
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A,线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队列树形结构图形结构数据结构的三个方面数据结构可描述为 Group=（ D,R）
数组
A,线性结构 （一对一）
特性,1.有且只有一个根结点
2.每个结点最多一个 前件,最多一个 后件 。
（第一个数据元素无前件，最后一个无后件，其它有且仅有一个 前驱 和一个 后继 。）
例,（ A,B,C,·······,X,Y,Z）
例,学 生 成 绩 表
86胡孝臣9861103
95刘忠赏9861107
100张卓9861109
成绩姓名学号
1．数据的逻辑结构
DS1=（ D1,R1） 集合表示法
D1={k1,k2,k3,k4}
R1={（ k1,k2），（ k2,k3），（ k3,k4） }
DS2=(D2,R2)
D2={k1,k2,k3}
R2={(k1,k2),(k1,k3)}
k1 k2 k3 k4
k1
k2
k3
例：
例：
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构可描述为 Group=（ D,R）
数组
B．非线性结构,树形结构 （一对多）
全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构识别,体,字的过程丿 乙 亻 刂借 何体 休体 休判断偏旁部首四角号码匹配局部匹配按分支和层次组织的数据，称为：
,树形结构,
A
B C
D
E F G H
树形结构 —— 结点间具有分层次的连接关系
H
B C D
E F G
A
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组
1 4
2 3
D={ 1,2,3,4}
R={(1,2),(1,3),(1,4),(2,3)
(3,4),(2,4) }
2
1
3
D={ 1,2,3 }
R={ (1,2),(2,3),(3,2),(1,3) }
B．非线性结构,图形结构 （多对多）
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址存储内容
Loc(a)=Lo+（ i-1)*m
A,顺序存储每个元素所占用的存储单元个数
2、数据的存储结构元素 n
……..
元素 i
……..
元素 2
元素 1
存储内容顺序存储结构 常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的三个 弱点,
1.插入或删除操作时，需移动大量元素。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h B.链式存储每个节点都由两部分组成,数据域 和 指针域 。
数据域 存放元素本身的数据，
指针域 存放指针。
数据元素之间逻辑上的联系由指针来体现 。
1536元素 21400元素 1 1346元素 3 ∧元素 4
head
1346元素 31536
……,……,.……,
1536元素 21400
……,……,.……,
∧元素 41346
1400元素 11345
指针存储内容存储地址链式存储
1345
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h 链式存储
1.比顺序存储结构的存储密度小
(每个节点都由数据域和指针愈组成 )。
2.逻辑上相邻的节点物理上不必相邻。
3.插入、删除灵活
(不必移动节点，只要改变节点中的指针 )。
链式存储结构特点：
链表的一个重要特点是 插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可
a b
H e a d
┄ a b
H e a d
┄
x
∧
插 入
a c
Head
┄b ∧
删 除
1．数据的逻辑结构
2、数据的存储结构
3,数据的运算,检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组例 管理信息系统中的查询问题各种计算机管理信息系统中，通常相关的信息 (记录 )组成一个表文件,表文件是一类很重要的数据结构文件中的记录可按顺序方式组织黄鹏 8211 编译原理刘东 8201 算法分析李季为 8211 编译原理李宾 8202 算法分析王华 8202 图形学杜可翔 8201 编译原理何平 8201 编译原理陈红英 8211 算法分析
姓名 班级 选修课 链链头
┊
(b)(a)
黄鹏 8211 编译原理刘东 8201 算法分析李季为 8211 编译原理李宾 8202 算法分析王华 8202 图形学杜可翔 8201 编译原理何平 8201 编译原理陈红英 8211 算法分析
姓名 班级 选修课 链链头
┊
(b)(a)
顺序文件 导出的链表为提高检索效率,可将所有选修,算法分析,课的同学记录串接到一起，这种串接称为,加链”
3.2.1.线性表的逻辑结构
3.2.2 线性表的存储结构及运算
3.2.3 线性表的应用
3.2.4 作业
3.2 线性表
3.2.1.线性表的逻辑结构
线性表逻辑结构
– n个数据元素的有限序列,(a1,a2,a3,… an)
n为线性表的长度 (n≥0),n=0的表称为 空表
特性：
– 数据元素呈线性关系,
– 所有数据元素 ai在同一个线性表中须是 相同的数据类型
例,学生表
86胡孝臣9861103
95刘忠赏9861107
100张卓9861109
成绩姓名学号
线性表的基本运算：
(1)插入,在两个确定的元素之间插入一个新的元素；
(2)删除,删除线性表中某个元素；
(3)修改,按某种要求查找线性表中的一个元素，
需要时，还可找到元素进行值的更新
3.2.2 线性表的存储结构
1.顺序存储结构及插入删除运算
2.链式存储结构 及插入删除运算
（ 1）单链表
（ 2）循环链表
（ 3）双向链表
elem length listsize
元素 1
元素 2
……,.
元素 i
……,.
0
1
i-1V.elem[i-1]
线性表的顺序存储结构,可用 C语言中的一维数组来描述,
#define LISTINITSIZE 100 //线性表存储空间的初始分配量
typedef struct{
ElemType *elem； //数组指针 表示存储空间基址
int length； //当前长度
int listsize //当前分配的存储容量 （ 以 sizeof（ ElemType） 为单位 ）
}Sqlist
C语言的库函数,
测算 ElemType节点需占用的字节数元素数据类型
1.顺序存储结构及插入删除运算
ai-1…..a2a1 alegth…ai+1ai
x
Status ListInsert_sq（ Sqlist?V,int i,ElemType x） {
//在线性表 V中第 i个元素之前插入 x,i 的合法值为 1? i?V.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; }
elem length listsize
…..
a2
a1
alength
…..
ai+1
ai
0
1
i-1
i
Length-1
P
（ P+1）
q
插入运算
ai-1…..a2a1 ai ai+1 … alegth alegth… …ai+1ix
删除运算
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)
线性表的线性链表存储结构,存储从头指针开始进行。
线性链表表示法,
a1 a2 an ∧a3L …..
Typedef struct Lnode
{
Elem Type data；
struct Lnode *next；
} Lnode,*linklist；
线性表的链式存储结构可用 C语言中的,结构指针,来描述
（ 1）线性表的单链式存储结构带头结点的线性链表
data next
单链表的插入运算
Status 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;
}
ba
ba
x
∧anai
a1 a2
P
P
ai-1
x
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
P
ai-1
L
单链表的插入运算
Status 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;
}
∧anai
a1 a2
ai-1
L
单链表的插入运算
Status 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;
}
P
∧anai
a1 a2
ai-1
L
单链表的插入运算
Status 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;
}
P
∧anai
a1 a2
Pa
i-1
L
单链表的插入运算
Status 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;
}
∧anai
a1 a2
Pa
i-1
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
Pa
i-1
x
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
Pa
i-1
x
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
P
ai-1
x
L
单链表的插入运算
Status 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;
}
ai-1a1 ai ai+1
L p q
Status 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） 循环链表将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点 。
循环链表：首尾相接的链表 。
将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点 。
a1 a2 an ∧a3L …..
带头结点的单链表
a1 a2 ana3L …..
循环单链表
（ 3） 双向链表在每个结点中设置两个指针,一个指向后继,一个指向前驱 。 可直接确定一个结点的前驱和后继结点 。 可提高效率 。
data nextbefore
编写算法的一般步骤
1、分析问题描述
输入，输出及模块功能等
2、分析算法实现的总体框架，关键问题的突破方法
3、核心算法的实现
4、算法补充完善，
如：
– 增加算法有效性的保护措施 ——越界判断等
– 其它更高效的算法实现？
3.2.3,线性表的应用
—— 应用最广的数据结构
·高级语言中的数组；
·计算机的文件系统；
·计算机的目录系统；
·电话号码查询系统 （ 可采用顺序表或单链表结构 ） ；
·各种事务处理 （ 各种表格均采用顺序表和线性链表结构 ）
作业 1,某百货公司仓库中，有一批电视机,按其价格由高到低的顺序存储在计算机中,经常发生的操作是入库和出库 。
现在又新到 m 台价格为 h 元的电视机需入库，请你为仓库管理系统 设计一种数据结构,并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：
数据元素是（数量，价格），数据元素之间的价格不同。
L
S
2 8375 ^
P R
(1) L=P->link;
作业 2,对以下单链表分别执行下列各程序段,并画出结果示意图,
(2) R->data=P->data;
(3) R->data=P->link->data;
(4) P->link->link->link->data=P->data;
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
(8) T=L;
T->link=P->link;
free(P);
(9) S->link=L;
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
创立具有头指针的链表（自学）
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
n=0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
n=0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
n=0
15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
∧
n=0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
∧
n=1
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1p2 15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1p2 15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 ∧15
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 ∧15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
23
n=2
3
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=2
3
∧23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
∧23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
23
0
∧3
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
23
0
∧3
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
15
n=3
23
∧3
重新播放单击此处作业 1,某百货公司仓库中，有一批电视机,按其价格由高到低的顺序存储在计算机中,经常发生的操作是入库和出库 。
现在又新到 m 台价格为 h 元的电视机需入库，请你为仓库管理系统 设计一种数据结构,并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：
数据元素是（数量，价格），数据元素之间的价格不同。
因为经常进行入库、出库操作，即插入、删除，故使用线性链表。
结点数据结构示意图为,价格 Pi 数量 Ni 指针域 link
数据域 data
价格由高到底的顺序存储,P1 > … > Pi-1 > Pi >… > P k
P1 N1?Pi-1 Ni-1 Pi Ni Pk Nk ^?
若,Pi-1 > h > Pi
h m
L
S
2 8375 ^
P R
(1) L=P->link;
2 8375 ^
P R S
L
L
作业 2,对以下单链表分别执行下列各程序段,并画出结果示意图,
L
S
2 8375 ^
P R
(2) R->data=P->data;
2 8575 ^
P R S
(3) R->data=P->link->data;
2 8775 ^
P R S
L
S
2 8375 ^
P R
(4) P->link->link->link->data=P->data;
2 5375 ^
P R S
L
S
2 8375 ^
P R
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 16
L
S
2 8375 ^
P R
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 8
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P 10
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(8) T=L;
T->link=P->link;
free(P);
L
S
2 837 ^
P
RT
5
L
S
2 8375 ^
P R
(9) S->link=L;
L
S
2 8375
P R
如果 S->link= =L 则 S所指向的结点为尾结点,
L
S
2 8375 ^
P R
3.1 概述
3.2 线性表
3.3 栈
3.4 队列
3.5 数组
3.6 树与二叉树
3.7 图第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
能输入到计算机中并能被计算机程序处理的符号的集合。
整数 (1,2)、实数 (1.1,1.2)
字符串 (Beijing)、
图形、声音。
第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
计算机管理图书问题在图书馆里有各种卡片：有按书名编排的、
有按作者编排的、有按分类编排如何将查询图书的这些信息存入计算机中既要考虑查询时间短，又要考虑节省空间第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
最简单的办法之一是建立一张表，
每一本书的信息在表中占一行，如第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
如何将 0,1,2,3,4,5,6,7,8,9这 10个数存放在计算机中能最快地达到你所需要的目的？
目的不同,最佳 的存储方方法就不同 。
从大到小排列,9,8,7,6,5,4,3,2,1,0
输出偶数,0,2,4,6,8,1,3,5,7,9
数据元素在计算机中的表示第三章 基本数据结构及运算
3.1 概述数据结构是一门研究 数据 组织,
存储 和 运算 的一般方法的学科。
对数据结构中的节点进行操作处理
(插入、删除、修改、查找、排序 )
数据,计算机处理的对象数据元素 (Data Element),数据的基本单位一个数据元素可由若干 数据项 (Data Item)组成。
数据项,数据的最小单位。
数据对象 (Data Object)：是性质相同的数据元素的集合。是数据的一个子集。
数据结构 (Data Structure)：是相互之间存在一种或多种特定关系的数据元素的集合。
数据元素亦称 结点 或 记录数据项亦称 字段 或 域数据结构 可描述为 Group=（ D,R）
有限个 数据元素 的集合有限个结点间 关系 的集合数据元素间的关系,前后件关系
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A,线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队列树形结构图形结构数据结构的三个方面数据结构可描述为 Group=（ D,R）
数组
A,线性结构 （一对一）
特性,1.有且只有一个根结点
2.每个结点最多一个 前件,最多一个 后件 。
（第一个数据元素无前件，最后一个无后件，其它有且仅有一个 前驱 和一个 后继 。）
例,（ A,B,C,·······,X,Y,Z）
例,学 生 成 绩 表
86胡孝臣9861103
95刘忠赏9861107
100张卓9861109
成绩姓名学号
1．数据的逻辑结构
DS1=（ D1,R1） 集合表示法
D1={k1,k2,k3,k4}
R1={（ k1,k2），（ k2,k3），（ k3,k4） }
DS2=(D2,R2)
D2={k1,k2,k3}
R2={(k1,k2),(k1,k3)}
k1 k2 k3 k4
k1
k2
k3
例：
例：
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面数据结构可描述为 Group=（ D,R）
数组
B．非线性结构,树形结构 （一对多）
全校学生档案管理的组织方式计算机程序管理系统也是典型的树形结构识别,体,字的过程丿 乙 亻 刂借 何体 休体 休判断偏旁部首四角号码匹配局部匹配按分支和层次组织的数据，称为：
,树形结构,
A
B C
D
E F G H
树形结构 —— 结点间具有分层次的连接关系
H
B C D
E F G
A
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组
1 4
2 3
D={ 1,2,3,4}
R={(1,2),(1,3),(1,4),(2,3)
(3,4),(2,4) }
2
1
3
D={ 1,2,3 }
R={ (1,2),(2,3),(3,2),(1,3) }
B．非线性结构,图形结构 （多对多）
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组元素 n
……..
元素 i
……..
元素 2
元素 1L
o
Lo+m
Lo+(i-1)*m
Lo+（ n-1)*m
存储地址存储内容
Loc(a)=Lo+（ i-1)*m
A,顺序存储每个元素所占用的存储单元个数
2、数据的存储结构元素 n
……..
元素 i
……..
元素 2
元素 1
存储内容顺序存储结构 常用于线性数据结构，将逻辑上相邻的数据元素存储在物理上相邻的存储单元里。
顺序存储结构的三个 弱点,
1.插入或删除操作时，需移动大量元素。
2.长度变化较大时，需按最大空间分配。
3.表的容量难以扩充。
1．数据的逻辑结构
2、数据的存储结构
3、数据的运算：检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h B.链式存储每个节点都由两部分组成,数据域 和 指针域 。
数据域 存放元素本身的数据，
指针域 存放指针。
数据元素之间逻辑上的联系由指针来体现 。
1536元素 21400元素 1 1346元素 3 ∧元素 4
head
1346元素 31536
……,……,.……,
1536元素 21400
……,……,.……,
∧元素 41346
1400元素 11345
指针存储内容存储地址链式存储
1345
1536元素 21400元素 1 1346元素 3 ∧元素 4
1345
h 链式存储
1.比顺序存储结构的存储密度小
(每个节点都由数据域和指针愈组成 )。
2.逻辑上相邻的节点物理上不必相邻。
3.插入、删除灵活
(不必移动节点，只要改变节点中的指针 )。
链式存储结构特点：
链表的一个重要特点是 插入、删除运算灵活方便，不需移动结点，只要改变结点中指针域的值即可
a b
H e a d
┄ a b
H e a d
┄
x
∧
插 入
a c
Head
┄b ∧
删 除
1．数据的逻辑结构
2、数据的存储结构
3,数据的运算,检索、排序、插入、删除、修改等。
A．线性结构
B,非线性结构
A 顺序存储
B 链式存储线性表栈队树形结构图形结构数据结构的三个方面
(亦称物理结构 )
数组例 管理信息系统中的查询问题各种计算机管理信息系统中，通常相关的信息 (记录 )组成一个表文件,表文件是一类很重要的数据结构文件中的记录可按顺序方式组织黄鹏 8211 编译原理刘东 8201 算法分析李季为 8211 编译原理李宾 8202 算法分析王华 8202 图形学杜可翔 8201 编译原理何平 8201 编译原理陈红英 8211 算法分析
姓名 班级 选修课 链链头
┊
(b)(a)
黄鹏 8211 编译原理刘东 8201 算法分析李季为 8211 编译原理李宾 8202 算法分析王华 8202 图形学杜可翔 8201 编译原理何平 8201 编译原理陈红英 8211 算法分析
姓名 班级 选修课 链链头
┊
(b)(a)
顺序文件 导出的链表为提高检索效率,可将所有选修,算法分析,课的同学记录串接到一起，这种串接称为,加链”
3.2.1.线性表的逻辑结构
3.2.2 线性表的存储结构及运算
3.2.3 线性表的应用
3.2.4 作业
3.2 线性表
3.2.1.线性表的逻辑结构
线性表逻辑结构
– n个数据元素的有限序列,(a1,a2,a3,… an)
n为线性表的长度 (n≥0),n=0的表称为 空表
特性：
– 数据元素呈线性关系,
– 所有数据元素 ai在同一个线性表中须是 相同的数据类型
例,学生表
86胡孝臣9861103
95刘忠赏9861107
100张卓9861109
成绩姓名学号
线性表的基本运算：
(1)插入,在两个确定的元素之间插入一个新的元素；
(2)删除,删除线性表中某个元素；
(3)修改,按某种要求查找线性表中的一个元素，
需要时，还可找到元素进行值的更新
3.2.2 线性表的存储结构
1.顺序存储结构及插入删除运算
2.链式存储结构 及插入删除运算
（ 1）单链表
（ 2）循环链表
（ 3）双向链表
elem length listsize
元素 1
元素 2
……,.
元素 i
……,.
0
1
i-1V.elem[i-1]
线性表的顺序存储结构,可用 C语言中的一维数组来描述,
#define LISTINITSIZE 100 //线性表存储空间的初始分配量
typedef struct{
ElemType *elem； //数组指针 表示存储空间基址
int length； //当前长度
int listsize //当前分配的存储容量 （ 以 sizeof（ ElemType） 为单位 ）
}Sqlist
C语言的库函数,
测算 ElemType节点需占用的字节数元素数据类型
1.顺序存储结构及插入删除运算
ai-1…..a2a1 alegth…ai+1ai
x
Status ListInsert_sq（ Sqlist?V,int i,ElemType x） {
//在线性表 V中第 i个元素之前插入 x,i 的合法值为 1? i?V.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; }
elem length listsize
…..
a2
a1
alength
…..
ai+1
ai
0
1
i-1
i
Length-1
P
（ P+1）
q
插入运算
ai-1…..a2a1 ai ai+1 … alegth alegth… …ai+1ix
删除运算
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)
线性表的线性链表存储结构,存储从头指针开始进行。
线性链表表示法,
a1 a2 an ∧a3L …..
Typedef struct Lnode
{
Elem Type data；
struct Lnode *next；
} Lnode,*linklist；
线性表的链式存储结构可用 C语言中的,结构指针,来描述
（ 1）线性表的单链式存储结构带头结点的线性链表
data next
单链表的插入运算
Status 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;
}
ba
ba
x
∧anai
a1 a2
P
P
ai-1
x
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
P
ai-1
L
单链表的插入运算
Status 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;
}
∧anai
a1 a2
ai-1
L
单链表的插入运算
Status 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;
}
P
∧anai
a1 a2
ai-1
L
单链表的插入运算
Status 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;
}
P
∧anai
a1 a2
Pa
i-1
L
单链表的插入运算
Status 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;
}
∧anai
a1 a2
Pa
i-1
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
Pa
i-1
x
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
Pa
i-1
x
L
单链表的插入运算
Status 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;
}
S
∧anai
a1 a2
P
ai-1
x
L
单链表的插入运算
Status 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;
}
ai-1a1 ai ai+1
L p q
Status 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） 循环链表将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点 。
循环链表：首尾相接的链表 。
将最后一个结点的空指针改为指向头结点,从任一结点出发均可找到其它结点 。
a1 a2 an ∧a3L …..
带头结点的单链表
a1 a2 ana3L …..
循环单链表
（ 3） 双向链表在每个结点中设置两个指针,一个指向后继,一个指向前驱 。 可直接确定一个结点的前驱和后继结点 。 可提高效率 。
data nextbefore
编写算法的一般步骤
1、分析问题描述
输入，输出及模块功能等
2、分析算法实现的总体框架，关键问题的突破方法
3、核心算法的实现
4、算法补充完善，
如：
– 增加算法有效性的保护措施 ——越界判断等
– 其它更高效的算法实现？
3.2.3,线性表的应用
—— 应用最广的数据结构
·高级语言中的数组；
·计算机的文件系统；
·计算机的目录系统；
·电话号码查询系统 （ 可采用顺序表或单链表结构 ） ；
·各种事务处理 （ 各种表格均采用顺序表和线性链表结构 ）
作业 1,某百货公司仓库中，有一批电视机,按其价格由高到低的顺序存储在计算机中,经常发生的操作是入库和出库 。
现在又新到 m 台价格为 h 元的电视机需入库，请你为仓库管理系统 设计一种数据结构,并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：
数据元素是（数量，价格），数据元素之间的价格不同。
L
S
2 8375 ^
P R
(1) L=P->link;
作业 2,对以下单链表分别执行下列各程序段,并画出结果示意图,
(2) R->data=P->data;
(3) R->data=P->link->data;
(4) P->link->link->link->data=P->data;
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
(8) T=L;
T->link=P->link;
free(P);
(9) S->link=L;
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
创立具有头指针的链表（自学）
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
n=0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
n=0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
n=0
15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
∧
n=0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n==1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
∧
n=1
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1p2 15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1p2 15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 ∧15
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 ∧15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2 15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
23
n=2
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
23
n=2
3
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=2
3
∧23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
∧23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
3
23
0
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
23
0
∧3
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
p1
p2
15
n=3
23
0
∧3
Linklist creat()
{linklist head,p1,p2;
n=0； p1=p2=(struct lnode*)malloc(LEN)；
scanf(“%d”,&p1->data)； head->next=NULL;
while(p1->data!>0)
{n=n+1；
if(n= =1) head->next=p1；
else p2->next=p1；
p2=p1； p1=(struct lnode*)malloc(LEN)；
scanf(%d”,&p1->data)； p2->next=NULL；
}return(head)； }
Head
15
n=3
23
∧3
重新播放单击此处作业 1,某百货公司仓库中，有一批电视机,按其价格由高到低的顺序存储在计算机中,经常发生的操作是入库和出库 。
现在又新到 m 台价格为 h 元的电视机需入库，请你为仓库管理系统 设计一种数据结构,并画出逻辑示意图。用框图的形式给出增加电视机到数据结构中（插入操作）的思想。注意：
数据元素是（数量，价格），数据元素之间的价格不同。
因为经常进行入库、出库操作，即插入、删除，故使用线性链表。
结点数据结构示意图为,价格 Pi 数量 Ni 指针域 link
数据域 data
价格由高到底的顺序存储,P1 > … > Pi-1 > Pi >… > P k
P1 N1?Pi-1 Ni-1 Pi Ni Pk Nk ^?
若,Pi-1 > h > Pi
h m
L
S
2 8375 ^
P R
(1) L=P->link;
2 8375 ^
P R S
L
L
作业 2,对以下单链表分别执行下列各程序段,并画出结果示意图,
L
S
2 8375 ^
P R
(2) R->data=P->data;
2 8575 ^
P R S
(3) R->data=P->link->data;
2 8775 ^
P R S
L
S
2 8375 ^
P R
(4) P->link->link->link->data=P->data;
2 5375 ^
P R S
L
S
2 8375 ^
P R
(5) T=P;
while(T!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 16
L
S
2 8375 ^
P R
(6) T=P;
while(T->link!=NULL)
{ T->data=(T->data)*2;
T=T->link; }
L
S
2 ^
P R
10 14 6 8
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
P 10
L
S
2 8375 ^
P R
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(7) P=(JD*)malloc(sizeof(JD));
P->data=10;
R->link=P;
P->link=S;
L
S
2 8375 ^
R
P 10
L
S
2 8375 ^
P R
(8) T=L;
T->link=P->link;
free(P);
L
S
2 837 ^
P
RT
5
L
S
2 8375 ^
P R
(9) S->link=L;
L
S
2 8375
P R
如果 S->link= =L 则 S所指向的结点为尾结点,
L
S
2 8375 ^
P R
