数据结构，清华大学出版社，严蔚敏吴伟民编著

第一章 绪论

1、 数据结构是计算机中存储、组织数据的方式。精心选择的数据结构可以带来最优效率的算法。

2、 程序设计= 算法 +数据结构

3、 解决问题方法的效率：

● 跟数据的组织方式有关

● 跟空间的利用效率有关

● 跟算法的巧妙程度有关

4、 数据：所有能输入到计算机中,且被计算机处理的符号的集合， 是计算机操作对象的总称；

是计算机处理的信息的某种特定的符号表示形式。

5、 数据元素：数据中的一个“个体”,数据结构中讨论的基本单位。 相当于“记录”,在计算机程序中通常作为一个整体考虑和处理。

6、 数据项: 相当于记录的“域”, 是数据的不可分割的最小单位,如学号。数据元素是数据项的集合。

7、 数据对象：性质相同的数据元素的集合.

例如: 所有运动员的记录集合

8、 数据结构：是相互间存在某种关系的数据元素集合。

9、 数据结构是带结构的数据元素的集合。

10、 不同的关系构成不同的结构。

11、 次序关系：

{|i=1,2,3,4,5,6}

12、 对每种数据结构，主要讨论如下两方面的问题：

1） 数据的逻辑结构，数据结构的基本操作；

2） 数据的存储结构，数据结构基本操作的实现；

13、 数据的逻辑结构：

数据之间的结构关系，是具体关系的抽象。

数据结构的基本操作：

指对数据结构的加工处理。

14、 数据的存储结构 (物理结构)：

数据结构在计算机内存中的表示。

数据结构基本操作的实现：

基本操作在计算机上的实现（方法)。

15、 数据结构的有关概念

16、数据元素的4类的基本结构：

集合；

线性结构：结构中数据元素之间存在一对一的关系；

树形结构：结构中数据元素之间存在一对多的关系；

图状结构或网状结构：结构中数据元素之间存在多对多的关系。

17、 C语言的优点：C语言可以直接操作内存。

18、 每个节点都由两部分组成：数据域和指针域。

19、 链接存储结构特点：

● 比顺序存储结构的存储密度小

(每个节点都由数据域和指针域组成)。

● 逻辑上相邻的节点物理上不必相邻。

● 插入、删除灵活

(不必移动节点，只要改变节点中的指针)。

20、 数据类型 是一个值的集合和定义在此集合上的一组操作的总称。

21、 ADT 有两个重要特征:数据抽象和数据封装。

22、 抽象数据类型 (Abstract Data Type 简称ADT)：是指一个数学模型以及定义在此数学模型上的一组操作。

23、 抽象数据类型有： 数据对象〈数据对象的定义〉、数据关系〈数据关系的定义〉、 基本操作〈基本操作的定义〉。

24、 数据类型的定义和含义。

定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。

含义：将数据按一定次序与形式存放的结构。

24、算法空间复杂度S(n)

算法的存储量包括：

1 输入数据所占的空间；

2 程序本身所占的空间；

3 辅助变量所占的空间。

25、 算法具有有穷性、确定性、可行性、输入和输出五大特性。

26、 抽象数据类型具有数据抽象、数据封装的特点。

27、 数据的储存结构分为：顺序存储结构和链式存储结构。

第二章 线性表

1、线性结构的特点：在数据元素中的非空有限集中。

（1）存在唯一的一个被称作“第一”的数据元素；

（2）存在唯一的一个被称作“最后一个”的数据元素；

（3）除第一个外，集合中的每一个数据元素均只有一个前驱；

（4）除最后一个外，集合中的每一个数据元素均只有一个后继。

2、线性表(Linear List) ：一个线性表是n个数据元素的有限序列。

3、线性表的顺序存储实现：

typedef struct {

ElementType Data[MAXSIZE];

int Last;

} List;

List L, *PtrL;

4、初始化（建立空的顺序表）

List *MakeEmpty( )

{ List *PtrL;

PtrL = (List *)malloc( sizeof(List) );

PtrL->Last = -1;

return PtrL;

}

5、查找

int Find( ElementType X, List *PtrL )

{ int i = 0;

while( i <= PtrL->Last && PtrL->Data[i]!= X )

i++;

if (i > PtrL->Last) return -1; /* 如果没找到，返回-1 */

else return i; /* 找到后返回的是存储位置 */

}

6、插入算法

void Insert( ElementType X, int i, List *PtrL )

{ int j;

if ( PtrL->Last == MAXSIZE-1 ){ /* 表空间已满，不能插入*/

printf(＂表满＂);

return;

}

if ( i < 1 || i > PtrL->Last+2) { /*检查插入位置的合法性*/

printf(＂位置不合法＂);

return;

}

for ( j = PtrL->Last; j >= i-1; j-- )

PtrL->Data[j+1] = PtrL->Data[j]; /*将 ai～ an倒序向后移动*/

PtrL->Data[i-1] = X; /*新元素插入*/

PtrL->Last++; /*Last仍指向最后元素*/

return;

}

7、删除算法

void Delete( int i, List *PtrL )

{ int j;

if( i < 1 || i > PtrL->Last+1 ) { /*检查空表及删除位置的合法性*/

printf (“不存在第%d个元素”, i );

return ;

}

for ( j = i; j <= PtrL->Last; j++ )

PtrL->Data[j-1] = PtrL->Data[j]; /*将 ai+1～ an顺序向前移动*/

PtrL->Last--; /*Last仍指向最后元素*/

return;

}

8、求表长

int Length ( List *PtrL )

{ List *p = PtrL; /* p指向表的第一个结点*/

int j = 0;

while ( p ) {

p = p->Next;

j++; /* 当前p指向的是第 j 个结点*/

}

return j;

}

9、查找

（1）按序号查找: FindKth;

List *FindKth( int K, List *PtrL )

{ List *p = PtrL;

int i = 1;

while (p !=NULL && i < K ) {

p = p->Next;

i++;

}

if ( i == K ) return p;

/* 找到第K个，返回指针 */

else return NULL;

/* 否则返回空 */

}

（2）按值查找: Find

List *Find( ElementType X, List *PtrL )

{

List *p = PtrL;

while ( p!=NULL && p->Data != X )

p = p->Next;

return p;

}

10、插入（在链表的第 i-1(1≤i≤n+1)个结点后插入一个值为X的新结点)

List *Insert( ElementType X, int i, List *PtrL )

{ List *p, *s;

if ( i == 1 ) { /* 新结点插入在表头 */

s = (List *)malloc(sizeof(List)); /*申请、填装结点*/

s->Data = X;

s->Next = PtrL;

return s; /*返回新表头指针*/

}

p = FindKth( i-1, PtrL ); /* 查找第i-1个结点 */

if ( p == NULL ) { /* 第i-1个不存在，不能插入 */

printf(＂参数i错＂);

return NULL;

}else {

s = (List *)malloc(sizeof(List)); /*申请、填装结点*/

s->Data = X;

s->Next = p->Next; /*新结点插入在第i-1个结点的后面*/

p->Next = s;

return PtrL;

}

}

11、删除（删除链表的第 i (1≤i≤n)个位置上的结点)

List *Delete( int i, List *PtrL )

{ List *p, *s;

if ( i == 1 ) { /* 若要删除的是表的第一个结点 */

s = PtrL; /*s指向第1个结点*/

PtrL = PtrL->Next; /*从链表中删除*/

free(s); /*释放被删除结点 */

return PtrL;

}

p = FindKth( i-1, PtrL ); /*查找第i-1个结点*/

if ( p == NULL ) {

printf(“第%d个结点不存在”, i-1); return NULL;

} else if ( p->Next == NULL ){

printf(“第%d个结点不存在”, i); return NULL;

} else {

s = p->Next; /*s指向第i个结点*/

p->Next = s->Next; /*从链表中删除*/

free(s); /*释放被删除结点 */

return PtrL;

}

}

12、链表不具备的特点是 1 。

①可随机访问任一节点 ②插入删除不须要移动元素

③不必事先估计存储空间 ④所需空间与其长度成正比

13、带头结点的单链表head为空的判定条件是 2 。

①head==NULL ②head->next==NULL

③head->next==head ④head!=NULL

14、如果最常用的操作是取第i个结点及其前驱，则采用 4 存储方式最节省时间。

①单链表 ②双链表 ③单循环链表 ④顺序表

第三章 Chapter 3 栈(stacks)和队列（queues）

1、 栈是限定仅能在表尾一端进行插入、删除操作的线性表。

2、 栈的特点是“后进栈的元素先出栈”（last in, first out），故栈又称为后进先出表（LIFO）。

3、 一个栈是一些元素的线形列表，其中元素的插入和删除均在表的同一端进行。插入和删除发生的一端称为栈顶（the top of the stack）。

4、 第一个进栈的元素在栈底，

最后一个进栈的元素在栈顶，

第一个出栈的元素为栈顶元素，

最后一个出栈的元素为栈底元素。

5、 连续栈(Contiguous Stack)的类型定义

#define MaxStack 50

Typedef struct

{datatype stack[MaxStack];

int top;

}Seqstack;

Seqstack *s;

6、 判断栈是否已满？

viod Push(Seqstack *s, datatype x )

{

if (s->top>=MaxStack-1) printf(“ overflow” );

else {

s-> top++;

s->stack[s->top]=x;}

}

7、 判断栈是否为空？

datatype pop(Seqstack *s )

{ if (s->top<0)

{printf(“underflow”); return(NULL);}

return(s->stack[s->top]);

s->top--;

}

8、 返回栈顶元素的值，栈不发生变化。

datatype top(Seqstack *s )

{ if (s->top<0)

{printf(“underflow”); return(NULL);}

return(s->stack[s->top]);

}

9、 链栈（Linked Stack)的类型定义

栈的链式存储结构称为链栈，它是运算受限的单链表，插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。

链栈的类型说明如下：

typedef struct stacknode {

datatype data

struct stacknode *next

}stacknode

10、 链式栈的特点：

链式栈无栈满问题；空间可扩充；插入与删除仅在栈顶处执行；链式栈的栈顶在链头；适合于多栈操作。

11、栈是限定仅能在表的一端进行插入、 删除操作的线性表。

12、栈的元素具有后进先出的特点。

13、栈顶元素的位置由栈顶指针的指示, 进栈、出栈操作要修改栈顶指针。

14、抽象数据类型队列的定义：

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。

15、队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。

16、双端队列：就是限定插入和删除操作在表的两端进行的线性表。

17、链队列结点定义：

typedef struct Qnode

{ QElemType data;

struct QNode *next;

} QNode,*QueuPtr;

18、 队列的顺序存储结构称为顺序队列，在队列的顺序存储结构中，除了用一组地址连续的储存单元依次存放从队头到队尾的元素之外，尚需要附设两个指针front和rear分别指示队列头元素和队列尾元素的位置。

19、 在非空队列中，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。

20、栈的特点是 先进后出 ，队列的特点是 先进后出 。

21、栈和队列的共同特点是只允许在端点处插入和删除元素 。

22、一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 C 。

（A）edcba （B）decba （C）dceab （D）abcde

23、若已知一个栈的进栈序列是p1，p2，p3， … ，pn 。其输出序列为1，2，3，…，n ，若p3=1，则p1为 C 。

（A）可能是2（B）一定是2（C）不可能是2 （D）不可能是3

24、设有一个空栈，栈顶指针为1000H（十六进制，下同），现有输入序列为1、2、3、4、5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH后，输出序列是 3 ，栈顶指针是 8 。

①5、4、3、2、1 ②2、1 ③2、3

④3、4 ⑤1002H ⑥1004H

⑦1005H ⑧1003H

24、一个队列的入队序列是若1，2，3，4，则队列的输出序列是 B 。

（A）4，3，2，1 （B）1，2，3，4

（C）1，4，3，2 （D）3，2，4，1

25、若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别是 B 。

（A）1和5 （B）2和4 （C）4和2 （D）5和1

26、有5个元素，其入栈次序为A、B、C、D、E，在各种可能的出栈次序中，以元素C、D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？

C、D、B、A、E C、D、E、B、A

C、D、B、E、A

第六章 树和二叉树

1、树型结构是一类重要的非线性结构。

2、树的定义：树是n(n>=0)个结点的有限集T，T为空时称为空树，否则它满足如下两个条件：

（1）有且仅有一个特定的称为根的结点；

（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2，T3…Tm，其中每个子集又是一棵树，并称其为根的子树。

3、基本术语

结点——表示树中的元素，包括数据项及若干指向其子树的分支

结点的度(degree)——结点拥有的子树数

叶子(leaf)——度为0的结点

孩子(child)——结点子树的根称为该结点的孩子

双亲(parents)——孩子结点的上层结点叫该结点的~

兄弟(sibling)——同一双亲的孩子

树的度——一棵树中最大的结点度数

结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……

深度(depth)——树中结点的最大层次数

森林(forest)——m(m0)棵互不相交的树的集合

例题:

4、二叉树是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。

二叉树可以是空集合，根可以有空的左子树或空的右子树。

性质1: 在二叉树的第i层上至多有2i-1个结点(i>=1)。

性质2：深度为k的二叉树至多有2k－1个结点（k>=1)。

性质3： 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。

性质4：具有n个结点的完全二叉树的深度为log2n＋1。

性质5： 如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第log2n +1层，每层从左到右)，则对任一结点i（1<=i<=n)，有：

（1）如果i＝1，则结点i无双亲，是二叉树的根；如果i>1，则其双亲是结点i/2 。

（2）如果2i>n，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。

（3）如果2i＋1>n，则结点i无右孩子；否则，其右孩子是结点2i＋1。

一棵深度为k且有2k-1个结点的二叉树称为满二叉树。如：

5、二叉树的存储结构

● 顺序存储结构

define MAX-TREE-SIZE 100

Typedef TelemType SqBiTree[ MAX-TREE-SIZE];

SqBitree bt;

缺点是有可能对存储空间造成极大的浪费。

● 链式存储结构

二叉链式存储结构

typedef struct BiTNode

{ TElemType data;

struct BiTNode *lchild, *rchild;

}BiTNode,*BiTree;

三叉链表

typedef struct node

{ datatype data;

struct node *lchild, *rchild, *parent;

}JD;

6、遍历二叉树

二叉树是由三个基本单元组成：根结点、左子树和右子树。

若限定先左后右，则只有前三种情况，分别称之为先（根）序遍历，中（根）序遍历和后（根）序遍历。

（1）先序遍历算法

若二叉树为空树，则空操作；否则，

● 访问根结点；

● 先序遍历左子树；

● 先序遍历右子树。

void PreOrder（BiTree bt）{/*先序遍历二叉树bt*/

if (bt==NULL) return; /*递归调用的结束条件*/

Visite（bt->data）; /*(1)访问结点的数据域*/

PreOrder（bt->lchild）; /*(2)先序递归遍历bt的左子树*/

PreOrder（bt->rchild）;/*(3)先序递归遍历bt的右子树*/}

例题：

先序遍历序列：A B D C

void preorder(JD *bt)

{ if(bt!=NULL)

{ printf("%d\t",bt->data);

preorder(bt->lchild);

preorder(bt->rchild);

}

}

（2）中序遍历算法

若二叉树为空树，则空操作；否则，

● 先序遍历左子树；

● 访问根结点；

● 先序遍历右子树。

void InOrder（BiTree bt）{/*先序遍历二叉树bt*/

if (bt==NULL) return; /*递归调用的结束条件*/

InOrder（bt->lchild）; /*(2)先序递归遍历bt的左子树*/

Visite（bt->data）; /*(1)访问结点的数据域*/

InOrder（bt->rchild）;/*(3)先序递归遍历bt的右子树*/}

例题：

中序遍历序列：B D A C

（3）后序遍历算法

若二叉树为空树，则空操作；否则，

● 先序遍历左子树；

● 先序遍历右子树；

● 访问根结点。

void PostOrder（BiTree bt）{/*后序遍历二叉树bt*/

if (bt==NULL) return; /*递归调用的结束条件*/

PostOrder（bt->lchild）;/*(1)后序递归遍历bt的左子树*/

PostOrder（bt->rchild）; /*(2)后序递归遍历bt的右子树

Visite（bt->data）; /*(3)访问结点的数据域*/}

例题：

后序遍历序列： D B C A

（4）层次遍历

所谓二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。

层次遍历序列:1 2 3 4 5 6

7、例题：1、

先序序列：A B C D E F G H K

中序序列：B D C A E H G K F

后序序列：D C B H K G F E K

层次序列：A B E C F D G H K

2、

若先序遍历此二叉树，按访问结点的先后次序将结点排列起来，其先序序列为：-+a*b-cd/ef

按中序遍历，其中序序列为：a+b*c-d-e/f

按后序遍历，其后序序列为：abcd-*+ef/ -

8、（1）查询二叉树中某个结点

Status Preorder (BiTree T, ElemType x, BiTree &p) {

// 若二叉树中存在和 x 相同的元素，则 p 指向该结点并

//返回 OK,// 否则返回 FALSE

if (T) {

if (T->data= =x) { p = T; return OK,}

else {

if (Preorder(T->lchild, x, p)） return OK;

else (Preorder(T->rchild, x, p)) return OK;

}//else

}//if

else return FALSE;

}

（2）计算二叉树中叶子结点的个数

int CountLeaf (BiTree T){

//返回指针T所指二叉树中所有叶子结点个数

if (!T ) return 0;

if (!T->lchild && !T->rchild) return 1;

else{

m = CountLeaf( T->lchild);

n = CountLeaf( T->rchild);

return (m+n);

} //else } // CountLeaf

（3）求二叉树的深度(后序遍历)

int Depth (BiTree T ){ // 返回二叉树的深度

if ( !T ) depthval = 0; else {

depthLeft = Depth( T->lchild );

depthRight= Depth( T->rchild );

depthval = 1 + (depthLeft > depthRight ?

depthLeft : depthRight);

}

return depthval;

}

（4）按先序遍历序列建立二叉树

Status CreateBiTree (BiTree &T ){ //按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，构造二叉链表表示的二叉树T

scanf (&ch);

if ( ch==‘ ‘ ) T=NULL; else {

if(!T=(BiTNode *)malloc(sizeof(BiTNode)))) exit (OVERFLOW);

T->data=ch; //生成根结点

CreateBiTree(T->lchild);//构造左子树

CreateBiTree(T->rchild);//构造右子树}

Return OK; }//CreateBiTree

9、遍历二叉树的非递归算法

（1）先序遍历二叉树的非递归算法

void inorder(JD *r)//先序遍历二叉树非递归算法//

{ int i=0; JD *p,*s[M]; p=r;

do {

while(p!=NULL) {

printf("%d\t",p->data);

if (p->rc!=NULL)

s[i++]=p->rc;

p=p->lc;

}

if ( i > 0) p=s[--i];

}while( i>0 || p!=NULL); }

（2）中序遍历二叉树的非递归算法

void inorder(JD *r)//先序遍历二叉树非递归算法//

{ int i=0; JD *p,*s[M]; p=r;

do {

while(p!=NULL) {

{s[i++]=p; p=p->lc;}

if (i>0)

{p=s[--i];

printf("%d\t",p->data);

p=p->lc;

}

if ( i > 0) p=s[--i];

}while( i>0 || p!=NULL); }

（3）后序遍历二叉树的非递归算法

void inorder(JD *r)//先序遍历二叉树非递归算法//

{ int s2[M],b,i=0; JD *p,*s1[M]; p=r;

do {

while(p!=NULL) {

{s1[i-1]=p;s2[i++]=0;p=p->lc;}

while (i>0 && (s2[i-1]=1))

{p=s1[--i]; printf(“%d\t”,p->data ); }

if (i>0)

{p=s[--i];

printf("%d\t",p->data);

p=p->lc;

}

if ( i > 0)

{ s2[i-1]=1; p=s1[i-1]; p=p->rc; }

}while( i>0); }

11、 线索二叉树：以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能在结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域;

Ltag=0 ，lchild 域指示结点的左孩子；Ltag=1， lchild 域指示结点的前驱。

Rtag=0，rchild 域指示结点的右孩子；Rtag=1，rchild 域指示结点的后驱。

以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索，加上线索的二叉树称之为线索二叉树。

（1）先序线索二叉树

（2）中序线索二叉树

（3）后序线索二叉树

12、 树的存储结构

双亲表示法

#define MAX_TREE_SIZE 100

typedef struct PTNode {//结点结构

ElemType data;

int parent; // 双亲位置域

} PTNode;

typedef struct {//树结构

PTNode nodes[MAX_TREE_SIZE];

int r, n; // 根结点的位置和结点个数

} PTree;

孩子表示法

带双亲的孩子链表

孩子兄弟表示法

链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。

typedef struct node

{ datatype data;

struct node *fch, *nsib;

}JD;

13、树和森林与二叉树的转换

加线：在兄弟之间加一连线 。

抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系，

旋转：以树的根结点为轴心，将整树顺时针转45°。

13、 将二叉树转换成树

● 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来.

● 抹线：抹掉原二叉树中双亲与右孩子之间的连线

● 调整：将结点按层次排列，形成树结构

14、森林转换二叉树

（1）将各棵树分别转换成二叉树.

（2）将每棵树的根结点用线相连.

（3）以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构

14、 二叉树转换成森林

抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树.

还原：将孤立的二叉树还原成

15、 树和森林的遍历

树的遍历

两种次序遍历树的方法：一种是先根（次序）遍历树，即先访问树的根结点，然后依次先根遍历根的每棵子树；

一种是后根（次序）遍历，即先依次后根遍历每棵子树，然后访问根结点。

森林的遍历

先序遍历：A B C D E F G H I J

中序遍历：B C D A F E H J I G

16、 赫夫曼树及其应用

例题： w={5, 29, 7, 8, 14, 23, 3, 11}

习题：

1、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法 B 。

（A）正确 （B）错误

2、某二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树一定是 D 。

（A）空或只有一个结点 （B） 完全二叉树

（C）二叉排序树 （D） 高度等于其节点数

3、 深度为5的二叉树至多有C 个结点。

（A）16 （B）32 （C）31 （D）10

4、根据使用频率为5个字符设计的赫夫曼编码不可能是C .

（A）111，110，10，01，00

（B）000，001，010，011，1

（C）100，11，10，1，0

（D）001，000，01，11，10

5、树和二叉树的主要差别是（1） 树的结点个数至少为1，而二叉树的结点个数可以为 0（2）树中结点的最大度数没有限制，而二叉树结点的最大度数为2（3）树的结点无左、右之分，而二叉树的结点右左、右之分。

6、深度为k的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号 。

7、一棵二叉树的第i(i1)层最多有 个结点；一棵有n（n>0）个结点的满二叉树共有 个叶子结点和

个非叶子结点。

8、已知二叉树的先序、中序和后序序列分别如下，其中有一些看不清的字母用*表示，请构造出一棵符合条件的二叉树并画出该二叉树。

● 先序序列是：*BC**FG

● 中序序列是：CB*EAG*

● 后序序列是：*EDB*FA

9、将右图所示的树转化为二叉树，并写出先序遍历，中序遍历和后序遍历的结果。

解：

先序：ABEFGCDHI

中序：EFGBCHIDA

后序：GFEIHDCBA

10、设给定权集w={2，3，4，7，8，9}，试构造关于w的一棵赫夫曼树，并求其加权路径长度WPL。

WPL=(9+7+8)*2+4*3+(2+3)*4=80

第十章　内部排序

1、内排序大致可分为五类：插入排序、交换排序、选择排序、归并排序和分配排序。

2、直接插入排序

● 直接插入的算法实现

void sort(NODE array[],int n)

//待排序元素用一个数组array[ ] 表示，数组有n个元素

{ int i, j;

NODE x; // x 为中间结点变量

for ( i=1; i表示插入次数,共进行n-1次插入

{ x=array[i]; //把待排序元素赋给 x

j=i-1;

while ((j>=0)&& ( x.key

{array[j+1]=array[j]; j--; } // 顺序比较和移动

array[j+1]=x; }

}

例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。它的直接插入排序的执行过程如图7-1所示。

直接插入排序的时间复杂度为O（n2）。

直接插入算法的元素移动是顺序的，该方法是稳定的。

3、希尔排序

希尔排序的时间复杂性在O（nlog2n）和O（n2 ）之间，大致为O（n1.3）。

由于希尔排序对每个子序列单独比较，在比较时进行元素移动，有可能改变相同排序码元素的原始顺序，因此希尔排序是不稳定的。

例如，n=8，数组array[ ]的八个元素分别为：91，67，35，62，29，72，46，57。下面用图10-2给出希尔排序算法的执行过程。

4、 交换排序

1）冒泡排序

冒泡排序的算法实现

void Bubblesort( NODE array[],int n)

{ int i, j, flag; //当flag为0则停止排序

NODE temp;

for ( i=1; i表示趟数，最多n-1趟

{ flag=0; //开始时元素未交换

for ( j=n-1; j>=i; j--)

if (array[j].key发生逆序

temp=array[j];array[j]=array[j-1];array[j-1]=temp;

flag=1; } //交换，并标记发生了交换

if(flag==0) break; }

}

例如，n=6，数组R的六个排序码分别为：17，3，25，14，20，9。下面用图10-3给出冒泡排序算法的执行过程。

冒泡排序算法的时间复杂度为O（n2）。由于其中的元素移动较多，所以属于内排序中速度较慢的一种。

因为冒泡排序算法只进行元素间的顺序移动，所以是一个稳定的算法。

2）快速排序

快速排序（Quick Sorting）是迄今为止所有内排序算法中速度最快的一种。

快速排序的算法实现

void quicksort(NODE array[],int start , int end)

{ int i , j; NODE mid;

if (start>=end) return;

i=start;j=end;mid=array[i];

while (i

{ while (imid.key) j--;

if (i

while (i

if (i一次划分得到基准值的正确位置

array[i]=mid;

quicksort(array,start,i-1); //递归调用左子区间

quicksort(array,i+1,end); }//递归调用右子区间

例如，给定排序码为：（46，55，13，42，94，05，17，70），具体划分如图10-4所示。

快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（log2n），最坏的空间复杂度为O(n)。

快速排序是一种不稳定的排序方法。

5、选择排序

1）直接选择排序

例如，给定n=8，数组R中的8个元素的排序码为：（8，3，2，1，7，4，6，5），则直接选择排序过程如图7-5所示。

直接选择排序的时间复杂度为O(n2)数量级

2）树形选择排序

例如，给定排序码头 50，37，66，98，75，12，26，49，树形选择排序过程见图7-7。

3）堆排序

例如，给定排序码49，38，65，97，76，13，27，70，建立初始堆的过程如图7-8所示。

按层次遍历完全二叉树，得到一个由大到小排列的有序序列：

97，76，70，65，49，38，27，13

每次筛选运算的时间复杂度为O(log2n)，故整个堆排序过程的时间复杂度为O(nlog2n)。

5、 归并排序

例如，给定排序码46，55，13，42，94，05，17，70，二路归并排序过程如图7-10所示。

二路归并排序的时间复杂度为O(nlog2n)。

6、各种内排序方法的比较和选择

1）从时间复杂度比较

从平均时间复杂度来考虑，直接插入排序、冒泡排序、直接选择排序是三种简单的排序方法，时间复杂度都为O(n2)，而快速排序、堆排序、二路归并排序的时间复杂度都为O(nlog2n)，希尔排序的复杂度介于这两者之间。若从最好的时间复杂度考虑，则直接插入排序和冒泡排序的时间复杂度最好，为O(n)，其它的最好情形同平均情形相同。若从最坏的时间复杂度考虑，则快速排序的为O(n2)，直接插入排序、冒泡排序、希尔排序同平均情形相同，但系数大约增加一倍，所以运行速度将降低一半，最坏情形对直接选择排序、堆排序和归并排序影响不大。

2）从空间复杂度比较

归并排序的空间复杂度最大，为O(n)，快速排序的空间复杂度为O(log2n)，其它排序的空间复杂度为O（1）。

3）从稳定性比较

直接插入排序、冒泡排序、归并排序是稳定的排序方法，而直接选择排序、希尔排序、快速排序、堆排序是不稳定的排序方法。

4）从算法简单性比较

直接插入排序、冒泡排序、直接选择排序都是简单的排序方法，算法简单，易于理解，而希尔排序、快速排序、堆排序、归并排序都是改进型的排序方法，算法比简单排序要复杂得多，也难于理解。

8、各种内排序方法的选择

1）从时间复杂度选择

对元素个数较多的排序，可以选快速排序、堆排序、归并排序，元素个数较少时，可以选简单的排序方法。

2）从空间复杂度选择

尽量选空间复杂度为O（1）的排序方法，其次选空间复杂度为O(log2n)的快速排序方法，最后才选空间复杂度为O（n）二路归并排序的排序方法。

3）一般选择规则

● 当待排序元素的个数n较大，排序码分布是随机，而对稳定性不做要求时，则采用快速排序为宜。

● 当待排序元素的个数n大，内存空间允许，且要求排序稳定时，则采用二路归并排序为宜。

● 当待排序元素的个数n大，排序码分布可能会出现正序或逆序的情形，且对稳定性不做要求时，则采用堆排序或二路归并排序为宜。

● 当待排序元素的个数n小，元素基本有序或分布较随机，且要求稳定时，则采用直接插入排序为宜。

● 当待排序元素的个数n小，对稳定性不做要求时，则采用直接选择排序为宜，若排序码不接近逆序，也可以采用直接插入排序。冒泡排序一般很少采用。

第９章 查找

1、顺序表的查找（顺序查找）

顺序查找的缺点是平均查找长度较大，特别是当n很大时，查找效率低。然而，它有很大的优点是：算法简单且适应面广。

2、有序表的查找（折半查找）

算法实现：假设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点，k为给定值，初始时，令low=1，high=n，mid=(low+high)/2

让k与mid指向的记录比较

若k==r[mid].key，查找成功

若k，则high=mid-1

若k>r[mid].key，则low=mid+1

重复上述操作，直至low>high时，查找失败。

例如：已知如下11个数据元素的有序表（05，13，19，21，37，56，64，75，80，88，92），现要查找关键字为21和70 的数据元素。

折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构。

3、查找方法的比较

4、二叉排序树的插入

例 {45，24， 53，45，12，24，90}

5、二叉排序树的删除

5、含有n个结点的二叉排序树的平均查找长度和树的形态有关。

第7章 图

1、图的定义和术语

● 若图中的边是顶点的有序对，则称此图为有向图。

● 若图中的边是顶点的无序对，则称此图为无向图。

● 有向边又称为弧，通常用尖括号表示一条有向边，，w>表示从顶点v到w顶点的一条弧，v称为边的始点（或弧尾），w称为边的终点（或弧头）。

● 有向完全图：具有n(n-1)条弧的有向图称为有向完全图。

● 无向完全图：n个顶点的无向图最大边数是n(n-1)/2，具有n(n-1)/2条边的无向图称为无向完全图。

度的例题：

子图的例题：

总的例题：

● 若G中任意两个顶点都是连通的，则称G为连通图。

● 非连通图的极大连通子图叫做连通分量。

● 强连通图与强连通分量

在有向图中 ，若对于每一对顶点vi和vj， 都存在一条从vi到vj和从vj到vi的路径，则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量。

若给图中每一条边附加一个实数作为权，则该图称为带权图或网。

2、图的存储结构

无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。

数组表示法（邻接矩阵）

网的邻接矩阵可为：

3、储存表示

1）有向图的十字链表表示法

2）无向图的邻接多重表存储表示

4、图的遍历

通常有两条遍历图的路径：

深度优先搜索遍历；

广度优先搜索遍历。

6、 如何拓扑排序

在有向图中选一个没有前驱的顶点且输出之。C1

第二章 homework

1、 填空题：

（1）在顺序表中插入或删除一个元素，平均要移动 表中一半的 元素，具体移动的元素个数与 插入或删除的位置 有关。

（2）线性表有 顺序存储和链式存储 两种存储结构。

（3）顺序表中，逻辑上相邻的元素，其物理位置 必定 相邻。在单链表中，逻辑上相邻的元素，其物理位置 不一定 相邻。

2、 选择题：

（1）在线性表中最常用的操作是存取第i个元素及其前驱的值，采用 A 存储方式最省时间？

A.顺序表 B.带头结点的单向链表

C.带头指针的单向循环链表 D.带头指针的双向循环链表 E.带尾指针的单向循环链表

（2）已知L是无表头结点的单链表，且P结点即不是首元素结点，也不是尾元素结点。按要求在下列语句中选择合适的语句序列。

A．在P结点后插入S结点的语句序列是： D、 A

B．在P结点前插入S结点的语句序列是： GKHDA

C．在表首插入S结点的语句序列是： E、L

D．在表尾插入S结点的语句序列是： KIAF

A. P->next=S; B. P->next=P->next->next; C. P->next=s->next;

D. S->next=P->next; E. S->next=L; F. S->next=NULL;

G. Q=P; H. while(P->next!=Q)P=P->next;

I. while(P->next!=NULL)P=P->next; J. P=Q;

K.P=L; L. L=S; M. L=P;

（3）某线性表中最常用的操作是存取序号为i的元素和在最后进行插入和删除运算，则采用 D 存储方式时间性能最好。

A.双向链表 B.双向循环链表 C.单向循环链表 D.顺序表

（4）下列选项中， D 项是链表不具有的特点。

A.插入和删除运算不需要移动元素

B.所需要的存储空间与线性表的长度成正比

C.不必事先估计存储空间的大小

D.可以随机访问表中的任意元素

3、描述以下三个概念的区别：头指针，头结点，首元素结点(略)。

4、已知顺序表L递增有序，编写一个算法，将X插入到线性表的适当位置上，以保持线性表的有序性。

Void inserX(Seqlist *L,Elemtype x)

{

int i;

i=L->length-1;

while(i>=0 && xelem[i])

{L->elem[i+1]=L->elem[i];

i--;

}

L->elem[i]=x;

L->length++;}

5、编写一个算法，从顺序表中删除自第i个元素开始的k个元素。

Void deletexfromatob(Seqlist *L,int i,int k)

{ int j;

for(j=i+k;jlength;j++;i++)

{

L->elem[i]=L->elem[j];

}

L->length=L->length-k;

}

6、已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试编写一个高效算法，删除表中所有大于minK且小于maxK的元素（若表中存在这样的元素），分析你的算法的时间复杂度（注意：minK和maxK是给定的两个参变量，它们的值为任意的整数）

Void DeleteX(linklist *head,int mink,int maxk)

{

Linklist *p,*q,*s;

q=head;

p=head->next;

while(p!=NULL)

{

While(p!=NULL && p->data < mink)//如果p所指向的结点的值小于mink，则继续往下找，q指向p的前驱结点

{

q=p;

p=p->next;

}

If(p->data > mink && p->data

{

　　If(p->next==NULL)//如果删除的是最后一个结点，要作特殊处理

q->next=NULL;

else

{

q->next=p->next;

s=p;

p=p->next;

free(s);

}

}

}

}

7、试分别以不同的存储结构实现线性表的就地逆值的算法，即在原表的存储空间中将线性表 （a1,a2,…,an）逆置为(an,an-1,…,a1)。

（1）以顺序表作存储结构，设线性表存于a[1:arrsize]的前elenum个分量中。

Void reverseqlist(Seqlist *L)

{int i;

int temp;

for(i=0;ilength/2;i++)

{

temp=L->elem[i];

L->elem[i]=L->elem[L->length-i-1];

L->elem[L->length-i-1]=temp;

}

}

（2）以单链表作存储结构。

Void reverselinklist(linklist *head)

{

Linklist *p,*q;

p=head->next;

head->next=NULL;

while(p->next!=NULL)

{

q=p->next;

p->next=head->next;

head->next=p;

p=q;

}

}

8、实习题：若干城市的信息存入一个带头结点的单链表，结点中的城市信息包括城市名、城市的位置坐标。

要求:

(1) 给定一个城市名，返回其坐标位置。

(2) 给定一个坐标位置P和一个距离D，返回所有距P的距离小于等于D的城市。

//在Ｃ语言下面可以实现的完整的程序

#include"stdlib.h"

#include"stdio.h"

#include"string.h"

#include "math.h"

#define NULL 0

typedef struct node

{

char city_na[10];

int x;

int y;

}city;

typedef struct citynode

{

city ct;

struct citynode *next;

}citylist;

void creatcitylist(citylist *head)

{

citylist *p,*r;

int i,n;

r=head;

printf("please input the city's number:");

scanf("%d",&n);

for(i=1;i<=n;i++)

{

p=(citylist *)malloc(sizeof(citylist));

printf("\nplease input city's name:");

scanf("%s",&p->ct.city_na);

printf("\nplease input the city's position:");

scanf("%d",&p->ct.x);

scanf("%d",&p->ct.y);

p->next=r->next;

r->next=p;

r=p;

}

}

void outputcitylist(citylist *head)

{

citylist *p;

p=head->next;

printf("\nthe citylist is:\n ");

while(p!=NULL)

{

printf("%s\n",p->ct.city_na);

printf("%2d%3d\n",p->ct.x,p->ct.y);

p=p->next;

}

}

void searchcity(citylist *head)

{

citylist *p;

char str[10];

p=head->next;

printf("\nplease input the city that you want to search:");

scanf("%s",&str);

while(p!=NULL)

{

if(strcmp(p->ct.city_na,str)==0)

{

printf("\nthis city's position is:%2d%3d",p->ct.x,p->ct.y);

}

p=p->next;

}

}

void returncity(citylist *head)

{

int x,y,d;

int dis;

citylist *p;

p=head->next;

printf("\nplease input the position:");

scanf("%d%d",&x,&y);

printf("\nplease input the distance:");

scanf("%d",&d);

while(p!=NULL)

{

dis=sqrt((p->ct.x)*(p->ct.x)+(p->ct.y)*(p->ct.x))-sqrt(x*x+y*y);//computer the distance

if(dis < d)

{ printf("\nthe city that distance is maller than d is:%s ",p->ct.city_na);

}

p=p->next;

}

}

void main()

{

citylist *head;

head=(citylist *)malloc(sizeof(citylist));

head->next=NULL;

//creating citylist

creatcitylist(head);

outputcitylist(head);

//searching city

searchcity(head);

//Having known a position and distance d,search the city that distance is maller than d

returncity(head);

}

实验内容

一、顺序存储结构

1．顺序表基本操作的实现

当我们要在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若要删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。

2．两个线性表的合并运算

已知线性表La和Lb，求La=La∩Lb。

3.已知两个有序表La和Lb,把两个有序表合并成仍然有序的线性表Lc.

代码：

#include"stdlib.h"

#include"stdio.h"

#define Maxsize 50

//线性表顺序存储的结构定义

typedef struct listnode

{

int computer[Maxsize];//假设线性表中存放的是学校每年计算机的拥有量

int length;//线性表的长度

}sqlist;

void initlist(sqlist *la) //初始化线性表

{

int i=0;

int x;

scanf("%d",&x);

while(x!=0)

{

la->computer[i]=x;

i=i+1;

scanf("%d",&x);

}

la->length =i;

}

void outputlist(sqlist *la)//输出线性表中的数据元素

{

int i;

printf("\nthe list is:\n");

for(i=0;ilength;i++)

{

printf("%5d",la->computer[i]);

}

printf("\n");

printf("\n列表的长度:%d\n",la->length);

printf("\n");

}

void Insert(sqlist *la,int i,int x)// 已知线性表la,线性表la已经存在，在线性表的第i个位置插入一个数据元素x,线性表的长度加1.

{

if (i>la->length+1) printf("Error!\n");

int j;

i=i-1;

for(j=la->length-1;j>=i;j--)

{

la->computer[j+1]=la->computer[j];

}

la->computer[i]=x;

la->length=la->length+1;

}

void Delete(sqlist *la,int i)// 删除线性表第i个位置上的数据元素，线性表的长度减1

{

int j;

if (i<1 || i>la->length) printf("Error!");

for(j=i;jlength;j++)

la->computer[j-1]=la->computer[j];

la->length=la->length-1;

}

int Select1(sqlist *la,int i)// //线性表la已经存在，读取第i个位置上的元素

{

return la->computer[i-1];

}

int Select2(sqlist *la,int e)// 线性表la已经存在，在线性表中查找值等于e的数据元素，如果存在这样的元素，则返回它的位置，如果不存在，则返回0.

{

int i,flag=0;

for(i=0;ilength;i++)

{

if (la->computer[i]==e)

{

flag=1;

return i+1;

}

}

if (flag==0)

return 0;

}

void Union(sqlist *la,sqlist *lb)//两个线性表的合并运算

{

int i,e,j;

for(i=1;i<=lb->length;i++)

{

e=Select1(lb,i);

j=Select2(la,e);

if(j==0)

{

la->computer[la->length]=e;

la->length=la->length+1;

}

}

}

void unionSort(sqlist *la,sqlist *lb,sqlist *lc)//已知两个有序表La和Lb,把两个有序表合并成仍然有序的线性表Lc.

{

int i,j=0,t;

for(i=0;ilength;i++)

{

lc->computer[i]=la->computer[i];

lc->length=la->length;

}

for(i=la->length;i<(la->length+lb->length);i++)

{

lc->computer[i]=lb->computer[j];

lc->length=lc->length+1;

j++;

}

for(i=0;ilength;i++)

for(j=i+1;jlength;j++)

{

if (lc->computer[i]>lc->computer[j])

{t=lc->computer[i];lc->computer[i]=lc->computer[j];lc->computer[j]=t;}

}

}

int main()

{

sqlist la,lb,lc;

printf("请输入la的值 :\n");

initlist(&la);

printf("输出la的值 :\n");

outputlist(&la);

printf("请输入lb的值:\n");

initlist(&lb);

printf("输出lb的值 :\n");

outputlist(&lb);

int choiceNumber;

char whetherContinue='Y';

while(whetherContinue!='N' && whetherContinue!='n')

{

printf("********************************************\n");

printf("实现la中的功能:\n");

printf("1.插入\n");

printf("2.删除\n");

printf("3.输入你想选择的位置\n");

printf("4. 输入你想选择的值\n");

printf("5.合并la和lb\n");

printf("6.合成一个新的线性表:\n");

printf("请输入你要执行的功能: ");

scanf("%d",&choiceNumber);

getchar();

printf("********************************************\n");

switch(choiceNumber)

{

case 1:

{

int insertPosition,insertValue;

printf("请输入所插入的位置和值:\n");

scanf("%d,%d",&insertPosition,&insertValue);

getchar();

Insert(&la,insertPosition,insertValue);outputlist(&la);break;

}

case 2:

{

int deletePosition;

printf("输入你所删除的位置:\n");

scanf("%d",&deletePosition);

getchar();

Delete(&la,deletePosition);outputlist(&la);break;

}

case 3:

{

int selectPosition;

printf("输入你想选择的位置:\n");

scanf("%d",&selectPosition);

getchar();

printf("值是:%d\n", Select1(&la,selectPosition));

break;

}

case 4:

{

int selectValue;

printf("输入你想选择的值:\n");

scanf("%d",&selectValue);

getchar();

printf("位置是:%d\n",Select2(&la,selectValue));break;

}

case 5:Union(&la,&lb);outputlist(&la);break;

case 6: unionSort(&la,&lb,&lc);outputlist(&lc);break;

default:printf("Error!\n");

}

printf("Continue? Y/N:");

scanf("%c",&whetherContinue);

getchar();

}

return 0;

}

二、链式储存结构

1、单链表的基本操作的实现：建表、插入、删除、查找。

当我们要在线性表的链式存储结构上的第i个位置上插入一个元素时，只需修改第 i-1个元素结点的指针和新元素结点指针便可完成插入；若要删除第i个元素时，也只需修改第 i-1个元素的指针就行。

2、两个线性表的合并运算

已知线性表La和Lb，求La=La∩Lb。

3、已知两个有序表La和Lb,把两个有序表合并成仍然有序的线性表Lc.

源程序代码：

#include

#include

#define Null 0

//链式存储的数据结构的定义

typedef struct node{

int data;

struct node *next;

} NODE;

NODE *Create()////用头插法建立带头节点的单链表

{

NODE *p,*head;

int x;

head=(NODE *)malloc(sizeof(NODE));

head->next=NULL;

printf("输入数据,-1 结束输入!\n");

scanf("%d",&x);

while(x!=-1){

p=(NODE *)malloc(sizeof(NODE));

p->data=x;

p->next=head->next;

head->next=p;

scanf("%d",&x);

}

return(head);

}

/*****************输出单链表各元素的值*************************/

void Output(NODE *head){

NODE *p;

p=head;

printf("the List is...\n");

while(p->next!=NULL){

printf("->%d",p->next->data);

p=p->next;

}

// printf("\nThe LinkList ended!\n");

}

/****************求单链表的长度（元素的个数）**************************/

int ListLen(NODE *head){

NODE *p=head;

int i=0;

while(p){

i++;

p=p->next;

}

return i-1;

}

/******************查找单链表中第i个元素的值************************/

int Get(NODE *head,int i){

NODE *p=head;

int j=0;

while(p && j

p=p->next;

j++;

}

if(!p || j>i) return -1;

else return p->data;

}

/*****************删除单链表的第i个位置上的元素***********************/

void Delete(NODE *head,int i){

if(i>ListLen(head) || i<=0)

printf("Error!\n");

else{

int j=0;

NODE *p=head,*q;

while(p && j

p=p->next;

j++;

}

q=(NODE *)malloc(sizeof(NODE));

q=p;

p=p->next;

q->next=p->next;

}

}

/*****************在单链表的第i个位置插入元素e***********************/

void Insert(NODE *head,int i,int e){

if(i>=(ListLen(head)+2) || i<=0)

printf("Error!\n");

else{

int j=0;

NODE *p=head,*q;

while(p && j

p=p->next;

j++;

}

q=(NODE *)malloc(sizeof(NODE));

q->data=e;

q->next=p->next;

p->next=q;

}

}

/*****************输入你要查找的位置***********************/

int Select(NODE *head,int e){

NODE *p=head;

int j=0;

while(p && p->data!=e){

p=p->next;

j++;

}

if(!p) return 0;

else return j;

}

/*****************合并两个表***********************/

NODE *Union(NODE *la,NODE *lb){

int i,j,k,l;

for(i=1;i<=ListLen(lb);i++){

k=Get(lb,i);

j=Select(la,k);

if(j==0){

l=ListLen(la);

Insert(la,l+1,k);

}

}

return la;

}

/*****************合并两个表构建一个新表***********************/

NODE *SortedUnion(NODE *la,NODE *lb){

int i,j,k,l=1;

NODE *p;

for(i=1;i<=ListLen(lb);i++){

k=Get(lb,i);

j=Select(la,k);

if(j==0){

p=la;

p=p->next;

while(p && (p->data)

p=p->next;

l++;

}

Insert(la,l,k);l=1;

}

}

return la;

}

int main(){

NODE *la,*lb,*lc=NULL;

la=Create();

Output(la);

printf("\n");

int choiceNumber;

char whetherContinue='Y';

while(whetherContinue!='N' && whetherContinue!='n')

{

printf("********************************************\n");

printf("选择你要执行的操作:\n");

printf("1.删除\n");

printf("2.插入\n");

printf("3.查询的位置\n");

printf("4.查询的值\n");

printf("5.la表和Lb表合并\n");

printf("6.la表和Lb表合成一个新表:\n");

printf("输入你要执行的操作: ");

scanf("%d",&choiceNumber);

getchar();

printf("********************************************\n");

switch(choiceNumber)

{

case 1:

{

int deletePosition;

printf("输入你要删除的位置:\n");

scanf("%d",&deletePosition);

getchar();

Delete(la,deletePosition);Output(la);

break;

}

case 2:

{

int insertPosition,insertValue;

printf("输入你要插入的位置和值:\n");

scanf("%d,%d",&insertPosition,&insertValue);

getchar();

Insert(la,insertPosition,insertValue);Output(la);break;

}

case 3:

{

int selectPosition;

printf("输入你要查询的位置:\n");

scanf("%d",&selectPosition);

getchar();

printf("The value is:%d\n", Get(la,selectPosition));

break;

}

case 4:

{

int selectValue;

printf("输入你要查询的值:\n");

scanf("%d",&selectValue);

getchar();

printf("The Position is:%d\n",Select(la,selectValue));break;

}

case 5:{printf("Input the Lb List:\n");

lb=Create();

Union(la,lb);

Output(la);break;}

case 6: {

printf("Input the value of Lb :\n");

lb=Create();

SortedUnion(lc,lb);

printf("the New Sorted List is:");

Output(lc);break;

}

default:printf("Error!\n");break;

}

printf("\nContinue? Y/N:");

scanf("%c",&whetherContinue);

getchar();

}

return 0;

}

三、二叉树的递归与非递归

1．树型结构是一种非常重要的非线性结构。树在客观世界是广泛存在的，在计算机领域里也得到了广泛的应用。在编译程序里，也可用树来表示源程序的语法结构，在数据库系统中，数形结构也是信息的重要组织形式。

2．节点的有限集合（N大于等于0）。在一棵非空数里：

（1）、有且仅有一个特定的根节点；

（2）、当N大于1时，其余结点可分为M（M大于0）个互不相交的子集，其中每一个集合又是一棵树，并且称为根的子树。树的定义是以递归形式给出的。

3．二叉树是另一种树形结构。它的特点是每个结点最多有两棵子树，并且，二叉树的子树有左右之分，其次序不能颠倒。

4．二叉树的结点存储结果示意图如下：

二叉树的存储（以五个结点为例）：

实验内容：

1、 如下二叉树：

为了便于在建立二叉树的时候递归的返回，在其先序遍历序列中要加入‘#’号表示结束。

例如，上面的二叉树的先序遍历的序列为：

A B D # G # ##CE##F##

已知以下二叉树的存储结构类型，

typedef struct node

{ int data;

stuuct node *lchild, *rchild;

} bitree;

InitiatTree() {root=NULL;}//初始建立二叉树为空

void CreateBTree(char* a); //根据存于字符数组a的二叉树广义表建立对应的二叉树存储结构

void TraverseBTree(bitree *root); //按任一种遍历（分别用递归和非递归）次序输出二叉树中的所有结点

int BTreeDepth(bitree *root);//求二叉树的深度

int BTreeCount(bitree *root);//求二叉树中所有结点数

int BTreeLeafCount(bitree *root);//求二叉树中所有叶子结点数

void PrintBTree(bitree *root);//按照二叉树的一种表示方法（广义表）输出整个二叉树

main()

{ bitree *root; //定义二叉树

int n,leaf;//定义二叉树的所有节点数和叶子节点数

int h;//定义二叉树的深度

………

………

………

}

源程序代码：

#include

#include

struct BiTree//二叉树的存储结构类型

{

char data;

struct BiTree* lChild;

struct BiTree* rChild;

};

struct NODE{

struct BiTree* BiNode;

int flag;

};

BiTree* CreateBiTree()//二叉树建立对应的二叉树存储结构

{

BiTree *T;

char ch;

scanf("\n%c",&ch);

if(ch=='#') T=NULL;

else{

T=(BiTree *)malloc(sizeof(BiTree));

T->data=ch;

T->lChild=CreateBiTree();

T->rChild=CreateBiTree();

}

return T;

}

void PreOrderTraverse(BiTree *T)

{

if(T)

{

printf("%c ",T->data);

PreOrderTraverse(T->lChild);

PreOrderTraverse(T->rChild);

}

}

void MidOrderTraverse(BiTree *T)

{

if(T)

{

MidOrderTraverse(T->lChild);

printf("%c ",T->data);

MidOrderTraverse(T->rChild);

}

}

void LastOrderTraverse(BiTree *T)

{

if(T)

{

LastOrderTraverse(T->lChild);

LastOrderTraverse(T->rChild);

printf("%c ",T->data);

}

}

int LeafNum(BiTree *T)

{

int m,n;

if(!T) return 0;

if(!T->lChild && !T->rChild) return 1;

else{

m=LeafNum(T->lChild);

n=LeafNum(T->rChild);

}return (m+n);

}

int depthBiTree(BiTree *T)

{

int depthLeft,depthRight,k;

if(!T) return 0;

else{

depthLeft=depthBiTree(T->lChild);

depthRight=depthBiTree(T->rChild);

k=depthLeft>depthRight ? depthLeft:depthRight;

}

return k+1;

}

int NodeNum(BiTree *T)

{

int leftNode,rightNode,k;

if(!T) return 0;

else{

leftNode=NodeNum(T->lChild);

rightNode=NodeNum(T->rChild);

k=leftNode+rightNode;

}

return k+1;

}

////////////递归非递归分割线/////////////////////////////////////

void PreOrderTraverse_2(BiTree *T)

{

int i=0;

BiTree *s[100],*p=T;

do{

while(p!=NULL){

printf("%c ",p->data);

if(p->rChild!=NULL)

s[i++]=p->rChild;

p=p->lChild;

}if(i>0) p=s[--i];

}while(p!=NULL || i>0);

}

void MidOrderTraverse_2(BiTree *T){

int i=0;

BiTree *s[100],*p=T;

while(p!=NULL || i>0){

while(p!=NULL ){

s[i++]=p;

p=p->lChild;

}

if(i>0){

p=s[--i];

printf("%c ",p->data);

p=p->rChild;

}

}

}

void LastOrderTraverse_2(BiTree *T){

NODE *q,*temp,*s[100];

BiTree *p=T;

int i=0;

while(p!=NULL || i>0){

while(p!=NULL){

q=(NODE *)malloc(sizeof(NODE));

q->BiNode=p;

q->flag=1;

s[i++]=q;

p=p->lChild;

}

if(i>0){

temp=s[--i];

if(temp->flag==1){

temp->flag=0;

s[i++]=temp;

p=temp->BiNode->rChild;

}

else{

printf("%c ",temp->BiNode->data);

p=NULL;

}

}

}

}

int LeafNum_2(BiTree *T){

if(!T) return 0;

else{

if(!T->lChild && !T->rChild)

return 1;

else{

BiTree *s[100],*p=T;

int i=0,j=0;

do{

while(p!=NULL){

if(!p->lChild && !p->rChild) j++;

if(p->rChild!=NULL)

s[i++]=p->rChild;

p=p->lChild;

}if(i>0) p=s[--i];

}while(p!=NULL || i>0);

return j;

}

}

}

int NodeNum_2(BiTree *T){

int i=0,j=0;

if(!T) return 0;

else{

if(!T->lChild && !T->rChild) return 1;

else{

BiTree *s[100],*p=T;

do{

while(p!=NULL){

j++;

if(p->rChild!=NULL)

s[i++]=p->rChild;

p=p->lChild;

}if(i>0) p=s[--i];

}while(p!=NULL || i>0);

return j;

}}

}

int main()

{

BiTree *T;

printf("前序遍历输入此二叉树的结点:\n");

T=CreateBiTree();

char ContinueOrNot='Y';

while(ContinueOrNot !='n' && ContinueOrNot !='N' ){

int ChoiceNum;

printf("\n********************************************\n");

printf("1、前序遍历二叉树\n");

printf("2、中序遍历二叉树\n");

printf("3、后序遍历二叉树\n");

printf("4、求二叉树的所有结点个数\n");

printf("5、求二叉树的叶子结点个数\n");

printf("6、求二叉树的深度\n");

printf("\n********************************************\n");

printf("输入选项：");

scanf("%d",&ChoiceNum);getchar();

switch(ChoiceNum){

case 1:{

printf("\n递归算法 ：");PreOrderTraverse(T);

printf("\n非递归算法：");PreOrderTraverse_2(T);

break;

}

case 2:{

printf("\n递归算法 ：");MidOrderTraverse(T);

printf("\n非递归算法：");MidOrderTraverse_2(T);

break;

}

case 3:{

printf("\n递归算法 ：");LastOrderTraverse(T);

printf("\n非递归算法：");LastOrderTraverse_2(T);

break;

}

case 4:{

printf("递归算法算得此树的结点个数为 ：%d\n",NodeNum(T));

printf("非递归算法算得此树的结点个数为：%d\n",NodeNum_2(T));

break;

}

case 5:{

printf("递归算法算得此树的叶子结点个数为 ：%d\n",LeafNum(T));

printf("非递归算法算得此树的叶子结点个数为：%d\n",LeafNum_2(T));

break;

}

case 6:{

printf("递归算法算得此树的深度为 ：%d\n",depthBiTree(T));

printf("非递归算法算得此树的叶子结点个数为：%d\n",LeafNum_2(T));

break;

}

default:printf("错误选项！\n");break;

}

printf("\n是否继续？Y/N:");

scanf("%c",&ChoiceNum);getchar();

}

return 0;

}

四、查询

查找和排序是数据处理中使用频率极高的重要运算，几乎在任何一个计算机系统软件和应用软件中都会涉及到。我们把同一数据类型的数据元素构成的集合称为查找表，把查找表中某个可以标识一个数据元素的数据项的值称为关键字。

当问题涉及的数据量大的时候，常常要求使用效率较高的查找方法，如折半查找法，这往往要求先对查找表中的记录进行排序。

源程序代码：

#include

#include

#include

typedef struct student

{

int num;

char name[20];

char sex[5];

int age;

int grade;

} StuNODE; /*定义学生记录的结构*/

StuNODE stu[10]={{2011140157,"王 琴","女",21,98},{2011140149,"刘 耀","男",22,85},{2011140164,"金文艳","女",21,90},{2011140135,"彭孟盛","男",22,96},{2011140158,"马梅艳","女",20,88},

{2011140101,"刘 健","女",20,97},{2011140101,"郭昭亁","男",24,95},{2011115123,"李绍刚","男",24,89},{2011140144,"邰 燕","女",22,96},{2011140134,"邓 锐","女",22,89}};

/*顺序查找算法的定义*/

int seqSearch(StuNODE stu[],int n,int key)

{

int i=0;

while(i

i++;

if(i>=n)

return -1;//输入key值，如果没有找到与key匹配，返回，否则返回i值

else return i;

}

/*冒泡排序*/

void BubbleSort(StuNODE stu[],int n)

{

int i,j;

StuNODE temp;

for(i=0;i

{for(j=n-1;j>i;j--)

{

if(stu[j].num 进行交换

{

temp.num =stu[j].num;//把stu[j].num复制给temp.num

strcpy(temp.name,stu[j].name);

strcpy(temp.sex,stu[j].sex);

temp.age=stu[j].age;

temp.grade=stu[j].grade;

stu[j].num =stu[j-1].num;

strcpy(stu[j].name,stu[j-1].name);//把stu[j-1].name字符串复制stu[j].name

strcpy(stu[j].sex,stu[j-1].sex);

stu[j].age=stu[j-1].age;

stu[j].grade=stu[j-1].grade;

stu[j-1].num =temp.num;

strcpy(stu[j-1].name,temp.name);

strcpy(stu[j-1].sex,temp.sex);

stu[j-1].age=temp.age;

stu[j-1].grade=temp.grade;//把temp.grade复制给stu[j-1].grade

}

}

}

}

/*折半查找*/

int BinSearch(StuNODE stu[],int n,int key)

{

int low=0,high=n-1,mid,count=0;

while(low<=high)

{

mid=(low+high)/2;//折半查找，取出中间值

printf("第%d次查找：在[%d,%d]中找到元素stu[%d]:%d\n",++count,low,high,mid,stu[mid].num);

if(stu[mid].num ==key)//如果输入的学号等于中间值mid的值，返回mid的值

return mid;

if(stu[mid].num > key)//如果输入的学号大于中间值mid的值，从左边查找

high=mid-1;

else

low=mid+1;//否则从右边查找

}

return -1;

}

/*主控函数*/

void main()

{

StuNODE *p;

int n=10;

int key,sResult;

printf("NO. Name Sex age grade\n");

for(p=stu;p

printf("%-8d %-10s %6s%10d%8d\n",p->num,p->name,p->sex,p->age,p->grade);//输出所有学生信息

printf("1、顺序查找：\n");

printf("请输入要查询的学生学号：\n");

scanf("%d",&key);//输入学号

sResult=seqSearch(stu,n,key);//调用seqSearch函数，查找学生表中的学号

if(sResult<0)

printf("没有学号为%d的学生\n",key);//如果找不到该学号，打印没有学号为这个的学生

else

{

printf("\n学号为%d的学生为：\n",key);//否则打印该学号的学生信息

printf("%-8d %-10s %6s%10d%8d\n",stu[sResult].num,stu[sResult].name,stu[sResult].sex,stu[sResult].age,stu[sResult].grade);

//输出所有学生信息

}

printf("2、按任意健，开始冒泡排序：\n");

printf("\n初始序列：\n");

printf("NO. Name Sex age grade\n");

for(p=stu;p

printf("%-8d %-10s %6s%10d%8d\n",p->num,p->name,p->sex,p->age,p->grade);

BubbleSort(stu,n);//BubbleSort函数，执行冒泡排序

printf("\n冒泡排序后的结果序列为：\n");

printf("NO. Name Sex age grade\n");

for(p=stu;p

printf("%-8d %-10s %6s%10d%8d\n",p->num,p->name,p->sex,p->age,p->grade);

printf("3、二分查找：\n");

printf("请输入要查询的学生的学号：\n");

scanf("%d",&key);

sResult=BinSearch(stu,n,key);//调用BinSearch函数，执行折半查找

if(sResult<0)

printf("没有学号为%d的学生\n",key);

else

{

printf("\n学号为%d的学生为：\n",key);

printf("%-8d %-10s %6s%10d%8d\n",stu[sResult].num,stu[sResult].name,stu[sResult].sex,stu[sResult].age,stu[sResult].grade);

}

}

本文来源：https://www.2haoxitong.net/k/doc/f53ae3f9a1c7aa00b52acb79.html