嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)所有算法代碼

1、嚴(yán)蔚敏版數(shù)據(jù)結(jié)構(gòu)所有算法代碼 線性數(shù)據(jù)結(jié)構(gòu)2013年9月/線性表、鏈表/棧、隊列/數(shù)組、廣義表/用 線性表typedef structchar name20;/ 注意如果應(yīng)用指針的形式/在初始化每個結(jié)點時一定要先為結(jié)點中的每個變量開辟內(nèi)存空間char sex;char addr100;unsigned int age;char phonenum20;node;/結(jié)點描述typedef structnode *p;int length;/ 當(dāng)前順序表長度int listsize;/當(dāng)前分配的線性表長度list;/ 線性表描述list L;/定義一個線性表int initlist(list &l)

2、/構(gòu)造一個空的線性表l.p=(node*)malloc(LIST_INIT_SIZE*sizeof(node);if(!(l.p)一 一exit；l.length=0;l.listsize=LIST_INIT_SIZE;return true;void destroylist(list &l)/銷毀線性表操作if(l.p!=NULL)free(l.p);printf(銷毀成功!n);elseprintf（線性表不存在！ n）;int clearlist(list &l)/將線性表置空操作if(l.p=NULL)printf(線性表不存在！ n);return false;elsefree(l.

3、p);l.p=(node*)malloc(l.listsize*sizeof(node);l.length=0;return true;int listempty(list &l)/判斷線性表是否為空表if(l.p=NULL)return true;elsereturn false;int getelem(list &l,int i,node &e)/if(l.p=NULL)return false;elsee=l.pi-1;return true;int priorelem(list &l,int i,node &pre_e)/if(i=0|l.p=NULL)return false;els

4、epre_e=l.pi-1;return true;int nextelem(list &l,int i,node &next_e)/if(i=l.length|l.p=NULL)return false;用e返回表中第i個數(shù)據(jù)元素得到第i個元素的前驅(qū)元素得到表中第i個元素的后繼元素elsenext_e=l.pi+1;return true;int insertlist(list &l,int i,node &e)/將元素 e 插入到表 l 中第 i 個元素的后面node *q,*k;if(il.length+1)return false;if(l.length=l.listsize)l.p=

5、(node*)realloc(l.p,(l.listsize+LISTINCREMENT)*sizeof(node);if(!l.p)exit(1);l.listsize+=LISTINCREMENT;k=&l.pi-1;for(q=&l.pl.length-1;qk;q-)*(q+1)=*q;*k=e;l.length+;return true;int deletelist(list &l,int i,node &e)/刪除表中第i個元素并用e返回其node *q;int j=i-1;if(il.length)return false;e=l.pi-1;for(q=&l.pi-1;jl.le

6、ngth-1;j+)*q=*(+q);l.length-;return true;void mergerlist(list la,list lb,list &lc)/歸并兩個按非遞減排列的線性表int la_len,lb_len,i=1,j=1,k=0;node ai,bj;la_len=la.length;3lb_len=lb.length;while(i=la_len&j=lb_len)一一getelem(la,i,ai);getelem(lb,j,bj);if(ai.a=bj.a)insertlist(lc,+k,ai); i+；elseinsertlist(lc,+k,bj); j+；

7、while(i=la_len).getelem(la,i,ai);insertlist(lc,+k,ai)； i+；while(j=lb_len).getelem(lb,j,bj);insertlist(lc,+k,bj)；j+；int ListAscendingOrder(list &l)/按結(jié)點中某一元素的比較升序排列線性表中的結(jié)點node e;int i,j;if(l.p=NULL|l.length=1)return ERROR;for(i=0;il.length-1;i+)for(j=i+1;j=l.pj.num) e=l.pi;l.pi=l.pj;l.pj=e; return OK;

8、/省略降序排列void MergerList(list la,list lb,list &lc)將兩線性表升序排列后再歸并node *q,*k,e1;int i=0,j=0,m=0,n;ListAscendingOrder(la);ListAscendingOrder(lb);printf( 表a升序排列后為：n);for(i=0;ila.length;i+)printf(%d ,la.pi.num);printf(n);printf( 表b升序排列后為：n);for(i=0;ilb.length;i+)printf(%d ,lb.pi.num);printf(n);i=0;while(ila

9、.length&jlb.length) if(la.pi.num=lb.pj.num)e1=la.pi; i+; else e1=lb.pj; j+;if(e1.num!=lc.plc.length-1.num)InsertList(lc,+m,e1);if(ila.length)while(ila.length)if(la.pi.num!=lc.plc.length-1.num)InsertList(lc,+m,la.pi); i+;if(jlb.length)while(jlb.length) if(lb.pj.num!=lc.plc.length-1.num)InsertList(lc,

10、+m,lb.pj);j+;printf(按升序排列再歸并兩表為：n);for(n=0;nnext=NULL;return OK;void InvertedList(slist &head1,slist &head2)/構(gòu)造新表逆置單鏈表函數(shù)list *p,*q;p=head1-next;q=p-next;if(p=NULL)printf(鏈表為空無法實現(xiàn)逆置操作n);else while(q!=NULL) p-next=head2-next;head2-next=p;p=q;q=q-next;p-next=head2-next;head2-next=p;printf(逆置成功！ ？n);5此處

11、應(yīng)為指針的引用void InsertList(slist &head,node &e)/ /而不應(yīng)該是list *headlist *p,*q;p=(list *)malloc(sizeof(list);q=head;while(q-next!=NULL)q=q-next;p-next=q-next;q-next=p;p-data=e;void InvertedList(sqlist &head)/不構(gòu)造新表逆置單鏈表函數(shù)/list *p,*q,*k;p=head-next;q=p-next;k=q-next;p-next=NULL;while(k!=NULL)q-next=p;p=q;q=k

12、;k=k-next;q-next=p;head-next=q;/-交換鏈表中第i個和第j個結(jié)點，函數(shù)實現(xiàn)如下一一/ int SwapListNode(sqlist &head,int i,int j)int m,n,m1,n1,sum=0; list *p,*q,*k,*c,*d,*ba; ba=head-next;while(ba!=NULL)sum+;ba=ba-next;if(i=j|isum|jsum|i1|j1)printf(所要交換的兩個結(jié)點有誤！n);return ERROR;) if(ij) m=i; n=j; else m=j;n=i; p=head;q=head;for(m

13、1=1;m1next;for(n1=1;n1next;if(p-next=q)/如果結(jié)點相鄰k=head;while(k-next!=p) k=k-next;/相鄰兩結(jié)點的交換p-next=q-next;q-next=p; k-next=q;else/如果結(jié)點不相鄰 k=head;c=head;while(k-next!=p) k=k-next;while(c-next!=q) c=c-next;d=p-next;/不相鄰兩結(jié)點之間的交換 p-next=q-next;c-next=p;k-next=q;q-next=d; return OK;/-將鏈表中結(jié)點按結(jié)點中某一項大小升序排列，函數(shù)實現(xiàn)

14、如下-/int AscendingList(sqlist &head)int m,n,sum=0,i,j;list *p,*q,*k;k=head-next;while(k!=NULL)sum+;k=k-next;for(i=1;isum;i+)for(j=i+1;jnext;m=1;while(m!=i)m+;p=p-next;q=head-next;n=1;while(n!=j) n+;q=q-next;if(p-data.expq-data.exp)/ 如果按 exp 降序排列，則應(yīng)將 改 為next;q=head2-next;while(p!=NULL&q!=NULL)if(p-dat

15、a.expdata.exp)InsertList(head3,p-data);p=p-next;elseif(p-data.expq-data.exp) InsertList(head3,q-data); q=q-next; elseif(p-data.exp=q-data.exp)e.coefficient=p-data.coefficient+q-data.coefficient; e.exp=p-data.exp;/e.exp=q-data.exp;InsertList(head3,e);p=p-next; q=q-next;if(p!=NULL)while(p!=NULL)Insert

16、List(head3,p-data);p=p-next;/如果p中有剩余，則直接將p中剩余元素插入head3中 if(q!=NULL)while(q!=NULL)InsertList(head3,q-data);q=q-next;/如果q中有剩余，則直接將q中的剩余元素插入head3中 return 0; 棧/ 利用棧結(jié)構(gòu)實現(xiàn)數(shù)制之間的轉(zhuǎn)換-書3.2.1/typedef structint num;node;typedef structnode *base;node *top;int stacksize;stack;/順序棧結(jié)構(gòu)定義int CreatStack(stack &stackll)s

17、tackll.base=(node *)malloc(INITSTACKSIZE*sizeof(node); if(!stackll.base)exit(OVERFLOW);stackll.top=stackll.base;stackll.stacksize=INITSTACKSIZE;return OK;void push(stack &s,node e)/進(jìn)棧操作if(s.top-s.base=s.stacksize) s.base=(node*)realloc(s.base,(s.stacksize+INCRESTACKMENT)*sizeof(node);if(!s.base)exit

18、(OVERFLOW);s.top=s.base+s.stacksize;/可以不寫止匕語句；s.stacksize+=INCRESTACKMENT;*(s.top+)=e;/*s.top+=e;void pop(stack &s,node &e)/出棧操作if(s.top=s.base|s.base=NULL)printf(信息有誤！ n);elsee=*-s.top;/取棧頂元素函數(shù)-/void gettop(stack &s,node &e)if(s.base=s.top)printf(棧為空，無法取得棧頂元素！n);elsee=*(s.top-1);/-棧的應(yīng)用：括號匹配的檢驗書3.2.

19、2/省略了大部分上述已有代碼int zypd(char c)/判斷是否為左括號字符if(c=|c=|c=。return OK;elsereturn ERROR;int main(void)stack s;node e1,e2,e3;char stINITSTACKSIZE;int i=0,j;CreatStack(s);printf(請輸入括號字符，以#做結(jié)束符：”)； scanf(%c,&sti);while(sti!=#)i+;scanf(%c,&sti);if(!zypd(st0)printf(輸入字符不合法！ n);elsefor(j=0;jnext=NULL;s.top=s.base

20、;void InsertStack(stack &s,node e)node *p;p=(node *)malloc(sizeof(node);if(!p)exit； else *p=e;p-next=s.top;s.top=p;void DeleteStack(stack &s,node &e)node *p;if(s.top=s.base)printf(棧為空！ n);else 11p=s.top;s.top=s.top-next;e=*p;free(p)； 隊列/-鏈隊列的描述及操作/typedef struct Nodeint a;struct Node *next;Qnode,*Qu

21、euePtr;typedef structQueuePtr front;QueuePtr rear;LinkQueue;void InitQueue(LinkQueue &Q)Q.front=(Qnode *)malloc(sizeof(Qnode);if(!Q.front)exit；Q.rear=Q.front;Q.front-next=NULL;void InsertQueue(LinkQueue &Q,Qnode e)QueuePtr p;p=(Qnode *)malloc(sizeof(Qnode);if(!p)exit；*p=e;p-next=NULL;Q.rear-next=p;Q

22、.rear=p;void DeleteQueue(LinkQueue &Q,Qnode &e)Qnode *p;if(Q.front=Q.rear)printf(隊列為空！ n);elsep=Q.front-next;e=*p;Q.front-next=p-next;if(p=Q.rear)Q.rear=Q.front;free(p)；/ 循環(huán)隊列/typedef struct nodeint data;struct node *next;node;typedef struct queuenode *base;int front;int rear;Queue;int tag;void Init

23、Queue(Queue &Q)Q.base=(node *)malloc(MAX*sizeof(node);if(!Q.base)exit；Q.front=Q.rear=0;tag=0;void InsertQueue(Queue &Q,node e)if(tag=1&Q.front=Q.rear) printf( 循環(huán)隊列已滿！ n);elseQ.baseQ.rear=e;Q.rear=(Q.rear+1)%MAX;if(Q.rear=Q.front)tag=1;void DeleteQueue(Queue &Q,node &e)if(tag=0&Q.front=Q.rear)printf(

24、隊列為空！ n);elsee=Q.baseQ.front;Q.front=(Q.front+1)%MAX;if(Q.front=Q.rear)tag=0；int EmptyQueue(Queue &Q)if(Q.front=Q.rear&tag=0)return 1;elsereturn 0; 申/ 用：堆分配存儲形式的一些操作/typedef struct stringchar *ch;int length;sstring;void CreatString(sstring &T)T.ch=(char*)malloc(sizeof(char);T.length=0;void StringAss

25、ign(sstring &T,char *s)/將用s的值賦值給用Tif(T.ch)free(T.ch);T.ch=(char*)malloc(strlen(s)*sizeof(char);/或者T.ch=(char*)malloc(sizeof(char);/動態(tài)開辟空間不同于靜態(tài)內(nèi)存開辟之處if(!T.ch)printf(ERROR);exit；strcpy(T.ch,s);T.length=strlen(s);void ClearString(sstring &T)if(T.ch)free(T.ch);T.length=0;void ConcatString(sstring &T,sst

26、ring s1,sstring s2)/用連接if(T.ch)free(T.ch);T.ch=(char*)malloc(strlen(s1.ch)+strlen(s2.ch)*sizeof(char); if(!T.ch)printf(ERRORn);exit；strcpy(T.ch,s1.ch);strcat(T.ch,s2.ch);T.length=strlen(s1.ch)+strlen(s2.ch);void SubString(sstring &sub,sstring s,int pos,int len)/取子用操作，取用s中位置從pos至len處的子用于sub中int i,j=0

27、;if(sub.ch)free(sub.ch);sub.ch=(char *)malloc(len-pos+1+1)*sizeof(char);if(!sub.ch)printf(ERRORn);exit；for(i=pos-1;is1.length)printf(ERRORn);return 0;elsefor(i=0;is1.length;i+)k=1;for(j=0;js2.length;j+)if(s2.chj!=s1.chi+j)k=0;break;if(k)count+;return count;void Deletestring(sstring &s,int pos,int le

28、n)/刪除s用中位置從pos到len處的元素int i,j,k;if(s.length=0)printf(ERRORn);elsefor(i=pos-1,j=len;js.length;i+,j+) s.chi=s.chj;s.chi=0;s.length-=(len-pos)+1;void DeleteSub(sstring &s1,sstring s2)/刪除母用s1中的子用s2int i,j,k,tag=0;for(i=0;is1.length;i+)k=1;if(tag)i-;for(j=0;js2.length;j+)if(s2.chj!=s1.chi+j)k=0;break; if

29、(k) Deletestring(s1,i+1,i+s2.length); tag=1；KMP 算法 int index_kmp(string T,string S,int pos).int i=pos,j=1;while(i=S.length&jT.length)return i-T.length;elsereturn 0;void get_next(string T).int i=1,j=0;next1=0;while(i=T.length)if(j-1=0|T.chi=T.chj)i+;j+;if(T.chi!=T.chj) nexti=j;elsenexti=nextj;elsej=n

30、extj; 數(shù)組 矩陣轉(zhuǎn)置的經(jīng)典算法 for (i=0;irow;i+)for (j=0;jcol;j+)bji=a皿時間復(fù)雜度為O(row*col),每個元素都要存儲，相對于稀疏矩陣來說比較浪費存 儲空間。 矩陣轉(zhuǎn)置-利用三元組實現(xiàn) #define MAX 12500/假設(shè)一個稀疏矩陣最多有1250亦非零元typedef structint i,j;/i,j用于存儲矩陣中元素的行、列下標(biāo)int num;/num為矩陣中非零元的值Triple;/定義一個三元組typedef structTriple dataMAX+1;int mu,nu,tu;/mu,nu非別表示一個稀疏矩陣的行數(shù)和列數(shù)/t

31、u表示該稀疏矩陣的非零元個數(shù)TSMatrix;/矩陣轉(zhuǎn)置，核心算法如下：t.mu=m.nu;t.nu=m.mu;t.tu=m.tu;for(i=0;im.nu;i+)for(j=0;jm.tu;j+)/ 按列遍歷三元組if(m.dataj.j=i)/按列升序存入數(shù)組t.datap.i=m.dataj.j;t.datap.j=m.dataj.i;t.datap.num=m.dataj.num;p+;該算法時間復(fù)雜度為 O(nu*tu),即與該矩陣的列數(shù)和非零元個數(shù)有關(guān)，當(dāng) tu=mu*nu時，時間復(fù)雜度為O(nu2*tu),此時的時間復(fù)雜度比一般算法的時間復(fù)雜 度還要大，因此此算法適用于tumu

32、*nu的情況，此算法相比一般算法節(jié)省了存 儲空間。 快速轉(zhuǎn)置算法 t.tu=m.tu;t.mu=m.nu;t.nu=m.mu;for (i=1;i=m.nu;i+)numi=0;/先使每列上元素的個數(shù)為0for (i=0;im.tu;i+)numm.datai.j+;/ 遍歷三元組求得每列上元素的個數(shù)for (i=2;i=m.nu;i+)cpoti=cpoti-1+numi-1;/求得每列上第一個元素在轉(zhuǎn)置矩陣三元組中的存儲序號for (i=0;im.tu;i+)j=m.datai.j;q=cpotj;t.dataq.i=m.datai.j;t.dataq.j=m.datai.i;t.data

33、q.num=m.datai.num;cpotj+;/當(dāng)該列上一個元素存儲完時序號加1該算法時間復(fù)雜度O(nu+tu),這種算法稱為快速轉(zhuǎn)置算法。 利用行邏輯連接順序表實現(xiàn)矩陣相乘typedef struct int i,j;int num;Triple;typedef struct Triple dataMAXSIZE;int rposMAXRC;/存放每行中首個非零元的位置int mu,nu,tu;RLSMatrix;/行邏輯連接順序表的定義int MultMatrix(RLSMatrix m,RLSMatrix n,RLSMatrix &q)/矩陣相乘函數(shù)、核心算法int arow,cte

34、mpMAXRC,i,tp,p,brow,t,ql,ccol;if(m.nu!=n.mu)return ERROR;q.mu=m.mu;q.nu=n.nu;q.tu=0;if(m.tu*n.tu!=0)for(arow=1;arow=m.mu;arow+)/按m矩陣中每行進(jìn)行處理for(i=1;i=n.nu;i+)ctempi=0;/每行處理開始，使得ctemp口置零q.rposarow=q.tu+1;/ 求矩陣 q 中 rpos 的值 if(arowm.mu)tp=m.rposarow+1;elsetp=m.tu+1;/求得arow下一行第一個非零所在的位置for(p=m.rposarow;p

35、tp;p+)/依次處理矩陣 m中每行上所有的brow=m.datap.j;if(brown.mu)t=n.rposbrow+1;elset=n.tu+1;for(ql=n.rposbrow;qlt;ql+)ccol=n.dataql.j;ctempccol+=m.datap.num*n.dataql.num;for(ccol=1;ccolMAXSIZE) return ERROR;q.dataq.tu.i=arow;q.dataq.tu.j=ccol;q.dataq.tu.num=ctempccol;return OK;void getrpos(RLSMatrix &m)int i,numMA

36、XRC,j;for(i=1;i=m.mu;i+)numi=0;/先使每行上元素的個數(shù)為0for(i=1;i=m.tu;i+)numm.datai.i+;/遍歷三元組求得每行上元素的個數(shù)for(j=1;j=m.mu;j+)if(numj!=0)break;m.rposj=1;/j代表第一個非零元數(shù)不為零的行的下標(biāo)for(i=j+1;ii=t-i;p-j=t-j;p-e=t-e;rpre=&q.rheadp-i;cpre=&q.cheadp-j;for(i=1;iright=NULL|rpre-right-jp-j) break;if(rpre-right-j=p-j) tag=0;break;

37、rpre=rpre-right;/找到指針rpre的位置while(1)if(cpre-dowm=NULL|cpre-dowm-ii) break;cpre=cpre-dowm;/找到cpre的位置if(tag)/判斷該要出入的結(jié)點所在的行是否已經(jīng)存在元素p-right=rpre-right;rpre-right=p;p-dowm=cpre-dowm;cpre-dowm=p;elseif(rpre-right-e+p-e=0)if(rpre-right!=NULL) rpre-right=rpre-right-right; if(cpre-dowm!=NULL) cpre-dowm=cpre-

38、dowm-dowm;if(rpre-right-e+p-e!=0) rpre-right-e+=p-e;/用十字鏈表存儲矩陣void CreatMatrix(ListMatrix &m)int m1,n,t,i;OLNode *p,*rpre,*cpre;printf(請輸入矩陣的行數(shù)、列數(shù)、非零元個數(shù)：);scanf(%d%d%d,&m1,&n,&t);m.mu=m1;m.nu=n;m.tu=t;m.rhead=(OLNode *)malloc(m1+1)*sizeof(OLNode);m.chead=(OLNode *)malloc(n+1)*sizeof(OLNode);for(i=1;

39、im1+1;i+)m.rheadi.right=NULL;for(i=1;in+1;i+)初始化指針的值m.cheadi.dowm=NULL;printf(請輸入這d個非零元：n,m.tu);for(i=0;ii,&p-j,&p-e);InsertMatrix(p,m); 廣義表2013/09/01 廣義表的構(gòu)造及遞歸遍歷 /廣義表的定義用到用的一些操作，上述已有用的定義在此不再敘述 typedef enumATOM,LISTElemTag;typedef struct GLNodeElemTag tag;unionchar atom;structstruct GLNode *hp,*tp;p

40、tr;/若atom占用內(nèi)存則表明為原子結(jié)點，否則 ptr占用內(nèi)存為表結(jié)點*Glist;/廣義表結(jié)點結(jié)構(gòu)的定義void SubString(Sstring &A,Sstring &B,int i,int n)/取子用操作將B用中從第i個字符起長度為n的字符串復(fù)制到A中 int j=0,m=0;for(j=i;ji+n;j+) A.chm+=B.chj;A.chm=0;A.length=m;void SeverGlist(Sstring &str,Sstring &hstr)/將非空用(廣義表形式的申)str中第一個逗號之前的 /字符置給hstr ,剩余的字符(除去該逗號)留在 str中 Sstr

41、ing Ch;int i=0,k=0,n=str.length;InitString(Ch); do i+； ClearString(Ch);InitString(Ch); SubString(Ch,str,i-1,1);/每次取一個字符至 Ch 用中if(Ch.ch0=() k+; elseif(Ch.ch0=)k-;while(in&(Ch.ch0!=,|k!=0); if(itag=ATOM; L-atom=S.ch0; else L-tag=LIST;p=L;/L 為表頭 SubString(sub,S,1,S.length-2);/脫去外層括號do SeverGlist(sub,hsub);/ 從 sub 中分離出表頭用 hsub CreatGlist(p-ptr.hp,hsub);q=p;if(!StringEmpty(sub) p=(Glist)malloczeof(GLNode); p-tag=LIST;q-ptr.tp=p; while(!StringEmpty(sub); q-ptr.tp=NULL;printf(廣義表構(gòu)造成功！ n); void TraverseGlist(Glist &L) /遞歸遍歷廣義表Glist p;if(L) p=L; if(p-tag=ATOM) printf(%c ”,p-atom);else whil