数据结构CLUB

typedef struct arcnode

{int adjvex;

struct Arcnode *nextarc;

}Arcnode;

 

typedef struct vnode

{char data;

Arcnode *firstarc;

}Vnode;

 

typedef struct

{Vnode vertices[MAX];

int vexnum,arcnum;

}ALGraph;

 

int locatevex(...

typedef struct{
 char vexs[MAX];
 int arcs[MAX][MAX];
 int vexnum,arcnum;
}MGraph;  // 以邻接矩阵作为图的存储结构

int Locatevex(MGraph *G,char v)
{ int i;
  for(i=0;ivexnum;++i)
   if(G->vexs[i]==v)  ret...

1.图的邻接矩阵建图算法

Status CreateUDG ( MGraph &G ) {

//采用数组（邻接矩阵）表示法，构造无向图G。

  scanf ( &G. vexnum, &G. arcnum );   

  for ( i = 0; i < G. vexnum; ++i )  scanf ( &G. v...

 1.假设一棵二叉树的前序遍历序列为EBADCFHGIKJ,中序遍历序列为ABCDEFGHIJK，试画出该二叉树并按后序线索化（用虚线表示线索）。

2.将下列森林转换为相应的二叉树，并写出此二叉树的中序遍历序列。
 

3.假定用于通信的电文仅由8个字符C1，C2，C3，C4，C5...

#include "stdio.h"
#include "stdlib.h"

typedef char TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BitNode,*BiTree;

void createBitree(BiTree &T)
{char ch;
ch=getchar(...

#include "stdio.h"
#include "stdlib.h"
#define SqStack_INIT_SIZE 100
#define SqStackINCREMENT 10
typedef char TElemType;
typedef struct BiTNode{
    TElemType data;
    struct BiTNode *lchild,*rchild;
}BitNode,*BiTree...

1、统计二叉树中叶子结点的个数。

void CountLeaf (BiTree T, int &count)

{

  if ( T ) {

    if ((!T->lchild)&& (!T->rchild))

       count++;

    CountLeaf( T->...

1.删除元素递增排列的链表L中所有值相同的元素。

int f1(LinkList L) {

 p=L->next;

 while(p->next) {

    q=p->next;

    if(p->data!=q->data)

       p=p->next...

1、写出下列程序段的功能是什么？

 (1)  void demo1(seqstack *s){

        int i;  arr[64];  n=0;

        while (!stackempty(s))   arr[n++]=pop(s);
...

int locatevex(algraph *g,char c)
{int i;
 for(i=0;i<=g->vexnum;i++)
   if(g->vertices[i].data==c)
     return i;
 return -1;
}


int firstadjvex(algraph *g,...

typedef struct{
 char vexs[MAX];
 int arcs[MAX][MAX];
 int vexnum,arcnum;
}MGraph;  // 以邻接矩阵作为图的存储结构

int Locatevex(MGraph *G,char v)
{ int i;
  for(i=0;i<G->vexnum;++i)
&nbs...

1.图的邻接矩阵建图算法

Status CreateUDG ( MGraph &G ) {

//采用数组（邻接矩阵）表示法，构造无向图G。

  scanf ( &G. vexnum, &G. arcnum );  

  for ( i = 0; i < G. vexnum; ++i )  scanf ( &G...

1.假设一棵二叉树的前序遍历序列为EBADCFHGIKJ,中序遍历序列为ABCDEFGHIJK，试画出该二叉树并按后序线索化（用虚线表示线索）。

树遍历算法的应用

1、求树的深度的算法：

int TreeDepth(CSTree T) {

  if(!T) return 0;

  else {

     h1 = TreeDepth( T->firstchild );

     h2 ...

1、统计二叉树中叶子结点的个数。

void CountLeaf (BiTree T, int &count)

{

  if ( T ) {

    if ((!T->lchild)&& (!T->rchild))

       count...

串的首尾匹配算法

    先比较模式串的第一个字符，再比较模式串的最后一个字符，最后比较模式串中从第二个到第n-1个字符。

int Index_FL(SString S, SString T, int pos) {

  sLength = S[0];  tLength = T[0];  i = pos;

  patStart...

1、指出下列程序段的功能是什么？

 (1)  void demo1(seqstack *s){

        int i;  arr[64];  n=0;

        while (!stackempty(s))   a...

以下就分"如何按后缀式进行运算"和"如何将原表达式转换成后缀式"两个问题进行讨论。

n       如何按后缀式进行运算？

可以用两句话来归纳它的求值规则："先找运算符，后找操作数。“

   运算过程为：对后缀式从左向右"扫描"，遇见操作数则暂时保存，遇见运算符即可进行运算；此时参加运算的两个操作数应该是在它之前刚刚碰到的两个操作数...

算法的设计思想：

1. 凡出现左括弧，则进栈

2. 凡出现右括弧，首先检查栈是否空

    若栈空，则表明右括号多了

    否则和栈顶元素比较

              ...

简述以下算法的功能。

 

(1) Status A(LinkedList L) { // L 是无表头结点的单链表
　　　　if (L && L->next){
　　　　　Q =L; L =L->next; P =L ;
　　　　　while ( P->next) P =P->next ;
　　　　　P->next =Q; Q->next = N...

 设n为正整数，求下列算法段的时间复杂度，即T(n)=？

(1) i=1; k=0;
  while ( i<=n-1) {
　 k += 10 * i;
　 i++;
  }

 

(2) k=0;
　  for( i=1; i<=n; i++) {
　　 for (j=i ; j<=n; ...

答疑地点：南校区实验楼五层系办公室（电话：2033957）
答疑时间：周一至周五上班时间均可
其他方式：
              Email- datastructure2008@163.com
           &...

【学习目标】
　　1．理解排序的定义和各种排序方法的特点，并能加以灵活应用。排序方法有不同的分类方法，基于"关键字间的比较"进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。
　　2．掌握各种排序方法的时间复杂度的分析方法。能从"关键字间的比较次数"分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分为三类：O (n2) 的简单排序方法，O (n·...

【学习目标】
　　1．理解"查找表"的结构特点以及各种表示方法的适用性；
　　2．熟练掌握以顺序表或有序表表示静态查找表时的查找方法；
　　3．熟练掌握二叉查找树的构造和查找方法；
　　4．理解二叉平衡树的构造过程；
　　5．熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；
　　6．掌握描述查找过程的判定树的构造方法，以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。
【重...

编者按：2009年是计算机专业考研专业基础课首次实行全国统考，面对今年的改变，想报考计算机专业的考生可能对复习的准备有很多的疑问。为了帮助考生正确的做好准备工作，学赛网研究生院特访问了我国著名的计算机教育专家、湖南师范大学计算机软件与理论/计算机应用技术硕士点专业课试题命题人张友生博士，请张博士对考试大纲进行全面的解析。本文为大纲解析的第二篇：数据结构知识点分析。
    在计算机考研专业基础课统考科目中，一共考查数据结构、操作系统、计算机组成原理、计算机网络...

Status Build_AdjList(ALGraph &G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表
{InitALGraph(G);
  scanf("%d",&v);
  if(v<0)   return ERROR; //顶点数不能为负
  G.vexnum=v;
  scanf(&...

typedef struct        {   int u;     /*边的起始顶点*/            int v;     /*边的终止顶点*/        ...

【学习目标】
　　1．领会图的类型定义。
　　2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。
　　3．熟练掌握图的两种遍历算法。
　　4．理解各种图的应用问题的算法。
【重点和难点】
　　图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。
【知识点】
　　图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、最小生成树、拓扑...

#define P 4
#define N 5
#define MAXSIZE 10
typedef struct
  { int i,j;
    int  e;
  }Triple;
typedef struct
  { Triple data[MAXSIZE+1];
    int mu,nu,tu;...

#define M 250
#include "stdio.h"
#include  "string.h"
typedef  char   SString;
int Index (SString S[M],SString T[M],int pos,int m,int n)
{ int i,j;
  i=pos-1;
  j=0;...