数据结构算法及线性表总结

ipqtjmqj 2020-03-28

一.思维导图

数据结构算法及线性表总结

二.重要概念

1:时间复杂度

时间复杂度是评判算法优劣的最重要的标准,所以要掌握时间复杂度的运算非常重要,并且要熟记常见时间复杂度以及对应的关系

2:链表的插入删除操作

注意:节点是包括数据域和指针域,插入和删除时要注意指针的指向问题,插入时,插入的节点跟前一个节点的下一个节点相连时,前一个节点也要与插入的节点相连,不然会出现断链情况,删除时也要链连接后在删除节点

3:栈与队列

栈和队列很想象,但要注意其区别,栈是后进先出(LIFO),而队列是先进先出(FIFO)。并且栈可以将递归程序转变成非递归程序,栈和队列都可以用来暂存状态。栈可以用来求解符号配对,表达式转换,迷宫等问题。而队列可以用来求排队,迷宫问题。两者都可以用来求解迷宫问题。要注意其区别。

4:串的模式匹配

要注意模式串某一个字符的前缀和后缀,找出其next的值,这样才能找出nextval的值,这样才能正确的找到主串与模式串相同的子串

三.疑难问题以及解决方案

1:有序表删除重复元素不能删除重复的最后一个元素

解决方案:有序表删除存放元素,要注意边界问题,在这个问题中一个元素都要依次后一个元素进行比较,所以应当画出其比较的示意图,这样才不会漏掉元素

2:单链表的逆置(头插法)出错

解决方案:头插法单链表的逆置要注意链表在遍历前的操作,先将第一个节点的指针域为空,让节点与链表断开,每遍历一次断开一个节点,并让其指向第一个节点,先前的第一个节点往后移,这样最后当遍历至最后一个节点时指针域为空,就逆置成功了

3:判断字符串对称出错

解决方案:当用指针指向字符时要注意指针的指向问题,因为你在遍历字符时,指针已经指向空指针,所以在判断出栈元素和和第一个字符是否相同时不能判断,因为指针所指向的地址没有值,所以当遍历字符过后,要将指针重新指向第一个字符。这样才正确

相关推荐