考研数据结构代码

目录线性表一、顺序存储1.顺序存储的静态分配2.顺序存储的动态分配3.顺序存储线性表的插入4.顺序存储线性表的删除二、链式存储5.链式存储线性表的结构6.头插法建立单链表7.尾插法建立单链表8.链式存储按序号查找结点9.链式存储按值查找结点10.链式存储插入结点11.链式存储删除结点12.双链表的结构13.双链表的插入14.双链表的删除15.静态链表的结构栈和队列一、顺序栈16.栈的结构17.判断栈空18.进栈19.出栈20.读取栈顶元素21.共享栈的结构22.共享栈的进栈二、链式栈23.链式栈的存储结构24.链式栈的进栈25.链式栈的出栈三、顺序队列26.队列的存储结构27.队列的入队28.队列的出队四、链式队列29.链式队列的存储结构30.链式队列的入队31.链式队列的出队五、栈的应用32.栈的应用：括号匹配34.栈的应用：求斐波那契数列的第n项树和二叉树一、树的存储结构35.树的双亲表示法36.树的孩子表示法37.孩子兄弟表示法38.二叉树的链式存储二、树的遍历39.二叉树的递归先序遍历40.二叉树的递归中序遍历41.二叉树的递归后序遍历42.二叉树的非递归先序遍历43.二叉树的非递归中序遍历44.二叉树的非递归后序遍历45.二叉树的层序遍历三、线索二叉树46.线索二叉树的结构47.中序遍历对二叉树线索化的递归算法48.遍历线索二叉树图一、图的存储结构49.图的邻接矩阵存储50.图的邻接表存储二、图的遍历51.图的广度优先搜索遍历（BFS）52.BFS应用：单源非带权图最短路径53.图的深度优先遍历（DFS）三、图的最小生成树54.求图的最小生成树（Prim算法）55.并查集:查找某个集合的根结点（Kruskal算法用到）56.并查集:合并两个集合（Kruskal算法用到）57.求图的最小生成树:（Kruskal算法）克鲁斯卡尔四、图的最短路径58.图的最短路径算法（Dijkstra算法）迪杰斯特拉59.图的最短路径算法（Floyd算法）弗洛伊德查找60.折半查找61.二叉排序树查找关键字（递归）62.二叉排序树查找关键字（非递归）63.二叉排序树插入关键字64.二叉排序树构造代码排序65.直接插入排序66.希尔排序67.冒泡排序68.快速排序69.选择排序70.堆排序71.归并排序73.拓扑排序线性表一、顺序存储1.顺序存储的静态分配#defineMaxSize50//定义线性表的最大长度typedefintElemtype//假定表中元素类型是inttypedefstruct{ElemTypedata[MaxSize];//顺序表的元素（数组）intlength;//顺序表的当前长度2.顺序存储的动态分配typedefintElemtypetypedefstruct{ElemType*data;//指示动态分配数组的指针intMaxSize,length;//数组的最大容量和当前个数};/*c语言的动态分配语句*/#defineInitSize100SeqListL;L.data=(ElemType*)malloc(sizeof(ElemType)*InitSzie);3.顺序存储线性表的插入boolListInset(Sqlist&L,inti,ElemTypee){if(i1||iL.length+1)returnfalse;//判断i的范围是否有效if(L.length=MaxSize)returnfalse;//当前存储空间已满，不能插入for(intj=L.length;j=i;j--){//将第i个元素及之后的元素后移L.data[j]=L.data[j-1];}L.data[i-1]=e;//在位置i处放入eL.length++;//线性表长度加1returntrue;}4.顺序存储线性表的删除boolListDelete(SqList&L,inti,Elemtype&e){if(i1||i=L.length)returnfalse;//判断i的范围是否有效e=L.data[i];//将被删除的元素赋值给efor(intj=i;j=L.length;j++){//将第i个位置之后的元素前移L.data[j]=L.data[j+1];}L.length--;//线性表长度减1returntrue;}二、链式存储5.链式存储线性表的结构typedefstructLNode//定义单链表结点类型{ElemTypedata;//数据域structLNode*next;//指针域}LNode,*LinkList;6.头插法建立单链表LinkListCreatLinkList(LinkList&L){LNode*s;//辅助指针intx;L=(LinkList)malloc(sizeof(LNode));//创建头结点L-next=NULL;//初始为空链表scanf(%d,&x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode*)malloc(sizeof(LNode));//创建新结点s-data=x;s-next=L-next;L-next=s;//将新结点插入表中，L为头指针scanf(%d,&x);//读入下一个结点值}returnL;}7.尾插法建立单链表LinkListCreatLinkList(LinkList&L){intx;L=(LinkList)malloc(sizeof(LNode));LNode*s,*r=L;//r为表尾指针指向表尾scanf(%d,x);//输入结点的值while(x!=9999){//输入9999表示结束s=(LNode*)malloc(sizeof(LNode));s-data=x;r-next=s;r=s;//r指向新的表尾结点scanf(%d,x);}r-next=NULL;//尾结点指针置空returnL;}8.链式存储按序号查找结点LNode*GetElem(LInkListL,inti){intj=1;//计数，初始为1LNode*p=L-next;//第一个结点指针赋给pif(i==0)returnL;//若i等于0，则返回头结点if(i1)returnNULL;//若i无效，则返回NULLwhile(p&&ji){//从第1个结点开始找，查找第i个结点p=p-next;j++;}returnp;//返回第i个结点的指针，如果i大于表长，直接返回p即可}9.链式存储按值查找结点LNode*LocateElem(LinkListL,ElemTypee){LNode*p=L-next;while(p!=NULL&&p-data!=e){//从第1个结点开始查找data域为e的结点p=p-next;}returnp;//找到后返回该结点指针，否则返回NULL}10.链式存储插入结点算法思路：1.取指向插入位置的前驱结点的指针①p=GetElem(L,i-1);2.令新结点*s的指针域指向*p的后继结点②s-next=p-next;3.令结点*p的指针域指向新插入的结点*s③p-next=s;boolLinkListInsert(LInkList&L,inti,ElemTypee){if(i1||i=L.length)returnfalse;intj=1;LNode*p=L-next,*s;s=(LNode*)malloc(sizeof(LNode));while(p&&ji-1){p=p-next;j++;}s-next=p-next;p-next=s;returntrue;}11.链式存储删除结点算法思路：1.取指向删除位置的前驱结点的指针p=GetElem(L,i-1);2.取指向删除位置的指针q=p-next;3.p指向结点的后继指向被删除结点的后继p-next=q-next4.释放删除结点free(q);boolLinkListDelete(LInkList&L,inti,ElemType&e){if(i1||i=L.length)returnfalse;intj=1;LNode*p=L-next，*q;while(p&&ji-1){p=p-next;j++;}q=p-next;p-next=q-next;e=q-data;free(q);returntrue;}12.双链表的结构typedefstructDNode//定义单链表结点类型{ElemTypedata;//数据域structDNode*prior,*next;//前驱和后继指针}DNode,*DLinkList;13.双链表的插入boolDLinListInsert(DLInkList&L,inti,ElemTypee){if(i1||i=L.length)returnfalse;intj=1;DNode*p=L-next,*s;s=(DNode*)malloc(sizeof(DNode));while(p&&ji-1){p=p-next;j++;}s-next=p-next;p-next-prior=s;s-prior=p;p-next=s;returntrue;}14.双链表的删除boolDLinkListDelete(DLinkList&L,inti,ElemType&e){if(i1||i=L.length)returnfalse;intj=1;DNode*p=L-next，*q;while(p&&ji-1){p=p-next;j++;}q=p-next;p-next=q-next;q-next-prior=p;e=q-data;free(q);returntrue;}15.静态链表的结构#defineMaxSize50//静态链表的最大长度typedefintElemType//静态链表的数据类型假定为inttypedefstruct//静态链表结构类型的定义{ElemTypedata;//数据域：存储数据元素intnext;//指针域：下一个元素的数组下标}SLinkList[MaxSize];栈和队列一、顺序栈16.栈的结构#defineMaxSize50//定义栈中元素的最大个数typedefstruct{ElemTypedata[MaxSize];//存放栈中元素inttop;//栈顶指针}SqStack;//顺序栈的简写17.判断栈空boolStackEmpty(SqStackS){if(s.top==-1)returntrue;elsereturnfalse;}18.进栈boolPush(SqStack&S,ElemTypex){if(S.top==MaxSize-1)returnfalse;S.data[++top]=x;returntrue;}19.出栈boolPop(SqStack&S,ElemType&x){if(S.top==-1)returnfalse;x=S.data[top--];returntrue;}20.读取栈顶元素boolGetTop(SqStack&S,ElemType&x){if(S.top==-1)returnfalse;x=S.data[top];returntrue;}21.共享栈的结构#defineMaxSize100//定义栈中元素的最大个数typedefstruct{ElemTypedata[MaxSize];//存放栈中元素inttop1;//栈1栈顶指针inttop2;//栈2栈顶指针}SqDoubleStack;//顺序共享栈的简写22.共享栈的进栈boolPush(SqDoubleStack&S,ElemTypex,intstackNum){if(S.top1+1==S.top2)returnfalse;//栈满if(stackNum==1)//栈1有元素进栈S.data[++top1]=x;else(stackNum==2)//栈