《软件技术基础》03 基本数据结构及其运算

第二章

基本数据结构及其运算

软件技术基础》课件制作人：钱玉文第

2

章基本数据结构及其运算

（有*号的标题表示最基本的内容）

2.1数据结构的基本概念*2.1.1

什么是数据结构2.2线性表

2.2.1

线性表的基本概念

2.2.2

线性顺序表及其运算

2.2.3

线性链表及其运算

2.2.4

栈及其应用

2.2.5

队列及其应用教学内容一、数据结构概述数据、数据元素、数据结构、逻辑结构、 物理结构、算法、特征、评价二、顺序表 线性表、顺序表、描述、创建、插入、删除等算法三、链表单链表、循环链表、双向链表、双向循环链表判空、插入、删除、定位等操作指针域、数据域、头节点、头指针2.1.1什么是数据结构数据（Data）

能存于计算机、并被计算机处理的符号的集合。它是客观事物的符号表示。数据元素（Element）

是数据的基本单位、数据集合中的个体。数据结构（DataStructure）

是带有结构特征的数据元素的集合；它有三个要素：

DS=数据的逻辑结构+存储结构+数据的运算一.基本概念二.数据的逻辑结构概念：客观事物本身存在的结构形式及关系。特点：描述数据间的顺序（逻辑）关系，抽象地反映数据元素的结构，而不管它们在计算机中如何存放。

与物理存放位置无关描述方法：用二元组来描述：

DS=（D，R）其中：

D：是数据元素的有限集合；

R：是数据元素之间关系的集合。成员：由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。数据结构的形式化描述：定义DS如下：

Group=（D，R）

其中：D={T，G1，…,Gn,S11,…Snm}1≤n≤3,1≤m≤2R={R1,R2}R1={<T,Gi>|1≤i≤n,1≤n≤3}R2={<Gi,Sij>|1≤

i≤

n,1≤

j≤m,1≤n≤3,1≤m≤2}1.数据的逻辑结构-举例（1）线性结构：一对一次序关系（2）树形结构：一对多层次关系（3）图或网状结构：多对多关系（4）集合：属性相同，元素间没有关系2.数据逻辑结构的类别7三、数据的存储结构

~是指数据结构在计算机中的表示(又称映象)，即数据在计算机中的存放形式。 逻辑结构在存储器中的映射。又称物理结构数据存储结构分类1.顺序存储结构2.链式存储结构3.索引存储结构（略）4.散列存储结构

（略）1.顺序存储结构概念：把数据元素按某种顺序存放在一块连续的存 储单元中的存储形式。数据结点结构:

d1d2……

dn数据域特点:

连续存放;逻辑上相邻,物理上也相邻。结构简单，易实现。插入、删除操作不便（需大量移动元素）。2.链式存储结构概念：以链表形式将数据元素存放于任意存储单元 中，可连续存放，也可以不连续存放，以指 针实现链表间的联系。数据结点结构:

d1...

d2dn

^特点:

非连续存放,借助指针来表示元素间的关系;插入、删除操作简单，只要修改指针即可；结构较复杂，需要额外存储空间。数据域指针域总结：

（1）逻辑结构和物理结构的关系数据的逻辑结构是从逻辑关系（某种顺序）上观察数据，它是独立于计算机的；可以在理论上、形式上进行研究、推理、运算等各种操作。数据的存储结构是逻辑结构在计算机中的实现，是依赖于计算机的；离开了机器，则无法进行任何操作。任何一个算法的设计取决于选定的逻辑结构；而算法的最终实现依赖于采用的存储结构。逻辑结构：独立于计算机。存储结构：依赖于计算机算法设计考虑逻辑结构，算法实现依赖存储结构。总结：

（2）数据结构分类线性表堆栈队列串数组树二叉树图线性结构非线性结构数据结构DS2.2线性表

2.2.1线性表基本概念线性表是指数据元素之间的关系为一一对应的线性关系的数据结构。

例如，一星期七天的英文缩写表示：

（Sun，Mon，Tue，Wed，Thu，Fri，Sat）是一个线性表，其中的元素是字符串，表的长度为7。

线性表虽然简单，但是应用范围非常广泛。非空线性表的结构特征有且只有一个根结点a1，它无前件；有且只有一个终端结点an，它无后件；除根结点和终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。一、线性表的逻辑结构定义：线性表是n（n≥0）个元素a1,a2,…,an

的有限序列；表中每个数据元素，除第一个外，有且只有一个前件；除最后一个外，有且只有一个后件。即线性表或是一个空表，或可以表示为例如：一星期七天的英文缩写表示：（Sun，Mon，Tue，Wed，Thu，Fri，Sat）是一个线性表，其中的元素是字符串，表的长度为7。二、元素关系描述1）L的长度为n（n≥0），当n为0时，表示是空表；

2）每个元素（除了第1个和最后一个元素外），有唯一的前件和后件；3）线性表中各元素间存在着线性关系；4）均匀性；各元素数据类型必须相同；5）有序性；各元素是有序的，不可交换次序。2.2.2线性顺序表存储结构线性表的顺序存储结构

将表中元素一个接一个的存入一组连续的存储单元中，这种存储结构是顺序结构。顺序表

采用顺序存储结构的线性表简称为“顺序表”。顺序表的存储特点：只要确定了起始位置，表中任一元素的地址都通过下列公式得到：

LOC（ai）=LOC（a1）+（i-1）*L1in

其中，L是每个元素占用存储单元的长度。一、定义二、线性表元素存储示意图

a1a2….ai….元素序号内存状态存储地址2

i1….….LOC(a1)LOC(a1)+1L….LOC(a1)+(i-1)L….三、线性表的基本操作Setnull（L）

置空表Length（L）

求表长度；求表中元素个数Get（L，i）

取表中第i个元素（1in）Prior（L，i）

取i的前件元素Next（L，i）

取i的后件元素Locate（L，x）

返回指定元素在表中的位置Insert（L，i，x）插入元素Delete（L，x）删除元素Empty（L）判别表是否为空顺序表(SeqList)类的定义template<classType> class

SqList

{Type*v;//顺序表存储数组

intmm; //最大允许长度

int

nn; //当前线性表的长度public:

Sq_LList(){mm=0;nn=0};

Sq_LList(int);

int

Prt_sq_list(Type

&x);//前驱

int

flag_sq_LList();voidins_sq_LList(int,T);voiddel_sq_LLIst()}1.插入算法线性表的存放形式：采用一维数组存放。操作要求：将X插入线性表（a1,a2,……,an）中 的第i个位置算法步骤:

step1将第n至第i个元素后移一个存储位置;

step2将x插入到ai-1之后;

step3表的长度加1。表项的插入2534571648096301234567data50插入x253457501648096301234567data50i长度为n的线性表中的第i个元素之前插入新元素b。PROCEDUREINSL（V，m，n，i，b）IF（n=m）THEN{OVERFLOW；RETURN}IF(i>n)THENi＝n＋1IF（i＜1)THENi＝1FORj=nTOiBY–1DOV（j+1）=V（j）V(i)=bn＝n＋1RETURNtemplate<classT>int

Sq_LList<T>::Ins_sq_LList(T*v,int*n;inti;Tb)//在表中第

i个位置插入新元素

b

{intk;if(*n==m){cout<<“overflow”<<endl;return;}if(i>*n)i=*n+1;

if(i<1)i=1;for(k=*n;k>=i;k--)v[k]=v[k-1];v[i-1]=b;*n=*n+1;return;}2.删除算法线性表的存放形式：采用一维数组存放。操作要求：删除线性表(a1,a2,……,an)中的第i个元素算法步骤:step1判别指定的位置是否合法；

step2若合法，则将位置i+1至n上的元素前移一个存储位置;

step3表的长度减1。表项的删除253457501648096301234567data16删除

x2534575048096301234567data在长度为n的线性表中删除第i个元素PROCEDUREINSL（V，m，n，i）IF（n=0）THEN{UNDERFLOW；RETURN}IF((i<1)or(i>n))THEN{“Notthiselementinthelist”;RETURN}FORj=iTOn-1DOV（j）=V（j+1）n＝n-1RETURN

template<classT>void

del_sq_LList

(T&v,intm,int*n,inti){//在表中删除已有第i元素

intk;

if(*n==0){cout<<“underflow”<<endl; return; }

if(i<1||i>*n){cout<<“underflow”<<endl; return; }for(k=i;k<*n;k++)v[k-1]=v[k];*n=*n-1;return0;

}总结：

顺序存储结构的优缺点数据连续存放、随机存取逻辑上相邻，物理上也相邻存储结构简单、易实现插入、删除操作不便存储密度大，空间利用率高结论：

顺序存储结构适合于表中元素变动较少的情况。2.2.3线性表链式存储结构线性表的顺序存储结构容易实现，可以随机存取表中的任意元素。顺序表缺点是：难于插入、删除操作；需要预先分配空间，不管这些空间能否最大限度地利用。链表存储结构在这两个方面恰好是优点：容易插入、删除操作不需要预分空间。一、链表有关基本概念定义：线性表的链式存储结构称为线性链表

结点（NODE）：表中元素的存储单元。由数据域和指针域组成。数据域存放元素数据，指针域存放指向下一结点位置的指针。结点形式为：

datanext数据域指针域链表（Link）：由结点组成的表。头指针（head）：指向链表中第1个结点的指针。

头结点：为方便操作，在头指针和第1个结点之 间设置的结点。首元结点

第一个结点（a1）。head头指针a1首元结点

ai...第i个结点头结点举例由食品组成的单链表（biscuit,butter,cheese,eggs,grapes,jam)

不带头结点。grapesbiscuitbuttercheesejameggs^head

头指针单链表的物理存储

存储地址数据域（data）指针域（next）grapes60biscuit61cheese13eggs1jamNULLbutter121111213606111头指针

head（biscuit,butter,cheese,eggs,grapes,jam)二、C++语言实现Template<classT>

structnode{Tdata;node*next;};Template<classT>classlinked_list{private:

node<T>*head;public:

linked_list();//建立空链表

int

flag_linked_list();//判断链表状态

{if(head==NULL)return0;return1;}voidprt_linked_list();//从头指针开始输出

voidins_linked_list(T);//插入到链表头

Tdel_linked_list();//删除链头}空表和非空表表示形式在头结点上得到统一空表的形式

:head->next=NULL

head^头结点head头结点非空表的形式:head->Next=Address头节点与无头节点三、单链表的操作

1.指针的基本操作

2.链表的动态生成3.单链表的查找4.单链表的的插入insert5.单链表的删除delete1.指针的基本操作设指针变量p、q的定义为：

NODE*p，*q；对链表的操作实际上是对指针的操作。例如，要删除结点ai，首先要使指针p指向ai，即：a1......headaian^p指针p是存储单元的地址，地址内的内容可以通过V(p)得到，指向下个元素的指针用next(p)得到

指针的基本操作列表p=（NODE*）malloc（sizeof（NODE））

申请一个结点空间，并将地址送入p中。free（p）释放p指针所指结点的空间p=q指针p指向指针q所指的结点p=q->next指针p指向指针q所指结点的后件p=p->next指针p向后移动一个结点p->next=q将指针q所指结点改接为指针p所指结点 的后件p->next=NULL将指针p所指结点与后件结点断开

指针操作的举例p=q->nextp指向q所指结点的后件操作前状态aiai-1ai-1qpaiai-1ai+1qp操作后状态2、链表的动态生成链表是一种动态存储结构。因此，建立链表的过程是动态生成的过程。按链表结点建立的顺序、方向不同，分为两种方法：从前往后的动态生成法 将元素插入链表的末尾从后往前的动态生成法 总是将元素插入到链表的第一个位置从后往前1)使p指向新生成的结点，2)p->d=x，p->next=head3)修改头指针head=p

head

...

pai-1aianai-1template<classT>voidlinked_llist<T>::ins_linked_list(Tx){node<T>*p;p=newnode<T>;p->d=x;p->next=head;head=p;return;}从前往后算法操作步骤：

1)使p指向新生成的结点，p->d=x2)若head=NULL(第1个结点)，head=p3)否则循环到最后一个节点，s->next=p4)头指针不变...head

^ai-1a2a1p2s34

ai1template<classT>voidlinked_llist<T>::ins_linked_list1(Tx){node<T>*p;p=newnode<T>;p->d=x;p->next=NULLs=head;q=s->next;while(q!=NULL){q=q->next;s=s->next;}s->next=p;return;}4.单链表的查找算法查找第i个元素，返回指向它的指针算法操作步骤:step1初始化，指针P指向头指针，

计数器置0；step2P非空且计数器小于i循环；step3每循环一次，P后移一个位置，

计数器加1；step4循环结束，返回指向ai

的指针P。

NODE*get(NODE*head,intｉ）(无头结点)｛NODE*p;

intcounter=0;//计数器

p=head;//p指向第1个结点

while((p!=NULL)&&(counter<i)){p=p->next;counter++;}//查找

if((p!=NULL)&&(counter==i))returnp;//找到

elsereturnNULL;//没找到

}template<classT>ListNode<T>*List<T>::Find(Tvalue){//在链表中从头搜索其数据值为value的结点

p=head->next;

//当前指针

p

指示第一个结点

while(p!=NULL)if(p->d==value)break;elsep=head->next;returnp;}5.单链表插入算法在第i个位置插入算法操作步骤:step1找到ai-1的位置，使指针p指向ai-1step2申请并生成新结点sstep3使s插入到ai-1和ai之间

s->next=p->nextp->next=ss->data=x（3）（2）pxai-1ais（1）

insert(NODE*head,inti,intx){NODE*p,*s;if(i==1)p=head;elsep=get(head,i-1);if(p==NULL){printf(“插入位置错\n”);exit(0);}else{s=(NODE*)malloc(sizeof(NODE));s->data=x; s->next=p->next;p->next=s;}}

/*令P指向Ai-1*//*若i=1，P指向头指针*//*P为空，说明找不到i位置*//*P定位成功*//*P定位操作*/5.单链表插入算法在x之前插入b算法操作步骤:step1找到x的位置，使指针p指向x前一结点step2申请并生成新结点sstep3使s插入s->next=p->nextp->next=ss->data=x（3）（2）pbxs（1）template<classT>voidlinked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;p=newnode<T>;p->d=b;if(head==NULL){head=p;p->next=NULL;return;}if(head->d==x){p->next=head;head=p;return;}

q=head;

while((q->next!=NULL)&&((q->next)->d)!=x))q=q->next;p->next=q->next;q->next=p;return;}

6.单链表删除算法删除第i个元素的算法操作步骤:step1找到ai-1的位置，使指针p指向ai-1；step2使指针t指向p所指结点的后继；step3使t所指结点ai

脱链；step4释放t。ai-1aiai+1t=p->nextp->next=t->nextfree(t)p1t23

delete(NODE*head,inti){NODE*p,*t;if(i==1)p=head;elsep=get(head,i-1);if(p==NULL){printf(“i<1或i>表长+1,无此结点\n”);exit(0);}if(p->next==NULL){printf(“i=表长+1,无此结点\n”);exit(0);}else{t=p->next;p->next=t->next;free(t);}}/*P定位操作*//*P定位成功*/删除元素x算法操作步骤:step1找到x的前一个结点位置，使指针p指向它；step2使指针t指向p所指结点的后件；step3使t所指结点x

脱链；step4释放t。ai-1aiai+1t=p->nextp->next=t->nextfree(t)p1t23template<classT>int

linked_llist<T>::ins_linked_llist(Tx){node<T>*p,*q;

i