单链表的算法设计方法PPT课件

1、 以查找为基础的算法设计以查找为基础的算法设计按照按照条件进行结点查找条件进行结点查找; ;进行插入或者删除操作。进行插入或者删除操作。 4、单链表的算法设计方法、单链表的算法设计方法 单链表的算法设计是线性表链式存储结构算法设计的基单链表的算法设计是线性表链式存储结构算法设计的基础，是需要重点掌握的内容。这里总结一般的算法设计方法。础，是需要重点掌握的内容。这里总结一般的算法设计方法。1/17 【例例2-7】设计一设计一个个算法，删除算法，删除一个单链表一个单链表L中元素值中元素值最大最大的结点（的结点（假设假设最大值结点是最大值结点是唯一的）。唯一的）。Lmaxpmaxpre算法设计思路算

2、法设计思路maxpre- -next=maxp- -nextppre一对同步指针一对同步指针2/17void delmaxnode(LinkNode *&L) LinkNode *p=L-next，*pre=L，*maxp=p，*maxpre=pre; /开始时，开始时，p和和maxp指向开始结点，指向开始结点，pre和和maxpre指向头结点指向头结点 while (p!=NULL) if (maxp-datadata)/若找到一个更若找到一个更大大的结点的结点 maxp=p;/更改更改maxp maxpre=pre;/更改更改maxprepre=p;/p、pre同步后移同步后移一一

3、个结点个结点p=p-next; maxpre-next=maxp-next; /删除删除*maxp结点结点 free(maxp);/释放释放*maxp结点结点该算法的时间复杂度为该算法的时间复杂度为O(n)。查找查找最大值结点的前最大值结点的前驱结点驱结点*maxpre删除删除最大值结点并最大值结点并释释放空间放空间3/17 【例例2-8】有一有一个个带头结点的带头结点的单链表单链表L（至少有一（至少有一个个数据数据结点），设计结点），设计一个算法使其元素递增有序排列。一个算法使其元素递增有序排列。Lppre有序单链表有序单链表算法设计思路算法设计思路4/17void sort(LinkNod

4、e *&L) LinkNode *p，*pre，*q; p=L-next-next;/p指向指向L的第的第2个个数据结点数据结点 L-next-next=NULL;/构造只含一构造只含一个个数据结点的数据结点的有序有序表表 /第第1个结点和第个结点和第2个结点之间截断个结点之间截断Lp含一含一个数据结点的个数据结点的单单链表是有序单链表链表是有序单链表将将L拆拆分为两个部分分为两个部分5/17 while (p!=NULL) q=p-next;/q保存保存*p结点后继结点的指针结点后继结点的指针pre=L; /从有序表开头进行从有序表开头进行比较，比较，pre指向指向插入插入p的前驱结

5、点的前驱结点while (pre-next!=NULL & pre-next-datadata) pre=pre-next;/在有序表中找在有序表中找插入插入p的前驱结点的前驱结点prep-next=pre-next;pre-next=p;p=q;/扫描原单链表余下扫描原单链表余下的结点的结点 在在pre之后插入之后插入p在有序单链表中查找插入在有序单链表中查找插入结点的前驱结点结点的前驱结点pre该算法的时间复杂度为该算法的时间复杂度为O(n2)。6/17单链表有尾单链表有尾插法和头插插法和头插法两种建表算法。法两种建表算法。很多算法是以这两个建表算法为基础进行设计的。很多算法是以这

6、两个建表算法为基础进行设计的。 以建表算法为基础的算法设计以建表算法为基础的算法设计 7/17 【例（补充）例（补充）】 假设假设有有一一个个带头带头结点结点的的单链表单链表L=a1，a2，an。设计。设计一个算法一个算法将所有结点逆置，即将所有结点逆置，即：L=an，an-1，a1La1a2an算法设计思路p头插法建表头插法建表8/17void Reverse(LinkNode *&L) LinkNode *p=L-next，*q; L-next=NULL; La1a2anp将将L拆分为两个部分拆分为两个部分9/17 while (p!=NULL) q=p-next; p-next=

7、L-next; L-next=p; p=q; La1a2anp头插法建表头插法建表10/17另一种解法La2a3anpqra1这种解法远不如前面解法清晰！这种解法远不如前面解法清晰！11/17 【例（补充）例（补充）】 假设假设有有一一个个带头带头结点结点的的单链表单链表L=a1，b1，a2，b2，an，bn。设计。设计一个算法将其拆分成两一个算法将其拆分成两个个带头带头结点的结点的单链表单链表L1和和L2：L1=a1，a2，an，L2=bn，bn-1，b1要求要求L1使用使用L的的头结点。头结点。La1b1bnanL1a1a2anan-1L2bnbn-1b1b212/17 解：解：利用原单链

8、表利用原单链表L中中的的所有结点通过所有结点通过改变指针域重组成改变指针域重组成单链表单链表L1和和L2。由于由于L1中结点的中结点的相对顺序与相对顺序与L中中的的相同，所以相同，所以采用尾插法采用尾插法建立单链表建立单链表L1；由于由于L2中结点的中结点的相对顺序与相对顺序与L中中的的相反，所以相反，所以采用头插法采用头插法建立单链表建立单链表L2。L1pL2头插法建表头插法建表尾插法建表尾插法建表13/17void split(LinkNode *&L，LinkNode *&L1，LinkNode *&L2) LinkNode *p=L-next，*q，*r1;/p

9、指向第指向第1个个数据结点数据结点 L1=L;/L1利用原来利用原来L的的头结点头结点 r1=L1;/r1始终指向始终指向L1的尾结点的尾结点 L2=(LinkNode *)malloc(sizeof(LinkNode); /创建创建L2的头结点的头结点 L2-next=NULL;/置置L2的指针域为的指针域为NULL L1L2p建表的准备工作建表的准备工作 14/17 while (p!=NULL) r1-next=p;/采用尾插法将采用尾插法将*p(data值为值为ai)插入插入L1中中r1=p;p=p-next;/p移向下移向下一一个结点个结点(data值为值为bi)q=p-next; /用用q保存保存*p的的后继结点后继结