2022年数据结构教材代码

第 2 章线性表void Union(List&La,List Lb)/算法 2.1/将所有在线性表Lb 中但不在 La 中的数据元素插入到La 中int La_len,Lb_len,i;ElemType e;La_len=ListLength(La);/求线性表的长度Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取 Lb 中第 i 个数据元素赋给 e if(!LocateElem(La,e,equal)/La 中不存在和 e相同的数据元素ListInsert(La,+La_len,e);/插入 /union void MergeList(List La,List Lb,List&Lc)/算法 2.2/已知线性表 La 和 Lb 中的元素按值非递减排列。/归并 La 和 Lb 得到新的线性表Lc，Lc 的元素也按值非递减排列。int La_len,Lb_len;ElemType ai,bj;int i=1,j=1,k=0;InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 20 页 -while(i=La_len)&(j=Lb_len)/La 和 Lb 均非空GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;while(i=La_len)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/MergeList Status InitList_Sq(SqList&L)/算法 2.3/构造一个空的线性表L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)return OK;/存储分配失败L.length=0;/空表长度为 0 L.listsize=LIST_INIT_SIZE;/初始存储容量return OK;/InitList_Sq 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 20 页 -Status ListInsert_Sq(SqList&L,int i,ElemType e)/算法 2.4/在顺序线性表 L 的第 i 个元素之前插入新的元素e，/i 的合法值为 1iListLength_Sq(L)+1 ElemType*p;if(i L.length+1)return ERROR;/i 值不合法if(L.length=L.listsize)/当前存储空间已满，增加容量ElemType*newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)return ERROR;/存储分配失败L.elem=newbase;/新基址L.listsize+=LISTINCREMENT;/增加存储容量 ElemType*q=&(L.elemi-1);/q 为插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移*q=e;/插入 e+L.length;/表长增 1 return OK;/ListInsert_Sq 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 20 页 -Status ListDelete_Sq(SqList&L,int i,ElemType&e)/算法 2.5/在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值。/i 的合法值为 1iListLength_Sq(L)。ElemType*p,*q;if(iL.length)return ERROR;/i 值不合法p=&(L.elemi-1);/p 为被删除元素的位置e=*p;/被删除元素的值赋给e q=L.elem+L.length-1;/表尾元素的位置for(+p;p=q;+p)*(p-1)=*p;/被删除元素之后的元素左移-L.length;/表长减 1 return OK;/ListDelete_Sq int LocateElem_Sq(SqList L,ElemType e,Status(*compare)(ElemType,ElemType)/算法 2.6/在顺序线性表 L 中查找第 1 个值与 e满足 compare()的元素的位序。/若找到，则返回其在L 中的位序，否则返回0。int i;ElemType*p;i=1;/i 的初值为第 1 个元素的位序p=L.elem;/p 的初值为第 1个元素的存储位置while(i=L.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;/LocateElem_Sq 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 20 页 -void MergeList_Sq(SqList La,SqList Lb,SqList&Lc)/算法 2.7/已知顺序线性表La和 Lb 的元素按值非递减排列。/归并 La 和 Lb 得到新的顺序线性表Lc，Lc 的元素也按值非递减排列。ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType);if(!Lc.elem)exit(OVERFLOW);/存储分配失败pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while(pa=pa_last&pb=pb_last)/归并if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;/插入 La 的剩余元素while(pb next;int j=1;/初始化，p 指向第一个结点，j 为计数器while(p&jnext;+j;if(!p|ji)return ERROR;/第 i 个元素不存在e=p-data;/取第 i 个元素return OK;/GetElem_L Status ListInsert_L(LinkList&L,int i,ElemType e)/算法 2.9/在带头结点的单链线性表L 的第 i 个元素之前插入元素e LinkList p,s;p=L;int j=0;while(p&j next;+j;if(!p|j i-1)return ERROR;/i 小于 1 或者大于表长s=(LinkList)malloc(sizeof(LNode);/生成新结点s-data=e;s-next=p-next;/插入 L 中p-next=s;return OK;/LinstInsert_L 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 20 页 -Status ListDelete_L(LinkList&L,int i,ElemType&e)/算法 2.10/在带头结点的单链线性表L 中，删除第 i 个元素，并由 e返回其值LinkList p,q;p=L;int j=0;while(p-next&j next;+j;if(!(p-next)|j i-1)return ERROR;/删除位置不合理q=p-next;p-next=q-next;/删除并释放结点e=q-data;free(q);return OK;/ListDelete_L void CreateList_L(LinkList&L,int n)/算法 2.11/逆位序输入（随机产生）n个元素的值，建立带表头结点的单链线性表L LinkList p;int i;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;/先建立一个带头结点的单链表for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);/生成新结点p-data=random(200);/改为一个随机生成的数字(200以内)p-next=L-next;L-next=p;/插入到表头/CreateList_L 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 20 页 -void MergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)/算法 2.12/已知单链线性表La和 Lb 的元素按值非递减排列。/归并 La 和 Lb 得到新的单链线性表Lc，Lc 的元素也按值非递减排列。LinkList pa,pb,pc;pa=La-next;pb=Lb-next;Lc=pc=La;/用 La 的头结点作为 Lc 的头结点while(pa&pb)if(pa-data data)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;/插入剩余段free(Lb);/释放 Lb 的头结点/MergeList_L 名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 20 页 -第 6 章二叉树Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/算法 6.2/采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。/中序遍历二叉树T 的非递归算法，对每个数据元素调用函数Visit。stack S;BiTree p;InitStack(S);Push(S,T);/根指针进栈while(!StackEmpty(S)while(GetTop(S,p)&p)Push(S,p-lchild);/向左走到尽头Pop(S,p);/空指针退栈if(!StackEmpty(S)/访问结点，向右一步Pop(S,p);if(!Visit(p-data)return ERROR;Push(S,p-rchild);return OK;/InOrderTraverse 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 20 页 -Status InOrderTraverse(BiTree T,Status(*Visit)(ElemType)/算法 6.3/采用二叉链表存储结构，Visit 是对数据元素操作的应用函数。/中序遍历二叉树T 的非递归算法，对每个数据元素调用函数Visit。stack S;BiTree p;InitStack(S);p=T;while(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;/非空指针进栈，继续左进else /上层指针退栈，访问其所指结点，再向右进Pop(S,p);if(!Visit(p-data)return ERROR;p=p-rchild;return OK;/InOrderTraverse BiTree CreateBiTree(BiTree&T)/算法 6.4/按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，/构造二叉链表表示的二叉树T。char ch;scanf(%c,&ch);if(ch=#)T=NULL;else if(!(T=(BiTNode*)malloc(sizeof(BiTNode)return ERROR;T-data=ch;/生成根结点名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 20 页 -CreateBiTree(T-lchild);/构造左子树CreateBiTree(T-rchild);/构造右子树 return T;/CreateBiTree Status InOrderTraverse_Thr(BiThrTree T,Status(*Visit)(ElemType)/算法 6.5/T 指向头结点，头结点的左链lchild 指向根结点，头结点的右链lchild 指向/中序遍历的最后一个结点。中序遍历二叉线索链表表示的二叉树T，/对每个数据元素调用函数Visit。BiThrTree p;p=T-lchild;/p 指向根结点while(p!=T)/空树或遍历结束时，p=T while(p-LTag=Link)p=p-lchild;if(!Visit(p-data)return ERROR;/访问其左子树为空的结点while(p-RTag=Thread&p-rchild!=T)p=p-rchild;Visit(p-data);/访问后继结点 p=p-rchild;/p 进至其右子树根 return OK;/InOrderTraverse_Thr 名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 20 页 -Status InOrderThreading(BiThrTree&Thrt,BiThrTree T)/算法 6.6/中序遍历二叉树T，并将其中序线索化，Thrt 指向头结点。if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)exit(OVERFLOW);Thrt-LTag=Link;Thrt-RTag=Thread;/建头结点Thrt-rchild=Thrt;/右指针回指if(!T)Thrt-lchild=Thrt;/若二叉树空，则左指针回指else Thrt-lchild=T;pre=Thrt;InThreading(T);/算法 6.7：中序遍历进行中序线索化pre-rchild=Thrt;pre-RTag=Thread;/最后一个结点线索化Thrt-rchild=pre;return OK;/InOrderThreading void InThreading(BiThrTree p)/算法 6.7 if(p)InThreading(p-lchild);/左子树线索化if(!p-lchild)/建前驱线索 p-LTag=Thread;p-lchild=pre;if(!pre-rchild)/建后继线索 pre-RTag=Thread;pre-rchild=p;pre=p;/保持 pre指向 p 的前驱InThreading(p-rchild);/右子树线索化 /InThreading 名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 20 页 -第9章查找int Search_Seq(SSTable ST,KeyType key)/算法 9.1/在顺序表 ST 中顺序查找其关键字等于key 的数据元素。/若找到，则函数值为该元素在表中的位置，否则为0。int i=0;ST.elem0.key=key;/哨兵 for(i=ST.length;ST.elemi.key!=key;-i);/从后往前找return i;/找不到时，i 为 0 /Search_Seq int Search_Bin(SSTable ST,KeyType key)/算法 9.2/在有序表 ST 中折半查找其关键字等于key 的数据元素。/若找到，则函数值为该元素在表中的位置，否则为0。int low,high,mid;low=1;high=ST.length;/置区间初值while(low data.key)return T;/查找结束else if(LT(key,T-data.key)return SearchBST(T-lchild,key);/在左子树中继续查找else return SearchBST(T-rchild,key);/在右子树中继续查找/SearchBST Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree&p)/算法 9.5(b)/在根指针 T 所指二叉排序树中递归地查找其关键字等于key 的数据元素，/若查找成功，则指针p 指向该数据元素结点，并返回TRUE，/否则指针 p 指向查找路径上访问的最后一个结点并返回FALSE，/指针 f 指向 T 的双亲，其初始调用值为NULL if(!T)p=f;return FALSE;/查找不成功else if(EQ(key,T-data.key)p=T;return TRUE;/查找成功else if(LT(key,T-data.key)return SearchBST(T-lchild,key,T,p);/在左子树中继续查找else return SearchBST(T-rchild,key,T,p);/在右子树中继续查找/SearchBST 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 20 页 -Status InsertBST(BiTree&T,ElemType e)/算法 9.6/当二叉排序树 T 中不存在关键字等于e.key 的数据元素时，/插入 e 并返回 TRUE，否则返回 FALSE BiTree p,s;if(!SearchBST(T,e.key,NULL,p)/查找不成功s=(BiTree)malloc(sizeof(BiTNode);s-data=e;s-lchild=s-rchild=NULL;if(!p)T=s;/插入 s 为新的根结点else if(LT(e.key,p-data.key)p-lchild=s;/插入 s为左孩子else p-rchild=s;/插入 s 为右孩子return TRUE;else return FALSE;/树中已有关键字相同的结点，不再插入/Insert BST Status DeleteBST(BiTree&T,KeyType key)/算法 9.7/若二叉排序树 T 中存在关键字等于key 的数据元素时，/则删除该数据元素结点p，并返回 TRUE；否则返回 FALSE if(!T)return FALSE;/不存在关键字等于key 的数据元素else if(EQ(key,T-data.key)/找到关键字等于 key 的数据元素return Delete(T);else if(LT(key,T-data.key)return DeleteBST(T-lchild,key);else return DeleteBST(T-rchild,key);/DeleteBST 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 20 页 -Status Delete(BiTree&p)/算法 9.8/从二叉排序树中删除结点p，并重接它的左或右子树BiTree q,s;if(!p-rchild)/右子树空则只需重接它的左子树q=p;p=p-lchild;free(q);else if(!p-lchild)/只需重接它的右子树q=p;p=p-rchild;free(q);else /左右子树均不空q=p;s=p-lchild;while(s-rchild)/转左，然后向右到尽头 q=s;s=s-rchild;p-data=s-data;/s 指向被删结点的“后继”if(q!=p)q-rchild=s-lchild;/重接*q 的右子树else q-lchild=s-lchild;/重接*q 的左子树free(s);return TRUE;/Delete 名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 20 页 -第10章排序void InsertSort(SqList&L)/算法 10.1/对顺序表 L 作直接插入排序。int i,j;for(i=2;i=L.length;+i)if(LT(L.ri.key,L.ri-1.key)/时，需将 L.ri 插入有序子表L.r0=L.ri;/复制为哨兵for(j=i-1;LT(L.r0.key,L.rj.key);-j)L.rj+1=L.rj;/记录后移L.rj+1=L.r0;/插入到正确位置 /InsertSort void BInsertSort(SqList&L)/算法 10.2/对顺序表 L 作折半插入排序。int i,j,high,low,m;for(i=2;i=L.length;+i)L.r0=L.ri;/将 L.ri 暂存到 L.r0 low=1;high=i-1;while(low=high+1;-j)L.rj+1=L.rj;/记录后移L.rhigh+1=L.r0;/插入/BInsertSort 名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 20 页 -void ShellInsert(SqList&L,int dk)/算法 10.4/对顺序表 L 作一趟希尔插入排序。本算法对算法10.1 作了以下修改：/1.前后记录位置的增量是dk，而不是 1；/2.r0只是暂存单元，不是哨兵。当j=0 时，插入位置已找到。int i,j;for(i=dk+1;i0&LT(L.r0.key,L.rj.key);j-=dk)L.rj+dk=L.rj;/记录后移，查找插入位置L.rj+dk=L.r0;/插入 /ShellInsert void ShellSort(SqList&L,int dlta,int t)/算法 10.5/按增量序列 dlta0.t-1 对顺序表 L 作希尔排序。for(int k=0;kt;+k)ShellInsert(L,dltak);/一趟增量为 dltak的插入排序/ShellSort int Partition(SqList&L,int low,int high)/算法 10.6(b)/交换顺序表 L 中子序列 L.rlow.high 的记录，使枢轴记录到位，/并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它KeyType pivotkey;L.r0=L.rlow;/用子表的第一个记录作枢轴记录pivotkey=L.rlow.key;/枢轴记录关键字名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 20 页 -while(lowhigh)/从表的两端交替地向中间扫描while(low=pivotkey)-high;L.rlow=L.rhigh;/将比枢轴记录小的记录移到低端while(lowhigh&L.rlow.key=pivotkey)+low;L.rhigh=L.rlow;/将比枢轴记录大的记录移到高端 L.rlow=L.r0;/枢轴记录到位return low;/返回枢轴位置/Partition void QSort(SqList&L,int low,int high)/算法 10.7/对顺序表 L 中的子序列 L.rlow.high 进行快速排序int pivotloc;if(low high)/长度大于 1 pivotloc=Partition(L,low,high);/将 L.rlow.high 一分为二QSort(L,low,pivotloc-1);/对低子表递归排序，pivotloc 是枢轴位置QSort(L,pivotloc+1,high);/对高子表递归排序 /QSort void QuickSort(SqList&L)/算法 10.8/对顺序表 L 进行快速排序QSort(L,1,L.length);/QuickSort 名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 20 页 -void HeapAdjust(HeapType&H,int s,int m)/算法 10.10/已知 H.rs.m中记录的关键字除H.rs.key 之外均满足堆的定义，/本函数调整 H.rs的关键字，使 H.rs.m成为一个大顶堆/（对其中记录的关键字而言）int j;RedType rc;rc=H.rs;for(j=2*s;j=m;j*=2)/沿 key 较大的孩子结点向下筛选if(jm&H.rj.key=H.rj.key)break;/rc 应插入在位置 s上H.rs=H.rj;s=j;H.rs=rc;/插入/HeapAdjust void HeapSort(HeapType&H)/算法 10.11/对顺序表 H 进行堆排序。int i;RedType temp;for(i=H.length/2;i0;-i)/把 H.r1.H.length建成大顶堆HeapAdjust(H,i,H.length);for(i=H.length;i1;-i)temp=H.ri;H.ri=H.r1;H.r1=temp;/将堆顶记录和当前未经排序子序列Hr1.i中/最后一个记录相互交换HeapAdjust(H,1,i-1);/将 H.r1.i-1 重新调整为大顶堆/HeapSort 名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 20 页 -