408第一季 - 数据结构 - 线性表

只能用C/C++！

顺序表

闲聊

线性表的逻辑顺序和物理顺序相同

都是1234

顺序表的优点：

随机访问，随机访问的意思是访问的时间 和位置没有关系，访问下标1和100一样的，更深层就是直接计算 a+100 * 数组大小，随便你访问，主打一个查的爽

缺点：

插入和删除要移动元素

然后就是书上的代码和最好情况最坏情况的公式没啥用，因为情况多变，做题就知道了

做题区 崛起！

1

A 指定元素的 算法   平均是n/2次

B 也是n/2次

C 也是n/2次

D 直接获取下标  ✔

2

题目解释一下，下面是循环左移三个位置 

高手思维（官方做法）

6，1，5反转一下

9，8，4，7反转一下

然后变成的5，1，6，7，4，8，9全部反转一下，就得到了

 

空间复杂度为O1

普通人思维

先开一个数组p=3

然后把其他的往前移，也就最前面变成了9，8，4，7，然后再把6，1，5塞后面

空间复杂度为Op

具体代码

R是最终要形成的数组，n是数的个数，这里是7，p是要左移的个数，这里是3

这里代码空间复杂度是Op

时间复杂度就是Op + On-p + Op = On+p

链表

指针的概念

指针指向地址

这里指针p取了a的地址，a的地址是4，那p这个框框里就是4

然后是对应的输出

这里的*是解地址

再来

结构体的概念

-------->

然后他们是一个意思 

然后给他们赋值的两种方式

 链表的定义

概念解释

比如这里的物理结构（存储结构）长这个样子（已分裂！）

然后逻辑结构就是这样，4后面可以是NULL

代码解释

typedef是重命名，因为结构体是自己定义的，比如上面的student就是我自己的定义的，不用typedef的话以后但凡遇到student就要struct student，太麻烦了，所以有了typedef，typede可以直接把struct LNode定义成 LNode 和 *LinkList，具体这两个可以看下面

然后如果以后遇到了LinkList  p要记住，p是包含指针的！

Elemtype 这个可以泛化类型，可以表示int，float，string都可以

例子分析

遍历

这里定义了指针LNode* cur = head

这里的cur = cur -> next 指向后变成了20，cur = 20

插入

这里会有一个p指向要插入的E

要先把 p->next = cur -> next 再 cur -> next = p,如果反过来，后果将可以设想

删除

注意到

p -> next = p -> next -> next 就可以实现了

但这样定义就不能释放那个被弃掉的节点了

所以