注册 登录
编程论坛 → 数据结构与算法

数据结构C程序

Antigloss 发布于 2004-12-30 21:15， 33801 次点击

在重新学数据结构~我会把我写的源代码发上来~希望大家能提出改进意见~谢谢~注释我写得很详细~就算初学者应该也可以看懂~希望能和大家一起讨论~用VC的话，双击main.dsw即可。如果用tc的话，dos下输入tcc main.c functions.c，然后回车即可。 打包下载~~ [attach]1797[/attach]

1. 顺序表的创建和操作

如果用tc的话，dos下输入tcc main.c functions.c，然后回车即可。

definition.h ============================= #define INITSIZE 100 //顺序表初始空间分配量 #define INCREMENT 10 //顺序表空间分配增量

typedef char ElemType; //定义ElemType代表的数据类型

unsigned short listlen; //全局变量，用于记录目前一共有多少个顺序表

//定义顺序表结构 typedef struct{ ElemType *elem; //存储空间基址 unsigned int length; //当前长度 unsigned int listsize; //当前空间分配量 unsigned int e; //用于记录元素编号 }Sqlist;

short Menu(); //打印菜单，请用户选择 short InitList(Sqlist *); //创建顺序表 short InputList(Sqlist *); //插入数据 short DelList(Sqlist *); //删除数据 short Union(Sqlist *); //求顺序表并集 short Purge(Sqlist *); //删除表中重复元素 short Purge2(Sqlist *); //删除表中重复元素 short Bubble(Sqlist *); //冒泡排序 short Compare(Sqlist *); //比较两个顺序表的大小 short Exchange(Sqlist *); //前N个元素和后M个元素互换 short Location(Sqlist *, ElemType); //求元素位置 void Disp(Sqlist *); //显示顺序表信息 void Three(Sqlist *, unsigned, unsigned); //三次逆转法 short Realloc(Sqlist *); //增加空间 ====================================================

main.c =========================== #include<stdio.h> #include<stdlib.h> #include"definition.h"

int main() { Sqlist L[10]; //最多可以建立10个顺序表 unsigned int i; unsigned short choice; //记录用户选择的操作 short (*option[])(Sqlist *)={InitList, InputList, DelList, Union, Purge, Bubble, Compare, Exchange, Purge2}; //定义函数指针

listlen=0;//初始化顺序表数目

printf("请输入1创建一个顺序表。最多可以创建10个顺序表\n");

while( (choice=Menu())!='q'-49 ){//根据用户输入选择函数运行 i=0; if(choice==0) InitList(&L[listlen]); //插入数据 else if(choice==3) Union(L); //合并顺序表 else if(choice==6) Compare(L); //比较顺序表 else{ while(i>listlen || i<1){ //如果用户输入不合法，则循环请用户输入 printf("请问您要对哪个顺序表（1 — %d）进行操作：", listlen); scanf("%d", &i); } getchar();//用于接收多余的字符'\n' option[choice](&L[i-1]); }

//打印顺序表的内容 Disp(L); }

for(i=0; i<listlen; i++) free(L[i].elem); //释放内存 return 0; //退出程序 } ===================================================

functions.c ========================= #include<stdio.h> #include<stdlib.h> #include<string.h> #include<ctype.h> #include"definition.h"

short Menu() //打印菜单，并且接受用户输入的操作 { char ch='0';

do{ if( strchr("23456789", ch) ) printf("您还没有建立顺序表呢，请输入1建立一个顺序表。\n");

printf("\n"); printf("********************************\n"); printf("*** 请选择您要进行的操作 ***\n"); printf("********************************\n"); printf("* 1. 创建顺序表 *\n"); printf("* 2. 插入数据 *\n"); printf("* 3. 删除数据 *\n"); printf("* 4. 求顺序表并集 *\n"); printf("* 5. 删除重复元素 *\n"); printf("* 6. 冒泡排序 *\n"); printf("* 7. 比较顺序表大小 *\n"); printf("* 8. 前N个元素和后M个元素互换 *\n"); printf("* 9. 删除重复元素(2) *\n"); printf("* q. 退出 *\n"); printf("********************************\n"); printf("\n");

ch=getch();//getch()并不在屏幕上输出 }while( !strchr("123456789q", ch) || (listlen==0 && strchr("23456789", ch)) );//如果在ch不存在于""之间，则循环请用户输入操作号

return ch-49;//返回操作号 }

short InitList(Sqlist *L)//创建顺序表 { if(listlen==10){ //当前已经有了10个顺序表 printf("最多只能创建10个顺序表。\n"); return 0; }

L->elem=(ElemType *)malloc(INITSIZE*sizeof(ElemType));//分配空间 if(!L->elem){ printf("Not Enough Memory!\n"); return 1;//创建失败返回1 }

//创建成功，初始化顺序表长度和字符串长度 L->length=0; L->listsize=INITSIZE; L->e=0; //初始化元素编号 listlen++; //更新顺序表数目

printf("顺序表创建成功！您可以开始对顺序表进行操作了。\n"); return 0;//创建成功返回0 }

short InputList(Sqlist *L)//接受用户输入的字符串 { unsigned int i; ElemType temp; //用于暂时存储用户输入的字符 if(L->length){ //如果顺序表中存在数据 L->e=L->length+1; while(L->e > L->length || L->e < 0){//如果用户输入不合法，则循环请用户输入 printf("请输入插入位置（0 — %d），0代表插入到最后：", L->length); scanf("%d", &L->e); } getchar();//用于接收多余的字符'\n' } printf("请输入字符串："); if(!L->e){//如果顺序表中不存在数据，或者用户前面输入为0 L->e=L->length;//从第length个位置开始插入字符。如果顺序表中不存在数据，此时length等于0 for(; ( L->elem[L->e]=getchar() )!='\n'; L->e++){//循环插入数据 L->length++; if(L->length==L->listsize){//如果顺序表已满 if( Realloc(L) ) //增加空间 return 1;//增加空间失败，退出 } } } else{//如果顺序表不空，而且用户前面输入不是0 L->e--; for(; (temp=getchar())!='\n'; L->e++, L->length++){//从第e个位置开始，循环插入数据 if(L->length==L->listsize){//如果顺序表已满 if( Realloc(L) ) //增加空间 return 1;//增加空间失败，退出 }

i=L->length; for(; i > L->e; i--){ L->elem[i]=L->elem[i-1];//将第e个位置开始的元素都向后移动一个位置 } L->elem[L->e]=temp;//将用户输入的字符插入第e个位置 } }

return 0;//返回 }

short DelList(Sqlist *L) { unsigned int i, j;

if(!L->length){ //如果顺序表中没有数据，退出 printf("\n该顺序表里没有数据。\n"); return 1; } //如果顺序表中存在数据 L->e=L->length+1; while(L->e > L->length || L->e < 1){//如果用户输入不合法，则循环请用户输入 printf("请输入删除位置（1 — %d）：", L->length); scanf("%d", &L->e); } i=L->length+1; j=L->length - L->e + 1; while( i<1 || i>j ){//如果用户输入不合法，则循环请用户输入 printf("请输入删除数目（1 — %d）：", j ); scanf("%d", &i); } getchar();//用于接收多余的字符'\n' //开始删除数据 if(i==j) ; else for( j=i+(--L->e); j<L->length; L->e++, j++ ){ L->elem[L->e]=L->elem[j]; } L->length-=i;//更新字符串长度

return 0;//返回 }

short Union(Sqlist *L){ //求顺序表并集 unsigned short i=0, j=0; unsigned k;

if(listlen<2){//如果少于两个顺序表，则返回1 printf("至少要有两个顺序表才能进行并集操作，请再建立一个顺序表。\n"); return 1; }

while( i<1||j<1||i>listlen||j>listlen||i==j){//如果用户输入不合法，则循环请用户输入 printf("\n请输入您想要进行并集操作的两个顺序表，两个数字之间用空格隔开（1 — %d）：", listlen); scanf("%d %d", &i, &j); }

//开始进行并集操作 for(i--, j--, k=0; k<L[j].length; k++){ if( !Location(&L[i], L[j].elem[k]) ){//在顺序表i中找不到顺序表j中的第k+1个元素，将第k+1个元素插入顺序表i if(L[i].length==L[i].listsize){ //如果顺序表已满 if( Realloc(&L[i]) ){ //增加空间 printf("\n没有足够的内存用于完成并集操作。\n"); return 1;//增加空间失败，退出 } } L[i].elem[L[i].length]=L[j].elem[k];//插入到表i L[i].length++;//表i长度增加 } } printf("\n并集操作完成。操作结果保存于顺序表 %d 。\n", ++i);

return 0;//无误返回 }

short Purge(Sqlist *L) //删除表中重复元素 { unsigned i, j, k;

for(i=0; i<L->length; i++){ for(j=i+1; j<L->length;){ if(L->elem[i]==L->elem[j]){//若找到重复元素 for(k=j; k<L->length; k++)//删除重复元素 L->elem[k]=L->elem[k+1]; L->length--;//顺序表长度减1 } else j++; } }

printf("\n重复数据已经删除完毕。\n"); return 0; }

short Purge2(Sqlist *L) //删除表中重复元素 { Sqlist T=*L; unsigned i;

T.length=1; for(i=1; i<L->length; i++){ if( !Location(&T, L->elem[i]) ){//若找不到重复元素 T.elem[T.length]=L->elem[i];//插入 T.length++;//更新长度 } } L->length=T.length;//更新长度

printf("\n重复数据已经删除完毕。"); return 0; }

short Bubble(Sqlist *L) { char ch='2'; ElemType temp; unsigned i, j, k=L->length-1; unsigned short l;

while( !strchr("01", ch) ){//如果用户输入不合法，则循环请用户输入 printf("\n请问您要进行降序排序还是升序排序？0代表降序，1代表升序。\n"); ch=getch(); }

if(ch=='0'){ for(l=1; l; k--){ l=0; for(i=0, j=1; i<k; i++, j++){//降序排列 if(L->elem[i] < L->elem[j]){ temp=L->elem[i]; L->elem[i]=L->elem[j]; L->elem[j]=temp; l=1; } } } } else{ for(l=1; l; k--){ l=0; for(i=0, j=1; i<k; i++, j++){//升序排列 if(L->elem[i] > L->elem[j]){ temp=L->elem[i]; L->elem[i]=L->elem[j]; L->elem[j]=temp; l=1; } } } } printf("\n排序完成。\n"); return 0; }

short Compare(Sqlist *L)//比较两个顺序表 { unsigned short i=0, j=0; unsigned k;

if(listlen<2){//如果少于两个顺序表，则返回1 printf("至少要有两个顺序表才能进行比较，请再建立一个顺序表。\n"); return 1; }

while( i<1||j<1||i>listlen||j>listlen||i==j){//如果用户输入不合法，则循环请用户输入 printf("\n请输入您想要比较的两个顺序表，两个数字之间用空格隔开（1 — %d）：", listlen); scanf("%d %d", &i, &j); }

//开始进行比较 for(i--, j--, k=0; k<L[i].length && k<L[j].length; k++){ if(L[i].elem[k] > L[j].elem[k]){ printf("\n顺序表 %d 比顺序表 %d 大。\n", ++i, ++j); return 1; } if(L[i].elem[k] < L[j].elem[k]){ printf("\n顺序表 %d 比顺序表 %d 大。\n", ++j, ++i); return 2; } }

if(L[i].length > L[j].length){ printf("\n顺序表 %d 比顺序表 %d 大。\n", ++i, ++j); return 1; } if(L[i].length < L[j].length){ printf("\n顺序表 %d 比顺序表 %d 大。\n", ++j, ++i); return 2; }

printf("\n两表相等。\n"); return 0;//相等返回0 }

short Exchange(Sqlist *L) //前N个元素和后M个元素互换 { unsigned i=0;

while(i<1 || i>=L->length){//如果用户输入不合法，则循环请用户输入 printf("\n请输如互换点（1 — %d）：", L->length-1); scanf("%d", &i); }

//三次逆转 Three(L, 0, i-1); Three(L, i, L->length-1); Three(L, 0, L->length-1);

printf("\n互换完成。\n"); return 0; }

void Three(Sqlist *L, unsigned i, unsigned j)//三次逆转法 { ElemType temp;

for(; i<j; i++, j--){ temp=L->elem[i]; L->elem[i]=L->elem[j]; L->elem[j]=temp; } }

short Location(Sqlist *L, ElemType elem)//求元素位置 { unsigned l;

for(l=0; l < L->length && L->elem[l]!=elem; l++) ; if(l==L->length)//在顺序表中找不到elem return 0; //返回0

return ++l;//找到则返回元素位置 }

short Realloc(Sqlist *L)//增加空间 { ElemType *newbase;

newbase=(ElemType *)realloc(L->elem, (L->listsize+INCREMENT)*sizeof(ElemType) );//增加空间 if(!newbase){//如果分配失败 printf("Not Enough Memory!\n"); return 1;//返回1 } //如果分配成功 L->elem=newbase;//将指针指向新分配好的空间 L->listsize+=INCREMENT;//增大listsize的值

return 0;//返回 }

void Disp(Sqlist *L) //显示顺序表信息 { unsigned short i; unsigned j;

printf("\n当前一共有 %d 个顺序表。每个表的数据如下：\n", listlen); for(i=0; i<listlen; i++){ printf("\n顺序表 %d ：", i+1); for(j=0; j<L[i].length; j++) printf("%c", L[i].elem[j]); printf("\n字符串长度：%d 顺序表长度：%d", L[i].length, L[i].listsize); printf("\n"); } }

[此贴子已经被作者于2005-4-17 9:17:06编辑过]

90 回复
#2
Antigloss2004-12-31 22:43
2. 静态链表的建立和操作 definition.h =========================================== #define MAXSIZE 1000

typedef char ElemType;

typedef struct{//定义静态链表结构 ElemType data; unsigned short cur; }component, SLinkList[MAXSIZE];

void Init(component *); //初始化静态链表 component* Insert(component *); //插入数据到链表 short Malloc(component *); //分配空间 void Free(component *, short); //回收空间 void Disp(component *, component *); //显示静态链表数据 void Purge(component *, component *); //删除重复数据 void Union(component *, component *, component *); //(A-B)交(B-A) ======================================================

functions.c ====================================== #include<stdio.h> #include"definition.h"

void Init(component *L)//初始化静态链表 { unsigned short i;

for(i=0; i<MAXSIZE-1; i++) L[i].cur=i+1; L[MAXSIZE-1].cur=0; }

component* Insert(component *L)//插入数据到链表 { component *T, *temp1, *temp2; unsigned short i; ElemType ch;

if( i=Malloc(L) ){ T=temp1=&L[i]; T->cur=0; } else return 0; while( (ch=getchar()) != '\n' ){ if( i=Malloc(L) ){ temp2=&L[i]; temp2->data=ch; temp2->cur=0; temp1->cur=i; temp1=temp2; } else return 0; }

return T; }

short Malloc(component *L)//分配空间 { unsigned short i;

i=L[0].cur; if(L[0].cur){ L[0].cur=L[i].cur; return i;//成功返回空间位置 }

return 0;//失败返回0 }

void Free(component *L, short i) //回收空间 { L[i].cur=L[0].cur; L[0].cur=i; }

void Disp(component *T, component *L)//显示静态链表数据 { while(T->cur){ T=&L[T->cur]; printf("%c", T->data); } printf("\n"); }

void Purge(component *T, component *L) //删除重复数据 { component *tmp, *temp;

for(T=&L[T->cur]; T->data; T=&L[T->cur]){//若T->data中没数据，则退出循环 for(temp=T, tmp=&L[T->cur]; tmp->data;){//若tmp->data中没数据，则退出循环 if(T->data==tmp->data){ temp->cur=tmp->cur; Free(L, (short)(tmp-L));//回收空间 tmp=&L[temp->cur]; } else{ tmp=&L[tmp->cur]; temp=&L[temp->cur]; } } } }

void Union(component *A, component *B, component *L)//(A-B)交(B-A) { component *T, *ta, *tb=B; short flag;//用于判断是否进行了删除操作

B=&L[B->cur]; while(B->data){//循环判断，直到B表中所有数据都和A表比较过后才结束 ta=T=A; flag=1;//1代表没有进行删除 while(T->cur){//循环判断，直到A表中所有数据都和B->data比较过后才结束 T=&L[T->cur]; if(T->data==B->data){//如果相等，则删除 ta->cur=T->cur; Free(L, (short)(T-L)); T=&L[ta->cur]; tb->cur=B->cur; Free(L, (short)(B-L)); B=&L[tb->cur]; flag=0;//1代表进行了删除 break; } else//不相等则把指针移动到一个数据 ta=&L[ta->cur]; } if(flag){//如果没有进行删除操作，则连接两个结点 T->cur=tb->cur; tb->cur=B->cur; B->cur=0; B=&L[tb->cur]; } } } ======================================================

main.c ============================= #include<stdio.h> #include"definition.h"

int main() { SLinkList L; component *A, *B;

L[0].data=0; Init(L);//初始化静态链表 printf("请为静态链表A输入数据："); A=Insert(L);//插入数据到链表A printf("请为静态链表B输入数据："); B=Insert(L);//插入数据到链表B

printf("静态链表A的数据为："); Disp(A, L); printf("静态链表A的数据为："); Disp(B, L);

Purge(A, L);//删除A中重复元素 printf("删除A中重复元素后得："); Disp(A, L); Purge(B, L);//删除B中重复元素 printf("删除B中重复元素后得："); Disp(B, L);

Union(A, B, L);//(A-B)交(B-A) printf("(A-B)交(B-A)得："); Disp(A, L);

return 0; }

[此贴子已经被作者于2005-1-4 17:31:51编辑过]
#3
agnes_2003032005-01-04 10:02
为什么点击后提示错误,系统找不到该文件?
#4
Antigloss2005-01-04 14:17
三、单链表的建立与操作

definition.h =========================== typedef char ElemType;

typedef struct{//定义单链表 ElemType data; struct Node* next; }Node, *LinkList;

LinkList FormList();//正向形成链表 LinkList FormList2();//逆向形成链表 void Insert(LinkList, unsigned);//插入数据 void Delete(LinkList, unsigned, unsigned);//删除数据 void Disp(LinkList);//显示数据 void Destroy(LinkList);//释放内存 void Bubble(LinkList);//冒泡排序 unsigned CountLen(LinkList);//计算链表长度 void Merge(LinkList, LinkList);//合并有序链表 void Exchange(LinkList, unsigned);//前 m 个结点和后 n 个结点的互换 void Purge(LinkList);//删除单链表中重复的数据元素 ======================================================

functions.c ======================== #include<malloc.h> #include<stdio.h> #include"definition.h"

LinkList FormList()//正向形成链表 { ElemType temp; LinkList h, head, end;

if( !( h=head=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return 0; } head->next=0; while( (temp=getchar())!='\n' ){ if( !( end=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return 0; } head->next=end; head=end; head->data=temp; head->next=0; }

return h; }

LinkList FormList2()//逆向形成链表 { LinkList head, end; ElemType temp;

if( !( head=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return 0; } head->next=0; while( (temp=getchar())!='\n' ){ if( !( end=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return 0; } end->data=temp; end->next=head->next; head->next=end; }

return head; } void Insert(LinkList L, unsigned i)//插入数据 {//若单链表没有头结点，需对在第一个结点之前进行插入的情况单独进行处理。很麻烦 unsigned j; LinkList T; ElemType temp; getchar(); for(j=1; L&&j<i; L=L->next, j++) ; if(!L||j>i){ printf("Error!\n"); return; } printf("请输入您要插入的数据："); while( (temp=getchar())!='\n' ){ if( !( T=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return; } T->data=temp; T->next=L->next; L->next=T; L=T; } }

void Delete(LinkList L, unsigned i, unsigned j)//删除数据 { LinkList T;

getchar(); for(i--; i&&L; L=L->next, i--) ; if(!L){ printf("Error!\n"); return; } for(T=L->next; j&&T; j--){ L->next=T->next; free(T); T=L->next; } }

void Disp(LinkList L)//显示数据 { for(L=L->next; L; L=L->next) printf("%c", L->data); printf("\n"); }

void Destroy(LinkList L)//释放内存 { LinkList T=L;

for(L=L->next; L; T=L, L=L->next) free(T); free(T); }

void Bubble(LinkList L)//冒泡排序 { ElemType temp; LinkList T, H; unsigned i, j, flag=1;

i=CountLen(L);//计算链表长度 H=L->next; while(flag){ L=H; T=H->next; flag=0; j=1; while(j<i){ if(L->data > T->data){ temp=T->data; T->data=L->data; L->data=temp; flag=1; } L=L->next; T=T->next; j++; } i--; } }

void Merge(LinkList A, LinkList B)//合并有序链表 { LinkList C=A, D=B;

A=A->next; B=B->next; while(A&&B){ if(A->data<=B->data){ C->next=A; C=A; A=A->next; } else{ C->next=B; C=B; B=B->next; } } C->next=A?A:B;

free(D); }

unsigned CountLen(LinkList L)//计算链表长度 { unsigned i=0;

for(L=L->next; L; L=L->next, i++) ; return i; }

void Exchange(LinkList L, unsigned i)//前 m 个结点和后 n 个结点的互换 { LinkList A, B;

A=B=L->next; for(i--; i&&A; A=A->next, i--) ; if(!A){ printf("Error!\n"); return; } L->next=A->next; A->next=0; A=L->next; while(A->next) A=A->next; A->next=B; }

void Purge(LinkList L)//删除单链表中重复的数据元素 { LinkList A, B, C, D;

B=C=L->next; L->next=0; while(B){ A=L->next; D=L; while(A){ if(A->data==B->data){ B=B->next; free(C); C=B; break; } else{ A=A->next; D=D->next; } } if(!A){ D->next=B; B=B->next; C->next=0; C=B; } } } ======================================================

main.c =================== #include<malloc.h> #include<stdio.h> #include"definition.h"

int main() { LinkList A, B; unsigned i, j;

//形成链表 printf("请为表A输入数据："); A=FormList(); printf("请为表B输入数据："); B=FormList2();

//显示数据 printf("表A："); Disp(A); printf("表B："); Disp(B);

//插入数据 printf("请问您要在表A的哪个位置插入数据："); scanf("%d", &i); Insert(A, i); printf("请问您要在表B的哪个位置插入数据："); scanf("%d", &i); Insert(B, i);

printf("表A："); Disp(A); printf("表B："); Disp(B);

//冒泡排序 Bubble(A); Bubble(B);

printf("表A排序后："); Disp(A); printf("表B排序后："); Disp(B);

//删除数据 printf("请问您要从表A的哪个位置开始删除数据："); scanf("%d", &i); printf("请问您要删除几个元素："); scanf("%d", &j); Delete(A, i, j); printf("请问您要从表B的哪个位置开始删除数据："); scanf("%d", &i); printf("请问您要删除几个元素："); scanf("%d", &j); Delete(B, i, j);

printf("表A："); Disp(A); printf("表B："); Disp(B);

Merge(A, B);//合并有序链表 printf("合并链表后："); Disp(A);

//前m个结点和后n个结点的互换 printf("前m个结点和后n个结点的互换。请输入一个整数："); scanf("%d", &i); Exchange(A, i); printf("前m个结点和后n个结点的互换后："); Disp(A);

//删除单链表中重复的数据元素 Purge(A); printf("删除重复元素后："); Disp(A);

//释放内存 Destroy(A); }

[此贴子已经被作者于2005-1-4 21:25:25编辑过]
#5
aniude2005-01-04 16:05
你直接贴上来吧，大家也好看//
#6
Antigloss2005-01-04 22:10

4. 双向链表的创建和操作 definition.h =============================== typedef char ElemType;

typedef struct{//定义单链表 ElemType data; struct Node* next; struct Node* prior; }Node, *LinkList;

LinkList FormList();//正向形成链表除数据 void Disp(LinkList);//显示数据 void Delete(LinkList, unsigned, unsigned);//删除数据 void Insert(LinkList, unsigned);//插入数据 ==================================================================== functions.c ====================== #include<malloc.h> #include<stdio.h> #include"definition.h"

LinkList FormList()//正向形成链表 { LinkList h, head, end; ElemType temp;

if( !( h=head=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return 0; } h->next=h->prior=h; while( (temp=getchar())!='\n' ){ if( !( end=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return 0; } end->data=temp; end->next=h; end->prior=head; head->next=end; head=end; h->prior=end; } return h; }

void Insert(LinkList L, unsigned i)//插入数据 {//若单链表没有头结点，需对在第一个结点之前进行插入的情况单独进行处理。很麻烦 LinkList T, A=L; ElemType temp; getchar(); while(--i){ L=L->next; if( !(L-A) ) break; } if(i&&!(L-A)){ printf("Error!\n"); return; } printf("请输入您要插入的数据："); while( (temp=getchar())!='\n' ){ if( !( T=(LinkList)malloc(sizeof(Node)) ) ){ printf("Not Enough Memory!\n"); return; } T->data=temp; T->next=L->next; A=L->next; A->prior=T; T->prior=L; L->next=T; L=T; } }

void Delete(LinkList L, unsigned i, unsigned j)//删除数据 { LinkList T, A, B=L;

getchar(); while(--i){ L=L->next; if( !(L-B) ) break; } if(i&&!(L-B)){ printf("Error!\n"); return; } for(T=L->next; j&&(T-B); j--){ L->next=T->next; A=T->next; A->prior=L; free(T); T=L->next; } }

void Disp(LinkList L)//显示数据 { LinkList T=L;

for(L=L->next; L-T; L=L->next) printf("%c", L->data); printf("\n"); } ============================================================= main.c ==================== #include<malloc.h> #include<stdio.h> #include"definition.h"

int main() { unsigned i, j; LinkList A;

printf("请输入数据："); A=FormList(); printf("表A中的数据为："); Disp(A);

//插入数据 printf("请问您要在表A的哪个位置插入数据："); scanf("%d", &i); Insert(A, i); printf("表A中的数据为："); Disp(A);

//删除数据 printf("请问您要从表A的哪个位置开始删除数据："); scanf("%d", &i); printf("请问您要删除几个元素："); scanf("%d", &j); Delete(A, i, j); printf("表A中的数据为："); Disp(A);

return 0; }
#7
Antigloss2005-02-01 14:28

5、堆栈的基本操作

definition.h ================================================= #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef char ElemType;

typedef struct{ ElemType *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

int InitStack(SqStack *);//创建一个空栈 int GetTop(SqStack *); //返回栈顶元素 int Push(SqStack *); //插入栈顶 int Pop(SqStack *); //删除栈顶元素 =============================================================

function.c ==================================================================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int InitStack(SqStack *S) //创建一个空栈 { S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int GetTop(SqStack *S) //返回栈顶元素 { if(S->base==S->top)//栈空，返回0 return 0; return *(S->top - 1);//栈不空，返回栈顶元素 }

int Push(SqStack *S) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof(ElemType) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 }

printf("请输入一个字符："); scanf( "%c", S->top++ );//接收输入后，S->top指向栈顶元素的下一个位置

return 0; }

int Pop(SqStack *S) //删除栈顶元素 { if(S->base == S->top)//空栈，返回0 return 0; return *( --(S->top) );//不空，栈顶指针下移（即删除栈顶元素），并且返回栈顶元素 } ===========================================================================================

main.c ============================================================ #include<stdio.h> #include"definition.h"

int main() { SqStack S; ElemType e;

if( InitStack(&S) ){ printf("创建堆栈失败。\n"); return 1; } printf("创建堆栈成功。\n");

if( Push(&S) ) printf("插入失败。\n"); else printf("插入成功。\n");

if( e=GetTop(&S) ) printf("栈顶元素为：%c\n", e); else printf("空栈。\n");

if( e=Pop(&S) ) printf("成功删除了栈顶元素 %c\n", e); else printf("空栈。\n");

return 0; }
#8
Antigloss2005-02-01 17:14

数制转换

十进制转换成其它进制。注意：转换为十进制以上的进制会出错。

definition.h ================================================ #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef char ElemType;

typedef struct{ ElemType *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

int InitStack(SqStack *); //创建一个空栈 int Push(SqStack *, char); //插入栈顶 ===============================================================================

function.c ============================================================= #include<stdio.h> #include<malloc.h> #include"definition.h"

int InitStack(SqStack *S) //创建一个空栈 { S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int Push(SqStack *S, char e) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof

(ElemType) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 }

*S->top++ = e;//入栈后，S->top指向栈顶元素的下一个位置

return 0; } ===================================================================================

main.c ============================================================= #include<stdio.h> #include<malloc.h> #include"definition.h"

int main() { SqStack S; unsigned short i, flag=0; long a;

printf("请输入一个不大于2147483647，不小于-2147483648的十进制整数：\n"); scanf("%d", &a); if(a<0){ a = -a; flag = 1; }

printf("您想转换为哪种进制的整数呢？"); scanf("%d", &i);

if( InitStack(&S) ){ printf("创建堆栈失败。\n"); return 1; } do{//数制转换 Push( &S, (char)(a % i) );//插入栈顶 }while(a /= i);

printf("转换结果为：");//显示结果 if(flag) printf("-"); while( S.top != S.base ) printf("%d", *(--S.top) ); printf("\n");

free(S.base);//释放内存

return 0; }
#9
Antigloss2005-02-01 19:02

括号匹配

definition =========================== #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef char ElemType;

typedef struct{ ElemType *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

int InitStack(SqStack *);//创建一个空栈 int Push(SqStack *, char); //插入栈顶 int Pop(SqStack *); //删除栈顶元素 =========================================================================

function.c ================================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int InitStack(SqStack *S) //创建一个空栈 { S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int Push(SqStack *S, char e) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof

(ElemType) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 }

*S->top++ = e; //接收输入后，S->top指向栈顶元素的下一个位置

return 0; }

int Pop(SqStack *S) //删除栈顶元素 { if(S->base == S->top)//空栈，返回0 return 0; return *( --(S->top) );//不空，栈顶指针下移（即删除栈顶元素），并且返回栈顶元素 } ============================================================================

main.c ================================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int main() { SqStack S; ElemType e;

if( InitStack(&S) ){ printf("创建堆栈失败。\n"); return 1; }

do{ printf("请输入“(、)、[ 或者 ]”中的任意一个："); e=getchar(); getchar(); if( e=='(' || e=='[' ) //左括号压栈 Push(&S, e); else if( e==')' || e==']' ){//右括号判断 if( (*(S.top-1)=='(' && e==')') || (*(S.top-1)=='[' && e==']') ) Pop(&S);//匹配则出栈 else{//不匹配则退出 printf("匹配失败。\n"); return 1; } } else{//输入不合法字符，退出 printf("输入不合法。\n"); return 1; } }while(S.top != S.base);//S.top==S.base则说明匹配完成

printf("匹配成功。\n"); free(S.base); return 0; }
#10
Antigloss2005-02-02 14:00

迷宫求解

definition.h ======================================================== #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef struct{ unsigned ord, x, y; //通道块在路径上的“序号”，通道快在迷宫中的“坐标位置” short di; //从此通道块走向下一通道块的“方向” }ElemType;

typedef struct{ ElemType *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

int InitStack(SqStack *);//创建一个空栈 int Push(SqStack *, ElemType);//插入栈顶 ElemType Pop(SqStack *); //删除栈顶元素 void NextPos(unsigned *, unsigned *, short);//定位下一个位置 ====================================================================

function.c =============================================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int InitStack(SqStack *S) //创建一个空栈 { S->base=(ElemType *)malloc( INIT_SIZE * sizeof(ElemType) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int Push(SqStack *S, ElemType e) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(ElemType *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof

(ElemType) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 }

*S->top++ = e;//接收输入后，S->top指向栈顶元素的下一个位置

return 0; }

ElemType Pop(SqStack *S) //删除栈顶元素 { if(S->base == S->top){//空栈，返回0 S->base->di=0; return *S->base; } return *( --(S->top) );//不空，栈顶指针下移（即删除栈顶元素），并且返回栈顶元素 }

void NextPos(unsigned *x, unsigned *y, short di)//定位下一个位置 { switch(di){ case 1: ++(*x); break; case 2: ++(*y); break; case 3: --(*x); break; case 4: --(*y); break; default: break; } } ==============================================================================

main.c =============================================== #include<stdio.h> #include<malloc.h> #include"definition.h"

int main() { SqStack S; unsigned x, y, curstep;//迷宫坐标，探索步数 ElemType e; char maze[10][10]={ {'#',' ','#','#','#','#','#','#','#','#'}, {'#',' ',' ','#',' ',' ',' ','#',' ','#'}, {'#',' ',' ','#',' ',' ',' ','#',' ','#'}, {'#',' ',' ',' ',' ','#','#',' ',' ','#'}, {'#',' ','#','#','#',' ',' ',' ',' ','#'}, {'#',' ',' ',' ','#',' ',' ',' ',' ','#'}, {'#',' ','#',' ',' ',' ','#',' ',' ','#'}, {'#',' ','#','#','#',' ','#','#',' ','#'}, {'#','#',' ',' ',' ',' ',' ',' ',' ','#'}, {'#','#','#','#','#','#','#','#',' ','#'}, };

printf("迷宫：\n"); for(x=0; x<10; x++){ for(y=0; y<10; y++) printf("%c", maze[x][y]); printf("\n"); }

if( InitStack(&S) ){ printf("创建堆栈失败。\n"); return 1; }

//入口坐标 x=1; y=0; curstep=1;//探索第一步 //进入迷宫 do{ if(maze[y][x]==' '){//如果当前位置可以通过 maze[y][x]='1';//留下足迹 e.x=x; e.y=y; e.di=1; e.ord=curstep; Push(&S, e);//加入路径，即压栈 if(x==8 && y==9)//到达终点 break; NextPos(&x, &y, 1);//下一位置是当前位置的东邻 curstep++; } else{//如果当前位置不能通过 if(S.top != S.base){ e=Pop(&S); while(e.di==4 && S.top!=S.base){ maze[e.y][e.x]='0';//留下不能通过足迹 e=Pop(&S);//退回一步，即出栈 } if(e.di<4){ e.di++; Push(&S, e); //重置坐标 x=e.x; y=e.y; NextPos(&x, &y, e.di);//寻找下一位置 } } } }while(S.top != S.base);

printf("\n路线：\n"); for(x=0; x<10; x++){ for(y=0; y<10; y++) printf("%c", maze[x][y]); printf("\n"); }

free(S.base);

return 0; }
#11
Antigloss2005-02-03 12:05

链队列的基本操作

definition.h =================================== typedef char ElemType;

typedef struct{ ElemType data; struct Qnode *next; }Qnode, *Qptr;//队列结点

typedef struct{ Qptr front, rear;//队头指针，队尾指针 }LinkQueue;

int InitQueue(LinkQueue *);//建立空队列 void Destroy(LinkQueue *);//销毁队列 int EnQueue(LinkQueue *, ElemType);//进入队列 int DeQueue(LinkQueue *);//出队 =====================================================================

main.c ==================================== #include<stdio.h> #include"definition.h"

int main() { return 0; } ================================================

function.c ================================================= #include <stdio.h> #include <malloc.h> #include "definition.h"

int InitQueue(LinkQueue *Q)//建立空队列 { Q->rear=Q->front=(Qptr)malloc(sizeof(Qnode)); if(!Q->front) return 1; Q->front->next=NULL; return 0; }

void Destroy(LinkQueue *Q)//销毁队列 { while(Q->front){ Q->rear=Q->front->next; free(Q->front); Q->front=Q->rear; } }

int EnQueue(LinkQueue *Q, ElemType e)//进入队列 { Qptr tmp;

tmp=(Qptr)malloc(sizeof(Qnode)); if(!tmp) return 1; tmp->data=e; tmp->next=NULL; Q->rear->next=tmp; Q->rear=tmp;

return 0; }

int DeQueue(LinkQueue *Q)//出队 { Qptr tmp;

if(Q->front==Q->rear) return 1;//如果队列已空，返回1

tmp=Q->front->next; Q->front->next=tmp->next; if(Q->rear==tmp)//如果队尾元素被删除，则队尾指针要指向头结点 Q->rear=Q->front;

free(tmp); return 0; } ============================================================================
#12
Antigloss2005-02-03 12:05

循环队列的基本操作

definition.h ====================================== #define MAXSIZE 100 //最大队列长度

typedef char ElemType;

typedef struct{ ElemType *base; unsigned front, rear;//队头指针，队尾指针 }SqQueue;

int InitQueue(SqQueue *);//建立空队列 int EnQueue(SqQueue *, ElemType);//进入队列 int DeQueue(SqQueue *);//出队 int Length(SqQueue *);//队列长度 =========================================================

main.c ============================================ #include<stdio.h> #include"definition.h"

int main() { return 0; } =============================================

function.c ==================================== #include <stdio.h> #include <malloc.h> #include "definition.h"

int InitQueue(SqQueue *Q)//建立空队列 { Q->base=(ElemType *)malloc( MAXSIZE*sizeof(ElemType) ); if(!Q->base) return 1; Q->front=Q->rear=0; return 0; }

int EnQueue(SqQueue *Q, ElemType e)//进入队列 { if( (Q->rear+1)%MAXSIZE==Q->front ) return 1;//队满(此判断队满法的代价是，少利用一个空间) Q->base[Q->rear]=e; Q->rear=++Q->rear % MAXSIZE; return 0; }

int DeQueue(SqQueue *Q)//出队 { if(Q->front==Q->rear) return 1;//队空 Q->front= ++Q->front % MAXSIZE; return 0; }

int Length(SqQueue *Q)//队列长度 { return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; }
#13
Antigloss2005-02-04 16:40

银行业务模拟（计算客户平均等待时间）

definition.h ============================================== #define CLOSETIME 1440

typedef struct{ unsigned OccurTime, NType;//事件发生时刻；事件类型，6代表到达事件，0-5代表6个窗口的

离开事件 }Event;//链表数据元素类型

typedef struct{ Event event; struct Enode *next; }Enode, *EventList;

typedef struct{ unsigned ArrTime, Duration;//到达时刻；办理时间 }QElem;//队列数据元素类型

typedef struct{ QElem Cust;//客户记录 struct Qnode *next; }Qnode, *Qptr;

typedef struct{ Qptr front, rear;//队头指针，队尾指针 }LinkQueue;

EventList ev;//事件表 Event en;//事件 LinkQueue q[6];//6个客户队列 QElem customer;//客户记录 unsigned TotalTime, CustNum;//累计客户逗留时间，客户数

int Open();//初始化操作 int CustArr();//处理客户到达事件 EventList InitList();//创建链表 int OrderInsert(EventList, Event);//插入事件表 int InitQueue(LinkQueue *);//建立空队列 short Minimun();//求长度最短队列 unsigned QueueLength(LinkQueue);//计算队列长度 int EnQueue(LinkQueue *, QElem);//进入队列 int CustDepart();//处理客户离开事件 int DeQueue(LinkQueue *);//出队 void DelFirst();//删除事件表第一个节点，并把值赋给en ==========================================================================

main.c ============================================================ #include <stdio.h> #include "definition.h"

int main() { if( !Open() ) return 1;//初始化失败，退出 while(ev->next){ DelFirst();//删除事件表第一个节点，并把值赋给en if( en.NType == 6 ){ if( !CustArr() ) return 1; } else{ if( !CustDepart() ) return 1; } }

printf( "平均逗留时间为：%g\n", (float)TotalTime / CustNum ); return 0; }

//还没回收动态分配了的空间，懒得写了 =====================================================================

function.c ===================================================== #include <stdio.h> #include <malloc.h> #include <stdlib.h> #include <time.h> #include "definition.h"

int Open()//初始化操作 { short i;

srand(time (NULL));//生成随机数种子 CustNum=TotalTime=0;//初始化累计时间和客户数 if( !(ev=InitList()) )//初始化事件链表 return 0;//创建失败，返回0 en.OccurTime=0; en.NType=6;//设定第一个客户到达事件 if( !OrderInsert(ev, en) )//插入事件表 return 0;//插入失败，返回0 for(i=0; i<6; i++){//置空队列 if( !InitQueue(&q[i]) ) return 0;//创建队列失败，返回0 } return 1; }

int CustArr()//处理客户到达事件，en.NType==6 { unsigned durtime, intertime; QElem e; short i;

CustNum++; //生成随机数 durtime = rand() % 30 + 1;//事务处理时间不超过30分钟 intertime = rand() % 5 + 1;//5分钟内有一位客人到达银行 e.ArrTime=en.OccurTime; e.Duration=durtime; en.OccurTime += intertime;//下一客户到达时间 if(en.OccurTime < CLOSETIME){//银行尚未关门，插入事件表 if( !OrderInsert(ev, en) )//插入失败 return 0; }

i=Minimun();//求长度最短队列 if( !EnQueue(&q[i], e) ) return 0; if( QueueLength(q[i]) == 1 ){//设定第i队列的一个离开事件并插入事件表 en.NType=i; en.OccurTime=e.ArrTime+durtime; OrderInsert(ev, en); }

return 1; }

int CustDepart()//处理客户离开事件，en.NType==(0 — 5) { Qptr tmp; unsigned i = en.NType;

if( !DeQueue( &q[i] ) )//删除排头客户 return 0; TotalTime = TotalTime + en.OccurTime - customer.ArrTime;//累计逗留时间 if( q[i].front != q[i].rear ){ tmp = q[i].front->next; customer = tmp->Cust; en.OccurTime += customer.Duration; if( !OrderInsert(ev, en) ) return 0; }

return 1; }

int DeQueue(LinkQueue *Q)//出队 { Qptr tmp;

if(Q->front==Q->rear) return 0;//如果队列已空，返回0

tmp=Q->front->next; customer=tmp->Cust; Q->front->next=tmp->next; if(Q->rear==tmp)//如果队尾元素被删除，则队尾指针要指向头结点 Q->rear=Q->front;

free(tmp); return 1; }

int EnQueue(LinkQueue *Q, QElem e)//进入队列 { Qptr tmp;

tmp=(Qptr)malloc(sizeof(Qnode)); if(!tmp) return 0;//进栈失败，返回0 tmp->Cust=e; tmp->next=NULL; Q->rear->next=tmp; Q->rear=tmp;

return 1; }

short Minimun()//求长度最短队列 { unsigned h=0, i, j, k;

j=QueueLength(q[0]); for(i=1; i<6; i++){ k = QueueLength(q[i]); if( j > k ){ j = k; h = i; } } return h; }

unsigned QueueLength(LinkQueue Q)//计算队列长度 { unsigned i;

for(i=0; Q.front->next; i++) Q.front=Q.front->next;

return i; }

EventList InitList()//创建链表 { EventList h;

if( !( h=(EventList)malloc(sizeof(Enode)) ) )//创建失败，返回0 return 0;

h->next=NULL; return h; }

int OrderInsert(EventList ev, Event a)//插入事件表 { EventList tmp, h=ev, e=ev->next;

if( !(tmp=InitList()) )//分配空间失败，返回0 return 0; //插入 tmp->event=a; while( e && (a.OccurTime > e->event.OccurTime) ){ h=e; e=e->next; } h->next=tmp; tmp->next=e;

return 1; }

int InitQueue(LinkQueue *Q)//建立空队列 { Q->rear=Q->front=(Qptr)malloc(sizeof(Qnode)); if(!Q->front)//创建失败，返回0 return 0; Q->front->next=NULL; return 1; }

void DelFirst()//删除事件表第一个节点，并把值赋给en { EventList tmp = ev->next;

ev->next = tmp->next; en = tmp->event;

free(tmp); }
#14
Antigloss2005-02-08 12:03

二叉树

definition.h ========================================= #define INIT_SIZE 100 //存储空间初始分配量 #define INCREMENT 10 //存储空间分配增量

typedef char TElemType;

typedef struct{ TElemType data; struct BiTNode *lchild, *rchild;//左右孩子指针 }BiTNode, *BiTree;//二叉树的二叉链表存储表示

typedef struct{ BiTree *top, *base; //栈顶指针和栈底指针 unsigned stacksize; //当前已分配的存储空间，以元素为单位 }SqStack;

BiTree CreateBiTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树 void PreOrderTraverse(BiTree);//先序遍历二叉树 int InOrderTraverse(BiTree);//中序遍历二叉树，非递归 int InOrderTraverse2(BiTree); int InitStack(SqStack *);//创建一个空栈 int Push(SqStack *, BiTree); //插入栈顶 ===========================================================================

main.c ================================================ #include <stdio.h> #include "definition.h"

int main() { BiTree bt;

printf("请输入根结点："); bt = CreateBiTree();//按先序次序创建二叉树 PreOrderTraverse(bt); //先序遍历二叉树 printf("\n"); if( InOrderTraverse(bt) )//中序遍历二叉树，非递归 return 1;//遍历失败，返回 printf("\n"); if( InOrderTraverse2(bt) )//中序遍历二叉树，非递归 return 1;//遍历失败，返回 printf("\n");

return 0; } ===================================================================

function.c ====================================================== #include <stdio.h> #include <malloc.h> #include "definition.h"

BiTree CreateBiTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树 { TElemType e; BiTree tmp = NULL;

if( (e=getchar())!='#' ){ getchar();//接收回车符 tmp=(BiTree)malloc(sizeof(BiTNode)); if(!tmp) return NULL; tmp->data=e; printf("请输入左孩子："); tmp->lchild=CreateBiTree(); printf("请输入右孩子："); tmp->rchild=CreateBiTree(); } else getchar();//接收回车符

return tmp; }

void PreOrderTraverse(BiTree bt)//先序遍历二叉树 { if(bt){ printf("%c", bt->data); PreOrderTraverse(bt->lchild); //printf("%c", bt->data);不要上面的printf，而用这个printf，则为中序遍历 PreOrderTraverse(bt->rchild); //printf("%c", bt->data);不要上面的printf，而用这个printf，则为后序遍历 } }

int InOrderTraverse(BiTree bt)//中序遍历二叉树，非递归 { SqStack S; BiTree tmp;

if( InitStack(&S) ) return 1;//如果创建空栈失败，返回1 if( Push(&S, bt) )//根指针进栈 return 1;//如果压栈失败，返回1 while(S.base!=S.top){ while( tmp=*(S.top-1) ){ if( Push(&S, tmp->lchild) )//向左走到尽头 return 1; //printf("%c", tmp->data);//printf放于此处即为先序遍历 } --S.top;//空指针退栈 //访问结点，向右一步 if(S.base!=S.top){ tmp = *(--S.top); printf("%c", tmp->data); if( Push(&S, tmp->rchild) ) return 1; } }

free(S.base); return 0; }

int InOrderTraverse2(BiTree bt) { SqStack S; BiTree tmp = bt;

if( InitStack(&S) ) return 1;//如果创建空栈失败，返回1 while( tmp||(S.base!=S.top) ){ if(tmp){ if( Push(&S, tmp) )//根指针进栈，遍历左子树 return 1; //printf("%c", tmp->data);//printf放于此处即为先序遍历 tmp = tmp->lchild; } //根指针退栈，访问根结点，遍历右子树 else{ tmp = *(--S.top); printf("%c", tmp->data); tmp = tmp->rchild; } }

free(S.base); return 0; }

int InitStack(SqStack *S) //创建一个空栈 { S->base=(BiTree *)malloc( INIT_SIZE * sizeof(BiTree) ); if(!S->base) //空间分配失败 return 1; //空间分配成功 S->top=S->base;//置栈顶指针 S->stacksize=INIT_SIZE;//栈大小 return 0; }

int Push(SqStack *S, BiTree T) //插入栈顶 { if( (unsigned)(S->top - S->base) >= S->stacksize){//栈满，追加存储空间 S->base=(BiTree *)realloc(S->base, (S->stacksize+INCREMENT)*sizeof(BiTree) ); if(!S->base)//分配失败，返回1 return 1; //分配成功 S->top = S->base + S->stacksize;//置栈顶指针 S->stacksize += INCREMENT;//栈大小 } *S->top++ = T;//接收输入后，S->top指向栈顶元素的下一个位置

return 0; }
#15
Antigloss2005-02-08 12:03

线索二叉树

definition.h ============================================ typedef char TElemType; typedef enum{Link, Thread} PointerTag;//Link==0：指针；Thread==1：线索

typedef struct{ TElemType data; struct BiThrNode *lchild, *rchild;//左右孩子指针 PointerTag LTag, RTag;//左右标志 }BiThrNode, *BiThrTree;//二叉树的二叉链表存储表示

BiThrTree CreateBiThrTree(void);//按先序次序输入二叉树中结点的值，'#'代表空树 void InOrderTraverse_Thr(BiThrTree);//中序遍历二叉线索树，非递归 BiThrTree InOrderThreading(BiThrTree);//中序线索化二叉线索树 BiThrTree InThreading(BiThrTree, BiThrTree);//中序遍历进行中序线索化 =======================================================================

main.c ==================================================== #include <stdio.h> #include "definition.h"

int main() { BiThrTree bt;

printf("请输入根结点："); bt = CreateBiThrTree();//按先序次序创建二叉树 if( !(bt=InOrderThreading(bt)) )//中序线索化二叉线索树 return 1;//线索化失败 InOrderTraverse_Thr(bt);//中序遍历二叉线索树，非递归 printf("\n");

return 0; } =================================================================

function.c ================================================== #include <stdio.h> #include <malloc.h> #include "definition.h"

BiThrTree CreateBiThrTree(void)//按先序次序输入二叉树中结点的值，'#'代表空树 { TElemType e; BiThrTree tmp = NULL;

if( (e=getchar())!='#' ){ getchar();//接收回车符 tmp=(BiThrTree)malloc(sizeof(BiThrNode)); if(!tmp) return NULL; tmp->data=e; tmp->LTag=tmp->RTag=Link; printf("请输入左孩子："); tmp->lchild=CreateBiThrTree(); printf("请输入右孩子："); tmp->rchild=CreateBiThrTree(); } else getchar();//接收回车符

return tmp; }

BiThrTree InOrderThreading(BiThrTree bt)//中序线索化二叉线索树 { BiThrTree thrt, pre;

if( !( thrt=(BiThrTree)malloc(sizeof(BiThrNode)) ) ) return NULL;//建头结点失败 thrt->LTag=Link; thrt->RTag=Thread; thrt->rchild=thrt;//右指针回指 if(!bt) thrt->lchild=thrt;//若二叉树空，左指针回指 else{ thrt->lchild=bt; pre=thrt; pre=InThreading(bt, pre);//中序遍历进行中序线索化 //最后一个结点线索化 pre->rchild=thrt; pre->RTag=Thread; thrt->rchild=pre; }

return thrt; }

BiThrTree InThreading(BiThrTree bt, BiThrTree pre)//中序遍历进行中序线索化 { if(bt){ pre=InThreading(bt->lchild, pre);//左子树线索化 //前驱线索 if(!bt->lchild){ bt->LTag=Thread; bt->lchild=pre; } //后继线索 if(!pre->rchild){ pre->RTag=Thread; pre->rchild=bt; } pre=bt;//保持pre指向p的前驱 pre=InThreading(bt->rchild, pre);//右子树线索化 }

return pre; }

void InOrderTraverse_Thr(BiThrTree bt)//中序遍历二叉线索树，非递归 { BiThrTree tmp = bt->lchild;

while(tmp != bt){ while(tmp->LTag==Link) tmp=tmp->lchild; printf("%c", tmp->data); while(tmp->RTag==Thread && tmp->rchild!=bt){ tmp=tmp->rchild; printf("%c", tmp->data); } tmp=tmp->rchild; } }
#16
Antigloss2005-02-08 12:04

赫夫曼树

definition.h ============================================ typedef struct{ unsigned weight; unsigned parent, lchild, rchild; }HTNode, *HuffmanTree;//动态分配数组存储赫夫曼树

typedef char **HuffmanCode;//动态分配数组存储赫夫曼编码表

void Select(HuffmanTree, unsigned, unsigned *, unsigned *);//选择parent为0，且weight最小的两个结点 ==================================================================

main.c ===================================================== #include <stdio.h> #include <malloc.h> #include <string.h> #include "definition.h"

int main() { unsigned n, m, i, s1, s2, start, c, f; char *cd; HuffmanTree HT, p; HuffmanCode HC;

printf("请问您要输入多少个字符？ "); scanf("%d", &n); if(n<2) return 1; m = 2 * n - 1; HT = (HuffmanTree)malloc( (m + 1) * sizeof(HTNode) );//0号单元未用 if(!HT) return 1; for(p=HT+1, i=1; i<=n; i++, p++){ printf("请您输入权值："); scanf("%d", &p->weight); p->lchild = p->parent = p->rchild = 0; } for(; i<=m; i++, p++) p->lchild = p->parent = p->rchild = p->weight = 0;

//建赫夫曼树 for(i=n+1; i<=m; i++){ s1 = s2 = 0; Select(HT, i, &s1, &s2);//选择parent为0，且weight最小的两个结点 HT[s1].parent = HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }

//从叶子到根逆向求每个字符的赫夫曼编码 HC = (HuffmanCode)malloc( (n+1) * sizeof(char *) );//分配n个字符编码的头指针向量 if(!HC) return 1; cd = (char *)malloc( n * sizeof(char) );//分配编码的工作空间 if(!cd) return 1; cd[n-1] = '\0';//编码结束符 for(i=1; i<=n; i++){//逐个字符求赫夫曼编码 start = n - 1;//编码结束位置 for(c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent){//从叶子到根逆向求编码 if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } HC[i] = (char *)malloc( (n-start)*sizeof(char) );//为第i个字符编码分配空间 if(!HC[i]) return 1; strcpy(HC[i], &cd[start]); printf("%s\n", HC[i]); } free(cd);//释放工作空间

return 0; } //其它动态分配的空间还没释放 ==============================================================================

function.c ================================================================= #include "definition.h"

void Select(HuffmanTree p, unsigned i, unsigned *s1, unsigned *s2) {//选择parent为0，且weight最小的两个结点 unsigned j;

for(j=1; j<i; j++){ if( !p[j].parent ){ if( !*s1 ) *s1 = j; else{ if(p[*s1].weight > p[j].weight){ *s2 = *s1; *s1 = j; } else *s2 = j; } } if( *s1 && *s2 ) break; } for(j++; j<i; j++){ if( !p[j].parent ){ if( p[*s1].weight > p[j].weight ){ *s2 = *s1; *s1 = j; } else{ if( p[*s2].weight > p[j].weight ) *s2 = j; } } } }
#17
sogood2005-03-29 20:28
非常好哈！！
#18
不羁浪子2005-04-07 13:28
弓虽！
#19
BlueDreame2005-04-07 19:10
楼主辛苦了
#20
luyulin2005-04-11 18:14
好 牛啊 厉害！！！！！ 顶
#21
luyulin2005-04-11 18:18
好
#22
不羁浪子2005-04-17 01:29
能不能提供压缩包下载啊？！
#23
Antigloss2005-04-17 09:15
打包下载~~
只有本站会员才能查看附件，请 登录
#24
lijunhua2005-04-21 23:00
非常好!在此谢了.
#25
涛声依旧2005-04-24 23:47
顶，一个字强～～～！～～～
佩服，以后有这个多发上来，大家看了共同学习哈．
#26
修因2005-05-19 14:37
下载的我也会啊！
#27
shuiyaojin2005-05-29 23:00
正在学习数据结构
楼主的帖子对我受益非浅
在此谢谢了
#28
david22342005-06-02 15:24
太强了,支持!
#29
foxsxt2005-06-04 14:25
高手，能不能帮不能帮我写一个关于文学助手研究的程序 题目是这样的：

文学助手研究

[问题描述]文学研究人员需要统计某篇英文小说某些形容词出现次数与位置。试写一个实现这一目标的文字统计系统，称为“文学研究助手”。

[基本要求]英文小说存在于一个文本文件中。待统计的词汇集合要一次输入完毕，即统计工作必须在程序的一次运行之后就会全部完成。程序的输出结果是每个词的出现次数和出现位置所在行的行号，格式自行设计。

[测试数据]以你的C源程序模拟英文小说，C语言的保留字集作为待统计的词汇集。

[实现提示]约定小说中的词汇一律不跨行。这样，每读入一行，就统计每个词在这行中的出现次数。出现位置所在行的行号可以用链表存储。若某行中出现了不止一次，不必存多个相同的行号。

如果读者希望达到选作部分（1）和（2）所提出的要求，则首先应把KMP算法改写成如下的等价形式，再把它推广到多个模式的情形。

i=1;j=1;

while(i=!s.curlen+1&&j!=t.curlen+1){

while(j!=0&&s.h[I]!=t.ch[j]j=next[j];

//j==0或s.ch[I]==t.ch[j]

j++;I++;//每次进入循环体，I 只增加一次}

[选作内容]

（1）模式匹配要基于KMP算法。

（2）整个统计过程中只对小说文字扫描一遍以提高效率。

（3）假设小说中的每个单词或者从首行开始，或者前置一个空格符。利用单词匹配特点另写一个高效的统计程序，与KMP算法统计程序进行效率比较。

（4）推广到更一般的模式集匹配问题，并设待查模式串可以跨行（提示：定义操作GetAChar）。
#30
hailiang2005-06-16 03:16
大哥，太厉害了！我什么时候能有这水平啊
#31
sogood2005-06-17 08:54
赫夫曼，2叉树的线索话，上机测试的结果是错的
这里尤其要说赫夫曼
#32
sogood2005-06-17 08:55
不要意思刚才发不出去，发了两次

[此贴子已经被作者于2005-6-17 8:58:07编辑过]
#33
泾水荣梦2005-06-18 09:06
你好强哦
#34
leefix2005-06-22 16:16
好长啊！！
#35
xl0072005-06-24 22:35
好!!! 不错  能不能 给出一个二叉树的操作程序  实现功能:1)用完全二叉树的性质建立一棵二叉树 2)统计叶子结点的个数  3)求二叉树的深度

谢谢了 !!!
#36
Flovex2005-06-26 16:10
哇，楼主真强啊！佩服啊！好东西，谢谢楼主的分享！顶！
#37
零度之爱2005-07-04 19:41
======在 2005-7-4 19:11:16 您来信中写道：======
编程论坛全体管理人员欢迎您的到来如有论坛使用上的疑问进『 论坛使用技巧 』里面的一些帖子对新手很有帮助。
======================================
OK
#38
非主流2005-08-23 00:05
太强了，非常有用的东西
#39
提灯寻影2006-03-27 00:01
学习了，谢谢
很经典哦
#40
angel_in_hel2006-05-08 17:18
太辛苦了
#41
lavender09162006-05-09 07:11

谁知道这个程序怎么编写啊～？大家帮帮忙啊～！写出来的可以发到我的邮箱啊～！lavender0916@163.com 谢谢啦～！

编写程序实现整型多维数组，各维的下标是任意整数开始的等差整数列，此数组能检查下标范围是否越界，下标能用变量赋值，同类型数组能相互赋值，数组大小能调整.
#42
haishanglang2006-05-13 16:51

楼主好强啊
#43
tianyu19832006-05-16 19:27
非常感谢
生了我不少的时间
呵呵
#44
hexquan2006-05-25 17:09

能不能用两个一唯的数组来代替栈的操作呢，那样太麻烦了？
#45
khyang2006-05-27 21:24
不错，应该好好学习
#46
月孤寒2006-05-28 17:11

这个函数缺个main函数,请各位高手帮帮忙 ,偶是新手
谢谢
int sq_insert(list,p_h,i,x)
int list[],x;
int *p_n,i;
{ int j;
if(i<0||i>*p_n) return(1);
if(*p_n==MAXSIZE) return(2);

for(j=*p_n;j>i;j--)

list[j]=list[j-1];

list[i]=x;

(*p_n)++;

return(0);

}

#47
mechanics2006-05-30 00:34
好东西
#48
carollvy2006-06-04 03:03

楼主，能不能帮忙写个程序啊！
在一个程序中，用六种以下：冒泡排序，直接插入排序，直接选择排序，希尔排序，快速排序，堆排序。方法编写出来，每个结果都不干涉．
即在主函数中要包括以上六种排序
而且都要有输出］
谢谢拉，呵呵
这可是我的期末考试题，哥哥帮帮忙拉
#49
superdesign2006-06-05 12:33
多谢上楼的大哥了。以后有好多要请教您。
#50
上杉冰枫2006-06-24 18:12
我倒
这强
#51
傻小鹰少2006-07-04 23:48

想请楼主帮小弟个忙,写个程序
因为小弟编程超烂的!~!~
设计一个简单的LISP算术表达式计算器。
简单LISP算术表达式定义如下：
（1）一个0..9的整数；或者（2）（运算符 表达式 表达式）
例如：6，（+45），（+（+25）8）都是表达式，其值分别为6，9和15。
[基本要求]
实现LISP加法表达式的求值。
[测试数据]
6，（+45），（+（+25）8），
（+2（+58）），
（+（+（+12）（+34））（+（+56）（+78）））
[实现提示]
写一个递归函数：
int Evaluate(FILE * CharFile)
字符文件CharFile的每行是一个如上定义的表达式。每读入CharFile的一行，求出并返回表达式的值。
可以设计以下辅助函数
status isNumber(char ReadInChar);
//视ReadInChar 是否是数字而返回TRUE或FALSE。
int TurnToInteger(char InChar)
//将字符‘0’....‘9’转换为整数0....9
麻烦楼主帮下忙,诚谢!~!~
12
©2025, BCCN.NET
电脑版