单元2_线性表

1、烟台职业学院信息工程学院- 数据结构数据结构-第第2章线性表章线性表 数据结构数据结构 第第2章章 线性表线性表 能力目标：能力目标：主要内容：主要内容： 数据结构数据结构 第第2章章 线性表的定义和顺序存储线性表的定义和顺序存储1线性表的操作和相应算法线性表的操作和相应算法26栈的定义及顺序存储、操作和算法栈的定义及顺序存储、操作和算法3队列的定义及顺序存储、操作和算法队列的定义及顺序存储、操作和算法45字符串的定义及顺序存储、操作和算法字符串的定义及顺序存储、操作和算法 数据结构数据结构 v线性表的定义（线性表的定义（LS）：）： 线性表（线性表（Linear List）是）是n（n0）个

2、具有相同属性的数据个具有相同属性的数据元素的有限序列，记为：元素的有限序列，记为： (a1，a2，ai-1 ，ai ，ai+1 ，an) ai(1in) 元素的个数元素的个数n称为线性表的长度。称为线性表的长度。 当当n=0时称为空表，不含有任何元素。时称为空表，不含有任何元素。 在非空在非空(n0)的线性表中：的线性表中： 有且仅有一个开始结点有且仅有一个开始结点a1（表头元素）（表头元素）,无直接前趋无直接前趋,仅有一个直接后继仅有一个直接后继a2。 有且仅有一个终端结点有且仅有一个终端结点an （表尾元素）（表尾元素）,无直接后继无直接后继,仅有一个直接前趋仅有一个直接前趋an-1。 其

3、余内部结点其余内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直接前趋ai-1和一个直接后继和一个直接后继ai+1。 线性表是一种典型的线性结构。线性表是一种典型的线性结构。 数据结构数据结构 v线性表的顺序存储线性表的顺序存储（MS）：）： 数据结构数据结构 假设线性表中的第一个数据元素的存储地址（首地址）为假设线性表中的第一个数据元素的存储地址（首地址）为LOC(a1)，每一个数据元素占每一个数据元素占k个字节，则各元素的存储地址有如下关系：个字节，则各元素的存储地址有如下关系： LOC（a2）=LOC(a1)1k LOC（a3）=LOC(a1)2k LOC（an）=LOC(

4、a1)(n-1)k （1nMAX） 因此，线性表中第因此，线性表中第i个元素个元素ai在计算机中的存储地址为：在计算机中的存储地址为： LOC(ai)= LOC(a1)+(i-1)k （1in） 顺序存储结构顺序存储结构线性表中每一个数据元素在计算机存储空间中的存储地址线性表中每一个数据元素在计算机存储空间中的存储地址由该元素在线性表中的序号惟一确定由该元素在线性表中的序号惟一确定 数据结构数据结构 数据结构数据结构 线性表的顺序存储结构定义线性表的顺序存储结构定义#define MAX 线性表最大长度线性表最大长度+1typedef 元素类型元素类型 datatypetypedef stru

5、ct datatype dataMAX; /*线性表的数据元素线性表的数据元素*/ int last; /*线性表的实际长度线性表的实际长度*/ list; /*线性表的结构类型线性表的结构类型*/ 数据结构数据结构 线性表变量线性表变量lst和指针变量和指针变量lp 数据结构数据结构 数据结构数据结构 1线性表初始化。线性表初始化。init(lst)构造一个空表构造一个空表线性表的顺序存储结构定义线性表的顺序存储结构定义#define MAX 线性表最大长度线性表最大长度+1typedef 元素类型元素类型 datatypetypedef struct datatype dataMAX; /

6、*线性表的数据元素线性表的数据元素*/ int last; /*线性表的实际长度线性表的实际长度*/ list; /*线性表的结构类型线性表的结构类型*/list lst; /*线性表变量线性表变量lst*/线性表的初始化线性表的初始化void init (list *lp) lp-last=0; 算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 2求线性表长度。求线性表长度。length(lst)求表所含元素的个数。求表所含元素的个数。线性表的顺序存储结构定义线性表的顺序存储结构定义#define MAX 线性表最大长度线性表最大长度+1typedef 元素类型元素类型 dat

7、atypetypedef struct datatype dataMAX; /*线性表的数据元素线性表的数据元素*/ int last; /*线性表的实际长度线性表的实际长度*/ list; /*线性表的结构类型线性表的结构类型*/list lst; /*线性表变量线性表变量lst*/线性表的长度线性表的长度int length(list *lp) return lp-last;算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 3插入。插入。insert(lst,i,x)在表第在表第i个位置插入一个值为个位置插入一个值为 x的新元素。的新元素。void insert(list *

8、lp,int i, datatype x) int j; if(lp-last=MAX-1) printf(“Overflow!”);exit(1); /表已满表已满 if(ilp-last+1)printf(“Error!”);exit(1); /插入位置出错插入位置出错 for(j=p-last ;j=i;j-) lp-dataj+1=lp-dataj; /数据元素后移数据元素后移 lp-datai=x; /插入插入x lp-last+; /表长度加表长度加1 时间复杂度为时间复杂度为(n)。 数据结构数据结构 数据结构数据结构 )1(11inpEniiin11112)1(11)1(Eni

9、niiinninninp假设表中任何位置插入概率是均等的假设表中任何位置插入概率是均等的, ,即即Pi=1/ (n+1) , ,则：则： 算法分析：算法分析： 该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置 i和表的长度和表的长度n。所所以可以用数据元素的移动操作来估计算法的时间复杂度。在第以可以用数据元素的移动操作来估计算法的时间复杂度。在第 i个位置上插入个位置上插入 x ，共需要移共需要移动动 n-i+1个元素，个元素， i 的取值范围为的取值范围为 ：1i n+1，即有即有 n+1个位置可以插入。个位置可以插入。

10、 当当i=n+1时，不需要移动结点；当时，不需要移动结点；当i=1时需要移动时需要移动n个结点个结点 。由此可以看出，算法在最好。由此可以看出，算法在最好的情况下时间复杂性为的情况下时间复杂性为O(1)，最坏的时间复杂性是最坏的时间复杂性是O(n)。 由于插入的位置是随机的，因此，需要分析执行该算法移动数据元素的平均值。设在第由于插入的位置是随机的，因此，需要分析执行该算法移动数据元素的平均值。设在第i个位置上作插入的概率为个位置上作插入的概率为Pi，则平均移动数据元素的次数：则平均移动数据元素的次数： 由此可以看出，在线性表上做插入操作需要移动表中一半的数据元素，当由此可以看出，在线性表上做

11、插入操作需要移动表中一半的数据元素，当n较大时，算法较大时，算法的效率是比较低的，所以在线性表上进行插入操作的时间复杂度为的效率是比较低的，所以在线性表上进行插入操作的时间复杂度为(n)。 数据结构数据结构 4删除。删除。delete(lst,i)在表中删除第在表中删除第i个数据元素。个数据元素。 void delete(list *lp,int i) /删除线性表中第删除线性表中第i个位置上的元素个位置上的元素 if(ilp-last) /检查空表及删除位置的合法性检查空表及删除位置的合法性 printf (不存在第不存在第i个元素个元素);exit(0); for(j=i+1;jlast;

12、j+) lp-dataj-1=lp-dataj; /向前移动元素向前移动元素 lp-last-; /表长度减表长度减1 时间复杂度为时间复杂度为(n)。 数据结构数据结构 niideinp1)(E11121)(1)(Eniniideninninp 删除算法的时间性能分析：删除算法的时间性能分析： 与插入运算相同，删除运算的时间也主要消耗在移动表中数与插入运算相同，删除运算的时间也主要消耗在移动表中数据元素上，删除第据元素上，删除第i个元素时，其后面的元素个元素时，其后面的元素 ai+1an 都要向前移都要向前移动一个位置，共移动了动一个位置，共移动了 n-i 个元素，所以在等概率的情况下，在个

13、元素，所以在等概率的情况下，在线性表中删除数据元素所需移动数据元素的期望值，即平均移动线性表中删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数为：数据元素的次数为： 由此可以看出，在线性表上删除数据元素时大约需要移动表由此可以看出，在线性表上删除数据元素时大约需要移动表中一半的元素，显然该算法的时间复杂度为中一半的元素，显然该算法的时间复杂度为(n)。 通常情况下，我们认为在线性表中任何位置删除元素是等通常情况下，我们认为在线性表中任何位置删除元素是等概率的，即概率的，即pi =1/ n，则：则： 数据结构数据结构 5按值查找。按值查找。locate(lst,x)在表中查找值为在

14、表中查找值为x的数据元素位置。的数据元素位置。 从头往后查找从头往后查找int locate(list *lp,datatype x) int i=1； while( ilast & lp-datai!=x ) i+; if(ilast) return i ; /*返回返回i下标，即元素位置下标，即元素位置*/ else return 0; O(n)。 数据结构数据结构 5按值查找。按值查找。locate(lst,x)在表查找值为在表查找值为x的数据元素的位置。的数据元素的位置。 从尾往头查找从尾往头查找int locate(list *lp,datatype x) int i=lp-

15、last; while(i0 & lp-datai!=x)i-; return i; 数据结构数据结构 数据结构数据结构 数据结构数据结构 v 栈栈的定义（的定义（LS）及顺序存储（）及顺序存储（MS）：）：栈的顺序存储结构定义栈的顺序存储结构定义#define MAX 栈中允许存放元素的最大个数栈中允许存放元素的最大个数+1typedef 元素类型元素类型 datatypetypedef struct datatype dataMAX; /*栈的数据元素栈的数据元素*/ int top; /*栈顶下标位置栈顶下标位置*/ stack; /*栈的结构类型栈的结构类型*/ 数据结构数据结

16、构 stack s,*sp;栈变量栈变量s和指针变量和指针变量spssps 数据结构数据结构 数据结构数据结构 1栈的初始化。栈的初始化。init(s)构造一个空表构造一个空表栈的初始化栈的初始化void init (stack *sp) sp-top=0; 算法的时间复杂度为算法的时间复杂度为O(1) 栈的顺序存储结构定义栈的顺序存储结构定义#define MAX 栈中允许存放元素的最大个数栈中允许存放元素的最大个数+1typedef 元素类型元素类型 datatypetypedef struct datatype dataMAX; /*栈的数据元素栈的数据元素*/ int top; /*栈

17、顶下标位置栈顶下标位置*/ stack; /*栈的结构类型栈的结构类型*/stack s,*sp; /*栈变量栈变量s和指针变量和指针变量sp*/ 数据结构数据结构 2判栈空。判栈空。empty(s)若栈若栈s为空返回为为空返回为1，否则返回为，否则返回为0。 int empty(stack *sp) return (sp-top=0?1:0);算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 3压栈。压栈。push(s,x)将元素将元素x插入栈中，使插入栈中，使x成为栈顶元素，栈满成为栈顶元素，栈满返回返回0，成功返回，成功返回1。 int push(stack *sp,dat

18、atype x)if(sp-top=MAX-1) printf(n Stack is full!); return 0; sp-top+; /*栈顶指针加栈顶指针加1*/ sp-datasp-top=x; /*数据元素入栈数据元素入栈*/ return 1; 算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 4出栈。出栈。pop(s)当栈当栈s不空，从栈中删除栈顶元素。不空，从栈中删除栈顶元素。 void pop(stack *sp,datatype *x) if(empty(s) printf(n Stack is free!); else *x=sp-datasp-top;

19、/*数据元素出栈数据元素出栈*/ sp-top-; /*栈顶指针减栈顶指针减1*/算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 5取栈顶元素。取栈顶元素。get (s) 若栈若栈s不空，取栈顶元素作为返回值。不空，取栈顶元素作为返回值。datatype get(stack *sp) if(empty(sp) printf(n Stack is free!); else return(sp-datasp-top); /*返回栈顶数据元素返回栈顶数据元素*/ 算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 数据结构数据结构 typedef int datatype

20、;void transfer(int n,int r)stack s; datatype x; init(s); while(n) push(s,n%r); n=n/r; while (!empty(s) pop(s,x); printf(%d,x); #define MAX 16void transfer (int n,int r)int sMAX,top;int x;top=0;while(n)s+top=n%r;n=n/r;while(top!=0)x=stop-;printf(%d,x); 数据结构数据结构 typedf int datatype; int fact(int n) st

21、ack s;datatype x;int m=1; init(s); if(n=0|n=1)m=1; else while(n1) push(s,n);n-; while(!empty(s) pop(s,x); m=m*x; return m; a) 调用函数#define MAX 20 int fact(int n) int sMAX,top=0,x,m=1; if(n=0|n=1)m=1; else while(n1) s+top=n;n-; while(top!=0) x=stop-;m=m*x; return m; b)一维数组 数据结构数据结构 数据结构数据结构 数据结构数据结构 #

22、define MAX 50float calcul(char *b) /*得到后缀表达式*/float s1MAX,d; char c=*b+; /*取表达式第1个字符*/ int i=0, t=0,top=0; while(c!=) d=c-0; /*字符转换为数值*/ if(c=0&cf=qp-r=0;算法的时间复杂度为算法的时间复杂度为O(1) 队列的顺序存储结构定义队列的顺序存储结构定义#define MAX 队列中允许存放元素的最大个数队列中允许存放元素的最大个数+1typedef 元素类型元素类型 datatypetypedef struct datatype dataMA

23、X; /*队列的数据元素队列的数据元素*/ int f,r; /*队列的头和尾的下标位置队列的头和尾的下标位置*/ queue; /*队列的结构类型队列的结构类型*/queue q,*qp; /*队列变量队列变量q和指针变量和指针变量qp*/ 数据结构数据结构 queue 2判队空。判队空。empty(q)若队空返回为若队空返回为1，否则返回为，否则返回为0。int empty(queue *qp)if(qp-f=0 & qp-r=0) return 1; else return 0;算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 queue 3入队。入队。insert

24、(q,x) 在队列在队列q中插入一个元素中插入一个元素x到队尾。到队尾。void insert(queue*qp,datatype x)if(qp-r=MAX-1)printf(“队满队满”); /*队满判断队满判断*/ elseif(qp-f=0&qp-r=0) qp-f=+qp-r; /*空队，队首队尾加空队，队首队尾加1*/ else qp-r+; /*队尾加队尾加1*/ qp-dataqp-r=x; /*入队元素入队元素*/算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 queue 4出队。出队。delete(q,x) 删除队列首元素，可以返回其值。删除队列首元素，可以返回其值。void delete(queue*qp,datatype *x)if(empty(qp)printf(“队空队空”); /*判队空判队空*/ else*x=qp-dataqp-f; /*队首元素赋给指定变量队首元素赋给指定变量*/ if(qp-f=qp-r) /*队首等于队尾，队列只有一个元素队首等于队尾，队列只有一个元素 */ qp-f=qp-r=0; /*初始化初始化*/ else qp-f+; /*队首加队首加1 */ 算法的时间复杂度为算法的时间复杂度为O(1) 数据结构数据结构 queu