数据结构与算法 第三章 简单数据结构new.ppt

1、7/9/2020,1,第三章 简单数据结构,7/9/2020,2,第3章 简单数据结构,3.1 顺序表,3.2 链表,3.3 栈,3.4 队列,3.5 *广义表,7/9/2020,3,线性结构的特点, 存在唯一的被称为“第一个”的或“起始”的数据元素； 存在唯一的被称为“最后一个”的或“终端”的数据元素； 除第一个元素之外，集合中的每一个数据元素均有且仅有一个前趋； 除最后一个元素之外，集合中的每一个数据元素均有且仅有一个后继。,7/9/2020,4,3.1 顺序表,3.1.1 线性表的基本概念 线性表是n（n0)个数据元素的有限序列，记为： L=（a1,a2,ai,an）,登记表,7/9/2

2、020,5,线性表的基本运算, 初始化setnull(L)，建立一个空的线性表L； 求表长length(L)，函数返回L中的元素个数； 取第i个元素get(L,i)，其中1ilength(L)，否则返回NULL； 求前趋prior(L,x)，返回元素x的前趋； 求后继next(L,x)，返回元素x的后继 定位locate(L,x)，返回元素x在L中的位置，若x不存在，返回0或NULL； 插入元素x到第i个元素之前 insert(L,x,i)，其中1ilength(L)+1，否则插入失败； 删除第i个元素delete(L,i)，其中1ilength(L)；,7/9/2020,6,3.1.2 线性

3、表的顺序存储顺序表,顺序表：用一组地址连续的存储单元依次存储线性表的元素，用数组实现,例：（A,B,C,D,E,Z),线性表的第i个元素的存储地址为 Loc(ai)=Loc(a1)+(i-1)*k,7/9/2020,7,顺序表数据类型的定义,/定义每一个结点，根据具体情况变化 typedef struct int yinyu; /英语 int shuxue ;/数学 elemtype; /定义顺序表 #define maxsize 1024 typedef struct /顺序表最多容纳maxlen个元素 elemtp datamaxsize; int last; / 指示当前表长 seque

4、nlist;,英语,数学,last=5,maxlen,7/9/2020,8,3.1.3 顺序表上的基本运算,（1）顺序表元素插入操作的算法：,在第i个位置插入需移动次数为n-i+1次，每个位置插入的概率为1/(n+1) 平均移动次数： (n-i+1)/(n+1)=n/2 (其中i=1.n+1) 算法的时间复杂度 T(n)=O(n),maxsize,7/9/2020,9,3.1.3 顺序表上的基本运算,（1）顺序表元素插入操作的算法： void insert(sequenlist *L,elemtype x,int i) int j; if(i(L-last+1) printf(“插入位置不正确

5、n”); else if(L-last=MAXSIZE) printf(“表已满，发生上溢n”); else for(j=L-last;j=i;j-) L-dataj+1=L-dataj; L-datai=x; L-last=L-last+1; /*insert*/,7/9/2020,10,3.1.3 顺序表上的基本运算,（2）顺序表元素删除操作的算法：,删除第i个元素需要移动n-i次 平均移动次数： (n-i)/n (其中i=0.n-1) 算法的时间复杂度T(n)=O(n),7/9/2020,11,3.1.3 顺序表上的基本运算,（2）顺序表元素删除操作的算法： void delete(se

6、quenlist *L, int i) int j; if(iL-last) printf(“删除位置不正确n”); else for(j=i+1;jlast;j+) L-dataj-1=L-dataj; L-last=L-last-1; ,7/9/2020,12,举例删除顺序表中的重复元素,算法思路：从顺序表中第一个元素起，逐个检查它后面是否有值相同的其它元素，若有便删除之；直到表中所有元素都已无重复元素为止。为此，算法中需设两重循环，外层控制清除的趟数，内层控制每趟的检查范围。,7/9/2020,13,举例删除顺序表中的重复元素,void Purge(sequenlist *L) int

7、i,j,k; i=1; while(ilast)/每个元素都要比较 j=i+1; while(jlast) if(L-dataj=L-datai)/相等则删除 for(k=j+1;klast;k+) L-datak-1=L-datak; L-last=L-last-1; else j+; i+; /*Purge*/,delete(L, j),7/9/2020,14,3.2 链表,顺序表存储的缺点 1）预先分配连续的空间 2）不能根据需要动态分配 3）插入删除等操作需要移动大量数据,7/9/2020,15,3.2 链表,单链表 循环链表 双向链表,7/9/2020,16,3.2.1单链表,单链表

8、的组成及定义,结点组成,结点定义： typedef struct node elemtp data; struct node *next; LinkList;,L,头指针,7/9/2020,17,3.2.1单链表,头结点，头指针，第一个结点（首元结点）,第一个结点,head,头结点,头指针,7/9/2020,18,3.2.1单链表,动态生成一个结点 LinkList *H; H=(LinkList *) malloc(sizeof(LinkList); 对结点中域的访问 H-elemtp和H-next 或 (*H).elemtp和(*H).next 释放结点占用的空间 free(H),7/9/

9、2020,19,3.2.2单链表上的基本运算,（1）单链表建立： / 尾插法建表 ：输入n个字符建立链表,直到输入为*结束 LinkList *CreateLinkList() char ch; LinkList *head;/*head为头结点指针*/ LinkList *r,*P; head=(LinkList *)malloc(sizeof(LinkList); head-next=NULL; r=head; /*尾指针初始化*/ ch=getchar(); while(ch!=*) /*“*”为输入数据结束符号*/ P=(LinkList *)malloc(sizeof(LinkLis

10、t); P-data=ch; P-next=NULL; r-next=P; r=r-next; ch=getchar(); return head; ,头结点,head,思考：头插法建表怎么建？,r,p,r,p,7/9/2020,20,3.2.2单链表上的基本运算,（2）求表长 int LengthLinkList(LinkList *L) LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长*/ ,头结点,head,7/9/2020,21,（3）单链表元素的查找,/查找元素为X的结点 LinkLi

11、st *LocateLinkList(LinkList *L，elemtyPe x;) LinkList *P; P=L-next; while(P!=NULL) /*返回找到的结点位置或NULL*/ /*LocateLinkList*/,7/9/2020,22,（3）单链表元素的查找,/查找第i个结点 LinkList *GetLinkList(LinkList *L,int i) LinkList *P; int j=0; P=L; while(jnext!=NULL) P=P-next; j+; if(j=i) return P; else return NULL; /*GetLinkL

12、ist*/,7/9/2020,23,3.2.2单链表上的基本运算,（4）单链表元素插入操作linklist_insert(linknode *L,int i,elemtp x),L,P,q=(LinkList *)malloc(sizeof(LinkList); q-data=x;q-next=p-next; / 修改指针 p-next=q;,q,7/9/2020,24,3.2.2单链表上的基本运算,（3）单链表元素插入操作 int linklist_insert(linknode *L,int i,elemtp x) linknode *p, *q;int j=0;p=L; while (p

13、-next!=NULL) / 插入位置无效 ,7/9/2020,25,3.2.2单链表上的基本运算,（5）单链表元素删除操作linklist_del(linknode *L,int i),L,P,q=p-next; p-next=q-next; free(p);,7/9/2020,26,删除单链表L中的第i个结点算法,LinkList *deleteLinkList(LinkList *L,int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第i-1个结点*/ if(P=NULL) Printf(“第i-1个元素不存在，参数i 有错n”); else

14、 S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 该算法的时间复杂度为O(n),7/9/2020,27,3.2.3循环链表和双向链表,1.循环链表,H,非空循环链表,思考：如何判断是最后一个元素？如何判断是空表？,空表,head-next=head；,7/9/2020,28,3.2.3循环链表和双向链表,2.双向链表,双链表结点格式,L,格式定义： typedef struct dbnode elemtp data; struct dbnode *prior,*next; dblinknode;,空表,L,7/9/2020,29,双向链

15、表,插入结点 将S结点插入P之前,L, S-prior=P-prior; S-next=P; P-prior-next=s; P-prior=S;,p,S,7/9/2020,30,双向链表,2.删除结点 思考：双向如何添加删除双链表结点,L,p-piror-next=p-next; p-next-piror=p-piror; free(p);,p,7/9/2020,31,3.2.4两一元多项式相加的算法,已经两多项式A,B A=X -6X3 + 3X4 -6X5 B=1+5X3+6X5+9x6 求A+B;,格式定义： typedef struct node double coef; / 表示系

16、数 int exp; / 表示指数 struct node *next; polynode;,7/9/2020,32,多项式相加算法的思路,不产生新结点而利用原有结点空间，设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点，依次比较两指针所指结点的指数项。 若指数相等系数相加，和不为零修改*p的系数项并删除*q，和为零删除*p和*q； 若指数不等，p-expexp时*p为和多项式中的一项，p-expq-exp时把*q插在*p之前（*q为和多项式中的一项）； 所有操作之后要相应移动指针。直到其中一个链空，把另一个链剩下的结点插在*p之后。,7/9/2020,33,3.2.4两一元多项

17、式相加的算法,7/9/2020,34,3.3栈（stack),3.3.1栈的概念及运算 栈:限制仅在一端对元素插入或删除操作的线性表,栈底,栈顶,入栈,出栈,是先进后出，后进现出的一种结构,7/9/2020,35,3.3.1栈的概念及运算,栈的基本运算： (1) 置空栈 setnull(S) 建立空栈S； (2)判栈空 empty(S) (3)入栈 push(S,x) 将元素x压入栈S中（插入），使之成为新的栈顶元素，成立的条件是栈未满； (4)出栈 pop(S) 弹出栈顶元素（返回栈顶并删除），成立的条件是栈非空； (5)取栈顶元素 gettop(S) 返回非空栈的栈顶元素的值；,7/9/2

18、020,36,3.3.2 顺序栈及运算实现,顺序栈:利用顺序存储结构实现的栈，用一数组实现 数据类型： typedef struct elemtp datamaxlen; int top; / 栈顶指针 sqstack;,top,7/9/2020,37,3.3.2 顺序栈及运算实现,运算实现 （1）顺序栈的初始化： void setnull(sqstack *S) S-top = -1; 说明栈为空,Top=-1,7/9/2020,38,3.3.2 顺序栈及运算实现,运算实现 （2）进栈算法： int push(sqstack *S,elemtp x) if (S-top=maxlen-1)

19、return(0); / 栈已满或溢出 S-top+ S-dataS-top = x; return(1); ,a6,7/9/2020,39,3.3.2 顺序栈及运算实现,运算实现 （3）顺序栈的元素出栈： elemtp pop (sqstack *S) if (S-top=-1) return NULL; / 栈已空 else S-top-; return (S-dataS-top); ,7/9/2020,40,3.3.3 链栈及运算实现,只能在链头进行操作的单链表 链栈的数据类型： typedef struct node elemtp data; struct node *next; li

20、nkstack;,TOP,7/9/2020,41,3.3.3 链栈及运算实现,（1）链栈的初始化： void init_linkstack(linkstacknode *t) t=NULL; ,7/9/2020,42,3.3.3 链栈及运算实现,（2）链栈的元素入栈： void push (linkstack *top,elemtp x) linkstack *p p=new linkstack; / 建立新的结点 p-data=x; p-next=top; t=top; / 修改栈顶指针 ,7/9/2020,43,3.3.3 链栈及运算实现,（3）链栈的元素出栈： elemtp pop (l

21、inkstack *t) linkstack *p; elemtp x; if (t=NULL) return NULL; / 链栈已空 x=t-data; p=t; t=t-next; / 修改栈顶指针 delete p; / free(p); 释放原栈顶结点 return(x); ,7/9/2020,44,3.3.4 栈的应用举例,递归算法的实现 递归算法的执行过程实际上应用了栈 例：求阶层函数,F(N)=,1 N=0,F(N-1)*N N=1,7/9/2020,45,3.3.4 栈的应用举例,递归算法的实现 例：求阶层函数,int fact(int n) if(n=0) return 1

22、; else return n*fact(n-1); ,F(N-1),F(N-2),F(N-3),F(2),F(1),7/9/2020,46,3.3.4 栈的应用举例,递归算法的实现 例：求阶层函数,改写成用栈实现,int fact(int n) sqstack s; int rs=1; if (n=0)return 1; while(n0)/入栈 push ( ,N,N-1,N-2,2,1,7/9/2020,47,3.4队列,3.4.1 队列的概念及其运算 队列：先进先出的线性表，仅限于表的一端进行元素的插入和表的另一端进行元素的删除操作。,队头,队尾,出队（删除）,入队插入,7/9/202

23、0,48,3.4.1 队列的概念及其运算,队列的基本运算： 初始化队列 init_queue(q)，建立空队列q； 入队列 in_queue(q,x)，元素x在对尾插入队列； 出队列 out_queue(q)，若q非空队列，取出对头元素，并在队列中删除，对头指针指向下一个元素； 判对列空 empty_queue(q)，队列中是否无元素； 求队列长度 length_queue(q)，返回队列中的元素个数； 取对头元素 getfront_queue(q)，读取对头元素数据； 置队列空 clear_queue(q)，删除队列中所有元素，使对长为0。,7/9/2020,49,3.4.2 顺序队列及运算

24、实现,如同顺序表，用一维数组存放队列元素数据。,顺序队列的类型定义如下： #define maxlen maxsize typedef struct elemtp datamaxlen; int front,rear; / 分别指示队头和队尾元素的下标 sequeue;,front,rear,7/9/2020,50,3.4.2 顺序队列及运算实现,（1）初始化队列： void init_cycque(sequeue ,front,rear,0,1,4,3,2,7/9/2020,51,3.4.2 顺序队列及运算实现,（2）入队 int in_que(sequeue *q,elemtp x) if

25、 (q-rear+1=maxsize) return(0); q-data+q-rear=x; return(1); ,Front=0,rear,a6,7/9/2020,52,3.4.2 顺序队列及运算实现,（3）出队 elemtp out_que(sequeue *q) if (q-rear=q-front) /空 return(0); /否则 return q-data+q-front; ,Front=1,rear,a6,a3,7/9/2020,53,3.4.2 顺序队列及运算实现,队列假溢出,思考： q-rear=q-front=maxsize-1时，队列真的为满吗？,front,rea

26、r,7/9/2020,54,3.4.2 顺序队列及运算实现,循环队列 将顺序队列的首尾相连， 即：q-datamaxsize-1 后紧跟q-data0,0,1,2,3,4,5,6,7,a2,a1,a3,front,rear,7/9/2020,55,3.4.2 顺序队列及运算实现,循环队列 :几种状态的判断,队列空,Q.front=Q.rear=k,(Q.rear+1) % maxlen=Q.front,7/9/2020,56,3.4.2 顺序队列及运算实现,（1）初始化循环队列： void init_cycque(cyclicqueue ,7/9/2020,57,3.4.2 顺序队列及运算实现

27、,（2）循环队列的元素入队操作的算法： int in_cycque(cyclicqueue ,7/9/2020,58,3.4.2 顺序队列及运算实现,（3）循环队列的元素出队操作的算法： elemtp out_cycque(cyclicqueue ,7/9/2020,59,3.4.3 链队列及运算实现,链队列的数据类型定义： typedef struct node elemtp data; struct node *next; linknode ; / 元素结点类型 typedef struct linknode *front,*rear; linkqueue; / 队头和队尾指针结构 lin

28、kqueue Q; / 队列变量,当Q.front=Q.rear时，表示队列为空,7/9/2020,60,3.4.3 链队列及运算实现,(1)链队列的初始化： void iniqueue(linkqueue *q) q-front=(linknode *)malloc(sizeof(linknode); q-rear=q-front; /*让尾指针也指向头结点*/ q-front-next=NULL; /*填头结点的next域为NULL*/ ,front,rear,头结点,7/9/2020,61,3.4.3 链队列及运算实现,（2）链队列的入队算法： void addqueue(linkque

29、ue *q,elemtype x) linknode *p; p=(linknode *)malloc(sizeof(linknode); p-data=x; /*填入元素值*/ p-next=NULL; /*指针域填NULL值*/ q-rear-next=p; /*新结点插入队尾*/ q-rear=p; /*修改队尾指针*/ ,7/9/2020,62,3.4.3 链队列及运算实现,（3）链队列的出队算法： elemtype outqueue(linkqueue *q) linknode *p; if(q-rear=q-front) return NULL; /*队列为空时返回NULL*/ e

30、lse p=q-front; /*p指向头结点*/ q-front=q-front-next; free (p); return q-front-data; ,7/9/2020,63,3.3.4队列的应用,（1）数据的输入/输出处理中的数据缓冲，如键盘缓冲区、打印缓冲区、文件缓冲区等 （2）实时数据采集时的平均值计算，如电子称的数据采集和显示处理（阻尼算法） （3）消息队列（Windows） （4）离散事件模拟,7/9/2020,64,3.5广义表,3.5.1 广义表的概念 广义表 是线性表的一种推广，它的数据元素不仅可以是一个数据元素，还可以是表本身。 通常记做：LS=(d1,d2,d3,d

31、n) 例： LS=(a, (b,c,d) ,e) 或LS=(a,LB,e) LB=(b,c,d),7/9/2020,65,3.5.1 广义表的概念,广义表的一些例子： 1）A=() A是一个空表，长度为0，深度为1 2）B=(e) 列表B只有一个单元素e，表长度为1，深度为1 3）C=(a,(b,c,d) 列表C的长度为2，两个元素分别为单元素a和子表(b,c,d)，列表的深度为2 4）D=(A,B,C) 列表D的长度为3，三个元素都是列表，即有D=(),(e),(a,(b,c,d) 5）E=(a,E) E是一个递归的表，它的长度为2，展开后相当于一个无限的列表E=(a,(a,(a,.),7/

32、9/2020,66,广义表的基本操作（运算）,（1）求广义表的长度len(LS) 表中元素的个数，不包括子表中的元素个数 例：A=(a, (b,c,d) ,d) B=(f,),7/9/2020,67,广义表的基本操作（运算）,（2）求广义表的深度 展开后括号的层次 例：A=(a, (b,c,d) ,d) B=(f,A),7/9/2020,68,广义表的基本操作（运算）,（3）求表头 （4）求表尾 表尾一定是个广义表 如:LB=(a),tail(LB)=() LC=(a,(b,c),tail(LC)=(b,c) l,7/9/2020,69,3.5.2 广义表的存储结构及运算实现,广义表的数据类型

33、定义： typedef struct node int atom; struct node *next; union elemtp data;/*atom=1时为数据*/ struct node *snext;/*atom=0时为子表*/ elemdata; glist;,atom,data/snext,next,7/9/2020,70,3.5.2 广义表的存储结构及运算实现,例：画出如下广义表的存储表示 Ls=(),a,(b,c),(d),e),7/9/2020,71,3.5.2 广义表的存储结构及运算实现,（1）求广义表深度的递归算法： int depth(glist *LS) glist

34、 *p; int dep，max； max=0； /*max为当前最大深度*/ p=LS-next ; while(p!=NULL) /* 判断所指结点是否为子表*/ if(p-atom=0) dep=depth(p-snext)； if(depmax) max=dep ; p=p-next； return max+1; ,7/9/2020,72,小结,顺序表:用数组表示元素 链表：单链表，循环链表，双向链表；一元多项式的加法 栈：顺序栈，链栈；递归调用 队列：顺序队列（循环队列），链队列； 广义表:存储结构,7/9/2020,73,typedef关键词,格式 typedef 已有类型 新定义

35、类型； 例如: typedef int count; count x,y;,7/9/2020,74,struct结构体,结构体（structure）是一种数据类型， 它把互相联系的数据组合成一个整体。例、,7/9/2020,75,一个学生的学号、姓名、性别、年龄、成绩、地址，是互相联系的数据，在C语言中用“结构体（structure）”来定义。 struct studentintnum; /* 学号 */char name20; /* 姓名 */char sex; /* 性别 */int age; /* 年龄 */float score; /* 成绩 */char addr30; /* 地址

36、*/；,7/9/2020,76,一、先定义结构体类型，再定义变量 例、 struct studentintnum; char name20; char sex; int age; float score; char addr30;； struct student student1, student2;,7/9/2020,77,二、在定义类型的同时定义变量,struct studentintnum; char name20;char sex; int age; floatscore; char addr30;student1, student2；,7/9/2020,78,三、直接定义变量,struct intnum; char name20; char se