第2讲 线性表及其顺序存储

数据结构课程的内容逻辑结构唯一存储结构不唯一运算的实现依赖于存储结构第2讲线性表及其顺序存储2.1线性表2.2顺序表A=（a1,a2,…ai-1，ai,ai＋1

，…,an）2.1

线性表1.定义：n个（n≥0）数据元素(结点)的有限序列n=0时称为数据元素开始结点ai的直接前驱ai的直接后继下标，是元素的序号，表示元素在表中的位置n为元素总个数，即表长空表终端结点线性表的特性：逻辑结构是线性结构除开始结点外，任何一个结点有且仅有一个前驱除终端结点外，任何一个结点有且仅有一个后继其中n称为线性表的表长说明：(a1，a2，…an)其中数据元素ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例：26个英文字母组成的英文表

（A,B,C,D,……,Z）学号姓名性别年龄班级2001011810205于春梅女182001级电信016班2001011810260何仕鹏男182001级电信017班2001011810284王爽女182001级通信011班2001011810360王亚武男182001级通信012班……………例：学生情况登记表数据元素都是学生记录;元素间关系是线性；表长为4数据元素都是字母;元素间关系是线性；表长为26同一线性表中的元素必定具有相同特性2.线性表上的运算置一个空表建一个线性表求表长查找某个元素插入一个元素删除一个元素拆分线性表合并排序…2.2顺序表2.2.1顺序表的基本概念及描述2.2.2顺序表的实现2.2.1顺序表的基本概念及描述

——线性表的顺序存储称为顺序表1、顺序表的定义

用一组连续的存储单元（地址连续）依次存放线性表的各个数据元素。即利用数组技术存放元素。2、顺序表的结点地址计算设首元素a1的存放地址为location(a1)（称为首地址），设每个元素占用存储空间（地址长度）为len字节，则表中任一数据元素的存放地址为：

loction(ai)=loction(a1)+len*（i-1）(1≤i≤n)

若首元素为a0：

loction(ai)=loction(a0)+len*i(0≤i≤n-1)

（参见顺序表存储结构示意图）顺序表存储结构示意图a1a2……aiai+1……an

地址内容元素在数组中的下标0i-11n-1空闲区ilenloction(a1)=bb+lenb+(i-1)lenb+(n-1)lenb+(MAX-1)lenMAX-1一个一维数组Ｍ，下标的范围是０到９，每个数组元素用相邻的５个字节存储。存储器按字节编址，设存储数组元素Ｍ[０]的第一个字节的地址是9８，则Ｍ[３]的第一个字节的地址是

113例1因此：loction(M[3])=98+5×3=113解：地址计算通式为：loction(ai)=loction(a0)+len*i1、顺序表数据类型的定义(1)定义数组的体积(最多允许的元素个数)#defineMAXSIZE100(2)数据元素类型定义为datatype如：处理学生信息typedefstruct{intn;charname[20];ints;}datatype;如：处理inttypedefintdatatype;2.2.2顺序表的实现(3)顺序表的类型定义typedefstruct{datatypea[MAXSIZE];/*存放线性表元素的数组*/

intsize;/*表示a中实际存放元素个数(表长)*/}sequence_list;/*顺序表的数据类型sequence_list*/(4)顺序表变量的定义sequence_listslt;

/*slt为顺序表变量*/sequence_list*lp;/*lp为顺序表指针变量*/结构体变量slta(数组)size(变量)slt.a[i]slt.size结构指针lpa(数组)size(变量)lp->a[i]lp->size本课堂顺序表的存储结构的C语言描述如下：#defineMAXSIZE100typedefintdatatype;typedefstruct{datatypea[MAXSIZE];intsize;}sequence_list;即定义相应运算的C语言函数。定义函数要确定：函数名形参返回值传入量传出量出错处理函数exit(1);/*返回OS,告知OS程序非正常结束，该函数定义在stdlib.h中*/2、顺序表的算法实现算法2.1初始化——建立一个空表空表的表长为0，使顺序表变量中的size为0。函数形参：须初始化顺序表的地址返回值：无算法实现：

voidinit(sequence_listlp){lp->size=0;}a(数组)size(变量)lp0算法2.2在表尾插入元素即在数组的size位置插入元素，表长增1。函数形参：指定顺序表的地址，插入元素返回值：无算法实现：

voidappend(sequence_listlp,datatypex){if(lp->size==MAXSIZE){printf("顺序表是满的!");exit(1);}lp->a[lp->size]=x;lp->size++;}

共size个元素01……size-1size……x算法2.3打印表中每个元素遍历整个顺序表，输出元素值。函数形参：指定顺序表变量返回值：无算法实现：

voiddisplay(sequence_listslt){inti;if(!slt.size)printf("\n顺序表是空的!");elsefor(i=0;i<slt.size;i++)printf("%5d",slt.a[i]);}算法2.4判顺序表是否为空表判断表长是否为0。函数形参：指定顺序表变量返回值：

1表示空,0表示非空算法实现：

intempty(sequence_listslt){ returnslt.size==0;}

遍历顺序表，查找与给定值x相同的元素，找到后返回元素的下标值，没找到返回-1。函数形参：指定顺序表变量被找元素值返回值：若找到——下标值若未找到——-1

遍历查找的范围01……size-1……算法2.5顺序表中查找指定值的元素intfind(sequence_listslt,datatypex){inti;

for(i=0;i<slt.size;i++)

if(slt.a[i]==x)returni;

return-1;

}

若datatype是结构类型，不能用“==”直接整体比较，应逐一比较结构中每个成员算法实现：

返回序号为i的元素值。函数形参：指定顺序表变量取元素值的序号返回值：序号为i的元素值i的有效范围01……size-1……算法2.6取得顺序表中序号为i的元素值

datatypeget(sequence_listslt,inti){if(i<0||i>=slt.size)/*查找位置不正确*/{printf("\n指定位置的结点不存在!");exit(1);}elsereturnslt.a[i];}算法实现：

顺序表的插入运算是将一个值为x的结点插入到顺序表的第i个位置0≤i≤n，即将x插入到ki-1和ki之间，如果i=n，则表示插入到表的最后，一般地可表示为： 插入前：{k0,k1,…,ki-1,ki,…,kn-1}

插入后：{k0,k1,…,ki-1,x,ki,…,kn-1}

插入过程的图示见下图：

kik0k1ki-1kn-1k0k1ki-1kn-1xki后移开始位置后移结束位置插入前插入后顺序表的插入运算

在顺序表下标为i（0<=i<=size)

的位置插入一个新的数据元素x。使长度为size的顺序表长增1。

元素可插入位置(0~size)0…i…size-1sizex

从表尾开始到下标i的元素依次向后移一位算法2.7在顺序表的i位置上插入x值返回值：无函数形参：指定顺序表的地址，插入元素值，

插入的位置（下标：0~size）

voidinsert(sequence_listlp,datatypex,inti){intj;if(lp->size==MAXSIZE)/*判表满*/{printf("\n顺序表是满的!没法插入!");exit(1);}if(i<0||i>lp->size)/*判插入位置不对*/ {printf("\n指定的插入位置不存在!");exit(1);}for(j=lp->size-1;j>=i;j--)/*从后往前元素后移*/

lp->a[j+1]=lp->a[j];lp->a[i]=x;lp->size++;/*插入并表长增1*/}插入算法实现：

元素可插入位置(0~size)0…i…size-1sizex

从表尾开始到下标i的元素依次向后移一位k0k1…ki…kn-1…移动n-i次插入位置移动次数

0n最坏O(n)

1n-1……n-11n0最好O(1)

in-i插入算法分析：

可能的插入位置为i=0,1,…,n共n+1个位置按等概率考虑,则插入概率：pi=1/(n+1)平均移动次数：顺序表插入算法平均约需移动一半元素，时间复杂度为O(n)顺序表的删除运算

顺序表的删除操作是指删除顺序表中的第i个结点，0≤i≤n-1，一般地可表示为：删除前：{k0,k1,…,ki-1,ki,ki+1,,…,kn-1}

删除后：{k0,k1,…,ki-1,ki+1,…,kn-1}

删除过程的图示见下图：kik0k1ki-1kn-1k0k1ki-1kn-1ki+1前移结束位置前移开始位置删除前删除后ki+1在顺序表中删除下标为i（0<=i<=size-1)

的元素。使长度为size的顺序表长减1。算法2.8删除顺序表的i位置上元素返回值：无函数形参：指定顺序表的地址，删除元素的位置（下标：0~size-1）

删除元素位置(0~size-1)0…i…size-1size删除

从下标i+1开始到表尾的元素依次向前移一位

voiddele(sequence_listlp,inti){intj;if(lp->size==0)/*判表为空*/{printf("\n顺序表是空的!");exit(1);}if(i<0||i>=lp->size)

)/*判删除位置不对*/{printf("\n指定的删除位置不存在!");exit(1);}for(j=i+1;j<=lp->size-1;j++)/*元素前移*/

lp->a[j-1]=lp->a[j];lp->size--;/*表长减1*/}删除算法实现：

删除元素位置(0~size-1)0…i…size-1size删除

从下标i+1开始到表尾的元素依次向前移一位k0k1…kiki+1…kn-1…移动n-i-1次删除位置移动次数

0n-1最坏O(n)

1n-2……n-21n-10最好O(1)

in-i-1删除算法分析：

可能的删除位置为i=0,1,…,n-1共n个位置按等概率考虑,则删除概率：pi=1/n平均移动次数：顺序表删除算法平均约需移动一半元素。时间复杂度为O(n)（1）voidreverse(sequence_list*lp)

将顺序表L就地倒置，即借助于O（1）的辅助空间。（2）voidsprit(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)

将有序顺序表L1分裂成两个线性表L2与L3，L2由表中所奇数组成，L3由所有偶数组成。顺序表上的一些其它常见算法（3）voidmerge(sequence_lsit*l1,sequence_list*l2,sequence_list*l3)[见顺序表应用]

将有序顺序表L1与L2合并成有序顺序表L3。元素类型：typedefstruct{intnum;/*学生学号*/charname[20];/*学生姓名*/intscore;/*成绩*/}datatype;建表要求：按输入顺序依次建表,输入学号为负时结束函数形参：被建顺序表地址返回值：无建立顺序表voidCreate(sequence_listslt)/*建立学生结点顺序表*/{datatypee;inti=0;/*i为计结点个数变量*/while(1){printf(“\nEnternewstudent:”);scanf(“%d”,&e.num);if(e.num<0)break;/*若学号值为负结束*/getchar();/*跳过输入学号后的回车换行*/gets();/*已是地址,前不要加&符*/scanf(“%d”,&e.score);slt->a[i]=e;i++;}slt->size=i;/*表长就是结点数*/}运算实现：优点：(1)逻辑结构上相邻的数据元素，其物理位置也是相邻的