《数据结构源代码(清华大学+严蔚敏).pdf》由会员分享，可在线阅读，更多相关《数据结构源代码(清华大学+严蔚敏).pdf（23页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、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);/插入 /union void Me
2、rgeList(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)ListIns
3、ert(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 Status InitList_Sq(SqList&L)/算法 2.3 /构造一个空的线性表 L。L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)return OK;/存储分配失败
4、L.length=0;/空表长度为 0 L.listsize=LIST_INIT_SIZE;/初始存储容量 return OK;/InitList_Sq Status ListInsert_Sq(SqList&L,int i,ElemType e)/算法 2.4 /在顺序线性表 L 的第 i 个元素之前插入新的元素 e，/i 的合法值为 1iListLength_Sq(L)+1 ElemType*p;if(i L.length+1)return ERROR;/i 值不合法 if(L.length=L.listsize)/当前存储空间已满，增加容量 ElemType*newbase=(ElemT
5、ype*)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_Sq Status
6、 ListDelete_Sq(SqList&L,int i,ElemType&e)/算法 2.5 /在顺序线性表 L 中删除第 i 个元素，并用 e 返回其值。/i 的合法值为 1iListLength_Sq(L)。ElemType*p,*q;if(iL.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;/Lis
7、tDelete_Sq int 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
8、;/LocateElem_Sq void 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);i
9、f(!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
10、;/取第 i 个元素 return OK;/GetElem_L Status ListInsert_L(LinkList&L,int i,ElemType e)/算法 2.9 /在带头结点的单链线性表 L 的第 i 个元素之前插入元素 e LinkList 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;/LinstI
11、nsert_L Status 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 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 void CreateList_L(LinkList&L,int n)/算
12、法 2.11/逆位序输入（随机产生）n 个元素的值，/建立带表头结点的单链线性表 L LinkList 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 void MergeList_L(LinkList&La,LinkList&Lb,Li
13、nkList&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 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 的头结点 /MergeLis
14、t_L int 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_SL void InitSpace_SL(SLinkList space)/算法 2.14/将一维数组 space 中各分量链成一个备用链表，/space0.cur 为头指针，/0表示空指针 for(int i=
15、0;iMAXSIZE-1;+i)spacei.cur=i+1;spaceMAXSIZE-1.cur=0;/InitSpace_SL int Malloc_SL(SLinkList&space)/算法 2.15 /若备用空间链表非空，则返回分配的结点下标，否则返回 0 int i=space0.cur;if(space0.cur)space0.cur=spacespace0.cur.cur;return i;/Malloc_SL void Free_SL(SLinkList&space,int k)/算法 2.16 /将下标为 k 的空闲结点回收到备用链表 spacek.cur=space0.c
16、ur;space0.cur=k;/Free_SL void 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=ran
17、dom(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;/
18、初始化，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_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&jn
19、ext;+j;if(p=va|jdata;p-prior-next=p-next;p-next-prior=p-prior;free(p);return OK;/ListDelete_DuL Status 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
20、 结点开始的链表，第 i-1 结点是它的头结点 return OK;/ListInsert_L Status 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=G
21、etHead(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;void CreatPolyn(PLinkList&P,int m)/算法 2.22 /输入 m 项的系数和指数，建
22、立表示一元多项式的有序链表 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;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)
23、;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;void AddPolyn(PLinkList&Pa,PLinkList&Pb)/算法 2.23/多项式加法：Pa=PaPb，利用两个多项式的结点构成和多项式。PLink ha,hb,qa,qb;PElemType a,b,temp;float sum;ha=GetHead(Pa
24、);/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
25、!=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);br
26、eak;/switch /while if(!Empty(Pb)Append(Pa,qb);/链接 Pb 中剩余结点 FreeNode(hb);/释放 Pb 的头结点 /AddPolyn void 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 void
27、 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;/有效字符进栈,
28、未考虑栈满情形 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
29、);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；否则返回 FALSE Stack S;PosType curpos;int curstep;SElemType e;InitStack(S);curpos=start
30、;/设定当前位置为入口位置 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
31、(S,e);while(e.di=4&!StackEmpty(S)MarkPrint(maze,e.seat);Pop(S,e);/留下不能通过的标记，并退回一步 /while if(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);float EvaluateExpression(char*MyExpression)/算法 3.4
32、/算术表达式求值的算符优先算法。/设 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
33、(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 /while return GetTop(OPND);/EvaluateExpression float Operate
34、(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
35、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);void hanoi(int n,char x,char y,char z)/算法 3.5 /*将塔座 x 上按直径由小到大且至上而下编号为 1 至 n 的 n 个圆盘按规则搬到*/塔座 z 上，y 可用作辅助塔座。/搬动操作 move(x,n,z
36、)可定义为：/(c 是初值为 0 的全局变量，对搬动计数)/printf(%i.Move disk%i from%c to%cn,+c,n,x,z);if(n=1)move(x,1,z);/将编号为的圆盘从 x 移到 z else hanoi(n-1,x,z,y);move(x,n,z);/将编号为 n 的圆盘从 x 移到 z hanoi(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,+Count,n,x,z);/程序中用到的主
37、要变量 EventList ev;/事件表 Event en;/事件 LinkQueue q5;/4 个客户队列,q0未用 QElemType customer;/客户记录 int TotalTime,CustomerNum;/累计客户逗留时间,客户数 int CloseTime;/-算法 3.7-int cmp(Event a,Event b)/*依事件 a 的发生时刻 事件 b 的发生时刻分别返回-1 或 0 或 1*/if(a.OccurTime b.OccurTime)return+1;return 0;void Random(int&durtime,int&intertime)/生成
38、随机数 durtime=random(2,10);intertime=random(10);int Minimum(LinkQueue 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;/初始化累计时间和客户数为 0 InitList(ev);/初始化事件链表为空表 en.OccurTime=0;
39、en.NType=0;/设定第一个客户到达事件 OrderInsert(ev,en,cmp);/按事件发生时刻的次序插入事件表 for(int i=1;i=4;+i)InitQueue(qi);/置空队列 /OpenForDay void CustomerArrived()/处理客户到达事件，en.NType=0 int durtime,intertime,i,t;+CustomerNum;printf(Customer%d arrived at%d and,CustomerNum,en.OccurTime);Random(durtime,intertime);/生成随机数 t=en.Occu
40、rTime+intertime;/下一客户到达时刻 if(t0 printf(Customer departure at%dn,en.OccurTime);int i=en.NType;DeQueue(qi,customer);/删除第 i 队列的排头客户 TotalTime+=en.OccurTime-customer.ArrivalTime;/累计客户逗留时间 if(!QueueEmpty(qi)/设定第 i 队列的一个离开事件并插入事件表 GetHead(qi,customer);OrderInsert(ev,MakeElem(en.OccurTime+customer.Duration
41、,i),cmp);/CustomerDeparture void Bank_Simulation(int closetime)int i=0;BLink p;CloseTime=closetime;printf(Bank_Simulation(%d)-银行业务模拟n,closetime);OpenForDay();/初始化 while(!ListEmpty(ev)printList(ev);if(DelFirst(GetHead(ev),p)en=GetCurElem(p);if(en.NType=0)CustomerArrived();/处理客户到达事件 else CustomerDepar
42、ture();/处理客户离开事件 if(+i%9=0)printf(n-按任意键，继续-);getch();printf(nn);/计算并输出平均逗留时间 printf(nThe Average Time is%fn,(float)TotalTime/CustomerNum);/Bank_Simulation Status TransposeSMatrix(TSMatrix M,TSMatrix&T)/算法 5.1 /采用三元组顺序表存储表示，求稀疏矩阵 M 的转置矩阵 T int p,q,col;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(co
43、l=1;col=M.nu;+col)for(p=1;p=M.tu;+p)if(M.datap.j=col)T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+q;return OK;/TransposeSMatrix Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T)/算法 5.2 /采用三元组顺序表存储表示，求稀疏矩阵 M 的转置矩阵 T int col,t,p,q;int num20,cpot20;T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu
44、)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)/求 M 中每一列所含非零元的个数 +numM.datat.j;cpot1=1;/求 M 中每一列的第一个非零元在 b.data 中的序号 for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p=M.tu;+p)col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol;/for /if return
45、OK;/FastTransposeSMatrix Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&Q)/算法 5.3 /求矩阵乘积 Q=M?N，采用行逻辑链接存储表示。int arow,brow,p,q,t,ctemp30,l,ccol,tp;if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;/Q 初始化 if(M.tu*N.tu!=0)/Q 是非零矩阵 for(arow=1;arow=M.mu;+arow)/处理 M 的每一行 for(l=1;l=M.nu;+l)ctempl=
46、0;/当前行各元素累加器清零 Q.rposarow=Q.tu+1;if(arowM.mu)tp=M.rposarow+1;else tp=M.tu+1;for(p=M.rposarow;ptp;+p)/对当前行中每一个非零元 brow=M.datap.j;/找到对应元在 N 中的行号 if(brow N.mu)t=N.rposbrow+1;else t=N.tu+1;for(q=N.rposbrow;q t;+q)ccol=N.dataq.j;/乘积元素在 Q 中列号 ctempccol+=M.datap.e*N.dataq.e;/for q /求得 Q 中第 crow(=arow)行的非零元
47、 for(ccol=1;ccol MAXSIZE)return ERROR;Q.dataQ.tu.i=arow;Q.dataQ.tu.j=ccol;Q.dataQ.tu.e=ctempccol;/if /for arow /if return OK;/MultSMatrix Status CreateSMatrix_OL(CrossList&M)/算法 5.4 /创建稀疏矩阵 M。采用十字链表存储表示。/if(M)free(M);/scanf(&m,&n,&t);/输入 M 的行数、列数和非零元个数 OLNode*p,*q;int i,j,e;int m=random(4,6),n=rando
48、m(4,6),t=random(4,5);M.mu=m;M.nu=n;M.tu=t;if(!(M.rhead=(OLink*)malloc(m+1)*sizeof(OLink)return ERROR;if(!(M.chead=(OLink*)malloc(n+1)*sizeof(OLink)return ERROR;for(int a=1;a=m;a+)/初始化行列头指针向量；各行列链表为空链表 M.rheada=NULL;for(int b=1;b=n;b+)M.cheadb=NULL;for(int c=1;ci=i;p-j=j;p-e=e;p-down=NULL;p-right=NUL
49、L;/新结点 if(M.rheadi=NULL|M.rheadi-j j)p-right=M.rheadi;M.rheadi=p;else /寻查在行表中的插入位置 for(q=M.rheadi;(q-right)&(q-right-jright);p-right=q-right;q-right=p;/完成行插入 if(M.cheadj=NULL|M.cheadj-i i)p-down=M.cheadj;M.cheadj=p;else /寻查在列表中的插入位置 for(q=M.cheadj;(q-down)&q-down-i down);p-down=q-down;q-down=p;/完成列插
50、入 /for return OK;/CreateSMatrix_OL int GListDepth(GList L)/算法 5.5 /采用头尾链表存储结构,求广义表 L 的深度。int max,dep;GList pp;if(!L)return 1;/空表深度为 1 if(L-tag=ATOM)return 0;/原子深度为 0 for(max=0,pp=L;pp;pp=pp-ptr.tp)dep=GListDepth(pp-ptr.hp);/求以 pp-ptr.hp 为头指针的子表深度 if(dep max)max=dep;return max+1;/非空表的深度是各子表的深度的最大值加 1