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

《数据结构算法整理(C语言版)》由会员分享，可在线阅读，更多相关《数据结构算法整理(C语言版)（47页珍藏版）》请在装配图网上搜索。

1、数据结构算法整理(C语言版)数据结构（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相同的数据元素Lis

2、tInsert(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

3、和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/ 构造一

4、个空的线性表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）+1E

5、lemType *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 = (

6、L.elemi1）； / 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 （i1 | iL.length） return ERROR; / i值不合

7、法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

8、中的位序，否则返回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的元素也按值非递减排列.ElemTy

9、pe *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。listsizesizeof（ElemType)）;if （！Lc。elem）exit(OVERFLOW)； / 存储分配失败pa_last = La.elem+La。length-1；pb_last = Lb。elem+Lb.length1;while （pa = pa_last & pb = pb_last) /

10、 归并if （*pa = pb） *pc+ = pa+；else *pc+ = pb+;while (pa 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

11、 = 0；while (p & j next;+j;if (!p | j i-1) return ERROR； / i小于1或者大于表长s = （LinkList）malloc(sizeof(LNode)）; / 生成新结点sdata = e； snext = pnext； / 插入L中pnext = 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；whi

12、le (pnext & j next) | j i1) return ERROR； / 删除位置不合理q = pnext;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；

13、 i0； -i) p = （LinkList）malloc(sizeof(LNode）); / 生成新结点pdata = random（200)； / 改为一个随机生成的数字(200以内)pnext = Lnext; 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； p

14、b = Lb-next;Lc = pc = La； / 用La的头结点作为Lc的头结点while （pa & pb） if (pa-data = pb-data） pcnext = pa； pc = pa; pa = pa-next；else pc-next = pb; pc = pb; pb = pbnext; pcnext = pa ? pa : pb; / 插入剩余段free(Lb）； / 释放Lb的头结点 / MergeList_L算法2。13int LocateElem_SL（SLinkList S, ElemType e) / 在静态单链线性表L中查找第1个值为e的元素。/ 若找到

15、，则返回它在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

16、 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) /

17、算法2.17/ 依次输入集合A和B的元素，在一维数组space中建立表示集合（A-B）（BA）/ 的静态链表, 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

18、next;int j = 1; / 初始化，p指向第一个结点，j为计数器while （p!=va & jnext;+j；if (p=va & ji) return NULL; / 第i个元素不存在else return p; / GetElem_L算法2.18Status 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

19、return ERROR； / p=NULL, 即第i个元素不存在if （！(s = (DuLinkList）malloc（sizeof(DuLNode)）)）return ERROR；s-data = e；sprior = p-prior；p-priornext = s；s-next = p；p-prior = s；return OK; / ListInsert_DuLDuLinkList GetElemP_DuL（DuLinkList va， int i） / L为带头结点的单链表的头指针。/ 当第i个元素存在时,其值赋给e并返回OK，否则返回ERRORDuLinkList p；p = v

20、a-next；int j = 1; / 初始化，p指向第一个结点，j为计数器while (p!=va & ji） /顺指针向后查找，直到p指向第i个元素或p为空p = pnext；+j；if （p=va | ji) 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

21、中确定第i个元素的位置指针preturn ERROR； / p=NULL, 即第i个元素不存在e = pdata;p-priornext = pnext；p-nextprior = 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

22、, 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

23、;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）next;while （q） if (fabs（q-data.coef） 0。

24、005） if （i0) if （q-data。coef0.005） printf(” + ）;else printf（” ”）;printf（”%.2f”， fabs（qdata。coef)）; else printf（”%.2f”， q-data.coef)；if （q-data。expn=1) printf(”x）；if （qdata.expn1) printf(”d， qdata.expn);q=qnext；if （+i % 6 = 0） printf(n ”)；printf（n);return OK；int Compare（PElemType a， PElemType b） if （

25、a。expn，,，,，,，,，,，,，,，,，,， ,： / 退栈并将运算结果入栈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 ab

26、;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)

27、 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，

28、z）；if （n=1）move（x， 1， z); /将编号为的圆盘从x移到zelse hanoi(n-1，x,z，y）;move（x， n, z); /将编号为n的圆盘从x移到zhanoi(n1， 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”,+Count，n,x，z)；算法 3。7/ 程序中用到的主要变量EventList ev； / 事件表Event en; / 事件LinkQueue q5； / 4个客户队列，q0未用QEl

29、emType customer； / 客户记录int TotalTime, CustomerNum； / 累计客户逗留时间, 客户数int CloseTime;/-算法 3。7-int cmp(Event a， Event b） / 依事件a的发生时刻 事件b的发生时刻分别返回1或0或1if (a。OccurTime b.OccurTime) return +1;return 0；void Random（int durtime， int intertime） / 生成随机数durtime = random(2, 10);intertime = random（10);int Minimum(Li

30、nkQueue q） / 求长度最短队列int minlen = QueueLength(q1)；int i = 1;for （int j=2; j=4； j+）if (QueueLength(qj） minlen) minlen = QueueLength(qj)；i = j;return i;void OpenForDay（) / 初始化操作TotalTime = 0; CustomerNum = 0； / 初始化累计时间和客户数为0InitList（ev）； / 初始化事件链表为空表en.OccurTime = 0; en。NType = 0; / 设定第一个客户到达事件OrderIns

31、ert(ev， en, cmp）; / 按事件发生时刻的次序插入事件表for (int i=1； i=4; +i） InitQueue（qi)； / 置空队列 / OpenForDayvoid CustomerArrived（） / 处理客户到达事件，en.NType=0int durtime， intertime, i， t；+CustomerNum；printf(Customer %d arrived at %d and ”， CustomerNum, en.OccurTime)；Random(durtime, intertime）; / 生成随机数t = en.OccurTime + i

32、ntertime; / 下一客户到达时刻if (tCloseTime) / 银行尚未关门，插入事件表OrderInsert(ev, MakeElem（t， 0）， cmp）;i = Minimum（q）; / 求长度最短队列printf（”enter the Queue %dn”, i）；EnQueue（qi, MakeQElem（en.OccurTime， durtime）)；if (QueueLength(qi) = 1) /设定第i队列的一个离开事件并插入事件表OrderInsert(ev， MakeElem（en。OccurTime+durtime, i), cmp); / CustomerArrivedvoid CustomerDeparture(） / 处理客户离开事件，en.NType0printf(Customer departure at dn, en.OccurTime)；int i = en.NType； DeQueue(qi, customer)； /删除第i队列的排头客户TotalTime += en.OccurTimecustomer.ArrivalTime; / 累计客户逗留时间if (!QueueEmpty(qi)） / 设定第i队列的一个离开事件并插入事件表GetHead (qi， customer)；OrderInsert(e