2.3.1单链表-删除操作（分析设计） 2.3.1单链表-创建操作 慰脍振作ListDelete_L(LinkList&L,intl,ElemType&e) .创建单链表CreateList_L((LinkList&L) 【设计恩略】 相关结点：a1、a和a, 。头插法 铺点的表示：引入指针变量山nk山istP 链表结点的指针娘是指向该塘点的直接后壁 新结点插入 当p指a时，a可用*(p->next)表示， 到线性表中的第1 a4可用*(p->next> 个结点之前. ① 关量步■： 了花时同！ e 花p推向a随减 p->nextNULL,则 0年道 ,思描法 a■D->net 8 ext =p->next->next; a□#aG 新结点插入 6IO 到线性表中最后1 {②p T(n)=0(n) 个结点之后， 47 回 e- 4W方 图 2.3.1单链表-头插法创建 2.3.1单链表-尾插法创建 ,头插法（算法2.11，P30) ,品描法 思想：每次将特插结点*s插入到第一个结点之前：当有头结点时， 思想：特输结点描入到最后一个结点之后。 特插结点也可视为描入到第0个结点（头结点）之后。 播入步丽：①获得最后一个结点的位置使即指向该储点 摇入步骤：以单链表中有头结点为例，单个结点的构造和蝴入步躁如 p->next =(LinkList)malloc(sizeof(LNode)); 下：①s=(LinkList)malloc(sizeof(LNode): ②scanf(&s->data);③s>next=L->next,④L->next=s 算法分新，由上可谱出每次描入一个结点所需的时间为0(1) 算法分析：要想扶取最后一个结点的位置，必须从头指针开始顺 式链撞套链麦的全部结点，该过四的时间复杂度是 ∴头插法创建单楚表的时间复杂度T()=0() ()。如果每次插入都按此 方法获取最后一个结点的位 知+一D一→ 置，则整个创魔算法的时间 复来度为T(n)=0(n2). 工 45/73 图 3 图 2.3.2循环链表 2.3.3静态链表 ■循环链表 ■静态链表(P31~34) ·问愿1 如何从一个结，旅出发，访问到能表中的全部结点？ ·问题： 循环表 ,若语言不支持指针类型，能有链式存储吗？ 可以借用语言中的数姐来表示能表—普态链衰 ·问愿2 数组元素（数据元素的值、描示器） 结点 如何在0(1)时间内由能表指针访问到第一个结燕和 最后一个站点？ ,类型定义 一头指针表示/尾指针表示 #define MAXSIZE 1000 typedef struct( ,与单链表在基本操作的实现上的差异 ElemType data; 如链表的创 int cur; 管代动态链表结点中的指针城 痛环结束泰件的判断：p--NULL>p一L )component,SLinkList[MAXSIZE]; 47 可图 图43/73 „ 删除操作ListDelete_L(LinkList &L, int i, ElemType &e) 【设计思路】 相关结点：ai-1、ai 和ai+1 结点的表示：引入指针变量LinkList p; ∵链表结点的指针域是指向该结点的直接后继 ∴当p指向ai-1时，ai 可用*(p->next)表示， ai+1可用*(p->next->next)表示 关键步骤： ①使p指向ai-1 结点 p->next≠NULL，则 ② q = p->next; ③ p->next = p->next->next; ④ free(q); 2.3.1 单链表–删除操作(分析设计) 耗时间！ T(n) =O(n) ai-1 ai p 1 ai+1 3 4 存储池 2 q 44/73 „ 创建单链表 CreateList_L(LinkList &L) „ 头插法 „ 尾插法 2.3.1 单链表–创建操作 新结点插入 到线性表中的第1 个结点之前. 新结点插入 到线性表中最后1 个结点之后. a1 s e L 1 2 s p 2 an ^ e ^ 1 3 p 45/73 „ 头插法(算法2.11, P30) 思想：每次将待插结点*s插入到第一个结点之前；当有头结点时， 待插结点也可视为插入到第0个结点(头结点)之后。 插入步骤：以单链表中有头结点为例，单个结点的构造和插入步骤如 下:① s = (LinkList)malloc(sizeof(LNode)); ② scanf(&s->data); ③ s->next = L->next; ④ L->next = s; 算法分析：由上可看出每次插入一个结点所需的时间为O(1) ∴头插法创建单链表的时间复杂度 T(n) = O(n) 2.3.1 单链表–头插法创建 a1 s e L 3 4 1 2 46/73 „ 尾插法 思想：待插结点插入到最后一个结点之后 。 插入步骤：① 获得最后一个结点的位置,使p指向该结点 ② p->next = (LinkList)malloc( sizeof(LNode)); ③ p = p->next; ④ scanf( &p->data ); ⑤ p->next = NULL; 算法分析：要想获取最后一个结点的位置，必须从头指针开始顺 着next链搜索链表的全部结点，该过程的时间复杂度是 O(n)。如果每次插入都按此 方法获取最后一个结点的位 置，则整个创建算法的时间 复杂度为T(n) = O(n2)。 2.3.1 单链表–尾插法创建 p 2 an ^ 3 p 1 e ^ 4 5 47/73 „ 循环链表 „ 问题1 如何从一个结点出发，访问到链表中的全部结点？ ——循环链表 „ 问题2 如何在O(1)时间内由链表指针访问到第一个结点和 最后一个结点？ ——头指针表示/尾指针表示 „ 与单链表在基本操作的实现上的差异 如链表的创建 循环结束条件的判断:p==NULL => p==L 2.3.2 循环链表 48/73 2.3.3 静态链表 „ 静态链表 (P31~34) „ 问题： „ 若语言不支持指针类型，能有链式存储吗？ 可以借用语言中的数组来表示链表——静态链表 数组元素(数据元素的值、指示器)——结点 „ 类型定义 #define MAXSIZE 1000 typedef struct{ ElemType data; int cur; //替代动态链表结点中的指针域 }component, SLinkList[MAXSIZE];