欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-05-26 11:33:44
...
数据结构——第二章 线性表
数据结构——第二章 线性表

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、一元多项式的表示及相加