二章线表.PPTVIP

第二章 线性表 2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 线性表的应用：一元多项式的表示及相加 例2：学生健康情况登记表如下： 线性表的抽象数据类型的定义： ADT List{ 数据对象:D={ai |ai∈ElemSet,i=1,2,…,n,n≥0} 数据关系:R1={ai-1,ai| ai-1,ai ∈D,i=2,…,n} 基本操作: InitList(L) 操作结果：构造一个空的线性表L。 DestroyList(L) 初始条件：线性表L已存在。 操作结果：销毁线性表L。 ListInsert(L,i,e) 初始条件：线性表L已存在,1≤i≤ListLength(L)+1. 操作结果：在L中第i个位置之前插入新的数据元素e。 ListDelete(L,i,e) 初始条件：线性表L已存在且非空,1≤i≤ListLength(L)+1. 操作结果：删除L的第i元素，并用e返回其值，L长度减1。 … } 单链表示意图 插入算法： Status ListInsert(LinkList L,int I,ElemType e){ p=L;j=0; while (pji-1){p=p-next;++j;} //寻找第i-1个结点 if (!p||ji-1) return ERROR; //i小于1或者大于表长 s=(LinkList)malloc(sizeof(LNode));//生成新结点 s-data=e;s-next=p-next; //插入L中 p-next=s; return OK; } 删除结点的算法： Status ListDelete(LinkList L,int I,ElemType e){ p=L;j=0; while (p-next ji-1){//寻找第i个结点，并令p指向其 //前趋 p=p-next;++j; } if (!(p-next)||ji-1) return ERROR;//删除位置不合理 q=p-next;p-next=q-next; //删除并释放结点 e=q-data;free(q); return OK; } 在带头结点单链表L中第i个位置之前插入元素e： … ai-1 ai … p j = 0 a1 an ^ L 在带头结点单链表L中第i个位置之前插入元素e： … ai-1 ai … j = 1 a1 an ^ p L 在带头结点单链表L中第i个位置之前插入元素e： p j = … … ai-1 ai … a1 an ^ L 在带头结点单链表L中第i个位置之前插入元素e： j = i-1 … ai-1 ai … a1 an ^ p L … ai-1 ai … a1 an ^ p e s L 关键语句： s=(LNode *)malloc(sizeof(LNode)); s-data = e; s-next = p-next; p-next = s; 删除元素b： a b p c data next … … b 三、单链表的删除 a b p c data next … … b 删除元素b： 三、单链表的删除 a b p c data next … … b 用C语言语句描述为： p-next=p-next-next; 删除元素b： 三、单链表的删除 删除元素b并释放之： a b p c data next … … b 步骤1：将b的地址记录下来 即：q=p-next; q a b p c data next … … b 删除元素b并释放之： 步骤2：让p-next指向b后第一个结点 即：p-next=q-next; q a b p c data next … … b 删除元素b并释放之： q 步骤3：释放b结点 即：free(q