目录课前准备顺序表概念及结构顺序表分类实现动态顺序表正文开始课前预备1. 课程目标C语言语法基础到数据结构与算法前面已经掌握并具备了扎实的C语言基础为什么要学习数据结构课程–通讯录项目2. 需要的储备知识简单了解通讯录具备增加、删除、修改、查找联系人等操作。要想实现通讯录项目有两个技术关键C语言语法基础数据结构之顺序表/链表3. 数据结构相关概念1. 什么是数据结构数据结构是由“数据”和“结构”两词组合而来。什么是数据常见的数值1、2、3、4…、教务系统里保存的用户信息姓名、性别、年龄、学历等等、网页里肉眼可以看到的信息文字、图片、视频等等这些都是数据。什么是结构当我们想要使用大量同一类型的数据时通过手动定义大量的独立变量对于程序来说可读性非常差。我们可以借助数组这样的数据结构将大量的数据组织在一起结构也可以理解为组织数据的方式。想要找到草原上名叫“咩咩”的羊很难但是从羊圈里找到1号羊就很简单羊圈这样的结构有效地将羊群组织起来。概念数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成即数据由哪部分构成以什么方式构成以及数据元素之间呈现的结构。总结能够存储数据如顺序表、链表等结构存储的数据能够方便查找2. 为什么需要数据结构如图中所示不借助排队的方式来管理客户会导致客户就餐感受差、等餐时间长、餐厅营业混乱等情况。同理程序中如果不对数据进行管理可能会导致数据丢失、操作数据困难、野指针等情况。通过数据结构能够有效将数据组织和管理在一起。按照我们的方式任意对数据进行增删改查等操作。最基础的数据结构数组。思考有了数组为什么还要学习其他的数据结构假定数组有10个空间已经使用了5个向数组中插入数据步骤求数组的长度求数组的有效数据个数向下标为数据有效个数的位置插入数据注意这里是否要判断数组是否满了满了还能继续插入吗…假设数据量非常庞大频繁地获取数组有效数据个数会影响程序执行效率。结论最基础的数据结构能够提供的操作已经不能完全满足复杂算法实现。顺序表1. 顺序表的概念及结构1.1 线性表线性表linear list是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构常见的线性表顺序表、链表、栈、队列、字符串……线性表在逻辑上是线性结构也就是说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储。案例蔬菜分为绿叶类、瓜类、菌菇类。线性表指的是具有部分相同特性的一类数据结构的集合。如何理解逻辑结构和物理结构2. 顺序表分类顺序表和数组的区别顺序表的底层结构是数组对数组的封装实现了常用的增删改查等接口。顺序表分类静态顺序表概念使用定长数组存储元素静态顺序表缺陷空间给少了不够用给多了造成空间浪费动态顺序表3. 动态顺序表的实现#defineINIT_CAPACITY4typedefintSLDataType;// 动态顺序表 -- 按需申请typedefstructSeqList{SLDataType*a;intsize;// 有效数据个数intcapacity;// 空间容量}SL;// 初始化和销毁voidSLInit(SL*ps);voidSLDestroy(SL*ps);voidSLPrint(SL*ps);// 扩容voidSLCheckCapacity(SL*ps);// 头部插入删除 / 尾部插入删除voidSLPushBack(SL*ps,SLDataType x);voidSLPopBack(SL*ps);voidSLPushFront(SL*ps,SLDataType x);voidSLPopFront(SL*ps);// 指定位置之前插入/删除数据voidSLInsert(SL*ps,intpos,SLDataType x);voidSLErase(SL*ps,intpos);intSLFind(SL*ps,SLDataType x);
