线性表
数据结构Data Structure
是指相互之间具有(存在)一定练习(关系)的数据元素的集合。
管理大量数据的方法。数据多到一定程度。
数据结构分为逻辑结构和存储结构。
逻辑结构，人对数据分析的结果，不存在于计算机中。
1.元素之间的相互联系(关系)
2.四种基本类型，根据元素之间关系的复杂度进行的分类。
2.1集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。
2.2线性结构：结构中的数据元素之间存在一对一的关系。
2.3树型结构：结构中的数据元素之间存在一对多的关系。
2.4图状结构或网状结构：结构中的数据元素之间存在多对多的关系。
存储结构，数据在计算机(内存、外存)中如何实际存放。
1.顺序存储结构：用数据元素在存储器中的相对位置(数组的下标)来表示数据元素之间的逻辑结构(关系)。所有数据元素都在一起。数组。
2.链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。链表。
逻辑结构 物理结构
线性表 顺序、链式
树 链式 (顺序的应用较少)
图 复合(同时使用顺序和链式)
数据的逻辑结构
线性结构 非线性结构
受限线性表 线性表推广 集合 树形结构 图状结构
一级线性表 栈和队列 串 数组 广义表 一般树 二叉树 有向图 无向图
最终要用程序说话。
数据结构的运算
1.建立 Create 建立数据结构
2.销毁 Destroy 不需要时一定要销毁
3.插入 Insert 插入一个新元素
4.删除 Delete 删除一个元素
5.修改 Modify 修改一个元素的值
6.查找 Search 找一个数据
7.访问 Access 取出数据
8.排序 Sort 按升序、降序进行排序
一、线性表
1.线性结构 一维 x轴
1.1是最常用、最简单的一种数据结构。
1.2基本特点是，线性表中的数据元素是有序且有限的。
2.在这种结构中：
2.1存在一个唯一的被称为“第一个”的数据元素
2.2存在一个唯一的被称为“最后一个”的数据元素
2.3除第一个元素外，每个元素均有唯一一个直接前驱
2.4除最后一个元素外，每个元素均有唯一一个直接后继
二、线性表的顺序存储
1.使用数组来描述顺序表
大小为表容量 ListSize
放数据的部分，称为表区，a[0],a[1]……a[n-1]
没有放元素的区域，称为空闲区，一直到a[ListSize-1]
当没有空闲区时，称顺序表满了，不能再存放数据。
/*
程序的格式非常重要！要规范！不能随意！
*/
#include
typedefint DataType;//要起别名的类型，起的别名，int和DataType是等效的
#define LISTSIZE 100//表容量
struct SeqList
{
DataType data[LISTSIZE];//存顺序表的元素
int nLength;//表的长度表区中元素的个数
};
int listLength(SeqList *list);//求表长
DataType getNode(SeqList list,int index);//查找
int locateNode(SeqList *list,DataType x);//定位一个节点
bool insert(SeqList *list,int index,DataType x);//指定位置，插入元素
bool insert(SeqList *list,DataType x);//尾部插入
bool erase(SeqList *list,int index);//删除指定位置的元素
bool set(SeqList *list,int index,DataType x);//修改指定位置的元素值
void trave(SeqList *list);//遍历表中的所有元素
int listLength(SeqList *list)
{
return list->nLength;
//如果用值传递，运行速度非常慢，占用内存非常多，所以用地址传递。
}
DataType getNode(SeqList list,int index)
{
if (index < 0 || index > (list->nLength) - 1)
{
returnNULL;//表示出错
}
return &(list->data[index]);
//返回这个数组元素的地址,区分是错误还是正确的数据
}
int locateNode(SeqList *list,DataType x)//第二个参数是需要定位的元素
{
//从顺序表的第一个元素开始对比，直到顺序表的最后一个元素，遍历数组
for (int i = 0; i < list->nLength; i++)
{
//逐个元素进行对比
if (x == list->data[i])
{
return i;
//找到了，返回在顺序表中的位置，终止循环退出函数，得到index
}
}
//如果始终没有找到x，返回-1
return -1;
}
bool insert(SeqList *list,int index,DataType x)
{
//从最后一个元素开始下移，占用空闲区的位置，最后空出元素需要插入的位置
if (list->nLength == LISTSIZE)
{
//如果线性表已满，则不可插入，直接退出，返回false表示插入失败
returnfalse;
}
//规范插入位置，从0到最后一个元素
int insertPosition = index;//中间变量，保存插入位置
if (index < 0)//插入位置越界
{
insertPosition = 0;//认为是要插入在第一个位置
}
if (index > list->nLength - 1)//插在最后一个元素下面，越界
{
insertPosition = list->nLength;
}
//向下移动元素
for (int i = list->nLength - 1; i >= insertPosition; i--)
{
list->data[i+1] = list->data[i];//向后移
}
//插入元素,之前的准备工作1.表不能满2.位置需要规范3.要空出这个位置
list->data[insertPosition] = x;
//一定记住，表长需要+1
list->nLength++;
//返回值是插入成功与否
returntrue;
}
bool insert(SeqList *list,DataType x)
{
//调用前一个参数，把具体位置指定为尾部
//函数重载，允许函数名相同，但要求参数类型或个数不能相同
returninsert(list, list->nLength, x);
}
bool erase(SeqList *list,int index)
{
//从要删除的位置开始，依次由后一个元素向前替换，直到最后一个元素
//与插入的循环方向相反
//判断index是否在表区
if (index < 0 || index >= list->nLength)
{
returnfalse;
}
//开始删除边界问题，注意！
for (int i = index; i < list->nLength - 1; i++)
{
list->data[i] = list->data[i + 1];
}
//同插入，涉及了表长的修改，一定要减1
list->nLength--;
//返回删除成功与否
returntrue;
}
bool set(SeqList *list,int index,DataType x)
{
//容错保护
if (index < 0 || index > list->nLength - 1)
//或if (index < 0 || index >= list->nLength)
{
returnfalse;
}
list->data[index] = x;
//返回修改成功与否
returntrue;
}
void trave(SeqList *list)
{
for (int i = 0; i < list->nLength; i++)
{
printf("第%d个数组元素是%d\n",i,list->data[i]);
/*if (0 == (i + 1) % 10)
printf("\n");*/
}
}
int main(int argc, constchar * argv[])
{
SeqList a;//与C不同，可以省略struct
//用类型声明变量 SeqList a;和int a;是一样的，存储空间不一样
//数据结构在定义一个变量后都不进行初始化，以后不要考虑初始化的问题
//元素的增删由专门的函数进行
printf("表长:%d\n",listLength(&a));
//插入一些数据
insert(&a, 10);
insert(&a, 20);
insert(&a, 30);
insert(&a, 2, 40);
insert(&a, 2, 50);
insert(&a, 2, 60);
insert(&a, 0, 80);
insert(&a, 100);
printf("表长:%d\n",listLength(&a));
trave(&a);
//定位数据
printf("50在表中第%d个位置\n",locateNode(&a, 50));
//获取指定位置的数据
DataType *p = getNode(&a, 4);
printf("%d\n",*p);
//删除元素
erase(&a, 0);
printf("80在表中第%d个位置\n",locateNode(&a, 80));//-1
erase(&a, 6);//删除最后一个元素仅仅修改了nlength的值
trave(&a);
//修改元素
p = getNode(&a, 0);
printf("修改前，%d\n",*p);//修改前，是10
set(&a, 0,111);
p = getNode(&a, 0);
printf("修改后，%d\n",*p);//修改后，111
trave(&a);
//遍历
trave(&a);
/*
int i = 0;
for (i = 0; i < LISTSIZE; i++)
{
printf("%d\t",a.data[i]);
if (0 == (i+1) % 10)
{
printf("\n");
}
}*/
return0;
}
三、线性表的链式存储
顺序表的问题：
1.顺序表中存在着空闲区。有内存浪费。如果取消空闲区，则表满，不可插入。所以空闲区必须预留，所以必须浪费内存。
2.使用数组时，数组有一个要求：必须先定义数组的大小。而一个程序中，如果数组大小已被定义，则说明这个程序没有扩展性，使用时必须修改源程序并重新编译。扩展性不好。
3.顺序表插入、删除元素太费时间。需要移动大量的元素。
顺序表的查找非常快。二分法查找也很快。
线性链表：
1.用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。（解决了空闲区的问题。有一个数据就申请一块空间存储。）
2.存储链表中结点的一组任意的存储单元是连续的或不连续的，甚至是零散分布在内存中的任意位置。（也解决了扩展性的问题。不管增加多少都可以存储。）
3.为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了两边中的结点结构。（不需要循环。）
链表的问题：逻辑顺序和物理顺序(存储顺序)不一样，导致要找到其中一个元素时无法找，增加一个指针，指向下一个数据，解决这个问题。
注意！要学会画链表，结点：data|next
4.链表时通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。最后一个结点的指针域为NULL。
5.每一个结点只包含一个指针域的链表，称为单链表。双向链表：每个结点还有一个指针指向前一个结点。
6.为操作方便，总是在链表的第一个结点之前附设一个头指针head指向第一个结点。
*指针的指针
int a = 10; //变量a中存储的是10
int p = &a; //变量p中存储的是a的地址，p就是a，10
int p1 = &p; //变量p1中存储的是p的地址，*p1就是p，a的地址；p1就是a，10
(p1) —> a
