[理学]课件c语言：数据结构Ch_2 线性表.ppt

顺序存储结构的优缺点 优点 逻辑相邻，物理相邻 可随机存取任一元素 存储空间使用紧凑 缺点 插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配，利用不充分 表容量难以扩充 作业 1.设有一个线性表(e0,e1,…,en-2,en-1)存放在一个一维数组A[Size]中的前n个数组单元中。请编写一个函数将这个线性表原地逆置，即将数组的前n个单元内容置换为(en-1,en-2,…,e1,e0) 、 2. 2.11 3. 2.12 实现 单链表的插入 第一种情况：在第一个结点前插入 第二种情况：在链表末尾插入 第三种情况：在链表中间插入 删除 第一种情况: 删除表中第一个元素 第二种情况: 删除表中或表尾元素 ① ② ③ ④ s ⑤ p p x a 单链表的插入运算 INSERT(linklist *L,datatype x,int i;) { linklist *p; int j; j＝i-1; p＝GET(L,j); if (p==NULL) printf(“error\n”); else INSERTAFTER(p,x); } 删除后继节点 ① ② ③ 存储池 r p 删除后继结点 DELETEAFTER(linklist *p) { linklist *r; r＝p-next; p-next＝r-next; free(r); } ? 删除运算 DELETE(linklist *L,int i) { linklist *p; int j; j＝i-1; p＝GET(L,j); if((p!=NULL)(p-next!=NULL)) DELETEAFTER(p); else printf(“error\n”); } （插入前） （插入后） 在单链表中删除含ai的结点 a1 a2 ∧ an 图2.7 带头结点的单链表 L (a)非空表 (b)空表 在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针。 单链表的头指针指向头结点。 若线性表为空表，则头结点的指针域为空。 L 单链表操作的实现 GetElem_L(L, i, e) // 取第i个数据元素 ListInsert_L(L, i, e) // 插入数据元素 ListDelete_L(L, i, e) // 删除数据元素 CreateList_L(L, n) // 生成含 n 个数据元素的链表 L 线性表的操作GetElem_L(L, i, e) 在单链表中的实现: 21 18 30 75 42 56 ∧ p p p j 1 2 3 因此，查找第 i 个数据元素的基本操作为：移动指针，比较 j 和 i。 单链表是一种顺序存取的结构，为找第 i 个数据元素，必须先找到第 i-1 个数据元素。 令指针 p 始终指向线性表中第 j 个数据元素。 Status GetElem_L(LinkList L, int i, ElemType e) { // L是带头结点的链表的头指针，以 e 返回第 i 个元素 p = L-next; j = 1; // p指向第一个结点，j为计数器 while (p ji) { p = p-next; ++j; } // 顺指针向后查找，直到 p 指向第 i 个元素或 p 为空 if ( !p || ji ) return ERROR; // 第 i 个元素不存在 e = p-data; // 取得第 i 个元素 return OK; } // GetElem_L 算法时间复杂度为: O(ListLength(L)) ai-1 线性表的操作 ListInsert(L, i, e) 在单链表中的实现： 有序对 ai-1, ai 改变为 ai-1, e 和e, ai e ai ai-1 因此，在单链表中第i个结点之前进行插入的基本操作为: 找到线性表中第i-1个结点，然后修改其指向后继的指针。 可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。 Status ListInsert_L(LinkList L, int i, ElemType e) { // L 为带头结点的单链表的头指针，本算法 // 在链表中第i 个结点之前插入新的元素 e p = L