数据结构与算法第三章简单数据结构new课件

1、第三章 简单数据结构8/22/20221第3章 简单数据结构3.1 顺序表3.2 链表3.3 栈3.4 队列3.5 *广义表8/22/20222线性结构的特点 存在唯一的被称为“第一个”的或“起始”的数据元素； 存在唯一的被称为“最后一个”的或“终端”的数据元素； 除第一个元素之外，集合中的每一个数据元素均有且仅有一个前趋； 除最后一个元素之外，集合中的每一个数据元素均有且仅有一个后继。8/22/202233.1 顺序表3.1.1 线性表的基本概念线性表是n（n0)个数据元素的有限序列，记为：L=（a1,a2,ai,an）林鹏黄龙张艺谋张三丰（A,B,C,D,E,Z)字母表登记表8/22/20

2、224线性表的基本运算 初始化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)；8/22/202253.1.2 线性表的顺序存储顺序表顺序

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

4、8985566775588英语数学last=5maxlen8/22/202273.1.3 顺序表上的基本运算（1）顺序表元素插入操作的算法：A1A2AiAn-1An在第i个位置插入需移动次数为n-i+1次，每个位置插入的概率为1/(n+1)平均移动次数： (n-i+1)/(n+1)=n/2 (其中i=1.n+1) 算法的时间复杂度 T(n)=O(n) maxsize8/22/202283.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*/8/22/202293.1.3 顺序表上的基本运算（2）顺序表元素删除操作的算法：A1A2A3AiAn删除第i个元素需要移动n-i次平均移动次数： (n-i)/n (其中i=0.n-1) 算法的时间复杂度T(n)=O(n) 8/22/2022103.1.3 顺序表上的基本运算（2）顺序表元素删除操作的算法： void d

6、elete(sequenlist *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; 8/22/202211举例删除顺序表中的重复元素算法思路：从顺序表中第一个元素起，逐个检查它后面是否有值相同的其它元素，若有便删除之；直到表中所有元素都已无重复元素为止。为此，算法中需设两重循环，外层控制清除的趟数，内层控制每趟的检查范围。8/22/202212举例删除顺序表中的重复元素void Purge(sequenlist *L) in

7、t 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)8/22/2022133.2 链表顺序表存储的缺点1）预先分配连续的空间2）不能根据需要动态分配3）插入删除等操作需要移动大量数据HELLO8/22/2022143.2 链表单链表 循环链表 双向链表 8/22/2022153.2.1单链表单链表的组成及定

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

9、83.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(LinkList); P-dat

10、a=ch; P-next=NULL; r-next=P; r=r-next; ch=getchar(); return head; HELLO头结点head思考：头插法建表怎么建？rprp8/22/2022193.2.2单链表上的基本运算（2）求表长int LengthLinkList(LinkList *L) LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长*/ HELLO头结点head8/22/202220（3）单链表元素的查找/查找元素为X的结点LinkList *LocateLinkLi

11、st(LinkList *L，elemtyPe x;) LinkList *P; P=L-next; while(P!=NULL)&(P-data!=x) P=P-next; return P; /*返回找到的结点位置或NULL*/ /*LocateLinkList*/8/22/202221（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

12、; /*GetLinkList*/8/22/2022223.2.2单链表上的基本运算（4）单链表元素插入操作linklist_insert(linknode *L,int i,elemtp x)HELLOLwPq=(LinkList *)malloc(sizeof(LinkList);q-data=x;q-next=p-next; / 修改指针 p-next=q;q8/22/2022233.2.2单链表上的基本运算（3）单链表元素插入操作int linklist_insert(linknode *L,int i,elemtp x) linknode *p, *q;int j=0;p=L; wh

13、ile (p-next!=NULL) & (j+next; if (j=i-1) q=(LinkList *)malloc(sizeof(LinkList); / 建立新结点 q-data=x; q-next=p-next; / 修改指针 p-next=q; return(1); else return(0); / 插入位置无效 8/22/2022243.2.2单链表上的基本运算（5）单链表元素删除操作linklist_del(linknode *L,int i)HELLOLPq=p-next;p-next=q-next; free(p); 8/22/202225删除单链表L中的第i个结点算法

14、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 S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 该算法的时间复杂度为O(n)8/22/2022263.2.3循环链表和双向链表1.循环链表HHELLOH非空循环链表思考：如何判断是最后一个元素？如何判断是空表？空表head-next=head；8/22/202

15、2273.2.3循环链表和双向链表2.双向链表前驱数据后继双链表结点格式Lhel格式定义：typedef struct dbnode elemtp data; struct dbnode *prior,*next;dblinknode;h空表L8/22/202228双向链表插入结点将S结点插入P之前Lhel S-prior=P-prior; S-next=P; P-prior-next=s; P-prior=S; pAS8/22/202229双向链表2.删除结点思考：双向如何添加删除双链表结点Lhelp-piror-next=p-next;p-next-piror=p-piror;free(p

16、);p8/22/2022303.2.4两一元多项式相加的算法 已经两多项式A,B A=X -6X3 + 3X4 -6X5B=1+5X3+6X5+9x6求A+B;系数指数next格式定义：typedef struct node double coef; / 表示系数 int exp; / 表示指数 struct node *next;polynode; 8/22/202231多项式相加算法的思路不产生新结点而利用原有结点空间，设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点，依次比较两指针所指结点的指数项。若指数相等系数相加，和不为零修改*p的系数项并删除*q，和为零删除*p和*q

17、；若指数不等，p-expexp时*p为和多项式中的一项，p-expq-exp时把*q插在*p之前（*q为和多项式中的一项）；所有操作之后要相应移动指针。直到其中一个链空，把另一个链剩下的结点插在*p之后。 A11633465B105365968/22/2022323.2.4两一元多项式相加的算法A11633465B105365968/22/2022333.3栈（stack)3.3.1栈的概念及运算栈:限制仅在一端对元素插入或删除操作的线性表 a5a4a3a2a1栈底栈顶入栈出栈是先进后出，后进现出的一种结构8/22/2022343.3.1栈的概念及运算栈的基本运算：(1) 置空栈 setnul

18、l(S) 建立空栈S；(2)判栈空 empty(S)(3)入栈 push(S,x) 将元素x压入栈S中（插入），使之成为新的栈顶元素，成立的条件是栈未满； (4)出栈 pop(S) 弹出栈顶元素（返回栈顶并删除），成立的条件是栈非空；(5)取栈顶元素 gettop(S) 返回非空栈的栈顶元素的值；8/22/2022353.3.2 顺序栈及运算实现顺序栈:利用顺序存储结构实现的栈，用一数组实现数据类型：typedef struct elemtp datamaxlen; int top; / 栈顶指针 sqstack;a5a4a3a2a1top8/22/2022363.3.2 顺序栈及运算实现运算

19、实现（1）顺序栈的初始化：void setnull(sqstack *S) S-top = -1;说明栈为空Top=-18/22/2022373.3.2 顺序栈及运算实现运算实现（2）进栈算法：int push(sqstack *S,elemtp x) if (S-top=maxlen-1) return(0); / 栈已满或溢出 S-top+ S-dataS-top = x; return(1);topa5a4a3a2a1a68/22/2022383.3.2 顺序栈及运算实现运算实现（3）顺序栈的元素出栈：elemtp pop (sqstack *S) if (S-top=-1)return

20、 NULL; / 栈已空 else S-top-; return (S-dataS-top); Topa5a4a3a2a18/22/2022393.3.3 链栈及运算实现只能在链头进行操作的单链表链栈的数据类型：typedef struct node elemtp data; struct node *next;linkstack;A5A4A3A2A1TOP8/22/2022403.3.3 链栈及运算实现（1）链栈的初始化：void init_linkstack(linkstacknode *t) t=NULL; 8/22/2022413.3.3 链栈及运算实现（2）链栈的元素入栈：void

21、push (linkstack *top,elemtp x) linkstack *p p=new linkstack; / 建立新的结点 p-data=x; p-next=top; t=top; / 修改栈顶指针A5A4A3A2A1TOP8/22/2022423.3.3 链栈及运算实现（3）链栈的元素出栈：elemtp pop (linkstack *t) linkstack *p; elemtp x; if (t=NULL) return NULL; / 链栈已空 x=t-data; p=t; t=t-next; / 修改栈顶指针 delete p; / free(p); 释放原栈顶结点

22、return(x);A5A4A3A2A1TOP8/22/2022433.3.4 栈的应用举例递归算法的实现递归算法的执行过程实际上应用了栈例：求阶层函数F(N)=1 N=0F(N-1)*N N=18/22/2022443.3.4 栈的应用举例递归算法的实现例：求阶层函数int fact(int n) if(n=0) return 1; else return n*fact(n-1); F(N-1)F(N-2)F(N-3)F(2)F(1)8/22/2022453.3.4 栈的应用举例递归算法的实现例：求阶层函数,改写成用栈实现int fact(int n) sqstack s; int rs=1

23、; if (n=0)return 1; while(n0)/入栈 push (&s,n);n-while(stack.top!=-1) /出栈 rs=pop (&s)*rs; return rs;NN-1N-2218/22/2022463.4队列3.4.1 队列的概念及其运算队列：先进先出的线性表，仅限于表的一端进行元素的插入和表的另一端进行元素的删除操作。 a1a2a3a4a5队头队尾出队（删除）入队插入8/22/2022473.4.1 队列的概念及其运算队列的基本运算：初始化队列 init_queue(q)，建立空队列q；入队列 in_queue(q,x)，元素x在对尾插入队列；出队列 o

24、ut_queue(q)，若q非空队列，取出对头元素，并在队列中删除，对头指针指向下一个元素；判对列空 empty_queue(q)，队列中是否无元素；求队列长度 length_queue(q)，返回队列中的元素个数；取对头元素 getfront_queue(q)，读取对头元素数据；置队列空 clear_queue(q)，删除队列中所有元素，使对长为0。 8/22/2022483.4.2 顺序队列及运算实现如同顺序表，用一维数组存放队列元素数据。a5a4a3a2顺序队列的类型定义如下：#define maxlen maxsizetypedef struct elemtp datamaxlen;

25、int front,rear; / 分别指示队头和队尾元素的下标 sequeue;frontrear8/22/2022493.4.2 顺序队列及运算实现（1）初始化队列：void init_cycque(sequeue &q) q-front=q-rear=-1;frontrear014328/22/2022503.4.2 顺序队列及运算实现（2）入队int in_que(sequeue *q,elemtp x) if (q-rear+1=maxsize) return(0); q-data+q-rear=x; return(1);a5a4a3a2Front=0reara68/22/20225

26、13.4.2 顺序队列及运算实现（3）出队elemtp out_que(sequeue *q) if (q-rear=q-front) /空 return(0);/否则 return q-data+q-front;a5a4Front=1reara6a38/22/2022523.4.2 顺序队列及运算实现队列假溢出思考： q-rear=q-front=maxsize-1时，队列真的为满吗？Maxsize-1frontrear8/22/2022533.4.2 顺序队列及运算实现循环队列 将顺序队列的首尾相连，即：q-datamaxsize-1后紧跟q-data001234567a2a1a3fron

27、trearrear8/22/2022543.4.2 顺序队列及运算实现循环队列 :几种状态的判断01234567a2a1a3a4a5a6a7frontrear队列满01234567frontrear队列空Q.front=Q.rear=k(Q.rear+1) % maxlen=Q.front8/22/2022553.4.2 顺序队列及运算实现（1）初始化循环队列：void init_cycque(cyclicqueue &q) q.front=q.rear=0;01234567frontrear8/22/2022563.4.2 顺序队列及运算实现（2）循环队列的元素入队操作的算法：int in_

28、cycque(cyclicqueue &q,elemtp x) if (q.rear+1) % maxlen=q.front) return(0); / 队满 q.rear=(q.rear+1) % maxlen; dataq.rear=x; return(1);8/22/2022573.4.2 顺序队列及运算实现（3）循环队列的元素出队操作的算法：elemtp out_cycque(cyclicqueue &q) if (q.front=q.rear) return NULL; / 对空 q.front=(q.front+1) % maxlen; return(dataq.front);8/

29、22/2022583.4.3 链队列及运算实现hLLOfrontrear头结点链队列的数据类型定义：typedef struct node elemtp data; struct node *next; linknode ; / 元素结点类型typedef structlinknode *front,*rear;linkqueue; / 队头和队尾指针结构linkqueue Q; / 队列变量当Q.front=Q.rear时，表示队列为空 8/22/2022593.4.3 链队列及运算实现(1)链队列的初始化：void iniqueue(linkqueue *q)q-front=(linkno

30、de *)malloc(sizeof(linknode); q-rear=q-front; /*让尾指针也指向头结点*/ q-front-next=NULL; /*填头结点的next域为NULL*/frontrear头结点8/22/2022603.4.3 链队列及运算实现（2）链队列的入队算法：void addqueue(linkqueue *q,elemtype x) linknode *p; p=(linknode *)malloc(sizeof(linknode); p-data=x; /*填入元素值*/ p-next=NULL; /*指针域填NULL值*/ q-rear-next=p;

31、 /*新结点插入队尾*/ q-rear=p; /*修改队尾指针*/8/22/2022613.4.3 链队列及运算实现（3）链队列的出队算法：elemtype outqueue(linkqueue *q) linknode *p; if(q-rear=q-front) return NULL; /*队列为空时返回NULL*/ else p=q-front; /*p指向头结点*/ q-front=q-front-next; free (p); return q-front-data; 8/22/2022623.3.4队列的应用（1）数据的输入/输出处理中的数据缓冲，如键盘缓冲区、打印缓冲区、文件缓

32、冲区等（2）实时数据采集时的平均值计算，如电子称的数据采集和显示处理（阻尼算法）（3）消息队列（Windows）（4）离散事件模拟8/22/2022633.5广义表3.5.1 广义表的概念广义表 是线性表的一种推广，它的数据元素不仅可以是一个数据元素，还可以是表本身。 通常记做：LS=(d1,d2,d3,dn) 例： LS=(a, (b,c,d) ,e) 或LS=(a,LB,e) LB=(b,c,d)8/22/2022643.5.1 广义表的概念广义表的一些例子：1）A=() A是一个空表，长度为0，深度为12）B=(e) 列表B只有一个单元素e，表长度为1，深度为13）C=(a,(b,c,d

33、) 列表C的长度为2，两个元素分别为单元素a和子表(b,c,d)，列表的深度为24）D=(A,B,C) 列表D的长度为3，三个元素都是列表，即有D=(),(e),(a,(b,c,d)5）E=(a,E) E是一个递归的表，它的长度为2，展开后相当于一个无限的列表E=(a,(a,(a,.)8/22/202265广义表的基本操作（运算）（1）求广义表的长度len(LS)表中元素的个数，不包括子表中的元素个数例：A=(a, (b,c,d) ,d) B=(f,) 8/22/202266广义表的基本操作（运算）（2）求广义表的深度 展开后括号的层次例：A=(a, (b,c,d) ,d) B=(f,A)8/

34、22/202267广义表的基本操作（运算）（3）求表头（4）求表尾 表尾一定是个广义表 如:LB=(a),tail(LB)=() LC=(a,(b,c),tail(LC)=(b,c) l8/22/2022683.5.2 广义表的存储结构及运算实现广义表的数据类型定义：typedef struct node int atom; struct node *next; union elemtp data;/*atom=1时为数据*/ struct node *snext;/*atom=0时为子表*/ elemdata;glist;atomdata/snextnext8/22/2022693.5.2

35、广义表的存储结构及运算实现例：画出如下广义表的存储表示Ls=(),a,(b,c),(d),e)01a1e0001c1b01d8/22/2022703.5.2 广义表的存储结构及运算实现（1）求广义表深度的递归算法：int depth(glist *LS) glist *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;a100Lb10

36、c08/22/202271小结 顺序表:用数组表示元素链表：单链表，循环链表，双向链表；一元多项式的加法栈：顺序栈，链栈；递归调用队列：顺序队列（循环队列），链队列；广义表:存储结构8/22/202272typedef关键词格式typedef 已有类型 新定义类型；例如:typedef int count;count x,y;8/22/202273struct结构体结构体（structure）是一种数据类型，它把互相联系的数据组合成一个整体。例、8/22/202274 一个学生的学号、姓名、性别、年龄、成绩、地址，是互相联系的数据，在C语言中用“结构体（structure）”来定义。struc

37、t studentintnum; /* 学号 */char name20; /* 姓名 */char sex; /* 性别 */int age; /* 年龄 */float score; /* 成绩 */char addr30; /* 地址 */； 8/22/202275一、先定义结构体类型，再定义变量例、struct studentintnum; char name20; char sex; int age; float score; char addr30;； struct student student1, student2; 8/22/202276二、在定义类型的同时定义变量struct studentintnum; char name20;char sex; int age; floatscore; char addr30;student1, student2；8/22/202277三、直接定义变量struct intnum; char name20; char sex; int age; float score; char ad