数据结构与算法Python语言描述

会计学1数据结构与算法Python语言描述内容提要线性结构线性表的类型定义线性表的顺序表示和实现线性表的链式表示和实现第1页/共37页线性结构第2页/共37页学生信息表通讯录短信、聊天记录邮件列表购物清单账单何处用到线性结构？？？第3页/共37页首元素相邻的元素组成前驱与后继关系线性表线性表的逻辑结构尾元素第4页/共37页线性表线性表是n个数据元素的有限序列。一般形式：(a1,…,ai-1,ai,ai+1,…,an)直接前驱、直接后继长度：表中元素的个数n(n=0时称为空表)非空表中，每个元素都有一个确定的位置第5页/共37页结构+操作结构的创建、结构的销毁：构造与析构引用型（访问型）：get加工型（改变型）：set线性表抽象数据类型？第6页/共37页ADT

List

{数据对象：D＝{

ai

|

ai

∈ElemSet,

i=1,2,...,n,

n≥0}数据关系：R1＝{

<ai-1,ai>|

ai-1,ai∈D,

i=2,...,n}基本操作：■■InitList(

&L)//初始化操作结果：构造一个空的线性表L。■■CreatList(

&L,

n)//创建操作结果：构造一个含n个元素的线性表L。■■■DestroyList(

&L)//结构销毁初始条件：线性表L已存在。操作结果：销毁线性表L。线性表类型第7页/共37页//引用型操作■■■ListLength(

L)//求线性表的长度初始条件：线性表L已存在。

操作结果：返回L中元素个数。■■■■驱■■■■继■■■第8页/共37页ListEmpty(

L)

//判断线性表是否为空初始条件：线性表L已存在。操作结果：若L不空，返回true，否则为false。PriorElem(

L,

cur_e,

&pre_e)

//求数据元素的前初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。NextElem(

L,

cur_e,

&next_e)

//求数据元素的后初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。

GetElem(

L,

i,

&e)//取线性表中第i个数据元素初始条件：线性表L已存在，且1≤i≤LengthList(L)。操作结果：用e返回L中第i个元素的值。

LocateElem(

L,

e,

compare())//定位函数初始条件：线性表L已存在，e为给定值，■compare()是元素判定函数。第9页/共37页//加工型操作：&L!!!

ClearList(&L)//线性表置空■初始条件：线性表L已存在。■操作结果：将L重置为空表//插入数

ListInsert(&L,i,e)据元素第10页/共37页

题目：假设利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合

A=A∪B。

方法：只要从LB中依次取出每个数据元素，并依值在LA中进行查访，若不存在，则插入。线性表类型的应用——求集合的并集第11页/共37页void

unionSet(List

&La,

List

Lb){La_len

=

ListLength(La);Lb_len

=

ListLength(Lb);for(i

=

1;

i

<=

Lb_len;

i++){GetElem(Lb,

i,

e);if(!LocateElem(La,

e,

EQUAL))InsertList(La,

++La_len,

e);}}线性表类型的应用——求集合的并集第12页/共37页

题目：已知线性表LA和LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的数据元素仍按值非递减有序排列。

方法：设置两个指针分别指向LA和LB的当前元素，将数值较小的元素插入LC中。线性表类型的应用——归并操作第13页/共37页//

ClearListvoid

MergeList(List

La,

List

Lb,

List

&Lc){ClearList(Lc);

//这里假定Lc已经做过InitList操作，之后表的空间还在！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);}while

(j

<=

Lb_len)

{GetElem(Lb,

j++,

bj);

ListInsert(Lc,

++k,

bj);}}第14页/共37页线性表的顺序表示和实现线性表的链式表示和实现线性表的表示和实现第15页/共37页

是指用一组地址连续的存储单元依次存放线性表的数据元素以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑相邻线性表的顺序表示第16页/共37页

是指用一组地址连续的存储单元依次存放线性表的数据元素设每个数据元素需占用C个存储单元LOC(ai)

=

LOC(ai-1)

+

CLOC(ai)

=

LOC(a1)

+

(i-1)×C线性表的顺序表示和实现第17页/共37页

是指用一组地址连续的存储单元依次存放线性表的数据元素线性表的顺序存储结构是一种能够随机存取的存储结构，通常用动态数组来实现。线性表的顺序表示和实现第18页/共37页ElemType

*elem;//存储空间基址//当前长度■intint listsize;//当前分配的存顺序存储结构的表示a7a1

a2

a3

a4

a5

a6listsizeelem

#define

LIST_INIT_SIZE

100//线性表存储空间的初始分配量

#define

LISTINCREMENT

10//线性表存储空间的分配增量typedef

strulecngtth

{le第n19页g/t共3h7页;2023-02-1721279103listsizelengthelem动态内存空间LL

ii

ss

tt

类型的对象LL第20页/共37页Status

InitList(List

&L)

{//分配空间■■//空间总长赋初值顺序存储时基本操作的实现ll

ii

ss

tt

ss

ii

zz

eeL.listsize

=

ee

ll

ee

mmL■L.elem

=

(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)

exit(OVERFLOW);ll

ee

nn

gg

tt

hh

==

00IST_INIT_SIZE;第21页/共37页【结构的销毁——没有空间了！】void

DestroyList(List

&L)

{//空间释放■free(L.elem);L.elem

=

NULL;■}L.length

=

0;L.listsize

=

0;第22页/共37页//引用型

void

TraverseList(List

L,

void(*visit)(ElemType)){■for

(i

=

0;

i

<

L.length;

i++) (*visit)(L.elem[i]);}//加工型—第—23页/m共a37页p操作！void

TraverseList(List

&L,Status

GetElem(List

L,

int

i,

ElemType

&e)

{//i的合法性检测if

(i

<

1

||

i

>

L.length)

return

ERROR;//取元素e

=

L.elem[i-1];return

OK;}第24页/共37页int

LocateElem(List

L,

ElemType

e,Status

(*compare)(ElemType,

ElemType))

{//起步i

=

1;p

=

L.elem;//在有效范围内查询while(i

<=

L.length

&&

!(*compare)(*p++,

e))++i;//返回元素的真实位置if

(i

<=

L.length)

return

i;else

return

0;}第25页/共37页int

LocateElem(List

L,

ElemType

e,Status

(*compare)(ElemType,

ElemType))

{//起步i

=

1;//在有效范围内查询while(i<=L.length

&&

!(*compare)(L.elem[i-1],e))++i;//返回元素的真实位置if

(i

<=

L.length)

return

i;else

return

0;}第26页/共37页插入操作：Status

InsertList()插入前的线性表：(a1,…,ai-1,ai,ai+1,…,an)插入后的线性表：(a1,…,ai-1,b,ai,ai+1,…,an)时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化第27页/共37页第28页/共37页

Status

InsertList(List

&L,

int

i,ElemType

e)

{//插入范围的合法性检测

if

(i

<

1

||

i

>

L.length+1)return

ERROR;if(L.length

>=

L.listsize)

{ newbase

=

(ElemType//空间不够，追加第29页/共37页【数组方式的元素移动、插入】

//从插入位置开始向后的元素，自后向前依次后移■for(j

=

L.length;

j>=i;

j--)

{L.elem[j]

=

L.elem[j-1];}■■//插入e，修改表长■L.elem[i-1]

=

e;++L.length;第30页/共37页

【指针方式的元素移动、插入，有些难以阅读。。。。】

//从插入位置开始向后的元素，自后向前依次后移■■q

=

&(L.elem[i-1]);for

(p

=

&(L.elem[L.length-1]);p

>=

q;

--p)*(p第+311页)/共3=7页*p;删除操作：Status

DeleteList()删除前的线性表：(a1,…,ai-1,ai,ai+1,…,an)删除后的线性表：(a1,…,ai-1,ai+1,…,an)时间复杂度：最坏和平均的情况O(n)逻辑关系发生了变化第32页/共37页第33页/共37页Status

DeleteList(List

&L,

int

i,

ElemType

&e)

{//合法性检测if

((i

<

1)

||

(i

>

L.length))

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;}第34页/共37页//两个表的有序归并//此处作为List类型的基本操作直接定义！！！void

MergeList(List

La,

List

Lb,

List

&Lc){【此处应细致考虑，如果！=NULL，要先做销毁DestroyList操作，再重新开空间！】//开了最少的空间Lc.l