数据结构第二章：线性表

2024-04-11 15:57:07

线性结构的基本特征:

线性结构是一个数据元素的有序（次序）集 1．集合中必存在唯一的一个“第一元素”
2．集合中必存在唯一的一个 “最后元素”
3．除最后元素在外，均有唯一的后继
4．除第一元素之外，均有唯一的前驱

一、线性表的基本概念

线性表L是n(n≥0)个具有相同属性的数据元素a1，a2，a3，…，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。

当n=0时称为空表，即不含有任何元素。

常常将非空的线性表(n>0)记作：
(a1，a2，…an)

数据元素 ai(1≦i≦n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。

非空的线性表的逻辑特征：
有且仅有一个开始结点a1，它没有直接前趋，仅有一个直接后继a2；
有且仅有一个终端结点an，它没有直接后继，仅有一个直接前趋an-1；
其余结点ai(2≦i≦n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。
运算定义在逻辑结构上，而运算的具体实现则是在存储结构上进行的。

二、线性表的类型定义

上述问题可演绎为对线性表作如下操作：
扩大线性表LA，将存在于线性表LB中而不存在于LA中的数据元素插入到线性表LA中去。

分析：设La=(a1，…，ai，…，an)
Lb= (b1，…，bi，…，bm)
Lc= (c1，…，ck，…，cm+n)
则ck=？，k=1，2，…，m+n
分别从LA，LB中取得当前元素ai和bj；
若ai<= bj，则将ai插入到Lc 中；否则将bj插入到Lc 中。

Void  MergeList(List La，List Lb，List &Lc)
//巳知线性表LA和线性表LB中的数据元素按值非递减排列
//归并LA和LB得到新的线性表LC，LC中的元素仍按值非递减排列。
     InitList(Lc);
     i=j=1;
     k=0;
     La_len=ListLength(La);
     Lb_len=ListLength(Lb);
     while((i<=La_len)&&(j<=Lb_len)){    
     	GetElem(La,i,ai);
     	GetElem(Lb,j,bj);
     	if(ai<=bj){
     		ListInsert(Lc,++k,ai);
            ++i;
        }
      	else{
      		ListInsert(Lc,++k,bj);
            ++j;
        }
      }
      while(i<=La_len){
          GetElem((La,i++,ai);
          ListInsert(Lc,++k,ai);
       }
      while(j<=Lb_len){
          GetElem((Lb,j++,bj);
          ListInsert(Lc,++k,bj);
       }
}

boolisEqual(List LA, List LB) {
 // 若线性表LA和LB不仅长度相等，且所含数据
  // 元素也相同，则返回 TRUE, 否则返回 FALSE
  	La_len = Listlength(LA);
  	Lb_len = Listlength(LB);
  	if ( La_len != Lb_len )
  		return FALSE; // 两表的长度不等
	else 
	{
		i = 1;  found = TRUE;
		while (i<= La_len && found ) {
			GetElem(LA, i, e);  
			if (LocateElem(LB, e, equal( ))
			    i++;  
			else  found = FALSE; 
		}
		return found; 
	}
}

三、线性表类型的实现——顺序映象

—— 以x的存储位置和y的存储位置之间某种关系表示逻辑关系<x,y>
最简单的一种顺序映象方法是：
令y的存储位置和x的存储位置相邻。

在C语言中，可用下述类型定义来描述顺序表：

     #define LIST_INIT_SIZE  100
     #define LISTINCREMENT  10 
     typedef  struct {
               ElemType *elem; 
               int      length;   
               int      listsize；
      }sqList;
      sqList   L;

在实际应用中，需要将ElemType定义成实际类型

1．线性表的初始化操作

顺序表的初始化操作：为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为0。

Status InitList_Sq(SqList &L){  
	L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
	if(!L.elem)
		exit(OVERFLOW);
	L.length=0;
	L.listsize= LIST_INIT_SIZE;
	return ok;
}

2.顺序表的查找算法LocateElem的实现：

int LocateElem_Sq(SqList L, ElemType e,status(*compare)( ElemType, ElemType)){ 
     i=1;
     p=L.elem;
     while(i<=L.length && ！(*compare )(*p++，e))
		++i；
    if(i<=L.length)  
		return  i ;
    else  
   		return  0;
}

3．顺序表的插入算法ListInsert(&L,i,e)的实现

Status compare(int x, int y){
	if (x == y){
		return OK;
	}
	else
	{
		return ERROR;
	}
}
//2.顺序表的插入
Status ListInsert_Sq(SqList &L, int i, ElemType e){
	ElemType *newbase, *q, *p;
	if (i<1 || i>L.length + 1){
		return ERROR;
	}
	if (L.length >= L.listsize){
		newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
		if (!newbase)
		{
			exit(OVERFLOW);
		}
		L.elem = newbase;
		L.listsize += LISTINCREMENT;
	}
	q = &(L.elem[i - 1]);
	for (p = &(L.elem[L.length-1]); p >= q; --p)
	{
		*(p + 1) = *p;
	}
	*q = e;
	++L.length;
	return OK;
}

考虑移动元素的平均情况:

假设在第i个元素之前插入的概率为pi，则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

若假定在线性表中任何一个位置上进行插入的概率都相等，则移动元素的期望值为：

4．顺序表的删除操作ListDelete(&L,i，&e)的实现

线性表的删除算法：

//4.顺序表的删除
Status ListDelete_Sq(SqList &L, int i, ElemType &e){
	if ((i<1)||(i>L.length))
	{
		return ERROR;
	}
	ElemType *p, *q;
	p = &(L.elem[i - 1]);
	e = *p;
	q = L.elem + L.length - 1;
	for (p++; p <= q; p++){
		*(p - 1) = *p;
	}
	L.length++;
	return OK;
}

线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。但是，顺序存储结构也有一些不方便之处，主要表现在：

（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；

（2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。

四、线性表类型的实现－链式映象

1、单链表

用一组地址任意的存储单元存放线性表中的数据元素。

以“结点的序列”表示线性表——称作单链表

单链表的 C 语言描述

typedef struct  LNode {
      ElemType      data;  // 数据域
      struct LNode   *next;  // 指针域
} *LinkList;  
LinkList  L；  // L 为单链表的头指针

单链表分为带头结点和不带头结点两种类型。
对于空链表，头结点的指针域为空。下图是带头结点的链表示方式：

假设有一个线性表为(A,B,C,D,E)，存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图2-7(a)所示。

2、单链表操作的实现

GetElem(L,i,&e)在单链表中的实现:
单链表是一种顺序存取的结构，为找第i个数据元素，必须先找到第 i-1个数据元素。

因此，查找第 i 个数据元素的基本操作为：

移动指针，比较j和i

令指针p始终指向线性表中第j个数据元素

基本操作：使指针p始终指向线性表中第j个数据元素

Status LinkInsert_L(LinkList &L, int i, ElemType e){
	LinkList p,s;
	int j = 0;
	p = L;
	while (p&&j<i-1)
	{
		p = p->next;
		++j;
	}
	if (!p || j>i - 1){
		return ERROR;
	}
	s = (LinkList)malloc(sizeof(LNode));
	s->data = e;
	s->next = p->next;
	p->next = s;
	return OK;
}

时间复杂度：O(ListLength(L))

ListInsert(&L, i, e)在单链表中的实现：

ListDelete(&L, i, &e)在链表中的实现:

Status ListDelete(LinkList L, int i, ElemType &e){
	LinkList p, q;
	int j;
	p = L;
	j = 0;
	while (p->next&&j<i-1)
	{
		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;
}

算法的时间复杂度：O(ListLength(L))
ClearList(&L) 在链表中的实现:

void ClearList(LinkList &L){
	LinkList p;
	while (L->next)
	{
		p = L->next;
		L->next = p->next;
		free(p);
	}
}

算法时间复杂度：O(ListLength(L))
如何从线性表得到单链表？
链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点“逐个插入”的过程。

void CreteList(LinkList &L, int n){
	LinkList p;
	L = (LinkList)malloc(sizeof(LNode));
	L->next = NULL;
	for (int i = n; i > 0; --i)
	{
		p = (LinkList)malloc(sizeof(LNode));
		scanf("%d",&p->next);
		p->next = L->next;
		L->next = p;
	}
}

算法的时间复杂度为:O(Listlength(L))

MergeList_L操作（单链表）

Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc){
	LNode *pa, *pb, *pc;
	pa = La->next;
	pb = Lb->next;
	Lc = pc = La;
	while (pa&&pb)
	{
		if (pa->data<=pb->data)
		{
			pc->next = pa;
			pc = pa;
			pa = pa->next;
		}
		else
		{
			pc->next = pb;
			pc = pb;
			pb = pb->next;
		}
	}
	pc->next = pa ? pa : pb;
	free(Lb);
}

用上述定义的单链表实现线性表的操作时，存在的问题：

单链表的表长是一个隐含的值；
在单链表的最后一个位置插入元素时，需遍历整个链表；
在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。

改进链表的设置：

增加“表长”、“表尾指针”和“当前位置指针”三个域；
将基本操作由“位序”改变为“指针”。

带尾指针的单链表

MergeList_L操作（带尾指针的单链表）
将有序链表LA和有序链表LB按照有序的方式合并到LC中。

Status MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc, 
                            int (* compare)(ElemType, ElemType)){
     if(!InitList(Lc)) return ERROR;
     ha = GetHead(La); hb = GetHead(Lb);
     pa=NextPos(La,ha); pb=NextPos(Lb,hb); 
     while(pa &&pb){
          a = GetCurElem(pa); b = GetCurElem(pb); 
   if((* compare)(a,b)<=0){
          DelFirst(ha,q);  Append(Lc,q);  pa=NextPos(La,ha);}
    else{
   DelFirst(hb,q);  Append(Lc,q);  pb=NextPos(Lb,hb);}
}
if(pa) Append(Lc,pa);
else   Append(Lc,pb);
       FreeNode(ha); FreeNode(hb); 
       return ok;		
}

4. 静态链表

静态链表的存储结构设计

#define MAXSIZE 1000
typedef struct{
	ElemType data;
	int cur;	
}component, SLinkList[MAXSIZE];

静态链表的操作设计

int LocateElem_SL(SLinkList S, ElemType e){
	i = S[0].cur;
	while(i!=-1 && S[i].data != e)
		i = S[i].cur;
	return i;
} //LocateElem_SL

5.循环链表

6. 双向链表

五、线性表的应用 —— 一元多项式的表示及相加

在计算机中，可以用一个线性表来表示:
P = (p0, p1, …，pn)
但是对于形如

的多项式，上述表示方法是否合适？

1.抽象数据类型一元多项式的定义：

2. 一元多项式相加

假设用单链表表示多项式：A(x)=12+7x+8x¹⁰+5x¹⁷ ，B(x)=8x+15x⁷-6x¹⁰，头指针ha与hb分别指向这两个链表，如图2-21所示：

对两个多项式进行相加运算，其结果为C(x)= 12+15x+15 x⁷+2x¹⁰+5x¹⁷。如图2-22所示。

两个一元多项式相加的运算规则：假设指针qa和qb分别指向多项式A(x)和B(x)中当前进行比较的某个结点，则需比较两个结点数据域的指数项，有三种情况：

(1)qa所指结点的指数值＜qb所指结点的指数值时，则保留qa所指向的结点，qa后移；

(2)qa所指结点的指数值＞qb所指结点的指数值时，则将qb所指向的结点插入到qa所指结点前，qb后移；

(3)qa所指结点的指数值＝qb所指结点的指数值时，将两个结点中的系数相加。若和不为零，则修改qa所指结点的系数值，同时释放qb所指结点；反之，从多项式A(x)的链表中删除相应结点，并释放qa和qb所指结点。
多项式相加算法：

Void  addpolyn(polynomial &pa, polynomial &pb)
{
     ha=GetHead(pa);
     hb=GetHead(pb); 
          //ha和hb分别指向两个链表的头结点
     qa=NextPos(pa,ha); 
     qb=NextPos(pb,hb);
           //qa和qb分别指向pa和pb中当前结点
       while(qa&&qb) { //两链表均非空 
   a=GetCurElem(qa);b=GetCurElem(qb);//
   Switch(*cmp(a,b)){
      case –1:
          ha=qa;qa= NextPos(pa,qa);break;
      case 0: //两者指数值相等
          sum=a.coef+b.coef;
          if(sum!=0.0){//相加后系数不为零时
              SetCurElem(qa,sum);ha=qa;}
          else{//相加后系数为零时
                DelFirst(ha,qa);FreeNode(qa);}    
         DelFirst(hb,qb);FreeNode(qb);qb=NextPos(pb,hb);
         qa=NextPos(pa,ha); break;      
               case 1:多项式pb的指数值小
              DelFirst(hb,qb);InsFirst(ha,qb);
              qb=NextPos(pb,hb);  ha=NextPos(pa,ha);break;
       }//switch
     }//while
    if (!ListEmpty(pb)  Append(pa,qb);
    FreeNode(hb);
} //Addpolyn

顺序表和链表的比较

顺序表和链表各有短长，在实际应用中应根据问题的要求和性质来选择使用。顺序存储有三个优点：
(1)方法简单，各种高级语言中都有数组，容易实现；
(2)不用为表示结点间的逻辑关系而增加额外的存储开销；
(3)具有按元素序号随机访问的特点。
两大缺点：
(1)在顺序表中做插入/删除操作时，平均移动大约表中一半的元素，因此当n较大时顺序表的操作效率低。
(2)需要预先分配足够大的存储空间。若估计过大，容易导致顺序表后部大量闲置；预先分配过小，又会造成溢出。
链表的优缺点恰好与顺序表相反。在实际中究竟怎样选取合适的存储结构？通常可考虑以下几点：
1．基于空间的考虑
顺序表的存储空间是静态分配的，在程序执行前必须明确规定它的存储规模。若线性表长度n变化较大，则存储规模很难预先正确估计。估计太大将造成空间浪费，估计太小又将使空间溢出机会增多。所以当对线性表的长度或存储规模难以估计时，不宜采用顺序存储结构。
链表不用事先估计存储规模，是动态分配。只要内存空间尚有空闲，就不会产生溢出。因此，当线性表的长度变化较大，难以估计其存储规模时，以采用动态链表作为存储结构为好。但链表的存储密度较低。存储密度指一个结点中数据元素所占的存储单元和整个结点所占的存储单元之比。显然链式存储结构的存储密度小于1，而顺序表的存储密度为1。

2．基于时间的考虑
随机存取结构，就是对表中任一结点都可在O(1)时间内直接取得。若对线性表主要做查找，很少做插入和删除操作时，采用顺序存储结构为宜；而在链表中按序号访问的时间性能为O(n)。所以，如果经常做的运算是按序号访问数据元素，显然顺序表优于链表。
而在顺序表中做插入、删除操作时，要平均移动表中一半的元素；尤其是当每个结点的信息量较大时，移动结点的时间开销就相当可观。在链表中的任何位置上进行插入和删除，都只需要修改指针。对于频繁进行插入和删除的线性表，宜采用链表做存储结构。若表的插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。

3．基于环境的考虑
顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，其使用受语言环境的限制，这也是用户应该考虑的因素之一。
总之，两种存储结构各有特点。选择哪种结构根据实际使用的主要因素决定。通常“较稳定”的线性表选择顺序存储结构；而插/删频繁“动态性“较强的线性表宜选择链式存储结构。

码农公寓