第2章 线性表.ppt

} } } /* end of while */ if (pb!=NULL) while(pb!=NULL) { p=(ploy *)malloc(sizeof(ploy)) ; p-coef=pb-coef ; p-expn=pb-expn ; p-next=NULL ; /* 生成一个新的结果结点并赋值 */ pc-next=p ; pc=p ; pb=pb-next ; } if (pa!=NULL) while(pa!=NULL) { p=(ploy *)malloc(sizeof(ploy)) ; p-coef=pb-coef ; p-expn=pa-expn ; p-next=NULL ; /* 生成一个新的结果结点并赋值 */ pc-next=p ; pc=p ; pa=pa-next ; } return (Lc) ; } 习 题 二 1 简述下列术语：线性表，顺序表，链表。 2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么? 3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素? 4 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解? 5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 6 写一求单链表的结点数目ListLength(L)的算法。 7 写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。 8 写一算法从一给定的向量A删除值在x到y(x≤y)之间的所有元素(注意：x和y是给定的参数，可以和表中的元素相同，也可以不同)。 9 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。 注意：C语言中数组的下标值是从0开始，第i个元素的下标值是i - 1 。 顺序存储的线性表的特点: 优点：表中任一结点的存取很方便，也能进行插入和删除操作。 缺点： (1) 插入和删除不方便。为保持连续存放，操作中需要移动大量元素。 (2) 会造成空间的浪费以及不易扩充。数组大小固定，对于处理长度变化较大的线性表时，分配数组大小不够，会造成溢出;分配大小太大，会造成空间浪费。 讲课时板书教案上的几种常见的指针操作。 讲课时板书教案上的几种常见的指针操作。 讲课时板书教案上的几种常见的指针操作。 算法描述2-8 ElemType Get_Elem(LNode *L ， int i) { int j ; LNode *p; p=L-next; j=1; /* 使p指向第一个结点 */ while (p!=NULL ji) { p=p–next; j++; } /* 移动指针p , j计数 */ if (j!=i) return(-32768) ; else return(p-data); /* p为NULL 表示i太大; ji表示i为0 */ } 移动指针p的频度： i1时：0次; i∈[1,n]：i-1次；in：n次。 ∴时间复杂度: O(n)。 (2) 按值查找 按值查找是在链表中，查找是否有结点值等于给定值key的结点? 若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。 算法描述 LNode *Locate_Node(LNode *L，int key) /* 在以L为头结点的单链表中查找值为key的第一个结点 */ { LNode *p=L–next; while ( p!=NULL p–data!=key) p=p–next; if (p–data==key) return p; else { printf(“所要查找的结点不存在!!\n”); retutn(NULL); } } 算法的执行与形参key有关，平均时间复杂度为O(n)。 3 单链表的插入 插入运算是将值为e的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。首先找到ai-1所在的结点p，然后生成一个数据域为e的新结点q，q结点作为p的直接后继结点。时间复杂