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

上传人:王** 文档编号:163019 上传时间:2023-03-02 格式:PPT 页数:88 大小:741.50KB
下载 相关 举报
数据结构与算法第三章简单数据结构new.ppt_第1页
第1页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第2页
第2页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第3页
第3页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第4页
第4页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第5页
第5页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第6页
第6页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第7页
第7页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第8页
第8页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第9页
第9页 / 共88页
数据结构与算法第三章简单数据结构new.ppt_第10页
第10页 / 共88页
亲,该文档总共88页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构与算法第三章简单数据结构new.ppt》由会员分享,可在线阅读,更多相关《数据结构与算法第三章简单数据结构new.ppt(88页珍藏版)》请在优知文库上搜索。

1、3/2/20231第三章 简单数据结构3/2/20232第3章 简单数据结构l3.13.1 顺序表顺序表l3.2 3.2 链表链表l3.33.3 栈栈l3.43.4 队列队列l3.53.5 * *广义表广义表3/2/20233线性结构的特点 存在唯一的被称为“第一个”的或“起始”的数据元素; 存在唯一的被称为“最后一个”的或“终端”的数据元素; 除第一个元素之外,集合中的每一个数据元素均有且仅有一个前趋; 除最后一个元素之外,集合中的每一个数据元素均有且仅有一个后继。3/2/202343.1 顺序表l3.1.1 线性表的基本概念线性表是n(n0)个数据元素的有限序列,记为:L=(a1,a2,a

2、i,an)林鹏黄龙张艺谋张三丰(A,B,C,D,E,Z)字母表登记表3/2/20235线性表的基本运算 初始化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),其中1

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

4、; int last; / 指示当前表长 sequenlist;89907868985566775588英语数学last=5maxlen3/2/202383.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) maxsize3/2/202393.1.3 顺序表上的基本运算(1)顺序表元素插入操作的算法:void insert(sequenlist *L,elemtype x,i

5、nt i) int j; if(i(L-last+1) printf(“插入位置不正确插入位置不正确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*/3/2/2023103.1.3 顺序表上的基本运算(2)顺序表元素删除操作的算法:A1A2A3AiAn删除第i个元素需要移动n-i次平均移动次数: (n-i)/n (其中i=0.n-1) 算法的时间复杂度T(n)=O(

6、n) 3/2/2023113.1.3 顺序表上的基本运算(2)顺序表元素删除操作的算法: void delete(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; 3/2/202312举例删除顺序表中的重复元素l算法思路:从顺序表中第一个元素起,逐个检查它后面是否有值相同的其它元素,若有便删除之;直到表中所有元素都已无重复元素为止。为此,算法中需设两重循环,外层控制清除的趟数,内层控制每趟

7、的检查范围。3/2/202313举例删除顺序表中的重复元素void Purge(sequenlist *L) int 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)3/2/2023143.2 链表l顺序表存储的缺点1)预先分配连续的空间2)不能根据需要动态分配3)插入删除等操作需要

8、移动大量数据HELLO3/2/2023153.2 链表l单链表单链表 l循环链表循环链表 l双向链表双向链表 3/2/2023163.2.1单链表l单链表的组成及定义HELLO数据域 指针域结点组成结点组成结点定义:结点定义:typedef struct node elemtp data; struct node *next;LinkList;L头指针头指针3/2/2023173.2.1单链表l头结点,头指针,第一个结点(首元结点)HELLO第一个结点第一个结点head头结点头结点头指针头指针3/2/2023183.2.1单链表l动态生成一个结点 LinkList *H; H=(LinkLis

9、t *) malloc(sizeof(LinkList);l 对结点中域的访问 H-elemtp和H-next 或 (*H).elemtp和(*H).nextl释放结点占用的空间 free(H) 3/2/2023193.2.2单链表上的基本运算(1)单链表建立: /尾插法建表尾插法建表:输入:输入n个字符建立链表个字符建立链表,直到输入为直到输入为*结束结束LinkList *CreateLinkList() char ch; LinkList *head;/*head为头结点指针为头结点指针*/ LinkList *r,*P; head=(LinkList *)malloc(sizeof(L

10、inkList); 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; HELLO头结点头结点head思考:头插法建表怎么建?rprp3/2/2023203.2.2单链表上的基本运算(2)求表长int LengthLinkList(LinkLi

11、st *L) LinkList *P=L; int j=0; While(P-next!=NULL) P=P-next; j+; return j; /*返回表长返回表长*/ HELLO头结点头结点head3/2/202321(3)单链表元素的查找/查找元素为查找元素为X的结点的结点LinkList *LocateLinkList(LinkList *L,elemtyPe x;) LinkList *P; P=L-next; while(P!=NULL)&(P-data!=x) P=P-next; return P; /*返回找到的结点位置或返回找到的结点位置或NULL*/ /*LocateL

12、inkList*/3/2/202322(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/2023233.2.2单链表上的基本运算(4)单链表元素插入操作linklist_insert(linknode *L,int i,elemtp x)HELLOLwPq=(LinkList*)mall

13、oc(sizeof(LinkList);q-data=x;q-next=p-next;/修改指针修改指针p-next=q;q3/2/2023243.2.2单链表上的基本运算(3 3)单链表元素插入操作)单链表元素插入操作intlinklist_insert(linknode*L,inti,elemtpx)linknode*p,*q;intj=0;p=L;while(p-next!=NULL)&(j+next;if(j=i-1)q=(LinkList *)malloc(sizeof(LinkList);/建立新建立新结点结点q-data=x;q-next=p-next;/修改指针修改指针p-ne

14、xt=q;return(1);elsereturn(0);/插入位置无效插入位置无效3/2/2023253.2.2单链表上的基本运算(5)单链表元素删除操作linklist_del(linknode *L,int i)HELLOLPq=p-next;p-next=q-next; free(p); 3/2/202326删除单链表L中的第i个结点算法LinkList *deleteLinkList(LinkList *L,int i) LinkList *P,*S; P=getLinkList(L,i-1);/*查找第查找第i-1个结点个结点*/ if(P=NULL) Printf(“第第i-1个

15、元素不存在,参数个元素不存在,参数i 有错有错n”); else S=P-next; P-next=S-next; free (S); *deleteLinkList*/ 该算法的时间复杂度为该算法的时间复杂度为O(n)3/2/2023273.2.3循环链表和双向链表1.循环链表HHELLOH非空循环链表非空循环链表思考:如何判断是最后一个元素?如何判断是空表?思考:如何判断是最后一个元素?如何判断是空表?空表空表head-next=head;3/2/2023283.2.3循环链表和双向链表2.双向链表前驱 数据 后继双链表结点格式Lhel格式定义:typedef struct dbnode

16、elemtp data; struct dbnode *prior,*next;dblinknode;h空表空表L3/2/202329双向链表l插入结点将S结点插入P之前Lhel S-prior=P-prior; S-next=P; P-prior-next=s; P-prior=S; pAS3/2/202330双向链表l2.删除结点思考:双向如何添加删除双链表结点Lhelp-piror-next=p-next;p-next-piror=p-piror;free(p);p3/2/2023313.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; 3/2/202332多项式相加算法的思路l不产生新结点而利用原有结点空间,设两个指针变量p和q分别指向A和B两个多项式单链表的第一个结点,依次比较两指针所指结点的指数项。l若

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!