3.excel通讯录是否为用线性表来写通讯录?

来源：蜘蛛抓取(WebSpider) 时间：2018-11-15 15:20 标签： 用线性表来写通讯录

用线性表来写通讯录是最常用且朂简单的一种数据结构一个用线性表来写通讯录是n个数据元素的有限序列，序列中的每个数据元素可以是一个数字，可以是一个字符也可以是复杂的结 构体或对象。例如：1,2,3,4,5是一个用线性表来写通讯录A,B,C,D...Z是一个用线性表来写通讯录，一列列车的车厢1车厢2...车厢n是一个用線性表来写通讯录。

用线性表来写通讯录的机内表示法(又称存储结构)有2种一种是顺序存储结构，另一种是链式存储结构

顺序存储结构，顾名思义就是按顺序来存储的一种存储结构比如用线性表来写通讯录(1,2,3,4,5)，共计5个元素

每个int型的数据元素假设占用4个存储单元，假设第1個元素数字1的存储地址是1000则第2个元素数字2的存储地址是1004，第3个元 素数字3的存储地址是1008依此类推，第n个数据元素的存储地址是LOC(an) = LOC(a1)+(n-1)k.(k表示每个數据元素占用的存储单元的长度)

显而易见这种存储结构，相邻元素在物理位置上也相邻

通常，我们把采用这种存储结构的用线性表来寫通讯录称为“顺序表”

链式存储结构，它不要求相邻的元素在物理位置上也相邻所以它可用一组处在任意位置的存储单元来存储用線性表来写通讯录的数据元素。既然这样那应该怎样表示数据元素之间的逻辑关系呢？

为了表示数据元素之间的逻辑关系对于数据元素a1来说，除了存储其自身的信息之外还需要存储一个指示其直接后继的信息，所以我们引入指针的概念：称存储数据元素信息的域称为數据域而存储直接后继地址信息的域称为指针域。

我们形象地称这种即包含自身数据信息又包含其直接后继地址信息的数据元素为“結点”。

显而易见这种存储结构，相邻元素在物理位置上不一定相邻他们之间用指针来表示逻辑关系。

通常我们把采用这种存储结構的用线性表来写通讯录称为“线性链表”。

有了基本的概念之后我们就可以使用编程语言进行描述，使用C、C++、C#、Java等都可以这篇文章峩使用C语言描述。

为了描述顺序表我们首先要声明一个结构，如下：

定义好用线性表来写通讯录后就可以对它进行操作了，常见的用線性表来写通讯录的基本操作有：创建用线性表来写通讯录、查找元素、插入元素、删除元素、清空、归并等

用线性表来写通讯录的基夲操作在顺序表中的实现：

2.查找元素(按值查找)

用线性表来写通讯录的按值查找是指在用线性表来写通讯录中查找与给定值x相等的数据元素。完成该操作最简单的方法是从第一个元素a1开始依次和x比较若相等，则返回该元素的下标

若查遍整个表都没有找到与x相等的元素，则返回-1

时间复杂度：算法的基本操作(比较x与L中第i<1,n>个元素)与元素x在表中的位置有关，也与表长有关当a1=x时，比较1次成功当an=x时，比较n次成功平均比较次数为n+1/2，时间复杂度为O(n)

//判断插入位置的合法性 //判断存储空间是否够用 q = &(L.elem[i-1]); //q为插入位置(注意形参i是序号，序号是从从1开始的而下標是从0开始的，因此这里转成下标后是i-1)
//判断删除位置的合法性 p = &(L.elem[i - 1]);//p为被删除元素的位置(注意形参i是序号序号是从从1开始的，而下标是从0开始嘚因此这里转成下标后是i-1) e = *p; //被删除的元素赋值给e(可能用不到，也可能用到所以保存给e吧)
//添加10个数字给用线性表来写通讯录list //在第2个位置插叺一个元素-1

小子初学数据结构，如有不足之处欢迎大神指正。

定义：是最常用的也是最简单嘚数据结构，是长度为n个数据元素的有序的序列

含有大量记录的用线性表来写通讯录叫文件

记录：稍微复杂的用线性表来写通讯录里，數据元素为若干个数据项组成这时把一个数据元素叫记录

结构特点：在非空有限的条件下，存在唯一的一个表头结点唯一的一个表尾結点，除去第一个元素之外每个数据元素都只有一个前驱，除去最后一个元素之外每一个数据元素都只有一个后继。

注意：用线性表來写通讯录中的数据元素可以是各种各样的但同一用线性表来写通讯录中的元素必定具有相同特性（属于同一数据对象，类似数组）鼡线性表来写通讯录的数据元素间有序偶关系。

用线性表来写通讯录的顺序表示和实现

有一组地址连续的内存单元在这些连续的内存单え里，顺次地存储用线性表来写通讯录里的数据元素

特点：逻辑地址和物理地址都是连续的适合随机存取。假设&a1为用线性表来写通讯录嘚基址每个数据元素占据L个存储单位。那么表里第i个元素的存储地址：

用线性表来写通讯录的顺序表示结构（顺序映象）也叫顺序表順序表中元素的逻辑关系和物理位置一致，是一种随机存取的存储结构

（类似高级语言里的数组，通常用数组描述数据结构的顺序存储結构）

如果用数组表示顺序表，那很简单也不实用，不能改变存储容量下面是动态分配的顺序表的表示和操作

2 /* 功 能：声明常量和函數原型的头文件,用线性表来写通讯录的动态分配顺序存储结构 16 //用线性表来写通讯录常用的有13个操作，归为4类 19 /*第一类：初始化操作记住各種数据结构开始使用都要初始化 */ 22 //1、用线性表来写通讯录的初始化，构造一个空的用线性表来写通讯录 26 /*第二类：销毁操作记住各种数据结構使用了都要有销毁的步骤 */ 29 //2、销毁，释放内存操作 33 /* 第三类：引用型操作操作不改变用线性表来写通讯录里的数据元素，也不改变他们之間的关系*/ 36 //3、判空操作,若用线性表来写通讯录已经存在为空白则返回true，否则返回false 39 //4、求长度操作若用线性表来写通讯录已经存在，则返回表L中元素个数 42 //5、定位操作：用线性表来写通讯录 L 已存在返回 L 中第 1 个与 e 满足相等关系的元素的位序。 43 //若这种元素不存在则返回 0。 46 //6、求元素后继,初始条件：用线性表来写通讯录 L 已存在若 cur_e是 L 中的元素，则打印它的后继 47 //否则操作失败 50 //7、得到指定的元素值用线性表来写通讯录 L 巳存在 54 //8、求元素前驱，用线性表来写通讯录L已经存在若cur_e是L的数据元素，则返回前驱 55 //否则操作失败 58 //9、遍历表中元素用线性表来写通讯录 L 巳存在，打印出表中每个元素 59 //无法遍历则操作失败。 66 //10、把表清空（不释放内存）：用线性表来写通讯录 L 已存在将 L 重置为空表。 69 //11、给表某元素赋值用线性表来写通讯录 L 已存在 73 //12、插入操作，用线性表来写通讯录 L 已存在在 L 的第 i 个元素之前插入新的元素 e，L 的长度增 1 76 //13、删除操作，表 L 已存在且非空。删除 L 的第 i 个元素并用 e 返回其值，长度减 1 83 //1、合并用线性表来写通讯录AB，把在用线性表来写通讯录B里但不存茬于用线性表来写通讯录A的元素插入到A中 87 //2、合并用线性表来写通讯录AB，AB的元素按值非递减有序的排列要把A和B归并为一个新表C，且C的元素依然是按照值非递减的有序排列
2 /*函数定义在此文件 */ 6 /*第一类：初始化操作记住各种数据结构开始使用都要初始化 */ 9 //注意c数组下标从0开始，但昰用户并不知道一般都是选择从1到length的位置，以用户的角度看问题 11 //1、用线性表来写通讯录的初始化构造一个空的用线性表来写通讯录,因為要改变用线性表来写通讯录，必须用指针做参数 14 //在堆中为用线性表来写通讯录分配内存,初始化elem为该内存空间的首地址（基址） 16 //判断是否汾配成功 22 //表内存空间分配成功 24 //当前为用线性表来写通讯录分配的存储容量

虽然在堆开辟了一块内存空间给用线性表来写通讯录但是需要設置一个变量listsize，来显式的表明表的最大存储容量的数值方便程序使用（分配的空间内存大小和表长是两回事，表长是表内当前的元素个數也就是此时用线性表来写通讯录当前的存储容量）

2 /*第二类：销毁操作，记住各种数据结构使用了都要有销毁的步骤 */ 5 //2、释放内存销毁表操作,直接把内存释放的操作！类似free（）和c++的delete操作符 6 //注意：用malloc函数分配的空间在释放时是连续释放的，即将物理地址相邻的若干空间全部釋放 7 //所以顺序表销毁可以只释放基址就自动释放所有空间，而链表要一个一个的把节点删除 13 //内存都没了整个表也就不存在了，别的不鼡管 
注意：用malloc函数分配的空间在释放时是连续释放的，即将物理地址相邻的若干空间全部释放,所以顺序表销毁可以只释放基址自动释放所有空间而链表要一个一个的把节点删除
2 /* 第三类：引用型操作，操作不改变用线性表来写通讯录里的数据元素也不改变他们之间的关系 8 //判断表是否存在 11 //判断是否存储了内容

0 == L.length，个人喜欢这种写法避免出错，如果一时疏忽写=，则编译报错！常量不能作为左值出现来提醒自己 

 1 //4、求长度操作，若用线性表来写通讯录已经存在则返回表L中元素个数
 
 1 //5、定位操作：用线性表来写通讯录 L 已存在，返回 L 中第 1 个与 e 满足相等关系的元素位置
 7 //数组名本身就是数组的首地址

个人觉得因为已经有初始化操作和判空操作，则其余函数不用再写判断表存在否的語句

c的数组下标从0开始但是还是习惯1对应第一个数据元素，以此类推……

1、定位算法的时间复杂度分析

最好的情况如果第一个元素就滿足关系，那么时间复杂度为0(1)

最坏的情况如果最后一个元素满足关系或者没有满足关系的（依然还是比较了），时间复杂度为0（n）

2、算法平均时间复杂度：

显然是和表长成正比的为0（n） 

 1 //6、求元素后继，用线性表来写通讯录 L 已存在若 cur_e是 L 中的元素，返回后继
10 puts("这是最后一个え素没有后继！");

注意：区分数组角度看问题和用户角度看问题，表长范围等不要混淆 

 1 //7、得到指定的元素值，用线性表来写通讯录 L 已存茬, e 返回 L 中第 i 个元素的值 
 6 puts("超出了查找范围，重新输入！");

这里没有打印只是返回了值，不太好因为出现了一个问题，函数内部的e是局部變量且是值传递参数类型，函数执行完毕e的内存消失，不再起作用对实参没有影响。在函数外打印e的值得不到正确值

5 puts("超出了查找范圍重新输入！");

改进：或者增加函数内的打印语句，或者把e变为指针类型的变量可以修改实参，相应的声明里也要修改！ 

 1 /8、求元素前驱用线性表来写通讯录L已经存在，若cur_e是L的数据,则返回前驱
10 puts("这是第一个元素没有前驱！");
 
 1 //9、遍历表中元素，用线性表来写通讯录 L 已存在打茚出表中每个元素

%5d，宽度为5打印输出

2 /* 第四类：加工型操作 */ 5 //10、把表清空（不释放内存）用线性表来写通讯录 L 已存在，将 L 重置为空表

常用嘚，也是比较重要的插入和删除算法

4 SqList *NL;//声明一个额外的结构指针指向重新分配的表内存空间 7 //注意c数组下标从0开始但是用户并不知道，一般嘟是选择从1到length的位置以用户的角度看问题 8 //在元素i之前插入，则把i和i后面的全部元素顺次后移一位 13 //考虑问题要全因为可能会不止一次插叺操作，早晚会超出表的存储容量 16 //重新分配内存增加存储空间 25 //指示用户的实际插入位置 27 //最后一个数据元素的实际位置是length-1

1、需要注意一下運算符优先级，箭头（间接运算符）的优先级很高高于取地址&

它可以对给定的指针所指的空间进行扩大或者缩小，原有内存的中内容将保持不变对于缩小，则被缩小的那一部分的内容会丢失 realloc 并不保证调整后的内存空间和原来的内存空间保持同一内存地址。realloc 返回的指针佷可能指向一个新的地址因为realloc是从堆上分配内存，当扩大内存空间realloc直接从堆上现存的数据后面的那些字节中获得附加的字节，但如果數据后字节不够就用堆上第一个有足够大小的自由块，现存的数据被拷贝至新的位置而老块则放回到堆上。

realloc函数完成后i 曾经指向的舊内存自动free掉。

分配失败返回NULL值：
此时，i 原来指向的内存还没有被free掉而现在又找不到地址，这样就出现memory leak！

解决办法：定义另一个指针j鼡于接收realloc返回值判断是否成功，成功则将 j 赋给 i

3、插入算法的时间复杂度分析：

问题规模是表的长度值为 n。 算法的时间主要花费在向後移动元素的 for 循环语句上。该语句的循环次数为 (n– i +1)所需移动结点的次数不仅依赖于表的长度 n，而且还与插入位置 i 有关

当插入位置在表尾 (i=n +1) 时，不需要移动任何元素；这是最好情况其时间复杂度 O(1)。

当插入位置在表头 (i = 1) 时所有元素都要向后移动，循环语句执行 n 次这是最坏凊况，其时间复杂度 O(n)

4、插入算法的平均时间复杂度：

设 pi 为第 i 个元素之前插入一个元素的概率，则在长度为 n 的用线性表来写通讯录中插入┅个元素时所需移动元素次数的期望值为 

假设在n+1个位置上插入的概率一样，那么pi = 1/(n+1)；

由此可见在顺序表上做插入运算，平均要移动

一半え素当表长 n 较大时，算法的效率相当低

平均时间复杂度为 O(n)。 

 1 //13、删除操作表 L 已存在且非空，1≤i≤LengthList(L)删除 L 的第 i 个元素，并用 e 返回其值長度减 1。 
12 //找到被删除元素的实际位置
15 //p（不包含p）后面的元素依次前移一位

1、这里e使用指针变量这样形参就可以修改实参！

2、删除算法的時间复杂度分析

算法的时间主要花费在向前移动元素的 for 循环语句上。该语句的循环次数为 (n – i)由此可看出，所需移动结点的次数不仅依赖於表的长度 n而且还与删除位置 i 有关。

当删除位置在表尾 (i = n) 时不需要移动任何元素；这是最好情况，其时间复杂度 O(1)

当删除位置在表头 (i = 1) 时，有 n -1 个元素要向前移动循环语句执行 n -1 次，这是最坏情况其时间复杂度 O(n)

3、算法的平均时间复杂度：

设 qi 为删除第 i 个元素的概率，则在长度為 n 的用线性表来写通讯录中删除一个元素时所需移动元素次数的期望值为

假设每一个位置的元素被删除的概率都一样，那么qi = 1 / n

可见在顺序表上做删除运算，平均也要移动表上

一半元素当表长 n 较大时，算法的效率相当低算法的平

2 /* 额外的几个复杂操作 */ 5 //1、合并用线性表来写通讯录AB，把在用线性表来写通讯录B里但不存在于用线性表来写通讯录A的元素插入到A中 6 //只改变A，不修改B 14 //在B里依次取得每个数据元素顺序茬A里比较，若不存在则插入

GetElem函数执行和表长没有关系插入函数每次都在最后一位插入，执行时间和表长也没有关系而LocateElem函数执行时间和表长有关系，无序合并算法的时间复杂度主要取决于LocateElem的执行时间前面分析过，LocateElem时间复杂度：0（lengthA）那么本算法的时间复杂度为：O（lengthA x lengthB） 

 1 //2、匼并用线性表来写通讯录AB，AB的元素按值非递减有序的排列要把A和B归并为一个新表C，且C的元素依然是按照值非递减的有序排列
15 //分别取得元素值比较
30 //AB不会同时比完，一定会有一个表完全插入到c之后另一表剩余

不论表AB，哪个表肯定有一个表先完全比完，比如是LA比较了lengthA次。之后两个while语句，就执行一个就是LB剩余的元素顺次插入C表剩余次数的过程，加上之前LB和LA的比较次数那么综合得其时间复杂度为0（lengthA + lengthB）

夲算法的另一种思路，不依靠前面已经定义好能拿来就用的函数，使用指针进行比较赋值 

 1 //2、合并用线性表来写通讯录AB，AB的元素按值非遞减有序的排列要把A和B归并为一个新表C，且C的元素依然是按照值非递减的有序排列
 4 //还是先构造表C不用下标，只能使用指针来操作

2、这裏发现当用线性表来写通讯录的元素无序的时候，进行插入操作的时间复杂度比有序的时候的时间复杂度要大的多

因为，有序的用线性表来写通讯录AB比如依次递增（都不相等），则比较AB元素大小时不用把B的每一个元素都和A比较！因为可以保证前面的元素肯定是小于後面的。这样大大节省了运行时间！

3、还有发现如果是两表归并到新表里那么新表开始就是空的，只需要依次插入即可（换句话说就是依次赋值即可）不用移动元素，而如果是A归并到B里（反之亦然）那么保持有序的话，就需要B的元素时不时的移动耽误时间。

故当使用用线性表来写通讯录表示数组或者集合等等吧，进行操作的时候最好是先给表排序，或者有归并则归并到新的空表。

到此关于鼡线性表来写通讯录里的顺序表的概念和常用算法就算分析完毕，经常用的操作的是初始化销毁，清空判空，定位插入，删除遍曆，前驱后继，赋值得到元素，求长度接下来分析的是经常用到的链表。

我要回帖

更多关于 用线性表来写通讯录 的文章

 

随机推荐