数据结构1-线性表

线性表是一种典型的线性结构，其基本特点是表中的数据元素是有序且是有限的

1)存在一个唯一的被称为“第一个”的数据元素

2)存在一个唯一的被称为“第二个”的数据元素

3)除了第一个元素外，每个元素均有唯一一个直接前驱

4)除了最后一个元素外，每个元素均有唯一一个直接后驱

(一)、线性表的逻辑结构

1.线性表的定义：

1) 是由n（n>=0）个数据元素（结点）a1,a2,……，an组成的有限序列。

2) 该序列中的所有结点具有相同的数据类型

3) 其中数据元素的个数n称为线性表的长度

4) n=0时称为空表

5) 当n>0时将非空的线性表记作：（a1,a2,……，an）

a. a1称为线性表的第一个（首）结点，an称为线性表的最后一个（尾）结点

b. a1,a2,……,ai-1都是ai的前驱，其中ai-1是ai的直接前驱

c. ai+1,ai+2,……,an都是ai的后继，其中ai+1是ai的直接后继

2.线性表的逻辑结构：

1) 线性表中的结点可以是单值元素（每个元素只有一个数据项）

2) 线性表中的结点可以是记录型元素(每个元素含有多个数据项,每个项称为结点的一个域)

3) 若线性表中的结点是按值（或按关键字值）由小到大（或由大到小）排列的，称线性表是有序的

4) 对线性表的数据元素可以访问、插入和删除

3.线性表的抽象数据类型定义：

ADT List{

数据对象：D = { ai | a i∈ElemSet, i=1,2,…,n, n≧0 }

数据关系：R = {<a i-1 , a i > | a i-1 , a i ∈D, i=2,3,…,n }

基本操作：

InitList( &L )

操作结果：构造一个空的线性表L；

ListEmpty( L )

初始条件：线性表L已存在；

操作结果：若L为空表，则返回TRUE，否则返回FALSE；

….

GetElem( L, i, &e )

初始条件：线性表L已存在，1≦i≦ListLength(L)；

操作结果：用e返回L中第i个数据元素的值；

ListInsert ( L, i, &e )

初始条件：线性表L已存在，1≦i≦ListLength(L) ；

操作结果：在线性表L中的第i个位置插入元素e；

…

} ADT List

(二)、线性表的顺序存储

1.线性表的顺序存储结构

1) 顺序存储：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。

2) 顺序表的特点：
a. 线性表的逻辑顺序和物理顺序一致

b. 数据元素之间的关系是以元素在计算机内“物理位置相邻”来体现

3) 设有非空的线性表：(a1，a 2，…an)，线性表的每个元素需占用l个存储单元。线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a 1 )+(i-1)*l

4) 除用数组来存储线性表的元素之外，还可用结构类型来定义顺序表类型。

#define OK				1
#define ERROR			-1
#define MAX_SIZE		100
#define LISTINCREMENT	10	//分配增量

typedef int Status;			//Status是函数的类型，其值是函数结果状态代码
typedef int ElemType;		//数据类型

/*用结构体定义顺序表类型*/
typedef struct sqlist
{
	ElemType* elem;
	int length;
	int listsize;
} SqList;

2.顺序表的基本操作

1) 顺序线性表初始化

/*顺序线性表的初始化*/
Status Init_SqList(SqList *L)		//创造一个空的顺序表L
{
	L->elem = (ElemType*)malloc(MAX_SIZE * sizeof(ElemType));			//为顺序表分配空间
	if (!L->elem)
	{
		return ERROR;		//存储分配失败
	}
	else
	{
		L->length = 0;		//空表长度为0
		return OK;
	}
}

2)顺序线性表的插入

在线性表 L= (a 1 ，…a i-1 ，a i ， a i+1 ，…，a n )中的第i(1≦i≦n+1)个位置上插入一个新结点e，使其成为线性表： L=(a 1 ，…a i-1 ，e，a i ，a i+1 ，…，a n )

(1) 将线性表L中的第i个至第n个结点后移一个位置。

(2) 将结点e插入到结点a i-1 之后。

(3) 线性表长度加1。

算法描述

/*顺序线性表的插入*/

Status ListInsert_Sq(SqList& L, int i, ElemType e) {

      // 在顺序线性表L的第i个元素之前插入新的元素e，

      // i的合法值为1≤i≤ListLength_Sq(L)+1

      ElemType* p;

      if (i < 1 || i > L.length + 1)

      {

           return ERROR; // i值不合法

      }

      if (L.length >= L.listsize) { // 当前存储空间已满，增加容量

           ElemType* newbase = (ElemType*)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));

           if (!newbase)

           {

                 return ERROR; // 存储分配失败

           }

           L.elem = newbase; // 新基址

           L.listsize += LISTINCREMENT; // 增加存储容量

      }

      ElemType* q = &(L.elem[i - 1]); // q为插入位置

      for (p = &(L.elem[L.length - 1]); p >= q; --p)

      {

           *(p + 1) = *p;

      }

      // 插入位置及之后的元素右移

      *q = e; // 插入e

      ++L.length; // 表长增1

      return OK;

} // ListInsert_Sq

3) 线性表的删除

在线性表 L=(a 1，…a i-1，ai， ai+1，…，a n) 中删除结点a i(1≦i≦n)，使其成为线性表：L= (a 1，…ai-1，ai+1，…，an)

(1) 将线性表L中的第i+1个至第n个结点依此向前移动一个位置。

(2) 线性表长度减1。

算法描述

/*顺序线性表的删除*/

Status ListDelete_Sq(SqList& L, int i, ElemType& e)

{

      // 在顺序线性表L中删除第i个元素，并用e返回其值。

      // i的合法值为1≤i≤ListLength_Sq(L)。

      ElemType* p, * q;

      if (i<1 || i>L.length)

      {

           return ERROR; // i值不合法

      }

      p = &(L.elem[i - 1]); // p为被删除元素的位置

      e = *p; // 被删除元素的值赋给e

      q = L.elem + L.length - 1; // 表尾元素的位置

      for (++p; p <= q; ++p)

      {

           *(p - 1) = *p; // 被删除元素之后的元素左移

      }

      --L.length; // 表长减1

      return OK;

} // ListDelete_Sq

4)顺序线性表的查找定位删除

在线性表 L= (a 1 ，a 2 ，…，a n ) 中删除值为x的第一个结点。

(1) 在线性表L查找值为x的第一个数据元素。

(2) 将从找到的位置至最后一个结点依次向前移动一个位

置。

(3) 线性表长度减1。

算法描述

Status Locate_Delete_SqList(Sqlist *L，ElemType x)

/* 删除线性表L中值为x的第一个结点 */

{

int i = 0, k;

      while (i < L->length) /*查找值为x的第一个结点*/

      {

           if (L->elem[i] != x) i++;

           else

           {

                 for (k = i + 1; k < L->length; k++)

                      L->elem[k - 1] = L->elem[k];

                 L->length--; break;

           }

      }

      if (i > L->length)

      {

           printf("要删除的数据元素不存在!\n");

           return ERROR;

      }

      return OK;

}

线性表顺序存储结构的特点

它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式

缺点

（1）在做插入或删除元素的操作时，会产生大量的数据元素移动；

（2）对于长度变化较大的线性表，要一次性地分配足够的存储空间，但

这些空间常常又得不到充分的利用；

（3）线性表的容量难以扩充。

(三)、线性表的链式存储

1.线性表的链式存储结构

1)链式存储：用一组任意的存储单元存储线性表中的数据元素。用这种方法存储的线性表简称线性链表。

2)存储链表中结点的一组任意的存储单元可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。

3)链表中结点的逻辑顺序和物理顺序不一定相同。

4) 链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。

5) 每一个结点只包含一个指针域的链表，称为单链表

head是头指针，它指向单链表中的第一个结点。由于最后一个结点没有直

接后继结点，所以，它的指针域放入一个特殊的值NULL。NULL值在图示

中常用（^）符号表示。

带头节点的单链表

在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。

6) 结点的描述与实现

a.C语言中用带指针的结构体类型来描述

b. 结点是通过动态分配和释放来的实现

即需要时分配，不需要时释放。实现时是分别使用C语言提供的标准函数：malloc() ，realloc()，sizeof() ，free() 。

动态分配 p=(LNode*)malloc(sizeof(LNode));

函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。

动态释放 free(p) ;

系统回收由指针变量p所指向的内存区。P必须是最近一次调用malloc函数时的返回值。

7) 最常见的基本操作及示意图

a.结点的赋值

b.常见的指针操作

q=p;

q=p->next;

p=p->next;(p指向下一个结点)

q->next=p;

q->next=p->next

2.单线性链式的基本操作

1）建立单链表

常用方法：头插入法，尾插入法

头插入法

从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。即每次插入的结点都作为链表的首元结点

算法描述

//头插入法创建单链表
LNode* create_LinkList(void)
/* 头插入法创建单链表,链表的头结点head作为返回值 */
{
	int data;
	LNode* head;
	LNode* p;
	head = (LNode*)malloc(sizeof(LNode));
	head->next = NULL; /* 创建链表的表头结点head */
	while (1)
	{
		scanf(" % d", &data);
		if (data == 32767) break; //以32767作为结束标志。
		p = (LNode*)malloc(sizeof(LNode));
		p-> data = data; /* 数据域赋值 */
		p-> next = head-> next; 
		head->next = p;
		/* 钩链，新创建的结点总是作为第一个结点 */
	}
	return (head);
}

尾插入法

头插入法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾，使其成为当前链表的尾结点。

算法描述

//尾插入法创建单链表
LNode* create_LinkList(void)
/* 尾插入法创建单链表,链表的头结点head作为返回值 / { int data; LNode head, * p, * q;
head = p = (LNode)malloc(sizeof(LNode)); p->next = NULL; / 创建单链表的表头结点head / while (1) { scanf(" % d", &data); if (data == 32767) break; q = (LNode)malloc(sizeof(LNode));
q-> data = data; /* 数据域赋值 / q-> next = p->next; p->next = q; p = q; /钩链，新创建的结点总是作为最后一个结点*/
}
return (head);
}

对于单链表，无论是哪种操作，只要涉及到钩链(或重新钩链)，如果没有明确给出直接后继，钩链(或重新钩链)的次序必须是“先右后左”。

2）单链表的查找

a.按序号查找

设单链表的长度为n，要查找表中第i个结点，仅当1≦i≦n时，i的值是合法的。

算法描述

Status GetElem_L(LinkList& L, int i, ElemType& e) {
// L为带头结点的单链表的头指针。
// 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
LinkList p;
p = L->next;
int j = 1; // 初始化，p指向第一个结点，j为计数器
while (p && j < i) { // 顺指针向后查找，直到p指向第i个元素或p为空 p = p->next;
++j;
}
if (!p || j > i)
{
return ERROR; // 第i个元素不存在
}
e = p->data; // 取第i个元素
return OK;
} // GetElem_L

b.按值查找

在链表中，查找等于给定值key的结点。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。

算法描述

//单链表按值查找
LNode* Locate_Node(LNode* L ,int key)
/* 在以L为头结点的单链表中查找值为key的第一个结点 / { LNode p = L-> next;
while (p != NULL && p->data != key)
{
p = p->next;
}
if (p->data == key)
{
return p;
}
else
{
printf("所要查找的结点不存在!!\n");
return(NULL);
}
}

3）单链表的插入

在带头结点的单链线性表L的第i个元素之前插入元素e

算法描述

//单链表插入元素
Status ListInsert_L(LinkList& L, int i, ElemType e) {
// 在带头结点的单链线性表L的第i个元素之前插入元素e
LinkList p, s;
p = L;
int j = 0;
while (p && j < i - 1) { // 寻找第i-1个结点 p = p->next;
++j;
}
if (!p || j > i - 1)
{
return ERROR; // i小于1或者大于表长
}
s = (LinkList)malloc(sizeof(LNode)); // 生成新结点
s->data = e;
s->next = p->next; // 插入L中
p->next = s;
return OK;
} // LinstInsert_L

4）单链表的删除

a.按序号删除

删除单链表中的第i个结点

算法描述

Status ListDelete_L(LinkList &L, int i, ElemType &e) { // 算法2.10

// 在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

LinkList p,q;

p = L;

int j = 0;

while (p->next && j < i-1) { // 寻找第i个结点，并令p指向其前趋

p = p->next;

++j;

}

if (!(p->next) || j > i-1) return ERROR; // 删除位置不合理

q = p->next;

p->next = q->next; // 删除并释放结点

e = q->data;

free(q);

return OK; } // ListDelete_L

b.按值删除

删除单链表中值为key的第一个结点。与按值查找相类似，首先要查找值为key的结点是否存在? 若存在，则删除；否则返回NULL。

算法描述

void Delete_LinkList(LNode *L，int key)

/* 删除以L为头结点的单链表中值为key的第一个结点 */

{ LNode *p=L, *q=L–>next;

while ( q!=NULL&& q–>data!=key)

{ p=q; q=q–>next; }

if (q–>data==key)

{ p->next=q->next; free(q); }

else

printf(“所要删除的结点不存在!!\n”);

}

c. 删除单链表中值为key的所有结点

从单链表的第一个结点开始，对每个结点进行检查，若结点的值为key，则删除之，然后检查下一个结点，直到所有的结点都检查。

算法描述

void Delete_LinkList_Node(LNode *L，int key)

/*删除单链表中值为key的所有结点*/

{ LNode *p=L, *q=L–>next;

while ( q!=NULL)

{ if (q–>data==key)

{ p->next=q->next; free(q); q=p->next; }

else

{ p=q; q=q–>next; }

}

}

d.删除单链表中所有值重复的结点，使得所有结点的值都不相同。

从单链表的第一个结点开始，对每个结点进行检查。检查链表中该结点的所有后继结点，只要有值和该结点的值相同，则删除之；然后检查下一个结点，直到所有的结点都检查。

算法描述

5）单链表的合并

设有两个有序的单链表，它们的头指针分别是La 、Lb，将它们合并为以Lc为头指针的有序链表。栈和队列

算法中pa ，pb分别是待考察的两个链表的当前结点，pc是合并过程中合并的链表的最后一个结点。

算法描述

LNode *Merge_LinkList(LNode *La， LNode *Lb)

/* 合并以La, Lb为头结点的两个有序单链表 */

{ LNode *Lc, *pa , *pb , *pc, *ptr ;

Lc=La ; pc=La ; pa=La->next ; pb=Lb->next ;

while (pa!=NULL && pb!=NULL)

{ if (pa->data<pb->data)

{ pc->next=pa ; pc=pa ; pa=pa->next ; }

/* 将pa所指的结点合并，pa指向下一个结点 */

if (pa->data>pb->data)

{ pc->next=pb ; pc=pb ; pb=pb->next ; }

/* 将pa所指的结点合并，pa指向下一个结点 */if (pa->data==pb->data)

{ pc->next=pa ; pc=pa ; pa=pa->next ;

ptr=pb ; pb=pb->next ; free(ptr) ; }

/* 将pa所指的结点合并，pb所指结点删除 */}

if (pa!=NULL) pc->next=pa ;

else pc->next=pb ; /*将剩余的结点链上*/

free(Lb) ;

return(Lc) ;}

3.循环链表

1）循环链表

是一种头尾相接的链表。其特点是最后一个结点的指针域指向链表的头结点，整个链表的指针域链接成一个环。从循环链表的任意一个结点出发都可以找到链表中的其它结点，使得表处理更加方便灵活。

2）循环链表的操作

⑴ 判断是否是空链表：head->next==head;

⑵ 判断是否是表尾结点：p->next==head;