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

数据结构与算法基本程序合集*/ -*/ 出自： 编程中国*/ 作者： cobbyE-mail：QQ：51160333*/ 时间： 2007-10-26编程论坛首发*/ 声明： 尊重作者劳动，转载请保留本段文字*/ -前言：这些是前几年我在大专教书时，数据结构课程中给学生写的学习例程，对于初学者有一定帮助。在此收集到一起，当个共享贴贡献给广大网友和编程爱好者。一般程序都不难也不大，并且所有例程均有较详细注释，适合自学。中间有一个“哈夫曼编码”，程序较大，希望能给大家一点启示。以下所有程序均在VC+6.0开发环境中调试通过，运行正常。有任何疑问可以“另外”发贴讨论。更多内容请访问我的博客。自认为本贴内容充实，对网友会所很大帮助，请版主或者管理员置顶加精，谢谢。数据结构与算法基本程序目录一、线性表及其操作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);elsep-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);elseprintf(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 dlnodechar 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;elsebreak;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 lnodeint 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 nodechar 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 nodechar 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;elseprintf(栈已清空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 nodechar 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;elseprintf(小括号不匹配);exit(0);else if(*string=)if(top-ch=)/括号匹配top=top-next;elseprintf(中括号不匹配);exit(0);elseif(top-ch=)/括号匹配top=top-next;elseprintf(大括号不匹配);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和