数据结构完整版电子课件_第1页
数据结构完整版电子课件_第2页
数据结构完整版电子课件_第3页
数据结构完整版电子课件_第4页
数据结构完整版电子课件_第5页
已阅读5页,还剩496页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

件全

册

课数据结构数据结构项目一共分为二个任务项目一

数据结构导论任务一数据结构入门任务二算法与算法分析数据结构项目二共分为三个任务项目二

线性表任务一 线性表的定义和基本操作任务二 线性表的顺序存储结构

任务三 线性表的链式存储结构一、线性表的定义二、线性表的基本操作任务一 线性表的定义和基本操作一、线性表的定义线性表是由n(n≥0)个类型相同的数据元素a1,a2,…,an组成的有限序列,数据元素之间是一对一的关系,记作L=(a1,

a2,

…,

ai-1,

ai,

ai+1,

…,

an)二、线性表的基本操作①InitList(L):初始化线性表L,即构造一个空的线性表L。②DestroyList(L):线性表L已存在,将表L销毁。③ClearList(L):线性表L已存在,将表L置为空表。④ListEmpty(L):线性表L已存在,如果表L为空则返回TRUE,否则返回FALSE。⑤ListLength(L):线性表L已存在,返回表L的长度,即表中数据元素的个数。⑥GetElem(L,i):线性表L已存在,返回表L中第i(1≤i≤ListLength(个元素的值。⑦Locate(L,e):线性表L已存在,返回表L中元素e所在位置;如果表L中不存在元素e,则返回0。⑧InsertList(L,i,e):线性表L已存在,在表L中第i(1≤i≤ListLengt个位置之前插入新的数据元素e,表L的长度加1。⑨DeleteList(L,i,e):线性表L已存在且非空,删除表L中的第i个数据元素,并用e返回其值,表L的长度减1。⑩PriorElem(L,e):线性表L已存在,若e是表L的数据元素且不是第一个,则返回数据元素e的前驱元素;否则操作失败。ⒶNextElem(L,e):线性表L已存在,若e是表L的数据元素且不是最后一个,则返回数据元素e的后继元素;否则操作失败。任务二 线性表的顺序存储结构线性表的顺序存储是指,在内存中用一组地址连续的存储单元依次存储线性表中的各个数据元素。采用顺序存储结构的线性表称为顺序表。一、顺序表的结构特点二、顺序表的基本操作一、顺序表的结构特点假设线性表中有n个数据元素,每个元素占用k个存储单元,其中第一个数据元素a1的存储地址称为线性表的起始位置或基地址,线性表的顺序存储结构如图2-1所示。相邻两个数据元素的存储地址之间的关系:LOC(ai+1)=LOC(ai)+k第i个数据元素ai的存储地址:LOC(ai)=LOC(a1)+(i-1)×k线性表的顺序存储结构是一种随机存取的存储结构。若已知线性表的起始位置(基地址)和表中每个数据元素所占存储单元的大小k,就可以计算出线性表中任意一个数据元素的存储地址,这种存取元素的方法称为随机存取法顺序表的存储结构通常用一维数组来描述,用C语言实现线性表的顺序存储结构的类型定义如下://线性表的最大长度#define

c

100typedef

struct{ElemType

elem

[MAXSIZE];

//存储线性表中数据元素的数组int

length;

//线性表的当前长度}SeqList;//线性表中数据元素的基地址//线性表的当前长度//当前为线性表分配的存储容量typedef

struct{ElemType

*elem;int

length;int

listsize;}SeqList;也可以这样来定义:定义一个顺序表的方法有两种:方法一:SeqList

L,表示将L定义为SeqList类型的变量;对表中数据元素进行操作应使用L.elem[i]方法二:SeqList*L,表示将L定义为指向SeqList类型的指针。对表中数据元素进行操作应使用L->elem[i]二、顺序表的基本操作初始化顺序表插入数据元素删除数据元素查找数据元素1.初始化顺序表初始化顺序表操作是指构造一个空的顺序表,并为其分配存储空间。其算法描述如下:Status

InitList

(SqList

*L){

//初始化顺序表L

->

elem

=

(ElemType

*)

malloc

(MAXSIZE*sizeof

(ElemType));//分配存储空间if

(!

L

->

elem) return

OVERFLOW;

//存储空间分配失败//当前线性表长度为0//初始化存储容量L

->

length

=

0;L

->

listsize

=

LIST_MAX_SIZE;return

TRUE;

}2.插入数据元素为了在顺序表中第i(1≤i≤n)个位置插入数据元素e,需先将第i个至第n个元素(共n-i+1个)依次向后移动一个位置,再将e插入到第i个位置。若i=n+1,则只需在线性表的末尾

插入e即可。算法描述如下:Status

ListInsert

(SqList

*L,

int

i,

ElemType

e){int

j;if

(i

<

1

||

i

>L

->

length

+

1)//i值不合法,出错处理//当前存储空间满return

FALSE;if

(L

->

length

=

L.listsize)return

OVERFLOWfor(j

=

L->

length

–

1;

j

>=

i

-

1;

j

--)L

->

elem

[j

+1]

=L

->

elem[j];//第i个位置之后的元素依次向后移//将e插入到第i个位置//表长增1L

->elem[i

–1]

=

e;L

->

length

++;return

TRUE;

}假设在顺序表中第i个位置插入一个元素的概率为pi,则在长度为n的线性表中插入一个数据元素时,需要移动其他元素的平均次数为:该算法的时间复杂度为O(n)。3.删除数据元素删除顺序表中第i(1≤i≤n)个数据元素,需将第i+1个至第n个元素(共n-i个)依次向前移动一个位置。顺序表进行删除

操作的前后,其数据元素在存

储空间中的位置变化如图2-3所示。算法描述如下:Status

ListDelete

(SqList

*L,

int

i){//在顺序表L中删除第i个数据元素,其中1≤i≤L->lengthint

j;if(i<1

||

i>L->length) return

FALSE;//i值不合法,出错处理for(j=i;j<L->length;j++)L

->elem[j

-

1]

=L

->

elem[j];//第i个位置之后的元素依次向前移L->length--;

//表长减1return

TRUE;}假设删除顺序表中第i个数据元素的概率为qi,则在长度为n的线性表中删除一个数据元素时,需要移动其他元素的平均次数为该算法的时间复杂度也为O(n)。4.查找数据元素在顺序表中查找值为e的数据元素,并返回该元素在表中的位置。方法:从第一个数据元素开始,依次将表中的元素与e进行比较,若相等,则返回该元素在表中的位置;否则,查找失败。算法描述如下:int

Locate

(SqList

L,

ElemType

e){//在顺序表中查找值为e的数据元素,查找成功,返回该元素的位置;否则返回0for

(i

=

0;

i

<

L.length;

i

++)if

(L.elem[i]

==

e)return

i

+

1;return

0;

}//查找成功,返回序号//查找失败,返回0该算法的时间复杂度为O(n)。【例2-1】一个线性表L中的数据元素按升序排列,编写一个算法,实现在线性表中插入一个数据元素item,使得线性表仍然保持升序排列。算法设计如下:void

Insert

(SqList

L,

ElemType

item){

int

i;int

j;if(item>=L.elem[L.length-1])//item值大于表中最大的数据元素//将item插入到表尾//寻找item的插入位置iL.elem[L.length]

=

item;else{

i

=

0;while

(item

>=

L.elem[i])i

++;ListInsert

(&L,

i,

item);

}L.length

++;

}//将item插入到位置i//表长增1任务三 线性表的链式存储结构一、单链表的结构特点二、单链表的基本操作三、静态链表及其基本操作四、循环链表及其基本操作五、双向链表及其基本操作数据元素的存储结构,称为结点(Node)数据域:存储数据元素本身的数据信息指针域:存储直接后继元素地址的信息一、单链表的结构特点将n个数据元素通过其对应结点的指针域按其逻辑关系链接成一个链表,链表中的每个结点只包含一个指针域,这样的链表称为线性链表或单链表,其一般形式如图2-5所示。head称为头指针,用于指向单链表的第一个结点。

由于单链表的最后一个结

点没有直接后继,所以其

指针域为“空”(NULL),用符号“∧”表示。单链表的存储结构定义:typedef

struct

Node{//结点类型ElemType

data;struct

Node

*next;//数据域//指针域}Node,

*LinkList;通常在单链表的第一个结点之前设立一个结点,称之为头结点。头结点的数据域可以不存储任何数据信息,也可以存储一个线性表中不包括的元素值;头结点的指针域存储第一个结点的地址信息。二、单链表的基本操作建立单链表插入数据元素删除数据元素查找数据元素求单链表的长度1.建立单链表//为头结点分配存储空间//r初值指向头结点LinkList

*Create

(LinkList

*L){//建立一个单链表,将新结点插入表尾Node

*r,*s;ElemType

c;int

i;*L

=

(LinkList)

malloc

(sizeof(Node));r

=

*L;for

(i

=

1;

i

<=

n;

i

++){READ(c);

//获取一个数据元素s=(LinkList)malloc(sizeof(Node));

//生成一个新结点s->data=c;

//将要插入数据元素的值赋给新结点的数据域//链表末尾结点指针域为空//将新结点插入到当前链表的表尾上//r始终指向链表的当前表尾s

->

next

=

NULL;r

->

next

=

s;r

=

s;

}return

L;

}算法描述如下:该算法的时间复杂度为O(n)2.插入数据元素StatusListInsert(LinkList

*L,int

i,ElemType

e)算{法//描在述单如链下表:L中第i个位置插入一个数据元素eNode

*p,

*s;int

j

=

0;p

=

*L;while

(p

!=

NULL

&&

j

<

i

-

1){//找到第i-1个结点p=p->next;j

++;

}if(j!=i-1) return

FALSE;

//未找到插入位置,出错处理s=(LinkList)malloc(sizeof(Node));//生成新结点//将要插入数据元素的值赋给新结点//插入新结点s->data=e;的数据域s

->

next

=

p->

next;p

->

next

=

s;

return

TRUE;

}该算法的时间复杂度为O(n)3.删除数据元素Status

ListDelete(LinkList

*L,int

i,ElemType

*e)算{法//描删述除如单下链:表L中的第i个结点,并用e返回被删除的元素Node

*p,*r;int

j

=

0;p

=

*L;while

(p

->

next

!=

NULL

&&

j

<

i

-1){//找到第i-1个结点p=p->next;j

++;

}if

(j

!=

i

-

1) return

FALSE;

//未找到要删除的结点,出错处理r

=

p

->

next;

//指针r指向要删除的结点p->next=p->next->next;//删除结点r//将删除结点的值保存在e中//释放被删除结点所占的内存空间*e

=

r

->

data;free

(r);return

TRUE;

}该算法的时间复杂度为O(n)4.查找数据元素(1)按序号查找LinkList

GetElem

(LinkList

L,

int

i)查{找//单在链单表链中表的L中第查i个找结第点i个,结算点法,描并述返如回下该:结点的指针Node

*p;int

j

=

0;p=L;

//指针p初值指向头结点while((p->next!=NULL)&&(j<i)){//逐个结点扫描p=p->next;j

++;

}return

p;

}//指向下一个结点//已扫描过的结点数//返回第i个结点算法的时间复杂度为O(n)(2)按值查找查找单链表中值为e的结点,算法描述如下:LinkList

Locate

(LinkList

L,

ElemType

e){//在单链表中查找值为e的结点,并返回该结点的指针Node

*p;p=L->next;

//指针p初值指向表中第1个结点while((p!=NULL)&&(p->data!=e))//从表中第1个结点开始逐个比较p=p->next;return

p;}

//返回值为e的结点5.求单链表的长度int

ListLength

(LinkList

L){//用来保存单链表的长度//指针p初值指向表中第1个结点//用指针p依次指向表中各个结点//返回单链表的长度Node

*p;int

j

=

0;p

=L

->

next;while

(p

!=

NULL){

p

=

p

->

next;j

++;

}return

j;

}//返回单链表的长度三、静态链表及其基本操作初始化静态链表分配结点回收结点1.初始化静态链表开辟一块连续的存储空间,将整个数组空间初始化为一个空闲静态链表算法描述如下:SeqLinkList

*InitList

(SeqLinkList

*S){//初始化静态链表int

i;for

(i

=

0;

i

<

MAXSIZE

-

1;

++

i)S[i].cur

=

i

+

1;//设置各个结点的游标域//最后一个结点的cur值为0S[MAXSIZE

-

1].cur

=

0;return

S;}2.分配结点当进行插入操作时,从空闲链表上取得第一个结点作为待插入的新结点算法描述如下:int

Malloc

(SLinkList

*S){//从空闲链表中分配结点,返回该结点下标i=S[0].cur;

//取第一个空闲结点的下标if

(S[0].cur)

S[0].cur

=

S[i].cur;//空闲链表非空,则其头指针赋新return

i;

//返回取出的结点下标}3.回收结点当进行删除操作时,将从链表中删除的结点链接到空闲链表中作为备用//将下标为k的结点作为空闲链表的头结点S[k].cur

=

S[0].cur;S[0].cur

=

k;}算法描述如下:void

Free

(SLinkList

*S,

int

k){//将下标为k的空闲结点回收到空闲链表中四、循环链表及其基本操作将表中最后一个结点的指针域指向头结点,从而形成一个首尾相接的链表,称为循环链表。所有结点被链接到一个环上,从循环链表中任一结点出发均可找到表中其他结点。尾指针(rear)a1=*(rear->next->next)an=*rear查找首尾结点的时间复杂度都为O(1)五、双向链表及其基本操作插入数据元素删除数据元素1.插入数据元素在双向链表中第i个位置插入一个数据元素e,此时需要同时修改两个方向上的指针,如图2-17所示。Status

DListInsert

(DLinkList

*L,int

i,

ElemType

e){//在双向循环链表L中第i个位置插入一个数据元素eDNode

*s,*pif(!(p=GetElem(L,i))) return

FALSE;//插入位置不合法s=(DLinkList)malloc(sizeof(DNode)//生成新结点if

(!

s) return

FALSE;s->data=e;

//将e赋给新结点的数据域s->prior=p->prior;

//新结点的前驱指向p结点的前驱//p结点前驱的后继指向新结点//新结点的后继指向p结点//p结点的前驱指向新结点p

->

prior

->

next

=

s;s

->

next

=

p;p

->

prior

=

s;return

TRUE;

}算法描述如下:2.删除数据元素删除双向链表中的第i个结点,其指针变化情况如图2-18所示。算法描述如下:Status

DListDelete

(DLinkList

*L,int

i,

ElemType

*e){//删除双向链表L中的第i个结点DNode

*pif(!(p=GetElem(L,i))) return

FALSE;//i值不合法*e=p->data;

//将要删除结点的值赋给ep->prior->next=p->next;//要删除结点前驱的后继指向其后继

p->next->prior=p->prior;//要删除结点后继的前驱指向其前驱//释放p结点free

(p);return

TRUE;}数据结构项目三共分为二个任务项目三

栈和队列任务一 栈的定义、存储结构和基本操作任务二 队列的定义、存储结构和基本操作任务一 栈的定义、存储结构和基本操作一、栈的定义及其基本操作二、栈的顺序存储结构三、栈的链式存储结构四、栈在递归中的应用一、栈的定义及其基本操作栈的定义栈的基本操作1.栈的定义栈是一种只允许在表的一端进行插入和删除操作的线性表。后进先出原则2.栈的基本操作①InitStack(S):将栈S初始化为一个空栈。②DestroyStack(S):栈S已存在,将栈S销毁。③ClearStack(S):栈S已存在,将栈S置为空栈。④StackEmpty(S):栈S已存在,如果栈S为空栈则返回TRUE,否则返回FALSE。⑤Push(S,e):栈S已存在,在栈S的栈顶位置插入一个数据元素e。⑥Pop(S,e):栈S非空,删除栈S的栈顶元素,并用e返回其值。⑦GetTop(S,e):栈S非空,用e返回栈S的栈顶元素。二、栈的顺序存储结构顺序栈的结构特点顺序栈的基本操作多栈共享空间1.顺序栈的结构特点顺序栈是指采用顺序存储结构的栈,即在内存中用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设置一个指针top指示栈顶元素的当前位置。//定义栈的最大容量类型定义如下:#define

MAXSIZE

100typedef

struct{ElemType

elem[MAXSIZE];

//存放栈中元素的一维数组空间int

top;

//栈顶指针变量}SeqStack;top用于指示某一时刻栈顶元素的位置elem[0]用于存放栈中第一个元素2.顺序栈的基本操作初始化判断栈是否为空进栈出栈取栈顶元素(1)初始化void

InitStack

(SeqStack*S){//构造一个空栈SS->top=0;}int

StackEmpty

(SeqStack

S){//判断S是否为空栈,为空时返回TRUE,否则返回FALSEreturn(S.top==0?TRUE:FALSE);}(2)判断栈是否为空int

Push

(SeqStack

*S,

ElemType

e){//将数据元素e压入栈顶if(S->top==MAXSIZE) return

FALSE;//栈已满,进栈失败顶S->elem[S->top]=e;

//将e插入栈S->top++;

//修改栈顶指针return

TRUE;}(3)进栈(4)出栈int

Pop

(SeqStack

*S,

ElemType

*e){//若栈不空,将栈顶元素弹出,并用e返回其值if

(S

->

top

==

0) return

FALSE;else{//修改栈顶指针//保存栈顶元素S

->

top

--;*e

=

S

->

elem[S

->

top];return

TRUE;

}}(5)取栈顶元素int

GetTop

(SeqStack

S,

ElemType

*e){//保存栈顶元素//若栈不空,则用e返回栈顶元素if

(S.top

==

0) return

FALSE;*e

=S.elem[S.top

-

1];return

TRUE;}3.多栈共享空间当元素进栈时,两个栈都是从两端向中间伸展。通过两个栈顶指针(top1和top2)的动态变化,使其存储空间相互补充。栈满的条件是:top1=top2+1栈空的条件是:top1=0或top2=M-1两栈共享空间的数据结构定义://两栈共享的存储空间大小//两栈共享的一维数组空间//两栈的栈顶指针#define

M

100typedef

struct{ElemType

Stack[M];int

top[2];}DSeqStack;两栈共享空间的一些基本操作:初始化进栈出栈(1)初始化void

InitStack

(DSeqStack

*S){//初始化两个空栈S->top[0]=0;S

->

top[1]=

M-1;}//参数错误default

:return

FALSE;

}return

TRUE;

}(2)进栈int

Push

(DSeqStack

*S,

ElemType

e,

int

i){//将数据元素e压入第i个栈的栈顶if(S->top[0]==S->top[1]+1) return

FALSE;//栈已满,进栈失败switch

(i){case

0:

//将e压入第1个栈

S->Stack[S->top[0]]=e;S

->top[0]++;break;case

1:

//将e压入第2个栈

S->Stack[S->top[1]]=e;S

->

top[1]

--;break;(3)出栈

int

Pop(DSeqStack

*S,ElemType

*e,int

i){//从第i个栈中弹出栈顶元素,并用e返回其值switch(i){case

0

:if

(S

->

top[0]

==

0)//从第1个栈弹出return

FALSE;*e

=

S

->Stack[S

->top[0]

-

1];S

->

top[0]

--;break;case

1

:if

(S

->

top[1]

==

M

-

1)//从第2个栈弹出return

FALSE;*e

=

S

->Stack[S

->top[1]

+

1];S

->top[1]++;break;//参数错误default

:return

FALSE;

}return

TRUE;

}三、栈的链式存储结构链栈的结构特点链栈的基本操作1.链栈的结构特点链栈是指利用一个单链表结构来实现的栈,即栈中的每一个数据元素用一个结点来表示,同时设置一个指针top指示栈顶元素的当前位置。链栈的类型定义如下://数据域//指针域//栈顶指针typedef

struct

SNode{ElemType

data;struct

SNode

*next;}SNode;typedef

struct{struct

SNode

*top;}LinkStack;2.链栈的基本操作初始化进栈出栈(1)初始化void

InitStack

(LinkStack

*S){//将栈S初始化为空栈S->top=NULL;//栈顶指针为空}(2)进栈int

Push

(LinkStack

*S,

ElemType

e){//将数据元素e压入链栈LinkStack

*temp;temp=(LinkStack)malloc(sizeof(struct

Node));//生成新结点//分配空间失败//为新结点数据域赋值//将新结点插入栈顶//修改栈顶指针if

(temp

==

NULL) return

FALSE;temp

->

data

=

e;temp

->

next

=

S

->

top;S

->

top

=

temp;return

TRUE;}(3)出栈int

Pop

(LinkStack

*S,

ElemType*e){//将栈顶元素弹出,并用e返回其值LinkStack

*temp;return

FALSE;//栈为空,出栈失败//修改栈顶指针//保存栈顶元素的值//释放出栈结点if

(S

->

top

==

NULL)temp

=

S

->

top;S

->

top

=

S

->

top->

next;*e

=

temp

->

data;free

(temp);return

TRUE;}指一个函数在定义自身的同时又直接或间接地调用自身四、栈在递归中的应用二阶Fibonacci数列C语言函数描述如下:int

fib(int

n){if

(n==

0) return

0;else

if

(n==

1) return

1;else returnfib

(n-

1)+

fib(n

-

2);A1:A2:A3:A4:

}Fib(3)递归栈的存储空间变化情况:任务二 队列的定义、存储结构和基本操作一、队列的定义及其基本操作二、队列的顺序存储结构三、队列的链式存储结构一、队列的定义及其基本操作队列的定义队列的基本操作队列是另一种操作受限的线性表,它只允许在表的一端进行插入操作,而在另一端进行删除操作。1.队列的定义2.队列的基本操作①InitQueue(Q):将队列Q初始化为一个空队列。②DestroyQueue(Q):队列Q已存在,将队列Q销毁。③ClearQueue(Q):队列Q已存在,将队列Q置为空队列。④QueueEmpty(Q):队列Q已存在,如果Q为空队列则返回TRUE,否则返回FALSE。⑤EnQueue(Q,e):队列Q已存在,插入一个数据元素e为新的队尾元素。⑥DeQueue(Q,e):队列Q非空,删除Q的队头元素,并用e返回其值。⑦GetHead(Q,e):队列Q非空,用e返回Q的队头元素。二、队列的顺序存储结构顺序队列循环队列的结构特点循环队列的基本操作1.顺序队列//队列的最大长度#define

MAXSIZE

100typedef

struct{ElemType

elem[MAXSIZE];//存放队列中元素的一维数组空间//头指针//尾指针int

front;int

rear;}SeqQueue;在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素,同时设置两个指针front和rear分别指示队头元素和队尾元素的位置。顺序队列的类型定义如下:2.循环队列的结构特点将队列的存储空间看成一个环状的空间,即将队列的首、尾的位置连接起来形成的结构称为循环队列。一般规定:少用一个元素的存储空间,当队列尾指针的下一个位置是队列头指针时,则停止进队操作,此时队列已满。循环队列满的条件是:(rear+1)mod

MAXSIZE=front循环队列空的条件是:front=rear3.循环队列的基本操作初始化判断队列是否为空进队出队取队头元素(1)初始化voidInitQueue

(SeqQueue

*Q){//将Q初始化为一个空的循环队列Q->front=Q->rear=0;}(2)判断队列是否为空int

QueueEmpty

(SeqQueue

Q){

//判断Q是否为空队列,为空时返回TRUE,否则返回FALSEif

(Q.front

==

Q.rear) return

TRUE;else return

FALSE;}(3)进队int

EnQueue

(SeqQueue

*Q,

ElemTypee){//将数据元素e插入到队列中if((Q->rear+1)%MAXSIZE==Q->front)//队列已满,插入失败return

FALSE;Q->elem[Q->rear]=e;

//将e插入队尾Q->rear=

(Q->rear+1)%MAXSIZE;//重新设置尾指针return

TRUE;}(4)出队int

DeQueue

(SeqQueue

*Q,

ElemType

*e){

//若队列不空,则删除Q的队头元素,并用e返回其值//队列空,删除失败if

(Q

->

front

==

Q

->

rear)return

FALSE;*e

=

Q

->

elem[Q

->

front];//用e返回队头元素Q->front=(Q->front+1)%MAXSIZE;//重新设置头指针return

TRUE;}(5)取队头元素int

GetFront

(SeqQueueQ,

ElemType

*e){//若队列不空,则用e返回队头元素if(Q.front==Q.rear)//保存队头元素return

FALSE;*e

=

Q.elem[Q.front];return

TRUE;}}三、队列的链式存储结构链队列的结构特点链队列的基本操作1.链队列的结构特点采用链表形式表示的队列称为链队列,队列中每一个元素对应链表中的一个结点,并设置两个分别指示队头和队尾的指针。链队列的类型定义如下://数据域//指针域//队头指针//队尾指针typedef

struct

Node{ElemType

data;struct

Node

*next;}LinkQueueNode;typedef

struct{LinkQueueNode

*front;LinkQueueNode

*rear;}LinkQueue;2.链队列的基本操作初始化进队出队(1)初始化void

InitQueue

(LinkQueue

*Q){//将Q初始化为一个空的链队列Q

->

front

=

(LinkQueueNode

*)

malloc

(sizeof

(LinkQueueNode));//生成头结点if(Q->front==NULL) return

FALSE;//存储空间分配失败//队头指针和队尾指针都指向头结点Q

->

rear

=

Q

->

front;Q

->

front

->

next

=

NULL;return

TRUE;}int

EnQueue

(LinkQueue

*Q,

ElemType

e){//将数据元素e插入到队列中LinkQueueNode

*NewNode;NewNode

=

(LinkQueueNode

*)

malloc

(sizeof

(LinkQueueNode));//生成新结点if(NewNode==NULL) return

FALSE;//存储空间分配失败//为新结点的数据域赋值//将新结点插入队尾//使队尾指针指向新结点NewNode

->

data

=

e;NewNode

->

next

=

NULL;Q

->

rear

->next

=

NewNode;Q

->

rear

=

NewNode;

return

TRUE;

}(2)进队int

DeQueue

(LinkQueue

*Q,

ElemType

*e){//若队列不空,则删除Q的队头元素,并用e返回其值LinkQueueNode

*p;//队列空,删除失败if

(Q

->

front

==

Q

->

rear)return

FALSE;p

=

Q

->

front

->

next;*e

=

p

->

data;Q

->

front

->

next

=

p

->

next;//从队头取出第一个结点//用e返回结点p的值//结点p出队if(Q->rear==p)//如果队列中只有一个结点p,则p出队后成为空队列Q->rear=Q->front;free(p);

//释放存储空间return

TRUE;}(3)出队数据结构项目三共分为二个任务项目三

栈和队列任务一 栈的定义、存储结构和基本操作任务二 队列的定义、存储结构和基本操作任务一 栈的定义、存储结构和基本操作一、栈的定义及其基本操作二、栈的顺序存储结构三、栈的链式存储结构四、栈在递归中的应用一、栈的定义及其基本操作栈的定义栈的基本操作1.栈的定义栈是一种只允许在表的一端进行插入和删除操作的线性表。后进先出原则2.栈的基本操作①InitStack(S):将栈S初始化为一个空栈。②DestroyStack(S):栈S已存在,将栈S销毁。③ClearStack(S):栈S已存在,将栈S置为空栈。④StackEmpty(S):栈S已存在,如果栈S为空栈则返回TRUE,否则返回FALSE。⑤Push(S,e):栈S已存在,在栈S的栈顶位置插入一个数据元素e。⑥Pop(S,e):栈S非空,删除栈S的栈顶元素,并用e返回其值。⑦GetTop(S,e):栈S非空,用e返回栈S的栈顶元素。二、栈的顺序存储结构顺序栈的结构特点顺序栈的基本操作多栈共享空间1.顺序栈的结构特点顺序栈是指采用顺序存储结构的栈,即在内存中用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时设置一个指针top指示栈顶元素的当前位置。//定义栈的最大容量类型定义如下:#define

MAXSIZE

100typedef

struct{ElemType

elem[MAXSIZE];

//存放栈中元素的一维数组空间int

top;

//栈顶指针变量}SeqStack;top用于指示某一时刻栈顶元素的位置elem[0]用于存放栈中第一个元素2.顺序栈的基本操作初始化判断栈是否为空进栈出栈取栈顶元素(1)初始化void

InitStack

(SeqStack*S){//构造一个空栈SS->top=0;}int

StackEmpty

(SeqStack

S){//判断S是否为空栈,为空时返回TRUE,否则返回FALSEreturn(S.top==0?TRUE:FALSE);}(2)判断栈是否为空int

Push

(SeqStack

*S,

ElemType

e){//将数据元素e压入栈顶if(S->top==MAXSIZE) return

FALSE;//栈已满,进栈失败顶S->elem[S->top]=e;

//将e插入栈S->top++;

//修改栈顶指针return

TRUE;}(3)进栈(4)出栈int

Pop

(SeqStack

*S,

ElemType

*e){//若栈不空,将栈顶元素弹出,并用e返回其值if

(S

->

top

==

0) return

FALSE;else{//修改栈顶指针//保存栈顶元素S

->

top

--;*e

=

S

->

elem[S

->

top];return

TRUE;

}}(5)取栈顶元素int

GetTop

(SeqStack

S,

ElemType

*e){//保存栈顶元素//若栈不空,则用e返回栈顶元素if

(S.top

==

0) return

FALSE;*e

=S.elem[S.top

-

1];return

TRUE;}3.多栈共享空间当元素进栈时,两个栈都是从两端向中间伸展。通过两个栈顶指针(top1和top2)的动态变化,使其存储空间相互补充。栈满的条件是:top1=top2+1栈空的条件是:top1=0或top2=M-1两栈共享空间的数据结构定义://两栈共享的存储空间大小//两栈共享的一维数组空间//两栈的栈顶指针#define

M

100typedef

struct{ElemType

Stack[M];int

top[2];}DSeqStack;两栈共享空间的一些基本操作:初始化进栈出栈(1)初始化void

InitStack

(DSeqStack

*S){//初始化两个空栈S->top[0]=0;S

->

top[1]=

M-1;}//参数错误default

:return

FALSE;

}return

TRUE;

}(2)进栈int

Push

(DSeqStack

*S,

ElemType

e,

int

i){//将数据元素e压入第i个栈的栈顶if(S->top[0]==S->top[1]+1) return

FALSE;//栈已满,进栈失败switch

(i){case

0:

//将e压入第1个栈

S->Stack[S->top[0]]=e;S

->top[0]++;break;case

1:

//将e压入第2个栈

S->Stack[S->top[1]]=e;S

->

top[1]

--;break;(3)出栈

int

Pop(DSeqStack

*S,ElemType

*e,int

i){//从第i个栈中弹出栈顶元素,并用e返回其值switch(i){case

0

:if

(S

->

top[0]

==

0)//从第1个栈弹出return

FALSE;*e

=

S

->Stack[S

->top[0]

-

1];S

->

top[0]

--;break;case

1

:if

(S

->

top[1]

==

M

-

1)//从第2个栈弹出return

FALSE;*e

=

S

->Stack[S

->top[1]

+

1];S

->top[1]++;break;//参数错误default

:return

FALSE;

}return

TRUE;

}三、栈的链式存储结构链栈的结构特点链栈的基本操作1.链栈的结构特点链栈是指利用一个单链表结构来实现的栈,即栈中的每一个数据元素用一个结点来表示,同时设置一个指针top指示栈顶元素的当前位置。链栈的类型定义如下://数据域//指针域//栈顶指针typedef

struct

SNode{ElemType

data;struct

SNode

*next;}SNode;typedef

struct{struct

SNode

*top;}LinkStack;2.链栈的基本操作初始化进栈出栈(1)初始化void

InitStack

(LinkStack

*S){//将栈S初始化为空栈S->top=NULL;//栈顶指针为空}(2)进栈int

Push

(LinkStack

*S,

ElemType

e){//将数据元素e压入链栈LinkStack

*temp;temp=(LinkStack)malloc(sizeof(struct

Node));//生成新结点//分配空间失败//为新结点数据域赋值//将新结点插入栈顶//修改栈顶指针if

(temp

==

NULL) return

FALSE;temp

->

data

=

e;temp

->

next

=

S

->

top;S

->

top

=

temp;return

TRUE;}(3)出栈int

Pop

(LinkStack

*S,

ElemType*e){//将栈顶元素弹出,并用e返回其值LinkStack

*temp;return

FALSE;//栈为空,出栈失败//修改栈顶指针//保存栈顶元素的值//释放出栈结点if

(S

->

top

==

NULL)temp

=

S

->

top;S

->

top

=

S

->

top->

next;*e

=

temp

->

data;free

(temp);return

TRUE;}指一个函数在定义自身的同时又直接或间接地调用自身四、栈在递归中的应用二阶Fibonacci数列C语言函数描述如下:int

fib(int

n){if

(n==

0) return

0;else

if

(n==

1) return

1;else returnfib

(n-

1)+

fib(n

-

2);A1:A2:A3:A4:

}Fib(3)递归栈的存储空间变化情况:任务二 队列的定义、存储结构和基本操作一、队列的定义及其基本操作二、队列的顺序存储结构三、队列的链式存储结构一、队列的定义及其基本操作队列的定义队列的基本操作队列是另一种操作受限的线性表,它只允许在表的一端进行插入操作,而在另一端进行删除操作。1.队列的定义2.队列的基本操作①InitQueue(Q):将队列Q初始化为一个空队列。②DestroyQueue(Q):队列Q已存在,将队列Q销毁。③ClearQueue(Q):队列Q已存在,将队列Q置为空队列。④QueueEmpty(Q):队列Q已存在,如果Q为空队列则返回TRUE,否则返回FALSE。⑤EnQueue(Q,e):队列Q已存在,插入一个数据元素e为新的队尾元素。⑥DeQueue(Q,e):队列Q非空,删除Q的队头元素,并用e返回其值。⑦GetHead(Q,e):队列Q非空,用e返回Q的队头元素。二、队列的顺序存储结构顺序队列循环队列的结构特点循环队列的基本操作1.顺序队列//队列的最大长度#define

MAXSIZE

100typedef

struct{ElemType

elem[MAXSIZE];//存放队列中元素的一维数组空间//头指针//尾指针int

front;int

rear;}SeqQueue;在内存中用一组地址连续的存储单元依次存放从队头到队尾的数据元素,同时设置两个指针front和rear分别指示队头元素和队尾元素的位置。顺序队列的类型定义如下:2.循环队列的结构特点将队列的存储空间看成一个环状的空间,即将队列的首、尾的位置连接起来形成的结构称为循环队列。一般规定:少用一个元素的存储空间,当队列尾指针的下一个位置是队列头指针时,则停止进队操作,此时队列已满。循环队列满的条件是:(rear+1)mod

MAXSIZE=front循环队列空的条件是:front=rear3.循环队列的基本操作初始化判断队列是否为空进队出队取队头元素(1)初始化voidInitQueue

(SeqQueue

*Q){//将Q初始化为一个空的循环队列Q->front=Q->rear=0;}(2)判断队列是否为空int

QueueEmpty

(SeqQueue

Q){

//判断Q是否为空队列,为空时返回TRUE,否则返回FALSEif

(Q.front

==

Q.rear) return

TRUE;else return

FALSE;}(3)进队int

EnQueue

(SeqQueue

*Q,

ElemTypee){//将数据元素e插入到队列中if((Q->rear+1)%MAXSIZE==Q->front)//队列已满,插入失败return

FALSE;Q->elem[Q->rear]=e;

//将e插入队尾Q->rear=

(Q->rear+1)%MAXSIZE;//重新设置尾指针return

TRUE;}(4)出队int

DeQueue

(SeqQueue

*Q,

ElemType

*e){

//若队列不空,则删除Q的队头元素,并用e返回其值//队列空,删除失败if

(Q

->

front

==

Q

->

rear)return

FALSE;*e

=

Q

->

elem[Q

->

front];//用e返回队头元素Q->front=(Q->front+1)%MAXSIZE;//重新设置头指针return

TRUE;}(5)取队头元素int

GetFront

(SeqQueueQ,

ElemType

*e){//若队列不空,则用e返回队头元素if(Q.front==Q.rear)//保存队头元素return

FALSE;*e

=

Q.elem[Q.front];return

TRUE;}}三、队列的链式存储结构链队列的结构特点链队列的基本操作1.链队列的结构特点采用链表形式表示的队列称为链队列,队列中每一个元素对应链表中的一个结点,并设置两个分别指示队头和队尾的指针。链队列的类型定义如下://数据域//指针域//队头指针//队尾指针typedef

struct

Node{ElemType

data;struct

Node

*next;}LinkQueueNode;typedef

struct{LinkQueueNode

*front;LinkQueueNode

*rear;}LinkQueue;2.链队列的基本操作初始化进队出队(1)初始化void

InitQueue

(LinkQueue

*Q){//将Q初始化为一个空的链队列Q

->

front

=

(LinkQueueNode

*)

malloc

(sizeof

(LinkQueueNode));//生成头结点if(Q->front==NULL) return

FALSE;//存储空间分配失败//队头指针和队尾指针都指向头结点Q

->

rear

=

Q

->

front;Q

->

front

->

next

=

NULL;return

TRUE;}int

EnQueue

(LinkQueue

*Q,

ElemType

e){//将数据元素e插入到队列中LinkQueueNode

*NewNode;NewNode

=

(LinkQueueNode

*)

malloc

(sizeof

(LinkQueueNode));//生成新结点if(NewNode==NULL) return

FALSE;//存储空间分配失败//为新结点的数据域赋值//将新结点插入队尾//使队尾指针指向新结点NewNode

->

data

=

e;NewNode

->

next

=

NULL;Q

->

rear

->next

=

NewNode;Q

->

rear

=

NewNode;

return

TRUE;

}(2)进队int

DeQueue

(LinkQueue

*Q,

ElemType

*e){//若队列不空,则删除Q的队头元素,并用e返回其值LinkQueueNode

*p;//队列空,删除失败if

(Q

->

front

==

Q

->

rear)return

FALSE;p

=

Q

->

front

->

next;*e

=

p

->

data;Q

->

front

->

next

=

p

->

next;//从队头取出第一个结点//用e返回结点p的值//结点p出队if(Q->rear==p)//如果队列中只有一个结点p,则p出队后成为空队列Q->rear=Q->front;free(p);

//释放存储空间return

TRUE;}(3)出队数据结构项目四共分为四个任务项目四

串和数组任务一 串的定义、存储结构和基本操作任务二 数组的定义和存储结构

任务三 矩阵的压缩存储任务四 广义表的定义和存储结构任务一 串的定义、存储结构和基本操作一、串的定义及其基本操作二、定长顺序存储结构三、堆存储结构四、块链存储结构一、串的定义及其基本操作串的定义串的基本操作1.串的定义串(string)是零个或多个字符组成的有限序列,通常记作:S="a1a2a3…an"(n≥0)串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串称为该子串的主串。子串在主串中第一次出现时第一个字符的位置称为子串的位置。当两个串的长度相等,并且各个对应位置的字符都相等时,称两个串是相等的。2.串的基本操作①StrAssign(S,string):串赋值。②生St成rE一mp个ty值(S为S为)s:tr判r判i断ng串的是串否S,为s空tr。ing是字符串常量。③若St串rCSo为mp空ar串e

(,(,S则,T返):回串TR比UE较;。否则返回FALSE。④已S知tr串CoSoS和pp和y串(T,,S若):S>串T复,制则。返回1;若S=T,则返回0;若S<T,则返⑤回已回已S-知-知tr1串1串L。eSeS,这nn这,g将里将里th的串的串(S比S比)的:较内求是容串按复的字制长典到度顺串。序T进中。的。例如,比较"行

that"和"this",

"th"相同,由于"a"<"i",故"that"<"this";又如"in"和"into","in"⑥已S知tr串ClSlSe,e,a返r(回S)串:S串的清长空度。,即串中元素的个数。相同,但"into"长,故"in"<"into"。已知串S,将串S清为空串。StrLength(S)-pos+1,用Sub返回串S的第pos个字符起长度为len的子串。⑦Concat(T,S1,S2):串连接。⑧Su已bS知tr串inSg1(和Su串u串bS,2S

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论