数据结构第2章线性表--2.12.2南京工程学院通信工程学院.ppt

线性结构的特点:
除第一个之外的数据元素均只有一个前驱;
存在唯一的一个被称作“第一个”的数据元素;
除最后一个之外的数据元素均只有一个后继。
数据元素的
非空有限集
存在唯一的一个被称作“最后一个”的数据元素;
第2章线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
线性链表
循环链表
双向链表
一元多项式的表示及相加
其中数据元素的个数n定义为表的长度。
当n=0时称为空表,常常将非空的线性表(n>0)记作: (a1,a2,…an)
这里的数据元素ai(1≦i≦n)只是一个抽象的符号,其具体含义在不同的情况下可以不同。
线性表(Linear List) :由 n (n0) 个数据元素 a1, a2, …, an 组成的
有限并且有序的序列。
线性表的类型定义
例3、学生健康情况登记表如下:
姓名
学号
性别
年龄
健康情况
王小林
790631
男
18
健康
陈红
790632
女
20
一般
刘建平
790633
男
21
健康
张立立
790634
男
17
神经衰弱
……..
……..
…….
…….
…….
名称
线性表
数据对象
D={ai| ai(-ElemSet,i=1,2,...,n,n>=0}
任意数据元素的集合
数据关系
R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
除第一个和最后一个外,每个元素有唯一的直接前趋和唯一的直接后继
基本操作
ListInsert(&L,i,e)
L为线性表,i为位置,e为数据元素。
ListDelete(&L,i,e)
...
线性表的抽象数据类型定义
2-1 利用两个线性表La和Lb分别表示两个集合A和B,现要求一个新的集合A=A∪B。
void union(List &La,List Lb)
{
La_len=Listlength(La);
Lb_len=Listlength(Lb);
for(i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,e);
if(!LocateEem(La,e,equal))
ListInsert(La,++La_len,e)
}
}
例2-2 巳知线性表La和线性表Lb中的数据元素按值非递减有序排列,现要求将La和Lb归并为一个新的线性表Lc,且Lc中的元素仍按值非递减有序排列。
void mergelist(list La,list Lb,list &Lc){
InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);
Lb_len=ListLength (Lb);
while((i<=La_len)&&(j<=Lb_len))
{
GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai<=bj){ListInsert(Lc,++k,ai);++i;}
else{ListInsert(Lc,++k,bj);++j;}
}
while(i<=La_len){
GetElem((La,i++,ai);
ListInsert(Lc,++k,ai);
}
while(j<=Lb_len)
{
GetElem((Lb,j++,bj);
ListInsert(Lc,++k,bi);
}
}
线性表的顺序表示和实现
线性表的顺序表示:在计算机中用一组地址连续的存储单元
依次存储线性表的各个数据元素,称作线性表的顺序存储结构或
顺序映象。用这种方法存储的线性表称作顺序表。
顺序表的特点:
以物理位置相邻表示逻辑关系。
任一元素均可随机存取。
顺序表的优点:
顺序表中数据元素存储位置的计算:
所有数据元素的存储位置均可由第一个数据元素的存
储位置得到: LOC(ai ) = LOC(a1) + (i -1)  l
a1 a2 … ai-1 ai … an