数据结构——第二章 线性表

数据结构——第二章 线性表

1、线性表的类型定义         

线性结构的定义:空或者只有一个结点,或者 存在唯一的一个被称之为”第一个“  的结点;存在唯一的一个被称之为”最后一个“  的结点; 除第一个结点之外，每个结点均只有一个直接前驱结点;除最后一个结点之外，每个结点均只有一个直接后驱结点。 分为以下几大类： 分类表  时间有序表    频率有序表    序列表

线性表：通过节点（数据元素）之间的相对位置，确定它们之间的相互关系的线性结构。      数据元素是数据的基本单位。   

e.g: 序列：a1、 a2、 a3…………………an-1、 an     

数据元素： 结点（数据元素）由多个数据项构成，每个数据项表示该结点的某种性质。    数据项是数据的最小单位。    

如：学生登记表中的每个学生结点，由学号、姓名、性别、系别…… 等构成。

线性表是n个元素的有限序列，它们之间的关系可以排成一个线性序列：                  

a1，a2，…… ，ai，…… ，an 其中n称作表的长度，当n=0时，称作空表。

线性表的特点：

1. 线性表中所有元素的性质相同
2. 除第一个和最后一个数据元素之外，其它数据元素有    且仅有一个直接前驱和一个直接后继。第一个数据元素无前驱，    最后一个数据元素无后继
3. 数据元素在表中的位置只取决于它自身的序号

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

ADT List{      
    数据对象:D={ai|ai∈ElemSet, i=1,2,…,n,n>=0}
    数据关系:R1={<ai-1,ai>| ai-1,ai ∈D, i=1,2,…,n,n>=0}
   基本操作:InintList(&L);
 DestroyList(&L);
 ClearList(&L);
 ListEmpty(L);
 ListLength(L);
 GetElem(L,i,&e);
 LocateElem(L,e, compare());
 ListInsert(&L,i, e);
 ListDelete(&L,I,&e);
……..
}ADT List

基本操作：插入、删除、查找 ……     

e.g:已知线性表 La 和线性表 Lb 中的结点为递增序。将 La 和 Lb 进行合并至  另一线性表 Lc， 并仍为递增序。

La ＝ （3，5，8，11）             

Lb ＝ （2，6，8，9，11，15，20）              

Lc ＝ （2，3，5，6，8，8，9，11，11，15，20）     

合并的方法如下：

Void Mergelist(List La,list Lb, list & Lc)
{ 
InitiList( 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 ) ; ++i; };
   while (j <= Lb.len)  { GetElem(Lb,j,bj); Listinsert(Lc, ++k, bj ) ; ++j; };
}  // Mergelist La Lb

简单的用JavaScript实现：

var La = [3, 5, 8, 11];
var Lb = [2, 6, 8, 9, 11, 15, 20];
var Lc = [];
var i = 0, j = 0, k = 0;
while (i < La.length && j < Lb.length) {
    if (La[i] <= Lb[j]) {
        Lc[k++] = La[i];
        i++;
    } else {
        Lc[k++] = Lb[j];
        j++;
    }
}
while (i < La.length ) {
    Lc[k++] = La[i];
    i++;
}
while (j < Lb.length) {
    Lc[k++] = Lb[j];
    j++;
}
console.info(“Lc:” + Lc);

// 结果： Lc：(11) [2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20]

时间复杂性:  和表 La、Lb 中的结点个数（之和）成正比, 即T(n) = O(La.len + Lb.len)

 

2、线性表的顺序表示和实现     

1, 物理存储位置的计算：     

·顺序表示：在物理位置上紧靠在一起。如用数组表示线性表

·设第一个结点的存储地址为 LOC(a1), 余类推。设每个结点占用 L 个单元。则：LOC(ai) = LOC(a1) + (i-1)L

LOC(ai) = LOC(ai-1) + L = LOC(ai-2) + 2L = LOC(ai-(i-1)) + (i-1)L = LOC(a1) + (i-1)L
所以：
LOC(ai) = LOC(a1) + (i-1)L

·随机存取：访问任何一个数据元素或结点花费同样多时间

2，在 c 中的表示和实现：

·表示：

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

建立一个顺序存储的线性表：

Status InitiLIst_sqStack(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;
 }  // initList_Sq;

主程序： Sqlist a; InitList(a); // 生成顺序存 // 储的线性表

 3，插入和删除的实现程序：   

//插入
Status ListInsert_Sq(sqlist &L,int i, ElemType e)
{  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;
 }  // initList_Sq;线性表的第 i 个结点存于 L.elem[i-1] 之中。
//删除
Status ListDelete_Sq(sqlist &L,int i, ElemType &e)
{  if ( i <1 || i > L.length +1) return Error;
    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;
 }  // initList_Sq;线性表的第 i 个结点存于 L.elem[i-1] 之中。

 

3、线性表的链接表示和实现

• 将线性表的元素放到一个具有头指针的链表中，链表中每个结点包含数据域和指针域。    
• 数据域存放数据，指针域存放后继结点的地址，最后一个结点的指针域为空。
• 逻辑上相邻的数据元素在内存中的物理存储空间不一定相邻。

上图的线性表为 ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG

上图的线性表为 ZHAO，QIAN，SUN，LI，ZHOU，WU，ZHENG，WANG

线性链表表示法:

线性链表表示法

链式存储结构的特点：

• 插入、删除灵活方便，不需要移动结点， 只要改变结点中指针域的值即可。    
• 适合于线性表是动态变化的,    不进行频繁查找操作、但经常进行插入删除时使用。                            
• 链表的查找只能从头指针开始顺序查找。

单链表：

由n个结点链接起来，而且每个结点只包含一个指针域的链表称为线性链表或者单链表。

区别几个概念：头指针，头结点，首结点

在链表存储结构中，分带头结点和不带头结点两种存贮方式，采用带头结点的存储方式可以简化链表的操作过程，通常都采用这种方式。

头指针：是指向链表中第一个结点（首结点）的指针。    

头结点：在单链表的第一个结点之前附设的一个结点。

首结点：链表中存储线性表中第一个数据元素的结点。

若链表中附设头结点，则不管线性表是否为空，头指针均不空，否则表示空表的链表的头指针为空。

空链表：假设L是单链表 型变量，则L为单链表的头指针，它指向链表中第一个结点。

空链表则是L=NULL 带头结点的单链表L为空的判断条件是：  L->next==NULL

单链接表的表示，参照下图所示的情况： 其中 H 是头指针。

单链接表的表示，其中 H 是头指针

 

 

 

 

    

4、一元多项式的表示及相加