p=p->next;指针下移
j++;
}
if（i==j）
returnp;
else
returnNULL;
}
2）按值查找。
Listnode*locatenode（linklisthead,datatypekey）
{
listnode*p=head->next;
while（p&&p->data!
=key）
p=p->next;
returnp;
}
（3）插入运算。
时间复杂度为O（n）。
Voidinsertlist（linklisthead,datatypex,inti）
{
listnode*p;
p=getnode（head,i-1）;
if（p==NULL）;
error（“positionerror”）;
s=（listnode*）malloc（sizeof（listnode））;
s->data=x;
s->next=p->next;
p->next=s;
}
（4）删除运算。
时间复杂度为O（n）。
Voiddeletelist（linklisthead,inti）
{
listnode*p,*r;
p=getnode（head,i-1）;
if（p==NULL||p->next==NULL）
error（“positionerror”）;
r=p->next;
p->next=r->next;
free（r）;
}
7.循环链表：
是一种首尾相连的链表。
特点是无需增加存储量，仅对表的链接方式修改使表的处理灵活方便。
8.空循环链表仅由一个自成循环的头结点表示。
9.很多时候表的操作是在表的首尾位置上进行，此时头指针表示的单循环链表就显的不够方便，改用尾指针rear来表示单循环链表。
用头指针表示的单循环链表查找开始结点的时间是O
（1）,查找尾结点的时间是O（n）；用尾指针表示的单循环链表查找开始结点和尾结点的时间都是O
（1）。
10.在结点中增加一个指针域，prior|data|next。
形成的链表中有两条不同方向的链称为双链表。
1）双链表的前插操作。
时间复杂度为O
（1）。
Voiddinsertbefore（dlistnode*p,datatypex）
{
dlistnode*s=malloc（sizeof（dlistnode））;
s->data=x;
s->prior=p->prior;
s->next=p;
p->prior->next=s;
p->prior=s;
}
2）双链表的删除操作。
时间复杂度为O
（1）。
Voidddeletenode（dlistnode*p）
{
p->prior->next=p->next;
p->next->prior=p->prior;
free（p）;
}
11.顺序表和链表的比较
1）基于空间的考虑：
顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。
顺序表的存储密度比链表大。
因此，在线性表长度变化不大，易于事先确定时，宜采用顺序表作为存储结构。
2）基于时间的考虑：
顺序表是随机存取结构，若线性表的操作主要是查找，很少有插入、删除操作时，宜用顺序表结构。
对频繁进行插入、删除操作的线性表宜采用链表。
若操作主要发生在表的首尾时采用尾指针表示的单循环链表。
12.存储密度=（结点数据本身所占的存储量）/（整个结点结构所占的存储总量）
存储密度：
顺序表=1，链表<1。
第三章 栈和队列
1.栈是限制仅在表的一端进行插入和删除运算的线性表又称为后进先出表（LIFO表）。
插入、删除端称为栈顶，另一端称栈底。
表中无元素称空栈。
2.栈的基本运算有：
1）initstack（s）,构造一个空栈；
2）stackempty（s）,判栈空；
3）stackfull（s）,判栈满；
4）push（s,x）,进栈；
5）pop（s）,退栈；
6）stacktop（s），取栈顶元素。
3.顺序栈：
栈的顺序存储结构称顺序栈。
4.当栈满时，做进栈运算必定产生空间溢出，称“上溢”。
当栈空时，做退栈运算必定产生空间溢出，称“下溢”。
上溢是一种错误应设法避免，下溢常用作程序控制转移的条件。
5.在顺序栈上的基本运算：
1）置空栈。
Voidinitstack（seqstack*s）
{
s->top=-1;
}
2）判栈空。
intstackempty（seqstack*s）
{
returns->top==-1;
}
3）判栈满。
intstackfull（seqstack*s）
{
returns->top==stacksize-1;
}
4）进栈。
Voidpush（seqstack*s,datatypex）
{
if（stackfull（s））
error（“stackoverflow”）;
s->data[++s->top]=x;
}
5）退栈。
Datatypepop（seqstack*s）
{
if（stackempty（s））
error（“stackunderflow”）;
returnS->data[s->top--];
}
6）取栈顶元素。
Dtatatypestacktop（seqstack*s）
{
if（stackempty（s））
error（“stackunderflow”）;
returnS->data[s->top];
}
6.链栈：
栈的链式存储结构称链栈。
栈顶指针是链表的头指针。
7.链栈上的基本运算：
1）建栈。
Voidinitstack（linkstack*s）
{
s->top=NULL;
}
2）判栈空。
Intstackempty（linkstack*s）
{
returns->top==NULL;
}
3）进栈。
Voidpush（linkstack*s,datatypex）
{
stacknode*p=（stacknode*）malloc（sizeof（stacknode））;
p->data=x;
p->next=s->top;
s->top=p;
}
4）退栈。
Datatypepop（linksatck*s）
{
datatypex;
stacknode*p=s->top;
if（stackempty（s））
error（“stackunderflow”）;
x=p->data;
s->top=p->next;
free（p）;
returnx;
}
5）取栈顶元素。
Datatypestacktop（linkstack*s）
{
if（stackempty（s））
error（“stackisempty”）;
returns->top->data;
}
8.队列是一种运算受限的线性表，允许删除的一端称队首，允许插入的一端称队尾。
队列又称为先进先出线性表，FIFO表。
9.队列的基本运算：
1）initqueue（q）,置空队；
2）queueempty（q）,判队空；
3）queuefull（q）,判队满；
4）enqueue（q,x）,入队；
5）dequeue（q）,出队；
6）queuefront（q）,返回队头元素。
10.顺序队列：
队列的顺序存储结构称顺序队列。
设置front和rear指针表示队头和队尾元素在向量空间的位置。
11.顺序队列中存在“假上溢”现象，由于入队和出队操作使头尾指针只增不减导致被删元素的空间无法利用，队尾指针超过向量空间的上界而不能入队。
12.为克服“假上溢”现象，将向量空间想象为首尾相连的循环向量，存储在其中的队列称循环队列。
i=（i+1）%queuesize
13.循环队列的边界条件处理：
由于无法用front==rear来判断队列的“空”和“满”。
解决的方法有：
1）另设一个布尔变量以区别队列的空和满；
2）少用一个元素，在入队前测试rear在循环意义下加1是否等于front；
3）使用一个记数器记录元素总数。
14.循环队列的基本运算：
1）置队空。
Voidinitqueue（cirqueue*q）
{
q->front=q->rear=0;
q->count=0;
}
2）判队空。
Intqueueempty（cirqueue*q）
{
returnq->count==0;
}
3）判队满。
Intqueuefull（cirqueue*q）
{
returnq->count==queuesize;
}
4）入队。
Voidenqueue（cirqueue*q,datatypex）
{
if（queuefull（q））
error（“queueoverfolw”）;
q->count++;
q->data[q->rear]=x;
q->rear=（q->rear+1）%queuesize;
}
5）出队。
Datatypedequeue（cirqueue*q）
{
datatypetemp;
if（queueempty（q））
error（“queueunderflow”）;
temp=q->data[q->front];
q->count--;
q->front=（q->front+1）%queuesize;
returntemp;
}
6）取队头元素。
Datatypequeuefront（cirqueue*q）
{
if（queueempty（q））
error（“queueisempty”）;
returnq->data[q->front];
}
15.链队列：
队列的链式存储结构称链队列，链队列由一个头指针和一个尾指针唯一确定。
16.链队列的基本运算：
1）建空队。
Voidinitqueue（linkqueue*q）
{
q->front=q->rear=NULL;
}
2）判队空。
Intqueueempty（linkqueue*q）
{
returnq->front==NULL&&q->rear==NULL;
}
3）入队。
Voidenqueue（linkqueue*q,datatypex）
{
queuenode*p=（queuenode*）malloc（sizeof（queuenode））;
p->data=x;
p->next=NULL;
if（queueempty（q））
q-front=q->rear=p;
else{
q->rear->next=p;
q->rear=p;
}
}
4）出队。
Datatypedequeue（linkqueue*q）
{
datatypex;
queuenode*p;
if（queueempty（q））
error（“queueisunderflow”）;
p=q->front;
x=p->data;
q->front=p->next;
if（q->rear==p）q->rear=NULL;
free（p）;
returnx;
}
5）取队头元素。
Datatypequeuefront（linkqueue*q）
{
if（queueempty（q））
error（“queueisempty”）;
returnq->front->data;
}
第四章 串
1.串：
是由零个或多个字符组成的有限序列；包含字符的个数称串的长度；
2.空串：
长度为零的串称空串； 空白串：
由一个或多个空格组成的串称空白串；
子串：
串中任意个连续字符组成的子序列称该串的子串； 主串：
包含子串的串称主串；
子串的首字符在主串中首次出现的位置定义为子串在主串中的位置；
3.空串是任意串的子串； 任意串是自身的子串；
串常量在程序中只能引用但不能改变其值；串变量取值可以改变；
4.串的基本运算
1）intstrlen（char*s）;求串长。
2）char*strcpy（char*to,char*from）;串复制。
3）char*strcat（char*to,char*from）;串联接。
4）intstrcmp（char*s1,char*s2）;串比较。
5）char*strchr（char*s,charc）;字符定位。
5.串的存储结构：
（1）串的顺序存储：
串的顺序存储结构称顺序串。
按存储分配不同分为：
1）静态存储分配的顺序串：
直接用定长的字符数组定义，以“\0”表示串值终结。
#definemaxstrsize256
typedefcharseqstring[maxstrsize];
seqstrings;
不设终结符，用串长表示。
Typedefstruct{
Charch[maxstrsize];
Intlength;
}seqstring;
以上方式的缺点是：
串值空间大小是静态的，难以适应插入、链接等操作。
2）动态存储分配的顺序串：
简单定义：
typedefchar*string;
复杂定义：
typedefstruct{
char*ch;
intlength;
}hstring;
（2）串的链式存储：
串的链式存储结构称链串。
链串由头指针唯一确定。
类型定义：
typedefstructnode{
chardata;
structnode*next;
}linkstrnode;
typedeflinkstrnode*linkstring;
linkstrings;
将结点数据域存放的字符个数定义为结点的大小。
结点大小不为1的链串类型定义：
#definenodesize80
typedefstructnode{
chardata[nodesize];
structnode*next;
}linkstrnode;
6.串运算的实现
（1）顺序串上的子串定位运算。
1）子串定位运算又称串的模式匹配或串匹配。
主串称目标串；子串称模式串。
2）朴素的串匹配算法。
时间复杂度为O（n^2）。
比较的字符总次数为（n-m+1）m。
Intnaivestrmatch（seqstringt,seqstringp）
{
inti,j,k;
intm=p.length;
intn=t.length;
for（i=0;i<=n-m;i++）{
j=0;k=i;
while（j j++;k++;
}
if（j==m）returni;
}
return–1;
}
（2）链串上的子串定位运算。
时间复杂度为O（n^2）。
比较的字符总次数为（n-m+1）m。
Linkstrnode*lilnkstrmatch（linkstringT,linkstringP）
{
linkstrnode*shift,*t,*p;
shift=T;
t=shift;p=P;
while（t&&p）{
if（t->data==p->data）{
t=t->next;
p=p->next;
}
else{
shift=shift->next;
t=shift;
p=P;
}
}
if（p==NULL）
returnshift;
else
returnNULL;
}
第五章 多维数组和广义表
1.多维数组：
一般用顺序存储的方式表示数组。
2.常用方式有：
1）行优先顺序，将数组元素按行向量排列；
2）列优先顺序，将数组元素按列向量排列。
3.计算地址的函数：
LOC（Aij）=LOC（Ac1c2）+（（i-c1）*（d2-c2+1）+j-c2）*d
4.矩阵的压缩存储：
为多个非零元素分配一个存储空间；对零元素不分配存储空间。
（1）对称矩阵：
在一个n阶的方阵A中，元素满足Aij=Aji0<=i,j<=n-1;称为对称矩阵。
元素的总数为：
n（n+1）/2;
设：
I=i或j中大的一个数；J=i或j中小的一个数；
则：
k=I*（I+1）/2+J;
地址计算：
LOC（Aij）=LOC（sa[k]）=LOC（sa[0]）+k*d=LOC（sa[0]）+（I*（I+1）/2+J）*d
（2）三角矩阵：
以主对角线划分，三角矩阵有上三角和下三角；上三角的主对角线下元素均为常数c；下三角的主对角线上元素均为常数c。
元素总数为：
（n（n+1）/2）+1;
以行优先顺序存放的Aij与SA[k]的关系：
上三角阵：
k=i*（2n-i+1）/2+j-i;
下三角阵：
k=i*（i+1）/2+j;
（3）对角矩阵：
所有的非零元素集中在以主对角线为中心的带状区域，相邻两侧元素均为零。
|i-j|>（k-1）/2
以行优先顺序存放的Aij与SA[k]的关系：
k=2i+j;
5.稀疏矩阵：
当矩阵A中有非零元素S个，且S远小于元素总数时，称为稀疏矩阵。
对其压缩的方法有顺序存储和链式存储。
（1）三元组表：
将表示稀疏矩阵的非零元素的三元组（行号、列号、值）按行或列优先的顺序排列得到的一个结点均是三元组的线性表，将该表的线性存储结
升级会员 