终于可以开始填这个坑了233333
————————————
像上一篇文章说的数据结构要解决的问题是数据如何在内存中存储，以什么结构存储。
用张仰森老师的话来说，就是“数据以及数据之间的关系。”
今天主要要聊的就是线性结构。
这里说的线性结构，是指从逻辑结构上来划分的。
说到这，就不得不提下物理结构。所谓逻辑结构，就是在逻辑、理论上定义的结构，而物理结构是指在实际的内存中数据的存储结构。
比如，有这么一种结构，每个元素只有唯一的前驱、唯一的后继、第一个元素没有前驱、最后一个元素没有后继。满足这样要求的结构就是线性结构。
而上面所说的结构仅仅是逻辑上的结构，而不是物理上的结构。之前已经学过的数组、链表，都可以表示这种结构。但是数组在物理结构上来说每个元素就是相邻摆放的，而链表的节点在实际内存中的分布却是分散的，仅仅是由于指针的存在好像使得前后有了关系。
C语言已经内置支持了最简单的线性结构，就是数组。
声明一个数组之后，就能得到N个相邻的物理空间。这N个空间中的变量就满足之前说的规律。
而概念里说的元素，可以是一个int，也可以是一个结构体。在本系列文章或者代码、我通常会用一个整数来代表一个元素。
而实际的应用中，一个元素可能是一个结构体、指针(最常见的是结构体的指针)。
说完了数据和数据之间的个关系，那么这个数据结构就已经快说完了，还差对应的一系列操作。
这里仅列出简单的几个操作，也就是增删改查，实际实现时候包括但不限于以下几种，候根据需要来写。
向线性表插入一个元素
从线性表删除一个元素
从线性表中查找关键字为i的元素
修改线性表中某个元素
套路：确定操作之后如何开始写代码
0.定义自己的数据结构(这里以C为例，所以写的是结构体。不排除以后用Java类的可能性=-=)
然后对每个操作按下面四个步骤
1.确定函数名、参数类型、参数数量
2.预想函数执行前内存的状态
3.确定函数执行后预期的内存状态
4.返回值类型极其含义
接下来将以两种实现方式进行说明，参考代码在github(求star求follow)：
第一种：用数组实现的线性表
头文件：https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.1.linearlist.h
源文件：https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.1.linearlist.c
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
#ifndef LinearList1_h #define LinearList1_h #include<stdlib.h> struct _list{ int lenth; int* elements; }; typedef struct _list List; List createList(int lenth); int get(List* l, int index); int set(List* l, int index, int x); int indexOf(List* l, int x); void add(List* l, int x); void insertInto(List* l, int index, int x); void deleteElementAt(List * l, int index); int getLength(List* l); void printAll(List* l); #endif |
0.定义一个新的类型，叫List
//我默认大家都能看懂C语言，看不懂的请回上一篇看基础测试或者重新看下C的教程=-=
如上面代码中5-9行所示，我把一个数组和数组的长度定义为一个List。
createList,创建一个列表，
参数：长度
执行前状态：无
执行后状态：初始化一个指定长度的List
返回值定义 返回一个List
其他的同理。。。。
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 |
/*线性表，数组实现*/ #include <stdio.h> #include "1.1.linearlist.h" int main(){ List tlist; List* list = &tlist; int i = 0; printf("创建空表：\n"); tlist = createList(10); printAll(list); printf("表长为%d\n", getLength(list)); printf("设置元素：\n"); for (i = 0; i < getLength(list); i++) set(list, i, i); printAll(list); printf("删除第3个：\n"); deleteElementAt(list, 3 - 1); printAll(list); printf("在第1个之前插入一个111：\n"); insertInto(list, 1 - 1,111); printAll(list); printf("在最后1个之前插入一个222：\n"); insertInto(list, getLength(list)- 1, 222); printAll(list); printf("在第6个之前插入一个10：\n"); insertInto(list, 6 - 1, 10); printAll(list); printf("10在第%d个位置：\n\n", indexOf(list, 10) + 1); printf("删除第1个：\n"); deleteElementAt(list, 1 - 1); printAll(list); printf("在最后加入333：\n"); add(list, 333); printAll(list); printf("删除最后1个：\n"); deleteElementAt(list,getLength(list) - 1); printAll(list); system("pause"); return 0; } // 初始化一个长度为lenth线性表； List createList(int lenth){ List list; int i = 0; list.lenth = lenth; list.elements = (int*)malloc(sizeof(int) * lenth); //初始化内容为0 for (i = 0; i < lenth; i++){ list.elements[i] = 0; } return list; } // 根据位序index，返回相应元素,失败返回-1； int get(List* l, int index){ if (index >= 0 && index < getLength(l)){ return l->elements[index]; } else{ return -1; } } // 根据位序index，设置相应元素,失败返回-1； int set(List* l, int index, int x){ if (index >= 0 && index < getLength(l)){ return l->elements[index] = x; } else{ return -1; } } //在线性表l中查找x的第一次出现位置,找不到返回-1 int indexOf(List* l, int x){ int ret = -1; int i = 0; for (i = 0; i < getLength(l); i++){ if (l->elements[i] == x){ ret = i; break; } } return ret; } //在位序index前插入一个新元素x； void insertInto(List* l, int index, int x){ int i = 0; if (index >= 0 && index <= getLength(l)){ l->lenth++;//表长度+1 l->elements = realloc(l->elements, (getLength(l) + 1)* sizeof(int)); for (i = getLength(l) - 1; i > index; i--) //index后面的部分照抄，注意位置 l->elements[i] = l->elements[i - 1]; l->elements[index] = x; } } /*/ //在位序index前插入一个新元素x； void insertInto(List* l, int index, int x){ int *telements = NULL; int i = 0; if (index >= 0 && index < getLength(l)){ l->lenth++;//表长度+1 telements = malloc(sizeof(int) * getLength(l));//分配新的内存空间 for (i = 0; i < getLength(l); i++){//生成插入后新表 if (i < index){//在index之前的元素直接复制 telements[i] = l->elements[i]; } else if (i == index){//等于index时候插入新的x telements[i] = x; } else{//index后面的部分照抄，注意位置 telements[i] = l->elements[i - 1]; } } free(l->elements);//释放旧的内存 l->elements = telements;//换成新的表 } } //*/ //在最后加入一个元素x void add(List* l, int x){ insertInto(l, getLength(l), x); } //删除指定位序index的元素； void deleteElementAt(List * l, int index){ int i = 0; if (index >= 0 && index < getLength(l)){ for (i = 0; i < getLength(l); i++) if (i == index) break; for (; i < getLength(l) - 1; i++) l->elements[i] = l->elements[i + 1]; l->lenth--; } } //返回线性表L的长度n。 int getLength(List* l){ return l->lenth; } //打印所有表元素 void printAll(List* l){ int i = 0; for (i = 0; i < getLength(l); i++) printf("element[%d] = %d\n", i, l->elements[i]); printf("\n"); } |
定义完了函数先写测试程序，如上面的主函数。
然后依次实现每个函数，createList的时候注意，在申请完内存后一定要初始化内存中每个地址的默认值，要么用NULL要么用0要么用参数，不要啥都不做，免得给自己挖坑
其实这也就是构造函数做的事情。。。
（代码中createList的时候其实应该返回指针更好一些，不然会再复制一份函数内部的List再return回去，然而这是很久之前的代码了，我懒得重写了=-=凑合着看吧233333）
代码中的问题(现在看当时写的代码简直是naive=-=)：
风格不是很好。。。比如我省略了一些大括号，这是不好的习惯。。。
容错处理并没有做到最好，有些地方并不是一定会成功的操作我都没有做判断，比如realloc之后的返回值可能为NULL然而我没判断。。。
第二种实现方法，用链表实现线性表：
参考代码我就不贴上来了，去github看吧。。。
地址：
头文件：https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.2.linearlist.h
源文件：https://github.com/956237586/DataStructure-C/blob/master/DataStructure-C/1.2.linearlist.c
这是最基本的线性结构，之后所有复杂的结构都是这两种结构的组合、延伸，说白了再复杂的结构最终也能用这两种形式来组合表达。
其实计算机内存是线性的，所以某种意义上来说，所有的存储都是在把非线性的结构转换成线性结构来表达、然后存储、运算。
建议自己亲手仿写一个自己版本的线性表。。。。
写完后再继续往下看。
刚刚的线性表我们可以对对任意位置、任意元素进行操作。
如果我们加一点点限制，就出现了新的数据结构（其实并不是新的数据结构，只是操作操作受限的线性表而已）
也就是栈、和队列。
如果我们限制只能在一端增加和删除元素，那么就是栈。
如果我们限制只能在一端增加、在另一端删除，那么就是队列。
代码稍稍改一改就能搞定，参考代码地址如下：
https://github.com/956237586/DataStructure-C/tree/master/DataStructure-C
其中2.1是用数组实现的栈。
2.2是用链表实现的栈、也叫链栈。
（待补充详细说明，链栈的部分有个经典写法。。。）
3.1是用数组实现的队列，一般来说为了节省空间，数组会重复利用已有的空余内存，所以一般是循环队列。
（待补充详细说明，循环队列的关键在push和pop如何复用空余空间。。。。）
3.2是用链表实现的队列。(未完待续)
——————————–
今天先写到这=-=之后再继续写。。。。
0 Comments