教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 【思考】对比无头结点和有头结点在插入算法上的不同，分析其中的原因。 6、删除ListDelete L(LinkList&L,inti,ElemType&e) 【设计思路】 相关结点：a-1、a和a+1 结点的表示：引入指针变量LinkList p; 9、0 链表结点的指针域指向该结点的直接后继 ai-1 ∴.当p指向a-1时，a可用*(p>next)表示，ai+ 可用*(p->next->next)表示 关键步骤：（如右图所示） ①找到a-的位置，即使p指向a-i结点，可参考GetElem L()的处理 p->next≠NULL(有待删除的结点)，则 ②q=p->next(记录待释放结点的位置) 3 p->next =p->next->next ④free(q) 注意：必须在③④前增加②步，否则在执行了③后要释放的结点无法标识。 【性能分析】 其时间消耗主要在①，其它为O1).T(n)=O) 7、创建单链表（带头结点）CreateList L(LinkList&L,intn) 【设计思路】 首先初始化单链表，而后根据结点输入的次序与其在线性表中的逻辑次序是否一致（正序） 或相反（逆序），决定是采用尾插法还是头插法，逐个将各结点依次插入到单链表中。 1)头插法 思想：每次将待插结点*s插入到第一个结点之前；当有头结点时，待插结点也可视 为插入到第0个结点（头结点）之后。 插入步骤：以单链表中有头结点为例，单个结点的构造和插入步骤如下 1s=(LinkList)malloc(sizeof(LNode))2 scanf(&s->data) ③s->next=L->next④L->next=s 算法分析：由上可看出每次插入一个结点所需的时间为O(1) ∴.头插法创建单链表的时间复杂度T(n)=O(n) 算法3带头结点，用头插法创建表 Status CreateList L(LinkList &L) ∥空链表的建立 L=(LinkList )malloc(sizeof(LNode)); ∥生成头结点 if (L==NULL exit(OVERFLOW); L->next NULL; ∥构造空表 ∥若是循环链表，则仅将上一语句政为：L->t=L:其余不变 bCycleFlag=1; ∥控制是否继续循环插入新结点 ∥循环插入新结点到头结点L之后 while(bCycleFlag){ scanf(&e)方 ∥输入待插的元素 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第9页程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 9 页 第 9 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 } 【思考】对比无头结点和有头结点在插入算法上的不同，分析其中的原因。 6、删除 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)表示 关键步骤：（如右图所示） ①找到 ai-1 的位置，即使 p 指向 ai-1 结点, 可参考 GetElem_L( )的处理 p->next≠NULL（有待删除的结点），则 ② q = p->next (记录待释放结点的位置) ③ p->next = p->next->next ④ free(q) 注意：必须在③④前增加②步，否则在执行了③后要释放的结点无法标识。 【性能分析】 其时间消耗主要在①,其它为 O(1) ∴T(n) = O(n) 7、创建单链表（带头结点）CreateList_L(LinkList &L, int n) 【设计思路】 首先初始化单链表，而后根据结点输入的次序与其在线性表中的逻辑次序是否一致（正序） 或相反（逆序），决定是采用尾插法还是头插法，逐个将各结点依次插入到单链表中。 1) 头插法 思想：每次将待插结点*s 插入到第一个结点之前；当有头结点时，待插结点也可视 为插入到第 0 个结点(头结点)之后。 插入步骤：以单链表中有头结点为例，单个结点的构造和插入步骤如下 ① s = (LinkList)malloc(sizeof(LNode)) ② scanf(&s->data) ③ s->next = L->next ④ L->next = s 算法分析：由上可看出每次插入一个结点所需的时间为 O(1) ∴头插法创建单链表的时间复杂度 T(n) = O(n) 算法 3 带头结点，用头插法创建表 Status CreateList_L( LinkList &L){ // 空链表的建立 L = (LinkList )malloc( sizeof( LNode)); // 生成头结点 if ( L == NULL ) exit(OVERFLOW); L->next = NULL; // 构造空表 // 若是循环链表，则仅将上一语句改为：L->next = L；其余不变 bCycleFlag = 1; // 控制是否继续循环插入新结点 // 循环插入新结点到头结点*L 之后 while(bCycleFlag){ scanf( &e ); // 输入待插的元素 ai-1 ai p 1 ai+1 2 3 4 存储池 q