首页 > 代码库 > （一）线性表
（一）线性表
一、线性表的定义
1、线性结构的特点
在数据元素的非空有限集中，（1）存在唯一的一个被称作“第一个”的数据元素；（2）存在惟一的一个被称作“最后一个”的数据元素；（3）除第一个之外，集合中的每个数据元素均只有一个前驱；（4）出最后一个之外，集合中每个数据元素均只有一个后继。
2、线性表
一个线性表n个数据元素（或结点）的有序序列：
a0，a1，a2，•••，an-1
其中a0是开始结点，an-1是终端结点，ai是ai+1的前驱结点，ai+1是ai的后继结点。一个数据元素可以由若干个数据项组成。在这种情况下，常把数据元素称为记录。含有大量记录的线性表称为文件。
3、线性表的常用基本操作
ElemType GetElement(Sqlist L,int i,EleType &e) //用e返回L中第i个数据元素的值 status ListInsert(Sqlist &L,int i,EleType e) //在L中第i个位置之前插入新的数据元素e，L长度加1 status ListDelete(Sqlist &L,int i,EleType &e); //删除L的第i个数据元素，并用e返回s其值，L长度减1
注：
- 以上操作均限定1<=i<=ListLength(L)
- &这个符号并不是C语言中的取地址操作，而是为了便于C语言的算法描述，除了值调用以外，增添了C++语言的引用调用的参数传递方式。
二、线性表的顺序表示和实现
1、线性表的顺序表示
指的是用一组地址连续的存储单元依次存储线性表的数据元素。这样，线性表中第0个元素的存储位置就是指定的存储位置，第i个元素(1<=i<=n-1)的存储位置紧接在第i-1个元素的存储位置的后面。顺序存储的线性表可简称为顺序表。线性表的顺序存储示意图见下图1.1
（图1.1 线性表的顺序存储示意图）
假设线性表的元素类型为ElemType,那么每个元素占用的存储空间大小即为sizeof(ElemType)，图中令l = sizeof(ElemType)。因此我们可以得出，在顺序存储方式下，只要我们知道线性表的首址以及数据元素的为序以及大小，我们就能够得到这个数据元素的存储地址，因此线性表的顺序存储是可以实现随机存取的。
maxlen定义为一个整型常量，为线性表中的最大元素数。如果线性表最多只有100个元素，可定义如下：
#define maxlen 100 typedef struct{ ElemType element[maxlen];//存放数据元素 int len; // 存放线性表的长度 }Sqlist;
2、顺序表基本操作的实现
（1）ElemType GetElement(Sqlist L,int i)：返回L中第i个数据元素的值
ElemType GetElem(Sqlist L,int i) { if(i<0 || i>L.len-1) Error("顺序表下标访问越界"); else return(L.element[i]); }
（2）status ListInsert(Sqlist &L,int i,EleType e)：在L中第i个位置之前插入新的数据元素e，L长度加1
status ListInsert(Sqlist &L,int i,EleType e) { int j; if(i<0 || i>L.len-1) //顺序表下界访问越界 return ERROR; else { for(j=L.len-1;j>=i;j--) //结点后移，为插入腾出位置 { L.data[j+1] = L.data[j]; } L.data[i] = e; //插入e L.len++; return OK; //成功插入 }}
说明：顺序表进行插入时要移动i后的所有元素，因此，插入效率不高。
（3）status ListDelete(Sqlist &L,int i,EleType &e) ：删除L的第i个数据元素，并用e返回s其值，L长度减1
status ListDelete(Sqlist &L,int i,EleType &e) { int j; if(i<0 || i>L.len-1) //顺序表下界访问越界
return ERROR; else { e = L.data[i]; for(j=i;j<L.len-1;j++) //结点依次前挪 L.data[j] = L.data[j+1]; L.len--; return OK; } }
说明：对顺序表进行删除时要将删除位置后的所有元素前移，因此删除的效率也不高。
3、线性表的链式存储及其实现
链式存储就是使用链表实现的存储结构，它不需要一组连续的存储单元，而是可以使用一组任意的，甚至是在存储空间中零散分布的存储单元存放线性表的数据，从而解决了顺序存储线性表需要大块连续存储单元的缺点。
（1）线性链表
为了表示每个数据元素与其直接后继元素之间的逻辑关系，我们在每个节点中除包含有数据域外，还设置了一个指针域，用来指向其后续结点。这样构成的链表称为线性链表或者单链表。
单链表分为带头节点和不带头节点两种。单链表带头节点好处有二：第一，有头结点后，插入和删除数据元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素；第二，不论链表是否为空，链表指针不变。因此，为了简便，以下讨论的都是带头节点的单链表。如果为空表，那么头结点的指针域为空（NULL）。
头指针是指指示链表中第一个结点存储位置的指针。头结点是指在单链表第一个结点前所附设的一个结点，这个结点的指针域存储指向第一个结点（包括头结点）的 指针。图1.2中，L为头指针，带阴影的结点为头结点。
由以上描述可知，如果想知道链表中某一个结点的信息，就必须知道这个结点的直接前驱结点的信息，因为此节点的存储位置保存在其直接前驱的地址域里。所以，链表是无法实现随机存取的。
下面定义线性链表的存储结构：
typedef struct LNode { ElemType data; //数据域 struct LNode * next; //指针域 }LNode, *LinkList; （2）线性链表基本操作的实现 1）ElemType GetElem(Linklist L, int i)：用e返回L中第i个数据元素的值。 ElemType GetElem(Linklist L, int i) { //L为带头节点的单链表的头指针 p = L->next; //让p指向L中的第一个元素 j = 1 ; //j为计数器， while(p&&j<i){ //顺指针往下找，直到p指向第i个元素或者p为空（即下标越界） p = p->next; j++; } if(!p || j>i) error(0); e = p->data; return e; }
说明：在给出线性表某一节点的位序后，我们必须从单链表的头结点开始，将位置标志指针p一直往下移动，如果我们需要的是线性表的最后一个元素，那么这个指针就将从链表头移动到链表尾，因此用单链表存储的线性表在对结点进行随机查询上效率是非常低的。
2）status ListInsert(LinkList &L,int i,ElemType e)：在L中第i个位置之前插入新的数据元素e
假设我们要在线性表的两个元素a和b之间插入一个元素x,指针的指向情况如图1.3所示。图1.3：单链表插入结点的指针变化情况：
首先要生成一个数据域是x的结点，然后使得x的指针域指向b结点，最后修改a结点的指针域，使其指向x结点。注意：这个步骤是不能调换顺序的！简单描述如下：
s->next = p->next; p->next = s;
完整算法描述如下：
status ListInsert(LinkLiST &l,int i,ElemType e) { //在带头结点的单链表L中第i个位置之前插入元素e p = L; j = 0; while(p&&j<i-1){ //寻找第i-1个结点 p = p->next; j++; } if(!p || j>i-1) return ERROR; s = (LinkList)malloc(sizeof(LNode));//生存新节点 s->data = http://www.mamicode.com/e; //插入结点 s->next = p->next; p->next = s; return OK; }
说明：单链表中插入数据时，不再需要像顺序表一样大量移动大量的结点已完成结点的插入，而只需要简单的修改几个指针即可，插入效率提高。并且还能很方便的实现线性表长度的动态变化，更加灵活的使用计算机内存资源。
3) status ListDelete(LinkList &L,int i,ElemType &e)：删除L的第i个数据元素，并用e返回其值。
如下图所示， 为了删除单链表中的b结点，仅需修改结点a的指针域，使其指向b的直接后继结点c。
其修改指针的语句如下：
p->next = p->next->next;
完整算法描述如下：
status ListDelete(LinkList &L,int i,ElemType &e) { //在带有头结点的单链表中删除第i个元素 p = L; j = 0; while(p&&j<i-1){ //顺着指针一直向后寻找插入位置 p = p->next; j++; } if(!(p->next)||j>i-1) //删除位置不正确 return ERROR; q = p->next; //因为考虑到要回收内存，因此用q指针保存需要删除结点的地址 p->next = q->next; e = q->data; free(q); //回收内存 return OK; }
说明：由以上算法我们可以知道，在已知链表中要删除的结点的确切位置的情况下，在单链表中删除一个结点时，仅需修改相关的指针，而不需要移动元素，删除的效率高。
（3）静态链表
在有的情况下，也可借用一维数组来描述线性链表，其存储结构如下：
#define MAX 100 typedef struct{ ElemType data; int cur; }SLinkList[MAX];
这种描述方法使得我们在没有设置指针类型的某些高级程序设计语言中可以使用链表结构，如java中。cur分量存储的不再是链表中的指针域，而是存储其下一结点在一维数组中的位序。为了和指针描述的线性链表相区别，我们就将这种用数组描述的链表叫做静态链表。如下图1.5。
静态链表以cur==0作为其结束的标志。总的来说，静态链表没有单链表使用起来灵活方便，但是在不支持指针的高级语言中，这又是一种非常巧妙的设计方法。
（4）循环链表
循环链表是另外一种形式的链式存储结构，其中比较常用的是循环单链表和循环双链表。
1）循环单链表
循环单链表的特点是表中最后一个结点的指针不再为空，而是指向该链表的表头结点，将整个链表链接成一个环。这样，由此表中的任一阶段出发均可以访问到链表中的其他结点。
循环单链表的基本操作的实现方法与单链表基本相同，只是在对表尾判断的条件上有所改变。例如，在一个头指针为h（此头指针指向头结点）的循环单链表中，判断表空的条件不再是h->next == null，而是h->next == h；判断表尾结点的条件是p->next == h。 如下图1.6所示。
2）循环双链表
以上讨论的链式存储结构的结点中只有一个指示直接后继结点的指针，这就造成了我们只有顺着指针往后访问其他结点。如果要访问某个节点的前驱，则必须从头指针开始查找。换句话说，就是在以上所有的链式存储结构中，找后继容易，找前驱麻烦。因此，为了克服这个缺点，我们引入了循环双向链表。
循环链表存储结构：
typedef struct DulNode { ElemType data; struct DulNode *prior; struct DulNode *next; }DulNode,*DulLinkList;
在双向链表中，若p为指向其中某一结点的指针，则显然有：
p->next->prior = p->prior->next = p;
如图1.6.1：
图1.6.1 双向链表结点示意图
循环双向链表存储示意图如下所示：
（5）循环双链表基本操作实现
1）ElemType GetElem(DulLinkList L,int i)：用e返回L中第i个数据元素的值。
ElemType GetElem(DulLink L,int i) { j = 0; q = L->next; while(j<i&&q!=L){//查找第i个结点 q = q->next; j++ } if(q!=L){ /返回第i个元素值 e = q->data; return e; } else{ error("位置参数i不正确"); return NULL; } }
说明：双向链表在的GetElem操作与单链表没有很多区别，但是在访问结点直接前驱方面是非常方便的，只要简单的顺着prior指针往前寻找即可。
2）status ListInsert(DulLinkList &L,int i,ElemType e)：在L中第i个位置之前插入新的数据元素e。插入时指针变化情况见下图1.8.
status ListInsert(DulLinkList & L,int i,ElemTYpe e) { if(!(p = GetElemP_Dul(L,i)))//在L中确定第i个元素的位置指针p return ERROR; //p=null，即第i个元素不存在，位置参数i错误 if(!(s = (DulLinkList)malloc(sizeof(DulNode)))) return ERROR; //内存分配不成功 s->data =http://www.mamicode.com/ e; s->prior = p->prior; //??????(1) p->prior->next = s; //(2) s->next = p; //(3) p->prior = s; //(4) return OK; }
说明：插入结点后指针的改变步骤见算法和图1.8的对应标号。
3）status ListDelete(DulLinkList & L,int i,ElemType &e)：删除L的第i个数据元素，并用e返回其值。删除时指针变化情况如图1.9所示：
status ListDelete(DulLinkList &L,int i,ElemType &e) { if(!(p = GetElem_Dul(L,i)))//在L中确定第i个元素的位置指针p return ERROR; e = p->data; p->prior->next = p->next; //(1) p->next->prior = p->prior; //(2) free(p); //内存回收 return OK; }
说明：删除结点后指针的变化步骤见算法和图1.9的对应标号。
（线性表的两种存储方式结构及其操作的实现整理完毕！）
（一）线性表