数据结构算法整理(C语言版).doc

数据结构（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=Lb_len; i+) GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给eif (!LocateElem(La, e, equal) / La中不存在和e相同的数据元素ListInsert(La, +La_len, e); / 插入 / union算法2.2void 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); / MergeList算法2.3Status InitList_Sq(SqList &L) / 算法2.3/ 构造一个空的线性表L。L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if (!L.elem) return OK; / 存储分配失败L.length = 0; / 空表长度为0L.listsize = LIST_INIT_SIZE; / 初始存储容量return OK; / InitList_Sq算法2.4Status ListInsert_Sq(SqList &L, int i, ElemType e) / 算法2.4/ 在顺序线性表L的第i个元素之前插入新的元素e，/ i的合法值为1iListLength_Sq(L)+1ElemType *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; / 表长增1return OK; / ListInsert_Sq算法2.5Status ListDelete_Sq(SqList &L, int i, ElemType &e) / 在顺序线性表L中删除第i个元素，并用e返回其值。/ i的合法值为1iListLength_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; p=q; +p) *(p-1) = *p; / 被删除元素之后的元素左移-L.length; / 表长减1return OK; / ListDelete_Sq算法2.6int LocateElem_Sq(SqList L, ElemType e,Status (*compare)(ElemType, ElemType) / 在顺序线性表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算法2.7void MergeList_Sq(SqList La, SqList Lb, SqList &Lc) / 已知顺序线性表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算法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 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;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算法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) 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-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算法2.13int LocateElem_SL(SLinkList S, ElemType e) / 在静态单链线性表L中查找第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; iMAXSIZE-1; +i)spacei.cur = i+1;spaceMAXSIZE-1.cur = 0; / InitSpace_SL算法2.15int Malloc_SL(SLinkList &space) / 若备用空间链表非空，则返回分配的结点下标，否则返回0int i = space0.cur;if (space0.cur) space0.cur = spacespace0.cur.cur;return i; / Malloc_SL算法2.16void Free_SL(SLinkList &space, int k) / 将下标为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; jnext;int j = 1; / 初始化，p指向第一个结点，j为计数器while (p!=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 & jnext;+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; / 结点存储分配失败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 (!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)=b.expn) return 1;else return 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);if (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) if (a.expnb.expn) return 1;return 0;算法2. 23void 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 / whileif (!Empty(Pb) Append(Pa, qb); / 链接Pb中剩余结点FreeNode(hb); / 释放Pb的头结点 / AddPolyn第三章 栈和队列算法3. 1void 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); / conversion算法3.2void LineEdit() ./利用字符栈S，从终端接收一行并传送至调用过程的数据区。char ch,*temp;SqStack S;InitStack(S); /构造空栈Sprintf(请输入一行(#:退格；:清行):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);算法3.3Status Pass(MazeType MyMaze, PosType CurPos);void FootPrint(MazeType &MyMaze, PosType CurPos);void MarkPrint(MazeType &MyMaze, PosType CurPos);PosType NextPos(PosType CurPos, int Dir);Status MazePath(MazeType &maze, PosType start, PosType end) / 算法3.3/ 若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中/ （从栈底到栈顶），并返回TRUE；否则返回FALSEStack S;PosType curpos;int curstep;SElemType e;InitStack(S);curpos = start; / 设定当前位置为入口位置curstep = 1; / 探索第一步do if (Pass(maze,curpos) / 当前位置可通过，即是未曾走到过的通道块FootPrint(maze,curpos); / 留下足迹e.di =1;e.ord = curstep;e.seat= curpos;Push(S,e); / 加入路径if (curpos.r = end.r & curpos.c=end.c)return (TRUE); / 到达终点（出口）curpos = NextPos(curpos, 1); / 下一位置是当前位置的东邻curstep+; / 探索下一步 else / 当前位置不能通过if (!StackEmpty(S) Pop(S,e);while (e.di=4 & !StackEmpty(S) MarkPrint(maze,e.seat);Pop(S,e); / 留下不能通过的标记，并退回一步 / whileif (e.di, , ,=;float Operate(float a, unsigned char theta, float b);char OPSETOPSETSIZE=+ , - , * , / ,( , ) , #;Status In(char Test,char* TestOp);char precede(char Aop, char Bop);算法3.4float EvaluateExpression(char* MyExpression) / 算法3.4/ 算术表达式求值的算符优先算法。/ 设OPTR和OPND分别为运算符栈和运算数栈，OP为运算符集合。StackChar OPTR; / 运算符栈，字符元素StackFloat OPND; / 运算数栈，实数元素char TempData20;float Data,a,b;char theta,*c,x,Dr2;InitStack (OPTR);Push (OPTR, #);InitStack (OPND);c = MyExpression;strcpy(TempData,0);while (*c!= # | GetTop(OPTR)!= #) if (!In(*c, OPSET) Dr0=*c;Dr1=0;strcat(TempData,Dr);c+;if(In(*c,OPSET) Data=(float)atof(TempData);Push(OPND, Data);strcpy(TempData,0); else / 不是运算符则进栈switch (precede(GetTop(OPTR), *c) case : / 退栈并将运算结果入栈Pop(OPTR, theta);Pop(OPND, b);Pop(OPND, a);Push(OPND, Operate(a, theta, b);break; / switch / whilereturn GetTop(OPND); / EvaluateExpressionfloat Operate(float a,unsigned char theta, float b) switch(theta) case +: return a+b;case -: return a-b;case *: return a*b;case /: return a/b;default : return 0;Status In(char Test,char* TestOp) bool Find=false;for (int i=0; i OPSETSIZE; i+) if (Test = TestOpi) Find= true;return Find;int ReturnOpOrd(char op,char* TestOp) int i;for(i=0; i OPSETSIZE; i+) if (op = TestOpi) return i;return 0;char precede(char Aop, char Bop) return PriorReturnOpOrd(Aop,OPSET)ReturnOpOrd(Bop,OPSET);int Count=0;void move(char x, int n, char z);算法3.5void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n的n个圆盘按规则搬到/ 塔座z上，y可用作辅助塔座。/ 搬动操作 move (x, n, z) 可定义为：/ (c是初值为0的全局变量，对搬动计数)/ printf(%i. Move disk %i from %c to %cn, +c, n, x, z);if (n=1)move(x, 1, z); /将编号为的圆盘从x移到zelse hanoi(n-1,x,z,y);move(x, n, z); /将编号为n的圆盘从x移到zhanoi(n-1, y, x, z); /将y上编号为至n-1的圆盘移到z,x作辅助塔void move(char x, int n, char z) printf( %2i. Move disk %i from %c to %cn,+C