在重新学数据结构~我会把我写的源代码发上来~希望大家能提出改进意见~谢谢~注释我写得很详细~就算初学者应该也可以看懂~希望能和大家一起讨论~用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编辑过]

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编辑过]

为什么点击后提示错误,系统找不到该文件?

三、单链表的建立与操作

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编辑过]

你直接贴上来吧，大家也好看//

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

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

数制转换

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

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

括号匹配

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

迷宫求解

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