=NULL>&&>
{
p=p->next;
j++;
}
returnp;
}
3.
单链表的插入
链表插入的核心语句：
Step1：
s->next=p->next;
Step2：
p->next=s；
6.单链表的删除
删除动作的核心语句〔要借助辅助指针变量q：
q=p->next;//首先保存b的指针,靠它才能找到c；
p->next=q->next;//将a、c两结点相连,淘汰b结点；
free；//彻底释放b结点空间
7.双向链表的插入操作：
设p已指向第i元素,请在第i元素前插入元素x：
①ai-1的后继从ai<指针是p>变为x〔指针是s>:
s->next=p;p->prior->next=s;
②ai的前驱从ai-1<指针是p->prior>变为x<指针是s>;
s->prior=p->prior;p->prior=s;
8.双向链表的删除操作：
设p指向第i个元素,删除第i个元素
后继方向：
ai-1的后继由ai<指针p>变为ai+1<指针p->next>;
p->prior->next=p->next;
前驱方向：
ai+1的前驱由ai<指针p>变为ai-1<指针p->prior>;
p->next->prior=p->prior;
◆数组的逻辑结构定义及存储
数组：
由一组名字相同、下标不同的变量构成
N维数组的特点：
n个下标,每个元素受到n个关系约束
一个n维数组可以看成是由若干个n－1维数组组成的线性表。
存储：
事先约定按某种次序将数组元素排成一列序列,然后将这个线性序列存入存储器中。
在二维数组中,我们既可以规定按行存储,也可以规定按列存储。
设一般的二维数组是A[c1..d1,c2..d2],
则行优先存储时的地址公式为：
二维数组列优先存储的通式为：
◆稀疏矩阵〔含特殊矩阵的存储及运算。
稀疏矩阵：
矩阵中非零元素的个数较少〔一般小于5%
学习重点：
◆线性表的逻辑结构,指线性表的数据元素间存在着线性关系。
在顺序存储结构中,元素存储的先后位置反映出这种线性关系,而在链式存储结构中,是靠指针来反映这种关系的。
◆顺序存储结构用一维数组表示,给定下标,可以存取相应元素,属于随机存取的存储结构。
◆链表操作中应注意不要使链意外"断开"。
因此,若在某结点前插入一个元素,或删除某元素,必须知道该元素的前驱结点的指针。
◆掌握通过画出结点图来进行链表〔单链表、循环链表等的生成、插入、删除、遍历等操作。
◆数组〔主要是二维在以行序/列序为主的存储中的地址计算方法。
◆稀疏矩阵的三元组表存储结构。
◆稀疏矩阵的十字链表存储方法。
补充重点：
1.每个存储结点都包含两部分：
数据域和指针域<链域>
2.在单链表中,除了首元结点外,任一结点的存储位置由其直接前驱结点的链域的值指示。
3.在链表中设置头结点有什么好处？
头结点即在链表的首元结点之前附设的一个结点,该结点的数据域可以为空,也可存放表长度等附加信息,其作用是为了对链表进行操作时,可以对空表、非空表的情况以及对首元结点进行统一处理,编程更方便。
4.如何表示空表？
〔1无头结点时,当头指针的值为空时表示空表；
〔2有头结点时,当头结点的指针域为空时表示空表。
5.链表的数据元素有两个域,不再是简单数据类型,编程时该如何表示？
因每个结点至少有两个分量,且数据类型通常不一致,所以要采用结构数据类型。
6.sizeof——计算变量x的长度〔字节数；
malloc—开辟m字节长度的地址空间,并返回这段空间的首地址；
free
——释放指针p所指变量的存储空间,即彻底删除一个变量。
7.链表的运算效率分析：
〔1查找
因线性链表只能顺序存取,即在查找时要从头指针找起,查找的时间复杂度为O。
〔2插入和删除
因线性链表不需要移动元素,只要修改指针,一般情况下时间复杂度为O<1>。
但是,如果要在单链表中进行前插或删除操作,因为要从头查找前驱结点,所耗时间复杂度将是O。
例：
在n个结点的单链表中要删除已知结点*P,需找到它的前驱结点的地址,其时间复杂度为O〔n
8.顺序存储和链式存储的区别和优缺点？
顺序存储时,逻辑上相邻的数据元素,其物理存放地址也相邻。
顺序存储的优点是存储密度大,存储空间利用率高；缺点是插入或删除元素时不方便。
链式存储时,相邻数据元素可随意存放,但所占存储空间分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针。
链式存储的优点是插入或删除元素时很方便,使用灵活。
缺点是存储密度小,存储空间利用率低。
◆顺序表适宜于做查找这样的静态操作；
◆链表宜于做插入、删除这样的动态操作。
◆若线性表的长度变化不大,且其主要操作是查找,则采用顺序表；
◆若线性表的长度变化较大,且其主要操作是插入、删除操作,则采用链表。
9.判断：
"数组的处理比其它复杂的结构要简单",对吗？
答：
对的。
因为——
①数组中各元素具有统一的类型；
②数组元素的下标一般具有固定的上界和下界,即数组一旦被定义,它的维数和维界就不再改变。
③数组的基本操作比较简单,除了结构的初始化和销毁之外,只有存取元素和修改元素值的操作。
10.三元素组表中的每个结点对应于稀疏矩阵的一个非零元素,它包含有三个数据项,分别表示该元素的行下标、列下标和元素值。
11.写出右图所示稀疏矩阵的压缩存储形式。
解：
介绍3种存储形式。
法1：
用线性表表示：
〔<1,2,12>,<1,3,9>,<3,1,-3>,<3,5,14>,
<4,3,24>,<5,2,18>,<6,1,15>,<6,4,-7>
法2：
用十字链表表示
用途：
方便稀疏矩阵的加减运算
方法：
每个非0元素占用5个域
法3：
用三元组矩阵表示：
稀疏矩阵压缩存储的缺点：
将失去随机存取功能
代码：
1.用数组V来存放26个英文字母组成的线性表〔a,b,c,…,z,写出在顺序结构上生成和显示该表的C语言程序。
charV[30];
voidbuild<>//字母线性表的生成,即建表操作
{
inti;
V[0]='a';
for
V[i]=V[i-1]+1;
}
voiddisplay<>//字母线性表的显示,即读表操作
{
inti;
for
printf<"%c",v[i]>;
printf<"\n">;
}
voidmain//主函数,字母线性表的生成和输出
{
n=26;//n是表长,是数据元素的个数,而不是V的实际下标
build<>;
display<>;
}
第三章栈和队列
内容提要：
◆从数据结构角度来讲,栈和队列也是线性表,其操作是线性表操作的子集,属操作受限的线性表。
但从数据类型的角度看,它们是和线性表大不相同的重要抽象数据类型。
◆栈的定义及操作。
栈是只准在一端进行插入和删除操作的线性表,该端称为栈的顶端。
插入元素到栈顶的操作,称为入栈。
从栈顶删除最后一个元素的操作,称为出栈。
对于向上生成的堆栈:
入栈口诀：
堆栈指针top"先压后加":
S[top++]=an+1
出栈口诀：
堆栈指针top"先减后弹":
e=S[--top]
◆栈的顺序和链式存储结构,及在这两种结构下实现栈的操作。
顺序栈入栈函数PUSH〔
statusPush
{ifM>{上溢}
elses[top++]=e;
}
顺序栈出栈函数POP<>
statusPop<>
{if{下溢}
else{e=s[--top];return;}
}
◆队列的定义及操作,队列的删除在一端〔队尾,而插入则在队列的另一端〔队头。
因此在两种存储结构中,都需要队头和队尾两个指针。
队列：
只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表。
链队列
结点类型定义：
typedefStructQNode{
QElemTypedata;//元素
StructQNode*next;//指向下一结点的指针
}Qnode,*QueuePtr;
链队列类型定义：
typedefstruct{
QueuePtrfront;//队首指针
QueuePtrrear;//队尾指针
}LinkQueue;
链队示意图：
①空链队的特征：
front=rear
②链队会满吗？
一般不会,因为删除时有free动作。
除非内存不足！
③入队〔尾部插入：
rear->next=S;rear=S;
出队〔头部删除：
front->next=p->next;
2.顺序队
顺序队类型定义：
#defineQUEUE-MAXSIZE100//最大队列长度
typedefstruct{
QElemType*base;//队列的基址
intfront;//队首指针
intrear;//队尾指针
}SqQueue
建队核心语句：
q.base=malloc*QUEUE_MAXSIZE;//分配空间
顺序队示意图：
循环队列：
队空条件:
front=rear<初始化时：
front=rear>
队满条件：
front=%N
队列长度〔即数据元素个数：
L=〔N＋rear－front%N
1）初始化一个空队列
StatusInitQueue//初始化空循环队列q
{
q.base=malloc*QUEUE_MAXSIZE>;//分配空间
if
q.base>exit;//内存分配失败,退出程序
q.front=q.rear=0;//置空队列
returnOK;
}//InitQueue;
2）入队操作
StatusEnQueue
{//向循环队列q的队尾加入一个元素e
if<%QUEUE_MAXSIZE==q.front>
returnERROR;//队满则上溢,无法再入队
q.rear=%QUEUE_MAXSIZE;
q.base[q.rear]=e;//新元素e入队
returnOK;
}//EnQueue;
3）出队操作
StatusDeQueue
{//若队列不空,删除循环队列q的队头元素,
//由e返回其值,并返回OK
ifreturnERROR;//队列空
q.front=%QUEUE_MAXSIZE;
e=q.base[q.front];
returnOK;
}//DeQueue
◆链队列空的条件是首尾指针相等,而循环队列满的条件的判定,则有队尾加1等于队头和设标记两种方法。
补充重点：
1.为什么要设计堆栈？
它有什么独特用途？
①调用函数或子程序非它莫属；
②递归运算的有力工具；
③用于保护现场和恢复现场；
④简化了程序设计的问题。
2.为什么要设计队列？
它有什么独特用途？
①离散事件的模拟〔模拟事件发生的先后顺序,例如CPU芯片中的指令译码队列；
②操作系统中的作业调度〔一个CPU执行多个作业；
③简化程序设计。
3.什么叫"假溢出"？
如何解决？
答：
在顺序队中,当尾指针已经到了数组的上界,不能再有入队操作,但其实数组中还有空位置,这就叫"假溢出"。
解决假溢出的途径———采用循环队列。
4.在一个循环队列中,若约定队首指针指向队首元素的前一个位置。
那么,从循环队列中删除一个元素时,其操作是先移动队首位置,后取出元素。
5.线性表、栈、队的异同点：
相同点：
逻辑结构相同,都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表,即受限的线性表〔只是对插入、删除运算加以限制。
不同点：
①运算规则不同：
线性表为随机存取；
而栈是只允许在一端进行插入和删除运算,因而是后进先出表LIFO；
队列是只允许在一端进行插入、另一端进行删除运算,因而是先进先出表FIFO。
②用途不同,线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。
第四章串
内容提要：
◆串是数据元素为字符的线性表,串的定义及操作。
串即字符串,是由零个或多个字符组成的有限序列,是数据元素为单个字符的特殊线性表。
串比较：
intstrcmp;
求串长：
intstrlen;
串连接：
charstrcat
子串T定位：
charstrchr;
◆串的存储结构,因串是数据元素为字符的线性表,所以存在"结点大小"的问题。
模式匹配算法。
串有三种机内表示方法：
模式匹配算法：
算法目的：
确定主串中所含子串第一次出现的位置〔定位
定位问题称为串的模式匹配,典型函数为Index
BF算法的实现—即编写Index函数
BF算法设计思想：
将主串S的第pos个字符和模式T的第1个字符比较,
若相等,继续逐个比较后续字符；
若不等,从主串S的下一字符〔pos+1起,重新与T第一个字符比较。
直到主串S的一个连续子串字符序列与模式T相等。
返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。
否则,匹配失败,返回值0。
IntIndex_BP
{//返回子串T在主串S中第pos个字符之后的位置。
若不存在,则函数值为0.
//其中,T非空,1≤pos≤StrLength
i=pos;j=1;
while//如果i,j二指针在正常长度范围,
{
if{++i,++j;}//则继续比较后续字符
else{i=i-j+2;j=1;}//若不相等,指针后退重新开始匹配
}
ifT[0]>returni-T[0];//T子串指针j正常到尾,说明匹配成功,elsereturn0;//否则属于i>S[0]情况,i先到尾就不正常
}//Index_BP
补充重点：
1.空串和空白串有无区别？
答：
有区别。
空串是指长度为零的串；
而空白串,是指包含一个或多个空白字符‘’<空格键>的字符串.
2."空串是任意串的子串；任意串S都是S本身的子串,除S本身外,S的其他子串称为S的真子串。
"
第六章树和二叉树
内容提要：
◆树是复杂的非线性数据结构,树,二叉树的递归定义,基本概念,术语。
树：
由一个或多个结点组成的有限集合T,有且仅有一个结点称为根〔root,当n>1时,其余的结点分为m个互不相交的有限集合T1,T2,…,Tm。
每个集合本身又是棵树,被称作这个根的子树。
二叉树：
是n〔n≥0个结点的有限集合,由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
术语：
P88
◆二叉树的性质,存储结构。
性质1:
在二叉树的第i层上至多有2i-1个结点〔i>0。
性质2:
深度为k的二叉树至多有2k-1个结点〔k>0。
性质3:
对于任何一棵二叉树,若2度的结点数有n2个,则叶子数〔n0必定为n2＋1
性质4:
具有n个结点的完全二叉树的深度必为
性质5:
对完全二叉树,若从上至下、从左至右编号,则编号为i的结点,其左孩子编号必为2i,其右孩子编号为2i＋1；其双亲的编号必为i/2〔i＝1时为根,除外。
二叉树的存储结构：
一、顺序存储结构
按二叉树的结点"自上而下、从左至右"编号,用一组连续的存储单元存储。
若是完全/满二叉树则可以做到唯一复原。
不是完全二叉树：
一律转为完全二叉树！
方法很简单,将各层空缺处统统补上"虚结点",其内容为空。
缺点：
①浪费空间；②插入、删除不便
二、链式存储结构
用二叉链表即可方便表示。
一般从根结点开始存储。
优点：
①不浪费空间；②插入、删除方便
◆二叉树的遍历。
指按照某种次序访问二叉树的所有结点,并且每个结点仅访问一次,得到一个线性序列。
遍历规则———
二叉树由根、左子树、右子树构成,定义为D、L、R
若限定先左后右,则有三种实现方案：
DLRLDRLRD
先序遍历中序遍历后序遍历
◆树的存储结构,树、森林的遍历及和二叉树的相互转换。
回顾2：
二叉树怎样还原为树？
要点：
逆操作,把所有右孩子变为兄弟！
讨论1：
森林如何转为二叉树？
法一：
①各森林先各自转为二叉树；②依次连到前一个二叉树的右子树上。
法二：
森林直接变兄
升级会员 