《数据结构算法整理(C语言版)》由会员分享，可在线阅读，更多相关《数据结构算法整理(C语言版)（49页珍藏版）》请在金锄头文库上搜索。
1、1数据结构（C 语言版）第二章 线性表算法 2.1void 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 L.length+1) return ERROR; / i 值不合法if (L.length = L.listsize) / 当前存储空间已满，增加容量ElemType *newbase = (Elem
2、Type *)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; / 表长增 1ret
3、urn OK; / ListInsert_Sq算法 2.5Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值。3/ i 的合法值为 1i ListLength_Sq(L) 。ElemType *p, *q;if (iL.length) return ERROR; / i 值不合法p = &(L.elemi-1); / p 为被删除元素的位置e = *p; / 被删除元素的值赋给 eq = L.elem+L.length-1; / 表尾元素的位置for (+p; pnext;int
4、 j = 1; / 初始化，p 指向第一个结点，j 为计数器while (p & jnext; +j;if ( !p | ji ) return ERROR; / 第 i 个元素不存在e = p-data; / 取第 i 个元素return OK; / GetElem_L算法 2.9Status ListInsert_L(LinkList &L, int i, ElemType e) / / 在带头结点的单链线性表 L 的第 i个元素之前插入元素 eLinkList p,s;p = L;int j = 0;while (p & j next;+j;if (!p | j i-1) return
5、ERROR; / i 小于 1 或者大于表长s = (LinkList)malloc(sizeof(LNode); / 生成新结点s-data = e; s-next = p-next; / 插入 L 中p-next = s;return OK; / LinstInsert_L算法 2.10Status ListDelete_L(LinkList &L, int i, ElemType &e) / 在带头结点的单链线性表 L 中，删除第 i 个元素，并由 e 返回其值LinkList p,q;p = L;5int j = 0;while (p-next & j next;+j;if (!(p-
6、next) | j i-1) return ERROR; / 删除位置不合理q = p-next;p-next = q-next; / 删除并释放结点e = q-data;free(q);return OK; / ListDelete_L算法 2.11void CreateList_L(LinkList &L, int n) / 逆位序输入（随机产生）n 个元素的值，建立带表头结点的单链线性表 LLinkList p;int i;L = (LinkList)malloc(sizeof(LNode);L-next = NULL; / 先建立一个带头结点的单链表for (i=n; i0; -i)
7、p = (LinkList)malloc(sizeof(LNode); / 生成新结点p-data = random(200); / 改为一个随机生成的数字(200 以内)p-next = L-next; L-next = p; / 插入到表头 / CreateList_L算法 2.12void MergeList_L(LinkList &La, LinkList &Lb, LinkList &Lc) / 已知单链线性表 La 和 Lb 的元素按值非递减排列。/ 归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按值非递减排列。LinkList pa, pb, pc;pa = La
8、-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 的头结点6 / MergeList_L算法 2.13int LocateElem_SL(SLinkList S, ElemType e) / 在静态单链线性表 L 中查
9、找第 1 个值为 e 的元素。/ 若找到，则返回它在 L 中的位序，否则返回 0。int i;i = S0.cur; / i 指示表中第一个结点while (i & Si.data != e) i = Si.cur; / 在表中顺链查找return i; / LocateElem_SL算法 2.14void InitSpace_SL(SLinkList space) / 将一维数组 space 中各分量链成一个备用链表， space0.cur 为头指针，/ 0表示空指针for (int i=0; inext;int j = 1; / 初始化， p 指向第一个结点，j 为计数器while (p!
10、=va & jnext;+j;if (p=va & jdata = e;s-prior = p-prior;p-prior-next = s;s-next = p;p-prior = s;return OK; / ListInsert_DuLDuLinkList GetElemP_DuL(DuLinkList va, int i) / L 为带头结点的单链表的头指针。/ 当第 i 个元素存在时，其值赋给 e 并返回 OK，否则返回 ERRORDuLinkList p;p = va-next;int j = 1; / 初始化， p 指向第一个结点，j 为计数器while (p!=va & jne
11、xt;+j;if (p=va | jdata;p-prior-next = p-next;p-next-prior = p-prior;free(p);return OK; / ListDelete_DuL算法 2. 20Status ListInsert_L(NLinkList L, int i, ElemType e) / 算法 2.20/ 在带头结点的单链线性表 L 的第 i 个元素之前插入元素 eNLink h,s;if (!LocatePos(L, i-1, h)return ERROR; / i 值不合法if (!MakeNode(s, e)return ERROR; / 结点存储
12、分配失败InsFirst(h, s); / 对于从第 i 结点开始的链表，第 i-1 结点是它的头结点return OK; / ListInsert_LStatus MergeList_L(NLinkList &La, NLinkList &Lb, NLinkList &Lc,int (*compare)(ElemType, ElemType) / 已知单链线性表 La 和 Lb 的元素按值非递减排列。/ 归并 La 和 Lb 得到新的单链线性表 Lc，Lc 的元素也按值非递减排列。NLink ha, hb;Position pa, pb, q;ElemType a, b;if (!InitL
13、ist(Lc) return ERROR; / 存储空间分配失败ha = GetHead(La); / ha 和 hb 分别指向 La 和 Lb 的头结点hb = GetHead(Lb);pa = NextPos(La, ha); / pa 和 pb 分别指向 La 和 Lb 中当前结点pb = NextPos(Lb, hb);while (pa & pb) / La 和 Lb 均非空a = GetCurElem(pa); / a 和 b 为两表中当前比较元素b = GetCurElem(pb);if (*compare)(a, b)=b.expn) return 1;else return
14、0;算法 2. 22void CreatPolyn(PLinkList &P, int m) / 算法 2.22/ 输入 m 项的系数和指数，建立表示一元多项式的有序链表 PPLink h, q, s;PElemType e;int i;InitList(P); h = GetHead(P);e.coef = 0.0; e.expn = -1;SetCurElem(h, e); / 设置头结点for (i=1; inext;while (q) if (fabs(q-data.coef) 0.005) if (i0) if (q-data.coef0.005) printf( + );else printf( - );printf(%.2f, fabs(q-data.coef); else printf(%.2f, q-data.coef);if (q-data.expn=1) printf(x);11if (q-data.expn1) printf(%d, q-data.expn);q=q-next;if (+i % 6 = 0) printf(n );printf(n);return OK;int Compare(PElemType a, PElemType b)
