《算法与数据结构》教学课件-第2章 线性表--C语言描述（第2版）张乃孝编著汇.ppt

张乃孝 算法与数据结构——C语言描述 算法2.4 顺序表的插入int insertPre_seq( PSeqList palist, int p, DataType x ) 算法2.5 顺序表的删除 int delete_seq( PSeqList palist, int p ) 2.2.3 分析与评价 在有n个元素的线性表里，在下标为i（第i+1个）的元素之前插入一个元素需要移动n - i 个元素；删除下标为i（第i+1个）的元素需要移动n - i - 1个元素。如果在下标为i的位置上插入和删除元素的概率分别是Pi和Pi’，则插入时的平均移动数是： n mi=?(n-i)pi i=0 删除的平均移动数是： n-1 md=?(n-i-1)pi’ i=0 所以顺序表的插入和删除操作的时间代价为O(n)。 类似地，在顺序表中进行定位(locate_seq)操作，则要依次与表中元素进行比较，当定位的概率平均分布在所有元素上时，一次定位平均需要和n/2个元素进行比较，其时间代价为O(n)。 算法2.4 顺序表的插入int insertPre_seq( PSeqList palist, int p, DataType x ) 算法2.5 顺序表的删除 int delete_seq( PSeqList palist, int p ) ?  ? LinkList llist; llist是LinkList类型的变量，它指向单链表中的第一个结点，如图2.7(a)所示。当单链表为空表时，llist的值为NULL。 算法2.6 创建空单链表LinkList createNullList_link( void ) /* 创建一个带头结点的空链表 */ { LinkList llist; llist = new struct Node ; /* 申请表头结点空间 */ if( llist != NULL ) llist-link = NULL; else cout”Out of space!”endl; return (llist); } 算法2.7 判断单链表是否为空 int isNullList_link( LinkList llist ) //判断带头结点的单链表llist是否是空链表 { return (llist-link == NULL); } 算法2.8 在单链表中求某元素的存储位置 PNode locate_link(LinkList llist,DataType x) // 在带有头结点的单链表llist中, // 找第一个值为x的结点存储位置 { PNode p; if (llist==NULL) return(NULL); p = llist-link; while( p != NULL p-info != x ) p = p-link; return (p); } 算法2.9 单链表的插入 int insertPost_link(LinkList llist,PNode p,DataType x) // 在带头结点的单链表llist中, // p所指结点后面插入元素x { PNode q = (PNode)malloc( sizeof( struct Node ) ); /* 申请新结点 */ if( q == NULL ) { printf( Out of space!!!\n); return(0); } else { q-info=x; q-link=p-link; p-link=q; return(1); } } int insertPre_link(LinkList llist,PNode p,DataType x) //在p所指前面插入x，首先要找到p所指结点的前驱结点p1 算法2.10 在单链表中求p所指结点的前驱结点 PNode locatePre_link(LinkList llist,PNode p){ PNode p1; if(llist==NULL) return(NULL); p1=llist; while( p1!=NULL p1-link!=p ) p1=p1-l