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

数据结构课程的主要内容☆数据结构的基本概念＞基本概念和术语＞算法和算法分析（典型算法）☆ 线性表＞线性表的概念定义和特点＞线性表的实现一一顺序表示和链式表示（特点、定义）＞线性表的基本操作——建立（正序、逆序、有序）、查找、插入、删除、输出＞线性表的应用一一合并、时间复杂度＞循环链表和双向链表☆ 栈和队列＞栈和队列的定义A栈的表示、实现和操作（出栈、入栈）＞队列的表示（链队列、循环队列*）、实现和操作（入队列、出队列）☆ 串（串的基本概念和基本操作）☆ 数组＞数组的定义＞数组的地址计算（一维、二维、三维）＞特殊矩阵的概念和地址计算（对称、上（下）三角、对角、稀疏）☆树和二叉树＞树的定义和基本术语＞二叉树o二叉树的性质o二叉树的存储结构o 二叉树的遍历＞树和森林o 树的存储结构o 树、森林与二叉树的转换o 树和森林的遍历＞哈夫曼树及其应用☆图＞图的定义和术语＞图的存储结构＞图的遍历☆ 查找＞查找的基本概念＞静态查找表（顺序表、有序表、索引顺序表）的算法和性能分析＞动态查找表（二叉排序树和平衡二叉树）＞哈希表☆ 排序（直接插入、冒泡、选择、快速和归并）第一章 数据结构课程的主要内容（二）线性表A线性表的类型定义线性表是n个（n 0）数据元素的有限序列。

数据元素可以是各种各样的（例若干个数据项组成），但同一线性表中的元素必定具有相同特性口在数据元素的非空有限集中，存在唯一的一个第一个和唯 个最后一个元素，除次之外，每个元素有唯一的前驱和唯一的后继口线性表（a],...,ai_]叫叫+],…叫）n 为线性表的长度， i 为元素性表中的位序线性表的操作：建立空表、删除表、置空表、判空表、统计表长、查询（值、位序、前驱、后继）、插入元素、删除元素、函数调用）〉线性表的顺序表示和实现——顺序表线性表的顺序表示（顺序存储结构）是指用一组地址连续的存储单元依次存放线性表的数据元素LOC（ai）=LOC（a1）+（i-1）*l l 为每个元素所占的空间线性表的顺序存储结构（顺序表）具有逻辑上相邻的元素， 物理位置上也相邻的特点顺序表是一种随机存取的存储结构通常用数组描述顺序表顺序表的表示struct sqlist{ int *elem; int length; int listsize; };#define LEN 100 struct sqlist{ int a[LEN]; int length;};#define LEN 100 int a[LEN]; int length;顺序表的操作顺序表初始化顺序表的插入顺序表的删除移动大量元素顺序表的查找线性表的插入(n+1)片件,..叫一1，气+i，...0(q)*(p)弘豊,・牛-1飞叫叫+F 线性表的删除(n-1)ai,a2,…备叫叫+f(p) —► (q)ai,a2,ai+1时间复杂度插入位置的判断(n+1)元素移动的顺序和位置 表长的变化删除位置的判断元素移动的顺序和位置表长的变化求表长 O(1)查找第 i 个元素、前趋、后继 O(1)查找值为x的元素的位序O(n)插入元素 O(n)删除元素 O（n）(0+1+ +n-l)/n=(n-l)/2顺序表适用于不常进行插入、删除运算，表中元素相对稳定的 场合。

»线性表的链式表示和实现——线性链表线性表的链式存储结构是用一组任意的（可连续、也可不连续） 存储单元存储线性表的数据元素为表示元素间的逻辑关系，除了存储数据元素本身的信息之 外，还需存储一个指示其直接后继的信息即指针为数据元素 之间逻辑关系的映象结点包括两个域：数据域和指针域（链）n个结点链接成一 个（单）链表指示链表中第一个结点地址的指针称为头指针，最后一个结点的指针为空（NULL）单链表可由头指针唯一确定链表的表示口#define structNULL 0node{int data;struct node *next;};structnode *head;/*head 为头指针/若head=NULL，则表示空表为处理方便，在单链表的第一个结点前附设一个结点，称为头 结点此时，head->next指向第一个结点p 指向第 i 个结点，则 p->data=ai; p->next->data=a i+1; 单链表是一种非随机(顺序)存储结构单链表的操作 .：.查找第i个元素O(n) 指针p从指向第一个结点的位置(head->next)向后移动p=p->next)i-1 次1)3)2)生成新结点 s查找插入点的前趋结点 ps->next=p->next;4) p->next=s;删除 O(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 =head->next; head->next=q;3) 有序——递增或递减循环链表 最后一个结点的指针域指向头结点，形成一个环。

口 空表：head->next=head;双向链表 结点含两个指针域，分别指向直接前趋和后继口 p->next->priou=p->priou->next=p口双向循环链表链表在空间上利用合理，插入、删除方便，很多场合是线性表的首选 存储结构栈和队列 栈和队列是两种重要的线性结构从数据结构角度看，它们 是操作受限的线性表>栈——后进先出的线性表（LIFO）◊抽象数据类型的定义o栈是限定仅在表尾进行插入或删除操作的线性表表尾称为 栈顶，表头称为栈底基本操作：取栈顶元素（查找）、入栈（插入）和出栈（删除）a a …… a- a1 2 n 1 n栈底 栈顶◊ 栈的表示和实现O顺序栈 栈的顺序存储结构利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，附设栈顶指针top指示栈顶元素在顺序栈中的位置typedef struct {int *base;int *top;}sqstack;#define MAX 100Typedef struct{int stack[MAX] int top;}SEQSTACK;SEQSTACK *s;构造空栈s.top = s.base返回栈顶元素e=*(s.top-1)入栈*s.top++=e出栈e=*--s.top栈满s->top = 0e=s.stack[s.top-1] s->stack[s->top]=es->top=s->top+1 e=s->stack[s->top-1]s->top=s->top-1O链栈 栈的链式表示栈顶指针为top栈空 top=NULL;入栈生成新结点ss->link=top; top=s;出栈输出 top-〉data;栈的应用举例int check(SEQSTACK *s)数制转换{int bool; char ch;括号匹配的检验push(s,'#'); bool=1;行编辑程序ch=getchar();表达式求值while (ch!=‘\n'&&bool)栈与递归{if (ch==‘(‘) push(s,ch)if (ch==‘)')if(gettop(s)==‘#') bool=0; elsetop=top->link;ch=getchar(); }pop(s);if (gettop(s)!=‘#') bool=0; /*'('多于‘)'*/if (bool) printf(“rigth”);else rintf(“error”);}队列——先进先出的线性表（FIFO）抽象数据类型队列的定义 队列是限定在表的一端（对尾）进行插入，而在另一端（队头 进行删除操作的线性表。

基本操作：入队列（插入）和出队列（删除）出队列 a a …… a- a 入队列1 2 n 1 nY < 队头 队尾链队列——队列的链式表示和实现typedef struct qnode{int data;struct qnode *next;}QNODEtypedef struct {QNODE *front, *rear;}LINKQUEUE;LINKQUEUE *q;链队列初始化q->front=q->rear=（QNODE*）malloc（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 循环队列——队列的顺序表示和实现typedef struct{int data[MAX]int front,rear;}SEUEUE;SEUEUE *q;头指针始终指向队列头元素，尾指针始终指向队列尾元素的下一个 位置。

由于存在假溢出（q-〉rear二MAX），可将顺序队列臆造成一个环状空 间，称为循环队列队空 和队满的判别条件相同：q-〉front==q-〉rear两种处理办法:(1)增设标志位(2)少用一元素空间队空： q-＞front==q-＞rear队满： q-＞front==(q-＞rear+1)%MAX串9 串类型的定义＞串(St ring)(或字符串)是由零个或多个字符组成的有限序列 记为：s二'a a・・・a ' (n 0)1 2 n＞ S为串名，单引号括起来的字符序列是串的值，n为串的长度＞子串一一主串中任意个连续字符组成的子序列＞位置——字符在序列中的序号为该字符在串中的位置子串在 主 串中的位置以子串的第一个字符在主串中位置来表示＞串相等一一两个串的长度相等，且每个对应位置的字符都相等＞空串——零个字符的串为空串，长度为0,用0表示＞空格串——由一个或多个空格组成的串为空格串长度为空格字 符的个数＞串的基本操作：通常以“串的整体”为操作对象＞串赋值 串复制＞求子串 判空串＞串连接 子串定位>串比较串替换>求串长串插入>串清空串删除9 串的表示和实现＞定长顺序存储表示为每个串变量分配一个固定长度地址连续的存储区。

define MAX 255unsigned char sstring[MAX+1];0 号单元存放串的长度＞堆分配存储表示。