数据结构学习笔记一
一.线性表的顺序存储的结构代码
#define MAXSIZE 20 /*存储空间初始分配量*/
typedef int ElemType; /*重新定义数据类型*/
typedef struct
{
ElemType data[MAXSIZE];
int length; /*线性表的当前长度*/
}SqList;
数据元素的序号和存放它的数组下标之间的对应关系，如下图所示：
用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入和删除操作，因此分配的数组空间要大于等于当前线性表的长度。
存储器中的每个存储单元都有自己的编号，这个编号称为地址。
由于每个数据元素，不管它是整型，字符型，它都是需要占用一定的存储单元空间的。假设占用的是c个存储单元，那么线性表中的第i+1个数据元素的存储位置和第i个数据元素的存储位置满足以下的关系：
注：c语言中的数组是从0开始的，线性表是从1开始的。
接下来是对线性表的一些操作：
①获取元素的操作
#define OK 1
#define Error 0
#define TRUE 1
#define False 0
typedef int Status;
/*初始条件：顺序表L已经存在
/*操作结果：用e返回L中第i个数据元素的值
Status GetElem(Sqlist L, int i,ElemType *e)
{
if(i<1||i>L.length||L.length==0)
return Error;
else
*e=L.data(i-1);
return OK;
}
②插入操作
/*初始条件：顺序表L已经存在
/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1
Status ListInsert（SqList *L,int i ,ElemType e）
{int k;
if(L->length==MAXSIZE) /* 这里和获取的区别是：不是L.length,而是L->length,因为L是地址*L
return Error;
if(i<1||i>L->length+1)
return Error;
if(i<=L->length)
{
for(k=L->length;k>=i-1;k--)
L->data[k+1]=L->data[k];
}
L->data[i-1]=e;
L->length++;
return OK;
}
③删除操作
/*初始条件：顺序表L已经存在
/*操作结果：删除L中第i个数据元素，并用e返回其值，L的长度减1
{
int k;
if(L->length==0|| i<1 || i>L->length)
return Error;
else
*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;
}
线性表顺序存储的优缺点：
优点：无须为表示表中元素之间的逻辑关系而增加额外的存储空间
可以快速的读取表中的任一位置的元素
缺点： 插入和删除操作需要移动大量的元素
当线性表的长度变化比较大时，难以确定存储空间的容量
造成存储空间的“碎片”
二、线性表的链式存储结构
针对顺序存储，我们知道它的删除和插入需要移动大量的元素，这显然是耗很多时间的。
针对以上问题，我们使用了另外一种存储方式：链式存储方式。如：下图所示：
一个节点包括两个部分，分别是数据域和指针域，数据域存储的是数据元素的信息，指针域是存储的是其后继的位置。
从上图我们可以看到，结点的存储不是按照顺序存储的，它可以随时存储在内存中的任何位置，大大的方便了增加和删除。
我们把链表的第一个结点的存储位置叫做头指针，那么整个链表的存取就是必须从头指针开始进行，那最后一个指针往哪里指呢？
最后一个，当然就意味着后继不存在，所以我们就规定，线性链表的最后一个结点指针设置为空，即null,如下图所示：
我们有的时候，为了方便对链表进行操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，头结点的指针域指向第一个结点的指针，如下图所示：
单链表的c语言结构：
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
p->data=ai; p->data的值是一个数据元素
p->next的值是一个指针。
①单链表的元素获取
由于它的存储方式是任意存放，不是像顺序表顺序存放，所以获取i个元素位置，只能从头开始找。
Status GetElem(LinkList L, int i, ElemType * e)
{
int j;
LinkList p; /声明一个结点 p
p=L->next;
j=1;
While(p !=null && j<i)
{
p=p-next;
++j;
}
if ( !p || j>i)
return error;
*e=p->data;
return OK ;
}