6 # 一 、线性表的定义与理解

• 线性表：零个或者多个数据元素的有限序列。
• 若线性表有N个元素，其中的第i个元素，i-1叫做这个i元素直接前驱元素，i+1叫做这个i元素的直接后继元素，每一个元素有且仅有一个直接前驱和一个直接后继，当线性表中的元素为0时，成为空表。
• 线性表中的每一个元素可以有多个数据项构成，如一个结构体中可以有多个组成的数据项。

struct people
// 数据元素
{
int year;
//数据项
string name; // 数据项
people *next; // 数据项
}

• 在一个线性表中可以有多个线性元素构成，即有多个数据元素构成的数组或者链表。

二、线性表的抽象数据类型

Operatioon :
T InitList（*L）;// 初始化线性表，建立一个空的线性表L，返回头结点
bool ListEmpty（L）;
// 判断一个线性表示否为空，为空返回true 否则返回false
void ClearList（*L）;
// 清空线性表
bool GetList（L，i，*e）;//将线性表上的第i个元素返回给e
int LocateElem（L，e）; //查找与定值e相等的元素，成功为返回的位置，否则返回0；
T ListInsert（*L,i,e）;//在表L上的第i个位置插入元素e,并返回头结点;
void ListDelete（*L,i,*e）;//在表L上删除第i个位置的元素，并将删除元素的数值给e；
int ListLength（L）; //返回线性表L的长度，即元素的个数；

三、线性表的存储结构

1、顺序存储

• 线性表的顺序存储结构是指用一段连续的存储单元依次存储线性表的数据元素。 即为用一段连续的地址存储数据元素。
• 顺序存储的方式：数组存储，
• 数组的长度是数组所占的存储空间的大小除以每个数据元素的空间大小，线性表的长度是数据元素的个数。
• 数组存储的下标是从0开始的，每一个存储单元都有自己的编号。

#define Max
20
typedef struct
{
int data[Max];
int length;
}SqList;

（1）、获得线性表中的元素：

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

（2）、插入线性表中的元素：

bool ListInsert(SqList *L,int i,ElemType e)
{
int k;
if(L->length==Max)
// 判断是否已经达到数组最大的限制
return false;
if(i<i||i>L->Length+1)
// 判断i是否符合在范围内；
return false;
if(i<=L->length)
//判断是否在最后的一点，如果不是则后退让出位置。
{
if(k=L->Length—1;k>=i-1;k--)
L->data[k+1]=L->data[k];
}
L->data[i-1]==e;
L->Length++;
return true;
}

（3）、删除线性表中的元素：

bool ListDelete（SqList *L,int i,ElemType *e);
{
int k;
if(L->length==0)
return false;
if(i<1||i>L->Length)
return false;
*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 true;
}

线性表顺序储存利弊

• 优点:

• 1、无需为表中的元素逻辑关系增加额外的存储空间
  2、可以快速获取表中的任意位置的元素

• 缺点:

• 1、插入和删除的操作需要移动大量的元素
  2、线性表变化过大的时候难以确定存储空间。
  3、产生存储空间碎片。

2、链表存储（链表结构体存储）

• 链表存储中一共有n个元素，对于其中的第i个元素，这一个元素除了存储第i个元素本身的信息之外，还要存储后面一个元素的位置，把一个元素存储自身信息的域称为数据域，把存储直接后继位置的域称为指针域。其中这样的一个元素称之为结点。
• 把链表中第一个结点的存储位置叫做头指针，有时候为了方便会在单链表的第一个结点前附设一个结点，称之为头结点，。
• 头指针：
  1、链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
  2、头指针具有标识作用，所以常用头指针冠以链表的名字。
  3、无论链表是否为空，头指针均不为空，头指针是链表必要的元素。
• 头结点：
  1、为了操作的统一和方便而设立的，放在第一元素的结点之前。
  2、数据域一般没有意义，也能用来表示链表的长度。
  3、头结点方便了对链表的前插入结点和删除第一结点，头结点不一定是链表的必要元素。

结点的代码表示：

创建结构体结点，并新建链表头指针；

typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
Node *LinkList;

（1）、获得线性表中的元素：

bool
GetElem（SqList L，int t，ElemType *e）
{
int j;
LinkList p; // 声明指针P
p = L->next; //p指向链表L的第一个结点
j = 1;
// 计数器
while(p&&j<i)
{
p=p->next;
++j;
}
if(!p||j>i)
return false;
*e = p->data;
return true;
}

（2）、插入线性表中的元素：

bool ListInsert(SqList *L,int i,ElemType e)
{
int j;
LinkList p,s;
p = *L;
j=1;
while(p&&j<i)
{
p=p->next;
+j;
}
if(!p||j>i)
return false;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
// e的值赋值给s的数据域
s->next = p->next; // 插入结点s将p的下一个的地址赋值给s的指针域；顺序不能改变!!!
p->next = s; // 改变P的指针域，使之指向s; 
return true;
}

（3）、删除线性表中的元素:

bool ListDelete（SqList *L,int i,ElemType *e);
{
int j;
LinkList p,q;
p = *L;
j = 1;
while(p->next && j < i)
{
p = p->next;
++j;
}
if(!(p->next)|| j>i)
return false;
q = p->next;
// 用q来存储要删除结点的位置
p->next = q->next;
// 更新p的结点指针域
*e = q->data;
free(q);
// 释放 q 
return true;
}

• 优点：

1:采用不联系的存储方式，降低了对内存的要求。
2：方便了存储，对顺序结构的插入和删除都在性能上有了很大的提升；

• 缺点：

1: 在查找上的性能比较弱，不如顺序存储的时间效率高。

3、静态链表

• 用数组描述的链表叫做静态链表；

#define Max 1000
typedef struct
{
ElemType data;
// 数据域
int index;	// 指针域，用来记录数组的下标，指向下一个元素的下标
}

（1）静态链表的查找：

与线性存储的查找相同，进行遍历，同时查找；

（2） 静态链表的插入：

int Malloc_SSL(StaticLinkList space)
{
int i = space[0].index;
if(space[0].index)
space[0].index = space[i].index;
return i;
}
bool ListInsert(SqList *L,int i,ElemType e)
{
int j,k,l;
k = Max-1；
// k是最后一个元素的下标
if(i<1||i>ListLength(L) +1)
// 如果i不满足条件，则返回错误：
return false;
j = Malloc_SSL(L);
// 获得空闲分量的下标
if(j)
// 还有空闲分量的进行；
{
L[i].data = e;
for(l=1;l<=i-1;l++)
//找到第i个元素的之前的位置。
k = L[k].index;
L[i].index = L[k].index; // 把第i个元素之前的位置index 赋值给新元素的位置。
L[k].index = j;
// 把新元素的下标赋值给第i个元素的指针域处；
return true;
}
return false;
}

（3）删除线性表中的元素:

void Free_SSL(StaticLinkList space, int k)
{
space[K].index = space[0].index;
space[0].cur = k;
}
bool ListDelete（SqList *L,int i,ElemType *e);
{
int j,k;
if(i<1||i>ListLength(L))
return false;
k = Max-1;
for(j = 1;j<=i-1;j++)
k = L[k].index;
j =L[k].index;
L[k].index = L[j].index;
Free_SSL(L,j);
return true;
}

• 优点：

• 在插入和删除操作时，只需修改游标不需要移动元素；

• 缺点：

• 没有解决连续存储带来的问题，失去了顺序存储的特性；

循环链表

• 将单链表中终端结点的指针端由空指针改向指为头结点，就使单链表形成一个环，这种头尾相接的单链表称为单循环链表，简称循环链表。

双向链表

• 在单链表的每个结点中，设置一个指向前驱结点的指针域。这样每一个结点（除了头尾结点）都有可以访问其前驱结点和后继结点。

最后

以上就是开朗口红为你收集整理的数据结构—线性表概述二、线性表的抽象数据类型三、线性表的存储结构的全部内容，希望文章能够帮你解决数据结构—线性表概述二、线性表的抽象数据类型三、线性表的存储结构所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。