数据结构学习笔记一_l指向length=maxsize

一.线性表的顺序存储的结构代码

#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

Status ListDelete（Sqlist *L, int  i,  ElemType *e）

{

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 ;

}