资源描述：
《数据结构c语言描述第2章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第2章线性表第2章线性表2.1线性表的概念及运算2.2线性表的顺序存储2.3线性表的链式存储2.4一元多项式的表示及相加第2章线性表2.1线性表的概念及运算2.1.1线性表的逻辑结构 图2.1线性表的逻辑结构第2章线性表例如：英文字母表(A,B,…,Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素，每个元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A，而字母B的后面是字母C。在较为复杂的线性表中，数据元素(dataelements)可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩是一个数
2、据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item)组成，常被称为一个记录(record)，含有大量记录的线性表称为文件(file)。数据对象（dataobject）是性质相同的数据元素集合。第2章线性表表2-1车辆登记表第2章线性表线性表(LinearList)是由n(n≥0)个类型相同的数据元素a,1a,…，a组成的有限序列，记作（a,a,…，a，a，a，…，2n12i-1ii+1a）。这里的数据元素a(1≤i≤n)只是一个抽象的符号，其具体ni含义在不同情况下可以不同，它既可以是原子类型，也可以是结构类型
3、但同一线性表中的数据元素必须属于同一数据对象。此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a,a,…，a,a,a,…,a），表中a领先于a，称a12i-1ii+1ni-1ii-1是a的直接前驱，而称a是a的直接后继。除了第一个元素aiii-11外，每个元素a有且仅有一个被称为其直接前驱的结点a，除了ii-1最后一个元素a外，每个元素a有且仅有一个被称为其直接后继ni的结点a。线性表中元素的个数n被定义为线性表的长度，n=0i+1时称为空表。第2章线性表线性表的特点可概括如下： 同一性：线性表由同类数
4、据元素组成，每一个a必须属于i同一数据对象。 有穷性：线性表由有限个数据元素组成，表长度就是表中数据元素的个数。 有序性：线性表中表中相邻数据元素之间存在着序偶关系。 ii+1由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、队列等都符合线性条件。第2章线性表2.1.2线性表的抽象数据类型定义ADTLinearList{数据元素：D={a
5、a∈D,i=1,2,…，n,n≥0，D为某一ii00数据对象}关系
6、：Ｓ＝｛
7、a,a∈D，i=1,2,…,n-1｝ ii+1ii+10基本操作：（1）InitList（L） 操作前提：L为未初始化线性表。 操作结果：将L初始化为空表。第2章线性表（2）DestroyList(L)操作前提：线性表L已存在。 操作结果：将L销毁。 （3）ClearList(L)操作前提：线性表L已存在。 操作结果：将表L置为空表。 （4）EmptyList（L） 操作前提：线性表L已存在。 操作结果：如果L为空表则返回真，否则返回假。第2章线性表（5）ListLength（L） 操作前提：线性表L
8、已存在。 操作结果：如果L为空表则返回0，否则返回表中的元素个数。（6）Locate(L,e)操作前提：表L已存在，e为合法元素值。 操作结果：如果L中存在元素e，则将“当前指针”指向元素e所在位置并返回真，否则返回假。 （7）GetData(L,i)操作前提：表L存在，且i值合法，即1≤i≤ListLength（L）。 操作结果：返回线性表L中第i个元素的值。第2章线性表（8）InsList(L,i,e)操作前提：表L已存在，e为合法元素值且1≤i≤ListLength(L)+1。 操作结果：在L中第i个位置插入新的数
9、据元素e，L的长度加1。（9）DelList(L,i,&e)操作前提：表L已存在且非空，1≤i≤ListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。 }ADTLinearList第2章线性表2.2线性表的顺序存储2.2.1线性表的顺序存储结构线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系。采用顺序存储结构的线性表通常称为顺序表
10、。第2章线性表假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计算出第i个元素的地址loc(a-i)： loc(a)=loc(a)+(i-1)×ki1其中loc(a-1)称为基地址。第2章线性表存储地址内存空间状态逻辑地址loc(a)a111loc(a)＋ka212
