《数据结构与算法第三章简单数据结构new.ppt》由会员分享，可在线阅读，更多相关《数据结构与算法第三章简单数据结构new.ppt（88页珍藏版）》请在课桌文档上搜索。
1、3/2/2023,1,第三章 简单数据结构,3/2/2023,2,第3章 简单数据结构,3.1 顺序表,3.2 链表,3.3 栈,3.4 队列,3.5*广义表,3/2/2023,3,线性结构的特点,存在唯一的被称为“第一个”的或“起始”的数据元素；存在唯一的被称为“最后一个”的或“终端”的数据元素；除第一个元素之外，集合中的每一个数据元素均有且仅有一个前趋；除最后一个元素之外，集合中的每一个数据元素均有且仅有一个后继。,3/2/2023,4,3.1 顺序表,3.1.1 线性表的基本概念线性表是n（n0)个数据元素的有限序列，记为：L=（a1,a2,ai,an）,登记表,3/2/2023,5,线
2、性表的基本运算,初始化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)；,3/2/2023,6,3.1.2 线性表的顺序存储顺序表,顺序表：用
3、一组地址连续的存储单元依次存储线性表的元素，用数组实现,例：（A,B,C,D,E,Z),线性表的第i个元素的存储地址为Loc(ai)=Loc(a1)+(i-1)*k,3/2/2023,7,顺序表数据类型的定义,/定义每一个结点，根据具体情况变化typedef struct int yinyu;/英语 int shuxue;/数学 elemtype;/定义顺序表#define maxsize 1024typedef struct/顺序表最多容纳maxlen个元素 elemtp datamaxsize;int last;/指示当前表长 sequenlist;,英语,数学,last=5,maxlen
4、,3/2/2023,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,3/2/2023,9,3.1.3 顺序表上的基本运算,（1）顺序表元素插入操作的算法：void insert(sequenlist*L,elemtype x,int i)int j;if(i(L-last+1)printf(“插入位置不正确n”);else if(L-last=MAXSIZE)printf(“
5、表已满，发生上溢n”);else for(j=L-last;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-last=L-last+1;/*insert*/,3/2/2023,10,3.1.3 顺序表上的基本运算,（2）顺序表元素删除操作的算法：,删除第i个元素需要移动n-i次平均移动次数：(n-i)/n(其中i=0.n-1)算法的时间复杂度T(n)=O(n),3/2/2023,11,3.1.3 顺序表上的基本运算,（2）顺序表元素删除操作的算法：void delete(sequenlist*L,int i)int j;if(iL-last)printf(“删除位置不
6、正确n”);else for(j=i+1;jlast;j+)L-dataj-1=L-dataj;L-last=L-last-1;,3/2/2023,12,举例删除顺序表中的重复元素,算法思路：从顺序表中第一个元素起，逐个检查它后面是否有值相同的其它元素，若有便删除之；直到表中所有元素都已无重复元素为止。为此，算法中需设两重循环，外层控制清除的趟数，内层控制每趟的检查范围。,3/2/2023,13,举例删除顺序表中的重复元素,void Purge(sequenlist*L)int i,j,k;i=1;while(ilast)/每个元素都要比较 j=i+1;while(jlast)if(L-dat
7、aj=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),3/2/2023,14,3.2 链表,顺序表存储的缺点1）预先分配连续的空间2）不能根据需要动态分配3）插入删除等操作需要移动大量数据,3/2/2023,15,3.2 链表,单链表 循环链表 双向链表,3/2/2023,16,3.2.1单链表,单链表的组成及定义,结点组成,结点定义：typedef struct node elemtp data;struct node*next;LinkL
8、ist;,L,头指针,3/2/2023,17,3.2.1单链表,头结点，头指针，第一个结点（首元结点）,第一个结点,head,头结点,头指针,3/2/2023,18,3.2.1单链表,动态生成一个结点 LinkList*H;H=(LinkList*)malloc(sizeof(LinkList);对结点中域的访问 H-elemtp和H-next 或(*H).elemtp和(*H).next释放结点占用的空间 free(H),3/2/2023,19,3.2.2单链表上的基本运算,（1）单链表建立：/尾插法建表：输入n个字符建立链表,直到输入为*结束LinkList*CreateLinkList(
9、)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-data=ch;P-next=NULL;r-next=P;r=r-next;ch=getchar();return head;,头结点,head,思考：头插法建表怎么建？,r,p,r,p,3/2
10、/2023,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,3/2/2023,21,（3）单链表元素的查找,/查找元素为X的结点LinkList*LocateLinkList(LinkList*L，elemtyPe x;)LinkList*P;P=L-next;while(P!=NULL)/*返回找到的结点位置或NULL*/*LocateLinkList*/,3/2/2023,2
11、2,（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;/*GetLinkList*/,3/2/2023,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
12、=p-next;/修改指针 p-next=q;,q,3/2/2023,24,3.2.2单链表上的基本运算,（3）单链表元素插入操作int linklist_insert(linknode*L,int i,elemtp x)linknode*p,*q;int j=0;p=L;while(p-next!=NULL)/插入位置无效,3/2/2023,25,3.2.2单链表上的基本运算,（5）单链表元素删除操作linklist_del(linknode*L,int i),L,P,q=p-next;p-next=q-next;free(p);,3/2/2023,26,删除单链表L中的第i个结点算法,Li
13、nkList*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),3/2/2023,27,3.2.3循环链表和双向链表,1.循环链表,H,非空循环链表,思考：如何判断是最后一个元素？如何判断是空表？,空表,head-next=head；,3/2/2023,28,3.2.3循环链
14、表和双向链表,2.双向链表,双链表结点格式,L,格式定义：typedef struct dbnode elemtp data;struct dbnode*prior,*next;dblinknode;,空表,L,3/2/2023,29,双向链表,插入结点将S结点插入P之前,L,S-prior=P-prior;S-next=P;P-prior-next=s;P-prior=S;,p,S,3/2/2023,30,双向链表,2.删除结点思考：双向如何添加删除双链表结点,L,p-piror-next=p-next;p-next-piror=p-piror;free(p);,p,3/2/2023,31,
15、3.2.4两一元多项式相加的算法,已经两多项式A,B A=X-6X3+3X4-6X5B=1+5X3+6X5+9x6求A+B;,格式定义：typedef struct node double coef;/表示系数 int exp;/表示指数 struct node*next;polynode;,3/2/2023,32,多项式相加算法的思路,不产生新结点而利用原有结点空间，设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点，依次比较两指针所指结点的指数项。若指数相等系数相加，和不为零修改*p的系数项并删除*q，和为零删除*p和*q；若指数不等，p-expexp时*p为和多项式中的一项，
16、p-expq-exp时把*q插在*p之前（*q为和多项式中的一项）；所有操作之后要相应移动指针。直到其中一个链空，把另一个链剩下的结点插在*p之后。,3/2/2023,33,3.2.4两一元多项式相加的算法,3/2/2023,34,3.3栈（stack),3.3.1栈的概念及运算栈:限制仅在一端对元素插入或删除操作的线性表,栈底,栈顶,入栈,出栈,是先进后出，后进现出的一种结构,3/2/2023,35,3.3.1栈的概念及运算,栈的基本运算：(1)置空栈 setnull(S)建立空栈S；(2)判栈空 empty(S)(3)入栈 push(S,x)将元素x压入栈S中（插入），使之成为新的栈顶元素
17、，成立的条件是栈未满；(4)出栈 pop(S)弹出栈顶元素（返回栈顶并删除），成立的条件是栈非空；(5)取栈顶元素 gettop(S)返回非空栈的栈顶元素的值；,3/2/2023,36,3.3.2 顺序栈及运算实现,顺序栈:利用顺序存储结构实现的栈，用一数组实现数据类型：typedef struct elemtp datamaxlen;int top;/栈顶指针 sqstack;,top,3/2/2023,37,3.3.2 顺序栈及运算实现,运算实现（1）顺序栈的初始化：void setnull(sqstack*S)S-top=-1;说明栈为空,Top=-1,3/2/2023,38,3.3.2
18、 顺序栈及运算实现,运算实现（2）进栈算法：int push(sqstack*S,elemtp x)if(S-top=maxlen-1)return(0);/栈已满或溢出 S-top+S-dataS-top=x;return(1);,a6,3/2/2023,39,3.3.2 顺序栈及运算实现,运算实现（3）顺序栈的元素出栈：elemtp pop(sqstack*S)if(S-top=-1)return NULL;/栈已空 else S-top-;return(S-dataS-top);,3/2/2023,40,3.3.3 链栈及运算实现,只能在链头进行操作的单链表链栈的数据类型：typedef
19、 struct node elemtp data;struct node*next;linkstack;,TOP,3/2/2023,41,3.3.3 链栈及运算实现,（1）链栈的初始化：void init_linkstack(linkstacknode*t)t=NULL;,3/2/2023,42,3.3.3 链栈及运算实现,（2）链栈的元素入栈：void push(linkstack*top,elemtp x)linkstack*p p=new linkstack;/建立新的结点 p-data=x;p-next=top;t=top;/修改栈顶指针,3/2/2023,43,3.3.3 链栈及运算
20、实现,（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);释放原栈顶结点 return(x);,3/2/2023,44,3.3.4 栈的应用举例,递归算法的实现递归算法的执行过程实际上应用了栈例：求阶层函数,F(N)=,1 N=0,F(N-1)*N N=1,3/2/2023,45,3.3.4 栈的应用举例,递归算法的实现例：求阶层函数,int fact(int n)if(n=0)retu
21、rn 1;else return n*fact(n-1);,F(N-1),F(N-2),F(N-3),F(2),F(1),3/2/2023,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,3/2/2023,47,3.4队列,3.4.1 队列的概念及其运算队列：先进先出的线性表，仅限于表的一端进行元素的插入和表的另一端进行元素的删除操作。,队头,队尾,出队（删除）,入队插入,3/2/2023,48,3.
22、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。,3/2/2023,49,3.4.2 顺序队列及运算实现,如同顺序表，用一维数组
23、存放队列元素数据。,顺序队列的类型定义如下：#define maxlen maxsizetypedef struct elemtp datamaxlen;int front,rear;/分别指示队头和队尾元素的下标 sequeue;,front,rear,3/2/2023,50,3.4.2 顺序队列及运算实现,（1）初始化队列：void init_cycque(sequeue,front,rear,0,1,4,3,2,3/2/2023,51,3.4.2 顺序队列及运算实现,（2）入队int in_que(sequeue*q,elemtp x)if(q-rear+1=maxsize)return
24、(0);q-data+q-rear=x;return(1);,Front=0,rear,a6,3/2/2023,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,3/2/2023,53,3.4.2 顺序队列及运算实现,队列假溢出,思考：q-rear=q-front=maxsize-1时，队列真的为满吗？,front,rear,3/2/2023,54,3.4.2 顺序队列及运算实现,循环队列 将顺
25、序队列的首尾相连，即：q-datamaxsize-1后紧跟q-data0,0,1,2,3,4,5,6,7,a2,a1,a3,front,rear,3/2/2023,55,3.4.2 顺序队列及运算实现,循环队列:几种状态的判断,队列空,Q.front=Q.rear=k,(Q.rear+1)%maxlen=Q.front,3/2/2023,56,3.4.2 顺序队列及运算实现,（1）初始化循环队列：void init_cycque(cyclicqueue,3/2/2023,57,3.4.2 顺序队列及运算实现,（2）循环队列的元素入队操作的算法：int in_cycque(cyclicqueue
26、,3/2/2023,58,3.4.2 顺序队列及运算实现,（3）循环队列的元素出队操作的算法：elemtp out_cycque(cyclicqueue,3/2/2023,59,3.4.3 链队列及运算实现,链队列的数据类型定义：typedef struct node elemtp data;struct node*next;linknode;/元素结点类型typedef structlinknode*front,*rear;linkqueue;/队头和队尾指针结构linkqueue Q;/队列变量,当Q.front=Q.rear时，表示队列为空,3/2/2023,60,3.4.3 链队列及运
27、算实现,(1)链队列的初始化：void iniqueue(linkqueue*q)q-front=(linknode*)malloc(sizeof(linknode);q-rear=q-front;/*让尾指针也指向头结点*/q-front-next=NULL;/*填头结点的next域为NULL*/,front,rear,头结点,3/2/2023,61,3.4.3 链队列及运算实现,（2）链队列的入队算法：void addqueue(linkqueue*q,elemtype x)linknode*p;p=(linknode*)malloc(sizeof(linknode);p-data=x;/
28、*填入元素值*/p-next=NULL;/*指针域填NULL值*/q-rear-next=p;/*新结点插入队尾*/q-rear=p;/*修改队尾指针*/,3/2/2023,62,3.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;,3/2/2023,63,3.3.4队列的应用
29、,（1）数据的输入/输出处理中的数据缓冲，如键盘缓冲区、打印缓冲区、文件缓冲区等（2）实时数据采集时的平均值计算，如电子称的数据采集和显示处理（阻尼算法）（3）消息队列（Windows）（4）离散事件模拟,3/2/2023,64,3.5广义表,3.5.1 广义表的概念广义表 是线性表的一种推广，它的数据元素不仅可以是一个数据元素，还可以是表本身。通常记做：LS=(d1,d2,d3,dn)例：LS=(a,(b,c,d),e)或LS=(a,LB,e)LB=(b,c,d),3/2/2023,65,3.5.1 广义表的概念,广义表的一些例子：1）A=()A是一个空表，长度为0，深度为12）B=(e)列
30、表B只有一个单元素e，表长度为1，深度为13）C=(a,(b,c,d)列表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,.),3/2/2023,66,广义表的基本操作（运算）,（1）求广义表的长度len(LS)表中元素的个数，不包括子表中的元素个数例：A=(a,(b,c,d),d)B=(f,),3/2/2023,67,广义表的基本操作（运算）,（2）求广义表的深度 展开后括
31、号的层次例：A=(a,(b,c,d),d)B=(f,A),3/2/2023,68,广义表的基本操作（运算）,（3）求表头（4）求表尾 表尾一定是个广义表 如:LB=(a),tail(LB)=()LC=(a,(b,c),tail(LC)=(b,c)l,3/2/2023,69,3.5.2 广义表的存储结构及运算实现,广义表的数据类型定义：typedef struct node int atom;struct node*next;union elemtp data;/*atom=1时为数据*/struct node*snext;/*atom=0时为子表*/elemdata;glist;,atom,d
32、ata/snext,next,3/2/2023,70,3.5.2 广义表的存储结构及运算实现,例：画出如下广义表的存储表示Ls=(),a,(b,c),(d),e),3/2/2023,71,3.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;,3
33、/2/2023,72,小结,顺序表:用数组表示元素链表：单链表，循环链表，双向链表；一元多项式的加法栈：顺序栈，链栈；递归调用队列：顺序队列（循环队列），链队列；广义表:存储结构,3/2/2023,73,typedef关键词,格式typedef 已有类型 新定义类型；例如:typedef int count;count x,y;,3/2/2023,74,struct结构体,结构体（structure）是一种数据类型，它把互相联系的数据组合成一个整体。例、,3/2/2023,75,一个学生的学号、姓名、性别、年龄、成绩、地址，是互相联系的数据，在C语言中用“结构体（structure）”来定义。
34、struct studentintnum;/*学号*/char name20;/*姓名*/char sex;/*性别*/int age;/*年龄*/float score;/*成绩*/char addr30;/*地址*/；,3/2/2023,76,一、先定义结构体类型，再定义变量例、struct studentintnum;char name20;char sex;int age;float score;char addr30;；struct student student1,student2;,3/2/2023,77,二、在定义类型的同时定义变量,struct studentintnum;c
35、har name20;char sex;int age;floatscore;char addr30;student1,student2；,3/2/2023,78,三、直接定义变量,struct intnum;char name20;char sex;int age;float score;char addr30;student1,student2；,3/2/2023,79,四、成员是另一个结构体变量,struct date int month;int day;int year;；struct studentintnum;char name20;char sex;int age;struct
36、date birthday;char addr30;student1,student2；,3/2/2023,80,结构体变量的引用,引用结构体成员的方式：结构体变量名.成员名例:student1.age=20;printf(%d,%s,%c,%d,%f,%s,student1.num,student1.name,student1.sex,student1.age,student1.score,sutdent1.addr);scanf(%d,3/2/2023,81,结构体数组,一、结构体数组的定义struct studentint num;char name20;char sex;int age
37、;float score;char addr30;struct student stu3;,3/2/2023,82,指针,一、指针变量的定义指针变量定义的一般形式：类型标识符*标识符例、int i,j;i=3;j=6;int*pointer_1;二、指针变量的赋值：例pointer_1=/相当于i=100,3/2/2023,83,也可以在定义指针变量的同时指定其初值，如：int a;int*p=,3/2/2023,84,二、指针变量的两个运算符,有两个运算符可以引用指针变量：（1）（2）*：指针运算符。用于访问指针变量所指向的变量。*和&是互逆运算,例；i=3;直接访问 ptr=间接访问等同于
38、i=15,3/2/2023,85,指针作为函数参数,void swap(int x,int y)int temp;temp=x;x=y;y=temp;,void swap(int*x,int*y)int temp;temp=*x;*x=*y;*y=temp;,3/2/2023,86,struct studentlong int nnum;char name20;char sex;floatscore;struct student stu_1;struct student*p;p=,结构体指针,3/2/2023,87,结构体指针，通过指向运算符引用结构体中的成员。例、p-nump-namep-sexp-score因此结构体成员的引用方式有以下三种：结构体变量.成员名(*p).成员名 p-成员名,3/2/2023,88,函数指针,
