目录
一，写在前面
到了下午放学的时候，我们会看到这样一幕，幼儿园的小朋友排队整齐的出校门，外面的家长乱糟糟站在外面，小朋友们有序的排队，就相当于我们在数据结构里面的线性表。
?二，线性表的定义
线性表,从名字上你就能感觉到,是具有像线一样的性质的表。在广场上,有很多人分散在各处,当中有些是小朋友,可也有很多大人,甚至还有不少宠物,这些小朋友的教抿对干整个广场人群来说,不能算是线性表的结构。但像刚才提到的那样,一个班级的小朋友,一个跟着一个排看队,有一个打头,有一个收尾,当中的小朋友每一个都知道他前面一个是谁,他后面一个是谁,这样如同有一根线把他们串联起来了。就可以称之为线性表。
线性表(?List?):零个或多个数据元素的有限序列。这里需要强调几个关键的地方。
首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他每个元素都有且只有一个前驱和后继。如果一个小朋友去拉两个小朋友后面的衣服,那就不可以排成一队了;同样,如果一个小朋友后面的衣服,被两个甚至多个小朋友拉扯,这其实是在打架,而不是有序排队。然后,线性表强调是有限的,小朋友班级人数是有限的,元素个数当然也是有限的。事实上,在计算机中处理的对象都是有限的,那种无限的数列,只存在于数学的概念中。
如果用数学语言来进行定义。可如下:
若将线性表记为( a1,....a(i-1),a(i),a(i+1),....,a(n)),则表中?a (i-1)领先于a(i) ,?a(i)领先于? ? ? ? ? ? ? ? ? ? a(i+1)?称?a(i-1) 是?a(i) 的直接前驱元素,?a(i+1) 是?a(i) 的直接后继元素。当i=1,2,…,?n-1时,?a(i)有且仅有一个直接后继,当i =2,3,…,?n?时,?a(i) 有且仅有一个直接前驱。如下图所示。
三，线性表的抽象数据类型
前面我们已经给了线性表的定义,现在我们来分析一下,线性表应该有一些什么样的操作呢?
还是回到刚オ幼儿园小朋友的例子,老师为了让小朋友有秩序地出入,所以就考虑给他们排一个队,并且是长期使用的顺序,这个考慮和安排的过程其实就是一个线性表的创建和初始化的过程。一开始没经验,把小朋友排好队后,发现有的高有的矮,队伍很难看,于是就让小朋友解散重新排一这是一个线性表重置为空表的操作。
排好了队,我们随时可以叫出队伍某一位置的小朋友名字及他的具体情况。比如有家长问,队伍里第五个孩子,怎么这么调皮,他叫什么名字呀,老师可以很快告诉这位家长。这种可以根据位序得到数据元素也是一种很重要的线性表操作。
还有什么呢?有时我们想知道,某个小朋友,比如麦兜是否是班里的小朋友,老师会告诉我说,不是,麦兜在春田花花幼儿园里,不在我们幼儿园。这种查找某个元素是否存在的操作很常用。而后有家长问老师,班里现在到底有多少个小朋友呀,这种获得线性表长度的问题也很普遍。显然,对于一个幼儿园来说,加入一个新的小朋友到队列中,或因某个小朋友生病,需要移除某个位置,都是很正常的情况。对于一个线性表来说,插入数据和删除数据都是必须的操作。
ADT性表(?List?)
Data?
线性表的数据对象集合为(a1,a2,a3,....a(n)),每个元素的类型均为?DataType?。其中,除第一个元素?a1,外,毎一个元素有且只有一个直接前驱元素,除了最后一个元素?a(n) ,外,每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。
?Operation?
? ? ? ? ? ? ? ? InitList?(*?L?):初始化操作,建立一个空的线性表?L?。
? ? ? ? ? ? ? ? ListEmpty?(?L?):若线性表为空,返回?true?,否则返回?false 。? ? ? ? ? ? ? ? ClearList?(*?L?):将线性表清空。
? ? ? ? ? ? ? ? GetElem?(?L?,?i?,*e?):将线性表中的第1个位置元素値返回给?e?。
? ? ? ? ? ? ? ? ?LocateElem?(?L?,?e?):在线性表ム中查拨与给定値?e?相等的元素,如果查找成功,返回该元素在表中序号表示成功;否则,返回0表示失败。
? ? ? ? ? ? ? ? ListInsert?(*L?,?i?,?e?):在线性表中的第1个位置插入新元素?e?。
? ? ? ? ? ? ? ? ListDelete?(*?L?,?i?,*?e?):瀏除线性表中第1个位置元素,并用?e?返回其值。?? ? ? ? ? ? ? ? ListLength?(1):返回线性表?L?的元素个数。
endADT
对于不同的应用,线性表的基本操作是不同的,上述操作是最基本的题中涉及的关于线性表的更复杂操作,完全可以用这些基本操作的组合来实现。
比如,要实现两个线性表集合?A?和?B?的并集操作。即要使得集合?A?=?AUB 就是把存在集合?B?中但并不存在集合?A?中的数据元素插入到集合?A?中即可。
仔细分析一下这个操作,发现我们只要循环集合?B?中的每个元素,判断存在集合?A?中,若不存在,则插入到集合?A?中即可。思路应该是很容易想到
我们假设?La?表示集合?A?,?Lb?表示集合?B?,则实现的代码如下:
/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void unionL(SqList* La, SqList Lb)
{
int La_len, Lb_len, i;
ElemType e; /*声明与La和Lb相同的数据元素e*/
La_len = ListLength(*La); /*求线性表的长度 */
Lb_len = ListLength(Lb);
for (i = 1; i <= Lb_len; i++)
{
GetElem(Lb, i, &e); /*取Lb中第i个数据元素赋给e*/
if (!LocateElem(*La, e)) /*La中不存在和e相同数据元素*/
ListInsert(La, ++La_len, e); /*插入*/
}
}注意：
当你传递一个参数给函数的时候,这个参数会不会在随数内被改动决定了使用什么参数形式。
如果需要被改动,则需要传递指向这个参数的指针。
如果不用被改动,可以直接传递这个参数。
四，线性表的顺序存储结构
4.1，顺序存储的定义
线性表的顺序存储结构，指用的是用一段地址连续的存储单元依次存储线性表的数据元素。
线性表如下：
?4.2，顺序存储方式
线性表的顺序存储结构，说白了，就是在内存中找一块，通过占有的方式，把一定内存空间给占了，然后依次把相同的数据类型的数据元素依次存放在这块空地中，数据类型相同。建立一个线性表，起始位置，最大存储容量，增加数据，删除数据等非常重要。
来看线性表的顺序存储代码：
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}SqList;注意：
存储空间的起始位置：数组data，他的存储位置就是存储空间的起始位置。
线性表的最大存储容量：数组长度MAXSIZE。
线性表当前的长度：length。
4.3，数据长度与线性长度的区别
注意哦,这里有两个概念“数组的长度”和“线性表的长度”需要区分。
数组的长度是存放线性表的存储空间的长度存储分配后这个量一般是不变的。有个别同学可能会问,数组的大小一定不可以变吗?可以动态分配的一维数组。是的,一般高级语言如C ，VB ，C?++都可以用编程手段实现动态分配数组,不过这会带来性能上的损耗。
线性表的长度是线性表中数据元素的个数,随着线性表插入和删除操作的进行,这个量是变化的。
在任意时刻,线性表的长度应该小于等于数组的长度。
4.4，地址计算方法
由于我们数数都是从1开始数的,线性表的定义也不能免俗,起始也是1,可?C?语言中的数组却是从0开始第一个下标的,于是线性表的第i个元素是要存储在数组下标为i-1的位置,即数据元素的序号和存放它的数组下标之间存在对应关系。
?用数组存储顺序表意味着要分配固定长度的数组空间,由于线性表中可以进行行插入和翻除操作,因此分配的数组空间要大于等于当前线性表的长度。
其实,内存中的地址,就和图书馆或电影院里的座位一样,都是有编号的。存储器中的每个存储单元都有自己的编号,这个编号称为地址。当我们占座后,占座的第一个位置确定后,后面的位置都是可以计算的。试想一下,我是班级成绩第五名,我后面的10名同学成绩名次是多少呢?当然是6,7,…,15,由于每个数据元素,不管它是整型、实型还是字符型,它都是需要占用一定的存储单元空间的。假设占用的是个存储单元,那么线性表中第+1个数据元素的存储位置和第个数据元素的存储位置满足下列关系(?LOC?表示获得存储位置的函数)。
LOC(a(i+1)) = LOC(a(i)）+ c
LOC(a(i)) = LOC(a(i)) + (i - 1)* c
下面我们从图理解：
?通过这个公式,你可以随时算出线性表中任意位置的地址,不管它是第一个还是最后一个,都是相同的时间。那么我们对每个线性表位置的存入或者取出数据,对于计算机来说都是相等的时间,也就是一个常数,因此用我们算法中学到的时间复杂度的概念来说,它的存取时间性能为O(1)。我们通常把具有这一特点的存储结构称为随机存取结构。
五，顺序存储结构的插入和删除
5.1，获得元素操作
对于线性表的顺序存储结构来说，如果我们要实现GetElem操作，就程序而言，只要i的数值在数组下标范围内，就是把数组i-1下标返回即可，代码如下：
#define OK 1
#define ERROR 0
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}5.2，插入操作
?插入算法的思路:
(1)如果插入位置不合理,抛出异常;
(2)如果线性表长度大于等于数组长度,则抛出异常或动态増加容量;
(3)从最后一个元素开始向前遍历到第i个位置,分别将它们都向后移动一个位置;
(4)将要插入元素填入位置i处;
(5)表长加1。代码如下：
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* 顺序线性表已经满 */
return ERROR;
if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i<=L->length) /* 若插入数据位置不在表尾 */
{
for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e; /* 将新元素插入 */
L->length++;
return OK;
}5.3，删除操作
?删除算法的思路:
(1)如果删除位置不合理,抛出异常:
(2)取出删除元素
(3)从删除元素位置开始遍历到最后一个元素位置,分別将它们都向前移动一个
位营(4)表长减1。实现代码如下:
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* 线性表为空 */
return ERROR;
if (i<1 || i>L->length) /* 删除位置不正确 */
return ERROR;
*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;
}5.4，线性表顺序存储结构的优缺点
?六，线性表的链式存储结构
6.1，线性表链式存储结构定义
以前在顺序结构中,每个数据元素只需要存储教据元素信息就可以了。现在链式结构中,除了要存儲数据元素信息外,还要存储它的后継元素的存储地址。
其本身的信息之外,还需存储一个指示其直接后维的信息(即直接后继的存储位置)。我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素?a (i)的存储映像,称为结点(?Node?)
?n?个结点(?a (i)的存储映像)链结成一个链表,即为线性表(?a1,?a2 ,.…?an .)的链式存储结构,因为此链表的每个结点中只包含一个指针域,所以叫做单链表,单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。
对于线性表来说,总得有个头有个尾,链表也不例外。我们把链表中第一个结点的存储位置叫做头指针,那么整个链表的存取就必须是从头指针开始进行了。之后的每一个结点,其实就是上一个的后继指针指向的位置。想象一下,最后一个结点,它的指针指向哪里?
最后一个,当然就意味着直接后继不存在了,所以我们规定,线性链表的最后一个结点指针为“空”(通常用?NULL?或“”符号表示,如下图所示。
?有时,我们为了更加方便地对链表进行操作,会在单链表的第一个结点前附设一个结点,称为头结点。头结点的数据域可以不存储任何信息,谁叫它是第一个呢,有这个特权。也可以存储如线性表的长度等附加信息,头结点的指针域存储指向第一个结点的指针,如下图所示。
?6.2，头节点和头指针的异同
6.3，线性表链式存储结构的代码描述
空链表
?为了表示线性表中数据元素及数据元素之间的关系，我们改用如下：
?带有头结点的单链表和空链表
?从这个结构定义中,我们也就知道,结点由存放数据元素的数据域和存放后继结点地址的指针域组成。假设?p?是指向线性表第个元素的指针,则该结点?a?的数据域我们可以?p?->?data?来表示,?p?->?data?的值是一个数据元素,结点?a?的指针域可以用?p?->?next?来表示,?P?->?next?的值是一个指针。?p?->?next?指向谁呢?当然是指向第社1个元素,即指向?a?.的指针。也就是说,如果?p?->?data?等于?a?,那么?p?->?next?->?data?等于?a?,(如下图所示)。
七，全部代码
#include "stdio.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int* ElemType /* ElemType类型根据实际情况而定，这里假设为int */
typedef struct
{
ElemType data[MAXSIZE]; /* 数组，存储数据元素 */
int length; /* 线性表当前长度 */
}SqList;
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
Status visit(ElemType c)
{
printf("%d ",c);
return OK;
}
/* 初始化顺序线性表 */
Status InitList(SqList *L)
{
L->length=0;
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
Status ListEmpty(SqList L)
{
if(L.length==0)
return TRUE;
else
return FALSE;
}
/* 初始条件：顺序线性表L已存在。操作结果：将L重置为空表 */
Status ClearList(SqList *L)
{
L->length=0;
return OK;
}
/* 初始条件：顺序线性表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(SqList L)
{
return L.length;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：用e返回L中第i个数据元素的值,注意i是指位置，第1个位置的数组是从0开始 */
Status GetElem(SqList L,int i,ElemType *e)
{
if(L.length==0 || i<1 || i>L.length)
return ERROR;
*e=L.data[i-1];
return OK;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：返回L中第1个与e满足关系的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int LocateElem(SqList L,ElemType e)
{
int i;
if (L.length==0)
return 0;
for(i=0;i<L.length;i++)
{
if (L.data[i]==e)
break;
}
if(i>=L.length)
return 0;
return i+1;
}
/* 初始条件：顺序线性表L已存在,1≤i≤ListLength(L)， */
/* 操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1 */
Status ListInsert(SqList *L,int i,ElemType e)
{
int k;
if (L->length==MAXSIZE) /* 顺序线性表已经满 */
return ERROR;
if (i<1 || i>L->length+1)/* 当i比第一位置小或者比最后一位置后一位置还要大时 */
return ERROR;
if (i<=L->length) /* 若插入数据位置不在表尾 */
{
for(k=L->length-1;k>=i-1;k--) /* 将要插入位置之后的数据元素向后移动一位 */
L->data[k+1]=L->data[k];
}
L->data[i-1]=e; /* 将新元素插入 */
L->length++;
return OK;
}
/* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
Status ListDelete(SqList *L,int i,ElemType *e)
{
int k;
if (L->length==0) /* 线性表为空 */
return ERROR;
if (i<1 || i>L->length) /* 删除位置不正确 */
return ERROR;
*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;
}
/* 初始条件：顺序线性表L已存在 */
/* 操作结果：依次对L的每个数据元素输出 */
Status ListTraverse(SqList L)
{
int i;
for(i=0;i<L.length;i++)
visit(L.data[i]);
printf("\n");
return OK;
}
/*将所有的在线性表Lb中但不在La中的数据元素插入到La中*/
void unionL(SqList *La,SqList Lb)
{
int La_len,Lb_len,i;
ElemType e; /*声明与La和Lb相同的数据元素e*/
La_len=ListLength(*La); /*求线性表的长度 */
Lb_len=ListLength(Lb);
for (i=1;i<=Lb_len;i++)
{
GetElem(Lb,i,&e); /*取Lb中第i个数据元素赋给e*/
if (!LocateElem(*La,e)) /*La中不存在和e相同数据元素*/
ListInsert(La,++La_len,e); /*插入*/
}
}
int main()
{
SqList L;
SqList Lb;
ElemType e;
Status i;
int j,k;
i=InitList(&L);
printf("初始化L后：L.length=%d\n",L.length);
for(j=1;j<=5;j++)
i=ListInsert(&L,1,j);
printf("在L的表头依次插入1～5后：L.data=");
ListTraverse(L);
printf("L.length=%d \n",L.length);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)\n",i);
i=ClearList(&L);
printf("清空L后：L.length=%d\n",L.length);
i=ListEmpty(L);
printf("L是否空：i=%d(1:是 0:否)\n",i);
for(j=1;j<=10;j++)
ListInsert(&L,j,j);
printf("在L的表尾依次插入1～10后：L.data=");
ListTraverse(L);
printf("L.length=%d \n",L.length);
ListInsert(&L,1,0);
printf("在L的表头插入0后：L.data=");
ListTraverse(L);
printf("L.length=%d \n", L.length);
GetElem(L,5,&e);
printf("第5个元素的值为：%d\n",e);
for(j=3;j<=4;j++)
{
k=LocateElem(L,j);
if(k)
printf("第%d个元素的值为%d\n",k,j);
else
printf("没有值为%d的元素\n",j);
}
k=ListLength(L); /* k为表长 */
for(j=k+1;j>=k;j--)
{
i=ListDelete(&L,j,&e); /* 删除第j个数据 */
if(i==ERROR)
printf("删除第%d个数据失败\n",j);
else
printf("删除第%d个的元素值为：%d\n",j,e);
}
printf("依次输出L的元素：");
ListTraverse(L);
j=5;
ListDelete(&L,j,&e); /* 删除第5个数据 */
printf("删除第%d个的元素值为：%d\n",j,e);
printf("依次输出L的元素：");
ListTraverse(L);
//构造一个有10个数的Lb
i=InitList(&Lb);
for(j=6;j<=15;j++)
i=ListInsert(&Lb,1,j);
unionL(&L,Lb);
printf("依次输出合并了Lb的L的元素：");
ListTraverse(L);
return 0;
}