数据结构2

 

线性表

 

 

 

线性结构是一个数据元素的有序（次序）集

 

 

 

线性结构的基本特征：

 

1、集合汇总必存在唯一的一个“第一元素”

 

2、集合中必存在唯一的“最后元素”

 

3、除最后元素外，均有唯一的后继

 

4、除第一元素外，均有唯一的前驱

 

 

 

<!--[if !supportLists]-->1、  <!--[endif]-->线性表的类型定义

 

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

 

ADT List{

 

         数据对象

 

         D={a1|a1<ElemSet,i=1,2,,,,,,n,n>=0}

 

                   称n为线性表的表长

 

                   称n=0时的线性表为空表

 

}

 

数据关系

 

R1={<ai-1,ai>|ai-1,ai属于D,i=2,,,,,n}

 

 

 

基本操作：

 

 

 

结构初始化

 

InitList(&L)

 

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

 

 

 

销毁结构

 

DestoryList(&L)

 

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

 

操作结果：销毁线性表L。

 

 

 

引用型操作

 

ListEmpty(L)

 

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

 

操作结果：若L为空表，则返回true,否则返回false

 

 

 

ListLength(L)

 

初始条件:线性表L已经存在。

 

操作结果：返回L中元素的个数。

 

 

 

PriorElem(L,cure_e)

 

初始条件：线性表L存在。

 

操作结果：若cur_e是L的元素，但不是第一个，则返回它的前驱，否则操作失效，

 

 

 

NextElem(L,cur_e)

 

初始条件：线性表L存在。

 

操作结果：若cur_e是L的一个元素，但不是最后一个元素，返回cur_e的下一个元素。

 

 

 

GetElem(L,i)

 

初始条件：线性表L存在，且1<=i<=LengthList(L)

 

操作结果：返回L中第i个元素的值

 

 

 

LocateElem(L,e,compare())

 

初始条件：线性表L存在，compare()是元素判定函数

 

操作结果：返回L中第1个与e满足关系compare()的元素的位序，若这样的元素不存在，则返回值为0

 

 

 

ListTraverse(L,visit())

 

初始条件：线性表L存在。

 

操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。

 

 

 

加工型操作

 

 

 

clearList(&L)

 

初始条件：线性表L存在。

 

操作结果：将L重置为空表。

 

 

 

PutElem(L,i,&e)

 

初始条件：线性表L存在，且1<=i<=LengthList(L)

 

操作结果：L中第i个元素赋值，同e的值

 

 

 

ListInsert(&L,i,e)

 

初始条件：线性表L存在，且1<=i<=LengthList(L)+1

 

操作结果：L中第i个元素之前插入新的元素e，L的长度增1.

 

 

 

例1、假设：有俩个集合A和B分别用俩个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员）

 

现要求一个新的集合A= A ∪ B

 

 

 

上述问题可演绎为，要求对线性表作如下操作：

 

扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。

 

 

 

1、从线性表LB中依次取得每个数据元素：

 

GetElem(LB,i)

 

2、依值在线性表LA中进行查访

 

LocateElem(LA,e,equal())

 

3、若不存在，则插入之。

 

ListInsert(LA,n+1,e)

 

 

 

代码实现：

 

void union(List La,List Lb){

 

         La_len = ListLenth(La);

 

         Lb_len =ListLenth(Lb);

 

         for(int i=0;i<=Lb_len;i++){

 

                   GetElem(Lb,i,e);

 

                   if(!LocateElem(La,e,equal())

 

                            ListInsert(La,++La_len;e);

 

         }

 

}

 

 

 

例2，已知一个非纯集合B，试狗杂一个纯结合A，使得A中只包含B中所有值各不相同的数据元素。

 

 

 

void union(List La,List Lb){

 

         InitList(La);//与上一个例子的区别，就是多了一个空表初始化

 

         La_len = ListLenth(La);

 

         Lb_len =ListLenth(Lb);

 

         for(int i=0;i<=Lb_len;i++){

 

                   GetElem(Lb,i,e);

 

                   if(!LocateElem(La,e,equal())

 

                            ListInsert(La,++La_len;e);

 

         }

 

}

 

 

 

 

 

 

 

二、线性表类型的实现------顺序映像

 

用一组地址连续的存储单元，依次存放线性表中的数据元素

 

a1,a2,....a(i-1),ai.......an

 

线性表的起始地址，称作线性表的基地址

 

 

 

顺序映像的C语音描述

 

#define LIST_INIT_SIZE 80 //线性表存储空间的初始分配量

 

#define LISTINCREMENT 10 //线性表存储空间的分配增量

 

typedof struct{

 

ElemType *elem; //存储空间基地

 

int length;//当前长度

 

int listsize; //当前分配的存储容量

 

}

 

 

 

线性表的初始化操作

 

Status InitList_sq(SqList &L){

 

         //构造一个空的线性表

 

         L.elem=(ElemType*)maclloc(LIST_INIT_SIZE*sizeof(ElemType));

 

         if(!L.elem)

 

                   exit(OVERFLOW);

 

         L.length=0;

 

         L.listsize=LIST_INIT_SIZE;

 

         return OK;

 

}//initList Sq

 

 

 

线性表操作LocateElem(L,e,companre())的实现; //查找和e满足compare（）关系的值

 

int LocateElem_sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)){

 

         i=1;

 

         p=L.length;

 

         while(i<=L.length&&!(&compare)(*p++,e))

 

                   ++i;

 

         if(i<=L.length;

 

                   return i;

 

         else

 

                   return 0;

 

}

 

 

 

线性表操作ListInsert(&L,i,e)的实现

 

问：插入元素时，线性表的逻辑关系发生什么变化

 

(a1,.....a(i-1),ai,,,,,an)改变为

 

(a1,,,,,,a(i-1),e,ai,,,,,an)

 

地址变化如下：

 

A1

A2

…..

Ai-1

Ai

…..

An

 

 

 

A1

A2

……

Ai-1

E

Ai

…..

an

 

 

 

 

 

<!--[if !supportLists]-->2、  <!--[endif]-->线性表类型的实现---链式映像

 

 

 

1、单链表

 

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

 

以元素+指针=节点

 

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

 

头->a1->a2->.....->an

 

 

 

以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。

 

 

 

 

 

结点和单链表的C语言描述

 

Typedof struct LNode{

 

         ElemType data;//数据域

 

         struct Lnode *next;//指针域

 

}LNode,*LinkList;

 

 

 

线性表的操作GetElem(L,i,&e)在链表中的实现

 

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

 

Status GetElem L(LinkList L,int pos,ElemType &e){

 

         p=L->next; j=1; //初始化，p指向第一个结点,j为计数器

 

         while(p&&j<post){

 

                   p=p->netx;++j;

 

         }

 

         if(!p||j>pos)

 

                   return ERROR;//第pos个元素不存在。

 

         e=p->data; //取第pos个元素

 

         return OK;

 

}

 

 

 

线性表的操作ListInsert(&L,i,e)在链表中的实现

 

基本操作：找到线性表中第在i-1个结点，修改其指向后继的指针

 

 

 

有序对<a(i-1),ai>改变为<a(i-1),e>和<e,ai>

 

 

 

Status ListInsert L(LinkList L,int pos,ElemType c){

 

         p=L;j=0;

 

         //寻找第pos-1个结点

 

         while(p&&j<pos-1){

 

                   p=p->next;

 

                   ++j;

 

         }

 

         if(!p||j>pos-1)

 

                   return ERROR;//pos小于1或者大于表长

 

         s=(LinkList)malloc(sizeof(LNode));//生成新结点

 

         s->data=e;

 

         s->next=p->next;//插入L中

 

         p->next=s;

 

         return OK;

 

        

 

}

 

 

 

 

 

 

 

 

 

线性表的操作ListDelete(&L,i,&e)在链表中的实现：

 

基本操作为：找到线性表中第i-1个结点，修改其指向后继的指针

 

有序对<a(i-1),ai>和<ai,a(i+1)>改变为<a(i-1),a(i+1)>

 

 

 

Status ListDelete_L(LinkList L,int pos,ElemType &e){

 

         p=L,j=0;

 

         while(p->next&&j<pos-1){

 

                   p=p->next;

 

                   j++;

 

         }

 

         if(!(p->next)||j>pos-1)

 

                   return ERROR;

 

         q=p->next;

 

         p->next=q->next;

 

         e=q->data;

 

         free(q);

 

         return OK;

 

}

 

 

 

链表的创建

 

void createList_L(LinkList&L,int n){

 

         L=(LinkList)malloc(sizeof(LNode));

 

         L->next=NULL;//先建立一个带头结点的单链表

 

         for(i=n;i>0;--i){

 

                   p =(Linklist)malloc(sizeof(LNode)); 

 

                   scanf(&p->data);//输入元素值

 

                   p->next=L->netx;

 

                   L->next=p;

 

         }

 

}

 

 

 

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

 

1、单链表的表长是一个隐含的值。

 

2、在单链表的最后一个元素最后插入时候，需要遍历整个链表

 

3、在链表中，元素的“位序”概念淡化、结点的“位置”概念强化。

 

改变链表的设置：

 

1、增加“表长”，“表尾指针”，和“当前位置的指针”三个数据域；

 

2.将基本操作“位序”改成“指针”

 

 

 

五，其他形式的链表

 

1、双向链表

 

typedef struct DulNode{

 

         ElemType data; //数据域

 

         struct DulNode *prior;//指向前驱的指针域

 

         struct DulNode *next;//指向后继的指针域

 

}

 

 

 

2、循环链表

 

最后一个节点的指针域的指针又指向第一个节点的链表

 

<!--[if !supportLists]-->3、  <!--[endif]-->一元多项式的表示

 

 

 

p(x)=p0+p1x+p2x+...+pnx

 

在计算机中，可以用一个线性表来表示

 

 

 

一般情况下，使用的时候存储结构不经常发生变化，使用线性表，如果使用的时候，存储结构经常发生变化，使用链表。