《数据结构课程的主要内容》由会员分享，可在线阅读，更多相关《数据结构课程的主要内容（31页珍藏版）》请在金锄头文库上搜索。
1、数据结构课程的主要容数据结构的基本概念基本概念和术语算法和算法分析（典型算法） 线性表线性表的概念定义和特点 线性表的实现顺序表示和链式表示（特点、定义） 线性表的基本操作建立（正序、逆序、有序）、查找、插入、删除、输出线性表的应用合并、时间复杂度A循环链表和双向链表 栈和队列栈和队列的定义栈的表示、实现和操作（出栈、入栈） 队列的表示（链队列、循环队列*）、实现和操作（入队列、 出队列） 串（串的基本概念和基本操作） 数组数组的定义A 数组的地址计算（一维、二维、三维）A 特殊矩阵的概念和地址计算（对称、上（下）三角、对角、 稀疏）树和二叉树A树的定义和基本术语二叉树O二叉树的性质O二叉树的
2、存储结构O 二叉树的遍历A树和森林O 树的存储结构O 树、森林与二叉树的转换O 树和森林的遍历哈夫曼树与其应用图图的定义和术语图的存储结构图的遍历 查找查找的基本概念静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析动态查找表（二叉排序树和平衡二叉树）哈希表 排序（直接插入、冒泡、选择、快速和归并）第一章 数据结构课程的主要容（二）线性表线性表的类型定义线性表是n个（n 0）数据元素的有限序列。数据元素可以是各种各 样的（例若干个数据项组成），但同一线性表中的元素必定具有一样特性。口 在数据元素的非空有限集中，存在唯一的一个第一个和唯一一个最后一个元素，除次之外，每个元素有唯一的前驱和唯
3、一的后继。 线性表（a1,ai-1,ai,ai+1,，a“）n为线性表的长度，i为元素在线性表中的位序。 线性表的操作：建立空表、删除表、置空表、判空表、统计表长、 查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用）线性表的顺序表示和实现顺序表 线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单 元依次存放线性表的数据元素。LOC（a）=LOC（a）+（i-l）*ll为每个元素所占的空间i1 线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素，物理位 置上也相邻的特点。顺序表是一种随机存取的存储结构 通常用数组描述顺序表struct sqlist#define LEN 100
4、#defineLEN 100int*elem;struct sqlistintaLEN;intlength;int aLEN;int length;intlistsize;int length;口顺序表的表示顺序表的操作 顺序表初始化 顺序表的插入 顺序表的删除移动大量元素 顺序表的查找线性表的插入(n +1)ai，a2,%-,ai，ai+i，插入位置的判斷(n +1)(q)(p)元素移动的顺序和位置ai，a2,耳詐,%,包表长的变化线性表的删除(n-1)a,a ,a .a.,a .a删除位置的判斷12i-1 i i+1 n(p) (q)元素移动的顺序和位置ai,a2,ai-i, %an表长的
5、变化时间复杂度求表长 O(1)查找第i个元素、前趋、后继0(1)查找值为x的元素的位序0(n)插入元素 O(n)(0+1+n)/(n +l)=n/2 删除元素 0(n)(0+1+n-1)/n=(n-1)/2 顺序表适用于不常进行插入、删除运算，表中元素相对稳定的 场合。A线性表的链式表示和实现线性链表线性表的链式存储结构是用一组任意的(可连续、也可不连续) 存储单元存储线性表的数据元素。为表示元素间的逻辑关系，除了存储数据元素本身的信息之 外，还需存储一个指示其直接后继的信息。即指针为数据元素 之间逻辑关系的映象。结点包括两个域：数据域和指针域(链)，个结点成一个(单) 链表。指示链表中第一个
6、结点地址的指针称为头指针，最后一个结点的指针为空(NULL)。单链表可由头指针唯一确定。h链表的表#define NULL 0struct nodeint data;struct node *next;struct node *head; /*head 为头指针/若head二NULL，则表示空表。headp-next为处理方便，在单链表的第一个结点前附设一个结点，称为头 结点。此时，head-next指向第一个结点。p指向第 i 个结点，则 p-data二a ; p-next-data二a ;ii+1单链表是一种非随机(顺序)存储结构。单链表的操作查找第i个元素O(n)指针p从指向第一个结点的
7、位置(head-next)向后移动(p=p-next)i_ 次。1)插入O(n)查找插入点的前趋结点p(2)生成新结点ss-next=p-next;4)p-next=s;删除0(n)p-next=p-next-next 建立含头结点的单链表(动态生成)head=(struct node *) malloc (sizeof(struct node); head-next=NULL;q=(struct node *) malloc (sizeof(struct node);(1)顺序从表头至表尾设P为指向链表当前最后一个结点的指针p-next=q; p=q;2）逆序从表尾至表头q-next =he
8、ad-next; head-next=q;3）有序递增或递减循环链表 最后一个结点的指针域指向头结点，形成一个环。空表：head-next二head;双向链表口结点含两个指针域，分别指向直接前趋和后继。口 p-next-priou二p-priou-next二p口双向循环链表链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选存 储结构。栈和队列 栈和队列是两种重要的线性结构。从数据结构角度看，它们是操 作受限的线性表。栈一一后进先出的线性表（LIFO）抽象数据类型的定义栈是限定仅在表尾进行插入或删除操作的线性表。表尾称为栈 顶，表头称为栈底。基本操作：取栈顶元素（查找）、入栈（插入）和
9、出栈（删除）栈底栈顶 栈的表示和实现顺序栈栈的顺序存储结构 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置。typedef struct int *base;int *top;sqstack;#define MAX 100Typedef structint stackMAXint top;SEQSTACK;SEQSTACK *s;构造空栈s.top = s.base s-top = 0 返回栈顶元素e=*(s.top-1) e=s.stacks.top-1 入栈*s.top+=e s-stacks-top=e s-top=s-top+1
10、 出栈e=*-s.tope=s-stacks-top-1 s-top=s-top-1栈满s.top-s.base=MAX s-top=MAX链栈栈的链式表示栈顶指针为top栈空 top=NULL;入栈生成新结点ss-link=top; top=s;出栈输出 top-data;top=top-link;栈的应用举例 int check(SEQSTACK *s) 数制转换int bool; char ch;括号匹配的检验push(s,#); bool=1;行编辑程序ch=getchar();表达式求值 while (ch!二n &bool)栈与递归if (ch二二()push(s,ch);if (
11、ch=)if (gettop(s)=#) bool=0; else pop(s);ch=getchar(); if （gettop（s）!=#） bool=0; /*（多于）*/if （bool） printf（“rigth”）; else rintf（“error”）;队列先进先出的线性表（FIFO）抽象数据类型队列的定义 队列是限定在表的一端（对尾）进行插入，而在另一端（队头）进 行删除操作的线性表。基本操作：入队列（插入）和出队列（删除） 出队列 a a a- a 入队列1 2 n 1 n4 front=q-rear=(QNODE*)malloc(QNODE);q-front-next=
12、NULL;链队列判空q-front=q-rear;元素入队列新生成结点s; s-next二NULL;q-rear-next=s; q-rear=s;元素出队列(非空队列)p=q-front-next; q-front-next=p-next if (q-rear=p) q-rear=q-front 循环队列队列的顺序表示和实现typedef structint dataMAXint front,rear;SE UEUE;SE UEUE *q;头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个 位置。由于存在假溢出(q-rear二MAX)，可将顺序队列臆造成一个环状空 间，称为循环队列。
13、队空和队满的判别条件一样：q-front二二q-rear两种处理办法：(1) 增设标志位(2) 少用一元素空间。队空：q-fro nt二二 q-rear队满：q-fron t=(q-rear +1)%MAX串9 串类型的定义串(String)(或字符串)是由零个或多个字符组成的有限序列。 记为：s=a a (n0)12 n S为串名，单引号括起来的字符序列是串的值，n为串的长度。子串主串中任意个连续字符组成的子序列。 位置字符在序列中的序号为该字符在串中的位置。子串在主 串中的位置以子串的第一个字符在主串中位置来表示。串相等两个串的长度相等，且每个对应位置的字符都相等。 空串零个字符的串为空串，长度为0，用0表示。 空格串由一个或多个空格组成的串为空格串。长度为空格字 符的个数。串的基本操作：通常以“串的整体”为操作对象。串赋值串复制求子串判空串串连接子串定位串比较串替换求串长串插入串清空串删除0 串的表示和实现定长顺序存储表示为每个串变量分配一个固定长度地址连续的存储区。 #defin
