西安电子科技大学出版社：算法与数据结构-C语言描述（樊希平）：数据结构

数组
#include <stdarg.h>
#include "likec.h"
#define MAX_ARRAY_DIM 8
typedef int ElemType;
typedef struct {
ElemType *base;
int dim;
int *bounds;
int *constants;
}Array;
Status InitArray(Array *A,int dim,...)
{ int elemtotal,i;
va_list ap;
if(dim<1||dim>MAX_ARRAY_DIM)return ERROR;
A->dim=dim;
A->bounds=(int *)malloc(dim*sizeof(int));
elemtotal=1;
va_start(ap,dim);
for(i=0;i<dim;++i)
{ A->bounds[i]=va_arg(ap,int);
elemtotal *=A->bounds[i];
}
va_end(ap);
A->base=(ElemType *)malloc(elemtotal*sizeof(ElemType));
A->constants=(int *)malloc(dim*sizeof(int));
A->constants[dim-1]=1;
for(i=dim-2;i>=0;--i)
A->constants[i]=A->bounds[i+1]*A->constants[i+1];
return OK;
}
Status DestroyArray(Array *A)
{ if(!A->base)return ERROR;
free(A->base); A->base=NULL;
free(A->bounds); A->bounds=NULL;
free(A->constants); A->constants=NULL;
return OK;
}
Status Locate(Array A,va_list ap,int *off)
{ int i,ind;
*off=0;
for(i=0;i<A.dim;++i)
{ ind=va_arg(ap,int);
if(ind<0||ind>=A.bounds[i])return OVERFLOW;
*off+=A.constants[i]*ind;
}
return OK;
}
Status Value(Array A,ElemType *e,...)
{ va_list ap;
int result,off;
va_start(ap,A.dim);
if((result=Locate(A,ap,&off))<=0)return result;
*e=*(A.base+off);
va_end(ap);
return OK;
}
Status Assign(Array A,ElemType e,...)
{ va_list ap;
int result,off;
va_start(ap,A.dim);
if((result=Locate(A,ap,&off))<=0)return result;
*(A.base+off)=e;
va_end(ap);
return OK;
}
main()
{
}
哈夫曼树
#include<stdio.h>
#define N 100
#define MAX 9999
typedef struct node{
union{ char data;
int w;
}val;
struct node *lchild;
struct node *rchild;
}NODE;
NODE *creat_huffman_tree(char dat[],int w[],int n)
{ NODE *T[N],*p;
int n1,n2,i,j,v,min1,min2;
for(i=0;i<n;i++)
{ T[i]=(NODE *)malloc(sizeof(NODE));
T[i]->val.w=w[i];
T[i]->lchild=NULL;
T[i]->rchild=NULL;
}
for(i=0;i<n-1;i++)
{ n1=-1;
min1=MAX;
n2=-1;
min2=MAX;
for(j=0;j<n;j++)
{ if(T[j]!=NULL)
{ v=T[j]->val.w;
if(v<min1)
{ min2=min1;
n2=n1;
min1=v;
n1=j;
}
else if(v<min2)
{ min2=v;
n2=j;
}
}
}
p=(NODE *)malloc(sizeof(NODE));
p->val.w=T[n1]->val.w+T[n2]->val.w;
p->lchild=T[n1];
p->rchild=T[n2];
if(T[n1]->lchild==NULL)T[n1]->val.data=dat[n1];
else T[n1]->val.data='*';
if(T[n2]->lchild==NULL)T[n2]->val.data=dat[n2];
else T[n2]->val.data='*';
T[n1]=p;
T[n2]=NULL;
}
p->val.data='*';
return(p);
}
prn_BT(NODE *b)
{ if(b!=NULL)
{ printf("%c",b->val.data);
if(b->lchild!=NULL)
{ printf("(");
prn_BT(b->lchild);
printf(",");
prn_BT(b->rchild);
printf(")");
}
}
}
main()
{ NODE *h;
char d[N]={'a','b','c','d'};
int w[N]={1,3,2,4};
h=creat_huffman_tree(d,w,4);
printf("\n");
prn_BT(h);
}
线性表的顺序存储与实现
#include "likec.h"
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
Status InitList_Sq(SqList *L){
L->elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType));
if(!L->elem)exit(OVERFLOW);
L->length=0;
L->listsize=LIST_INIT_SIZE;
return OK;
}
void DestroyList_Sq(SqList *L){
if(L->elem){
free(L->elem);
L->length=0;
L->listsize=0;
}
}
void ClearList_Sq(SqList *L){
if(L->elem){
L->elem=(ElemType *)realloc(L->elem,L->listsize*sizeof(ElemType));
L->length=0;
}
}
Status ListEmpty_Sq(SqList L){
if(L.length==0)return TRUE;
else return FALSE;
}
int ListLength_Sq(SqList L){
return L.length;
}
Status GetElem_Sq(SqList L,int i,ElemType *e){
if(i<0||i>=L.length)return ERROR;
*e=L.elem[i];
return OK;
}
int LocateElem_Sq(SqList L,ElemType e){
int i=0;
while(i<L.length){
if(L.elem[i]==e)return(i);
i++;
}
return(-1);
}
Status PriorElem_Sq(SqList L,ElemType cur_e,ElemType *pre_e){
int i;
i=LocateElem_Sq(L,cur_e);
if(i==-1||i==0)return FALSE;
else{
*pre_e=L.elem[i-1];
return OK;
}
}
Status NextElem_Sq(SqList L,ElemType cur_e,ElemType *next_e){
int i;
i=LocateElem_Sq(L,cur_e);
if(i==-1||i==L.length-1)return FALSE;
else{
*next_e=L.elem[i+1];
return OK;
}
}
Status ListInsert_Sq(SqList *L,int i,ElemType e){
int j;
if(i<0||i>L->length)return ERROR;
if(L->length==L->listsize){
L->elem=(ElemType *)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
L->listsize+=LISTINCREMENT;
}
for(j=L->length;j>i&&j;j--)L->elem[j]=L->elem[j-1];
L->elem[i]=e;
L->length+=1;
return OK;
}
Status ListDelete_Sq(SqList *L,int i,ElemType *e){
int j;
if(i<0||i>=L->length)return ERROR;
*e=L->elem[i];
for(j=i;j<L->length-1;j++)L->elem[j]=L->elem[j+1];
L->length-=1;
return OK;
}
void ListPrint_Sq(SqList L){
int i;
for(i=0;i<L.length;i++)printf("%3d",L.elem[i]);
}
main()
{ int m;
SqList L;
InitList_Sq(&L);
for(m=0;m<10;m++)
if(!ListInsert_Sq(&L,m,2*m))printf("error");
ListPrint_Sq(L);
}
线性表的链式存储与实现
/*This list use link,have a head node */
#include "likec.h"
#include <stdio.h>
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
Status InitList_L(LinkList *L){
*L=(LinkList)malloc(sizeof(LNode));
if(!(*L))exit(OVERFLOW);
(*L)->next=NULL;
return OK;
}
void DestroyList_L(LinkList *L){
LinkList p=*L,q;
while(p){
q=p;
p=p->next;
free(q);
}
*L=NULL;
}
void ClearList_L(LinkList *L){
LinkList p=(*L)->next,q;
while(p){
q=p;
p=p->next;
free(q);
}
(*L)->next=NULL;
}
Status ListEmpty_L(LinkList L){
if(L->next==NULL)return TRUE;
else return FALSE;
}
int ListLength_L(LinkList L){
LinkList p;
int i=0;
for(p=L->next;p;p=p->next)i++;
return i;
}
Status GetElem_L(LinkList L,int i,ElemType *e){
int j=-1;
while(L&&j!=i){
L=L->next;
j++;
}
if(j==i){*e=L->data;
return OK;
}
else return ERROR;
}
LinkList LocateElem_L(LinkList L,ElemType e){
LinkList p=L->next;
while(p&&p->data!=e) p=p->next;
return(p);
}
Status PriorElem_L(LinkList L,ElemType cur_e,ElemType *pre_e){
LinkList p,q;
p=LocateElem_L(L,cur_e);
if(!p)return ERROR;
q=L;
while(q->next!=p)q=q->next;
if(q==L)return ERROR;
*pre_e=q->data;
return OK;
}
Status NextElem_L(LinkList L,ElemType cur_e,ElemType *next_e){
LinkList p,q;
p=LocateElem_L(L,cur_e);
if(!p)return ERROR;
q=p->next;
if(!q)return ERROR;
*next_e=q->data;
return OK;
}
Status ListInsert_L(LinkList L,int i,ElemType e){
int len,j=0;
LinkList p=L,q;
len=ListLength_L(L);
if(i<0||i>=len+1)return ERROR;
q=(LinkList)malloc(sizeof(LNode));
q->data=e;
while(j!=i){p=p->next;j++;}
q->next=p->next;
p->next=q;
return OK;
}
Status ListDelete_L(LinkList L,int i,ElemType *e){
int j=0,len;
LinkList p=L,q;
len=ListLength_L(L);
if(i<0||i>=len)return ERROR;
while(j!=i){p=p->next;j++;}
q=p->next;
p->next=q->next;
*e=q->data;
free(q);
return OK;
}
void ListPrint_L(LinkList L){
LinkList p=L->next;
for(;p;p=p->next)printf("%3d",p->data);
printf("\n");
}
main()
{ int m;
char ch;
LinkList L;
InitList_L(&L);
ch=getchar();
while(ch!='Q'){
switch(ch){
case 'C':
for(m=0;m<10;m++)
if(!ListInsert_L(L,m,2*m))printf("error");
ListPrint_L(L);
break;
case 'I':
ListInsert_L(L,3,77);
ListPrint_L(L);
break;
case 'L':
ClearList_L(&L);
ListPrint_L(L);
break;
}
getchar();
ch=getchar();
}
}
矩阵及其操作
#include "likec.h"
#define MAXSIZE 1250
typedef int ElemType;
typedef struct {
int i,j;
ElemType e;
}Triple;
typedef union{
Triple data[MAXSIZE+1];
int mu,nu,tu;
}TSMatrix;
Status Input(TSMatrix *M)
{ int m,n,t,i,j,k;
ElemType e;
printf("Please input line,col and numbers:");
scanf("%d%d%d",&m,&n,&t);
if(m<2||n<2||t<0)return ERROR;
M->mu=m; M->nu=n; M->tu=t;
for(k=1;k<=t;k++)
{ printf("Please input the triple NO:%d",k);
scanf("%d%d%d",&i,&j,&e);
if(i>m||i<1||j>n||j<1)return ERROR;
M->data[k].i=i; M->data[k].j=j; M->data[k].e=e;
}
return OK;
}
void Output(TSMatrix M)
{ int m,n,t=1;
for(m=1;m<=M.mu;m++)
{ for(n=1;n<=M.nu;n++)
{ if(M.data[t].i==m&&M.data[t].j==n)
{ printf("%4d\t",M.data[t].e);
t++;
}
else
printf("%4d\t",0);
}
printf("\n");
}
}
Status Transpose(TSMatrix M,TSMatrix *T)
{ int col,q,p;
T->mu=M.nu; T->nu=M.mu; T->tu=M.tu;
if(M.tu){
q=1;
for(col=1;col<=M.nu;++col)
for(p=1;p<=M.tu;++p)
if(M.data[p].j==col){
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
++q;
}
}
return OK;
}
Status Transpose_f(TSMatrix M,TSMatrix *T)
{ int col,q,p,t,num[100],cpot[100];
T->mu=M.nu; T->nu=M.mu; T->tu=M.tu;
if(M.tu){
for(col=1;col<M.nu;++col)num[col]=0;
for(t=1;t<=M.tu;++t)++num[M.data[t].j];
cpot[1]=1;
for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];
for(p=1;p<=M.tu;++p){
col=M.data[p].j; q=cpot[col];
T->data[q].i=M.data[p].j;
T->data[q].j=M.data[p].i;
T->data[q].e=M.data[p].e;
++cpot[col];
}
}
return OK;
}
main()
{ TSMatrix M,T;
if(Input(&M))Output(M);
Transpose_f(M,&T);
Output(T);
}
线性表的静态链表
/*static link */
#include "likec.h"
#define MAXSIZE 100
typedef int ElemType;
typedef struct{
ElemType data;
int cur;
}component,SLinkList[MAXSIZE];
void InitSpace_SL(SLinkList space){
int i;
for(i=0;i<MAXSIZE-1;i++)space[i].cur=i+1;
space[MAXSIZE-1].cur=0;
}
int Malloc_SL(SLinkList space){
int i=space[0].cur;
if(space[0].cur)space[0].cur=space[i].cur;
return i;
}
void Free_SL(SLinkList space,int k){
space[k].cur=space[0].cur;
space[0].cur=k;
}
void Print_SL(SLinkList space,int head){
int i=space[head].cur;
while(i!=head){
printf("%3d",space[i].data);
i=space[i].cur;
}
}
void difference(SLinkList space,int *ph)
{ int s,r,m,n,i,j,b,k,p;
InitSpace_SL(space);
s=Malloc_SL(space);
r=s;
scanf("%d,%d",&m,&n);
for(j=1;j<=m;++j){
i=Malloc_SL(space);
scanf("%d",&space[i].data);
space[r].cur=i;r=i;
}
space[r].cur=s;
Print_SL(space,s);
for(j=1;j<=n;++j){
scanf("%d",&b);
k=space[s].cur;
while(k!=space[r].cur&&space[k].data!=b){
p=k;k=space[k].cur;
}
if(k==space[r].cur){
i=Malloc_SL(space);
space[i].data=b;
space[i].cur=space[r].cur;
space[r].cur=i;
}
else{
space[p].cur=space[k].cur;
Free_SL(space,k);
if(r==k)r=p;
}
}
*ph=s;
}
main()
{ int head,tail,i,elem;
SLinkList L;
InitSpace_SL(L);
head=Malloc_SL(L);
L[head].cur=head;
for(i=0;i<10;i++){
scanf("%d",&elem);
tail=Malloc_SL(L);
L[tail].data=elem;
L[tail].cur=L[head].cur;
L[head].cur=tail;
}
Print_SL(L,head);
difference(L,&head);
Print_SL(L,head);
}
堆栈操作算法
#include "likec.h"
#include <stdio.h>
typedef int SElemType;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef struct{
SElemType *base,*top;
int stacksize;
}SqStack;
Status InitStack(SqStack *S)
{ S->base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!S->base)exit(OVERFLOW);
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
return OK;
}
Status DestroyStack(SqStack *S)
{ if(S->base){
free(S->base);
S->base=S->top=NULL;
S->stacksize=0;
return OK;
}
}
Status ClearStack(SqStack *S)
{ if(S->base)
{ S->top=S->base;
return OK;
}
else return ERROR;
}
Status StackEmpty(SqStack S)
{ if(S.base&&S.base==S.top)return TRUE;
else return FALSE;
}
int StackLength(SqStack S)
{ if(S.base)return(S.top-S.base);
else return -1;
}
Status GetTop(SqStack S,SElemType *e)
{ if(StackEmpty(S))return ERROR;
*e=*(S.top-1);
return OK;
}
Status Push(SqStack *S,SElemType e)
{ if(S->top-S->base>=S->stacksize){
S->base=(SElemType *)realloc(S->base,
(S->stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S->base)exit(OVERFLOW);
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*(S->top++)=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{ if(StackEmpty(*S))return ERROR;
*e=*(--S->top);
return OK;
}
void PrintStack(SqStack S)
{ while(S.base<S.top)printf("%3d",*S.base++);
printf("\n");
}
main()
{ char ch;
SElemType e;
SqStack S;
InitStack(&S);
ch=getchar();
while(ch!='q')
{ switch(ch)
{ case 'i':
printf("Input a elem to push:");
scanf("%d",&e);
Push(&S,e);
break;
case 'o':
Pop(&S,&e);
printf("number %d popup",e);
break;
case 'p':
PrintStack(S);
break;
}
getchar();
ch=getchar();
}
}
字符串操作算法
#include"likec.h"
typedef struct{
char *ch;
int length;
}HString;
Status InitStr(HString *T)
{ T->ch=NULL;
T->length=0;
}
Status StrAssign(HString *T,char *chars)
{ int i,j;
char *c;
if(T->ch)free(T->ch);
for(i=0,c=chars;*c;++i,++c);
if(!i){T->ch=NULL; T->length=0;}
else{
c=(char *)malloc(i*sizeof(char));
if(!c)exit(OVERFLOW);
T->ch=c;
for(j=0;j<i;j++)T->ch[j]=chars[j];
T->length=i;
}
return OK;
}
int StrLength(HString S)
{ return S.length;
}
int StrCompare(HString S,HString T)
{ int i;
for(i=0;i<S.length&&i<T.length;++i)
if(S.ch[i]!=T.ch[i])return S.ch[i]-T.ch[i];
return S.length-T.length;
}
Status ClearString(HString *S)
{ if(S->ch){
free(S->ch);
S->ch=NULL;
S->length=0;
return OK;
}
}
Status Concat(HString *T,HString S1,HString S2)
{ int i;
ClearString(T);
T->ch=(char *)malloc((S1.length+S2.length)*sizeof(char));
if(!T->ch)exit(OVERFLOW);
for(i=0;i<S1.length;i++)T->ch[i]=S1.ch[i];
for(;i<S1.length+S2.length;i++)T->ch[i]=S2.ch[i-S1.length];
T->length=S1.length+S2.length;
return OK;
}
Status SubString(HString *Sub,HString S,int pos,int len)
{ int i;
if(pos<1||pos>S.length||len<0||len>S.length-pos+1)return ERROR;
if(Sub->ch)free(Sub->ch);
if(len==0){Sub->ch=NULL; Sub->length=0;}
else
{ Sub->ch=(char *)malloc(len*sizeof(char));
for(i=0;i<len;i++)Sub->ch[i]=S.ch[pos-1+i];
Sub->length=len;
}
return OK;
}
void PrintString(HString S)
{ int i;
for(i=0;i<S.length;i++)printf("%c",S.ch[i]);
printf("\n");
}
main()
{ char temp[80];
HString S1,S2,T;
InitStr(&S1); InitStr(&S2); InitStr(&T);
gets(temp);
StrAssign(&S1,temp);
PrintString(S1);
SubString(&S2,S1,3,8);
PrintString(S2);
Concat(&T,S1,S2);
PrintString(T);2
}
字符串匹配算法
#define MAXSTRLEN 255
int next[100];
typedef unsigned char SString[MAXSTRLEN+1];
int Index(SString S,SString T,int pos)
{ int i=pos,j=1;
while(i<=S[0]&&j<=T[0]){
if(S[i]==T[j]){++i;++j;}
else{i=i-j+2; j=1;}
}
if(j>T[0])return i-T[0];
else return 0;
}
void Assign(SString S)
{ int i=0;
char str[255];
printf("Please input a string:");
gets(str);
S[0]=strlen(str);
while(i<S[0]){
S[i+1]=str[i];
i++;
}
}
int Index_KMP(SString S,SString T,int pos)
{ int i=pos,j=1;
while(i<=S[0]&&j<=T[0]){
if(j==0||S[i]==T[j]){++i;++j;}
else j=next[j];
}
if(j>T[0])return i-T[0];
else return 0;
}
void get_next(SString T)
{ int i=1,j=0;
next[1]=0;
while(i<T[0]){
if(j==0||T[i]==T[j]){++i;++j;next[i]=j;}
else j=next[j];
}
}
main()
{ SString S,T;
int i;
Assign(S);
Assign(T);
get_next(T);
for(i=0;i<10;i++)printf("%5d",next[i]);
printf("\n");
i=Index_KMP(S,T,1);
/* i=Index(S,T,1);*/
printf("%d\n",i);
}