[数据结构（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的线性表。

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

基数排序 #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

归并排序 二路归并算法： 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

选择排序 直接选择排序： 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); } }

交换排序 冒泡排序： 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); }

插入排序 直接插入排序的算法： 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); }

[color=&#35;DC143C]排序
数据定义
typedef struct
{int key;
elemty otheritem;
} recdtype;
recdtype R[n];

树表的检索 二叉排序树： 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; }

[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; } }

拓扑排序 用邻接表存储结构实现拓扑排序： 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

最短路径： 求从一个顶点到其它各顶点的最短路径： (迪杰斯特拉算法) #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]; } }

最小生成树 普里姆算法： #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

图的遍历 深度优先搜索遍历 从顶点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; } } }

[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;