《2022年数据结构教材代码》由会员分享，可在线阅读，更多相关《2022年数据结构教材代码（20页珍藏版）》请在金锄头文库上搜索。
1、第 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,
2、 +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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - -
3、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 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); w
4、hile (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; / InitLi
5、st_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
6、 = 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
7、+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 的合法值为 1iL
8、istLength_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 (*compar
9、e)(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 名师资料总结 - - -精品资料欢迎下载
10、- - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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
11、.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
12、) *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;
13、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 页 - - - - - -
14、 - - - 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
15、 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; /
16、插入到表头 / 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;
17、 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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
18、 - - - - 第 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)
19、; / 向左走到尽头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 (
20、*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
21、; / 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; / 生成根结点名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理
22、- - - - - - - 第 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，/ 对每个数据元素调用函数Vi
23、sit。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 名师资料总结 - - -精品资料
24、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 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; / 建头结点Thr
25、t-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
26、); / 左子树线索化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 页 - - - - -
27、- - - - 第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 中
28、折半查找其关键字等于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, K
29、eyType 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) ret
30、urn 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.ke
31、y 的数据元素时，/ 插入 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 retur
32、n 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 D
33、eleteBST(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
34、-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;
35、/ 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.r
36、0.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; / 插入
37、 / 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
38、.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.
39、6(b) / 交换顺序表 L 中子序列 L.rlow.high 的记录，使枢轴记录到位，/ 并返回其所在位置，此时，在它之前（后）的记录均不大（小）于它KeyType pivotkey; L.r0 = L.rlow; / 用子表的第一个记录作枢轴记录pivotkey = L.rlow.key; / 枢轴记录关键字名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - while (lowhigh) / 从表的两端交替地向中间扫描wh
40、ile (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
41、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 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -
42、- - - - - - - 名师精心整理 - - - - - - - 第 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.r
43、j.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 页 - - - - - - - - -
