首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

数据结构之顺序表实现2.1

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多多,下次更的时间从来未定,但是我肯定会尽量压缩时间,加快复习进度,下次见,我是潇雷,晚安。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180707G1M3ZL00?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券