Board logo

标题: [数据结构（C语言版）]数据结构 模板 [打印本页]
作者: 一生逍遥    时间: 2006-10-28 11:37     标题: [数据结构（C语言版）]数据结构 模板

[color=#B22222]线性表： 线性表基本运算 (1)置空表setnull(L) 将线性表L置成空表。 (2)求长度length(L) 求给定线性表L中数据元素的个数。 (3)取元素get(L,i) 若i<=length(L)，则结果是线性表L中的第i个数据元素，否则为空元素null，i表示位序。 (4)定位函数locate(L,x) 当线性表中存在一个值为x的数据元素，则结果是该数据元素在表中的位序，否则，将给出一个值，表示值为x的数据元素不存在。如果线性表中值为x的数据元素不止一个，则结果是第一次找到的数据元素的位序。 (5)前趋函数prior(L,x) 若x为线性表L中的一个数据元素，且其位序大于1，则结果为L的直接前趋。否则，给出一个特殊值示出该元素无前趋。 (6)后继函数next(L,x) 若x为线性表L中的一个数据元素，且其位序小于length(L)，则结果为该元素的后继，否则，给出一个特殊值示出该元素无后继。 (7)插入insert(L,x,i) 若1<=i<=length(L)+1时，则在线性表L中的第i个位置插入一个值为x的新元素，使运算前长度为n的线性表变为长度为n+1的线性表。 (8)删除delete(L,i) 若1<=i<=length(L)时，则结果为删除线性表L中的第i个元素，使运算前长度为n的线性表变为长度为n-1的线性表。
作者: 一生逍遥    时间: 2006-10-28 11:38     标题: [数据结构（C语言版）]数据结构 模板

顺序表： 定义： #define maxsize maxlen; typedef int elemtype; typedef struct {elemtype vec[maxlen]; int len;} sequenlist; 插入： int insert(L,x,i) sequenlist *L; int i; {int j; if(((*L).len)>=maxlen-1) {printf("the list is overflow!\n") return Null;} else if((i<1)||(i>(*L).len+1)) {printf("position is not correct!\n"); return Null; } else {for(j=(*L).len;j>=i-1;j--) (*L).vec[j+1]=(*L).vec[j]; (*L).vec[i-1]=x; (*L).len=(*L).len+1; } return(1); } 删除： void delete(L,i) sequenlist *L; int i,*y; {int j; if((i<1)||(i>(*L).len+1)) printf("delete fail\n"); else {*y=(*L).vec[i-1]; for(j=i;j<=(*L).len;j++) (*L).vec[j-1]=(*L).vec[j]; (*L).len-- } }
作者: 一生逍遥    时间: 2006-10-28 11:39     标题: [数据结构（C语言版）]数据结构 模板

单链表： 定义： typedef int elemtp; typedef struct node {elemtp data; struct node *next;} linklist； linklist *head,*p; 建立单链表：带头结点 linklist *creatlist() {char ch; int x; linklist *head,*r,*p; p=malloc(sizeof(linklist)); head=p; p->next=Null; r=p; ch=getchar(); while(ch!=';?';) {scanf("%d",&x); p=malloc(sizeof(linklist)); p->data=x; p->next=Null; r->next=p; r=r->next; ch=getchar(); } return(head); } 建立单链表：不带头结点 linklist *creatlist() {char ch; int x; linklist *head,*p,*r; head=Null; r=Null; ch=getchar(); while(ch!=';?';) {p=malloc(sizeof(linklist)); scanf("%d",&x); p->data=x; if(head==Null) head=p; else r->next=p; r=p; ch=getchar(); } if(r!=Null) r->next=Null; return head; } 查找：按值查找 linklist *locate(head,k) linklist *head; elemtp k; {linklist *s; s=head->next; while(s!=Null) if(s->data!=k) s=s->next; else break; return s; } 查找：按序号查找 linklist *Get(head,i); linklist *head; int i; {int j; linklist *p; p=head;j=0; while((p->next!=Null)&&(i>j)) {p=p->next; j++; } if(i==j) return p; else return Null; } 插入： insert(p,x)/*将值为x的新结点插入*p之后*/ linklist *p; elemtp x; {linklist *s; s=malloc(sizeof(linklist)); s->data=x; s->next=p->next; p->next=s; } void insert(head,x,k)/*在单链表中值为k的结点之前插入一个值为x的新结点*/ linklist *head; int x,k; {linklist *q,*p,*r; r=malloc(sizeof(linklist)); r->data=x; if(head->next==Null) {head->next=r; r->next=Null; } else {q=head->next; p=head->next->next; while(p!=Null) {if(p->data!=k) {q=p; p=p->next;} else break; if(p!=Null) {q->next=r; r->next=p;} else {q->next=r; r->next=Null;} } } } 删除： delete(p) /*删除*p结点的后继*/ linklist *p; {linklist *r; r=p->next; p->next=r->next; free(r);} linklist *delete(head,i)/*删除单链表head的第i个结点*/ linklist *head,*s; int i; {int j=0; linklist *p,*q; p=head; while((p->next!=Null)&&(jnext;j++;} if(p->next==Null) {q=p->next; p->next=p->next->next; free(q); } else return Null; s=head; return s; }
作者: 一生逍遥    时间: 2006-10-28 11:39     标题: [数据结构（C语言版）]数据结构 模板

循环链表：
只要将单链表算法中出现的Null改为head
作者: 一生逍遥    时间: 2006-10-28 11:40     标题: [数据结构（C语言版）]数据结构 模板

双向循环链表 定义： typedef struct dupnode {elemtp data; struct dupnode *next,*prior;} dulinklist; dulinklist *head; 插入:有头结点 void insdulist(head,i,x)/*在双向循环链表head中的第i个结点之前插入值为x的新结点*/ dulinklist *head; int i; elemtp x; {dulinklist *p,*s; int j; p=head; j=0; while((p->next!=head)&&(jnext; j++;} if((i>0)&&(j=i-1)) {s=malloc(sizeof(dulinklist)); s->data=x; s->next=p->next; s->prior=p; p->next=s; p->next->prior=s; } else printf("error\n"); } 删除： void deledulist(head,i) dulinklist *head; int i; {dulinklist *p; int j; p=head; j=0; while((p->next!=head)&&(jnext; j++;} if((i>0)&&(j==i)) {p->prior->next=p->next; p->next->prior=p->prior; free(p);} else printf("error\n"); }
作者: 一生逍遥    时间: 2006-10-28 11:42     标题: [数据结构（C语言版）]数据结构 模板

线性表，模板：
作者: 风灵风之子    时间: 2006-10-28 20:39     标题: [数据结构（C语言版）]数据结构 模板

:)
我以前写过C++版发到这里
作者: 一生逍遥    时间: 2006-10-29 12:09     标题: [数据结构（C语言版）]数据结构 模板

再起个帖子吧。。。也给个rar我下来看看。。。算是给我做个辅导
作者: 一生逍遥    时间: 2006-10-29 14:53     标题: [数据结构（C语言版）]数据结构 模板

栈基本运算：
(1)初始化栈：inistack(s)
将栈s置成空栈，建立起栈顶指针。
(2)进栈：push(s,x)
s为已知栈，若s未满，则将x插入栈顶，并使栈顶指针指向x，函数返回true；否则出错，函数返回false值。
(3)出栈：pop(s)
s为已知栈，若s非空，则函数返回栈顶元素，且从栈中删去栈顶元素；否则函数返回空元素值Null。
(4)取栈顶元素：gettop(s)
s为已知栈，若s非空，则函数返回栈顶元素；否则函数返回空元素值Null。
(5)判栈空：empty(s)
若s为空栈，则函数true值，否则返回false值。
作者: 一生逍遥    时间: 2006-10-29 14:54     标题: [数据结构（C语言版）]数据结构 模板

顺序栈 定义： #define MAXNUM 100 typedef struct {elemtype stack[MAXNUM]; int top;} sqstktp; sqstktp *s; 初始化栈算法： void inistack(sqstktp *s) {s->top=1;} 进栈算法： #define ture 1 #define false 0 int push(sqstktp *s,elemtype x) {if(s->top>=MAXNUM-1) return(false); else {s->stack[++s->top]=x; return(true); } } 出栈算法： elemtype pop(sqstktp *s) {if(s->top<0) return(Null); else {s->top--; return(s->stack[s->top+1]);} } 取栈顶元素算法： elemtype gettop(sqstktp *s) {if(s->top<0) return(Null); else return(s->stack[s->top];) } 判栈空算法： int empty(sqstktp *s) /*int? boolean?*/ {if(s->top<0) return(true); else return(false); }
作者: 一生逍遥    时间: 2006-10-29 14:54     标题: [数据结构（C语言版）]数据结构 模板

顺序栈两栈共享空间： 定义： typedef struct {elemtype stack[m]; int top[2];} dustktp; 初始化算法： void inistack(dustktp *s) {s->top[0]=-1; s->top[1]=m; } 进栈算法： int push(dustktp *s,int i,elemtype x) {if(s->top[0]==s->top[1]-1) {printf("栈已满"); return(False);} if(i!=0||i!=1) {printf("栈参数出错"); return(False);} if(i==0) s->stack[++s->top[0]]=x; else s->stack[++s->top[1]]=x; return(True); } 出栈算法： elemtype pop(dustktp *s,int i) {if(i!=0||i!=1) {printf("栈参数出错"); return(false);} if(i==0) {if(s->top[0]<=-1) {printf("0号栈已空"); return(Null);} else {s->top[0]--; return(s->stack[s->top[0]+1]);} } else if(s->top[1]==m) {printf("1号栈已空"); return(Null);} else {s->top[1]++; return(s->stack[s->top[1]-1]);} }
作者: 一生逍遥    时间: 2006-10-29 14:55     标题: [数据结构（C语言版）]数据结构 模板

单链栈
定义：
typedef struct node
{elemtype data;
struct node *next;} linkstktp;
linkstktp *top;
进栈算法：
void push(linkstktp *top,elemtype x)
{linkstktp *p;
p=(linkstktp *)malloc(sizeof(linkstktp));
p->data=x;
p->next=top->next;
top->next=p;}
出栈算法：
elemtype pop(linkstktp *top)
{linkstktp *p;
elemtype x;
p=top->next;
if(p=Null)
   {printf("栈已空");
    return(Null);}
else
   {top->next=p->next;
   x=p->data;
   free(p);
   return(x);
   }
}
作者: 一生逍遥    时间: 2006-10-29 14:56     标题: [数据结构（C语言版）]数据结构 模板

队列基本运算：
(1)初始化队列：iniqueue(Q)
设置一个空的队列Q。
(2)入队列：enqueue(Q,X)
Q为已知队列，在队尾加入数据元素X，使X成为新的队尾元素。
(3)出队列：dlqueue(Q)
Q为已知队列，若Q非空，则删除队头元素，并返回该队头元素，再设置其后继元素为新的队头元素；否则返回空元素值Null
(4)取队头元素：gethead(Q)
Q为已知队列，若Q非空，则返回队头元素；否则返回空元素值Null
(5)判队列空；empty(Q)
若队列Q为空，则返回true，否则返回false
作者: 一生逍遥    时间: 2006-10-29 14:56     标题: [数据结构（C语言版）]数据结构 模板

顺序队列
定义：
typedef struct
{elemtype queue[MAXSIZE];
int front,rear;} sequeuetp;
初始化算法：
void iniqueue(sequeue *s)
{s->front=-1;
s->rear=-1;}
入队列算法：
int enqueue(sequeuetp *s,elemtype x)
{if(s->rear==MAXSIZE-1)
return(false);
else
  {s->queue[++s->rear]=x;
   return(true);
  }
}
出队列算法：
elemtype dlqueue(sequeuetp *s)
{if(s->front==s->rear)
   return(Null);
else
   {return(s->queue[++s->front];)}
}
作者: 一生逍遥    时间: 2006-10-29 14:57     标题: [数据结构（C语言版）]数据结构 模板

循环队列
入队列算法：
int encycque(sequeuetp *s,elemtype x)
{if((s->rear+1)%MAXSIZE==front)
   return(false);
else
   {s->rear=(s->rear+1)%MAXSIZE;
    s->queue[s->rear]=x;
    return(true);}  
}

出队列算法：
elemtype dlcycque(sequeuetp *s)
{if(s->front==s->rear)
   return(Null);
else
  {s->front=(s->front+1)%MAXSIZE;
  return(s->queue[s->front]);
  }
}
作者: 一生逍遥    时间: 2006-10-29 14:58     标题: [数据结构（C语言版）]数据结构 模板

队列的链式存储
定义：
typedef struct node
{elemtype data;
struct node *next;}  queueqtr;
typedef struct
{queueptr *front,*rear;} linkedquetp;

初始化算法：
void inilinkedque(linkedquetp *s)
{s->front=(queueptr *)malloc(sizeof(queueptr));
s->rear=s->front;
s->front->next=Null';
}
入队列算法：
void enlinkedque(linkedquetp *s,elemtype x)
{queueptr *p;
p=(queueptr *)malloc(sizeof(queueptr));
p->data=x;
p->next=Null;
s->rear->next=p;
s->rear=p;
}
出队列算法：
elemtype dllinkedque(linkedquetp *s)
{queueptr *p;
if(s->front==s->rear)
   return(Null);
else
   {p=s->front;
    s->front=s->front->next;
    free(p);
    return(s->front->data);}
}
作者: 一生逍遥    时间: 2006-10-29 15:00     标题: [数据结构（C语言版）]数据结构 模板

[color=&#35;DC143C]栈和队列
作者: 一生逍遥    时间: 2006-10-30 15:35     标题: [数据结构（C语言版）]数据结构 模板

[color="ffffff"]串 基本运算： StrAssign(&t,chars) 初始条件：chars是字符串常量。 操作结果：生成一个其值等于chars的串t。 StrCopy(&t,s) 初始条件：串s存在。 操作结果：由串s复制得串t。 StrEpty(s) 初始条件：串s存在。 操作结果：若s为空串，则返回TRUE，否则返回FALSE。 StrCompare(s,t) 初始条件：串s和串t存在。 操作结果：若s>t，则返回值>0；若s=t，则返回值=0；若s 作者: 一生逍遥    时间: 2006-10-30 15:37     标题: [数据结构（C语言版）]数据结构 模板

[color="FFFFFF"]串的实现 定义： #define STRINGMAX 81 struct string {int len; static char ch[STRINGMAX];}; typedef struct string STRING; 初始化： void ClearString(s) STRING *s; {int i; for(i=0;i='; ';; (*s).len=0; } 从文本文件f上读入一串字符到串变量s中： #include "stdio.h" void readstring(s,f) STRING *s; char f[]; {FILE *fp; int i=1; ClearString(s); if((fp=fopen(f,"r"))=Null) {printf("不能打开此文件\n"); exit(0); } while(((*s).ch=fgetc(fp)!=eof)&&(i<(STRINGMAX-1))) {(*s).len++; i++; } (*s).ch=';\0';; close(fp); } 求串长： int StrLength(s) STRING *s; {return((*s).len);} 串的联接： Status concat(&t,s1,s2) STRING *t,*s1,*s2; {int j,k; if((*s1).len+(*s2).len>=(STRINGMAX-1)) printf("t串超长\n") else {将s1前s1.len个转移到t； 将s2前s2.len个转移到t中的s1后； (*t).len=(*s1).len+(*s2).len; } } 求子串： void substring(&t,s,pos,len) STRING *t,*s; int pos,len; {int i; if((pos<1)||(pos)>(*s).len)||(len<0)||(len>(*s).len-pos+1) printf("pos或len超界\n"); else {(*t).ch[1..len]=(*s).ch[pos..pos+len-1]; (*t).len=len; } } 子串的插入： void StrInsert(s,pos,t) STRING *s,*t; int pos; {if((*t).len>0) if((pos>0)&&(pos<=(*s).len+1)) if((*s).len+(*t).len<(STRINGMAX-1)) {(*s).ch[pos+(*t).len..(*s).len+(*t).len]=(*s).ch[pos..(*s).len]; (*s).ch[pos..pos+(*t).len-1]=(*t).ch[1..(*t).len]; (*s).len=(*s).len+(*t).len; } else printf("t串超长\n"); else printf("pos位置不合适\n"); else printf("t串是空串\n"); } 字串的删除： 略 串的置换： void replace(s,t,v) STRING *s,*t,*v; {int index1,p,m,n,p; n=(*s).len; m=(*t).len; q=(*v).len; p=1; do {index1=index(s,t,p); if(index1!=0) { StrDelete(s,index1,m); StrInsert(s,index1,v); p=index1+q; (*s).len=(*s).len+q-m; n=(*s).len; } } while((p<=n-m+1)&&(index1!=0)); } 求子串位置： int Index(s,t,pos) STRING *s,*t; int pos; {int i,j; if((pos<1)||(pos+(*t).len>(*s).len+1)||((*t).len==0)) return(0); else {i=pos;j=1; while((i<=(*s).len)&&(j<=(*t).len)) {if ((*s).ch==(*t).ch[j]) {i++;j++;} else {i=i-j+2;j=1;} } if(j>(*t).len) return i-(*t).len; else return(0); } } 更好的匹配算法，求子串位置： int index_kmp(s,t,pos) STRING *s,*t; int pos; {if((pos<1)||(pos+(*t).len>(*s).len+1)||((*t).len==0)) return(0); else {i=pos;j=1; while((i<=(*s).len)&&(j<=(*t).len)) {if((j==0)||(s==t[j]) {++i;++j;} else j=next[j]; } if(j>(*t).len) return(i-(*t).len) else return(0); } } next函数： void get_next(t,int &next[]) STRING *t; {i=1;next[1]=0;j=0; while(i<(*t).len) {if((j=0)||((*t).ch==(*t).ch[j])) {++i;++j;next=j;} else j=next[j]; } } 更好的next函数： void get_nextval(t,int &next[]) STRING *t; {i=1;nextval[1]=0;j=0; while(i<(*t).len) {if((j=0)||((*t).ch==(*t).ch[j])) {++i;++j;nextval=j; if((*t).ch!=(*t).ch[j]) nextval=j; else nextval=nextval[j]; } else j=nextval[j]; } }
作者: 一生逍遥    时间: 2006-10-30 15:49     标题: [数据结构（C语言版）]数据结构 模板

串：
作者: 一生逍遥    时间: 2006-10-31 20:20     标题: [数据结构（C语言版）]数据结构 模板

[color=#DC143C]数组和广义表 三元组顺序表： 定义： #define maxsize 1000 typedef struct {int i,j; datatype v; } node; typedef strcut {int mu,nu,tu; node data[maxsize]; } matrix; 求a的转置矩阵： matrix transmatrix(a) matrix *a; {int am,bn,col; matrix *b; b=(matrix)malloc(sizeof(matrix)); b.mu=a.nu; b.nu=a.mu; a.tu=b.tu; bn=0; for(col=0;col 作者: 一生逍遥    时间: 2006-10-31 20:20     标题: [数据结构（C语言版）]数据结构 模板

十字链表 定义： typedef struct node {int i,j; struct node *down,*right; union {struct node *next; datatype v;} val; } linklist; 建表： linklist *creatcrosslink() {linklist *p,*q,*h,*cp[smax]; int i,j,m,n,t,s; datatype v; sacnf("%d%d%d",&m,&n,&t); if(m>n) s=m; else s=n; h=malloc(sizeof(linklist)); h->i=m;h->j=m; cp[0]=h; for(i=1;i<=s;i++) {p=malloc(sizeof(linklist)); p->i=0;p->j=0; p->right=p; p->down=p; cp=p; cp[i-1]->val.next=p; } cp->val.next=h; for(i=1;i<=t;i++) {scanf("%d%d%d",&i,&j,&v) p=malloc(sizeof(linklist)); p->i=i;p->j=j;p->val.v=v; q=cp; while((q->right!=cp)&&(q->right->jright; p->right=q->right; q->right=p; q=cp[j]; while((q->down!=cp[j])&&(q->down->idown; p->down=q->down; q->down=p; } return h; } 一个插入函数： insert(crow,ccol,cval,cp) int crow,ccol,cval; linklist *cp[smax]; {linklist *s,*last; s=malloc(sizeof(linklist)); s->i=crow;s->j=ccol;s->v=cval; last->right=s;last=s; cp[ccol]->next->down=s; cp[ccol]->next=s; } 加法运算： linklist *matrixadd(a,b,c,cp) linklist *a,*b,*c,*cp[smax]; {int n,i,arow,brow; linklist *last,*arow,*brow,*s,*pa,*pb; c=malloc(sizeof(linklist)); c->i=a->i;c->j=a->j; if(a->i>a->j) n=a->i; else n=a->j; cp[0]=c; for(i=1;i<=n;i++) {s=malloc(sizeof(linklist)); s->i=0;s->j=0; s->right=s;s->down=s; sp=s; } arow=a->next;brow=b->next; last=cp[0]; i=0; while((arow!=a)&&(brow!=b)) {pa=arow->right;pb=brow->right; while((pa!=arow)&&(pb!=brow)) { if(pa->j==pb->j) {if(pa->v+pb->v!=0) insert(pa->i,pa->j,pa->v+pb->v); pa=pa->right;pb=pb->right; } else if(pa->j>pb->j) {insert(pb->i,pb->j,pb->v); pb=pb->right; } else {insert(pa->i,pa->j,pa->v); pa=pa->right; } } while(pa!=arow) {insert(pa->i,pa->j,pa->v); pa=pa->right;} while(pb!=arow) {insert(pb->i,pb->j,pb->v); pb=pb->right; } last->right=cp; i++; last=cp; arow=arow->next;brow=brow->next; } for(i=1;i<=c->j;i++) cp->next->down=cp; for(i=1;i<=n-1;i++) cp->next=cp[i+1]; if(n==0) c->next=c; else {cp[n]->next=c; c->next=cp[1]; } }
作者: 一生逍遥    时间: 2006-10-31 20:21     标题: [数据结构（C语言版）]数据结构 模板

广义表
定义：
typedef struct bnode
{int atom;
struct bnode *next;
union
  {struct bnode *snext;
   datatype data;} elemtype;
} slists;
或：
typedef struct dbnode
{datatype data;
struct dbnode *next1,*next2;
} dblists;
求深度：
depth(ls)
slists *ls;
{int max,dep;
max=0;
while(ls!=Null)
  {if(ls->atom==1)
     {dep=depth(ls->snext);
        if(dep>max)  max=dep;
      }
   ls=ls->next;
  }
return max+1;
}
作者: 一生逍遥    时间: 2006-10-31 20:25     标题: [数据结构（C语言版）]数据结构 模板

[color=&#35;DC143C]数组和广义表
作者: 一生逍遥    时间: 2006-11-8 07:33     标题: [数据结构（C语言版）]数据结构 模板

[color=&#35;DC143C]树
树的基本运算：
(1)SETNULL(T)
置T为空表。
(2)ROOT(T)或ROOT(x)
找根函数。求树T的根或求结点x所在的树的根结点。若T是空树或x不在任何一棵树上，则函数值为“空”。
(3)PARENT(T,x)
找双亲函数。求树T结点为x的双亲结点。若结点x是树T的根结点，或者结点x不在树T上，则函数值为“空”。
(4)CHILD(T,x,i)
找孩子结点函数。求树T中结点为x的第i个孩子结点。若结点x无第i个孩子，则函数值为“空”。
(5)CREATE(x,F)
建树函数。生成一棵以x为结点为根、以森林F为子树森林的树。
(6)ADDCHILD(y,i,x)
添加子树操作。把结点x为根的树置为结点y的第i棵子树。若原树中无结点y或结点y个子树个数小于i-1，则为空操作。
(7)DELCHILD(x,i)
删除子树操作。删除结点x的第i棵子树。若无结点x或结点x的子树个数小于i，则为空操作。
(8)TRAVERSE(T)
遍历操作。按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。
作者: 一生逍遥    时间: 2006-11-8 07:34     标题: [数据结构（C语言版）]数据结构 模板

二叉树的基本操作：
(1)SETNULL(BT)
置BT为空表。
(2)ROOT(BT)或ROOT(x)
找根函数。求树BT的根或求结点x所在的树的根结点。若BT是空树或x不在任何一棵树上，则函数值为“空”。
(3)PARENT(BT,x)
找双亲函数。求树BT结点为x的双亲结点。若结点x是树BT的根结点，或者结点x不在树BT上，则函数值为“空”。
(4)LCHILD(BT,x)和RCHILD(BT,x)
找孩子结点函数。求树BT中结点x的左孩子和右孩子结点。若结点x为叶子结点或不在二叉树BT中，则函数值为“空”。
(5)CREATE(x,LBT,RBT)
建树函数。生成一棵以x结点为根、LBT和RBT分别为左子树和右子树的二叉树。
(6)ADDLCHILD(BT,y,x)和ADDLCHILD(BT,y,x)
添加子树操作。把结点x为根的树置为结点y的左边或右边。
(7)DELLCHILD(BT,x)和DELRCHILD(BT,x)
删除子树操作。分别删除二叉树BT中以结点x为根的左子树或右子树。若无左子树或右子树，则为空操作。
(8)TRAVERSE(BT)
遍历操作。按某个次序依次访问树中的各个结点，并使每个结点只被访问一次。
作者: 一生逍遥    时间: 2006-11-8 07:35     标题: [数据结构（C语言版）]数据结构 模板

二叉树的存储
顺序存储结构：
利用满二叉树编号，将二叉树的结点按对应的编号存储在数组中。
二叉链表法：
typedef struct btnode
{telemtype data;
struct btnode *lchild,*rchild;
} bitnode,*bitree;
三叉链表法：
typedef struct btnode
{telemtype data;
struct btnode *lchild,*rchild，*parent;
} bitnode,*bitree;
作者: 一生逍遥    时间: 2006-11-8 07:36     标题: [数据结构（C语言版）]数据结构 模板

生成二叉排序树的算法 生成二叉排序树的递归算法： bitree creat_ordbt() {bitree t,s; telemtree x; t=Null; scanf(&x); while(x!=0) {s=(bitree)malloc(sizeof(binode)); s->data=x;s->lchild->Null;s->right=Null; t=ins_node(s,t);/* 插入结点函数 */ scanf(&x); } return t; } bitree ins_node(bitree s,bitree t) {if(t==Null) t=s; else if(s->datadata) t->lchild=ins_node(s,t-lchild); else t->rchild=ins_node(s,t->rchild); return t; } 生成二叉排序树的非递归算法： bitree creat_ordbt_2() {bitree t,s,p,q; telemtree x; t=Null; scanf(&x); while(x!=0) {s=(bitree)malloc(sizeof(binode)); s->data=x;s->lchild->Null;s->right=Null; if(!t) t=s; else {p=t; while(p) {q=p; if(s->datadata) p=p->lchild; else p=p->rchild; } if(s->datadata) q->lchild=s; else q->rchild=s; } } return t; }
作者: 一生逍遥    时间: 2006-11-8 07:36     标题: [数据结构（C语言版）]数据结构 模板

二叉树的遍历
前序遍历：先访问根结点，再按前序遍历左子树，最后按前序遍历右子树。
中序遍历：先按中序遍历左子树，再访问根结点，最后按中序遍历右子树。
后序遍历：先按后序遍历左子树，再按后序遍历右子树，最后访问根结点。

遍历的递归算法
前序遍历：
void preorder(bitree root)
{if(root!=Null)
   {printf("%d\t",root-data);
    preorder(root->lchild);
    preorder(root->rchild);
   }
}
中序遍历：
void inorder(bitree root)
{if(root!=Null)
   {inorder(root->lchild);
    printf("%d\t",root-data);
    inorder(root->rchild);
   }
}
后序遍历：
void postorder(bitree root)
{if(root!=Null)
   {postorder(root->lchild);
    postorder(root->rchild);
    printf("%d\t",root-data);
   }
}

按前序序列建二叉树的算法：
bitree createbitree()
{bitree t;char ch;
scanf("%c",&ch);
if(ch==" ") t=Null;
else
    {t=(bitree)malloc(sizeof(bitnode));
     t->data=ch;
     t->lchild=creatbitree();
     t->rchild=creatbitree();
    }
return t;
}
遍历的非递归算法
&#35;define M 100
前序遍历：
void preorder(bitree t)
{int top=0;
bitree p,s[M];
p=t;
do
   {while(p!=Null)
         {printf("%d\t",p->data);
          if(p->rchild!=null)
          s[top++]=p->rchild;
          p=p->lchild;
         }
    if(top>=0) p=s[--top];
   }
while(top>=0);   
}
中序遍历：
void inorder(bitree t)
{int top=0;
bitree p,s[M];
p=t;
do
   {while(p!=Null)
         {s[top++]=p;
          p=p->lchild;
         }
    if(top>=0)
         {p=s[--top];
          printf("%d\t",p->data);
          p=p->rchild;
         }
   }
while(top>=0);
}
后序遍历：
void postorder(bitree t)
{int s2[M],top=0,b;
bitree p,s1[M];
p=t;
do
    {while(p!=Null)
        {s1[top]=p;
         s2[top++]=0;
         p=p->lchild;
        }
     if(top>0)
        {b=s2[--top];
         p=s1[top];
         if(b==0)
            {s1[top]=p;s2[top++]=1;
             p=p->rchild;
            }
         else
            {printf("%d\t",p->data);
             p=Null;
            }
        }
    }
while(top>0);
}
作者: 一生逍遥    时间: 2006-11-8 07:37     标题: [数据结构（C语言版）]数据结构 模板

二叉树算法举例
求二叉树的叶子树：
int countleaf(bitree t,int num)
{if(t!=Null)
      {if((t->lchild==Null)&&(t->rchild==Null)) num++;
       num=countleaf(t->lchild,num);
       num=countleaf(t->rchild,num);
      }
return num;
}
求二叉树的树高：
int treedepth(bitree t)
{int h,lh,rh;
if(t==Null) h=0;
else
    {lh=treedepth(p->lchild);
     rh=treedepth(p->rchild);
     if(lh>=rh) h=lh+1;
     else h=rh+1;
    }
return h;
}
作者: 一生逍遥    时间: 2006-11-8 07:38     标题: [数据结构（C语言版）]数据结构 模板

线索二叉树
定义：
typedef enum{0,1} ptrtag;
typedef struct bithrnode
{telemtype data;
struct bithrnode *lchild,*rchild;
ptrtag ltag,rtag;
} bithrnode,*bithrtree;
构造中序线索二叉树：
bithrtree crt_inordthrd(t,pre)
bithrtree thrt,pre;
{thrt=(bithrtree)malloc(sizeof(bithrnode));
thrt->ltag=0;thrt->rtag=1;
thrt->rchild=thrt;
if(t==null) thrt->lchild=thrt;
else
   {thrt->lchild=t;pre=thrt;
    inthrd(t);
    pre->rchild=thrt;pre->rtag=1;
    thrt->rchild=pre;
   }
return thrt;
}
void inthrd(bithrtree p)
{if(p!=Null)
   {inthrd(p->lchild);
    if(p->lchild==Null)
       {p->ltag=1;p->lchild=pre;}
    if(p->rchild==Null)
       {pre->rtag=1;pre->rchild=p;}
    pre=p;
   }
inthrd(p->rchild);
}
遍历线索二叉树：
void inordtraverse_thr(bithrtree t)
{bithrtree p;
p=t->lchild;
while(p!=t)
    {while(p->ltag==0) p=p->lchild;
     printf("%..",p->data);
     while((p->rtag==1)&&(p->rchild!=t))
         {p=p->rchild;
          printf("%..",p->data);}
     p=p->rchild;
    }
}
作者: 一生逍遥    时间: 2006-11-8 07:38     标题: [数据结构（C语言版）]数据结构 模板


树的存储结构
&#35;define mtsize 100
双亲表示法：
typedef struct ptnode
{telemtype data;
int parent;
} ptnode;
typedef struct
{ptnode tree[mtsize];
int n;
} ptree;
孩子表示法：
typedef struct ctnode
{int child;
struct ctnode *next;
} *childptr;
typedef struct
{telemtype data;
childptr firstchild
} ctbox;
typedef struct
{ctbox tree[mtsize];
int n,r;
} ctree;
孩子兄弟表示法：
typedef struct csnode
{elemtype data;
struct csnode *firstchild,*nextsibling;
} csnode,*cstree;
作者: 一生逍遥    时间: 2006-11-8 07:39     标题: [数据结构（C语言版）]数据结构 模板

哈夫曼树： 定义： typedef struct {unsigned int weight; unsigned int parent,lchild,rchild; }htnode,*huffmantree; typedef char *huffmancode 求哈夫曼树： huffmantree crt_huffmantree(int *w,int n) {huffmantree ht; m=2*n-1; ht=(huffmantree)malloc((m+1)*sizeof(htnode)); for(p=ht,i=1;i<=n;i++,p++,w++) *p={*w,0,0,0}; for(;i<=m;i++,p++) *p={0,0,0,0}; for(i=n+1;i<=m;i++) {select(ht,i-1,s1,s2); ht[s1].parent=i;ht[s2].parent=i; ht.lchild=s1;ht.rchild=s2; ht.weight=ht[s1].weight+ht[s2].weight; } return ht; } 从叶子到根逆向求每个字符的哈夫曼编码： huffmancode get_huffmancode(huffmantree ht,int n) {hc=(huffmancode)malloc((n+1)*sizeof(char)); cd=(char*)malloc(n*sizeof(char)); cd[n-1]="\0"; for(i=1;i<=n;i++) {start=n-1; for(c=i,f=ht.parent;f!=c;f=ht[f].parent) if(ht[f].lchild==c) cd[--start]="0"; else cd[--start]="1"; hc=(char*)malloc((n-start)*sizeof(char)); strcpy(hc,&cd[start]); } free(cd); return hc; }
作者: 一生逍遥    时间: 2006-11-9 19:12     标题: [数据结构（C语言版）]数据结构 模板

[color=#DC143C]图 图的存储结构 接矩阵表示法： #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 int adjmatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct {vertextype vex[MAX_VERTEX_NUM]; adjmatrix arcs; int vexnum,arcnum; } mgraph; 邻接矩阵表示法建立无向网： void creatmg(mgraph g) {int i,j,k,v1,v2,w; scanf(&g.vexnum,&g.arcnum); for(i=0;i"); for(i=0;i[j]=INFINITY; for(k=0;k[j]=g.arcs[j]=w; } } 邻接表表示法： 结点： #define M 60 typedef struct node {int vex; struct node *link; } JD; 表头结点： typedef struct tnode {int data; struct node *link; } TD; 邻接表表示法建立无向网： void creatljb(TD ad[],int n) {JD *p; int i,j,k; for(k=1;k<=n;k++) ad[k].link=Null; scanf("%d,%d",&i,&j); while((i>0)&&(j>0)) {p=(JD)malloc(sizeof(JD)); p->vex=j;p->link=ad.link; ad.link=p; p=(JD*)malloc(sizeof(JD)); p->vex=i;p->link=ad[j].link; ad[j].link=p; scanf("%d,%d",&i,&j); } } 邻接多重表表示法： 表示边的结点： typedef struct arcnode {int mark,ivex,jvex; struct arcnode *ilink,*jlink; } JD; 表示顶点的结点： typedef struct vexnode {int data; struct arcnode *firstarc; } DD;
作者: 一生逍遥    时间: 2006-11-9 19:13     标题: [数据结构（C语言版）]数据结构 模板

图的遍历 深度优先搜索遍历 从顶点v按深度优先： void dfs(TD g[],int v,int c[]) {JD *p;int i; c[v]=1;printf("%d\n",v); for(p=g[v].link;p!=Null;p=p->link) {i=p->vex; if(c==0) dfs(g,i,c); } } 对整个图遍历的算法： void blt(TD g[];int n) {int v; int c[M]; for(v=1;v<=n;v++) c[v]=0; for(v=1;v<=n;v++) if(c[v]==0) dfs(g,v,c); } 广度优先搜索遍历 从顶点v按广度优先： void bfs(TD g[],int v,int c[]) {int q[M],r=0,f=0; JD *p; c[v]=1;printf("%d\n",v); q[0]=v; while(f<=r) {v=q[f++]; p=g[v].link; while(p!=Null) {v=p->vex; if(c[v]==0) {c[v]=1; printf("%d\n",v); q[++r]=v; } p=p->link; } } }
作者: 一生逍遥    时间: 2006-11-9 19:13     标题: [数据结构（C语言版）]数据结构 模板

最小生成树 普里姆算法： #define M 30 #define MAX 99 void prim(mgragh g,int k,int n) {int i,j,min,p; struct {int adjvex; int lowcost; } closedge[M]; for(i=1;i.adjvex=k; closedge.lowcost=g.arcs[k]; } closedge[k].lowcost=0; for(i=1;i 作者: 一生逍遥    时间: 2006-11-9 19:14     标题: [数据结构（C语言版）]数据结构 模板

最短路径： 求从一个顶点到其它各顶点的最短路径： (迪杰斯特拉算法) #define MAX 32767 void dijkstra(int ad[][M],int k,int pre[],int dist[],int n) {int i,j,p,min; k=k-1; for(i=0;i=ad[k]; if(dist=k+1; else pre=0; } pre[k]=0;dist[k]=0; ad[k][k]=1; for(j=0;j<(n-1);j++) {min=MAX; p=-1; for(i=0;i==0&&dist;} if(p==-1) break; else {ad[p][p]=1; for(i=0;i==0&&(min+ad[p])) {dist=min+ad[p]; pre=p+1; } } } } 求每一对顶点之间的最短路径： (弗洛伊德算法) void floyd(int ad[][M],int p[][M],int n) {int i,j,k; for(i=0;i[j]=0; else if(ad[j][j]=i+1; else p[j]=0 } for(k=0;k[k]+ad[k][j][j]) {ad[j]=ad[k]+ad[k][j]; p[j]=p[k][j]; } }
作者: 一生逍遥    时间: 2006-11-9 19:14     标题: [数据结构（C语言版）]数据结构 模板

拓扑排序 用邻接表存储结构实现拓扑排序： typedef struct node {int vex; struct node *link; } JD; typedef struct tnode {int in; struct node *link; } TD; void topsort(TD g[],int n) {int top,m,k,j; JD *p; top=0;m=0; for(j=1;j<=n;j++) if(g[j].in==0) {g[j].in=top;top=j;}/*入度为0的顶点进栈*/ while(top>0) {j=top;top=g[top].in; printf("%d\n",j); m++; p=g[j].link; while(p!=Null) {k=p->vex; g[k].in--; if(g[k].in==0) {g[k].in=top; top=k; } p=p->link; } } printf("m=%d\n",m); if(m 作者: 一生逍遥    时间: 2006-11-10 18:42     标题: [数据结构（C语言版）]数据结构 模板

[color=#DC143C]检索 线性表的检索 顺序检索： typedef struct {keytype key; elemtype other; } sqlist; sqlist R[n+1] int seqsrch(R,k) sqlist R[]; keytype k; {int i; R[0].key=k; i=n; while(R.key!=k) i--; if(i==0) return(False); else return i; } 折半检索： int binsrch(R,k) keytype k; {int low,high,mid; low=0; high=n-1; while(low<=high) {mid=(low+high)/2; if(k==R[mid].key) return mid; else if(k; int Blocksrch(R,ID,m,k); sqlist R[]; indexlist ID[]; keytype k; int m; {int i,j; i=0; while((i<=m-1)&&(k>ID.key)) i++; if(i>m-1) return(False); else {j=R.stadr; while((j.stadr+ID.len)&&(k!=R[j].key)) j++; if(j==ID.stadr+ID.len) return(False); else return j; } }
作者: 一生逍遥    时间: 2006-11-10 18:43     标题: [数据结构（C语言版）]数据结构 模板

树表的检索 二叉排序树： typedef struct node {keytype key; elemtype other; strcut node *lchild,*rchild; } bilist; bilist *bstsrch(t,k) bilist *t; keytype k; {if((t==Null)||(t->key==k)) return(t); else if(t->keyright,k)); else return(bstsrch(t->left,k)); } 插入一个新的叶子结点到二叉排序树： bilist *insert(t,s) bilist *t,*s; {bilist *p,*q; if(t==Null) return s; p=t; while(p!=Null) {q=p; if(s->key==p->key) return t; else {if(s-key>p->key) p=p->right; else p=p->left; } } if(s->key>q->key) q->right=s; else q->left=s; return t; } 利用插入算法构造一棵具有n个结点的二叉排序树： bilist *bstcreat() {bilist *t,*s; keytype k; int i,n; elemtype data; t=Null; scanf("%d",&n); for(i=1;i<=n;i++) {scanf("%d",&key); s=malloc(sizeof(bilist)); s->lchild=Null; s->rchild=Null; s->key=key; s->other=data; t=insert(t,s); } } 三叉表示法： typedef struct node {keytype key; elemtype other; strcut node *left,*right,*parent; } bstsrchtree; 在一个排序二叉树删除一个关键值为k的结点： bstsrchtree *delete(k,t) keytype k; bstsrchtree t; {bstsrchtree *p,*q,*r; p=t; while((p!=Null)&&(k!=p->key)) if(kkey) p=p->left; else p=p->right; if(p==Null) break; if((p->left==Null)||(p->right==Null)) q=p; else {q=p->right; while (q->left!=Null) q=q->left; } if(q->left!=Null) r=q->left; else r=q->right; if(r!=Null) r->parent=q->parent; if(q->parent==Null) t=r; else if(q==q->parent->left) q->parent->left=r; else q->parent->right=r; if(p!=q) p->key=q->key; return t; }
作者: 一生逍遥    时间: 2006-11-11 12:08     标题: [数据结构（C语言版）]数据结构 模板

[color=&#35;DC143C]排序
数据定义
typedef struct
{int key;
elemty otheritem;
} recdtype;
recdtype R[n];
作者: 一生逍遥    时间: 2006-11-11 12:09     标题: [数据结构（C语言版）]数据结构 模板

插入排序 直接插入排序的算法： insertsorting(R) {recdtype R[]; int i,j; for(i=2;i; j=i-1; while(R[0].key=1) {d=d%2; do{bool=True; for(i=1;i<=n-d;i++) {j=j+d; if(R.key>R[j].key) {x=R;R=R[j];R[j]=x; bool=False; } } } while(bool==true); } } 设监视哨的希尔排序： int d[m];/*存放增量序列*/ recdtype R[n+d[0]];/*前d[0]个为监视哨*/ shellsort(R,d) recdtype R[]; int d[]; {int i,j,k,t; recdtype temp; int maxint=32767; for(i=0;i.key=-maxint; /*设置监视哨*/ k=0; do {t=d[k]; for(i=t+d[0];i; j=i-t; while(temp.key;temp=R.key; s=1;j=i-1; while(s<=j) {m=(s+j)/2; if(x=j+1;k++) R[j+1]=R[0]; } binsort(R) recdtype R[n]; {int i; for(i=2;i<=n;i++) binsearch(R,i); } 共享栈插入排序： sharedinsertsort(R) recdtype R[n]; {int maxint=32767; int i,j,m; recdtype t; R[0]=-maxint;R[n+1]=maxint; if(R[1]>R[n]) {t=R[1];R[1]=R[n];R[n]=t;} i=2;j=n-1; do {t=R; if((t>=R[i-1])&&(t<=R[j+1])) i=i+1; else if(tt) k=k-1; for(m=i;m>=k+1;m--) R[m]=R[m-1]; R[k]=t; i=i+1; } else {k=j; while(R[k+1]j); }
作者: 一生逍遥    时间: 2006-11-11 12:10     标题: [数据结构（C语言版）]数据结构 模板

交换排序 冒泡排序： bubblesort(R) recdtype R[n]; {int i,j,flag; recdtype temp; for(i=0;i=i;j++) if(R[j+1].key; while(i=temp.key)&&(ii) {R=R[j];i++;} while((R.key<=temp.key)&&(ii) {R[j]=R;} } R=temp; if(s<(i-1)) quicksort(R,s,i-1); if(t>(i+1)) quicksort(R,i+1,t); }
作者: 一生逍遥    时间: 2006-11-11 12:11     标题: [数据结构（C语言版）]数据结构 模板

选择排序 直接选择排序： selectsort(R) recdtype R[]; {int i,j,m; recdtype temp; for(i=0;i<=n-2;i++) {m=i; for(j=i+1;j<=n-1;j++) if(R[j].key; R=R[m]; R[m]=temp; } } } 堆排序：(堆顶为最小值情况) 筛选算法： creatheap(R,i,m) recdtype R[]; int i,n; {int j; recdtype temp; temp=R; j=2*i; while(j<=n) {if((jR[j+1].key)) j++; if(temp.key>R[j].key) {R=R[j]; i=j; j=2*i; } else j=n+1; } R=temp; } 完整的堆排序算法： heapsort(R,n) recdtype R[]; int n; {recdtype temp; int i,j; for(i=n/2;i>=1;i--) creatheap(R,i,n); for(i=n;i>=1;i--) {temp=R[1]; R[1]=R; R=temp; cteatheap(R,1,i-1); } }
作者: 一生逍遥    时间: 2006-11-11 12:11     标题: [数据结构（C语言版）]数据结构 模板

归并排序 二路归并算法： merge(R,A,s,m,t) /*R->R[m],R[m+1]->R[t]=>A->A[t]*/ int s,m,t; {int i,j,k; i=s; j=m+1; k=s; while((i<=m)&&(j<=t)) if(R.key<=R[j].key) {A[k]=R; i++; k++; } else {A[k]=R[j]; j++; k++; } while(i<=m) {A[k]=R; i++; k++; } while(j<=t) {A[k]=R[j]; j++; k++; } } 对数组R[n]做一趟归并，R[n]以长度c分段： mergepass(R,A,n,c) recdtype R[],A[]; int n,c; {int i,j; i=1; while(i+2*c-1<=n) {merge(R,A,i,i+c-1,i+2*c-1); i=i+2*c; } if(i+c-1 作者: 一生逍遥    时间: 2006-11-11 12:12     标题: [数据结构（C语言版）]数据结构 模板

基数排序 #define rd 10; typedef struct {int key[d]; int next; datatype other; } recdtype; recdtype R[n]; int f[rd],e[rd]; int radixsorting(R) recdtype R[]; {int i,j,k,p,t; p=0; for(i=d;i>=1;i--) {for(j=0;j; if(f[k]==-1) f[k]=p; else R[e[k]].next=p; e[k]=p; p=R[p].next; } j=0; while(f[j]==-1) j++; p=f[j]; t=e[j]; while(j 作者: 一生逍遥    时间: 2006-11-11 12:14     标题: [数据结构（C语言版）]数据结构 模板

数据结构C版本模板－－chm




欢迎光临 黑色海岸线论坛 (http://bbs.thysea.com/) Powered by Discuz! 7.2