数据结构经典代码(严蔚敏)

/*线性表的顺序表示：类型和界面定义*//*线性表的顺序表示：函数实现*//*线性表的单链表表示：类型和界面函数定义*//*线性表的单链表表示：函数实现*//*线性表的顺序表示：类型和界面定义*//*线性表的顺序表示：函数实现*//*用顺序表解决josephus问题的算法*//*用循环单链表解决josephus问题的算法*//*字符串的顺序表示*//*字符串的链接表示*//*顺序栈表示：类型和界面函数声明*//*顺序栈表示：函数定义*//*栈链接表示：类型和界面函数声明*//*栈链接表示：函数定义*//*简化背包问题的递归算法*//*简化背包问题的非递归算法*//*迷宫问题的递归算法*//*迷宫问题的非递归算法(栈实现)*//*队列的顺序表示：类型和函数声明*//*队列的顺序表示：函数定义*//*队列链接表示：类型和界面函数声明*//*队列链接表示：函数定义*//*用队列解决农夫过河问题的算法*//*树的长子-兄弟表示法*//*树的父指针表示法*//*树的子表表示法*//*树的后根周游的递归算法*//*树的先根周游的非递归算法*//*树的中根周游的递归算法*//*树的后根周游的递归算法*//*树的广度优先周游算法*//*二叉树的链接表示*//*二叉树的顺序表示*//*线索二叉树的定义,构造算法和中根周游算法*//*二叉树前根周游的递归算法*//*二叉树对称根周游的递归算法*//*二叉树后根周游的递归算法*//*二叉树后根周游的非递归算法*//*本程序提供了用顺序表实现字典的存储表示定义*//*本程序是用开地址法解决碰撞的散列表示方法,提供了字典的一些基本操作*//*字典的二叉排序树实现,本程序实现了二叉排序树的基本操作的算法*//*字典的AVL树实现*//*本程序提供了用顺序表实现字典的情况下的顺序检索算法*//*本程序提供了用顺序表实现字典的情况下的二分法检索算法*//*本程序是用开地址法实现散列的检索算法*//*二叉排序树的检索算法*//*AVL树的检索算法*//*最佳二叉排序树是具有最佳检索效率的二叉排序树,本程序提供了最佳二叉排序树的构造方法*//*直接插入排序的算法源程序*//*二分法插入排序的算法源程序*//*表插入排序的算法源程序*//*shell排序的算法源程序*//*直接选择排序的算法源程序*//*堆排序的算法源程序*//*起泡排序的算法源程序*//*快速排序的算法源程序*//*基数排序的算法源程序*//*二路归并排序算法的源程序*//*用图邻接矩阵表示实现的一些基本运算*//*用图邻接表表示实现的一些基本运算*//*用邻接矩阵表示的图的广度优先周游算法*//*用邻接表表示的图的广度优先周游算法*//*用邻接矩阵表示的图的深度优先周游的递归算法*//*用邻接矩阵表示的图的深度优先周游的非递归算法*//*用邻接表表示的图的深度优先周游的非递归算法*//*用邻接矩阵表示的图的Kruskal算法的源程序*//*用邻接矩阵表示的图的prim算法的源程序*//*用邻接矩阵表示的图的Dijkstra算法的源程序*//*用邻接矩阵表示的图的Floyd算法的源程序*//*用邻接表表示图的拓扑排序算法*//*用邻接矩阵表示图的拓扑排序算法*//*图的关键路径问题的算法*//*背包问题的贪心法算法*//*用动态规划法求组和数的算法*//*用回溯法解决骑士周游问题的算法*//*0/1背包问题的回溯法算法*//*0/1背包问题的动态规划法算法*//*0/1背包问题的分支定界法算法*//*线性表的顺序表示：类型和界面定义*/#defineTRUE1#defineFALSE0#defineSPECIAL-1/*定义顺序表的大小。应根据需要修改*/#defineMAXNUM20/*定义顺序表的元素类型。应根据需要修改*/typedefintDataType;structSeqList{intn;/*存放线性表中元素的个数nMAXNUM*/DataTypeelement[MAXNUM];/*存放线性表中的元素*/};typedefstructSeqListSeqList,*PSeqList;/*创建新的顺序表*/PSeqListcreateNullList_seq(void);/*判断顺序表是否为空*/intisNullList_seq(PSeqListpalist);/*在palist所指顺序表中下标为p的元素之前插入元素x*/intinsert_seq(PSeqListpalist,intp,DataTypex);/*在palist所指顺序表中删除下标为ｐ的元素*/intdelete_seq(PSeqListpalist,intp);/*求x在palist所指顺序表中的下标*/intlocate_seq(PSeqListpalist,DataTypex);/*求palist所指顺序表中下标为p的元素值*/DataTyperetrieve_seq(PSeqListpalist,intp);/*线性表的顺序表示：函数实现*/#includestdio.h#includestdlib.h#includeslist.hPSeqListcreateNullList_seq(void){PSeqListpalist=(PSeqList)malloc(sizeof(structSeqList));if(palist!=NULL)palist-n=0;/*空表长度为0*/elseprintf(Outofspace!\n);/*存储分配失败*/returnpalist;}/*在palist所指顺序表中下标为p的元素之前插入元素x*/intinsert_seq(PSeqListpalist,intp,DataTypex){intq;if(palist-n==MAXNUM){/*溢出*/printf(Seq-listoverflow!\n);returnFALSE;}if(p0||ppalist-n){/*不存在下标为p的元素*/printf(Indexofseq-listisoutofrange!\n);returnFALSE;}for(q=palist-n-1;q=p;q--)/*插入位置及之后的元素均后移一个位置*/palist-element[q+1]=palist-element[q];palist-element[p]=x;/*插入元素x*/palist-n++;/*元素个数加1*/returnTRUE;}/*在palist所指顺序表中删除下标为ｐ的元素*/intdelete_seq(PSeqListpalist,intp){intq;if(p0||ppalist-n-1){/*不存在下标为p的元素*/printf(Indexofseq-listisoutofrange!\n);returnFALSE;}for(q=p;qpalist-n-1;q++)/*被删除元素之后的元素均前移一个位置*/palist-element[q]=palist-element[q+1];palist-n--;/*元素个数减1*/returnTRUE;}/*求x在palist所指顺序表中的下标*/intlocate_seq(PSeqListpalist,DataTypex){intq;for(q=0;qpalist-n;q++)if(palist-element[q]==x)returnq;return-1;}/*求palist所指顺序表中下标为p的元素值*/DataTyperetrieve_seq(PSeqListpalist,intp){if(p=0&&ppalist-n)/*存在下标为p的元素*/returnpalist-element[p];printf(Indexofseq-listisoutofrange.\n);returnSPECIAL;/*返回一个顺序表中没有的特殊值*/}intisNullList_seq(PSeqListpalist){returnpalist-n==0;}/*线性表的单链表表示：类型和界面函数定义*//*定义链接表元素类型。应根据需要定义*/typedefintDataType;structNode;/*单链表结点类型*/typedefstructNode*PNode;/*结点指针类型*/typedefstructNode*LinkList;/*单链表类型*/structNode{/*单链表结点结构*/DataTypeinfo;PNodelink;};/*创建一个带头结点的空链表*/LinkListcreateNullList_link(void);/*在llist带头结点的单链表中下标为i的(第i+1个)结点前插入元素x*/intinsert_link(LinkListllist,inti,DataTypex);/*在llist带有头结点的单链表中删除第一个值为x的结点*/intdelete_link(LinkListllist,DataTypex);/*在llist带有头结点的单链表中找第一个值为x的结点存储位置*/PNodelocate_link(LinkListllist,DataTypex);/*在带有头结点的单链表llist中求下标为i的(第i+1个)结点的存储位置*//*当表中无下标为i的(第i+1个)元素时，返回值为NULL*/PNodefind_link(LinkListllist,inti);/*判断llist带有头结点的单链表是否是空链表*/intisNullList_link(LinkListllist);/*线性表的单链表表示：函数实现*/#includestdio.h#includestdlib.h#includellist.h/*创建一个带头结点的空链表*/LinkListcreateNullList_link(void){LinkListllist;llist=(LinkList)malloc(sizeof(structNode));/*申请表头结点空间*/if(llist!=NULL)llist-link=NULL;returnllist;}/*在llist带头结点的单链表中下标为i的(第i+1个)结点前插入元素x*/intinsert_link(LinkListllist,inti,DataTypex){PNodep=llist,q;intj;for(j=0;p!=NULL&&ji;j++)/*找下标为i-1的(第i个)结点*/p=p-link;if(j!=i){/*i1或者大于表长*/printf(Indexoflink-listisoutofrange.\n,i);return0;}q=(PNode)malloc(sizeof(structNode));/*申请新结点*/if(q==NULL){printf(Outofspace!\n);return0;}/*插入链表中*/q-info=x;q-link=p-link;p-link=q;/*注意该句必须在上句后执行*/return1;}/*在llist带有头结点的单链表中删除第一个值为x的结点*//*这时要求DataType可以用!=比较*/intdelete_link(LinkListllist,DataTypex){PNodep=llist,q;/*找值为x的结点的前驱结点的存储位置*/while(p-link!=NULL&&p-link-info!=x)p=p-link;if(p-link==NULL){/*没找到值为x的结点*/printf(Datumdoesnotexist!\n);return0;}q=p-link;/*找到值为x的结点*/p-link=p-link-link;/*删除该结点*/free(q);return1;}/*在llist带有头结点的单链表中找第一个值为x的结点存储位置*//*找不到时