资源描述：
《数据结构——使用c语言版朱战立 线性表.ppt》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、第2章线性表主要知识点线性表抽象数据类型顺序表单链表循环单链表循环双向链表静态链表设计举例2.1线性表抽象数据类型1.线性表的定义线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0,a1,…,an-1组成的线性结构。线性结构:2.线性表抽象数据类型数据:｛a0,a1,…,an-1｝,ai的数据类型为DataType操作:(1)ListInitiate(L)初始化线性表(2)ListLength(L)求当前数据元素个数(3)ListInsert(L,i,x)插入数据元素(4)ListDelete(L,i,x)删除数据元素(5)ListGet(L,i,x)
2、取数据元素｛a0,a1,…,an-1｝表示数据元素有次序关系,简称序列。2.2线性表的顺序表示和实现1.顺序表的存储结构实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。顺序表的存储结构如图所示顺序存储结构的线性表称作顺序表a0a1a2a3a4a5…listsize=6MaxSize-10123456其中a0,a1,a2等表示顺序表中存储的数据元素，list表示顺序表存储数据元素的数组，MaxSize表示存储顺
3、序表的数组的最大存储单元个数，size表示顺序表当前存储的数据元素个数。typedefstruct{DataTypelist[MaxSize];intsize;}SeqList;2.顺序表操作的实现（1）初始化ListInitiate(L)voidListInitiate(SeqList*L){L->size=0;//定义初始数据元素个数}（2）求当前数据元素个数ListLength(L)intListLength(SeqListL){returnL.size;}（3）插入数据元素ListInsert(L,i,x)intListInsert(SeqList*L,inti,DataType
4、x){intj;for(j=L->size;j>i;j--)L->list[j]=L->list[j-1];//依次后移L->list[i]=x;//插入xL->size++;//元素个数加1return1;}intListInsert(SeqList*L,inti,DataTypex) {intj; if(L->size>=MaxSize) {printf("顺序表已满无法插入!"); return0;} elseif(i<0
5、
6、i>L->size) {printf("参数i不合法!"); return0;} else{for(j=L->size;j>i;j--) L->lis
7、t[j]=L->list[j-1]; L->list[i]=x; L->size++; return1;}}（4）删除数据元素ListDelete(L,i,x)intListDelete(SeqList*L,inti,DataType*x){intj;*x=L->list[i];//保存删除的元素到x中for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];//依次前移L->size--;//数据元素个数减1return1;}intListDelete(SeqList*L,inti,DataType*x){intj;if(L->size<=0
8、){printf("顺序表已空无数据元素可删!");return0;}elseif(i<0
9、
10、i>L->size-1){printf("参数i不合法");return0;}else{*x=L->list[i];for(j=i+1;j<=L->size-1;j++)L->list[j-1]=L->list[j];L->size--;return1;}}（5）取数据元素ListGet(L,i,x)intListGet(SeqListL,inti,DataType*x){if(i<0
11、
12、i>L.size-1){printf("参数i不合法!");return0;}else{*x=L.l
13、ist[i];return1;}}3.顺序表操作的效率分析时间效率分析:算法时间主要耗费在移动元素的操作上T(n)=O(移动元素次数)而移动元素的个数取决于插入或删除元素的位置i.若i=size，则根本无需移动（特别快）；若i=0，则表中元素全部要后移（特别慢）；应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。设Pi是在第i个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素
