数据结构对象的基本概念.docx
- 文档编号:18588085
- 上传时间:2023-08-19
- 格式:DOCX
- 页数:59
- 大小:73.43KB
数据结构对象的基本概念.docx
《数据结构对象的基本概念.docx》由会员分享,可在线阅读,更多相关《数据结构对象的基本概念.docx(59页珍藏版)》请在冰点文库上搜索。
数据结构对象的基本概念
第一章绪论
一、内容提要
1数据结构研究的内容。
2基本概念:
数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。
3算法的定义及五个特征。
4算法描述:
类PASCAL语言。
5算法设计要求。
6算法分析。
二、学习重点
1数据结构的“三要素”:
逻辑结构、物理(存储)结构及在这种结构上所定义的操作(运算)。
2抽象数据类型的定义、表示和实现方法。
3类PASCAL书写规范,过程(函数)中值参和变参的差别,过程调用规则。
4用计算语句频度来估算算法的时间复杂度。
三、例题解析
1写出以下各语句执行次数(左边括号内数字为语句序号)
(1)FORi:
=1TOnDO
(2)FORj:
=1tonDO
(3)[c[I,j]:
=0;
(4)FORk:
=1TOnDO
(5) c[I,j]:
=c[I,j]+a[I,k]*b[k,j]
]
[答案]:
各语句执行次数(频度)分别为n+1,n(n+1),n2,n2(n+1),n3
[分析]:
最容易发生的错误,是将第一个语句的执行次数答成n。
2编写最优算法,从小到大依次输出顺序读入的三个整数
PROCasscending;
{本算法对读入的三个整数进行排序,然后按从小到大输出}
{算法中核心语句如下}
read(a,b,c);
IFa>b
THEN[t:
=a;a:
=b;b:
=t];{a,b按正序排序}
IFb>c
THEN[t:
=c;c:
=b;{c为最大}
IFa =t{b为中间值} ELSE[b: =a;a: =t]{a,b正序} WRITELN(a: 4,b: 4,c: 4); ENDP;{assending} [分析]: 本题正确算法有多种,但上面是最优算法: 最好情况下只经过两次比较且无数据移动,而在最 坏情况下,也只是经过三次比较,七个赋值语句就完成了排序。 在本课程教学中,强调“好”的算法,不仅仅是结果正确,而且是最优的算法。 这与PASCAL语言教学中的要求有很大不同。 算法是供人来阅读的,必须牢记这一点。 算法中语句的书写格式采用缩进规则,保留字用大写 ,其余标识符小写,提高了算法的易读性。 第二章 线性表 一、内容提要 1.线性表是元素间约束力最强的一类数据结构。 2.线性表的逻辑结构定义,对线性表定义的操作。 3.线性表的存储结构: 顺序存储结构和链式存储结构。 4.线性表的操作在两种存储结构中的实现。 5.一元多项式的线性表表示方法,及高次(稀疏)多项式的抽象数据类型定义、表示和加法的实现。 二、学习重点 1.1. 线性表的逻辑结构,指线性表的数据元素间存在着线性关系。 在顺序存储结构中,元素存储的先后位置反映出这种线性关系,而在链式存储结构中,是靠指针来反映这种关系的。 2.2. 顺序存储结构用向量(一维数组)表示,给定下标,可以存取相应元素,属于随机存取的存储结构。 3.3. 尽管“只要知道某结点的指针就可以存取该元素”,但因链表的存取都需要从头指针开始,顺链而行,故链表不属于随机存取结构。 4.4. 链表是本章学习的重点和难点。 要理解头结点,首元结点和元素结点的差别。 理解头结点是为了在插入、删除等操作时,为了算法的统一而设立的(若无头结点,则在第一元素前插入元素或删除第一元素时,链表的头指针总在变化)。 掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作。 5.5. 链表操作中应注意不要使链意外“断开”。 因此,若在某结点前插入一个元素,或删除某元素,必须知道该元素的前驱结点的指针。 6.6. 从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点。 7.7. 静态链表是又一重点和难点。 应和链表进行比较、理解。 例如,在有头结点的链表情况下,第一元素是p: =la^.next,而在静态链表中则i: =sa[0].next;相对p: =p^.next,有i: =sa[i].next来找到第i个元素的后继。 三、例题解析 1.设线性表以顺序存储结构存于a(1..n)中,试编写算法将该线性表就地逆置。 【分析】 向量逆置有几种方法,如逆向读入到另一数组中,在正向对应赋值,即: FORi: =nDOWNTO1DOb[n-i+1]: =a[i];FORi: =1TOnDOa[i]: =b[i]; 这里要求“就地逆置”,即不能另用一数组空间。 【算法】 PROCinvert(VARa: arr;n: integer); {a是存储线性表的一维数组,有n个元素,本算法将a逆置。 } FORi: =1TO(nDIV2)DOa[i]↔a[n-i+1]; endp; 【讨论】 将n个元素的一维数组逆置,为什么循环控制变量用ndiv2,而不用n? 2.编写在单链表上进行排序的算法 【分析】 这里使用插入排序。 链表中插入元素要知道待插入元素位置的前驱, 以pre表示之。 结束的条件是链表为空。 【算法】 PROCinsertsort(VARla: linklist); {la是带头结点的单链表的指针,本算法将链表中元素正序排序。 算法的基本思想是先假定第一个元素有序,然后从第二个元素开始,依次插入到有序的表中,直到全部元素插入完为止} p: =la^.next^.next;{假定链表非空,即至少有一个结点} la^.next^.next: =nil;{设有序链表中当前只有一个结点} found: =false; WHILE(p<>nil)ANDNOTfoundDO [s: =p^.next;{记住下一个结点} pre: =la; q: =la^.next; found: =false; WHILE(q<>nil)ANDNOTfoundDO IFq^.data =q;q: =q^.next] ELSEfound: =true; p^.next: =q; pre^.next: =p;{p结点插入} p: =s;{取下一个结点} ] ENDP;{insertsort} 【讨论】算法中found为一布尔变量,为的是在链表到尾前,如找到p的插 入位置,即可退出WHILE循环。 这里循环条件未写成: (p<>nil)AND(q^.data 因为若q=nil,则再引用q^.data是无意义的。 请记住这种退出循环,引入布尔变量的作法。 3.设两个非递减有序的线性表各有m和n个元素(m>0,n>0),分别存于一维数组a和b中,且a的存储空间足够大。 试编写算法将两线性表合并成一线性表,结果仍是非递减有序,要求算法的时间复杂度是o(m+n)。 【分析】两个有序线性表合并成一个有序表,教材中已有讨论,算法非常简单。 本算法要求复杂度为O(m+n),这是着重点。 题目叙述中有“a的空间足够大”,暗示出若将m+n个元素合并到a中,不会溢出。 为使数据移动次数最少,应先将两表中最大元素置于m+n的位置上,然后相应指针减1,再比较之,直到两表中有一个指针减到0,则结束,否则,将b中剩余元素传到a中相应位置即可。 【算法】 PROCunion(VARa: seqlisttp;b: seqlisttp); {a,b是两个非递减有序表,顺序存储结构存储,各有m和n个元素,本算法将两表合并到a中,仍为有序表,算法时间复杂度为O(m+n)} i: =m;j: =n;k: =m+n;{i,j,k分别为表a,b和结果表的指针} WHILE(i>0)AND(j>0)DO IFa[i]>b[j]THEN[a[k]: =a[i];i: =i-1;k: =k-1] ELSE[a[k]: =b[j];j: =j-1;k: =k-1]; WHILE(j>0)DO[a[k]: =b[j];j: =j-1;k: =k-1]; {若b表中尚有元素,则传至a中相应位置} 【讨论】本算法至多比较m+n次,往a中赋值m+n次。 最好情况是比较n次,往a中赋值n次,该种情况是b中最小元素不小于a中最大元素。 问题: 为什么在退出第一个WHILE循环后,不讨论(即没有)WHILEi>0的情况? 第三章栈和队列 一、内容提要 1.1.从数据结构角度讲,栈和队列也是线性表,其操作是线性表操作的子集,属操作受限的线性表。 但从数据类型的角度看,它们是和线性表大不相同的重要抽象数据类型。 2.2.栈的定义及操作。 栈是只准在一端进行插入和删除操作的线性表,该端称为栈的顶端。 3.3.栈的顺序和链式存储结构,及在这两种结构下实现栈的操作。 4.4.栈的应用: 表达式求值,递归过程及消除递归。 5.5.队列的定义及操作,队列的删除在一端(尾),而插入则在队列的另一端(头)。 因此在两种存储结构中,都需要队头和队尾两个指针。 6.6.链队列空的条件是首尾指针相等,而循环队列满的条件的判定,则有队尾加1等于 队头和设标记两种方法。 二、学习重点 1.栈和队列操作在两种存储结构下的实现。 2.中缀表达式转成前缀、后缀表达式并求值。 3.用递归解决的问题: 定义是递归的,数据结构是递归的,及问题的解法是递归的, 掌握典型问题的算法。 4.4. 链队列删除时为空的处理(令队尾指针指向队头)。 特别是仅设尾指针的循环链队 列的各种操作的实现。 5.5. 循环队列队空定义为队头指针等于队尾指针,队满则可用一个单元(教材中所示) 及设标记办法(下面例题)。 这里特别注意取模运算。 6.6. 在后续章节中要注意栈和队列的应用,如串中心对称的判定,二叉树遍历的递归 和非递归算法,图的深度优先遍历等都用到栈,而树的层次遍历、图的宽度优先遍 历等则用到队列。 三、例题解析 1.1.两栈共享一向量空间,编写入栈和出栈算法。 TYPE TwoWayStack=RECORD{双栈共享一向量空间} elem: ARRAY[1..m]OFelemtype; top: ARRAY[0..1]OF0..m+1;{两个栈顶指针} END; PROCinistack(VARtws: TwoWayStack);{初始化} {初始化双向栈tws为空} tws.top[0]: =0;{左端栈指针} tws.top[1]: =m+1;{右端栈指针} ENDP;{inistack} PROCPUSH(VARtws: TwoWayStack;i: 0..1;x: elemtype;VARofw: boolean); {若双向栈tws不满,则将x插入到i端,成功时ofw为true,失败为false} IF(tws.top[1]-tws.top[0])<>1 THEN{栈未满} CASEiOF 0: tws.top[0]: =tws.top[0]+1;tws.elem[tws.top[0]]: =x;ofw: =true 1: tws.top[1]: =tws.top[1]-1;tws.elem[tws.top[1]]: =x;ofw: =true ENDC ELSEofw: =false;(栈满) ENDP;{push} PROCPOP(VARtws: TwoWayStack;i: 0..1;VARx: elemtype;VARunderflow: boolean); {若双向栈tws非空,则将i端退栈,栈空时underflow为true} CASEiOF 0: IFtws.top[0]=0{栈空} THEN[underflow: =true;return(underflow)] ELSE[tws.top[0]: =tws.top[0]-1; x: =tws.elem[tws.top[0]+1];{弹出元素} ]; 1: IFtws.top[1]=m+1{栈空} THEN[underflow: =true;return(underflow)] ELSE[tws.top[1]: =tws.top[1]+1; x: =tws.elem[tws.top[1]-1];{弹出元素} ]; ENDC ENDP;{pop} 【讨论】上面算法中用0和1代表两端,且按操作在哪端来分两种情况进行讨论,逻辑清楚。 也可用一个公式表示插入(进栈)和删除(退栈)指针位置。 例如,插入时top=top+1-2*i,删除时top=top-1+2*i。 表达简洁,但不如上面清楚易读。 2.2.将中缀表达式转换成后缀表达式,并进行表达式求值。 PROCtrnssufix(VARexp2: string;s: stack;exp1: string); {本算法将中缀表达式exp1转为后缀表达式exp2,使用运算符栈s} {算法基本思想是依次从中缀表达式读入字符w: 若w是变量,直接送入结果表达式,若w是运算符,则与栈顶运算符比较,若级别高,则进栈;若低,则栈顶元素退栈,并送入结果表达式,再取栈顶运算符比较,重复以上步骤;若w=’)’,则栈元素依次退栈,并送入结果表达式,直至')'退栈} initstring(exp2);initstack(s);push(s,’#’); op: =['+','-','*','/','(',')','#'];{操作符集合} read(w); WHILENOT((w='#')AND(GETTOP(OPTR)='#'))DO IFNOT(wINop)THEN[insert(exp2,w);read(w) ]; ELSECASEprecede(GETTOP(s),w)OF '<': [PUSH(S,w);read(w)]; '=': IFw=’)’THEN{遇右括号后,运算符退栈并送结果表达式, 直至左括号} [x: =POP(S); WHILEx<>’(‘DO[insert(exp2,x);x: =POP(S)] read(w)]; '>': [b: =POP(S);insert(exp2,b)]; END; ENDP; PROCsufixeval(VARexp2: string;s: stack;VARsn: stack); {本算法对后缀表达式exp2求值,使用运算符栈s和操作数栈sn} {算法基本思想是逐字符从左到右顺序读入后缀表达式。 若读入的字符w是数,则直接压入栈sn中;若w是运算符,则与栈顶运算符比较,若级别高,则进栈;否则,从运算数栈弹出两个操作数,和从运算符栈弹出的一个运算符进行相应运算,结果存入操作数栈中。 w运算符再与栈顶运算符比较优先级。 直至后缀表达式处理完毕。 这时sn栈中只剩一个数,即表达式结果。 } initstring(sn);initstack(s); op: =['+','-','*','/','(',')','#'];{操作符集合} read(w);{从左到右顺序读入后缀表达式} WHILENOTempty(exp2)DO IFNOT(wINop)THEN[PUSH(sn,w);read(w) ]; ELSECASEprecede(GETTOP(s),w)OF '<': [PUSH(s,w);read(w)]; '>': [a: =POP(sn);b: =POP(sn);theta: =POP(s); PUSH(sn,operate(athetab))]; END; ENDP;{sufixeval} 3、用设标记来判定循环队列满,编写入队和出队的算法。 {本算法用设标记tag的办法,解决循环队列队满和队列空的判断问题,tag=0表示队列空,tag=1表示队列不空} TYPE cyclicqueue=RECORD{设头 尾指针和标志域的循环队列} elem: =ARRAY[0..m-1]OFelemtype; rear,front: 0..m-1 tag: 0..1; {0为空,1为非空} END; PROCINITQUEDE(VARcq: cyclicqueue); {初始化} cq.tag: =0;cq.tear: =cq.front: =0; ENDP; PROCENQUEUE(VARcq: cyclicqueue;x: elemtype); {cq是由头尾指针和标志域的循环队列,本算法是入队操作,若队列不满,} {则将x插入到队尾} IF(cq.tag=1)AND(cq.front=cq.rear) THENreturn(false){队满} ELSE[cq.rear: =(cq.rear+1)MODm; cq.elem(cq.rear): =r; IFcq.tag=0THENcq.tag: =1{由空变不空标记} ] ENDP; PROCDELQUEUE(VARcq: cyclicqueue); {cq是由头尾指针和标志域的循环队列,本算法是出队操作,若队列非空} {则将队头元素出队} IFcq.tag=0 THENreturn(false){队空} ELSE[cq.front: =(cq.front+1)MODm; IFcq.front=cq.rearTHENcq.tag: =0{队空} ] ENDP; CONSTm=maxlen; {队列长度} TYPE cyclicqueue=RECORD {只设尾指针和队列长度的循环队列} elem: ARRAY[0..m-1]OFelemtype; rear: 0..m-1; length: 0..m; {队列长度} END; PROCINIT_queue(VARq: cyclicqueue); {初始化} q.rear: =0;q.length: =0; ENDP; FUNCadd_queue(VARq: cyclicqueue;x: elemtype): boolean; {q是由尾指针和长度标志的循环队列,本算法是入队操作,若队列不满,} {将x插入到队尾} IFq.length=m THENadd_queue: =false{队列满} ELSE[q.rear: =(q.rear+1)modm; q.elem[q.rear]: =x; q.length;=q.length+1; add_queue: =true{入队成功} ] ENDF; FUNCdd_queue(VARq: cyclicqueue;x;elemtype): boolean; {q是由尾指针和长度标志的循环队列,本算法是出队操作,若队列不空,} {将将队头元素出列,并赋给x,队长度减1} IFq.length=0 THENdd_queue: =false{队空} ELSE[front;=(q.rear-q.length+1+m)modm x: =q.elem[front] q.length: =q.length-1 ] ENDF; 第四章 串 一、内容提要 1、1、 是数据元素为字符的线性表,串的定义及操作。 2、2、 的基本操作,编制算法求串的其它操作。 3、3、 的存储结构,因串是数据元素为字符的线性表,所以存在“结点大小“的问题。 静态和动态(块链结构,堆结构)存储的优缺点。 4、4、 朴素模式匹配算法及改进(KMP)算法。 二、学习重点 1、1、 串的基本操作,编写串的其他操作(如index,replace等)。 2、在串的模式匹配中,求匹配串的nextval函数值。 3、尽管朴素的模式匹配的时间复杂度是O(m*n),KMP算法是O(m+n),但在一般情况下,前者实际执行时间近似O(m+n),因此至今仍被采用。 KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多,其主要优点是主串不回嗍。 5、5、 串操作在存储结构下的实现。 三、例题解析 1、利用串的如下基本运算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法 PROCreplace(VARs: string;t,v: string); {本算法实现串的置换操作,用串v置换串s中所有非重叠的t串。 } i: =INDEX(s,t);{判s中有无t} IFi<>0 THEN[CREATE(temp,‘’);{t为临时串变量,存放部分结果} m: =LENGTH(t);n: =LENGTH(s); WHILEi<>0DO [ASSIGN(temp,CONCAT(temp,SUBSTR(s,1,i-1),v)); {用v替换t形成部分结果} ASSIGN(s,SUBSTR(s,i+m,n-i-m+1));{t串以后形成新s串} n: =n-(i-1)-m; i: =INDEX(s,t); ] ASSIGN(s,CONCAT(temp,s));{将剩余s连接临时串t再赋给s} ] ENDP; FUNCindex(s1: string;t: string): integer; {本算法求串t在串s中的第一次出现。 结果是: 若t在s中,则给出串t的第一个字符在串s中的位置,若不存在,则返回0} j: =1;m: =length(s);n: =length(t);eq: =true; WHILE(j<=m-n+1)ANDeqDO IFequal(substr(s,j,n),t) THENeq: =false ELSEj: =j+1; IFj<=m+n-1THENindex: =j ELSEindex: =0 ENDF;{index} 【讨论】本题是用给定的基本操作,编写其它操作的算法。 这种类型题较多,必须严格按题的要求来做,不准选择具体存储结构。 否则,即使全对,也很难得分。 22 设目标为t=’abcaabbabcabaac
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 对象 基本概念