数据结构（C语言版）

C语言经典(C语言必看文档)数据结构C语言实现系列［1］一一线性表#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是关于线性表顺序存储操作的16种算法*//*****************************************************************"structList{elemType*list;intsize;intmaxSize;）；voidagainMalloc(structList*L)(/*空间扩展为原来的2倍，并由p指针所指向，原内容被自动拷贝到p所指向的存储空间*/elemType*p=realloc(L->listr2*L->maxSize*sizeof(elemType));if(!p){ /*分配失败则退出运行*/printf("存储空间分配失败！")；exit(1);1L->list=p;/*使list指向新线性表空间*/L->maxSize=2*L->maxSize;/*把线性表空间大小修改为新的长度*/)/*1.初始化线性表L,即进行动态存储空间分配并置L为一个空表*/voidinitList(structList*LZintms)(/*检查ms是否有效，若无效的则退出运行*/if(ms<=0){printf("MaxSize非法！H;exit(l);/*执行此函数中止程序运行，此函数在stdlib.h中有定义*/)L->maxSize=ms;/★设置线性表空间大小为ms*/L->size=0;L->list=malloc(ms*sizeof(elemType));if(!L->list){printf("空间分配失败！”)；

exit(1);}return;}/*2.清除线性表L中的所有元素，释放存储空间，使之成为一个空表*/voidclearList(structList*L)(if(L->list!=NULL){free(L->list);L->list=0;L->size=L->maxSize=0;|return;}/*3.返回线性表L当前的长度，若L为空则返回0*/intsizeList(structList*L)(returnL->size;}/*4.判定线性表L是否为空，若为空则返回1,否则返回0*/intemptyList(structList*L)(if(L->size==0){return1;)else{return0;))/*5.返回线性表L中第pos个元素的值，若pos超出范围，则停止程序运行*/elemTypegetElem(structList*L,intpos)(if(pos<1pos>L->size){ /★若pos越界则退出运行*/printf("元素序号越界！");exit(1);}returnL->list[pos-1]; /*返回线性表中序号为pos值的元素值*/}/*6.顺序扫描(即遍历)输出线性表L中的每个元素*/voidtraverseList(structList*L)

inti;for(i=0;i<L->size;i++){printf(*'%d”,L->list[i]);}printf(MM);return;}/*7.从线性表L中查找值与x相等的元素，若查找成功则返回其位置，否则返回-1*/intfindList(structList★L,elemTypex)(inti;for(i=0;i<L->size;i++){if(L->list[i]==x){returni;)}return-1;)/*8.把线性表L中第pos个元素的值修改为x的值，若修改成功返回1,否则返回0*/intupdatePosList(structList*LZintpos,elemTypex)(if(pos<1pos>L->size){ /*若pos越界则修改失败*/return0;}L->list[pos-1]=x;return1;}/*9.向线性表L的表头插入元素x*/voidinserFirstList(structList*L,elemTypex)(inti;if(L->size==L->maxSize){againMalloc(L);}for(i=L->size-1;i>=0;i--){L->list[i+1]=L->list[i];}L->list[0]=x;L->size++;return;

/*10.向线性表L的表尾插入元素x*/voidinsertLastList(structList*L,elemTypex)(if(L->size==L->maxSize){ /*重新分配更大的存储空间*/againMalloc(L);}L->list[L->size]=x;/*把x插入到表尾*/L->size++;/*线性表的长度增加1*/return;)/★11.向线性表L中第pos个元素位置插入元素x,若插入成功返回1,否则返回0*/intinsertPosList(structList*LZintpos,elemTypex)(inti;if(pos<1pos>L->size+1){ /*若pos越界则插入失败*/return0;)if(L->size==L->maxSize){ /*重新分配更大的存储空间*/againMalloc(L);)for(i=L->size-1;i>=pos-1;i——){L->list[i+1]=L->list[i];}L->list[pos-1]=x;L->size++;return1;)/*12.向有序线性表L中插入元素x,使得插入后仍然有序*/voidinsertOrderList(structList*LZelemTypex)(intizj;/*若数组空间用完则重新分配更大的存储空间*/if(L->size==L->maxSize){againMalloc(L);}/*顺序查找出X的插入位置*/for(i=0;i<L->size;i++){if(x<L->list[i]){break;)}/*从表尾到下标i元素依次后移一个位置，把i的位置空出来*/for(j=L->size-1;j>=i;j——)

L->list[j+1]=L->list[j]；/*把x值赋给下标为i的元素*/L->list[i]=x;/*线性表长度增加1*/L->size++;return;}/*13.从线性表L中删除表头元素并返回它，若删除失败则停止程序运行*/elemTypedeleteFirstList(structList*L)(elemTypetemp;inti;if(L->size==0){printf("线性表为空，不能进行删除操作！");exit(1);}temp=L->list[0];for(i=1;i<L->size;i++)L->list[i-l]=L->list[i];L->size--;returntemp;)/*14.从线性表L中删除表尾元素并返回它，若删除失败则停止程序运行*/elemTypedeleteLastList(structList*L)(if(L->size==0){printf(”线性表为空，不能进行删除操作！exit(1);}L->size--;returnL->list[L->size]; /*返回原来表尾元素的值*/}/*15.从线性表L中删除第pos个元素并返回它，若删除失败则停止程序运行*/elemTypedeletePosList(structList*LZintpos)(elemTypetemp;inti;if(pos<1pos>L->size){ /*pos越界则删除失败*/printf("pos值越界，不能进行删除操作！n);exit(1);}temp=L->list[pos-1];

for(i=pos;i<L->size;i++)L->list[i-1]=L->list[i];L->size——;returntemp;}/*16.从线性表L中删除值为x的第一个元素，若成功返回1,失败返回0*/intdeleteValueList(structList*LZelemTypex)(int1,j;/★从线性表中顺序查找出值为x的第一个元素*/for(i=0;i<L->size;i++){if(L->list[i]==x){break;))/*若查找失败，表明不存在值为x的元素，返回0*/if(i==L->size){return0;}/*删除值为x的元素[i]*/for(j=i+1;j<L->size;j++){L->list[j-1]=L->list[j];}L->size—;return1;}voidmain()(inta[10]=[2,4,6,8,10,12,14,16,18,20);inti;structListL;initList(&L,5);for(i=0;i<10;i++){insertLastList(&Lra[i]);}insertPosList(&LZ11r48); insertPosList(&LZ1,64);printf(n%d”，getElem(&L,1));traverseList(&L);printf(n%d”,findList(&LZ10));updatePosList(&LZ3,20);printf(n%d”,getElem(&Lf3));traverseList(&L);deleteFirstList(&L); deleteFirstList(&L);

deleteLastList(&L);;deleteLastList(&L);;deletePosList(&LZ7);deletePosList(&LZ5);printf(H%d”,sizeList(&L));printf(H%d",emptyList(&L));traverseList(&L);clearList(&L);return0;#include<stdio.h>#include<stdlib.h>#defineNN12#defineMM20typedefintelemType;/★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★Hr*************************************//* 以下是关于线性表链接存储(单链表)操作的16种算法 */structsNode{ /*定义单链表结点类型*/elemTypedata;structsNode*next;}；/★1.初始化线性表，即置单链表的表头指针为空*/voidinitList(structsNode**hl)(*hl=NULL;return;}/*2.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表*/voidclearList(structsNode**hl)(/*cp和np分别作为指向两个相邻结点的指针*/structsNode*cpz*np;cp=*hl;/*遍历单链表，依次释放每个结点*/while(cp!=NULL){np=cp->next;/*保存下•个结点的指针*/free(cp);cp=np;}*hl=NULL; /*置单链表的表头指针为空*/return;/*3.返回单链表的长度*/intsizeList(structsNode*hl)(intcount=0; /*用于统计结点的个数*/while(hl!=NULL){count++;hl=hl->next;}returncount;)/*4.检查单链表是否为空，若为空则返回1,否则返回0*/intemptyList(structsNode*hl)(if(hl==NULL){return1;}else{return0;))/*5.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行*/elemTypegetElem(structsNode*hlfintpos)(inti=0; /*统计已遍历的结点个数*/if(pos<1){printf("pos值非法，退出运行！”)；exit(1);)while(hl!=NULL){i++；if(i==pos){break;)hl=hl->next;}if(hl!=NULL){returnhl->data;}else{printf("pos值非法，退出运行！");exit(1);)

/*6.遍历一个单链表★/voidtraverseList(structsNode*hl)(while(hl!=NULL){printf(n%5dH,hl->data);hl=hl->next;)printf(Hn);return;)/*7.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL*/elemType*findList(structsNode*hl,elemTypex)(while(hl!=NULL){if(hl->data==x){return&hl->data;}else{hl=hl->next;))returnNULL;)/*8.把单链表中第pos个结点的值修改为x的值，若修改成功返回1,否则返回0*/intupdatePosList(structsNode★hl,intpos,elemTypex)(inti=0;structsNode*p=hl;while(p!=NULL){ /*查找第pos个结点*/i++；if(pos==i){break;}else{p=p->next;))if(pos==i){p->data=x;return1;}else{return0;

/*9.向单链表的表头插入一个元素*/voidinsertFirstList(structsNode**hl,elemTypex)structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf(”内存分配失败，退出运行！n)；exit(1);}newP->data=x; /*把x的值赋给新结点的data域*//*把新结点作为新的表头结点插入*/newP->next=*hl;*hl=newP;return;}/★10.向单链表的末尾添加一个元素*/voidinsertLastList(structsNode**hlrelemTypex)(structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf(”内在分配失败，退出运行！");exit(1);}/*把X的值赋给新结点的data域，把空值赋给新结点的next域*/newP->data=x;newP->next=NULL;/★若原表为空，则作为表头结点插入*/if(*hl==NULL){*hl=newP;}/*查找到表尾结点并完成插入*/else(structsNode*p=NULL;while(p->next!=NULL){p=p->next;)p->next=newP;}return;

/*11.向单链表中第pos个结点位置插入元素为X的结点，若插入成功返回1,否则返回0*/intinsetPosList(structsNode**hl,intpos,elemTypex){inti=0;structsNode*newP;structsNode*cp=*hl,*ap=NULL;/*对pos值小于等于0的情况进行处理*/if(pos<=0){printf("pos值非法，返回0表示插入失败！”)；return0;}/*查找第pos个结点*/while(cp!=NULL){i++；if(pos==i){break;}else{ap=cp;cp=cp->next;))/*产生新结点，若分配失败，则停止插入*/newP=malloc(sizeof(structsNode));if(newP==NULL){printf(”内存分配失败，无法进行插入操作！”)；return0;)/*把x的值赋给新结点的data域*/newP->data=x;/*把新结点插入到表头★/if(ap==NULL){newP->next=cp; /*或改为newP->next=*hl;*/*hl=newP;}/*把新结点插入到ap和cp之间*/else(newP->next=cp;ap->next=newP;}return1; /*插入成功返回1*/}/*12.向有序单链表中插入元素x结点，使得插入后仍然有序*/voidinsertOrderList(structsNode**hlzelemTypex)

/*把单链表的表头指针赋给CP，把ap置空*/structsNode*cp=*hl,*ap=NULL;/*建立新结点*/structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf("内在分配失败，退出运行！")；exit(1);}newP->data=x; /*把x的值赋给新结点的data域*//*把新结点插入到表头*/if((cp==NULL)(x<cp->data)){/*这个地方要注意呀*/newP->next=cp;*hl=newP;return;}/*顺序查找出x结点的插入位置*/while(cp!=NULL){if(x<cp->data){break;}else(ap=cp;cp=cp->next;}}/*把x结点插入到ap和cp之间*/newP->next=cp;ap->next=newP;return;)/*13.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行*/elemTypedeleteFirstList(structsNode**hl)(elemTypetemp;structsNode*p=*hl; /*暂存表头结点指针，以便回收*/if(*hl==NULL){printf("单链表为空，无表头可进行删除，退出运行！”)；exit(1);}*hl=(*hl)->next; /*使表头指针指向第二个结点*/temp=p->data; /*暂存原表头元素，以便返回★/

free(p);returntemp;/*free(p);returntemp;/*返回第•个结点的值*//*14.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行*/elemTypedeleteLastList(structsNode**hl)(elemTypetemp;/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/structsNode*cp=*hl;structsNode*ap=NULL;/★单链表为空则停止运行*/if(cp==NULL){printf(”单链表为空，无表头进行删除，退出运行！»,);exit(1);}/*从单链表中查找表尾结点，循环结束时cp指向表尾结点，ap指向其前驱结点*/while(cp->next!=NULL){ap=cp;cp=cp->next;)/*若单链表中只有一个结点，则需要修改表头指针*/if(ap==NULL){*hl=(*hl)->next; /*或改为=NULL;*/}/*删除表尾结点*/else(ap->next=NULL;}/*暂存表尾元素，以便返回*/temp=cp->data;free(cp); /★回收被删除的表尾结点★/returntemp; /★返回表尾结点的值★/}/*15.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行*/elemTypedeletePosList(structsNode**hlzintpos)(inti=0;elemTypetemp;/★初始化cp和ap指针，使cp指向表头结点，使ap为空*/structsNode*cp=*hl;structsNode*ap=NULL;/*单链表为空或pos值非法则停止运行*/

if((cp==NULL)(pos<=0)){printf("单链表为空或pos值不正确，退出运行!exit(1);}/*从单链表中查找第POS个结点，找到后由cp指向该结点，由ap指向其前驱结点★/while(cp!=NULL){i++；if(i==pos){break;}ap=cp;cp=cp->next;)/*单链表中没有第pos个结点*/if(cp==NULL){printf("pos值不正确，退出।运行！u);exit(1);}/*若pos等于1,则需要删除表头结点*/if(pos==1){*hl=(*hl)->next; /*或改为*hl=cp->next;*/}/★否则删除非表头结点，此时cp指向该结点，ap指向前驱结点★/else{ap->next=cp->next;)/*暂存第pos个结点的值，以便返回*/temp=cp->data;free(cp); /*回收被删除的第pos个结点*/returntemp;/*返回在temp中暂存的第pos个结点的值*/}/*16.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0*/intdeleteValueList(structsNode**hl,elemTypex)(/*初始化cp和ap指针，使cp指向表头结点，使ap为空*/structsNode*cp=*hl;structsNode*ap=NULL;/*从单链表中查找值为X的结点，找到后由cp指向该结点，由ap指向其前驱结点★/while(cp!=NULL){if(cp->data==x){break;

ap=cp;cp=cp->next;}/*若查找失败，即该单链表中不存在值为x的结点，则返回0*/if(cp==NULL){return0;)/*假如删除的是表头或非表头结点则分别进行处理*/if(ap==NULL){*hl=(*hl)->next; /*或改为*hl=cp->next*/}else{ap->next=cp->next;}free(cp); /*回收被删除的结点*/return1; /*返回1表示删除成功*/intmain(intargc,char*argv[])(inta[NN];inti;structsNode*p,*h,*s;srand(time(NULL));initList(&p);for(i=0;i<NN;i++){a[i]=rand()&MM;)printf("随机数序列：”)；for(i=0;i<NN;i++){printf(H%5dnza[i]);}printf(Mn);printf(“随机数逆序：“);for(i=0;i<NN;i++){insertFirstList(&pza[i]);}traverseList(p);printf("单链表长度：%5d”，sizeList(p));for(h=p;h!NULL;h=h->next){while(deleteValueList(&(h->next),h->data)){

}printf("去除重复数：“);traverseList(p);printf("单链表长度：%5d",sizeList(p));h=NULL;for(s=p;s!=NULL;s=s->next){insertOrderList(&h,s->data);)printf("有序表序列：，')；traverseList(h);clearList(&p);system(npausen);return0;数据结构C语言实现系列［2］一栈#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是关于栈顺序存储操作的6种算法 */structstack{elemType*stack; /*存储栈元素的数组指针*/inttop; /*存储栈顶元素的下标位置★/intmaxSize; /*存储stack数组的长度*/}；voidagainMalloc(structstack*s)(/*空间扩展为原来的2倍，原内容被自动拷贝到p所指向的存储空间中★/elemType*p;p=realloc(s->stackr2*s->maxSize*sizeof(elemType));if(!p){printf(”内在分配失败！”);exit(1);}/*把栈空间的大小修改新的长度*/s->stack=p; /*使stack/*把栈空间的大小修改新的长度*/s->maxSize=2*s->maxSize;return;

/*1.初始化栈S为空*/voidinitStack(structstack★s,intms)(if(ms<=0){printf(nms的值非法！H);exit(1);)s->maxSize=ms;s->stack=malloc(ms*(sizeof(elemType)));if(!s->stack){printf(”内在分配失败！");exit(1);)s->top=-1; /*初始置栈为空*/return;)/*2.新元素进栈，即把它插入到栈顶*/voidpush(structstack*s,elemTypex)(/*若栈空间用尽则重新分配更大的存储空间*/if(s->top==s->maxSize-1){againMalloc(s);)s->top++; /★栈顶指针后移一个位置*/s->stack[s->top]=x; /*将新元索插入到栈顶*/return;)/*3.删除(弹出)栈顶元素并返回其值*/elemTypepop(structstack*s)(/*若栈空则退出运行*/if(s->top==-1){printf("栈空，无元素出栈！”)；exit(1);)s->top—； /*栈顶指针减1表示出栈*/returns->stack[s->top+l]; /*返回原栈顶元素的值*//*4.读取栈顶元素的值*/

elemTypepeek(structstack*s)/*若栈空则退出运行*/if(s->top==-1){printf("栈空，无元素可读取！”)；exit(1);)returns->stack[s->top]; /★返回原栈顶元素的值*/}/*5.判断s是否为空，若是则返回1表示其，否则返回0表示假*/intemptyStack(structstack*s)(if(s->top==-1){return1;}else(return0;/*6.清除栈s中的所有元素，释放动态存储空间*/voidclearStack(structstack*s)(if(s->stack){free(s->stack);s->stack=NULL;s->top=-1;s->maxSize=0;}return;intmain()(structstacks;inta[8]={3,8,5,17,9,30,15,22);inti;initStack(&s,5);for(i=0;i<8;i++){push(&s,a[i]);)printf(H%d”,pop(&s));printf(n%d”，pop(&s));

push(&s,68);printf(M%d”，peek(&s));printf(M%d”，pop(&s));while(!emptyStack(&s)){printf(M%d”，pop(&s));)printf("n);clearStack(&s);system('*pausen);return0;/* 以下是关于栈链接存储操作的6种算法structsNode{elemTypedata;structsNode*next;)；/*1,初始化链栈为空*/voidinitStack(structsNode**hs)(*hs=NULL;return;)/*2.向链中插入一个元素(入栈)*/voidpush(structsNode**hszelemTypex)(structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf("内在空间分配失败！”)；exit(1);)newP->data=x; /*给新分配的结点赋值*//*向栈顶插入新结点*/newP->next=*hs;*hs=newP;return;}/*3.从链栈中删除一个元素并返回它(出栈)elemTypepop(structsNode**hs)

structsNode*p;elemTypetemp;if(*hs==NULL){printf("栈空无法删除！");exit(1);)/*暂存栈顶结点指针，并使栈顶指针指向下一个结点*/p=*hs;*hs=p->next;/*暂存原栈顶元素以便返回，同时回收原栈顶结点*/temp=p->data;free(p);returntemp; /*返【可原栈顶元素*/}/*4.读取栈顶元素*/elemTypepeek(structsNode**hs)(/*对于空栈则退出运行★/if(*hs==NULL){printf("栈空，无栈顶元素！");exit(1);)return(*hs)->data; /*返回栈顶结点的值*/}/*5.判断链栈是否为空，为空返回1,否则返回0*/intemptyStack(structsNode**hs)(if(*hs==NULL){return1;}else{return0;))/*6.清除链栈为空*/voidclearStack(structsNode**hs)(structsNode*cp,*np;cp=*hs; /*使cp指向栈顶结点*//*从栈底依次删除每个结点*/while(cp!=NULL){

np=cp->next;free(cp);cp=np;}*hs=NULL; /*置链栈为空*/return;数据结构C语言实现系列[3]—关于栈的一些习题#include<stdio.h>#include<stdlib.h>typedefintelemType;#includenLinkAccess.cH/*对由fname所指字符串为文件名的程序文件进行括号配对检查*/intbracketsCheck(char*fname)(structsNode*a; /*申明一个链栈*/charch;FILE*fp;fp=fopen(fname,"rn);if(!fp){printf("File,%s*nofound!",fname);exit(1);}initStack(&a);ch=fgetc(fp); /★从文件中读取第一个字符到ch★/while(ch!=EOF){printf(M%cnrch);switch(ch){case'{':case1[1:case'push(&a,ch);break;case*},:if(peek(&a)==1{*){pop(&a);}else{return0;break;case*]*:

if(peek(&a)==1[*){pop(&a);}else{return0;)break;case*)1:if(peek(&a)==1(*){pop(&a);}else{return0;}break;)ch=fgetc(fp);}if(emptyStack(&a)){return1;}else{return0;intmain()(if(bracketsCheck(nABCD.cn)){printf("Match!n);}else{printf(nMissmatch!");)system(Mpause°);return0;)#include<stdio.h>#include<stdlib.h>typedefdoubleelemType;#includenLinkA/*计算由str所指向字符串的后缀表达式(逆波兰式)的值*/doublecompute(char*str)(structsNode*s;/*用s栈存储操作数和中间计算结果，元素类型为double*/doublex,y; /★x,y用于保存浮点数*/inti=0; /*i用于扫描后缀表达式*/

typedefdoubleelemType;initStack(&s);/*扫描后缀表达式中的每个字符，并进行相应处理★/while(str[i])(if(str[i]==*1){ /*扫描到空格字符不做任何处理*/i++；continue;)switch(str[i])(case'+':x=pop(&s)+pop(&s);i++；break;case'-：x=pop(&s)； /*弹出减数*/x=pop(&s)-X；i++;break;case'*'：x=pop(&s)*pop(&s);i++；break;case*/*:x=pop(&s); /★弹出除数*/if(x!=0.0)(x=pop(&s)/X；}else(printf(“除数为0!");exit(1);}i++；break;default:/*扫描到的是浮点数字符串，生成对应的浮点数*/x=0; /*x保存扫描到的整数部分的值*/while(str[i]>=48&&str[i]<=57)(x=x*10+str[i]-48;i++;

if(str[i]doublej=10.0;/*j作为相应小数位的权值*/i++；y=0;while(str[i]>=48&&str[i]<=57)(y=y+(str[i]-48)/j;i++;j*=10;1x+=y;/*把小数部分合并到整数部分x中*/))/*把扫描转换后或进行相应运算后得到的浮点数压入栈s中*/push(&s,x);}/*若计算结束后栈为空则中止运算*/if(emptyStack(&s))(printf("后缀表达式错误！");exit(1);)/*若栈中只有一个元素，则它就是该后缀表达式的值，否则出错*/X=pop(&S);if(emptyStack(&s)){returnx;)else(printf("后缀表达式错误！M);exit(1);})/*返回运算符。p所对应的优先级数值*/intprecedence(charop)(switch(op){case1+1:casereturn1;case***:case1/1:return2;case'(':case101;default:return0;数据结构c语言实现系列［4］一队列#include<stdio.h>#include<stdlib.h>typedefintelemType;/★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★if★/* 以下是关于队列链接存储操作的6种算法 */structsNode{/★值域*//*/★值域*//*链接指针*//*队首指针*//*队尾指针*/structsNode*next;}；structqueueLK{structsNode*front;structsNode*rear;)；/*1.初始化链队*/voidinitQueue(structqueueLK*hq)(hq->front=hq->rear=NULL; /*把队首和队尾指针置空*/return;}/*2.向链队中插入一个元素x*/voidenQueue(structqueueLK*hq,elemTypex)(/★得到一个由newP指针所指向的新结点*/structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf("内存空间分配失败！");

exit(1);}/*把X的值赋给新结点的值域，把新结点的指针域置空*/newP->data=x;newP->next=NULL;/★若链队为空，则新结点即是队首结点又是队尾结点*/if(hq->rear==NULL){hq->front=hq->rear=newP;}else{/*若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点*/hq->rear=hq->rear->next=newP; /★注重赋值顺序哦*/)return;)/*3.从队列中删除一个元素*/elemTypeoutQueue(structqueueLK*hq)(structsNode*p;elemTypetemp;/*若链队为空则停止运行*/if(hq->front==NULL){printf(”队歹ij为空，无法删除！n);exit(1);}temp=hq->front->data; /*暂存队尾元素以便返回*/p=hq->front; /*暂存队尾指针以便回收队尾结点★/hq->front=p->next; /*使队首指针指向下一个结点*//★若删除后链队为空，则需同时使队尾指针为空★/if(hq->front==NULL){hq->rear=NULL;}free(p); /*回收原队首结点*/returntemp;/*返回被删除的队首元素值*/}/*4.读取队首元素*/elemTypepeekQueue(structqueueLK*hq)(/★若链队为空则停止运行★/if(hq->front==NULL){printf("队列为空，无法删除！");exit(1);

returnhq->front->data;/*returnhq->front->data;/*返回队首元素*//*5.检查链队是否为空，若为空则返回1,否则返回0*/intemptyQueue(structqueueLK*hq)(/*判定队首或队尾任一个指针是否为空即可*/if(hq->front==NULL){return1;}else{return0;))/*6.清除链队中的所有元素*/voidclearQueue(structqueueLK*hq)(structsNode*p=hq->front; /*队首指针赋给p*//★依次删除队列中的每一个结点，最后使队首指针为空★/while(p!=NULL){hq->front=hq->front->next;free(p);p=hq->front;} /*循环结束后队首指针已经为空*/hq->rear=NULL; /*置队尾指针为空*/return;intmain(intargcrchar*argv[])(structqueueLKq;inta[8]={3,8,5,11,9,30,15,22);inti;initQueue(&q);for(i=0;i<8;i++){enQueue(&q,a[i]);)printf(n%d”,outQueue(&q));printf(M%d”,outQueue(&q));enQueue(&qz68);printf(n%d”，peekQueue(&q));printf(M%d”，outQueue(&q));while(!emptyQueue(&q)){printf(n%d”，outQueue(&q));

printf(nn);clearQueue(&q);system(Hpausen);#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是关于队列链接存储操作的typedefintelemType;/* 以下是关于队列链接存储操作的6种算法 *//*值域*//*链接指针*//*队首指针*//*值域*//*链接指针*//*队首指针*//*队尾指针*/)；structqueueLK{structsNode*frent;structsNode*rear;)；/*1.初始化链队*/voidinitQueue(structqueueLK*hq)(hq->front=hq->rear=NULL; /*把队首和队尾指针置空*/return;}/*2.向链队中插入一个元素x*/voidenQueue(structqueueLK*hq,elemTypex)(/★得到一个由newP指针所指向的新结点★/structsNode*newP;newP=malloc(sizeof(structsNode));if(newP==NULL){printf(“内存空间分配失败！”);exit(1);)/*把X的值赋给新结点的值域，把新结点的指针域置空*/newP->data=x;newP->next=NULL;/*若链队为空，则新结点即是队首结点又是队尾结点★/if(hq->rear==NULL){hq->front=hq->rear=newP;}else{/*若链队非空，则依次修改队尾结点的指针域和队尾指针，使之指向新的队尾结点*/

hq->rear=hq->rear->next=newP;/*注重赋值顺序哦*//*注重赋值顺序哦*//*3.从队列中删除一个元素*/elemTypeoutQueue(structqueueLK*hq)(structsNode*p;elemTypetemp;/*若链队为空则停止运行*/if(hq->front==NULL){printf("队列为空，无法删除！”)；exit(1);)temp=hq->front->data; /*暂存队尾元素以便返回*/p=hq->front; /*暂存队尾指针以便回收队尾结点*/hq->front=p->next; /*使队首指针指向下一个结点*//*若删除后链队为空，则需同时使队尾指针为空*/if(hq->front==NULL){hq->rear=NULL;)free(p); /*回收原队首结点*/returntemp; /*返回被删除的队首元素值*/}/*4.读取队首元素*/elemTypepeekQueue(structqueueLK*hq)(/*若链队为空则停止运行*/if(hq->front==NULL){printf("队列为空，无法删除！exit(1);)returnhq->front->data; /★返回队首元素*/)/*5.检查链队是否为空，若为空则返回1,否则返回0*/intemptyQueue(structqueueLK*hq)(/*判定队首或队尾任一个指针是否为空即可*/if(hq->front==NULL){return1;}else{return0;

/*6.清除链队中的所有元素*/voidclearQueue(structqueueLK*hq)structsNode*p=hq->front; /*队首指针赋给p*//*依次删除队列中的每一个结点，最后使队首指针为空*/while(p!=NULL){hq->front=hq->front->next;free(p);p=hq->front;} /*循环结束后队首指针已经为空*/hq->rear=NULL; /*置队尾指针为空*/return;intmain(intargc,char*argv[])(structqueueLKq;inta[8]={3,8,5,17,9,30,15,22};inti;initQueue(&q);for(i=0;i<8;i++){enQueue(&q,a[i]);)printf(n%d”,outQueue(&q));printf(M%d”,outQueue(&q));enQueue(&qz68);printf(n%d”,peekQueue(&q));printf(n%d”,outQueue(&q));while(!emptyQueue(&q)){printf(H%d”,outQueue(&q));)printf(nn);clearQueue(&q);system(HpauseH);数据结构c语言实现系列［5］一串串的简单模式匹配

#include<stdio.h>#include<stdlib.h>/*定义单链表结构体★/structnode(charch;structnode*next;)；/*初始化单链表*/voidinit(structnode**h)(*h=(structnode*)malloc(sizeof(structnode));(*h)->next=NULL;return;)/*将x结点插入到链表后*/voidappend(structnode*p,intx)(structnode*s;s=(structnode*)malloc(sizeof(structnode));s->ch=x;s->next=NULL;/*移动到表尾*/while(p->next!=NULL)(p=p->next;}p->next=s;return;}voiddisplay(structnode*p)(printf(nYoutypedstringis:n);while(p->next!=NULL)printf(n%cMzp->next->ch);

p=p->next;)printf(Mn);return;)intmain(intargc,char*argv[])(structnode*tz*s; /*s为主串，t为模式串*/structnode*sNextz*p,*q;inti,x=0;init(&s);printf("Pleasetypemainstring:n);while(x!=1,){x=getchar();if(x!=*1)(append(s,x); /*添加到表尾*/})display(s);init(&t);printf(HPleasetypesubstring:n);x=0;while(x!='1)(x=getchar();if(x!=1')(append(t,x); /*添力口到表尾*/)}display(t);/*初始化*/sNext=s->next;p=sNext;q=t->next;i=1；/*从开始字符进行比较*/

while((p->next!=NULL)&&(q->next!=NULL))/*进行匹配检验★/if(p->ch==q->ch)(p=p->next;q=q->next;)else(sNext=sNext->next;p=sNext; /*指向主串中的下一个*/q=t->next;/*指针后退重新开始匹配★/i++; /*记录位置*/})/*输出结果★/if((q->next)==NULL&&(t->next->ch==s->next->ch))(printf(Mmatchposition:为d”，i);)else{printf(nNotmatch!n);)printf(MM;return0;}数据结构C语言实现系列［6］一堆#include<stdio.h>#include<stdlib.h>typedefintelemType;/* 以下是关于堆顺序存储操作的5种算法 *//★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★it//★定义堆的顺序存储类型★/structheap{elemType*heap; /*定义指向动态数组空间的指针*/intlen; /*定义保存堆长度的变量*/intmaxSize;/*用于保存初始化时所给的动态数组空间的大小*//*1.初始化堆★/voidinitHeap(structheap*hbt,intms)(/*检查ms的值是否有效*/if(ms<=0){printf("数组长度参数非法！")；exit(1);}/*动态分配存储的数组空间*/hbt->heap=malloc(ms*sizeof(elemType));if(hbt->heap==NULL){printf("空间分配失败！");exit(1);}/*设置maxSize域和len域的值*/hbt->maxSize=ms;hbt->len=0;return;}/*2.清除堆*/voidclearHeap(structheap*hbt)(if(hbt->heap!=NULL){free(hbt->heap);hbt->heap=NULL;hbt->len=0;hbt->maxSize=0;)return;}/*3.检查一个堆是否为空*/intemptyHeap(structheap*hbt)

if(0==hbt->len){return1;)else{return0;/*4.向堆中插入一个元素*/voidinsertHeap(structheap*hbt,elemTypex)(inti;/*堆满时数组空间扩展为原来的2倍，原内容被自动拷贝到P所指向的存储空间中*/if(hbt->len==hbt->maxSize){elemType*p;p=realloc(hbt->heapz2*hbt->maxSize*sizeof(elemType));if(p==NULL){printf("存储空间分配失败！”)；exit(1);}hbt->heap=p; /*堆数组空间指向新空间*/hbt->maxSize=2*hbt->maxSize; /*修改数组空间的大小*/)/*向堆尾添加新元素*/hbt->heap[hbt->len]=x;hbt->len++;/*用i指向待调整元素的位置，初始指向新元素所在的堆尾位置*/i=hbt->len-1;/*寻找新元素的最终位置，每次使双亲元素下移一层*/while(0!=i){intj=(i-1)/2; /*j指向下标为i的元素的双亲*//*比较调整结束退出循环*/if(x>=hbt->heap[j]){break;)hbt->heap[i]=hbt->heap[j]; /*双亲元素下移*/i=j；}hbt->heap[i}hbt->heap[i]/*把新元素调整到最终位置*/return;/*5.从堆中删除元素*/elemTypedeleteHeap(structheap*hbt)(elemTypetemp,x;inti,j;/*若为空堆，则显示出错信息并退出运行*/if(0==hbt->len){prints(”堆已空，退出运行！”)；exit(1);}/*将堆顶元素暂存在temp中以便返回*/temp=hbt->heap[0];hbt->len——;/*若删除操作后变为空堆则返回★/if(0==hbt->len){returntemp;)/*将待调整的堆尾元素暂存在X中，以便放入最终位置*/x=hbt->heap[hbt->len];/*用i指向待调整元素的位置，初始指向堆顶位置*/i=0;/*用j指向i的左孩子位置，初始指向下标1的位置*/j=2*i+1;/*寻找待调整元素的最终位置，每次使孩子元素上移一层*/while(j<=hbt->len-1){ /*调整到孩子为空时止*//*若右孩子存在并且较小，应使j指向右孩子*/if((j<hbt->len-1)&&(hbt->heap[j]>hbt->heap[j+1])){j++；}/*若条件成立则调整结束，退出循环*/if(x<=hbt->heap[j]){break;}/*孩子元素上移到双亲位置*/hbt->heap[i]=hbt->heap[j];/*使i和j分别指向下一层结点*/i=j；

2*i+1;)/*把待调整元素放到最终位置*/hbt->heap[i]=x;returntemp;intmain(void)(intI,x;inta[8]={23,56,40,62,38,55,10,16);structheapb;initHeap(&br5);/*向堆b中依次插入数组a中的每一个元素*/for(i=0;i<8;i++){insertHeap(&b,a[i]);)while(!emptyHeap(&b)){x=deleteHeap(&b);printf(n%dH,x);if(!emptyHeap(&b)){printf(“，")；}}printf("n);clearHeap(&b);return0;}数据结构C语言实现系列[7]一二叉树#include<stdio.h>#include<stdlib.h>#defineSTACK_MAX_SIZE30#defineQUEUE_MAX_SIZE30#ifndefelemType

typedefcharelemType;#endif/* 以下是关于二叉树操作的11个简单算法strUCtBTreeNode{elemTypedata;structBTreeNode*left;structBTreeNode*right;)；/*1.初始化二叉树*/voidinitBTree(structBTreeNode**bt)(*bt=NULL;return;}/*2.建立二叉树(根据a所指向的二叉树广义表字符串建立)*/voidcreateBTree(structBTreeNode**btzchar*a)(structBTreeNode*p;structBTreeNode*s[STACK_MAX_SIZE];/*定义s数组为存储根结点指针的栈使用*/inttop=-1;/*定义top作为s栈的栈顶指针，初值为-1,表示空栈*/intk;/*用k作为处理结点的左子树和右子树，k=1处理左子树，k=2处理右子树*/inti=0;/*用i扫描数组a中存储的二叉树广义表字符串，初值为0*/*bt=NULL;/*把树根指针置为空，即从空树开始建立二叉树*//*每循环一次处理一个字符，直到扫描到字符串结束符\0为止*/while(a[i]!='\0'){switch(a[i]){case11:break;/*对空格不作任何处理*/case'(1：if(top==STACK_MAX_SIZE-1){printf("栈空间太小！\nH);exit(1);}top++;s[top]=p;k=1;break;case*),:if(top==-1){printf("二叉树广义表字符串错误！\n”);exit(1);)top--;break;

casek=2;break;default:p=malloc(sizeof(structBTreeNode));p->data=a[i];p->left=p->right=NULL;if(*bt==NULL){*bt=p;}else{if(k==1){s[top]->left=p;}else{s[top]->right=p;}}}i++;/*为扫描下一个字符修改i值*/)return;)/*3.检查二叉树是否为空，为空则返回1,否则返回0*/intemptyBTree(structBTreeNode*bt)(if(bt==NULL){return1;}else{return0;}}/*4.求二叉树深度★/intBTreeDepth(structBTreeNode*bt)(if(bt==NULL){return0;/*对于空树，返回。结束递归*/}else{intdepl=BTreeDepth(bt->left);/*计算左子树的深度*/intdep2=BTreeDepth(bt->right);/*计算右子树的深度*/if(depl>dep2){returndepl+1;}else{returndep2+1;}/*5.从二叉树中查找值为x的结点，若存在则返回元素存储位置，否则返回空值*/

elemType*findBTree(structBTreeNodeelemTypex)if(bt==NULL){returnNULL;}else{if(bt->data==x){return&(bt->data);}else{/*分别向左右子树递归查找*/elemType*p;if(p=findBTree(bt->left,x)){returnp;}if(p=findBTree(bt->right,x)){returnp;)returnNULL;})}/*6.输出二叉树(前序遍历)*/voidprintBTree(structBTreeNode*bt)(/*树为空时结束递归，否则执行如下操作*/if(bt!=NULL){printfbt->data);/*输出根结点的值*/if(bt->left!=NULLbt->right!=NULL){printf(“(”)；printBTree(bt->left);if(bt->right!=NULL){printf(11,n);)printBTree(bt->right);printf(M)0);})return;}/*7.清除二叉树，使之变为一棵空树*/voidclearBTree(structBTreeNode**bt)(if(*bt!=NULL){clearBTree(&((*bt)->left));clearBTree(&((*bt)->right));free(*bt);*bt=NULL;

}return;)/*8.前序遍历*/voidpreOrder(structBTreeNode*bt)(if(bt!=NULL){printf(H%c”，bt->data);/*访问根结点*/preOrder(bt->left); /*前序遍历左子树*/preOrder(bt->right); /*前序遍历右子树*/)return;}/*9.前序遍历*/voidinOrder(structBTreeNode*bt)(if(bt!=NULL){inOrder(bt->left); /*中序遍历左子树*/printf(n%c”，bt->data);/★访问根结点*/inOrder(bt->right); /★中序遍历右子树*/}return;}/*10.后序遍历*/voidpostOrder(structBTreeNode*bt)(if(bt!=NULL){postOrder(bt->left); /*后序遍历左子树★/postOrder(bt->right); /*后序遍历右子树*/printf(n%c”，bt->data); /*访问根结点*/}return;}/*11*按层遍历*/voidlevelOrder(structBTreeNode*bt)(structBTreeNode