数据结构算法基本程序.doc

一、 线性表及其操作1、 尾插法建立一个单链表，并按顺序输出2、 单链表的元素查找，按内容查找3、 元素插入操作4、 按内容元素删除操作5、 按位置删除元素6、 建立双向链表7、 单链表就地逆置8、 约瑟夫环问题二、 栈及其操作1、 建立堆栈2、 进栈与出栈3、 栈的应用，括号匹配三、 队及其操作1、 链队列的建立2、 入队和出队3、 循环队列建立4、 循环队列的入队和出队操作四、 串及其操作1、 串的朴素匹配五、 树（二叉树）及其操作1、 二叉排序树2、 哈夫曼编码六、 排序1、 冒泡排序2、 直接选择排序法一、线性表及其操作/All copyright are preserved by cobby/*尾插法建立一个单链表，并按顺序输出*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/ char c; /*数据域，类型为字符型*/ struct node *next; /*指针域，类型为本结构体类型*/*L; /*类型重定义，即Node和*L和struct node等价*/main() L l,p,q; /*用指针类型定义三个结点类型的指针*/ char ch; l=(L)malloc(sizeof(L); /*分配内存空间*/ l-c=0; /*为头结点的数据域赋值，值为空*/ l-next=NULL; /*指明下一个结点目前不存在*/ q=l; /*q为游动指针，链表结点的连结要用*/ printf(Input a character:n); scanf(%c,&ch); getchar(); /此语句用来吸收键盘输入的回车符，没有其它含义 while(ch!=!) /*输入!表示输入结束*/ p=(L)malloc(sizeof(L); /*为新输入的数据分配内存空间*/ p-c=ch; p-next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/ q-next=p; /*q用于将上一个元素链接至当前新元素*/ q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/ scanf(%c,&ch); getchar(); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /All copyright are preserved bycobby/*单链表的元素查找，按内容查找*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/ char c; /*数据域，类型为字符型*/ struct node *next; /*指针域，类型为本结构体类型*/*L; /*类型重定义，即Node和*L和struct node等价*/main() L l,p,q; /*用指针类型定义三个结点类型的指针*/ char ch; int n; l=(L)malloc(sizeof(L); /*分配内存空间*/ l-c=0; /*为头结点的数据域赋值，值为空*/ l-next=NULL; /*指明下一个结点目前不存在*/ q=l; /*q为游动指针，链表结点的连结要用*/ printf(Input a character:n); scanf(%c,&ch); getchar(); while(ch!=!) /*输入!表示输入结束*/ p=(L)malloc(sizeof(L); /*为新输入的数据分配内存空间*/ p-c=ch; p-next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/ q-next=p; /*q用于将上一个元素链接至当前新元素*/ q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/ scanf(%c,&ch); getchar(); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /*-以上为建立一个单链表-*/ printf(nInput a character you wanna findn); scanf(%c,&ch); printf(nthe character you wanna find is %cn,ch); q=l-next; /*q移至头结点的后一个元素，即实际第一个数据点*/ n=1; /位置计数器 while(q!=NULL) /*若q不为空，即该结点存在*/ if(q-c=ch) /*字符匹配*/ printf(character found in position %dn,n); q=q-next; /*移至下一个元素继续查找*/ n+; /All copyright are preserved bycobby/*元素插入操作*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/ char c; /*数据域，类型为字符型*/ struct node *next; /*指针域，类型为本结构体类型*/Node,*L; /*类型重定义，即Node和*L和struct node等价*/main() L l,p,q; /*用指针类型定义三个结点类型的指针*/ char ch; int pos,n; l=(L)malloc(sizeof(Node); /*分配内存空间*/ l-c=0; /*为头结点的数据域赋值，值为空*/ l-next=NULL; /*指明下一个结点目前不存在*/ q=l; /*q为游动指针，链表结点的连结要用*/ printf(Input a character:n); scanf(%c,&ch); getchar(); while(ch!=!) /*输入!表示输入结束*/ p=(L)malloc(sizeof(Node); /*为新输入的数据分配内存空间*/ p-c=ch; p-next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/ q-next=p; /*q用于将上一个元素链接至当前新元素*/ q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/ scanf(%c,&ch); getchar(); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /*以上为建立一个单链表*/ printf(Input the character and its position, such as s,3nn); scanf(%c,%d,&ch,&pos); q=l; n=1; while(n!=pos&q-next!=NULL) /*未找到插入位置，且后面还有元素*/ q=q-next; n+; /*退出循环后，要么找到插入位置，要么表已到最后，输入的插入位置过大*/ if(nc=ch; p-next=q-next; q-next=p; /*操作完成，然后输出新表*/ q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /All copyright are preserved bycobby/*按内容元素删除操作*/#include#include#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/ char c; /*数据域，类型为字符型*/ struct node *next; /*指针域，类型为本结构体类型*/Node,*L; /*类型重定义，即Node和*L和struct node等价*/main() L l,p,q; /*用指针类型定义三个结点类型的指针*/ char ch; int n; l=(L)malloc(sizeof(Node); /*分配内存空间*/ l-c=0; /*为头结点的数据域赋值，值为空*/ l-next=NULL; /*指明下一个结点目前不存在*/ q=l; /*q为游动指针，链表结点的连结要用*/ printf(Input a character:n); scanf(%c,&ch); getchar(); while(ch!=!) /*输入!表示输入结束*/ p=(L)malloc(sizeof(Node); /*为新输入的数据分配内存空间*/ p-c=ch; p-next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/ q-next=p; /*q用于将上一个元素链接至当前新元素*/ q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/ scanf(%c,&ch); getchar(); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /*以上为建立单链表*/ printf(input the character you wanna deletenn); scanf(%c,&ch); printf(the element you wanna delete is %cnn,ch); q=l-next; p=l; n=1; while(q!=NULL&q-c!=ch) p=q; q=q-next; n+; /*退出循环时可能找到指定元素，也可能表读完，需要进一步判断*/ if(q=NULL) printf(element not found, delete failednn); else p-next=q-next; q=l-next; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /All copyright are preserved bycobby/*按位置删除元素*/#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/ char c; /*数据域，类型为字符型*/ struct node *next; /*指针域，类型为本结构体类型*/Node,*L; /*类型重定义，即Node和*L和struct node等价*/main() L l,p,q; /*用指针类型定义三个结点类型的指针*/ char ch; int pos,n; l=(L)malloc(sizeof(Node); /*分配内存空间*/ l-c=0; /*为头结点的数据域赋值，值为空*/ l-next=NULL; /*指明下一个结点目前不存在*/ q=l; /*q为游动指针，链表结点的连结要用*/ printf(Input a character:n); scanf(%c,&ch); getchar(); while(ch!=!) /*输入!表示输入结束*/ p=(L)malloc(sizeof(Node); /*为新输入的数据分配内存空间*/ p-c=ch; p-next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/ q-next=p; /*q用于将上一个元素链接至当前新元素*/ q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/ scanf(%c,&ch); getchar(); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /*以上为建立单链表*/ printf(Input the positionn); scanf(%d,&pos); p=l; n=1; while(p-next!=NULL&n!=pos) p=p-next; n+; /*退出循环后，可能找到删除的元素位置，可能表读完，需要进一步判断*/ if(n=pos) /*删除位置找到，删除该位置上的元素*/ p-next=p-next-next; /free(p); else printf(incorrect position, delete failedn); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ /建立双向链表#include#include#include#define NULL 0typedef struct dlnode char ch; struct dlnode *pri,*next;dnode,*dl;main() dl l,p,q; char c; l=(dl)malloc(sizeof(dnode); l-ch=0; l-next=NULL; l-pri=NULL; q=l; printf(输入字符建立双向链表n); scanf(%c,&c); getchar(); while(c!=!) p=(dl)malloc(sizeof(dnode); p-ch=c; p-pri=q; p-next=NULL; q-next=p; q=p; scanf(%c,&c); getchar(); q=l; while(q-next!=NULL) q=q-next; printf(%c-,q-ch); printf(n); while(q-pri!=NULL) printf(%c-,q-ch); q=q-pri; printf(n);/单链表就地逆置#define NULL 0 /*宏定义*/typedef struct node /*定义结点类型的数据结构*/ char c; /*数据域，类型为字符型*/ struct node *next; /*指针域，类型为本结构体类型*/Node,*L; /*类型重定义，即Node和*L和struct node等价*/main() L l,p,q,r; /*用指针类型定义三个结点类型的指针*/ char ch; l=(L)malloc(sizeof(Node); /*分配内存空间*/ l-c=0; /*为头结点的数据域赋值，值为空*/ l-next=NULL; /*指明下一个结点目前不存在*/ q=l; /*q为游动指针，链表结点的连结要用*/ printf(Input a character:n); scanf(%c,&ch); getchar(); while(ch!=!) /*输入!表示输入结束*/ p=(L)malloc(sizeof(Node); /*为新输入的数据分配内存空间*/ p-c=ch; p-next=NULL; /*新输入的结点在链表的最后，即它的后面没有其它元素*/ q-next=p; /*q用于将上一个元素链接至当前新元素*/ q=p; /*q自己移到当前最后一个元素，以备继续链接所用*/ scanf(%c,&ch); getchar(); q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ printf(n); /以上完成了单链表的创建 q=l-next; p=q-next; r=p-next; q-next=NULL; while(r!=NULL) p-next=q; q=p; p=r; if(r-next!=NULL) /r后面还有结点，则逆置继续 r=r-next; else break; r-next=q; l-next=r; /头结点指向最后一个结点 q=l; /*输入整个链表前，先将q移到链表头，l一般不动*/ while(q-next!=NULL) /*若q所指向的元素后面还有其它元素，则将该元素的数据输出*/ printf(%c-,q-next-c); /*q-next-c表示q所指向的下一个元素的数据*/ q=q-next; /*完成该元素的输出后，q移至下一个元素重复输出操作*/ printf(n);/约瑟夫环问题#include#includetypedef struct lnode int num; struct lnode *next;node,*L;main() int amount,start,circle,n,c; L p,l,q; printf(一共有几个人围成一圈？n); scanf(%d,&amount); getchar(); printf(从第几个开始计数？n); scanf(%d,&start); getchar(); printf(每几人一次循环？n); scanf(%d,&circle); getchar(); l=(L)malloc(sizeof(node); /头结点 l-next=NULL; l-num=0; q=l; n=0; while(n+next=NULL; p-num=n; q-next=p; q=p; q-next=l-next; /形成循环链表 /以上完成了单向循环链表的建立 p=l-next; q=l; n=1; while(n+next; q=q-next; /退出循环时p,q分别位于指定位置 /接下去进行周期性结点删除，直到链表只余一个结点为止 n=1; /n计算被删除的结点的数量，当n=amount-1时删除结束 while(n+amount) c=1; /c作为循环临时变量 while(C+next; q=q-next; /删除当前p指向的结点 printf(删除结点%dt,p-num); q-next=p-next; p=p-next; printf(n最后剩下%dn,p-num);二、栈及其操作/All copyright are preserved bycobby/*建立堆栈*/#include#include#define NULL 0typedef struct node char ch; struct node *next;Snode,*stack;main() stack s,top,p; char ch; s=(stack)malloc(sizeof(Snode); s-ch=0; s-next=NULL; /*建立栈底指针*/ top=s; scanf(%c,&ch); getchar(); while(ch!=!) p=(stack)malloc(sizeof(Snode); p-ch=ch; p-next=top; top=p; scanf(%c,&ch); getchar(); while(top-next!=NULL) printf(%c-,top-ch); top=top-next; printf(n);/All copyright are preserved bycobby/*进栈与出栈*/#include#include#define NULL 0typedef struct node char ch; struct node *next;Snode,*stack;main() stack s,top,p; char ch; int choice; s=(stack)malloc(sizeof(Snode); s-ch=!; s-next=NULL; /*建立栈底指针*/ top=s; scanf(%c,&ch); getchar(); while(ch!=!) p=(stack)malloc(sizeof(Snode); p-ch=ch; p-next=top; top=p; scanf(%c,&ch); getchar(); while(p-next!=NULL) /此处p可用top代替 printf(%c-,p-ch); p=p-next; printf(n); /*以上建立了一个堆栈*/ printf(进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退出程序n); scanf(%d,&choice); getchar(); while(choice=1|choice=2) /若不是输入1或2，则不做任何操作 if(choice=1) /*进栈*/ printf(n输入要入栈的元素n); scanf(%c,&ch); getchar(); p=(stack)malloc(sizeof(Snode); p-ch=ch; p-next=top; top=p; else if(choice=2) if(top-next!=NULL) top=top-next; else printf(栈已清空n); exit(); /*出栈*/ /printf(%c-,top-ch); p=top; while(p-next!=NULL) printf(%c-,p-ch); p=p-next; printf(n); printf(进栈或出栈？输入“1”为进栈，输入“2”为出栈，其它则退出程序n); scanf(%d,&choice); getchar(); /All copyright are preserved bycobby/栈的应用，括号匹配#include#include#define NULL 0typedef struct node char ch; struct node *next;snode,*stack;main() stack s,top,p; char *string,ch100=; s=(stack)malloc(sizeof(snode); /建立栈底元素 s-ch=0; s-next=NULL; top=s; printf(输入一个含括号的四则运算表达式：n); scanf(%s,ch); string=ch; while(*string!=0) if(*string=(|*string=|*string=) /遇到左括号，入栈 p=(stack)malloc(sizeof(snode); p-ch=*string; p-next=top; top=p; else if(*string=)|*string=|*string=) /遇到右括号 if(*string=) if(top-ch=() /括号匹配 top=top-next; else printf(小括号不匹配); exit(0); else if(*string=) if(top-ch=) /括号匹配 top=top-next; else printf(中括号不匹配); exit(0); else if(top-ch=) /括号匹配 top=top-next; else printf(大括号不匹配); exit(0); string+; if(top-ch!=0) printf(多出左括号%cn,top-ch); 三、队及其操作/All copyright are preserved bycobby/链队列的建立#include#include#include#define NULL 0typedef struct node /队列结点的基本数据结构，即队列中每个结点的类型 char c; struct node *next;qnode,*basic_node;typedef struct /队列实际上由头、尾两个结点指针构成，即头指针和尾指针唯一确定时，队列也被唯一确定 qnode *head; qnode *rear;queue,*Q;main() Q q; /定义队列，结构体变量q中含有头指针head和尾指针rear，所以q是一个完整的队列（只不过队列为空） /事实上，任何由Q定义的结构体变量都是一个独立完整的队列 basic_node p,l; /basic_node是基本结点类型，即是独立的结点，它是组成队列的基本元素。 /基本结点p,l和队列q的关系可由下图表示： / (q-head)-p-l-p-l-p-l-(q-rear) char ch; q=(Q)malloc(sizeof(queue); q-head=NULL; /初始化时队列为空 q-rear=NULL; printf(输入队列元素:n)