前言：
呵呵，啥，你会编程，不会数据结构？是的，我会编程，却没学过数据结构。够无语吧！从大一学C++编程开始，就对编程充满了兴趣。其实我一直对软件编程蛮喜欢的，谁叫我小时候就喜欢计算机呢！谁叫我从小就觉得电脑很神奇呢！呵呵，废话不多说了，因为大学的课程没开数据结构（⊙﹏⊙b汗，不知道学校领导怎么想的）所以自己抽空来大致的学学吧。
手上有本书，实用数据结构 高职高专计算机系列教材。书有点磋，不过还好，我只是抽空了解下数据结构，补补这方面的一些知识，不求了解的多深刻。进入正题啦：
数据结构学习 一
2009-08-13日
（1）数据：一切能够由计算机接收和处理的对象，注意不仅仅是数字哦。
（2）数据元素：数据的基本单位，在程序中做为一个整体加以考虑和处理。
（3）数据项：数据中不可分割的最小单位（让你想起来啥？原子呗）
（4）数据结构：数据之间的相互关系，即数据的组织形式。包括物理结构和逻辑结构，逻辑结构指相互之间的逻辑关系，物理结构指如何存储。
（5）研究数据结构：除了要定义数据元素之间的关系，更重要的是要定义一组有关数据元素的运算。这话挺重要的，这话的意思就是，你定义了一个数组，自然同时你也应该定义如何获得数组首地址，如何获得数组中的元素，如何获得数组的大小等等的操作；你定义了一个链表，自然同时你也应该定义链表的头，链表的添加元素的操作，链表的减少元素的操作，链表中元素的查找等等。
（6）算法：对特定问题求解步骤的一种描述。一直挺喜欢算法的，感觉这种东西比较神奇，比较玄妙。你说不玄妙吗？当你自己费了千百行才能完成的操作，被别人用几句话解决的时候，你就会不得不感叹算法的神奇了。书上说算法是有穷的规则序列。这个解释，还可以，现在的我还没看出有什么不对的地反过来。
（7）算法 + 数据结构 = 程序？MAYBE吧 名人说的，肯定有一定道理。
（8）算法的评价： 一看正确与否；二看可读性；三看简单与否（啥，影响中越复杂的算法感觉越酷吧）；四看效率，即时空性能。
（9）算法复杂性的分析：时间复杂性+空间复杂性。因为现在硬件技术的发展，空间基本上还是够用的，所以现在强调的多的是时间复杂性。
（10）时间复杂性的计算： temp = i; 时间复杂性 T(N) = O(1);
sum = 0; for(i=1;i
数组和线性表
线性表，最基本最常用的数据结构。栈和队列是线性表的特例。
（1）数组，最常见的数据结构。这个地球人都知道吧。
计算数组元素地址的寻址公式。设下标下界为LB，上界为UB，第一个元素的地址loc(LB),下标为i的元素地址loc(i) = loc(LB) + (i-LB)*s。
同样m行n列二维数组的寻址公式是：loc(i,j)=loc(0,0) + (i*n+j)*s。应该可以看出。这里的下标下界都是0哦。三维A[m][n][p]的寻址公式就是loc(i,j,k) = loc(0,0,0) + (i*n*p + j*p + k)*s。这个，没有再写下去的必要了吧。呵呵。
（2）线性表：有限数目的相同类型的元素组成序列。（结构体中的元素可以不同，比线性表要好哦。）表中的元素，除了第一个和最后一个元素，其余元素都是只有一个前驱元素只有一个后续元素。再这句话的意思就是说，一个接一个了。元素的个数可以为0哦，此时叫空表。（哎呀，到时候又得多个判断是否是空表的操作唉）
线性表在内存中采用各元素顺序存储的方式，这种存储结构叫做向量。
（3）线性表的一些运算：
数据元素的插入 void insert(A,n,m,i,G) 一维数组A[n],已有m个元素，插入到第i个元素的前面，元素的值为G。（要求还真多）
void insert(A,n,m,i,G){
int j=0;
if(i<1||i>n+1) printg("error!");
else{
for(j=m;j>=i;j--) A[j+1] = A[j];
A[i]=G;
n++;
}
}
线性表中数据元素的删除 A[n]n个元素，删除第i个数据元素。
void delete(A,n,i){
int j;
if(i<1||i>n) printf("error");
else{
for(j=i;j<=n;j++) A[j] = A[j+1];
n--;
}
}
（4）栈(stack)及其应用：（书上叫堆栈，⊙﹏⊙b汗，堆和栈的区别。）
栈是限定在表的一端进行插入或删除操作的线性表（有道理唉，我以前怎么没发现），所以它是LIFO(last in first out)。进行删除操作的一端叫栈顶（不是最高的地址那端哦，这我知道）TOP，另一端叫栈底BOTTOM。插入元素叫入栈PUSH，删除元素叫出栈POP。不含元素的栈叫空栈。
（5）栈的一些运算：
入栈 PUSH
void push(STACK,n,top,G)（每个符号的意义应该可以猜出来了吧？）
{
if(top = n) printf("overflow");
else
{
top = top+1;
STACK[TOP] = G;
}
}
出栈 POP
void pop(STACK,top,X)
{
if(top = 0) printf("empty stack");
X = STACK[top];
top--;
}
堆栈的两个典型应用：
一。函数调用函数时；二。表达式计算中的应用（提示，采用了两个堆栈，一个存操作数，一个存操作符）。不懂的可以去学习下哦。
（6）队列（QUEUE） ⊙﹏⊙b汗，链表了解些，这个倒真没听过。
队列，和堆栈不同的是，一头只进（队尾rear），一头只出（对头front），FIFO。
（7）队列的一些运算
入队（insert）
void insert(QUEUE,n,f,r,X)
{
if(r == n) printf("overflow");
else
{
r = r+1;
Q[r] = X;
if(f = 0) f = 1;
}
}
出队（delete）
void delete(QUEUE,f,r,X)
{
if(f = 0) printf("empty queue");
else
{
X = QUEUE[f];
if( f == r)
{
f=0;r=0;
}
else f++;
}
}
呵呵，这里大家有没有发现啥啊？
（8）循环队列 （不知道谁想出来的，有点意思）
入队函数
void insert(QUEUE,n,f,r,X)
{
if(r == n) r= 1;
else r = r+1;
if(f == r) printf("overflow");
else
{
Q[r] = X;
if(f = 0) f = 1;
}
}
出队函数
void delete(QUEUE,n,f,r,X)
{
if(f = 0) printf("empty queue");
else
{
X=Q[f];
if(f == r){f=0;r=0;}
else if(f == n) f = 1;
else f = f+1;
}
}
队列两个的应用
一。计算机的输入输出管理中；二。对CPU的分配管理中。
阅读(1076) | 评论(1) | 转发(0) |
