第2章 数据结构-线性表_1_顺序表

null第2章 线性表第2章 线性表2.1 线性表的定义和运算2.1 线性表的定义和运算一、线性表的定义：一、线性表的定义：1、定义： 线性表 L是由n个元素a1，a2，…，an组成的有限序列。记作L=(a1,a2, …,an) 注：（1）n>=0为表长； （2）n=0时为L空表；记作L=（） 如：字母表{A,B,C,…,Z} 数字表（0,1,2,3,…,9） （同一表中，元素类型相同。）null2、特点： …, ai-1 , ai , ai+1 ,… ai-1 称为 ai 的直接前驱， ai+1称为 ai 的直接后继。 除首元素外每个元素有且仅有一个直接前驱； 除尾元素外每个元素有且仅有一个直接后继；二、线性表的基本运算 二、线性表的基本运算 （1）初始化 initial_list（L） 建空表； （2）求表长 list_length（L） （3）按序号取元素 get_element（L，i） （4）按值查找 list_locate（L，x）null（5）插入 list_insert（L，i，x） 在表中第i个位置上插入元素x； 1 ≤ i ≤ n+1 （6）删除 list_delete（L，i） 删除表中第i个元素; 1 ≤ i ≤ n2.2 顺序表2.2 顺序表一、线性表的顺序存储结构一、线性表的顺序存储结构1、定义： 假设有一个足够大的连续的存储空间，将线性表中的元素按其逻辑次序依次存储到这一存储空间中，由此方式存储的线性表称为顺序表。 null顺序表示意图n-1null2、类型描述 #define maxlen 100 typedef struct { elementtype data[maxlen]； int listlen； }seqlist； 变量定义，如：seqlist L，L1； 注：a：data[maxlen]的下标是0到maxlen-1； b：listlen是线性表的长度，最后一个元素下标是listlen-1；null3、顺序表的特点： 逻辑上相邻的元素，其存储地址也相邻； 即，可以随机存取元素。 二、顺序表运算的实现二、顺序表运算的实现1、初始化（建空表）： void initial_list（seqlist *L） { L->listlen=0; } 2、求表长： int list_length（seqlist L） { return L.listlen; }null3、按序号取元素： void get_element(seqlist L,int i,elementtype & x) { if (i<1||i>L.listlen) error(“序号错”); else x=L.data[i-1]; }null4、按值查找： （找到则返回其序号，否则返回0） int list_locate（seqlist L，elementtype x） { int i; for(i=0;ilistlen==maxlen) error(“溢出”); else if(i<1||i>L->listlen+1) error(“序号错误”); else { for(j=L->listlen-1;j>=i-1;j--) L->data[j+1]=L.data[j]; L->data[i-1]=x; L->listlen++; } }null插入算法的时间分析 在i=1，2，…，n+1时， 元素移动的次数分为n，n-1，…，0。 平均移动次数（等概率情况下）： (0+1+…+n)/(n+1)=n/2null6、删除： null分析： 首先判断顺序表是否为空以及i的取值； 可以则删除： (1)ai+1~an往前移一位； (2)表长-1; nullvoid list_delete（seqlist *L，int i） { int j; if (L->listlen<=0) error(“下溢出”); else if(i<1||i>L->listlen) error(“序号错误”); else { for (j=i; j<=L->listlen-1; j++) L->data[j-1]=L->data[j]; L->listlen--; } }null删除算法的时间分析： 在i=1，2，…，n时，元素移动的次数分别为n-1，n-2，…,0。 平均移动次数： (0+1+…+(n-1))/n=(n-1)/2三、顺序表的应用三、顺序表的应用 已知顺序表L递增有序，

设计

领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计

算法，在L中插入元素x，使得L依然递增有序。例null算法如下： void insert( seqlist *L,elementtype x ) { int i=L->listlen-1; if (i>=maxlen-1) error(“溢出”); else { while(i>=0 && L->data[i]>x) L->data[i+1]=L->data[i--]; L->data[i+1]=x; L->listlen++; } }解:null