数据结构入门"/>
C语言数据结构入门
1.数据
数据:是描述客观事物的符号,是计算机中可以操作的对象,是能被计算机识别,并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型,还包括字符及声音、图像、视频等非数值类型。比如我们现在常用的搜索引擎,一般会有网页、MP3、图片、视频等分类。MP3就是声音数据,图片当然是图像数据,视频就不用说了,而网页其实指的就是全部数据的集合,包括最重要的数字和字符等文字数据。也就是说,我们这里说的数据,其实就是符号,而且这些符号必须具备两个前提:
可以输入到计算机中。
能被计算机程序处理。
对于整型、实型等数值类型,可以进行数值计算。
对于字符数据类型,就需要进行非数值的处理。而声音、图像、视频等其实是可以通过编码的手段变成字符数据来处理的。
2. 数据元素
数据元素:是组成数据的、有一定意义的基本单位,在计算机中通常作为整体处理。也被称为记录。
比如,在人类中,什么是数据元素呀?当然是人了。
畜类呢?哈,牛、马、羊、鸡、猪、狗等动物当然就是禽类的数据元素。
3.数据项
数据项:一个数据元素可以由若干个数据项组成。
比如人这样的数据元素,可以有眼、耳、鼻、嘴、手、脚这些数据项,也可以有姓名、年龄、性别、出生地址、联系电话等数据项,具体有哪些数据项,要视你做的系统来决定。
数据项是数据不可分割的最小单位。在数据结构这门课程中,我们把数据项定义为最小单位,是有助于我们更好地解决问题。所以,记住了,数据项是数据的最小单位。但真正讨论问题时,数据元素才是数据结构中建立数据模型的着眼点。就像我们讨论一部电影时,是讨论这部电影角色这样的“数据元素”,而不是针对这个角色的姓名或者年龄这样的“数据项”去研究分析。
4.数据对象
数据对象:是性质相同的数据元素的集合,是数据的子集。
什么叫性质相同呢,是指数据元素具有相同数量和类型的数据项,比如,还是刚才的例子,人都有姓名、生日、性别等相同的数据项。
既然数据对象是数据的子集,在实际应用中,处理的数据元素通常具有相同性质,在不产生混淆的情况下,我们都将数据对象简称为数据。
5.什么是数据结构
数据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成,即一个数据由那些成分数据构成,以什么方式构成,呈什么结构。数据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系,而物理上的数据结构反映成分数据在计算机内部的存储安排。数据结构是数据存在的形式。 数据结构是信息的一种组织方式,其目的是为了提高算法的效率,它通常与一组算法的集合相对应,通过这组算法集合可以对数据结构中的数据进行某种操作。
6.顺序存储方式
线性表的顺序存储结构,说白了,和刚才的例子一样,就是在内存中找了块地儿,通过占位的形式,把一定内存空间给占了,然后把相同数据类型的数据元素依次存放在这块空地中。既然线性表的每个数据元素的类型都相同,所以可以用C语言(其他语言也相同)的一维数组来实现顺序存储结构,即把第一个数据元素存到数组下标为0的位置中,接着把线性表相邻的元素存储在数组中相邻的位置。
我那同学占座时,如果图书馆里空座很多,他当然不必一定要选择第一排第一个位子,而是可以选择风水不错、美女较多的地儿。找到后,放一个书包在第一个位置,就表示从这开始,这地方暂时归我了。为了建立一个线性表,要在内存中找一块地,于是这块地的第一个位置就非常关键,它是存储空间的起始位置。
接着,因为我们一共九个人,所以他需要占九个座。线性表中,我们估算这个线性表的最大存储容量,建立一个数组,数组的长度就是这个最大存储容量。
可现实中,我们宿舍总有那么几个不是很好学的人,为了游戏,为了恋爱,就不去图书馆自习了。假设我们九个人,去了六个,真正被使用的座位也就只是六个,另三个是空的。同样的,我们已经有了起始的位置,也有了最大的容量,于是我们可以在里面增加数据了。随着数据的插入,我们线性表的长度开始变大,不过线性表的当前长度不能超过存储容量,即数组的长度。想想也是,如果我们有十个人,只占了九个座,自然是坐不下的。
描述顺序存储结构需要三个属性:
a.存储空间的起始位置:数组data,它的存储位置就是存储空间的存储位置。
b.线性表的最大存储容量:数组长度MaxSize。
c.线性表的当前长度:length
7.数组长度与线性表长度区别
数组的长度是存放线性表的存储空间的长度,存储分配后这个量一般是不变的。有个别同学可能会问,数组的大小一定不可以变吗?我怎么看到有书中谈到可以动态分配的一维数组。是的,一般高级语言,比如C、VB、C++都可以用编程手段实现动态分配数组,不过这会带来性能上的损耗。
线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。
在任意时刻,线性表的长度应该小于等于数组的长度。
8.如何获取元素
对于线性表的顺序存储结构来说,如果我们要实现GetElem操作,即将线性表L中的第i个位置元素值返回,其实是非常简单的。就程序而言,只要i的数值在数组下标范围内,就是把数组第i-1下标的值返回即可。来看代码:
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
/* Status是函数的类型,其值是函数结果状态代
码,如OK等 */
/* 初始条件:顺序线性表L已存在,1≤i≤
ListLength(L) */
/* 操作结果:用e返回L中第i个数据元素的值 */
Status GetElem(SqList L, int i, ElemType *e)
{
if (L.length == 0 || i < 1 ||
i > L.length)
return ERROR;
*e = L.data[i - 1];
return OK;
}
注意这里返回值类型Status是一个整型,返回OK代表1,ERROR代表0。之后代码中出现就不再详述。
9.如何插入
插入算法的思路:
a.如果插入位置不合理,抛出异常;
b.如果线性表长度大于等于数组长度,则抛出异常或动态增加容量;
c.从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
d.将要插入元素填入位置i处; ?表长加1。
实现代码如下:
/* 初始条件:顺序线性表L已存在,1≤i≤
ListLength(L), */
/* 操作结果:在L中第i个位置之前插入新的数据元
素e,L的长度加1 */
Status ListInsert(SqList *L, int i, ElemType e)
{
int k;
/* 顺序线性表已经满 */
if (L->length == MAXSIZE)
return ERROR;
/* 当i不在范围内时 */
if (i < 1 || i >L->length + 1)
return ERROR;
/* 若插入数据位置不在表尾 */
if (i <= L->length)
{
/*将要插入位置后数据元素向后移动一位 */
for (k = L->length - 1; k >= i - 1; k--)
L->data[k + 1] = L->data[k];
}
/* 将新元素插入 */
L->data[i - 1] = e;
L->length++;
return OK;
}
10.删除操作
删除算法的思路:
a.如果删除位置不合理,抛出异常;
b.取出删除元素;
c.从删除元素位置开始遍历到最后一个元素位置,分别将它们都向前移动一个位置;
d.表长减1。
实现代码如下:
/* 初始条件:顺序线性表L已存在,1≤i≤
ListLength(L) */
/* 操作结果:删除L的第i个数据元素,并用e返回
其值,L的长度减1 */
Status ListDelete(SqList *L, int i, ElemType *e)
{
int k;
/* 线性表为空 */
if (L->length == 0)
return ERROR;
/* 删除位置不正确 */
if (i < 1 || i > L->length)
return ERROR;
*e = L->data[i - 1];
/* 如果删除不是最后位置 */
if (i < L->length)
{
/* 将删除位置后继元素前移 */
for (k = i; k < L->length; k++)
L->data[k - 1] = L->data[k];
}
L->length--;
return OK;
}
现在我们来分析一下,插入和删除的时间复杂度。
先来看最好的情况,如果元素要插入到最后一个位置,或者删除最后一个元素,此时时间复杂度为O(1),因为不需要移动元素的,就如同来了一个新人要正常排队,当然是排在最后,如果此时他又不想排了,那么他一个人离开就好了,不影响任何人。
最坏的情况呢,如果元素要插入到第一个位置或者删除第一个元素,此时时间复杂度是多少呢?那就意味着要移动所有的元素向后或者向前,所以这个时间复杂度为O(n)。
至于平均的情况,由于元素插入到第i个位置,或删除第i个元素,需要移动n-i个元素。根据概率原理,每个位置插入或删除元素的可能性是相同的,也就说位置靠前,移动元素多,位置靠后,移动元素少。最终平均移动次数和最中间的那个元素的移动次数相等,为(n-1)/2。
更多推荐
C语言数据结构入门
发布评论