请勿删除谢谢合作.PPTVIP

2. 1 线性表的概念 2.1 线性表的概念 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 插入后,线性表长度是L.length+1, 线性表为 (a1, a2, a3,…, ai-1 , e, ai,,… aL.length ) 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 1、线性表的概念 2.2 顺序存储和实现 插入后,线性表长度是L.length+1, 线性表为 (a1, a2, a3,…, ai-1 , e, ai,,… aL.length ) 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.2 顺序存储和实现 2.3 链式存储和实现 2.3.1 线性链表 status Create_L(LinkNode L) /*建立带头结点的单链表的算法*/ { } void Insert_L(LinkNode L,elemtype x, int i) { p=Get_L(L,i-1); if (p==NULL) return(0); s=(LinkNode)(malloc(sizcof(LNode)); s-data=x; s-next=p-next; p-next=s; return(1); } q=p-next; p-next=q-next; free(q); statuse Delete_L(LinkNode L, int i) { p=Get_L (L,i-1); if(p==NULL||p-next==NULL) return(0); q=p-next; p-next=q-next; free(q); return(1); } 2. 3.2 循环链表 2. 3.2 循环链表 2.3.3 双向链表 2.5 双向链表 本章学习了线性表的顺序存储结构——顺序表，链式存储结构,线性链表,循环链表, 双向链表，以及在这两种存储结构下如何实现线性表的基本操作。这里再一次需要强调：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构和基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表，如何在计算机上实现线性表的操作。我们已经看到，在不同的存储结构下，线性表的同一操作的算法是不同的，在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。对于某一实际问题，如何选择合适的存储结构，如何在某种存储结构下实现对数据对象的操作，我们要通过数据结构课程的学习，很好地理解各种存储结构是如何存储和表达数据对象的有关信息的，各种存储结构下操作的特点。为实际问题的程序设计打下坚实的基础。 第二章 线性表 删除位置 移动元素个数 1?????????????????????????n-1 删除算法时间复杂度取决于移动元素的个数，移动元素的个数不仅与表长有关，而且与删除位置有关。 a1 a2 ai-1 ai ai+1 an 0 1 i-1 i-2 n-1 . . 三、算法时间复杂度分析 2??????????????????????? n-2 …???????????????????????… i???????????????????????? n-i n-1?????????????????????? 1 …????????????????????????… 2、删除算法的时间复杂度分析 第二章 线性表 由此可见·在顺序表中删除一个元素 ，平均要移动表的一半元素。·表长为n的顺序表，删除