线性表

定义：是具有相同特性的数据元素的一个有限序列。一般表示为（a1，a2，a3，ai，an）a1为第一个元素，称作表头元素，an为最后一个元素，称作表尾元素

线性表长度：该序列中所含元素的个数。（当元素为零时，线性表是一个空表。）

线性表的运算

初始化线性表InitList（&L）：构造一个空的线性表L。

销毁线性表DestroyList（&L）：释放线性表L占用的内存空间。

判断线性表是否为空表ListEmpty（&L）：若L为空表，则返回真，否则返回假。

求线性表的长度ListLength（L）：返回L中元素个数。

输出线性表DispList（L）：当线性表L不为空时，顺序显示L中各结点的值域。

求线性表中指定位置数据元素GetElem（L，i，&e）：用e返回L中第i个元素的值。

求定位查找LocateElem（L，e）：返回L中第一个值域与e相等的逻辑位序。

若这样的元素不存在，则返回值为0.

插入数据元素ListInsert（&L，i，e）：在L的第i个元素之前插入新的元素e，L的长度增1。

删除数据元素ListDelete（&L，i，&e）：删除L的第i个元素，并用e返回其值，L的长度减1。

实例：

顺序表

定义：把线性表中的所有元素按照其逻辑顺序依次存储到计算机储存器中指定存储位置开始的一块连续的存储空间中。

存储空间大小：n*sizeof（ElemType）

n表示线性表长度，ElemType表示线性表元素类型。

储存方式：结构体，数组。

建立顺序表

实例：

[block]

void CreateList(SqList *&L,ElemType a[],int n)
{
int i;
L=(SqList *)malloc(sizeof(SqList));
for (i=0;i<n;i++)
L->data[i]=s[i];
L->length=n;
}

[/block]

 初始化线性表InitList（&L）

实例：

[block]

void InitList（SqList *&L）
{

L=（SqList *）malloc（sizeof（SqList））；

L-》length=0；

[/block]

此算法时间复杂度为O（0）

销毁线性表DestroyList（&L）

作用：释放线性表L占用的内存空间。

实例：

[block]

void DestroyList(SqList *&L)
{
free(L)
}

[/block]

此算法的时间复杂度为O（1）

判断是否为空表ListEmpty（L）

作用：该运算返回一个值表示L是否为空表。若为空返回true，否则返回false。

实例：

[block]

bool ListEmpty（SqList *L）
{
return（L->length==0);
}

[/block]

此算法的时间复杂度为O（1）

求线性表的长度ListLength（L）

作用：该运算返回顺序表L的长度。

实例：

[block]

int ListLength(SqList *L)
{
return(L->length);
}

[/block]

此算法的时间复杂度为O（1）

输出线性表DispList（L）

作用：该运算当线性表L不为空时，顺序显示L中各元素的值

[block]

void DispList(SqList *L)
{
int i;
if (ListEmpty(L))
return;
for (i=0;i<L->length;i++)
printf("%c",L->data[i]);
printf("\n");
}

[/block]

此算法时间复杂度为：O（L->length)或O（n）

求某个数据元素值GetElem（L，i，&e）

该运算返回L中第i个元素的值，存放在e中。

[block]

bool GetElem（SqList *L，int i，ElemType &e）
{
if （i<1 || i>L->length)
return false;
e=L->data[i-1];
return true;
}

[/block]

此算法的时间复杂度为O（1）

按元素值查找LocateElem（L，e）

作用：该运算顺序查找第1个值域与e相等的元素的逻辑位序。若这样的元素不存在，则返回值为0。

[block]

int LocateElem(SqList *L,ElemType e)
{
int i=0;
while (i<L->length && L->data[i]!=e)
i++;
if (i>=L->length)
return 0;
else
return i+1;

[/block]

本算法时间复杂度为：O（L->Length)或O（n）

插入数据元素ListInsert（&L，i，e）

作用：该运算在顺序表L的第i个位置上插入新的元素e。将顺序表第i个元素及以后元素均后移一个位置，移动方向从右向左，腾出一个空位置插入新元素，最后顺序表长度增1。

实例：

[block]

bool ListInsert（SqList *&L,int i,ElemType e)
{
int j;
if(i<1 || i>L->length+1)
return false;
i--;
for (j=L->length;j>i:j--)
L->data[j]=L->data[j-1];
l->length++;
return true;

[/block]

此算法的平均时间复杂度为O（n）

删除数据元素ListDelete（&L，i，e）

作用：删除顺序表L的第i个元素,将线性表第i个元素以后的元素均向前移动一个位置，移动方向从左向右覆盖原来的第i个元素，达到删除该元素的目的，最后顺序表长度减1。

[block]

bool ListDelete(SqList *&L,int i,ElemType &e)
{
int j;
if (i<1 || I>L->length)
return false;
i--;
e=L->data[i];
for (j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return true;

[/block]

此算法的平均时间复杂度为O（n）

链表

单链表

指针域：在链式存储中，每个存储结点不仅包含有所存元素本身的信息（数据域），而且包含有元素之间逻辑关系的信息，即前驱结点包含有后继结点的地址信息。

单链表：在每个结点中除包含有数据域外，只设置一个指针域，用以指向其后继结点。

线性表到单链表的映射：在线性表的链式存储中，为了便于插入和删除运算的实现，每个链表带有一个头结点，并通过头结点的指针唯一标识该链表。

存储密度：结点数据本身占用的空间/结点占用的空间总量

（存储密度越大，存储空间的利用率就越高）

插入结点：

删除结点：

头插法建表：

[block]

void CreateListF(LinkList *&L,ElemType a[],int n)
{

LinkList *s;

int i;

L=(LinkList *)malloc(sizeof(LinkList));

L->next=null;

for (i=0;i<n;i++)

{

s=(LinkList *)malloc(sizeof(LinkList));

s->data=a[i];

s->next=L->next;

L->next=s;

[/block]

尾插法建表：

[block]

void CreateListR(LinkList *&L,ElemType a[],int n)
{
LinkList *s.*r;
int i;
L=(LinkList *)malloc(sizeof(LinkList));
r=L;
for (i=0;i<n;i++)
{
s=(LinikList *)malloc(sizeof(LinkList));
s->data=a[i];
r->next=s;
r=s;
}
r->next=NULL;
}

[/block]

初始化单链表InitList(&L)

实例：

[block]

void InitList(LinkList *&L)
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}

[/block]

销毁单链表DstroyList（&L）

实例：

[block]

void DestroyList(LinkList *&L)
{
LinkList *pre=L,*p=p->next;
while (p!=NULL)
{
free(pre);
pre=p;
p=pre->next;

[/block]

判断单链表是否为空表ListEmpty(L)

实例：

[block]

bool ListEmpty(LinkList *L)
{
return(L->next==NULL);
}

[/block]

求单链表长度ListLength（L）

作用：返回单链表L中数据结点的个数

实例：

[block]

int ListLength(LinkList *L)
{
int n=0;
LinkList *P=L;
while (p->next!=NULL)
{
n++;
p=p->next;
}
return(n);
}

[/block]

输出单链表DispList（L）

作用：注意扫描单链表L的每个数据结点，并显示各结点的data域值

实例：

[highlight lanaguage="c"]

void DispList(LinkList *L)
{
  LinkList *p=L->next;
  while (P!=null)
  {
    printf("%d",p->data);
    p=p->next;
  }
  printf("\n");
}

[/highlight]

求单链表某个数据元素值GetElem(L,i,&e)

作用：在单链表L中从头开始找到第i个结点，若存在第i个数据结点，则将其data域值赋给变量e。

实例：

[highlight lanaguage="c"]

bool GetElem(LinkList *L,int i,ElemTtpe &e)
{
 int j=0;
 LinkList *p=L;
 while (j<i && p!=NULL)
 { 

[/highlight]

插入数据元素ListInsert(&L,i,e)

作用：先在单链表L中找到第i-1个结点*p，若存在这样的家电，将值为e的结点*s插入到*p的后面

实例：

[highlight lanaguage="语言"]

bool List Insert(LinkList *&L,int i ,ElemType)
{
	int j=0;
	LinkList *p=L,*s;
	while (j<i-1 && p!=NULL)
	{
		j++;
		p==->next;
		
	}
	if (p==NULL)
	return false;
	else
	{
		s=(LinkList *)malloc (sizeof(LinkList));
		s->data=e;
		s->next = p->next;
		p->next=s;
		return true;
		
		
	}
}

[/highlight]

删除数据元素ListDelete（&L,i,&e)

作用：现在单链表L中找到第i-1个结点*p，若存在这样的结点，且也存在后继结点*p，则删除*结点，返回true，否则返回false表示i错误

实例：

[highlight lanaguage="语言"]

[/highlight]

双链表

单链表与双链表的区别：单链表当访问过一个节点后，只能接着访问它的后继结点，而无法访问它的前驱结点。双链表既可以访问它的前驱结点，也可以访问它的后继结点。

定义：在每个结点中除包含有数值域外，设置有两个指针域，分别用以指向其前驱结点和后继结点。

实例：

[block]

typedef struct DNode
{
ElemType data;
struct DNode *prior;//指向前驱结点
struct DNode *next;//指向后继结点
}DLinkList;

[/block]