1.大纲:抽象数据类型表的基本概念及其逻辑特征。实现抽象数据类型表的一般步骤及常用实现表的方法。
2.定义:线性表是具有相同特性数据元素的一个有限序列。
【注】:相同特性是把同一类事物归类,方便批量处理。
3.逻辑特征:只有一个表头,只有一个表尾,表头没有前驱,表尾没有后继。
4.存储结构对比:
⑴顺序表:随机访问特性,会占用连续的存储空间。
⑵链表:不支持随机访问,结点存储空间利用率较顺序表稍低一些。
5.链表5种形式:单链表,双链表,循环单链表,循环双链表,静态链表。
6.对顺序表插入的时间复杂度分析:
数列{1,2,3…n-2,n-1,n}的一个顺序表中进行操作,插入一个元素的平均移动个数?
①求概率:插入位置的随机性,n个可插入位置,p=1/n.
②求插入需要移动元素:第i个元素插入之后,所有元素将往后移动一个位置,因此,移动元素个数为n-i.
总的移动数:n-1+n-2+n-3+……+n-(n-1)+n-n=n*n-(1+n)n/2
数学期望E=p*[ n*n-(1+n)n/2]=(n-1)/2
要移动近一半的元素,时间复杂度O(n)。
7.顺序表的五大必备操作:
①初始化顺序表的算法
②求指定位置元素的算法(返回L p位置上的元素)
③按元素查找(查出第一个e的元素)
④插入(在第p个元素后插入元素e)
⑤删除(删除第p个元素)
综合代码示例(可以左右滑动)
ps:代码总结自网络及严版数据结构。时间太紧,就不在意文章排版了,内容虽少,但一篇文章耗时也是不少,可能有点得不偿失了,我一直希望能用c来将数据结构部分的代码实现一遍,可惜能力有限,bug多多,下次更的时间从来未定,但是我肯定会尽量压缩时间,加快复习进度,下次见,我是潇雷,晚安。
领取专属 10元无门槛券
私享最新 技术干货