四川企业品牌网站建设,免费发布广告信息平台,网站建设源代码 费用,临汾市住房城乡建设局网站1.数据结构基本概念
数据结构: 它是研究计算机数据间关系#xff0c;包括数据的逻辑结构和存储结构及其操作。 数据#xff08;Data#xff09;#xff1a;数据即信息的载体#xff0c;是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。 数据元素#xf…1.数据结构基本概念
数据结构: 它是研究计算机数据间关系包括数据的逻辑结构和存储结构及其操作。 数据Data数据即信息的载体是能够输入到计算机中并且能被计算机识别、存储和处理的符号总称。 数据元素Data Element数据元素是数据的基本单位又称之为记录Record。一般数据元素由若干基本项或称字段、域、属性组成。 #mermaid-svg-p7j3wYItEhBWfkeo {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-p7j3wYItEhBWfkeo .error-icon{fill:#552222;}#mermaid-svg-p7j3wYItEhBWfkeo .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-p7j3wYItEhBWfkeo .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-p7j3wYItEhBWfkeo .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-p7j3wYItEhBWfkeo .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-p7j3wYItEhBWfkeo .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-p7j3wYItEhBWfkeo .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-p7j3wYItEhBWfkeo .marker{fill:#333333;stroke:#333333;}#mermaid-svg-p7j3wYItEhBWfkeo .marker.cross{stroke:#333333;}#mermaid-svg-p7j3wYItEhBWfkeo svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-p7j3wYItEhBWfkeo .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-p7j3wYItEhBWfkeo .cluster-label text{fill:#333;}#mermaid-svg-p7j3wYItEhBWfkeo .cluster-label span{color:#333;}#mermaid-svg-p7j3wYItEhBWfkeo .label text,#mermaid-svg-p7j3wYItEhBWfkeo span{fill:#333;color:#333;}#mermaid-svg-p7j3wYItEhBWfkeo .node rect,#mermaid-svg-p7j3wYItEhBWfkeo .node circle,#mermaid-svg-p7j3wYItEhBWfkeo .node ellipse,#mermaid-svg-p7j3wYItEhBWfkeo .node polygon,#mermaid-svg-p7j3wYItEhBWfkeo .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-p7j3wYItEhBWfkeo .node .label{text-align:center;}#mermaid-svg-p7j3wYItEhBWfkeo .node.clickable{cursor:pointer;}#mermaid-svg-p7j3wYItEhBWfkeo .arrowheadPath{fill:#333333;}#mermaid-svg-p7j3wYItEhBWfkeo .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-p7j3wYItEhBWfkeo .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-p7j3wYItEhBWfkeo .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-p7j3wYItEhBWfkeo .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-p7j3wYItEhBWfkeo .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-p7j3wYItEhBWfkeo .cluster text{fill:#333;}#mermaid-svg-p7j3wYItEhBWfkeo .cluster span{color:#333;}#mermaid-svg-p7j3wYItEhBWfkeo div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-p7j3wYItEhBWfkeo :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 数据结构 逻辑结构 存储结构 线性结构 线性表 栈 队列 非线性结构 树形结构 图形结构 顺序存储 链式存储 索引存储 散列存储 数据运算 检索\排序\插入\删除\修改 1.1.数据的逻辑结构
数据的逻辑结构表示数据运算之间的抽象关系。按每个元素可能具有的直接前趋数和直接后继数将逻辑结构分为“线性结构”和“非线性结构”两大类。 线性结构 一个对一个如线性表、栈、队列 树形结构 一个对多个如树。
图状结构 多个对多个 此外还有集合 数据元素间除“同属于一个集合”外无其它关系。
1.2.数据的存储结构
存储结构逻辑结构在计算机中的具体实现方法。
存储结构是通过计算机语言所编制的程序来实现的因而是依赖于具体的计算机语言的。
顺序存储Sequential Storage 将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中。 如c语言的一维数组如表 L(a1,a2……,an)的顺序结构 链式存储重点 将数据结构中各元素分布到存储器的不同点用地址或链指针方式建立它们之间的联系。 数据结构中元素之间的关系在计算机内部很大程度上是通过地址或指针来建立的。
索引存储 在存储数据的同时建立一个附加的索引表即索引存储结构数据文件索引表。 散列存储 根据数据元素的特殊字段(称为关键字key)计算数据元素的存放地址然后数据元素按地址存放
2.线性表
线性表是包含若干数据元素的一个线性序列 记为 L(a0, … ai-1, ai, ai1 … an-1)
L为表名ai (0≤i≤n-1)为数据元素 n为表长,n0 时线性表L为非空表否则为空表。 线性表L可用二元组形式描述 L (D,R)即线性表L包含数据元素集合D和关系集合R D{ai | ai∈datatype ,i0,1,2, ∙∙∙∙∙∙∙∙∙n-1 ,n≥0}R{ai , ai1 | ai , ai1∈D, 0≤i≤n-2}关系符ai, ai1在这里称为有序对表示任意相邻的两个元素之间的一种先后次序关系ai是ai1的直接前驱, ai1是ai的直接后继
线性表的特征
对非空表,a0是表头,无前驱an-1是表尾,无后继其它的每个元素ai有且仅有一个直接前驱ai-1和一个直接后继ai1。
线性表包括顺序表和链表其中链表又包括单链和双链。线性表具体分类如下 设有一个顺序表L{1,2,3,4,5,6}; 他们的关系如图: #mermaid-svg-V3R5GysfzjOPGZog {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-V3R5GysfzjOPGZog .error-icon{fill:#552222;}#mermaid-svg-V3R5GysfzjOPGZog .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-V3R5GysfzjOPGZog .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-V3R5GysfzjOPGZog .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-V3R5GysfzjOPGZog .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-V3R5GysfzjOPGZog .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-V3R5GysfzjOPGZog .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-V3R5GysfzjOPGZog .marker{fill:#333333;stroke:#333333;}#mermaid-svg-V3R5GysfzjOPGZog .marker.cross{stroke:#333333;}#mermaid-svg-V3R5GysfzjOPGZog svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-V3R5GysfzjOPGZog .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-V3R5GysfzjOPGZog .cluster-label text{fill:#333;}#mermaid-svg-V3R5GysfzjOPGZog .cluster-label span{color:#333;}#mermaid-svg-V3R5GysfzjOPGZog .label text,#mermaid-svg-V3R5GysfzjOPGZog span{fill:#333;color:#333;}#mermaid-svg-V3R5GysfzjOPGZog .node rect,#mermaid-svg-V3R5GysfzjOPGZog .node circle,#mermaid-svg-V3R5GysfzjOPGZog .node ellipse,#mermaid-svg-V3R5GysfzjOPGZog .node polygon,#mermaid-svg-V3R5GysfzjOPGZog .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-V3R5GysfzjOPGZog .node .label{text-align:center;}#mermaid-svg-V3R5GysfzjOPGZog .node.clickable{cursor:pointer;}#mermaid-svg-V3R5GysfzjOPGZog .arrowheadPath{fill:#333333;}#mermaid-svg-V3R5GysfzjOPGZog .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-V3R5GysfzjOPGZog .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-V3R5GysfzjOPGZog .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-V3R5GysfzjOPGZog .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-V3R5GysfzjOPGZog .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-V3R5GysfzjOPGZog .cluster text{fill:#333;}#mermaid-svg-V3R5GysfzjOPGZog .cluster span{color:#333;}#mermaid-svg-V3R5GysfzjOPGZog div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-V3R5GysfzjOPGZog :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 1 2 3 4 5 6 使用二元组描述L(D,R),则 D{1 , 2 , 3 , 4 , 5 , 6}(n6)R{1,2 , 2,3 , 3,4 , 4,5 , 5,6}2.1. 顺序表
2.1.1.顺序存储结构的表示
若将线性表L(a0,a1, ……,an-1)中的各元素依次存储于计算机一片连续的存储空间。 设Loc(ai)为ai的地址Loc(a0)b每个元素占d个单元 则Loc(ai)bi*d
2.1.2.顺序存储结构的特点
逻辑上相邻的元素 ai, ai1其存储位置也是相邻的对数据元素ai的存取为随机存取或按地址存取存储密度高存储密度D(数据结构中元素所占存储空间)/整个数据结构所占空间顺序存储结构的不足 对表的插入和删除等运算的时间复杂度较差
2.1.3.顺序存储的C语言实现
在C语言中可借助于一维数组类型来描述线性表的顺序存储结构
#define N 100
typedef int data_t;
typedef struct
{ data_t data[N] //表的存储空间int last;
} sqlist, *sqlink; 2.1.4.线性表的基本运算
设线性表 L(a0,a1, ……,an-1)对 L的基本运算有 1)建立一个空表list_create(L) 2)置空表list_clear(L) 3)判断表是否为空list_empty (L)。若表为空返回值为1 , 否则返回 0 4)求表长length (L) 5)取表中某个元素GetList(L , i ), 即ai。要求0≤i≤length(L)-1 6)定位运算Locate(L,x)。确定元素x在表L中的位置或序号 L o c a t e ( L , x ) { i 当元素 x a i ∈ L , 且 a i 是第一个与 x 相等时 − 1 x 不属于 L 时 Locate(L,x) \begin{cases} i 当元素xai∈L,且ai是第一个与x相等时 \\ -1 x不属于L时 \\ \end{cases} Locate(L,x){i−1当元素xai∈L,且ai是第一个与x相等时x不属于L时 定位确定给定元素x在表L中第一次出现的位置或序号。即实现Locate(L,x)。算法对应的存储结构如图所示。 7)插入 Insert(L,x,i)。将元素x插入到表L中第i个元素ai之前,且表长1。 插入前: (a0,a1,—,ai-1,ai,ai1-------,an-1) 0≤i≤n,in时,x插入表尾 插入后: (a0,a1,—,ai-1, x, ai,ai1-------,an-1)
插入算法思路若表存在空闲空间且参数i满足0≤i≤L-last1,则可进行正常插入。插入前将表中L-data[L-last]L-data[i]部分顺序下移一个位置然后将x插入L-data[i]处即可。算法对应的表结构。 8)删除 Delete(L,i)。删除表L中第i个元素ai且表长减1, 要求0≤i≤n-1。 删除前: (a0,a1,—,ai-1,ai,ai1-------,an-1) 删除后: (a0,a1,—,ai-1ai1-------,an) 删除将表中第i个元素ai从表中删除即实现DeleteSqlist(L, i)。 算法思路 若参数i满足0≤i≤L-last, 将表中L-data[i1]∽L-data[L-last] 部分顺序向上移动一个位置覆盖L-data[i]。
2.1.5.顺序表缺点
线性表的顺序存储结构有存储密度高及能够随机存取等优点但存在以下不足 (1)要求系统提供一片较大的连续存储空间。 (2)插入、删除等运算耗时且存在元素在存储器中成片移动的现象
2.2. 链表
链表主要学习单链表
2.2.1.线性表的链式存储结构
将线性表L(a0,a1,……,an-1)中各元素分布在存储器的不同存储块称为结点通过地址或指针建立元素之间的联系 结点的data域存放数据元素ai而next域是一个指针指向ai的直接后继ai1所在的结点。
2.2.2.单链表的C语言实现
1.创建结构体 typedef struct node{ data_t data; //结点的数据域//struct node *next; //结点的后继指针域//}listnode, *linklist; 设p指向链表中结点ai 获取ai写作p-data 而取ai1,写作p-next-data 若指针p的值为NULL则它不指向任何结点, 此时取p-data或p-next是错误的。 可调用C语言中malloc()函数向系统申请结点的存储空间
linklist p;
p (linklist)malloc(sizeof(listnode));则创建一个类型为linklist的结点且该结点的地址已存入指针变量p中 2.建立单链表 依次读入表L(a0,…,an-1)中每一元素ai(假设为整型)若ai≠结束符-1则为ai创建一结点然后插入表尾最后返回链表的头结点指针H。 设L(248-1)则建表过程如下 链表的结构是动态形成的即算法运行前表结构是不存在的 3.链表查找 1按序号查找实现GetLinklist(h, i)运算。 算法思路从链表的a0起判断是否为第i结点若是则返回该结点的指针否则查找下一结点,依次类推。 2按值查找定位 即实现Locate(h, x)。 算法思路从链表结点a0起依次判断某结点是否等于x,若是则返回该结点的地址若不是则查找下一结点a1,依次类推。若表中不存在x,则返回NULL。 4.链表的插入 即实现InsertLinklist(h, x, i,)。将x插入表中结点ai之前的情况。 算法思路调用算法GetLinklist(h, i-1)获取结点ai-1的指针p(ai 之前驱)然后申请一个q结点存入x并将其插入p指向的结点之后。 5.链表的删除 即实现DeleteLinklist(h, i) 算法对应的链表结构如图所示。 算法思路同插入法先调用函数GetLinklist(h, i-1),找到结点ai的前驱然后将结点ai删除之。
2.2.3.设计算法将单链表H倒置
算法思路依次取原链表中各结点将其作为新链表首结点插入H结点之后
2.2.4.设计算法求两节点之和
设结点data域为整型求链表中相邻两结点data值之和为最大的第一结点的指针。
算法思路设p,q 分别为链表中相邻两结点指针求p-dataq-data为最大的那一组值返回其相应的指针p即可
2.2.5.链表合并
设两单链表A、B按data值设为整型递增有序将表A和B合并成一表A且表A也按data值递增有序。 算法思路设指针p、q分别指向表A和B中的结点若p-data ≤q-data则p结点进入结果表否则q结点进入结果表。
3.栈
栈是限制在一端进行插入操作和删除操作的线性表俗称堆栈允许进行操作的一端称为“栈顶”另一固定端称为“栈底”当栈中没有元素时称为“空栈”。 特点 后进先出LIFO。
3.1.顺序栈
它是顺序表的一种具有顺序表同样的存储结构由数组定义配合用数组下标表示的栈顶指针top相对指针完成各种操作。
3.1.1.C语言实现
1.创建结构体
typedef int data_t ; /*定义栈中数据元素的数据类型*/
typedef struct
{ data_t *data ; /*用指针指向栈的存储空间*/int maxlen; /*当前栈的最大元素个数*/int top ; /*指示栈顶位置(数组下标)的变量*/} sqstack; /*顺序栈类型定义*/2.创建栈
sqstack *stack_create (int len)
{
sqstack *ss;
ss (seqstack *)malloc(sizeof(sqstack));
ss-data (data_t *)malloc(sizeof(data_t) * len);
ss-top -1;
ss-maxlen len;
return ss;
}3.清空栈
stack _clear(sqstack *s)
{s- top -1 ;
} //判断栈是否空
int stack_empty (sqstack *s)
{ return (s-top -1 ? 1 : 0);
}4.进栈
void stack_push (sqstack *s , data_t x)
{ if s-top N - 1{printf ( “overflow !\n”) ; return ;}else { s-top ;s-data[s-top] x ;}return ;
}5.出栈
datatype stack_pop(sqstack *s)
{s-top--;return (s-data[s-top1]);
} //取栈顶元素:
datatype get_top(sqstack *s)
{return (s-data[s-top]);
}3.2.链式栈
C语言实现过程如下 插入操作和删除操作均在链表头部进行链表尾部就是栈底栈顶指针就是头指针。 1.创建结构体
ypedef int data_t ; /*定义栈中数据元素数据类型*/
typedef struct node_t {data_t data ; /*数据域*/struct node_t *next ; /*链接指针域*/
} linkstack_t ; /*链栈类型定义*/ 2.创建空栈 linkstack_t *CreateLinkstack() { linkstack_t *top;top (linkstack_t *)malloc(sizeof(linkstack_t));top-next NULL;return top;
}//判断是否空栈 :
int EmptyStack (linkstack_t *top)
{ return (top-next NULL ? 1 : 0);
}3.入栈
void PushStack(linkstack_t *top, data_t x)
{
linkstack_t *p ;
p (linkstack_t *)malloc ( sizeof (linkstack_t) ) ;
p-data x ;
p-next top-next;
top-next p;
return;
}4.队列
队列是限制在两端进行插入操作和删除操作的线性表
允许进行存入操作的一端称为“队尾”允许进行删除操作的一端称为“队头”当线性表中没有元素时称为“空队”特点 先进先出FIFO front指向队头元素的位置; rear指向队尾元素的下一个位置。在队列操作过程中为了提高效率以调整指针代替队列元素的移动并将数组作为循环队列的操作空间。为区别空队和满队满队元素个数比数组元素个数少一个。
4.1.顺序队列
C语言实现 1.创建结构体
typedef int data_t ; /*定义队列中数据元素的数据类型*/
#define N 64 /*定义队列的容量*/
typedef struct {data_t data[N] ; /*用数组作为队列的储存空间*/int front, rear ; /*指示队头位置和队尾位置的指针*/
} sequeue_t ; /*顺序队列类型定义*/2.创建空队列
sequeue_t *CreateQueue ()
{ sequeue_t *sq (sequeue_t *)malloc(sizeof(sequeue_t));sq-front sq-rear maxsize -1;return sq;
}
//判断队列空
int EmptyQueue (sequeue_t *sq) {return (sq-front sq-rear) ;
}3.入队 将新数据元素x插入到队列的尾部
void EnQueue (sequeue_t *sq , data_t x)
{sq-data[sq-rear] x ; sq-rear (sq-rear 1) % N return ;
}4.2.链式队列 C语言实现 1.创建结构体 插入操作在队尾进行删除操作在队头进行由队头指针和队尾指针控制队列的操作。
typedef int data_t;
typedef struct node_t
{ data_t data ; struct node_t *next; } linknode_t, *linklist_t; typedef struct{ linklist_t front, rear; } linkqueue_t; 2.创建空队列
linkqueue_t *CreateQueue()
{ linkqueue_t *lq (linkqueue_t *)malloc(sizeof(linkqueue_t));lq-front lq-rear (linklist_t)malloc(sizeof(linknode_t));lq-front-next NULL ; /*置空队*/return lq; /*返回队列指针*/
}//判断队列空
int EmptyQueue(linkqueue_t *lq) { return ( lq-front lq-rear) ;
} 3.入队 void EnQueue (linkqueue_t *lq, data_t x)
{lq-rear-next (linklist_t)malloc(sizeof(linknode_t)) ; lq-rear lq-rear-next; /*修改队尾指针*/lq-rear-data x ; /*新数据存入新节点*/lq-rear-next NULL ; /*新节点为队尾*/return;
}4.出队
data_t DeQueue(linkqueue_t *lq)
{data_t x;linklist_t p; /*定义一个指向队头结点的辅助指针*/p lq-front-next ; /*将它指向队头结点*/lq-front-next p-next ; /*删除原先队头结点x p-data;free(p) ; /*释放原队头结点*/if (lq-front-next NULL) lq-rear lq-front;return x;
}5.树和二叉树
5.1.树的相关概念
树Tree是nn≥0个节点的有限集合T它满足两个条件
有且仅有一个特定的称为根Root的节点。其余的节点可以分为mm≥0个互不相交的有限集合T1、T2、……、Tm其中每一个集合又是一棵树并称为其根的子树。 表示方法 树形表示法、目录表示法。 度 一个节点的子树的个数称为该节点的度数一棵树的度数是指该树中节点的最大度数。度数为零的节点称为树叶或终端节点度数不为零的节点称为分支节点除根节点外的分支节点称为内部节点。 路径 一个节点系列k1,k2, ……,ki,ki1, ……,kj,并满足ki是ki1的父节点就称为一条从k1到kj的路径路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先后面节点是前面节点的子孙。节点的层数等于父节点的层数加一根节点的层数定义为一。树中节点层数的最大值称为该树的高度或深度。 有序树 若树中每个节点的各个子树的排列为从左到右不能交换即兄弟之间是有序的则该树称为有序树。 森林 mm≥0棵互不相交的树的集合称为森林。 树去掉根节点就成为森林森林加上一个新的根节点就成为树 树的逻辑结构 树中任何节点都可以有零个或多个直接后继节点子节点但至多只有一个直接前趋节点父节点根节点没有前趋节点叶节点没有后继节点。
5.2.二叉树
二叉树是nn≥0个节点的有限集合可以是空集n0 也可以是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。 严格区分左孩子和右孩子即使只有一个子节点也要区分左右。
5.2.1.二叉树的性质
二叉树第ii≥1层上的节点最多为2i-1个。 深度为kk≥1的二叉树最多有2k1个节点。 满二叉树 深度为kk≥1时有2k1个节点的二叉树。 完全二叉树 只有最下面两层有度数小于2的节点且最下面一层的叶节点集中在最左边的若干位置上。 具有n个节点的完全二叉树的深度为 log2n1或 log2(n1)。 顺序存储结构 完全二叉树节点的编号方法是从上到下从左到右根节点为1号节点。设完全二叉树的节点数为n某节点编号为i。
当i1不是根节点时有父节点其编号为i/2;当2i≤n时有左孩子其编号为2i ,否则没有左孩子本身是叶节点;当2i1≤n时有右孩子其编号为2i1 ,否则没有右孩子当i为奇数且不为1时有左兄弟其编号为i-1,否则没有左兄弟当i为偶数且小于n时有右兄弟其编号为i1,否则没有右兄弟
有n个节点的完全二叉树可以用有n1个元素的数组进行顺序存储节点号和数组下标一一对应下标为零的元素不用。 利用以上特性可以从下标获得节点的逻辑关系。不完全二叉树通过添加虚节点构成完全二叉树然后用数组存储这要浪费一些存储空间。
5.2.2.二叉树的顺序存储 5.2.2.二叉树的链式存储
C语言实现创建结构体
typedef int data_t ;
typedef struct node_t;
{data_t data ; struct node_t *lchild ,*rchild ;
} bitree_t ;
bitree_t *root ; 二叉树由根节点指针决定。
5.2.3.二叉树的遍历运算
遍历 沿某条搜索路径周游二叉树对树中的每一个节点访问一次且仅访问一次。 二叉树是非线性结构每个结点有两个后继则存在如何遍历即按什么样的搜索路径进行遍历的问题。 由于二叉树的递归性质遍历算法也是递归的。三种基本的遍历算法如下
先访问树根再访问左子树最后访问右子树先访问左子树再访问树根最后访问右子树先访问左子树再访问右子树最后访问树根
先序遍历算法
void PREORDER ( bitree *r)
{if ( r NULL ) return ; //空树返回printf ( “ %c ”,r-data ); //先访问当前结点PREORDER( r-lchild ); //再访问该结点的左子树PREORDER( r-rchild ); //最后访问该结点右子树
}中序遍历算法 若二叉树为空树则空操作否则中序遍历左子树。 当访问根结点中序遍历右子树。
void INORDER ( bitree *r)
{if ( r NULL ) return ; //空树返回INORDER( r-lchild ); //先访问该结点的左子树printf ( “ %c ”,r-data ); //再访问当前结点INORDER( r-rchild ); //最后访问该结点右子树
}后序遍历算法 若二叉树为空树则空操作否则后序遍历左子树 当访问根结点后序遍历右子树。
void POSTORDER ( bitree *r)
{if ( r NULL ) return ; //空树返回POSTORDER( r-lchild ); //先访问该结点的左子树POSTORDER( r-rchild ); //再访问该结点右子树printf ( “ %c ”,r-data ); //最后访问当前结点
}遍历的路径相同均为从根节点出发逆时针沿二叉树的外缘移动每个节点均经过三次。按不同的次序访问可得不同的访问系列每个节点有它的逻辑前趋父节点和逻辑后继子节点也有它的遍历前趋和遍历后继要指明遍历方式。
按编号遍历算法
NOORDER ( bitree *r) /*按编号顺序遍历算法*/
{int front, rear;bitree *Q[N];if ( r NULL ) return ; /*空树返回*/for (rear1;rearN; rear) Q[rear] NULL ;front rear 1; Q[rear] r;while ( Q[front] ! NULL ) { /*以下部分算法由学生完成设计*//*访问当前出队节点*//*若左孩子存在则左孩子入队*//*若有孩子存在则右孩子入队*//* front向后移动*/}
}#mermaid-svg-MYe6VxLrI1IMyzcV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV .error-icon{fill:#552222;}#mermaid-svg-MYe6VxLrI1IMyzcV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-MYe6VxLrI1IMyzcV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-MYe6VxLrI1IMyzcV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-MYe6VxLrI1IMyzcV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-MYe6VxLrI1IMyzcV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-MYe6VxLrI1IMyzcV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-MYe6VxLrI1IMyzcV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-MYe6VxLrI1IMyzcV .marker.cross{stroke:#333333;}#mermaid-svg-MYe6VxLrI1IMyzcV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-MYe6VxLrI1IMyzcV .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV .cluster-label text{fill:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV .cluster-label span{color:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV .label text,#mermaid-svg-MYe6VxLrI1IMyzcV span{fill:#333;color:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV .node rect,#mermaid-svg-MYe6VxLrI1IMyzcV .node circle,#mermaid-svg-MYe6VxLrI1IMyzcV .node ellipse,#mermaid-svg-MYe6VxLrI1IMyzcV .node polygon,#mermaid-svg-MYe6VxLrI1IMyzcV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-MYe6VxLrI1IMyzcV .node .label{text-align:center;}#mermaid-svg-MYe6VxLrI1IMyzcV .node.clickable{cursor:pointer;}#mermaid-svg-MYe6VxLrI1IMyzcV .arrowheadPath{fill:#333333;}#mermaid-svg-MYe6VxLrI1IMyzcV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-MYe6VxLrI1IMyzcV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-MYe6VxLrI1IMyzcV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-MYe6VxLrI1IMyzcV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-MYe6VxLrI1IMyzcV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-MYe6VxLrI1IMyzcV .cluster text{fill:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV .cluster span{color:#333;}#mermaid-svg-MYe6VxLrI1IMyzcV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-MYe6VxLrI1IMyzcV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} # # # # A B C D E F G H I J K 6.查找算法
查找 设记录表L(R1 R2……Rn)其中Ri(l≤i≤n)为记录对给定的某个值k在表L中确定keyk的记录的过程称为查找。 若表L中存在一个记录Ri的keyk记为Ri.keyk则查找成功返回该记录在表L中的序号i(或Ri 的地址)否则(查找失败)返回0(或空地址Null)。
6.1.平均查找长度
对查找算法主要分析其T(n)。查找过程是key的比较过程时间主要耗费在各记录的key与给定k值的比较上。比较次数越多算法效率越差即T(n)量级越高故用“比较次数”刻画算法的T(n)。
一般以“平均查找长度”来衡量T(n)。 平均查找长度ASLAverage Search Length对给定k查找表L中记录比较次数的期望值(或平均值)即 Pi为查找Ri的概率。等概率情况下Pi1/nCi为查找Ri时key的比较次数(或查找次数)。
6.2.顺序表的查找
顺序表是将表中记录(R1 R2……Rn)按其序号存储于一维数组空间 记录Ri的类型描述如下
typedef struct
{ keytype key; //记录key//…… //记录其他项//
} Retype;顺序表类型描述如下:
#define maxn 1024 //表最大长度//
typedef struct
{ Retype data[maxn]; //顺序表空间//int len; //当前表长表空时len0//
} sqlist;若说明sqlist r则r.data[1]……r.data[r.len]为记录表(R1……Rn) Ri.key为r.data[i].key, r.data[0]称为监视哨为算法设计方便所设。
算法思路: 设给定值为k在表(R1 R2……Rn)中从Rn开始查找keyk的记录。
int sqsearch(sqlist r, keytype k)
{ int i;r.data[0].key k; //k存入监视哨//i r.len; //取表长//while(r.data[i].key ! k) i--; return (i);
}设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数) 若r.data[n].key k Cn1若r.data[n-1].key k Cn-12……若r.data[i].key k Cin-i1……若r.data[1].key k C1n故ASL O(n)。而查找失败时查找次数等于nl同样为O(n)。
对查找算法若ASLO(n)则效率是很低的意味着查找某记录几乎要扫描整个表当表长n很大时会令人无法忍受。
6.3.折半查找算法
算法思路: 对给定值k逐步确定待查记录所在区间每次将搜索空间减少一半(折半)直到查找成功或失败为止。 设两个游标low、high分别指向当前待查找表的上界(表头)和下界(表尾)。mid指向中间元素。 现查找k20的记录。 再看查找失败的情况设要查找k85的记录。 C语言实现如下
int Binsearch(sqlist r, keytype k) //对有序表r折半查找的算法//
{ int low, high, mid; low 1;high r.len; while (low high) { mid (lowhigh) / 2; if (k r.data[mid].key) return (mid); if (k r.data[mid].key) high mid-1; else low mid1;} return(0);} 不失一般性设表长n2h-lhlog2(n1)。记录数n恰为一棵h层的满二叉树的结点数。得出表的判定树及各记录的查找次数如图所示。
6.4.分块查找算法
设记录表长为n将表的n个记录分成b[n/s]个块每块s个记录最后一块记录数可以少于s个即 且表分块有序即第i1≤i≤b-1块所有记录的key小于第i1块中记录的key但块内记录可以无序。 步骤
建立索引每块对应一索引项其中kmax为该块内记录的最大keylink为该块第一记录的序号或指针。 顺序、折半、分块查找和树表的查找中其ASL的量级在O(n)O(log2n)之间。不论ASL在哪个量级都与记录长度n有关。随着n的扩大算法的效率会越来越低。ASL与n有关是因为记录在存储器中的存放是随机的或者说记录的key与记录的存放地址无关因而查找只能建立在key的“比较”基础上。
7.排序算法
稳定排序和非稳定排序 设文件fR1……Ri……Rj……Rn中记录Ri、Rji≠ji、j1……n的key相等即KiKj。 若在排序前Ri领先于Rj排序后Ri仍领先于Rj则称这种排序是稳定的其含义是它没有破坏原本已有序的次序。 内排序和外排序
若待排文件f在计算机的内存储器中且排序过程也在内存中进行称这种排序为内排序。若排序中的文件存入外存储器排序过程借助于内外存数据交换或归并来完成则称这种排序为外排序。 各种内排序方法可归纳为以下五类 1插入排序 2交换排序 3选择排序 4归并排序 插入排序方法可归纳为以下五类 (1) 直接插入排序 (2) 折半插入排序 (3) 链表插入排序 (4) Shell希尔排序
7.1.直接插入排序
设待排文件fR1 R2……Rn相应的key集合为k{k1 k2……kn} 排序方法: 先将文件中的R1看成只含一个记录的有序子文件然后从R2起逐个将R2至Rn按key插入到当前有序子文件中最后得到一个有序的文件。插入的过程上是一个key的比较过程即每插入一个记录时将其key与当前有序子表中的key进行比较找到待插入记录的位置后将其插入即可。 设文件记录的key集合k{5036667695122536}
7.2.折半插入排序
排序算法的T(n)O(n2),是内排序时耗最高的时间复杂度。
折半插入排序方法 先将R[1]看成一个子文件然后依次插入R[2]……R[n]。但在插入R[i]时子表[R[1]……R[i-1]]已是有序的查找R[i]在子表中的位置可按折半查找方法进行从而降低key的比较次数。
7.3.链表插入排序
设待排序文件fR1 R2……Rn对应的存储结构为单链表结构 链表插入排序实际上是一个对链表遍历的过程。先将表置为空表然后依次扫描链表中每个结点设其指针为p搜索到p结点在当前子表的适当位置将其插入。 设含4个记录的链表如图
7.4.起泡排序 7.5.快速排序
设记录的key集合k{5036667636122595}每次以集合中第一个key为基准的快速排序过程如下
