DS笔记(2)顺序表与链表

王朝other·作者佚名  2006-02-01
窄屏简体版  字體: |||超大  

DS笔记(2)顺序表与链表

一、 顺序表---线性表的顺序存储

1.内涵:

线性表的顺序存储指用一组地址连续的存储

单元依次存储线性表的数据元素。这称为顺序表。

2.特点:

* 存储单元地址连续(需要一段连续空间)

* 逻辑上相邻的数据元素其物理位置也相邻

* 随机存取

* 存储密度为大(100%)

3.优点:

* 不需要额外空间来存储元素之间的关系

* 可以随机存取任一元素

4.缺点:

* 插入和删除运算需要移动大量元素

* 需要一段连续空间

* 预先分配足够大的空间

* 表的容量难以扩充

(可以通过使用动态数组数据类型来描述顺序表而改进最后两个缺点)

5.存储位置的计算

对线性表L,设每个元素占k个存储单元,则有:

递推关系:

LOC(ai+1)=LOC(ai )+k

任一元素ai+1的存储位置:

LOC(ai)=LOC(a1 )+(i-1)*k

(其中1<= i <=ListLength(L))

二、 链表---线性表的链式存储

1.内涵:

线性表的链式存储指用任意的存储单元存放线性表中的元素,每个元素与其前驱和(或)后继之间的关系用指针来存储。这称为链表。

术语:

* 结点

* 数据域

* 指针域

* 头指针

* 头结点

分类:

* 单链表

* 循环链表

* 双向链表

* 双向循环链表

* 静态链表

2.数据类型描述

//----------用结构指针描述------------

typedef struct LNode{

ElemType data //数据域

struct LNode *next //指针域

} Lnode, *LinkList

3.单链表上插入运算的实现T(n)=O(n)

4.链表应用:一元多项式的相加

一元多项式的链式存储结构

//----------用结构指针描述------------

typedef struct Term{

float coef //系数数据域

int expn //指数数据域

struct Term *next //指针域

} Term, *LinkList

一元多项式相加的运算规则

“和多项式”中结点无需另生成,可看成是将多项式B加到

多项式A上。设p和q分别指向多项式A和B中某一结点,比较结点中的指数项:

若p^.exp<q^.exp,则p结点应是“和多项式”中的一项,令p指针向后移;

若p^.exp>q^.exp,则q结点应是“和多项式”中的一项,令q结点插入在p结点之前,且q指针在原来的链表上后移;

若p^.exp=q^.exp,则将两个结点中的系数相加,当和不为零时修改p结点中的系数域,释放q结点;反之,“和多项式”中没有此项,从A表中删去p结点,同时释放p和q结点。

算法如下:

PROC add_poly(VAR pa:polyty; pb:polytp);

p:=pa^.next; q:=pb^.next;

pre:=pa; pc:=pa;

WHILE (p!=NIL)AND (q!=NIL) DO

CASE

p^.exp<q^.exp:

[pre:=p; p:=p^.next];

p^.exp=q^.exp:

[x:=p^.coef+q^.coef;

IF x!=0

THEN [ p^.coef:=x; pre:=p]

ELSE [pre^.next:=p^.next;

dispose(p)];

p:=pre^.next; u:=q;

q:=q^.next; dispose(u)]

p^.exp>q^.exp:

[u:=q^.next; q^.next:=p; pre^.next:=q; pre:=q; q:=u ]

IF q!= NIL THEN pre^.next:= q;

dispose(pb);

ENDP; {add_poly}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航