c从队头入队，d从队尾入队-中国教育在线.ppt

数据结构 重难点串讲;第一章概论;重难点导航;;第二章 线性表;重难点导航;重难点剖析;其中，L为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公式为： LOC(ai+1)=LOC(a1)+(i-1)*L;顺序存储结构的特点： （1）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致； 2）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被称为随机存取法，使用这种存取方法的存储结构被称为随机存储结构。;在线性表L中第i个数据元素之前插入数据元素e int ListInsert(SQ_LIST *L,int i,EntryType e) { if (L-length==LIST_MAX_LENGTH) return ERROR; //检查是否有剩余空间 if (i1||iL-length+1) return ERROR; //检查i值是否合理 for (j=L-length-1;j=i-1;i++) //将线性表第i个元素之后的所有元素向后移动 L.-item[j+1]=L-item[j]; L-item[i-1]=e; //将新元素的内容放入线性表的第i个位置， L-length++; return OK; };插入算法的分析 假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为： ;将线性表L中第i个数据元素删除 int ListDelete(SQ_LIST *L,int i,EntryType *e) { if (IsEmpty(L)) return ERROR; //检测线性表是否为空 if (i1||iL-length) return ERROR; //检查i值是否合理 *e=L-item[i-1]; //将欲删除的数据元素内容保留在e所指示的存储单元中 for (j=i;j=L-length-1;j++) //将线性表第i+1个元素之后的所有元素向前移动 L-item[j-1]=L-item[j]; L-length--; return OK; };删除算法的分析 在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为： 分析结论 顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑。;线性表的链式存储结构 线性表的链式存储结构是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线性表（a,b,c,d），可用下图2-2所示的形式存储： ;图2-2 线性表链式存储结构示意图;链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为顺序存取方式。;在C语言中，实现线性表的链式存储结构的类型定义 typedef strcut node{ //结点类型 EntryType item; struct node *next; }NODE; typedef struct{ //链表类型 NODE *head; }LINK_LIST;;求链表L的长度 int ListLength(LINK_LIST L) { NODE *p; int len; for(p=L.head, len=0;p-next==NULL; p=p-next,len++); return(len); };在链表L中第i个数据元素之前插入数据元素e int ListInsert(LINK_LIST *L,int i,EntryType e) { NODE *p,*s; int j; if (i1||iListLength(L)+1) return E