第三章介绍的是栈和队列以及有关它们的应用．前面提到，栈和队列都是操作受限的线性表．也就是说，它们都属于线性表．但是它们在访问上受到了限制．栈这种结构，它的特点就是要求：先进后出．而队列是：先进先出．栈，比如说我们给一个订书机放入订书针，放进去的时候，头朝里的却是最后才订出来．又如果从一个玩具枪的枪口往里放子弹，一个个放入以后，出来时，是后进去的先打出来．（这当然是随意举个例子，只图形象生动一些，而并不科学，真正科学的例子，课本上已经给出了很多，在此就不列举了．）队列的例子就好举了，排队打饭的时候，排在前面的就先打到先离开，这就是一个队伍，也是队列．而栈和队列还有许多变形，有可能是两个栈放在一个数组中，栈顶相对着增长；还有队列也有可能是两个并排的队列，两头都可进可出，等等，在原有的基础上进行演绎，这些就是更多的一些内容，更大的范围．在这里我们就都不说了，简单提提栈与队列的存储结构．它们具有线性表的特质，也就是说即可以顺序数组存储也可以链表存储．相应的于是就有：顺序栈，链栈，顺序队列，链队．它们的程序实现起来，也还是蛮有意思的．
　　在应用的时候，我们结合现实工作与生活中的一些具体情况，根据我们的需要，可以选择这些相应的存储结构进行一些程序设计，来帮助我们更好地实现所要做的事情．比如：利用栈可以进行：逆置数组，回文游戏，进制互换，括号匹配，表达式转换或计算，以及树部份的利用栈实现非递归遍历算法等，还有迷宫游戏，汉诺塔问题等等．而栈还有手动栈和系统自动栈等．系统自动栈就是说系统的内部还设置了栈，可以自动进行栈结构的操作．比如做一个递归程序，需要用到递归工作栈的时候，计算机系统自动会使用内部程序已经设置好的递归工作栈，进行层层递归，来实现程序操作．而如果说不用系统定义的栈，那就要自己手动地定义一个栈，并指定所有的栈所需要的操作以及用程序语言来实现它．这需要熟悉栈的算法．扯远了，接着讲队列吧．
　　队列的应用也是较为广泛的．银行问题，航空售票系统等，这些就可以用队列来实现啦．而前面的最基本的线性表呢，学了以后，也可以实现计算多项式的加加减减等这样的操作．还是挺好的啦．

　　接下来进入第四章吧．第四章介绍的是串．串也同样是线性表中的一种了，只是它的特殊性在于它所有的数据都是字符组成的．这些数据的处理在存储结构上就有三种：定长顺序，堆栈，块链．其中顺序是常见的一种了，书上的很多算法都基本是基于这种顺序存储结构来进行讲解的．比如串的查找，ＫＭＰ算法等这些都是假设在定长顺序的存储结构上进行的．也就是说以数组来存储啦．而堆栈同样也是以地址连续的存储单元来实现的，所不同的是它能够在空间不够的情况下用relloc（）再次进行申请增加空间．块链就是一个字符一个链结点或是多个字符成一个链接点，一块一块地由链子链在一起了，这里的块可以是一个字符或是多个字符，按具体情况来选择．
　　在第四章中，除了replace,substring,contact这样的一些基本操作之外，最难的要数index, 和在index上的改进的ＫＭＰ啦．ＫＭＰ应该是本章中的最难点之一．而ＫＭＰ又是一个比较精华的思想，而其精华之精华又在于getnext函数，即求next[]值的方法．在有了next[]之基础上，还可以再次进行改进，产生了一个nextval[]，即修正以后的next值．
　　本人学KMP，前后用了总共两星期左右的时间．第一次用的是殷版的书，上面说得比较详细，而第二次用的就是严版的书了，看严版的时候，由于有了殷版的基础，所以就主要是以听课件讲解的形式进行．当然，感觉还是看书的效果要好一些．所以如果有人看这帖子的话，奉劝还是多看教材为妙．在殷版与严版之间，还有一些差异，关于next值的定义上，殷好象是用了-1一律表示Ｋ值之外的情况时next的值．而严版分别有0和1两种数值来表示next值．另外，对于K的具体取值两本书也有不同的规定．当然，这对算法的本质上是没有区别的．
　　在看ＫＭＰ的时候，细细地比较改进前与改进后的差异，并搞清楚next[]值具体是怎么求的，这很关键．在弄熟悉这部份的内容以后，可以达到＂看＂一下串，就能够＂看＂出它的next[]数组的值来．这是一个很快的计算过程．

　　至此，已经基本将前面部份的内容总结完了．一共是四章．后面第五章是广义表，它同样属于线性表，但它是一种广义的线性表，也就是说它在某种意义上拓广了线性表的概念，故而称之为广义表．后面若有空，还是会在学习之后进行总结，并同大家交流的．谢过看帖的朋友，如果看后有什么意见的话，欢迎跟帖，或是加入＂数据结构＂交流群（ＱＱ群号码：27196587）与大家交流．

　　［雨523　总结　于2006/10/13夜 9:40pm)

顶一下杭电

//(1)顺序表
//2006/10/04

#include<stdio.h>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10

typedef struct {
int *elem;
int length;
int listsize;
}Sqlist;

Sqlist  InitList(Sqlist L)
{
L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int));
if(!L.elem) exit(0);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return L;
}

Sqlist Create(Sqlist L, int n)
{int i;
for (i=0;i<n;i++)
{scanf("%d",&L.elem[i]);}

L.length=n;
return L;
}



Sqlist ListInsert(Sqlist L, int i, int e)
{
int *p,*q;
if (i<1||i>L.length-1) printf("error");
if(L.length>=L.listsize)
{
L.elem=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!L.elem)exit(0);
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
L.length=L.length+1;
printf ("the now length is%d\n",L.length);
return L;
}


Sqlist Print(Sqlist L)
{
int i=0;
for (i=0;i<L.length;i++)
printf("%d ",L.elem[i]);
}

main()
{
Sqlist a;
int an,ae;
int number;
printf("\ntoday is 2006.10.04");
printf("\n顺序表练习,请选择要进行的操作:\n1, 建初始顺序表；\n2，插入数据;\n0.退出\n");
while(number!=0)
{
scanf("%d",&number);
switch(number)
{case 1: a=InitList(a);
         printf("\n请输入十个数建初始表：");
         a=Create(a,10);
         printf("\n您所建立的表为:");
         Print(a);
         printf("\n继续操作请按2，否则请按0退出，重新输入请按1:");
         break;
 case 2://a=ListInsert(a, 2, 10);
         printf("\n请输入您要插入的位置an=? 插入的数据ae=?");
         //printf("an=?ae=?");
         scanf("%d %d",&an,&ae);
         a=ListInsert(a,an,ae);
         printf("\n您所进行的插入操作已成功，新的顺序表数据为:");
         Print(a);
         printf("\n请选择您要继续的操作：0,1,2:");
         break;
 case 0: break;

 default:printf ("error,您的选择超出范围\n");
 }
}
printf("\nok\n");
}

//(2)顺序表的改进
//2006/10/05

#include<stdio.h>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10

typedef struct {
int *elem;
int length;
int listsize;
}Sqlist;

//算法2.3
Sqlist  InitList(Sqlist L)
{
L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int));
if(!L.elem) exit(0);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return L;
}



//算法2.4
Sqlist ListInsert(Sqlist L, int i, int e)
{
int *p,*q;
if (i<1) printf("error");
if(L.length>=L.listsize)
{
L.elem=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!L.elem)exit(0);
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
L.length=L.length+1;
printf ("the now length is%d\n",L.length);
return L;
}


//算法2.5
Sqlist ListDelete(Sqlist L,int i,int e){
int *p,*q;
if((i<1)||(i>L.length))printf("ERROR");

p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return L;
}

Sqlist Print(Sqlist L)
{
int i=0;
for (i=0;i<L.length;i++)
printf("%d ",L.elem[i]);
}

main()
{
Sqlist a;
int x;
int n;
printf("\ntoday is 2006.10.05");

//初始化顺序表，表为空
a=InitList(a);

//给当前顺序表插入结点
printf("为链表输入结点，如果输入为0，则缺省结束\n");
while(x!=0){
scanf("%d",&x);
if(x!=0)a=ListInsert(a,1,x);
}

//输出顺序表中的全部数据
a=Print(a);

//删除顺序表中的数据
printf("请输入要删除的结点位序:\n");
scanf("%d",&n);
a=ListDelete(a,n,x);
printf("删除以后余下的数据为:\n");
a=Print(a);
}

//(2)顺序表的改进_B
//2006/10/06

#include<stdio.h>

#define LIST_INIT_SIZE 100
#define LISTINCREMENT  10

typedef struct {
int *elem;
int length;
int listsize;
}Sqlist;

//算法2.3
Sqlist  InitList(Sqlist L)
{
L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int));
if(!L.elem) exit(0);
L.length=0;
L.listsize=LIST_INIT_SIZE;
return L;
}



//算法2.4
Sqlist ListInsert(Sqlist L, int i, int e)
{
int *p,*q;
if (i<1) printf("error");
if(L.length>=L.listsize)
{
L.elem=(int *)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!L.elem)exit(0);
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p;
*q=e;
L.length=L.length+1;
printf ("the now length is%d\n",L.length);
return L;
}


//算法2.5
Sqlist ListDelete(Sqlist L,int i,int e){
int *p,*q;
if((i<1)||(i>L.length))printf("ERROR");
p=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
for(++p;p<=q;++p)*(p-1)=*p;
--L.length;
return L;
}

/*
//算法2.6
int LocateElem(Sqlist L,int e,int(*compare)(int,int))
{  int i=1;
int *p=L.elem;
while(i<L.length&&!(*compare)(*p++,e))++i;
if(i<=L.length) return i;
else return 0;
}

int equal(int a,int b)
{if (a==b) return 1;
else return 0;
}
*/

int Locate(Sqlist L,int e)
{
int i=0;
while((i<=(L.length-1))&&(e!=L.elem))i++;
if(i<=(L.length-1))
 return i;
 return 0;
}


//算法2.1
Sqlist Union(Sqlist L1,Sqlist L2)
{
int i,*p;
for (i=0;i<L1.length;i++)
{
 *p=L2.elem[i];
 if(Locate(L1,*P)==0)
 ListInsert(L1,++L1.length,*p);
 }
return L1;
}

Sqlist Print(Sqlist L)
{
int i=0;
for (i=0;i<L.length;i++)
printf("%d ",L.elem[i]);
return L;

}


main()
{
Sqlist a,b,c;
int x,x2,x3;
int n,find=0;
printf("\ntoday is 2006.10.05");

//初始化顺序表，表为空
a=InitList(a);

//给当前顺序表插入结点
printf("为链表输入结点，如果输入为0，则缺省结束\n");
while(x!=0){
scanf("%d",&x);
if(x!=0)a=ListInsert(a,1,x);
}

//输出顺序表中的全部数据
Print(a);

//删除顺序表中的数据
printf("请输入要删除的结点位序:\n");
scanf("%d",&n);
a=ListDelete(a,n,x);
printf("删除以后余下的数据为:\n");
Print(a);

//查找
//find=LocateElem(a,3,equal);
printf("请输入要查找的数据:");
scanf("%d",&x);
printf("%d\n",x);

a=Print(a);
find=Locate(a,x);
printf("\n要查找的数据为第%d位置",find);

//建二个顺序表b,c，并进行合并

      //初始化顺序表，表为空
b=InitList(b);

//给当前顺序表插入结点
printf("为顺序表b输入结点，如果输入为0，则缺省结束\n");
while(x2!=0){
scanf("%d",&x2);
if(x!=0)b=ListInsert(b,1,x2);
}

//输出顺序表中的全部数据
Print(b);

//初始化顺序表，表为空
c=InitList(c);

//给当前顺序表插入结点
printf("为顺序表输入结点，如果输入为0，则缺省结束\n");
while(x3!=0){
scanf("%d",&x3);
if(x!=0)c=ListInsert(c,1,x3);
}

//输出顺序表中的全部数据
Print(c);

//合并bc到b内
b=Union(b,c);
Print(b);

}

第五六两章很快就从开始走向了尾声，在走过的这一着里，不知道自己吸收与消化了多少。现在惯例写个简单的总结。<BR><BR>　　在第五章中介绍了数组、矩阵的存储、广义表的概念及操作等。这一部份中，考得较多的就是各种矩阵在相应的存储方式下相应的地址，主要考如何计算它的地址，要求写公式，或是某一个具体的地址。感觉三对角矩阵的i,j,k的关系还是略有些麻烦，它要求考虑到a11(a00)或是k1(k0)的对应关系。也就是说到底下标是从０开始还是１开始？不同的书或是不同的算法标准不一定相同，这略有些麻烦。十字链表倒是极为有趣，算法还是较详细地看了一下。快速转置算法也还是算高明的。这里就不说啦。广义表部份只是看了简单的概念和存储。一些相关算法就有待以后有余力的时候再看。<BR><BR>　　第六章中，树，二叉树，森林，是重头戏了。当然后面还有线索树，哈夫曼树这样一些较有意思的东东。在前三者中，务必要会存储，会遍历，会做一些简单的算法。而且还要会相互转化。主要有把树转换为二叉树或是把森林转换为二叉树。而遍历的时候，树对应了先序，后序。二叉树对应了前序，中序，后序。森林的遍历也还是应该了解。在二叉树中，还用到了利用栈进行非递归遍历，以及利用队列进行层次遍历。线索树的时候，要注意会穿线，而且清楚整个算法的来龙去脉。哈夫曼树要会作出树来，而且能够编码。这些个东西内容还是较丰富的。虽然很快就复习完了课本上相关部份的内容，但需要时间去做一些习题，并反复领悟课本的内容。<BR><BR>　　关于树这一章，找一些相关的树的算法题，是非常必要的。<BR><BR>　　好，就简单地谈这。算是接在第１～４章总结后面的一点东西。

顶一下这个帖子，欢迎大家交流

写的真详细！
谢谢楼主！
我会努力的

我是一个初学者
请让我加入该群
谢谢！
[em1][em1][em1][em1]

忘了说我的QQ了407194737