[工学]02-线性表.ppt

第二章 线性表 第二章 线性表 2.1 线性表的定义和运算 2.2 顺序表 2.3 链表 2.4 其它结构形式的链表 2.5 串 2.1 线性表的定义和运算 定义： 线性表L是由n个元素a1，a2，……，an组成的 有限 序列。 记作 L =（a1，a2，……，an） 其中n=0为表长；n=0时为L空表，记作L=（） 特性： A、只有一个第一个元素和一个最后一个元素； B、除第一个元素外其他元素有且仅有一个直接前趋（前驱）； C、除最后一个元素外其他元素有且仅有一个直接后继 元素ai的含义： 同一表中，元素类型相同。在不同的场合有不同的含义 例：字母表（A，B，C，D，……，Z）； 数字表（0，1，2，3，4，……，9）； 每月天数（31,29,31,30,31,30,31,31,30,31,30,31）; 2.1 线性表的定义和运算 运算： (1)初始化 initial_List(L)建立线性表的初始结构，即建空表 (2)求长度 List_length(L) 即求表中的元素个数 (3)按序号取元素 get_element(L,i) 取出表中序号为i的元素 (4)按值查找元素 List_locate(L,x) 取出指定值为x的元素，若存在则返回其地址；否则返回特殊值 (5)插入 List_insert(L,i,x) 在表L的第i个位置上插入值为x的元素( 1=i=n+1) (6)删除 List_delete（L,i）删除表L中序号为i的元素1=i=n 2.2 顺序表 存储结构： 顺序表类型描述 #define maxlen 100 //假设元素个数最大为100 typedef struct{ elementtype data[maxlen]; //存储表中元素的数组 int listlen; //表长度 } seqlist; 顺序表的特点：逻辑上相邻的元素，其存储地址也相邻。 2.2 顺序表 – 初始化、长度、按序号求元素、按元素找序号 运算实现： void initial_List（seqlist *L） { L-listlen=0; } int List_length（seqlist L）{ return L.listlen ; } void get_element（seqlist L，int i, elementtype x） { if（ i 1 || iL.listlen） error(“超出范围”); else x = L.data[i-1]; } int List_locate（seqlist L，elementtype x）{ int i; for (i=0; iL.listlen; i++) if (L.data[i]==x) return (i+1); return(0); } 2.2 顺序表 — 插入 void List_insert（seqlist *L，elementtype x，int i）{ int j; if （L-listlen==maxlen） error（“overflow”）; else if（i1||iL-listlen+1） error(“position 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++; } } 2.2 顺序表 — 删除 void List_delete(seqlist *L,int i){ int j; if (L-listlen=0) error