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

内容小结：

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

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的相关知识。