《数据结构算法整理(c语言版)》由会员分享，可在线阅读，更多相关《数据结构算法整理(c语言版)（49页珍藏版）》请在金锄头文库上搜索。
1、1数据结构（数据结构（C 语言版）语言版）第二章第二章 线性表线性表算法 2.1void Union(List 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 = (ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof (
2、ElemType);if (!newbase) return ERROR; / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ElemType *q = / q 为插入位置 for (p = p=q; -p) *(p+1) = *p;/ 插入位置及之后的元素右移 *q = e; / 插入 e +L.length; / 表长增 1 return OK; / ListInsert_Sq算法 2.5Status ListDelete_Sq(SqList if (iL.length) return ERROR;
3、 / i 值不合法 p = / p 为被删除元素的位置 e = *p; / 被删除元素的值赋给 e q = L.elem+L.length-1; / 表尾元素的位置 for (+p; pnext;int j = 1; / 初始化，p 指向第一个结点，j 为计数器 while (p +j; if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; / 取第 i 个元素 return OK; / GetElem_L算法 2.9Status ListInsert_L(LinkList p = L; int j = 0;while (p +j; if
4、(!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算法 2.10Status ListDelete_L(LinkList p = L;5int j = 0;while (p-next +j; if (!(p-next) | j i-1) return ERROR; / 删除位置不合理 q = p-next;p-next =
5、 q-next; / 删除并释放结点 e = q-data; free(q); return OK; / ListDelete_L算法 2.11void CreateList_L(LinkList 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-nex
6、t = p; / 插入到表头 / CreateList_L算法 2.12void MergeList_L(LinkList pa = La-next; pb = Lb-next;Lc = pc = La; / 用 La 的头结点作为 Lc 的头结点 while (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(SLinkL
7、ist S, ElemType e) / 在静态单链线性表 L 中查找第 1 个值为 e 的元素。 / 若找到，则返回它在 L 中的位序，否则返回 0。 int i;i = S0.cur; / i 指示表中第一个结点 while (i / 在表中顺链查找 return i; / LocateElem_SL算法 2.14void InitSpace_SL(SLinkList space) / 将一维数组 space 中各分量链成一个备用链表，space0.cur 为头指针， / “0“表示空指针 for (int i=0; inext;int j = 1; / 初始化，p 指向第一个结点，j 为
8、计数器 while (p!=va +j; if (p=va s-prior = p-prior; p-prior-next = s; s-next = p; p-prior = s; return OK; / ListInsert_DuL DuLinkList GetElemP_DuL(DuLinkList va, int i) / L 为带头结点的单链表的头指针。 / 当第 i 个元素存在时，其值赋给 e 并返回 OK，否则返回 ERROR DuLinkList p; p = va-next;int j = 1; / 初始化，p 指向第一个结点，j 为计数器 while (p!=va +j;
9、 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 个元素之前插入元素 e NLink h,s; if (!LocatePos(L, i-1, h)return ERROR; / i 值不合法 if (!MakeNode(s, e)return ERROR; / 结
10、点存储分配失败 InsFirst(h, s); / 对于从第 i 结点开始的链表，第 i-1 结点是它的头结点 return OK; / ListInsert_LStatus MergeList_L(NLinkList Position pa, pb, q; ElemType a, b;if (!InitList(Lc) return ERROR; / 存储空间分配失败 ha = GetHead(La); / ha 和 hb 分别指向 La 和 Lb 的头结点 hb = GetHead(Lb);pa = NextPos(La, ha); / pa 和 pb 分别指向 La 和 Lb 中当前结点
11、 pb = NextPos(Lb, hb);while (pa / a 和 b 为两表中当前比较元素 b = GetCurElem(pb);if (*compare)(a, b)=b.expn) return 1; else return 0; 算法 2. 22void CreatPolyn(PLinkList 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
12、.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
13、(PElemType a, PElemType b) if (a.expnb.expn) return 1; return 0; 算法 2. 23void AddPolyn(PLinkList PElemType a, b, temp; float sum;ha = GetHead(Pa); / ha 和 hb 分别指向 Pa 和 Pb 的头结点 hb = GetHead(Pb);qa = NextPos(Pa,ha); / qa 和 qb 分别指向 La 和 Lb 中当前结点 qb = NextPos(Pb,hb);while (qa / a 和 b 为两表中当前比较元素 b = GetCu
14、rElem (qb); switch (Compare(a,b) case -1: / 多项式 PA 中当前结点的指数值小 ha = qa; qa = NextPos (Pa, qa); break;case 0: / 两者的指数值相等 sum = a.coef + b.coef ;if (sum != 0.0) / 修改多项式 PA 中当前结点的系数值 temp.coef=sum; temp.expn=a.expn; SetCurElem(qa, temp) ; ha = qa; else / 删除多项式 PA 中当前结点 DelFirst(ha, qa);12FreeNode(qa); DelFirst(hb, qb); FreeNode(qb); qb = NextPos(Pb, hb); qa = NextPos(Pa, ha); break;case 1: / 多项式 PB 中当前结点的指数值小 DelFirst(hb, qb); InsFirst(ha, qb); qb = NextPos(Pb, hb); ha = NextPos(Pa, ha); break; / switch / whileif (!Empty(Pb) Append(Pa, qb); / 链接 Pb 中剩余结点 FreeNode(h
