亲宝软件园·资讯

展开

常见的基本数据结构——表

Baby-Lily 人气:0

表 ADT

形如A1,A2,A3,.....,An这样的表。这个表的大小是n,大小为0的表为空表。

对于除空表外的任何表,我们说A[i+1]后继A[i]并且A[i-1]前驱A[i]。表中的第一个元素A[1]不定义前驱,最后一个元素A[N]不定义后继。

表ADT上面的操作:PrintList,MakeEmpty,Find,FindKth,Insert,Delete。

 

表的简单数组

对表的所有操作都可以通过使用数组来实现。需要对表的最大值进行预估,估计大了会严重的浪费空间。

数组实现使得PrintList和MakeEmpty以线性时间执行,而FindKth花费常数时间,但是插入和删除的代价

是昂贵的。插入需要将后面的元素进行向后移动,删除需要将后面的元素向前移动。平均来看,还是以线性时间执行。

 

链表

为了避免插入和删除的开销,我们允许使用不连续存储。

链表由一系列不必再内存中相连的结构组成。每一个结构均包含有表元素和指向后继元素的指针。我们称之为Next指针。最后的Next指针指向NULL。

 

链表上面的操作

对于PrintList和Find只需间指针传递到该表的第一个元素,然后用一些Next指针传递即可,此时的时间是线性的。删除命令可以通过修改指

针来实现,插入命令需要申请空间调用mallo函数,然后调整两次指针。

下面是链表的相关操作的具体实现

 

链表的类型声明

struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

struct Node{
     ElementType Element;
     Position Next;
};

 

判断链表是否为空

int
IsEmpty(List L){
     return L->Next == NULL;
}

 

判断当前是否为链表的末尾位置

int
IsLast(Position P,List L){
     return P->Next == NULL;
}

 

Find查找函数

Position
Find(ElementType X, List L){
    Position p;
    P = L->Next;
    while(p != NULL && p->Element != X){
        p = p->Next;
    } 
     return p;
}

 

链表的删除操作

void 
Delete(ElementType X, List L){
    Position p, TepCell;
    p = FindPrevious(X);
    if(!IsLast(P, L)){
        TmpCell = p->Next;
        p->Next = TmpCell->Next;
        free(TmpCell);
    } 
}

Position
FindPrevious(ElementType X, List L){
    Position P;
    P = L;
    while(P->Next != NULL && P->Next->Element != X){
        p=p->next;
    }
    return P;
}
    

 

链表的插入操作

void
Insert(ElementType X, List L, Position P){
    Position TmpCell;
    TmpCell = malloc(sizeof(Struct Node));
    if(TMpCell == NULL){
        FatalError(”out of space”);
    }
    TmpCell->Element = X;
    TmpCell->Next = P->Next;
    P->Next = TmpCell;
}

注意上述的方法中的参数,虽然有些参数在函数中没有使用,但是之所以这么做是因为别的实现方法可能会用上。

对于上述的操作,最坏的情况是扫描整个表,平均来看运行时间是O(N),因为必须平均扫描半个表。

 

常见的错误

当指针为空时,指向的是非法空间,使用指针的属性或者操作时将会产生错误,无论何时只要你确定一个指向,就必须要保证该指针不是NULL。

删除表的不正确的做法

void
DeleteList(List L){
    Position P, Tmp;
    P = L->Next;
    L->Next = NULL;
    while(P != NULL){
        Tmp = P->Next;
        free(P);
        P = Temp;
    }
}

 

双链表

有时候以倒序扫描链表很方便,标准的实现方法却是无能为力了,然而解决办法很简单,就是在数据域附加上一个域,使它包含指向前一个单元的指针即可。其附加的开销是它增加了空间,同时插入

和删除的开销增加了一倍,因为有更多的指针需要定位。另一方面,它简化了删除操作,不再使用指向前驱的的指针来访问关键字。

 

循环链表

让最后的元素反过来指向第一个元素是一种流行的做法,若有表头,则最后的元素就指向表头,并且它还可以是双向链表。

 

多项式ADT

我们用表来定义一种一元(具有非负次幂)多项式的的抽象数据类型。如果多项式的大部分系数非零,那么可以用一个简单的数组来存储这些系数。

多项式ADT的数组实现类型声明

typedef struct{
    int Coeffarray[MaxDegree + 1];
    int HighPower;
}* Polynomial;

//将多项式初始化为0的过程
void
ZeroPolynomial(Polynomial Poly){
    int i;
    for(i=0; i<=MaxDegree; i++){
        Poly->CoffArray[i] = 0;
    }
    Poly->HighPower = 0;
}

两个多项式相加

void 
AddPolynomial(const Polynomial Poly1, const Polynomial Poly2, Polynomial PolySum){
    int i;
    ZeroPolynomial(PolySum)
    PolySum->HighPower = Max(Poly1->HighPower, Poly2->HighPower);
    for(i=PolySum->HighPower; i>=0; i++){
       PolySum->CoeffArray[i] = Poly1->CoeffArray[i] + Poly2->CoeffArray[i];
    }
}

两个多项式相乘的过程

void
MultPolynomial(onst Polynomial Poly1, const Polynomial Poly2, Polynomial PolyProd){
  int i, j;
  ZeroPolynomial(PolyProd);
  PolyProd->HighPower = Poly1->HighPower + Poly2->HighPower;
  if(PolyProd->HighPower > MaxDegree){
    Error(Except array size);
  }else{
    for(i=0; i<=Poly1->HighPower; i++){
      for(j=0; j<=Poly2->HighPower; j++){
        PolyPord->CoeffArray[i + j] = Poly1->CoeffArray[i] * Poly2->CoeffArray[j];
      }
    }
  }
}

多项式的另一种表示方法:

通过单链表的方式表示多项式,多项式的每一项保存在链表元素中,并且按照幂的大小间须降序进行排列。

多项式的表示多用于较稀疏的多项式的情况,需要注意的操作时,当链表的多项式相乘时,需要进行多项式的合并同类型。

typedef struct Node *PtrToNode;
struct Node{
  int Coefficient;
  int Expoent;
  PtrToNode Next;
};
typedef PtrToNode Polynomial;

 

基数排序

将链表用于基数排序(radix sort),基数排序有时也称为卡式排序,因为在现代计算机出现之前,它一直用于老式穿孔卡的排序。

如果我们有N个整数,它的范围是从1到M(或者是0到M-1),我们可以利用这个信息得到一种快速排序,叫做桶式排序。我们留置一个数组称为Count,大小为M,并初始化为0。那么,Count有M个单元(桶),开始时他们都是空的。当Ai被读入时令Count[Ai]+1。当所有的输入结束后,扫描Count数组,打印好排序的数组。该算法花费的时间是O(M+N),如果M=N,那么桶排序为O(N)。

基数排序是这种方法的推广。下面的这个例子就是详细的说明,设我们有10个数,范围是0到999之间,我对其排序。一般来说,这是0到N^P-1之间的N个数,p是某个常数。显然我们不适合使用桶排序,因为这样桶太多了。于是我们的策略是使用多次桶排序,通过用最低位优先的方式,进行桶排序,算法将得到正确的结果。如果使用最高位将会出现错误,而且还无法判断最高位。当然,有时会有多个数落入到桶中,而且这些数还是不同的,因此我们需要使用一个表来保存,因为所有的数字都可能有某位,所以用简单数组来保存的话,数组的空间需求是O(N^2)。

下面是10个数的桶式排序的具体例子。本例的输入是:64,8,216,512,27,729,0,1,343,64。为了是问题简化,此时操作按基是10进行,第一遍桶排序的结果是0, 1, 512, 343, 64, 125, 216, 27, 8, 729。在使用次低位对第一遍桶排序的结果进行排序,得到第二次桶排序的结果:0,1,8,512,216,125,27,729,343,64。最后按照最高位进行排序,最后得到的表:0,1,8,27,64,125,216,343,512,729。

第一趟桶排序结果

0

1

512

343

64

125

316

27

8

729

0

1

2

3

4

5

6

7

8

9

第二趟桶排序结果

8

1

0

 

216

512

729

27

125

 

 

 

343

 

 

 

64

 

 

 

0

1

2

3

4

5

6

7

8

9

第三趟桶排序结果

67

27

8

1

0

 

 

 

 

125

 

 

 

 

216

 

 

 

 

343

 

 

 

 

 

512

 

 

 

 

 

729

 

 

0

1

2

3

4

5

6

7

8

9

 

在使用数组进行实现时,下面的算法的步骤:

  1.计算待排序数组的最大位数。

  2.对桶数组和下表数组进行初始化,根据位数进行循环。

  3.根据当前的位数,对待排数组进行遍历,计算出当前位的数值,根据数值将其放入对应的桶数组中,并更新下表数组。

  4.将桶数组中的元素更新到待排数组中,

  5.更新位数计算,跳转至2步骤,直至位数大于最大位数。

该排序算法的时间复杂度是O(P(N+B)),其中P是排序趟数,N是要被排序的元素的个数,B是桶数。该算法的一大缺点是不能用于浮点数的排序。

当我们把32位机器所能便是的所有整数进行排序时,假设我们在大小为2^11的桶分三趟进行即可,并且算法总是O(N)的时间消耗。

 

多重表

常见的多重链表是十字链表,十字链表的特点是对于二维的数据,它也能够通过不连续的空间进行表达,即水平方向和垂直方向都是都是链表,且可以是循环链表。

链表的游标实现

在一些不支持指针的语言中,如果需要链表而不能使用指针的话,那么游标法是一种实现方式。

链表的指针实现的重要特点

1.数据存储在一组结构体中,每个结构体含有指向下一个结构体的指针。

2.一个新的结构体可以通过调用malloc从系统中得到,并通过调用free而被释放。

游标实现必须要满足上述条件,条件一可以通过全局结构体数组实现,通过数组下标代表一个地址。

下面是游标的实现

struct Node{
  ElementType Element;
  Position Next;
}
struct Node CursoSpace[SpaceSize];

为了模拟条件二,让CursorSpace数组中的单元代替malloc和free的职能。为此,我们保留一个表,表由不再任何表中的元素构成。该表将用0作为表头,对于Next,0的值为NULL,为了执行malloc功能,将第一个元素从freelist中删除,为了执行free功能,我们将该单元放在freelist的前段。

下面是malloc函数和free函数的实现

static Position
CoursorAlloc(void){
  Position P;
  P = CoursorSpace[0].next;
  CursirSpace[0].Next = CursorSpace[P].next;
  return P;
}
static void
CursorFree(Position P){
  CursorSpace[P].next = CursorSpace[0].next;
  CursorSpace[0].next = P;
}

下面是一个链表游标实现的列表:

slot

Element

Next

0

-

6

1

b

9

2

f

0

3

header

7

4

-

0

5

header

10

6

-

4

7

c

8

8

d

2

9

e

0

10

a

1

slot

Element

Next

0

-

6

1

b

9

2

f

0

3

header

7

4

-

0

5

header

10

6

-

4

7

c

8

8

d

2

9

e

0

10

a

1

判断链表是否为空
int IsEmpty(List L){
  return CursorSpace[L].Next == 0;
}
判断P是否是链表的末尾
int IsLast(Position P, List L){
  return CursorSpace[P].Next == 0; 
}

游标的Find实现
Position Find(Element X, List L){
  Position P;
  P = CursorSpace[L].Next;
  while(P && CursorSpace[P].Element != X){
    P = CursorSpace[P].Next;
  } 
  reutrn P;
}

链表的delete操作 void Delete(Element X, List L){   Position P, TmpCell;   P = FindPrevious(X, L);   if(!IsLast){     TmpCell = CursorSpace[P].Next;     CursorSpace[P].Next = CursorSpace[TmpCell].Next;     CursorFree(TmpCell);   } }

加载全部内容

相关教程
猜你喜欢
用户评论