数据结构常用算法数据结构算法.doc

数据结构常用算法集合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); / 插入 / unionvoid 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); 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); / MergeListStatus 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_SqStatus ListInsert_Sq(SqList &L, int i, ElemType e) / 算法2.4 / 在顺序线性表L的第i个元素之前插入新的元素e， / i的合法值为1iListLength_Sq(L)+1 ElemType *p; if (i < 1 | 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_SqStatus ListDelete_Sq(SqList &L, int i, ElemType &e) / 算法2.5 / 在顺序线性表L中删除第i个元素，并用e返回其值。 / i的合法值为1iListLength_Sq(L)。 ElemType *p, *q; if (i<1 | i>L.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_Sqint 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_Sqvoid 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 <= pb_last) *pc+ = *pb+; / 插入Lb的剩余元素 / MergeListStatus GetElem_L(LinkList &L,int i, ElemType &e) / 算法2.8 / L为带头结点的单链表的头指针。 当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR LinkList p; p = L->next; int j = 1; / 初始化，p指向第一个结点，j为计数器 while (p && j<i) / 顺指针向后查找，直到p指向第i个元素或p为空 p = p->next; +j; if ( !p | j>i ) return ERROR; / 第i个元素不存在 e = p->data; / 取第i个元素 return OK; / GetElem_LStatus ListInsert_L(LinkList &L, int i, ElemType e) / 算法2.9 / 在带头结点的单链线性表L的第i个元素之前插入元素e LinkList p,s; p = L; int j = 0; while (p && j < i-1) / 寻找第i-1个结点 p = p->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_LStatus 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 < i-1) / 寻找第i个结点，并令p指向其前趋 p = p->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_Lvoid 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; i>0; -i) p = (LinkList)malloc(sizeof(LNode); / 生成新结点 p->data = random(200); / 改为一个随机生成的数字(200以内) p->next = L->next; L->next = p; / 插入到表头 / CreateList_Lvoid 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 <= pb->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_Lint LocateElem_SL(SLinkList S, ElemType e) / 算法2.13 / 在静态单链线性表L中查找第1个值为e的元素。 / 若找到，则返回它在L中的位序，否则返回0。 int i; i = S0.cur; / i指示表中第一个结点 while (i && Si.data != e) i = Si.cur; / 在表中顺链查找 return i; / LocateElem_SLvoid InitSpace_SL(SLinkList space) / 算法2.14 / 将一维数组space中各分量链成一个备用链表，space0.cur为头指针， / "0"表示空指针 for (int i=0; i<MAXSIZE-1; +i) spacei.cur = i+1; spaceMAXSIZE-1.cur = 0; / InitSpace_SLint Malloc_SL(SLinkList &space) / 算法2.15 / 若备用空间链表非空，则返回分配的结点下标，否则返回0 int i = space0.cur; if (space0.cur) space0.cur = spacespace0.cur.cur; return i; / Malloc_SLvoid Free_SL(SLinkList &space, int k) / 算法2.16 / 将下标为k的空闲结点回收到备用链表 spacek.cur = space0.cur; space0.cur = k; / Free_SLvoid difference(SLinkList &space, int &S) / 算法2.17 / 依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)(B-A) / 的静态链表, S为头指针。假设备用空间足够大，space0.cur为头指针。 int i, j, k, m, n, p, r; ElemType b; InitSpace_SL(space); / 初始化备用空间 S = Malloc_SL(space); / 生成S的头结点 r = S; / r指向S的当前最后结点 m = random(2,8); / 输入A的元素个数 n = random(2,8); / 输入B的元素个数 printf(" A = ( "); initrandom_c1(); for (j=1; j<=m; +j) / 建立集合A的链表 i = Malloc_SL(space); / 分配结点 /printf("i=%d ",i); spacei.data = random_next_c1(); / 输入A的元素值 printf("%c ", spacei.data); / 输出A的元素 spacer.cur = i; r = i; / 插入到表尾 printf(")n"); spacer.cur = 0; / 尾结点的指针为空 initrandom_c1(); printf(" B = ( "); for (j=1; j<=n; +j) / 依次输入B的元素,若不在当前表中,则插入,否则删除 b = random_next_c1(); / 输入B的元素值 printf("%c ", b); / 输出B的元素 p = S; k = spaceS.cur; / k指向集合A中第一个结点 while (k!=spacer.cur && spacek.data!=b) / 在当前表中查找 p = k; k = spacek.cur; if (k = spacer.cur) / 当前表中不存在该元素,插入在r所指结点之后，且r的位置不变 i = Malloc_SL(space); spacei.data = b; spacei.cur = spacer.cur; spacer.cur = i; else / 该元素已在表中,删除之 spacep.cur = spacek.cur; Free_SL(space, k); if (r = k) r = p; / 若删除的是尾元素，则需修改尾指针 printf(")n"); / differenceDuLinkList 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<i) /顺指针向后查找，直到p指向第i个元素或p为空 p = p->next; +j; if (p=va && j<i) return NULL; / 第i个元素不存在 else return p; / GetElem_LStatus ListInsert_DuL(DuLinkList &L, int i, ElemType e) /算法2.18 / 在带头结点的双链循环线性表L的第i个元素之前插入元素e， / i的合法值为1i表长+1。 DuLinkList p,s; if (!(p = GetElemP_DuL(L, i) / 在L中确定第i个元素的位置指针p return ERROR; / p=NULL, 即第i个元素不存在 if (!(s = (DuLinkList)malloc(sizeof(DuLNode) return ERROR; s->data = 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，否则返回ERROR DuLinkList p; p = va->next; int j = 1; / 初始化，p指向第一个结点，j为计数器 while (p!=va && j<i) /顺指针向后查找，直到p指向第i个元素或p为空 p = p->next; +j; if (p=va | j<i) return NULL; / 第i个元素不存在 else return p; / GetElem_LStatus ListDelete_DuL(DuLinkList &L, int i, ElemType &e) /算法2.19 / 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1i表长 DuLinkList p; if (!(p = GetElemP_DuL(L, i) / 在L中确定第i个元素的位置指针p return ERROR; / p=NULL, 即第i个元素不存在 e = p->data; p->prior->next = p->next; p->next->prior = p->prior; free(p); return OK; / ListDelete_DuLStatus 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; / 结点存储分配失败 InsFirst(h, s); / 对于从第i结点开始的链表，第i-1结点是它的头结点 return OK; / ListInsert_LStatus MergeList_L(NLinkList &La, NLinkList &Lb, NLinkList &Lc, int (*compare)(ElemType, ElemType) / 算法2.21 / 已知单链线性表La和Lb的元素按值非递减排列。 / 归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。 NLink ha, hb; 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中当前结点 pb = NextPos(Lb, hb); while (pa && pb) / La和Lb均非空 a = GetCurElem(pa); / a和b为两表中当前比较元素 b = GetCurElem(pb); if (*compare)(a, b)<=0) / ab DelFirst(ha, q); Append(Lc, q); pa = NextPos(La, pa); else / ab DelFirst(hb, q); Append(Lc, q); pb = NextPos(Lb, pb); / while if (pa) Append(Lc, pa); / 链接La中剩余结点 else Append(Lc, pb); / 链接Lb中剩余结点 FreeNode(ha); FreeNode(hb); / 释放La和Lb的头结点 return OK; / MergeList_LStatus cmp(PElemType a, PElemType b) if (a.expn>=b.expn) return 1; else return 0;void CreatPolyn(PLinkList &P, int m) / 算法2.22 / 输入m项的系数和指数，建立表示一元多项式的有序链表P PLink 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; i<=m; +i) / 依次输入m个非零项 / scanf ("%f,%dn",&e.coef, &e.expn); e.coef = (float)(random(1, 90) + random(10)/10.0); if (random(2) e.coef = -e.coef; e.expn=e.expn+random(1,10); /产生随机的数据，但是expn值是递增的 if (!LocateElem(P, e, q, cmp) / 当前链表中不存在该指数项 if (MakeNode(s,e) InsFirst(q, s); / 生成结点并插入链表 if(q=P.tail) P.tail=s; else i-; / 如果没有产生插入，则将i值减1 / CreatPolynStatus PrintfPoly(PLinkList P) int i=0; PLink q=P.head->next; while (q) if (fabs(q->data.coef) > 0.005) if (i>0) if (q->data.coef>0.005) printf(" + "); else printf(" - "); printf("%.2f", fabs(q->data.coef); else printf("%.2f", q->data.coef); if (q->data.expn>=1) printf("x"); if (q->data.expn>1) printf("%d", q->data.expn); q=q->next; if (+i % 6 = 0) printf("n "); printf("n"); return OK;int Compare(PElemType a, PElemType b) if (a.expn<b.expn) return -1; if (a.expn>b.expn) return 1; return 0;void AddPolyn(PLinkList &Pa, PLinkList &Pb) / 算法2.23 / 多项式加法：Pa = PaPb，利用两个多项式的结点构成"和多项式"。 PLink ha,hb,qa,qb; 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 && qb) / Pa和Pb均非空 a = GetCurElem (qa); / a和b为两表中当前比较元素 b = GetCurElem (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); FreeNode(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 / while if (!Empty(Pb) Append(Pa, qb); / 链接Pb中剩余结点 FreeNode(hb); / 释放Pb的头结点 / AddPolynvoid conversion (int Num) / 算法3.1 / 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 ElemType e; SqStack S; InitStack(S); / 构造空栈 while (Num) Push(S, Num % 8); Num = Num/8; while (!StackEmpty(S) Pop(S,e); printf ("%d", e); printf("n"); / conversionvoid LineEdit() / 算法3.2 /利用字符栈S，从终端接收一行并传送至调用过程的数据区。 char ch,*temp; SqStack S; InitStack(S); /构造空栈S printf("请输入一行(#:退格；:清行):n"); ch = getchar(); /从终端接收第一个字符 while (ch != EOF) /EOF为全文结束符 while (ch != EOF && ch != 'n') switch (ch) case '#': Pop(S, ch); break; / 仅当栈非空时退栈 case '': ClearStack(S); break; / 重置S为空栈 default : Push(S, ch); break; / 有效字符进栈,未考虑栈满情形 ch = getchar(); / 从终端接收下一个字符 temp=S.base; while(temp!=S.top) printf("%c",*temp); +temp; / 将从栈底到栈顶的栈内字符传送至调用过程的数据区； ClearStack(S); / 重置S为空栈 printf("n"); if (ch != EOF) printf("请输入一行(#:退格；:清行):n"); ch = getchar(); DestroyStack(S);Status Pass(MazeType MyMaze, PosType CurPos);void FootPrint(MazeType &MyMaze, PosType CurPos);