数据结构:第四章学习小结

内容小结:

第四章学习了串、数组、广义表等,其中包括:

1.串:

①串的定义:注意空串(Ø)和空格串(“ ”)的区别。

②串的存储结构:分为顺序存储和链式存储,其中:

  i. 顺序存储又分为定长顺序存储和堆式顺序存储,前者为静态存储,相当于一维数组,而后者为动态存储;

  ii. 链式存储:每个结点可以存放一个或多个字符;最后一个结点若是未被占满,可用“#”或其他非串值字符补全。

③串的模式匹配算法:

  i. BF算法:时间复杂度为O(m×n),效率比较低

  ii. KMP算法:时间复杂度为O(m+n)

2.数组:

①存储特点:一般用顺序存储结构,存储多维数组有按 “行“ 和按 “列“ 两种方式,注意不同存储方式的元素地址计算方法!

②特殊矩阵的压缩:

  i.矩阵中存在大量值相同的元素,称为特殊矩阵:对称矩阵、三角矩阵、对角矩阵、

  ii. 矩阵中存在极少量非零元素,称为稀疏矩阵:三元组表、行逻辑链接顺序表,十字链表

3.广义表:

注意表中的的数据元素可能为原子或广义表,通常用链式存储结构。

心得体会:

1.PTA:

①串的模式匹配:使用string来表示串,需要注意string是从下标为0的数组分量开始存储,因此部分操作与书上不同(此处不赘述,很好理解修改的)。

②求集合交集:一开始使用链表,时间复杂度过大,虽然做错了,但是了解到一些链表排序的方法,还是有所收获的。

void SortList(LinkList &a)//直接交换结点 升序排序
{
    LNode *p = a->Next, *pre;
    LNode *r = p->Next;    
    p->Next = NULL;//断开结点 
    p = r;
    while (p != NULL) {
        r = p->Next;
        pre = a;        
        while (pre->Next && pre->Next->data < p->data) 
        {            
            pre = pre->Next;//直到找到较大的结点或者已经排序完 
        }        
        p->Next = pre->Next; 
        pre->Next = p;//将较大的结点插入到较小的结点之后 
        p = r;//将当前结点往后移,继续比较 
    }
}

后来改用为数组,使用sort函数实现。

#include<algorithm>
sort(start,end,cmp)
//参数:start表示要排序数组的起始地址;end表示数组结束地址的下一位;cmp用于规定排序的方法,默认升序。
//时间复杂度为n*log2(n)

上一阶段的目标完成情况:

大致完成,但是对于第四章的部分知识很生疏,做起题目不够顺利吧。

接下来的目标:

1.先继续掌握第四章的知识,比如KMP算法、广义表的存储结构等等;

2.巩固上一周教的时间复杂度计算方法以及慕课讨论上关于char*和string的相关知识。

相关推荐