《数据结构课件第2章 +线 性表》由会员分享，可在线阅读，更多相关《数据结构课件第2章 +线 性表（78页珍藏版）》请在金锄头文库上搜索。
1、数据结构,第2章 线 性 表,在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。,2.1 线性表基本特征和基本运算,1线性表的定义 线性表是具有相同数据类型的n(n=0)个数据元素的有限序列，通常记为 (a1，a2， ai-1，ai，ai+1，an) 其中n为表长，n0时称为空表。,线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2； 有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1； 其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和
2、一个直接后继a i+1。,例1、数学中的数列（11，13，15，17，19，21） 例2、英文字母表（A, B, C, D, E Z ）。 例3、某单位的电话号码簿。,2 线性表的基本运算,对于给定的线性表，可进行如下的基本运算： （1）线性表的初始化init; （2）判断线性表是否为空empty; （3）求线性表的长度n; （4）在线性表中查找值为x的数据元素的位置locate; （5）取得线性表中第i个数据元素的值get； （6）输出线性表中的数据元素print; （7）在第i个数据元素前面插入值为x的数据元素insert； （8）在线性表中删除第i个数据元素delete;,还有一些比较复
3、杂的运算： （9）将两个线性表合并成一个线性表merge; （10）将一个线性表拆成多个线性表split; （11）将线性表中的数据元素按照关键字排序sort;,为了存储线性表，至少要保存两类信息： 1）线性表中的数据元素； 2）线性表中数据元素的顺序关系；,线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。,用顺序存储结构存储的线性表称为顺序表,2.2 线性表的顺序存储及运算实现,2.2.1 顺序表,#define MAXSIZE 100 typedef struct int dataMAXSIZE; int n; SeqList; 定义一个顺序表：SeqList L
4、;,存放数据,表长,顺序表的完整定义,（1）顺序表的初始化init;,/ / 函数功能:顺序表的初始化置空表 / / 函数参数:指向SeqList型变量的指针变量slt / / 函数返回值:空 / / 函数名:init() / /,void init(SeqList slt) slt-n=0; ,SeqList init( ) SeqList slt; slt.n=0; return slt; ,（2）判断顺序表是否为空,/ / 函数功能:判断顺序表是否为空 / / 函数参数:SeqList型变量slt / / 函数返回值:int类型。1表示空,0表示非空 / / 函数名:empty() /
5、/,int empty(SeqList slt) return (slt.n=0 ? 1:0); ,（3）求线性表的长度n,/ / 函数功能: 求线性表的长度n / / 函数参数: SeqList型变量slt / / 函数返回值: int类型。 / / 函数名: length() / /,int length(SeqList slt) return (slt.n); ,(4) 在线性表中查找值为x的数据元素的位置locate,/ / 函数功能:查找顺序表中值为x的结点位置 / / 函数参数: SeqList型变量slt, datatype型变量x / / 函数返回值:int类型。返回x的下标值
6、, -1表示没找到 / / 函数名:locate() / /,int locate(SeqList slt, datatype x) int i=0; while(islt.n ,(5) 取得线性表中第i个数据元素的值get,/ / 函数功能: 取得顺序表中第i个结点的值 / / 函数参数: SeqList型变量slt, int型变量i / / 函数返回值: datatype类型。返回第i个结点的值 / / 函数名:get() / /,datatype get(SeqList slt, int i) if(islt.n) printf(“n指定位置的结点不存在!“);exit(1); else
7、 return slt.datai-1; ,（6）输出线性表中的数据元素print;,/ / 函数功能:打印顺序表的各结点值 / / 函数参数:SeqList型变量slt / / 函数返回值:空 / / 函数名:print() / /,void print(SeqList slt) int i; if(!slt.n) printf(“n顺序表是空的!“); else for(i=0; islt.n; i+) printf(“%5d“,slt.datai); ,（7）在第i个数据元素前面插入值为x的数据元素insert；,功能：在顺序表中的第 i ( 1=i=n+1)个数据元素之前插入一个新元素
8、x, 插入前线性表为 (a1, a2, a3, ai-1 ,ai, an ) 插入后,线性表长度为n+1, 线性表为 (a1, a2, a3, ai-1 , x, ai, an ),/ / 函数功能:在顺序表的第i个位置插入值为x的结点 / / 函数参数:指向SeqList型变量的指针变量slt / / datatype型变量x,int型变量 position / / 函数返回值:空 函数名:insert() / /,if(i(slt-n)+1) printf(“n指定的插入位置不存在!“);exit(1);,void insert(SeqList slt, datatype x, int i
9、), int j; for(j=slt-n;j=i;j-) slt-dataj=slt-dataj-1; slt-datai-1=x; slt-n+; ,if(slt-n=MAXSIZE) printf(“n顺序表是满的!没法插入!“);exit(1);,算法中，所花费的时间主要是元素后移操作，对于在第i个位置上插入一个新的元素，需要移动（n-i）个元素，设在第i个位置上插入一个元素的概率为pi，且在任意一个位置上插入元素的概率相等，即p0=p1=p2=pn=1/n+1，则在一个长度为n的顺序表中插入一个元素所需的平均移动次数为：,即在长度为n的顺序表中插入一个元素平均需要移动表中的一半元素。
10、该算法的时间复杂度为O（n）。,（8）在线性表中删除第i个数据元素delete,功能：在顺序表中删除第 i ( 1=i=n)个数据元素, 删除前线性表为 (a1, a2, a3, ai-1 ,ai, an ) 插入后,线性表长度为n+1, 线性表为 (a1, a2, a3, ai-1 , ai,+1, an ) 注：要求删除第i个数据元素，线性表元素在数组中必须连续排列，中间不能有空单元。,/ / 函数功能:删除顺序表中第i位置的结点 / / 函数参数:指向SeqList型变量的指针变量slt, int型变量i / / 函数返回值:空 , 函数名:delete() / /,void dele(
11、SeqList slt, int i), int j; for(j=i; jn;j+) slt-dataj-1=slt-dataj; slt-n-; ,if(slt-n=0) printf(“n顺序表是空的!“);exit(1);,if(islt-n) printf(“n指定的删除位置不存在!“);exit(1);,要删除顺序表中的第i个结点，则需要称动（n-i-1）个元素，设删除表中第i个结点的概率为qi，且在表中每一个位置删除的概率相等，即： q0=q1=qn-1=1/n 则在一个长度为n的顺序表中删除一个结点的平均移动次数为：,这表明，在一个长为n的顺序表中删除一个元素平均需要移动表中大约一半的元素。该算法的时间复杂度为O（n）。,举例删除顺序表中的重复元素,一个顺序表中可能含有一些值相同的重复元素，题目要求对于值相同的重复元素只保留位序最小的一个而删除其它多余的元素。 如（5，2，2，3，5，2）经删除重复元素后变为 （5，2，3） 算法思路：从顺序表中第一个元素起，逐个检查它后面是否有值相同的其它元素，若有便删除之；直到表中所有元素都已无重复元素为止。为此，算法中需设两重循环，外层控制清除的趟数，内层控制每趟的检查范围。,删除顺序表中的
