逻辑结构之一线性表

1.线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列，其中n为表长，当n=0时是一个空表。若用L命名线性表，则其一般表示为L=(a₁,a₂,…,  a_i,a_i+1,…,a_n)，式中a₁称为表头元素，有且仅有一个直接后继，a_n称为表尾元素有且仅有一个直接前驱，其他元素有且仅有一个直接后继和一个直接前驱。

线性表的特点：1.表中元素有限；2.表中元素具有逻辑上的先后顺序；3.表中元素都是数据元素；4.表中元素的数据类型都相同，这意味着每个元素都有相同大小的存储空间；5.表中元素具有抽象性，仅讨论表中元素的逻辑关系，而不管元素实际内容如何。

2.线性表的实现

2.1线性表的顺序存储

线性表的顺序存储又称顺序表。它是用一组连续的地址单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点就是表中的元素逻辑顺序与其物理顺序相同。所以顺序表的顺序存储是一种随机存取的存储结构。

假定线性表中的元素类型为Elemtype，则顺序表的顺序存储类型描述为

#define MaxSize 50					//定义线性表的最大长度
typedef struct{							
	Elemtype data[MaxSize];		//顺序表的元素
  int length;								//顺序表的当前元素
}SqList;										//顺序表的类型定义

2.2线性表的链式存储

顺序表可以随机存储表中元素，但是插入和删除操作需要移动大量元素。而链式存储不需要使用地址连续的地址单元，而是通过指针链接表中元素的位置，所以链表中的元素逻辑位置与物理位置并不相同，因此没有顺序表随机存储的优点，但是插入和删除操作并不需要移动元素，只需要修改指针即可。

2.2.1单链表

它是指通过一组任意的存储单元来存储线性表中的数据元素，为了建立数据元素之间的线性关系，对每个链表节点除了保存自身的信息外，还需要存放一个指向其直接后继的指针。

typedef struct LNode{		//定义单链表的节点类型		
	Elemtype data;				//数据域
  struct LNode *next;		//指针域
}LNode, *LinkList;

由于链表无法实现随机存取，所以在查找某一特定节点时，需要从表头开始遍历，依次查找。

通常用一个头指针来标识一个单链表，如单链表L，头指针为NULL时表示一个空表。除此之外，为了操作上的方便，可以为单链表创建一个头节点作为第一个节点。

1.头插法建立单链表

头插法建立的单链表中节点次序是逆序。

带头结点的头插法：

LinkList HeadInsert(LinkList L){
	LNode *s;		//LNode*表示节点指针，LinkList表示头指针
  	Elemtype	datax;
    L = (LinkList)malloc(sizeof(LNode));	//创建头节点
    L->next = NULL;							//初始为空链表
    while(scanf("", datax) != EOF){
    	s = (LNode *)malloc(sizeof(LNode));	//创建节点
        s->data = datax;
        /* 头插法 */
        s->next = L->next;
        L->next = s;						//利用头节点指向新增节点
    }
}

不带头节点的头插法：

void HeadInsert(LinkList L){
	LNode *s;		//LNode*表示节点指针，LinkList表示头指针
  	Elemtype	datax;
    s = (LNode *)malloc(sizeof(LNode));			//第一个节点
    L = s;										//头指针指向第一个节点
    /* 保存节点信息 */
    scanf("", datax);
    s->data = datax;
    s->next = NULL;	
    while(scanf("", datax) != EOF){
    	s = (LNode *)malloc(sizeof(LNode));	//创建节点
        s->data = datax;
        /* 头插法 */
        s->next = L->next;
        L = s;									//头指针始终指向第一个节点
    }
}

2.尾插法建立单链表

尾插法建立的单链表中节点次序与输入数据顺序一致，通过将新节点直接插入到当前链表的结尾，由于头指针只能指向链表的第一个节点，结点指针s需要指向新增节点，因此需要一个额外的尾指针，来指向链表的最后一个节点。

void TailInsert(LinkList L){
	LNode *s, *r;		//s为节点指针，r为尾指针
    Elemtype datax;
    L = (LinkList)malloc(sizeof(LNode));	//创建头节点
    L->next = NULL;							//初始为空链表
    r = L;									//r始终指向链表最后一个节点
    while(scanf("", datax) != EOF){
    	s = (LNode *)malloc(sizeof(LNode));	//创建节点
        s->data = datax;
        /* 尾插法 */
        s->next = r->next;
        r->next = s;						
        r = s;								//尾指针始终指向最后一个节点
    }
}

2.2.2双链表

与单链表不同的是，双链表有两个指针域，一个指向前驱元素，一个指向后继元素，因此双链表很容易找到其前驱节点。在不断”链“的操作中，与单链表相同，如查找操作：按值查找和按序查找，但是在删除和插入节点的操作中，与单链表不同，因为需要同时修改指向前驱节点的指针。双链表也属于链表，自然也有带头结点与不带头节点。

2.2.3循环链表

1.循环单链表

循环单链表与单链表的区别就在于，表中最后一个节点的指针不指向NULL，而是指向链表的第一个节点（可能是头节点），从而使得整个链表成为一个环。因此需要一个额外的尾指针来指向链表的最后一个节点，即r->next=L，这也是判断循环链表是否为空的条件，为NULL或者为r和L是否指向同一个节点。

2.循环双链表

与循环单链表的定义类似，只不过循环双链表的第一个节点指向其前驱节点的指针需要指向表尾节点。当循环双链表为空表时，L为NULL或者头节点的前驱指针和后继指针指向的节点时头节点（即前驱指针域和后继指针域都是L）。

2.2.4静态链表

静态链表借助数组来描述线性表的链式存储结构，因此与顺序表一样，都需要预先分配一块连续的内存空间。静态链表的节点也有数据域data和指针域next，只不过通过静态链表中节点的相对位置来模拟指针，又称游标。

静态链表与单链表的对应关系如下：

静态链表结构类型的描述如下：

#define MaxSize 50
typedef struct{
	Elemtype	data;
  int		next;
}SLinkList[MaxSize];

静态链表以next==-1为结束标志。