平湖公司做网站,旅游网站建设的市场分析,my eclipse网站开发,宁波荣胜网络科技有限公司C语言语法基础到数据结构与算法#xff0c;前面已经掌握并具备了扎实的C语言基础#xff0c;为什么要学习数据结构课程#xff1f;--我们学完本章就可以实践一个#xff1a;通讯录项目
简单了解过后#xff0c;通讯录具备增加、删除、修改、查找联系人等操作。要想实现通…C语言语法基础到数据结构与算法前面已经掌握并具备了扎实的C语言基础为什么要学习数据结构课程--我们学完本章就可以实践一个通讯录项目
简单了解过后通讯录具备增加、删除、修改、查找联系人等操作。要想实现通讯录项目必须有两个技术关键1C语言语法基础2数据结构 之 顺序表/链表。 一、初步了解数据结构
什么是数据结构数据结构就是“数据”与“结构”两个词组合而来。
什么是数据常见的数值1、2、3......、教务系统里保存的用户信息姓名、性别、年龄、学历等、网页里的图片、视频、文字等等都是数据。我们知晓的所有信息都可以称之为数据数据在计算机中存储的方式都是二进制数字包括图文、视频等
什么是结构当我们想要大量使用同一类型的数据时通过手动定义大量的独立的变量对于程序来说可读性非常差我们可以借助数组这样的数据结构将大量的数据组织在一起结构也可以理解为组织数据的方式。
概念数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在的一种或多种特定关系的数据元素的集合。数据结构反映数据的内部构成即数据由哪部分构成、以什么方式构成、以及数据元素之间呈现的结构。 小结 1.能够存储数据(如顺序表、链表等结构) 2.存储的数据能够方便查找 为什么需要数据结构通过数据结构可以有效的将数据组织和管理在一起。按照我们的方式任意对数据进行增删查改等操作。最基础的数据结构数组。
【思考】有了数组为什么还要学习其它数据结构
假定数组有10个空间已经使用了5个向数组中插入数据的步骤有
1.求数组的长度求总长是为了判断有效个数与最大长度是否相等数组满员还能继续插入吗 2.求数组的有效数据个数 3.向下标为数据有效个数的位置插入数据
假设数据量非常的庞大频繁的获取数组有效个数会影响程序执行效率。
结论最基础的数据结构能提供的操作已经不能完全满足复杂算法的实现。 二、顺序表
1.顺序表的概念及结构
顺序表是一种线性表。线性表(linear list)是n个相同特性的数据元素的有限序列。线性表是一种在实际中广泛应用的数据结构常见的线性表包括顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构也就说是连续的一条直线。但是在物理结构上并不一定是连续的线性表在物理上的存储方式通常是顺序(数组)存储和链式存储。
如何理解逻辑结构和物理结构下面给大家画一张图 第一种就是物理顺序和逻辑顺序一致在一段连续的空间中依次存放数据。第二种就是这些数据逻辑上是一条线但由于存储的位置不连续在忽略其它空间的情况下将这些空间取出并将其放置到一条直线上就可以验证它的线性存储形式是逻辑线性物理上的存储是不确定的。
2.顺序表分类
顺序表和数组的区别顺序表的底层结构是数组对数组的封装实现了常用的增删查改等接口。
分类静态顺序表-动态顺序表
//静态顺序表
typedef int DataType;
#define SQLIST_INIT_LENGTH 10
typedef struct SqList{DataType arr[SQLIST_INIT_LENGTH];size_t _size;//有效数据个数每插入一个数据就会1用来记录
}SL;
//静态顺序表缺陷空间给少了不够用给多了造成空间浪费
//动态顺序表--按需分配
typedef struct SqList{DataType* arr;size_t _size;//有效数据个数size_t _capacity;//空间容量
}SL;
3.动态顺序表的基本操作
#define LIST_INIT_SIZE 10
typedef int DataType;
typedef struct SqList{DataType* arr;size_t size;//有效数据个数size_t capacity;//空间容量
}SL;//判空、取长、寻值
bool isEmpty(SL s);
int GetSize(SL s);
int SLFind(SL s,DataType data);//初始化与销毁
void SLInit(SL* s);
void SLDestroy(SL* s);
//打印
void SLPrint(SL s);
//扩容
void SLCheckCapacity(SL* s);
//修改指定位置的值
void UpdateNode(SL* s,int index,DataType data);//指定位置之前插入/删除数据
void SLInsert(SL* s,int index,DataType data);
void DeleteByIndex(SL* s,int index);
//按值删除数据
void DeleteByData(SL s,DataType data);//增删操作也可以有下面的几种
//头插、头删、尾插、尾删
void SLInsert_Head(SL* s,DataType data);
void SLDelete_Head(SL* s);
void SLInsert_Tail(SL* s,DataType data);
void SLDelete_Tail(SL* s); 三、动态顺序表的实现
1.顺序表的判空操作
顺序表的内容是否为空主要就是看里面的动态数组是否指向空指针。然后返回这个表达式的结果(布尔类型)。
bool isEmpty(SL s)
{return (s.arr nullptr);
}
2.顺序表的长度
我们说的顺序表的长度是有效数据个数而非顺序表的空间总量 。所以我们返回的就是顺序表内部的size属性。
int GetSize(SL s)
{return s.size;
}
3.查找某值在顺序表的位置
查找某值在顺序表的位置时首先判断顺序表是不是空的如果是空的那就没必要再继续了直接返回-1。否则循环遍历直至顺序表中顺组的有效长度的最后一个值。如果循环结束仍未找到返回-1。那么综上返回-1就代表表内无该元素。
int SLFind(SL s, DataType data)
{if (isEmpty(s))return -1;else{for (int i 0; i s-size; i) {if (*(s-arr i) data) {return i;}}}return -1;
}
4.顺序表的初始化与销毁
初始化时使用宏定义的初始化长度LIST_INIT_SIZE使用malloc为数组申请一定长度的空间然后对该表进行判断如果仍然为空说明malloc申请空间时由于某些原因申请失败了离开程序。否则就将顺序表的最大长度设为初始值有效长度设为0。
销毁顺序表时将顺序表长度和空间容量都置零令数组指针指向NULL(按理来说nullptr更为严谨)。最后使用free释放内存空间。 //初始化顺序表:给arr开辟10个空间void SLInit(SL* s){s-arr (DataType*)malloc(sizeof(DataType) * LIST_INIT_SIZE);if (isEmpty(*s))exit(OVERFLOW);//s-arr new DataType[LIST_INIT_SIZE];s-capacity LIST_INIT_SIZE;s-size 0;//尚未存储数据}//销毁顺序表void SLDestroy(SL* s){assert(s-arr);//在头文件assert.h中s-capacity s-size 0;s-arr NULL;free(s-arr);cout 销毁完毕 endl;}
5.顺序表打印
如果顺序表为空那还打印什么直接告诉用户顺序表为空就可以了。非空的话那就循环遍历顺序表的有效数据将其中存储的值依次打印出来。
void PrintSqlist(SL s)
{if (isEmpty(s))cout 顺序表为空;else {for (int i 0; i s.size; i)cout *(s.arr i) ;}cout endl;
}
6.顺序表插入数据
此处涉及到一个扩容的问题当有效长度与最大容量相等时说明顺序表满了需要使用realloc动态扩容考虑到不断扩容会导致效率变低或者出现问题我们每次表满时直接选择二倍扩容。
//尾插
void SLInsert_Tail(SL* s, DataType data)
{if (isEmpty(*s)) {SLInit(s);//如果顺序表为空则开辟一个顺序表}if ((s-size) (s-capacity)){//2倍扩容DataType* tmp (DataType*)realloc(s-arr, (s-capacity * 2) * sizeof(DataType));assert(tmp);//判断指针是否为空s-arr tmp;//(s-capacity) * 2;}*(s-arr s-size) data;(s-size);
}//指定位置插入
void SLInsert(SL* s, int index, DataType data)
{if (isEmpty(*s)) SLInit(s);if (index 0 || index s-size) return;if (s-size s-capacity){int newcapacity s-capacity * 2;DataType* tmp (DataType*)realloc(s-arr, sizeof(DataType) * newcapacity);assert(tmp);s-arr tmp;}for (int i s-size; i index; i--){s-arr[i 1] s-arr[i];}s-arr[index] data;s-size;
}
7.顺序表删除数据 //删除顺序表第index位数据按位删
void DeleteByIndex(SL* s, int index)
{if (isEmpty(*s)|| index s-size||index 0)cout 空表或索引溢出 endl;else {for (int i index; i (s-size); i) {DataType tmp *(s-arr i);*(s-arr i) *(s-arr i 1);*(s-arr i 1) tmp;}(s-size)--;}cout 删除成功 endl;
}//删除顺序表数据data按值删
void DeleteByData(SL s, DataType data)
{if (isEmpty(s))cout 空表 endl;else {for (int i 0; i s.size; i){if (*(s.arr i) data) {for (int j i; j s.size; j){DataType tmp *(s.arr j);*(s.arr j) *(s.arr j 1);*(s.arr j 1) tmp;}s.size--; }cout 删除完毕 endl;}}
}
8.修改顺序表内容
void UpdateNode(SL* s, int index, DataType data)
{if (isEmpty(*s))cout 顺序表为空 endl;else{*(s-arr index) data;cout 修改成功 endl;}
}9.顺序表扩容
扩容操作参考插入时的特殊处理。 我们在下节的项目实战中完成顺序表实现通讯录。大家先试着完成写一写自己的通讯录系统独立的完成每一个小项目才能为完成大项目积累经验。加油各位
