数据结构课程的主要内容.docx

《数据结构课程的主要内容.docx》由会员分享，可在线阅读，更多相关《数据结构课程的主要内容.docx（20页珍藏版）》请在优知文库上搜索。

1、数据结构课程的主要内容数据结构课程的主要内容数据结构的基本概念基本概念和术语算法和算法分析（典型算法）线性表线性表的概念定义和特点线性表的实现依次表示和链式表示（特点、定义）线性表的基本操作建立（正序、逆序、有序）、查找、插入、删除、输出线性表的应用合并、时间困难度循环链表和双向链表栈和队列栈和队列的定义栈的表示、实现和操作（出栈、入栈）队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列）串（串的基本概念和基本操作）数组数组的定义数组的地址计算（一维、二维、三维）特别矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏）树和二叉树树的定义和基本术语二叉树O二叉树的性质O二叉树的存储结

2、构O二叉树的遍历树和森林O树的存储结构O树、森林与二叉树的转换。树和森林的遍历哈夫曼树及其应用图图的定义和术语图的存储结构图的遍历查找查找的基本概念静态查找表（依次表、有序表、索引依次表）的算法和性能分析动态查找表（二叉排序树和平衡二叉树）哈希表排序（干脆插入、冒泡、选择、快速和归并）第一章数据结构课程的主要内容（二）线性表线性表的类型定义线性表是n个（n0）数据元素的有限序列。数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性。在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最终一个元素，除次之外，每个元素有唯一的前驱和唯一的后继。线性表(al,ai

3、T,ai,ai+l,an)n为线性表的长度，i为元素在线性表中的位序。线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询(值、位序、前驱、后继)、插入元素、删除元素、函数调用)线性表的依次表示和实现依次表线性表的依次表示(依次存储结构)是指用一组地址连续的存储单元依次存放线性表的数据元素。1.OC(ai)=LOC(al)+(i-l)*l1为每个元素所占的空间线性表的依次存储结构(依次表)具有逻辑上相邻的元素，物理位置上也相邻的特点。依次表是一种随机存取的存储结构通常用数组描述依次表依次表的表示structsqlistttdefineLEN100#define1.EN100int*e

4、lem;structsqlistintaLEN:;intlength;intaLEN;intlength;intlistsize;intlength;)；依次表的操作依次表初始化依次表的插入依次表的删除移动大量元素依次表的查找线性表的插入(n+l)al,a2,ai-l,ai,ai+l,an插入位置的推断(n+l)(q)(P)元素移动的依次和位置al,a2,ai-l,b,ai,ai+l,an表长的变更线性表的删除(n-l)al,a2,ai-l,ai,ai+l,an删除位置的推断(p)(q)元素移动的依次和位置al,a2,ai-l,ai+l,an表长的变更时间困难度求表长O(I)查找第i个元素、前

5、趋、后继0(1)查找值为X的元素的位序0(n)插入元素0(n)(0+l+n)(n+l)=n2删除元素0(n)(0+l+n-l)n=(n-l)2依次表适用于不常进行插入、删除运算，表中元素相对稳定的场合。线性表的链式表示和实现线性链表线性表的链式存储结构是用一组随意的(可连续、也可不连续)存储单元存储线性表的数据元素。为表示元素间的逻辑关系，除了存储数据元素本身的信息之外，还需存储一个指示其干脆后继的信息。即指针为数据元素之间逻辑关系的映象。结点包括两个域：数据域和指针域(链)，n个结点链接成一个(单)链表。指示链表中第一个结点地址的指针称为头指针，最终一个结点的指针为空(NULL)。单链表可由

6、头指针唯一确定。链表的表示#defineNULLOstructnodeintdata;structnode*next;structnode*head;Ahead为头指针/若head=NULL,则表示空表。h为处理便利，在单链表的第一个结点前附设一个结点，称为头结点。此时，head-next指向第一个结点。P指向第i个结点，则p-data=ai;p-next-data=ai+1;单链表是一种非随机(依次)存储结构。单链表的操作查找第i个元素0(n)指针p从指向第一个结点的位置(head-next)向后移动(p=p-next)i-l次。插入0(n)(1)查找插入点的前趋结点p(2)生成新结点S(3

7、)s-next=p-next;(4)p-next=s;删除0(n)headppnneexxttppp-nextsppp-nneexxtt-nneexxttpp-nneexxttppp-next=p-next-next建立含头结点的单链表(动态生成)head=(structnode*)malloc(sizeof(structnode);head-next=NULL;q=(structnode*)malloc(sizeof(structnode);(1)依次从表头至表尾设p为指向链表当前最终一个结点的指针p-next=q;p=q;(2)逆序从表尾至表头q-next=head-next;head-n

8、ext=q;(3)有序递增或递减循环链表最终一个结点的指针域指向头结点，形成一个环。空表：head-next=head;双向链表结点含两个指针域，分别指向干脆前趋和后继。p-next-priou=p-priou-next=p双向循环链表链表在空间上利用合理，插入、删除便利，很多场合是线性表的首选存储结构。栈和队列栈和队列是两种重要的线性结构。从数据结构角度看，它们是操作受限的线性表。栈后进先出的线性表（LIFO）抽象数据类型的定义栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈顶，表头称为栈底。基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除）ala2an-1an栈底栈顶栈的表示和

9、实现依次栈栈的依次存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在依次栈中的位置。typedefstructint*base;int*top;sqstack;#defineMAX100TypedefstructintstackMAXinttop;SEQSTACK;SEQSTACK*s;构造空栈s.top=s.bases-top二0返回栈顶元素e=*（s.top-1）e=s.stacks.top-1入栈*s.top+=es-stacks-top=es-top=s-top+l出栈e=*-s.tope=s-stacks-top-ls-top=s-to

10、p-l栈满s.top-s.base=MAXs-top=MAX链栈栈的链式表示栈顶指针为top栈空top=NULL;入栈生成新结点sSTink=top;top=s;出栈输出top-data;top=top-link;栈的应用举例intcheck(SEQSTACK*s)数制转换i11tbool;charch;括号匹配的检验push(s,#);bool=l;行编辑程序ch=getchar();表达式求值while(ch!-nbool)栈与递归if(Ch=()push(s,ch);if(Ch=)if(gettop(s)bool=0;elsepop(s);ch=getchar();if(gettop(s

11、)1-#)bool=0;*(多于)*/if(bool)printf(rigth);elserintf(error);队列先进先出的线性表(FIFO)抽象数据类型队列的定义队列是限定在表的一端(对尾)进行插入，而在另一端(队头)进行删除操作的线性表。基本操作：入队列(插入)和出队列(删除)出队列ala2an-lan入队列队头队尾链队列队列的链式表示和实现typedefstructqnodeintdata;structqnode*next;QNODEtypedefstructQNODE*front,*rear;LINKQUEUE;1.INKQUEUE*q;链队列初始化q-front=q-rear=

12、(QNODE*)maHoc(QNODE);q-front-next=NULL;链队列判空q-front=q-rear;元素入队列新生成结点s;s-next=NULL;q-rear-next=s;q-rear=s;元素出队列(非空队列)p=q-front-next;q-front-next=p-nextif(q-rear=p)q-rear=q-front循环队列队列的依次表示和实现typedefstructintdataMAXintfront,rear;seqqueue；seqqueue*q；头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个位置。由于存在假溢出(q-rear=MAX),

13、可将依次队列臆造成一个环状空间，称为循环队列。队空和队满的判别条件相同：q-front=q-rear两种处理方法：(1)增设标记位(2)少用一元素空间。队空：q-front=q-rear队满：q-front=(q-rear+l)%MAX串串类型的定义串(String)(或字符串)是由零个或多个字符组成的有限序列。记为：S=ala2an(n0)S为串名，单引号括起来的字符序列是串的值，n为串的长度。子串主串中随意个连续字符组成的子序列。位置字符在序列中的序号为该字符在串中的位置。子串在主串中的位置以子串的第一个字符在主串中位置来表JO串相等两个串的长度相等，且每个对应位置的字符都相等。空串零个字

14、符的串为空串，长度为0,用表示。空格串由一个或多个空格组成的串为空格串。长度为空格字符的个数。串的基本操作：通常以串的整体为操作对象。串赋值串复制求子串判空串串连接子串定位串比较串替换求串长串插入串清空串删除串的表示和实现定长依次存储表示为每个串变量安排一个固定长度地址连续的存储区。defineMAX255unsignedcharsstringMAX+l;0号单元存放串的长度。堆安排存储表示在程序执行过程中，为每个串变量动态安排(malloc)一个地址连续的存储区。串的块链存储表示defineCSIZE80块的大小typedefstructChunkcharchCSIZE;structChun

15、k*next;Chunk;typedefstructChunk串长度*head,*tail;头尾指针intcurlen;1.string;数组数组的定义数组的性质数组元素数目固定，一旦定义，维数和维界就不再变更。数组元素具有相同的类型。数据元素的下标关系具有上下界的约束并且下标有序。数组的描述ji=O,bi-l,i=l,2,n,bi是数组第i维的长度D=ajlj2jnn（0）为数组的维数，ji是数组元素的第i维下标n=l表示一维数组，是线性表。n=2表示二维数组，以矩阵形式表示，它也可以看成是线性表，其中每个数据元素本身又是一个线性表。数组的基本操作初始化数组销毁数组取元素给定一组下标，返回相应的数组元素值。修改元素值（赋值）给定一组下标，修改相应的数组元素的值。数组的依次表