第一章 概论 1.数据是信息的载体,是能够输入到计算机中,并被计算机识别,存储和处理的符号的集合. 2.数据元素是数据中具有独立意义的个体.一个数据元素可以由若干各数据项(称为字段,域)组成. 3.数据类型是具有相同性质的计算机数据的集合及再这个数据集合上的一组操作. 4.数据结构是指组成数据的元素之间的结构关系.它一般包括以下三个方面的内容:(1)数据元素之间的逻辑关系,也称为数据的逻辑结构.(2)数据元素及其关系再计算机存储器内的表示,称为数据的存储结构.(3)数据的运算,即对数据施加的操作. 5.算法分析:主要是考虑算法的时间性能.(1)算法的总时间复杂度是由所有语句的执行次数相加来计算的.(2)通过相同的级别可以求出算法的数量级,比如O(1),O(n),O(n2)等等.(3)如果算法的时间复杂度并不只是由N来决定的,比如还有条件等等,就要求出算法的最坏时间复杂度.有时候也需要求平均时间复杂度. 第二章 线性表 线性表这里主要讨论的就是顺序表,链表和串(其实也就是前两种). 这一章的习题超多,做的很痛苦,大约做了3天才做完,现在都弄指针弄的走路都不知道指哪儿了:)所有的习题都写的全部完整,直接在TC下运行检测成功了,终于完成了. 奋发图强,下午继续第三章!  第三章 栈、队列和数组 一、栈栈是只能在一端进行插入和删除的线性表。（别看只是个定义，非常重要，已经道出了运算方法：只能在一端插入和删除。) 栈的特征：后进先出，先进后出。 插入和删除元素的一端称为栈顶。（说明了我们在栈顶操作）另一端称为栈底。插入元素和删除元素的操作称为入栈和出栈。 1.顺序栈结构：(top总是指向数组最后的元素，比如data[n]，而不是前面)#define MAXSIZE 100typedef struct{    elementtype data[MAXSIZE];    int top;} seqstack; 初始化栈：void init_stack(seqstack *S){    S->top = -1;    //一个元素也没有，注意因为TOP是下标而不是元素个数，用-1} 判断栈是否为空：int stack_empty(seqstack *S){    if (S->top == -1)        return 1;    else        return 0;} 取栈顶元素：elementtype stack_top(seqstack *S){    if (stack_empty(S))        error("栈为空！");    else        return S->data[S->top];} 入栈：void push_stack(seqstack *S, elementtype x){    if (S->top == MAXSIZE -1)        error("溢出！");    else        S->data[++S->top] = x;    //注意->运算符的优先级是最高的} 出栈：elementtype pop_stack(seqstack *S){    if (stack_empty(S))        error("栈为空！");    else        return S->data[S->top--];} 判断栈是否为满：int stack_full(seqstack *S){    if (S->top == MAXSIZE -1)        return 1;    else        return 0;} 总体来说，顺序栈很简单，出的时候取最后的元素，进的时候一样进在尾部。 2.链栈栈的链式存储结构称为链栈。其插入和删除操作仅限制在表头位置上进行。由于只能在链表头部进行操作，故链栈没有必要象单链表那样添加头结点。栈顶指针就是链表的头指针。结构：typedef struct node    //和一般链表的结构一样。{    elementtype data;    struct node *next;} linkstack; linkstack *top;当top=NULL时，链栈为空栈。 入栈：void push_stack(linkstack *top, elementtype x){    linkstack *P = (linkstack *)malloc(sizeof(linkstack));    P->data = x;    P->next = top->next;    top = P;} 出栈：elementype pop_stack(linkstack *top){    elementtype x;    linkstack *P;    if (top == NULL)        error("栈为空！");    else    {        x = top->data;        P = top;        top = top->next;        free(P);        return x;    }}  二、队列队列是只能在一端插入，另一端删除的线性表。特征是：先进先出，后进后出。 1.顺序队列注意顺序队列多是循环队列，这里要注意几点：(1)front是队头的前一个位置。(2)尾部入队，头部出队。(3)由于循环，任何的位置移动计算之后要取余：P = (P + 1) % MAXSIZE 。结构：#define MAXSIZE 100typedef struct{    elementtype data[MAXSIZE];    int front;    //头序号（注意是队头的前一个位置）    int rear;    //尾序号（直接指向尾元素）} seqqueue; 初始化队列：void init_queue(seqqueue *Q){    Q->front = 0;    Q->rear = 0;}还有一种写法：void init_queue(seqqueue *Q){    Q->front = MAXSIZE - 1;    Q->rear = MAXSIZE - 1;}两种方法的区别是第一种插入第一个元素是data[1]，而第二种是data[0]。 判断队列是否为空：int queue_empty(seqqueue *Q){    if (Q->front == Q->rear)        return 1;    else        return -1;} 判断队列是否为满：int queue_full(seqqueue *Q){    if ((Q->rear + 1) % MAXSIZE == Q->front)        return 1;    else        return 0;} 取队头元素：elementtype queue_front(seqqueue *Q){    if (queue_empty(Q))        error("队列为空！");    else        return Q->data[(Q->front + 1) % MAXSIZE];} 入队：void Enqueue(seqqueue *Q, elementtype x){    if (queue_full(Q))        error("队列满！");    else    {        Q->rear = (Q->rear + 1) % MAXSIZE;    //千万不能直接用Q->rear++，在循环队列要特别注意        Q->data[Q->rear] = x;    }} 出队：elementtype Outqueue(seqqueue *Q){    if (queue_empty(Q))        error("队列为空！");    else    {        Q->front = (Q->front + 1) % MAXSIZE;        return Q->data[Q->front];    }} 2.链队列出队时，删除表头操作，入队时，在表尾添加结点。（也就是头部出，尾部进）使用带头结点的单链表形式。（注意链栈是不带头结点的）结构：typedef struct mynode{    elementtype data;    mynode *next;} node;    //就是单链表typedef struct{    node *front;    node *rear;} linkqueue; 初始化队列：void init_queue(linkqueue *Q){    Q->front = (node *)malloc(sizeof(node));    //生成头结点（注意是NODE类型，Q结构是已有的一个结构，这里有点特殊，仔细体会）    Q->rear = Q->front;    Q->front = NULL;} 判断队列是否为空：int queue_empty(linkqueue *Q){    if (Q->front == Q->rear)        return 1;    else        return 0;} 取队头元素：elementtype queue_front(linkqueue *Q){    if (queue_empty(Q))        error("队列为空！");    else        return Q->front->next->data;} 入队：void Enqueue(linkqueue *Q, elementtype x){    node *P = (node *)malloc(sizeof(node));    P->data = x;    P->next = NULL;    Q->rear->next = P;    Q->rear = P;} 出队：elementtype Outqueue(linkqueue *Q){    node *P;    elmenttype x;    if (queue_empty(Q))        error("队列为空！");    else    {        P = Q->front->next;        Q->front->next = P->next;        x = P->data;        free(P);    }    if (Q->front->next == NULL)    //只剩一个结点删除后队列为空时的特殊情况，一定要注意处理        Q->rear = Q->front;    return x;}  三、数组主要是稀疏矩阵的压缩存储：当数组中非零元素非常少时，称之为稀疏矩阵。存储特别如下：(1)对稀疏矩阵压缩存储时，除了存储非零元素的值v以外，还要存储其行列号i和j，故每个元素对应一个三元组(i, j, v)。将这些元素的三元组组织起来构成三元组表。(2)需要在三元组表中增设元素个数、行列数，以唯一确定一个稀疏矩阵。 结构如下：#define MAXSIZE 100typedef struct    //三元组结构{    int i, j;    elementtype v;} tuple;typedef struct{    int mu, nu, tu;    //行数、列数、非0元素个数    tuple data[MAXSIZE];} spmatrix; 递归的应用可具体见书。# 第四章 树    2005-10-22 17:49 by wddavid 第四章 树 一、树树中的每个结点最多只有一个前驱（父辈），但可能有多个后继（后代）。一个结点的度是指该结点的孩子数目。若一个结点的度为0，称为叶子结点或终结点，否则称为分支结点或非终结点。一棵树的度是树中最大的结点的度。某个结点的子树的根称为其孩子结点，而该结点为其孩子结点的双亲结点或父结点。同一个结点的孩子互相称为兄弟结点。根的层次为1，其余结点的层次为父结点的层次数加1，而最大的层次数称为树的高度或深度。如果树中各兄弟结点之间的排列次序是无关的，则称之为有序树，否则称为无序树。称多棵树为森林。 二、二叉树二叉树和树一样，都可以为空树。注意二叉树每个结点的孩子都有左右之分，每个结点都有左右两个子树，这与树结构明显不同。二叉树和树本质上是完全不同的两种结构。 定义：满二叉树是指每层都有最大数目结点的二叉树，即高度为k的满二叉树中有2k-1个结点。而完全二叉树则是指在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。 二叉树的性质：1.在二叉树的第i层上的结点个数<=2i-1(i>0) 2.深度（高度）为k的二叉树的结点个数<=2k-1 3.对任一棵非空的二叉树，如果其叶子数为n0, 度为2的结点数为n2, 则有下面的关系式成立：n0=n2+1 (这个性质很重要。主要是有个概念：除去根结点，每个结点都与一个它上面的分支一一对应，也就是说，结点数＝分支数＋1，所以有：n-1=n1+2*n2) 4.有n个结点的完全二叉树(n>0)的深度为[log2n]+1([]为取整)5.在编号的完全二叉树中，各结点的编号之间的关系为：编号为i的结点如果存在左孩子，则其编号为2i，如果存在右孩子，则其编号为2i+1，如果存在父结点，则其编号为[i/2]。 二叉树的存储结构：1.顺序存储结构：按完全二叉树的编号次序进行，即编号为i的结点存储在数组中下标为i的元素中。缺点：若二叉树不是完全二叉树，则为了保持结点之间的关系，不得不空出许多元素来，这就造成了空间的浪费。 2.二叉链表存储结构：typedef struct node{    datatype data;    struct node *lchild, *rchild;} bitree; 三、二叉树的遍历：所谓遍历二叉树是指按某种次序访问二叉树中每个结点一次且仅一次。根据访问根结点的次序，可以分为先序遍历，中序遍历，后序遍历。先序遍历可描述为：若二叉树T不为空：(1)访问T的根结点；(2)先序遍历T的左子树；(3)先序遍历T的右子树。遍历的算法非常简单，只写出先序遍历算法：void preorder(bitree *T){    if (T != NULL)    {        visit(T);    //一般用的最多的就是输出        preorder(T->lchild);        preorder(T->rchild);    }} 四、线索二叉树线索二叉树主要是为了求解在某种次序下的前驱或后继结点。将二叉树各结点中的空的左孩子指针域改为指向其前驱，空的右孩子指针域改为指向其后继。称这种新的指针（前驱或后继）为线索，所得到的二叉树被称为线索二叉树，将二叉树转变成线索二叉树的过程称为线索化。同时，为了区分到底指针是指向前驱（后继）还是孩子，要加入两个标志来判断。结构：typedef struct node{    int ltag, rtag;    //0为孩子，1为前驱或后继    datatype data;    struct node *lchild, *rchild;} ordertree; 先序后继的求解：ordertree *presuc(ordertree *P){    if (P->ltag == 0)        return P->lchild;    else        return P->rchild;}中序后继：ordertree *insuc(ordertree *P){    ordertree *q = P->rchild;    if (P->rtag == 1)        return q;    else    {        while (q->ltag == 0)            q = q->lchild;        return q;    }}中序先驱：ordertree *infore(ordertree *P){    ordertree *q = P->lchild;    if (P->ltag == 1)        return q;    else    {        while (q->rtag == 0)            q = q->rchild;        return q;    }}后序先驱：ordertree *postfore(ordertree *P){    if (P->rtag == 0)        return P->rchild;    else        return P->lchild;} 五、树和森林 1.树的存储结构：(1)双亲表示法struct tnode{    datatype data;    int parent;}struct tnode treelist[MAXSIZE];    //整个树的存储数组说明其中parent指示该结点父结点的下标，data存放结点的值。优点：便于搜索相应结点的父结点和祖先结点。缺点：若要搜索孩子结点或后代结点需要搜索整个表，浪费时间。 (2)孩子链表表示法分别将每个结点的孩子结点连成一个链表，然后将各表头指针放在一个表中构成一个整体结构。typedef struct node    //链表中每个孩子结点的定义{    int data;    struct node *next;} listnode;typedef struct    //数组元素的定义，每个数组元素都是一个单链表，单头元素不同{    datatype info;    listnode *firstchild;} arrnode;arrnode tree[MAXSIZE];    //MAXSIZE为所有结点的个数优缺点：与双亲表示法恰好相反。 (3)孩子－兄弟链表表示法（二叉链表表示法，二叉树表示法）树中每个结点用一个链表结点来存储，每个链表结点中除了存放结点的值外，还有两个指针，一个用来指示该结点的第一个孩子，另一个用于指示该结点的下一个兄弟结点。typedef struct node{    datatype data;    struct node *firstchild, *nextbrother;} tnode; 2.树（森林）与二叉树的转换树或森林的子树转换为二叉树的左子树，兄弟转化为右子树。 3.树（森林）的遍历树的遍历可分为先序遍历和后序遍历。（注意没有中序，因为树有不只两个孩子）即结点是在其子树之前还是之后访问。遍历树（森林）要转换为遍历其对应的二叉树：先序遍历：（同二叉树的先序遍历）void preorder(tnode *T){    if (T != NULL)    {        visit(T);        preorder(T->firstchild);        preorder(T->nextbrother);    }}后序遍历：（同二叉树的中序遍历）void postorder(tnode *T){    if (T != NULL)    {        postorder(T->firstchild);        visit(T);        postorder(T->nextbrother);    }} 六、哈夫曼树哈夫曼树主要用来处理压缩算法。 一般的判断问题的流程就象是一棵二叉树，其中分支（判断）结点对应于二叉树的分支结点；而最后得出的结论对应于叶子结点；一个结论所需要的判断次数是从根结点到该叶子结点的分支线数（层次数-1）；每个结论成立的次数作为叶子结点的权值。(这个权值可能比较少接触,但是其实它非常重要,因为我们平时设计的系统,判断的结果常常都是通过长年的实践会有一个出现机率分配,而不可能是平分的,比如考试,如果常常80-90分的比较多,也许就要换一种算法,当然这是后话,和考试无关了.) 哈夫曼算法步骤如下:(1)根据给定的n个权值,构成一排结点T,每个的值都是相应的权值.(2)从T中选两棵权值最小的二叉树,作为左右子树构成一棵新的二叉树T',并且新二叉树的权值为左右子树权值之和.(3)将新二叉树T'并入到T中,删除原来的两棵二叉树.(4)重复2,3直到只剩一棵二叉树.这棵树就是哈夫曼树. 哈夫曼树的带权路径长度WPL=∑wL即所有叶子结点的 权值*比较次数(层次数-1) 之和.而WPL也正好等于所有分支结点(不包括叶子结点)的值之和.# 第五章 图    2005-10-25 23:16 by wddavid 第五章 图图中将每个对象用一个顶点表示，并常用一个序号来标识一个顶点。其中弧表示单向关系，边表示双向关系，用离散数学中的术语来说，则分别表示为非对称关系和对称关系。弧用表示（A为尾，B为头），边用(A, B)表示。一个图G由两部分内容构成，即顶点(vertex)集合(V)和边(或弧edge)的集合(E)，并用二元组(V, E)来表示，记做G = (V, E) 根据顶点间的关系是否有向而引入有向图和无向图。 给每条边或弧加上权值，这样的带权图称为网络。若无向图中任意两点间都有一条边，则称此图G为无向完全图。(共有边数 n*(n-1)/2 )若有向图中任意一个顶点到其余各点间均有一条弧，则称为有向完全图。(共有弧数 n*(n-1) ) 若一个图G1是从G中选取部分顶点和部分边（或弧）组成，则称G1是G的子图。（注意，顶点和边必须都为子关系） 若无向图中两个顶点i, j之间存在一条边，则称i, j相邻接，并互为邻接点。在有向图中，若存在弧，也做Vi, Vj相邻接，但为区别弧的头、尾顶点，可进一步称做Vi邻接到Vj，Vj邻接于Vi。 与一个顶点相邻接的顶点数称为该顶点的度。在有向图中，进入一个顶点的弧数称为该顶点的入度，从一个顶点发出的弧数为该顶点的出度，并将入度和出度之和作为该顶点的度。 一个顶点经过一定的可经路程到达另一个顶点，就为顶点之间的路径。若某路径所经过的顶点不重复，则称此路径为简单路径。若某路径的首尾相同，则称此路径为回路（或称为环）。若某回路的中间不重复，则称之为简单回路。 若无向图中任意两点之间均存在路径，则称G为连通图，否则不连通，就存在若干个连通分量。若有向图中任意两点间可以互相到达，则称为强连通图。 一个无向图，连通并且无回路，称这样的图为树。若有向图中仅有一个顶点的入度为0，其余顶点的入度都为1，称此图为有向树，入度为0的顶点为根。 图的存储结构：1。邻接矩阵表示对n个顶点的图来说，其邻接矩阵为n*n阶的。邻接矩阵的元素存放边（弧）的权值，对不存在的边（弧），则用0或∞表示。定义格式如下：#define n 6    /* 图顶点数 */ #define e 8    /* 图的边（弧）数 */ typedef struct{    vextype vexs[n];    /* 顶点类型 */    datatype arcs[n][n];    /* 权值类型 */} graph; 建立一个无向网络的算法： CreateGraph(graph *G) {     int i, j, k;     float w;     for (i=0; i

评论