资源描述：
《数据结构课件(c语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1第2章线性表2.1线性表的定义及其基本操作2.2线性表的顺序存储2.3线性表的链式存储2.4线性表的存储方式小结2线性结构是一种简单的数据结构。这种结构具有以下特点：在数据元素的非空有限集合中，有且只有一个“首”数据元素；有且只有一个“末”数据元素；除“首”数据元素外，其它数据元素有且只有一个直接前驱；除“末”数据元素外，其它数据元素有且只有一个直接后继。线性表属于线性结构的范畴，是最常用的数据结构。2.1线性表的定义及其基本操作3线性表（linearlist）是具有相同数据类型的n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n称为数
2、据元素的个数或线性表的长度，当n=0时称为空表，n>0时称为非空表。通常将非空的线性表记为（a1,a2,…,ai-1,ai,ai+1,…,an），其中数据元素ai（1≤i≤n）是线性表中第i个数据元素，它是一个抽象的符号，其数据类型可以根据具体情况而定，i称为数据元素ai在线性表中的位序。2.1.1线性表的定义例2.1大写英文字母表：（A,B,C,D……,Y,Z），其中每个字母为一个数据元素，A是字母序列的“首”数据元素，Z是字母序列的“末”数据元素，其它每个字母有且只有一个直接前驱和一个直接后继，这个序列是一个线性表。例2.2教师信息表，其中每位教
3、师的有关信息为一个数据元素，所有教师的信息集合构成一个线性表。52.1.2线性表的基本操作(1)InitList(*L):(2)InsItem(*L,i,item):(3)DelItem(*L,i):(4)ClearList(*L):(5)ListEmpty(*L):(6)LenList(*L):(7)LocItem(*L,item):(8)GetItem(*L,i,item):(9)GetPrior(*L,item,&prior):(10)GetNext(*L,item,&next):62.2.1顺序表的定义所谓顺序表，就是在内存中开辟一片连续的存
4、储空间，将线性表中数据元素按照数据元素之间的逻辑顺序依次存放其中，需注意的是该连续存储空间所能容纳的数据元素个数不得小于顺序表的长度。在顺序表中，逻辑关系相邻的两个元素在物理位置上也相邻。线性表的顺序存储结构很容易确定每个数据元素在存储单元中起始地址的相对位置：假设线性表中元素为（a1,a2,…,ai-1,ai,ai+1,…,an），设第一个元素a1的内存地址为LOC(a1)，而每个元素在计算机内占t个存贮单元,则第i个元素ai的首地址LOC(ai)为：LOC(ai)=LOC(a1)+(i-1)×t(其中1≤i≤n)2.2线性表的顺序存储7例2.3设
5、有顺序表S，其描述如下：typedefstruct{charno[10];charname[20];floatgrade[3];floataver;}Student;Studentt[30];线性表中每个数据元素所占存储单元为10*1+20*1+3*4+1*4=46，假设顺序表中第一个数据元素的存储地址为d，则第i个数据元素的存储地址为d+(i-1)×46。8由于顺序表的表长通常是可变的，因此可定义一个整型变量来记录表长，且需要定义一个足够大的数组来保存数据。#defineMAXSIZEmaxlentypedefintelemtype;typedef
6、struct{elemtypedata[MAXSIZE];intlen;/*顺序表的长度*/}Sequenlist;92.2.2顺序表的基本操作(1)初始化顺序表InitList(*L):算法说明:创建一个空的顺序表，将该顺序表的表长设为零。算法实现:Sequenlist*InitList(Sequenlist*L){L=(Sequenlist*)malloc(sizeof(Sequenlist));L–>len=0;return(L);}/*L为指向Sequenlist类型的指针变量*/10(2)在顺序表中插入数据元素InsItem(*L,i,it
7、em):intInsItem(sequenlist*L,inti,elemtypeitem)/*(*L).data[0]中存储表L的第一个数据元素a1*/{intj;if((*L).len>=MAXSIZE)/*表满，插入操作失败*/{printf(“Thelistisoverflow.”);returnNULL;}elseif((i<1)
8、
9、(i>(*L).len+1))/*插入位置设定不合适，插入操作失败*/{printf(“Positionisnotcorrent.”);returnNULL;}else{for(j=(*L).len-1
10、;j>=i-1;j--)(*L).data[j+1]=(*L).data[j];(*L).data[i-1]
