2.3.1单链表-头结点的引入 2.3.1单链表-插入操作（分析设计） ,播入振作ListInsertL(LinkList&L,tntl,ElemType e】 ,单链表中是否引入头结，点？ 【设计思路】 。无头站点 相关塘点：a,和a 儿D-国的 点的示：引入指针变量LinkList p; 空表时，L为NULL :能表结点的指针城是推向读姑旅的直捷后健 第一个结点无前驱结点，只能通过某指针变量来指向，如L: ∴，当p指向a时，a可用p->next)表示 其余结点均有前驱结点，放可通过其直接前配结点的ext城 关整步： 来指向，即->next; ①液p推向a:暗点> P 5 '如a·-F p≠NULL,则 ▣有头站点 分操作 ②s=(LinkList -0 空表时，L指向一结点（称为头结点） of(LNode)); e 第一个结点和其食结点均可线一表示为其直接前驱结点的 ®s->data=e; ④s->next=p->next ③ next城所指向的结点，即. ->next. p->next =s; 3773 回 3/3 T(n)=0(n) 图 2.3.1单链表-插入操作（分析设计） 2.3.1单链表插入操作（算法） .入摄作ListInsert_(L LinkList&L,intl,ElemType e) 【有头纳点的算法】 【设计恩席】 Status ListInsert(LinkList&L,inti,ElemType eX 桶关填点：a1和a /有头结点，无须对为1的横入位置作特躁处理 第点的衰示，引入指计变量LinkList p: p=L:j=0://对Pj初始化：多p为L的第j个结点 while(p!=NULL &j<i-1) 感表结京的指针是指南该结点的直后 p=p->next; j+ /1零找第-1个结点的位量 当p指向a1时，a可用(p->next)表示 关敏步源： 9 if(p==NULL II j>i-1) PNULL,则 正于 return ERROR; /川i小于1或大于表长 ②s=(LinkList)malloc 0 s=(LinkList)mallod(sizeof(LNode)/I生成新结点 if (s==NULL) (sizeof(LNode)); exit(OVERFLOW:/空间分配不成动，报幢返园 s>data=e 0 s>daa=写s>net=p->next入中 ③q=p->next p->next= ③p->next=5 return OK; s->next =q; 3/73 图 40y72 图 2.3.1单链表插入操作（算法） 2.3.1单链表插入操作（小结） 【无头铺点的算法】 Status ListInsert(LinkList &L int i,ElemType eX /无头俯点，须对为1的插入位量作特珠处理 ■链表操作的算法设计小结 if (i=1X s=(LinkList)malloc(sizeof(Node:/∥生R事铺点 ·采用画图法 Cown:1宅分不热：带运日 。先画初始状态 升金铁 s>data■e时s->net=山/瓶) ,画出结果状态 L=s; 。标出各操作步骤的次序 P二升精架的热线8集的粥a 次序的确定方法： ,根据操作步廉之间的依被关系 随意确定一种次序信惠的丢失 return OK; 在信息丢失前，增加操作步腰以暂存将要丢失的信意 游活结点和有头结在入祛上的不 。假设一些条件：有无头结点 图 42万 图37/73 „ 单链表中是否引入头结点？ „ 无头结点 空表时，L为NULL 第一个结点无前驱结点,只能通过某指针变量来指向，如L； 其余结点均有前驱结点，故可通过其直接前驱结点的next域 来指向，即……->next； „ 有头结点 空表时，L指向一结点(称为头结点) 第一个结点和其余结点均可统一表示为其直接前驱结点的 next域所指向的结点，即……->next。 2.3.1 单链表–头结点的引入 a1 a2 L an ^ a1 an ^ L 38/73 „ 插入操作ListInsert_L(LinkList &L, int i, ElemType e) 【设计思路】 相关结点：ai-1和ai 结点的表示：引入指针变量LinkList p; ∵链表结点的指针域是指向该结点的直接后继 ∴当p指向ai-1时，ai 可用*(p->next)表示 关键步骤： ①使p指向ai-1 结点 p≠NULL，则 ② s = (LinkList)malloc (sizeof(LNode)); ③ s->data = e; ④ s->next = p->next; ⑤ p->next = s; 2.3.1 单链表–插入操作(分析设计) 耗时间！ T(n) =O(n) ai-1 ai p 1 2 s e 3 分析操作 5 4 间的依赖关 系，确定操 作的次序！ 39/73 „ 插入操作ListInsert_L(LinkList &L, int i, ElemType e) 【设计思路】 相关结点：ai-1和ai 结点的表示：引入指针变量LinkList p; ∵链表结点的指针域是指向该结点的直接后继 ∴当p指向ai-1时，ai 可用*(p->next)表示 关键步骤： ①使p指向ai-1 结点 p≠NULL，则 ② s = (LinkList)malloc (sizeof(LNode)); ③ s->data = e; 3' q=p->next; ④ p->next = s; ⑤ s->next = q; 2.3.1 单链表–插入操作(分析设计) ai-1 ai p 1 2 s e 3 4 5 信息丢失： ai 的位置？ q 3' 随意给 出操作的 次序！ 40/73 【有头结点的算法】 Status ListInsert(LinkList &L, int i, ElemType e){ // 有头结点，无须对i为1的插入位置作特殊处理 p = L; j = 0; // 对p,j初始化; *p为L的第j个结点 while( p != NULL && j<i-1){ p = p->next; j++; // 寻找第i-1个结点的位置 } if( p == NULL || j>i-1) return ERROR; // i小于1或大于表长 s = (LinkList )malloc(sizeof(LNode)); // 生成新结点 if ( s == NULL ) exit(OVERFLOW); // 空间分配不成功，报错返回 s->data = e; s->next = p->next; // 插入L中 p->next = s; return OK; } 2.3.1 单链表–插入操作(算法) 41/73 【无头结点的算法】 Status ListInsert(LinkList &L, int i, ElemType e){ //无头结点，须对i为1的插入位置作特殊处理 if ( i==1){ s = (LinkList )malloc(sizeof(LNode)); // 生成新结点 if ( s == NULL ) exit(OVERFLOW); // 空间分配不成功，报错返回 s->data = e; s->next = L; // 插入到链表L中 L = s; // 修改链头指针L }else{ p = L; j = 1; // 对p,j初始化; *p为链表的第j个结点 …… //同有头结点算法的处理：①~⑤ } return OK; } 【思考】对比无头结点和有头结点在插入算法上的不同， 分析其中的原因。 2.3.1 单链表–插入操作(算法) 42/73 2.3.1 单链表–插入操作(小结) „ 链表操作的算法设计小结 „ 采用画图法 „ 先画初始状态 „ 画出结果状态 „ 标出各操作步骤的次序 次序的确定方法： „ 根据操作步骤之间的依赖关系 „ 随意确定一种次序Î信息的丢失 在信息丢失前，增加操作步骤以暂存将要丢失的信息 „ 假设一些条件: 有无头结点…