数据结构之线性表2.pptxVIP

一、单链表; 用一组地址任意的存储单元存放线性表中的数据元素。;; Typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域 } LNode, *LinkList; ;三、单链表操作的实现;; 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i ; Status GetElem_L(LinkList L, int i, ElemType e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 } // GetElem_L;ai-1; 因此，在单链表中第 i 个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。; Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L;s = new LNode; // 生成新结点 s-data = e; s-next = p-next; p-next = s; // 插入 return OK;; Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e } // LinstInsert_L;有序对ai-1, ai 和 ai, ai+1 改变为 ai-1, ai+1; 在单链表中删除第 i 个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。; Status ListDelete_L(LinkList L, int i, ElemType e) { // 删除以 L 为头指针(带头结点)的单链表中第 i 个结点 } // ListDelete_L;void ClearList(L) { // 将单链表重新置为一个空表 while (L-next) { p=L-next; L-next=p-next; } } // ClearList;如何构造单链表？;操作步骤：;void CreateList_L(LinkList L, int n) { // 逆序输入 n 个数据元素，建立带头结点的单链表 } // CreateList_L;一、单链表;回顾 2.1 节中第二个例子的算法，看一下当线性表分别以顺序存储结构和链表存储结构实现时，它们的时间复杂度为多少？;则 ;1．初始化 LC 为空表；;; // La 和 Lb 均不空，i = j = 1, k = 0 GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) { // 将 ai 插入到 Lc 中 ListInsert(Lc, ++k, ai); ++i; } else { // 将 bj 插入到 Lc 中 ListInsert(Lc, ++k, bj); ++j; };;void MergeList(List La, List Lb, List Lc) { InitList(Lc); i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb); while ((i = La_len) (j = Lb_len)) { GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) { ListInsert(Lc, ++k, ai); ++i; } else { ListInsert(Lc, ++k, bj); ++j; } } … …;;用上述定义的单链表实现线性表的操作时， 存在的问题：; 重新定义线性链表的类型：;五、带头尾指针结点的线性链表类型;typedef struct { // 头结点类型 Link head, tail; // 分别指向头结点和