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

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

2、mp;l)/構(gòu)造一個(gè)空的線性表l.p=(node*)malloc(LIST_INIT_SIZE*sizeof(node);if(!(l.p)exit(1);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

3、("線性表不存在！n");return false;elsefree(l.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)/用e返回表中第i個(gè)數(shù)據(jù)元素if(l.p=NULL)return false;elsee=l.pi-1; return true

4、;int priorelem(list &l,int i,node &pre_e)/得到第i個(gè)元素的前驅(qū)元素if(i=0|l.p=NULL)return false;elsepre_e=l.pi-1;return true;int nextelem(list &l,int i,node &next_e)/得到表中第i個(gè)元素的后繼元素if(i>=l.length|l.p=NULL)return false;elsenext_e=l.pi+1;return true;int insertlist(list &l,int i,node &e)/將

5、元素e插入到表l中第i個(gè)元素的后面node *q,*k;if(i<1|i>l.length+1)return false;if(l.length>=l.listsize)l.p=(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;q>k;q-)*(q+1)=*q;*k=e;l.length+;return true;int deletelist

6、(list &l,int i,node &e)/刪除表中第i個(gè)元素并用e返回其值node *q;int j=i-1;if(i<1|i>l.length)return false;e=l.pi-1;for(q=&l.pi-1;j<l.length-1;j+)*q=*(+q);l.length-;return true;void mergerlist(list la,list lb,list &lc)/歸并兩個(gè)按非遞減排列的線性表int la_len,lb_len,i=1,j=1,k=0;node ai,bj;la_len=la.length;lb

7、_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+;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 ListAscendingOrde

8、r(list &l)/按結(jié)點(diǎn)中某一元素的比較升序排列線性表中的結(jié)點(diǎn)node e;int i,j;if(l.p=NULL|l.length=1)return ERROR;for(i=0;i<l.length-1;i+)for(j=i+1;j<l.length;j+)if(l.pi.num>=l.pj.num)e=l.pi;l.pi=l.pj;l.pj=e;return OK;/省略降序排列void MergerList(list la,list lb,list &lc)/將兩線性表升序排列后再歸并node *q,*k,e1;int i=0,j=0,m=0,n;L

9、istAscendingOrder(la);ListAscendingOrder(lb);printf("表a升序排列后為：n");for(i=0;i<la.length;i+)printf("%d ",la.pi.num);printf("n");printf("表b升序排列后為：n");for(i=0;i<lb.length;i+)printf("%d ",lb.pi.num);printf("n");i=0;while(i<la.length&

10、&j<lb.length)if(la.pi.num<=lb.pj.num)e1=la.pi;i+;elsee1=lb.pj;j+;if(e1.num!=lc.plc.length-1.num)InsertList(lc,+m,e1);if(i<la.length)while(i<la.length)if(la.pi.num!=lc.plc.length-1.num)InsertList(lc,+m,la.pi);i+;if(j<lb.length)while(j<lb.length)if(lb.pj.num!=lc.plc.length-1.num)

11、InsertList(lc,+m,lb.pj);j+;printf("按升序排列再歸并兩表為：n");for(n=0;n<lc.length;n+)printf("%d ",lc.pn.num);printf("n");-鏈表-typedef struct int num;node;typedef struct LISTnode data;struct LIST *next;list,*slist;int CreatList(slist &head)/此處應(yīng)為只針對(duì)的引用head=(list *)malloc(sizeo

12、f(list);if(!head)return ERROR;head->next=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("鏈表為空無法實(shí)現(xiàn)逆置操作n");elsewhile(q!=NULL)p->next=head2->next; head2->next=p;p=q;q=q->next;p->next=he

13、ad2->next;head2->next=p;printf("逆置成功！?n");void InsertList(slist &head,node &e)/此處應(yīng)為指針的引用/而不應(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)造

14、新表逆置單鏈表函數(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;k=k->next;q->next=p;head->next=q;/-交換鏈表中第i個(gè)和第j個(gè)結(jié)點(diǎn)，函數(shù)實(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!

15、=NULL)sum+;ba=ba->next;if(i=j|i>sum|j>sum|i<1|j<1)printf("所要交換的兩個(gè)結(jié)點(diǎn)有誤！n");return ERROR;if(i<j) m=i; n=j;else m=j;n=i;p=head;q=head;for(m1=1;m1<=m;m1+)p=p->next;for(n1=1;n1<=n;n1+)q=q->next;if(p->next=q)/如果結(jié)點(diǎn)相鄰k=head;while(k->next!=p)k=k->next;/相鄰兩結(jié)點(diǎn)的交

16、換p->next=q->next;q->next=p;k->next=q;else/如果結(jié)點(diǎn)不相鄰k=head;c=head;while(k->next!=p)k=k->next;while(c->next!=q)c=c->next;d=p->next;/不相鄰兩結(jié)點(diǎn)之間的交換p->next=q->next;c->next=p;k->next=q;q->next=d;return OK;/-將鏈表中結(jié)點(diǎn)按結(jié)點(diǎn)中某一項(xiàng)大小升序排列，函數(shù)實(shí)現(xiàn)如下-/int AscendingList(sqlist &hea

17、d)int m,n,sum=0,i,j;list *p,*q,*k;k=head->next;while(k!=NULL)sum+;k=k->next;for(i=1;i<sum;i+)for(j=i+1;j<=sum;j+)p=head->next;m=1;while(m!=i)m+;p=p->next;q=head->next;n=1;while(n!=j)n+;q=q->next;if(p->data.exp>q->data.exp)/如果按exp降序排列，則應(yīng)將>改為<；SwapListNode(head,i

18、,j);return OK;/-將兩鏈表合并為一個(gè)鏈表-/int AddList(sqlist &head1,sqlist &head2,sqlist &head3)/已將表head1和表head2按某一項(xiàng)升序排列過sqlist p,q;node e;p=head1->next;q=head2->next;while(p!=NULL&&q!=NULL)if(p->data.exp<q->data.exp)InsertList(head3,p->data);p=p->next;elseif(p->data.e

19、xp>q->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)InsertList(head3,p->dat

20、a);p=p->next;/如果p中有剩余，則直接將p中剩余元素插入head3中if(q!=NULL)while(q!=NULL)InsertList(head3,q->data);q=q->next;/如果q中有剩余，則直接將q中的剩余元素插入head3中return 0;-棧-typedef structint num;node;typedef struct node *base;node *top;int stacksize;stack;/順序棧結(jié)構(gòu)定義int CreatStack(stack &stackll)stackll.base=(node *)mall

21、oc(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(OVERFLOW);s.top=

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

23、1);/省略了大部分上述已有代碼/int zypd(char c)/判斷是否為左括號(hào)字符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("請(qǐng)輸入括號(hào)字符，以'#'做結(jié)束符：");scanf("%c",&sti);while(sti!='#')i+;sc

24、anf("%c",&sti);if(!zypd(st0)printf("輸入字符不合法！n");elsefor(j=0;j<i;j+) if(zypd(stj)/如果是左括號(hào)則將此字符壓入棧中e1.c=stj;push(s,e1);else/如果當(dāng)前stj元素不是左括號(hào)/則取出棧頂元素，比較棧頂元素與當(dāng)前stj元素是否項(xiàng)匹配/如果匹配，則棧頂元素出棧gettop(s,e2);if(e2.c=''&&stj=''|e2.c=''&&stj=''|e

25、2.c='('&&stj=')')pop(s,e3);elseprintf("括號(hào)驗(yàn)證失?。");break;if(s.top=s.base)/當(dāng)循環(huán)結(jié)束時(shí)，如果棧為空棧說明輸入的括號(hào)合法printf("括號(hào)驗(yàn)證成功！n");getchar();system("pause");return 0;/-鏈棧描述-/typedef struct Nodeint num;struct Node *next;node;typedef struct Node *top;Node *base;sta

26、ck;void InitStack(stack &s)s.base=(Node *)malloc(sizeof(node);if(!s.base)exit(1);elses.base->next=NULL;s.top=s.base;void InsertStack(stack &s,node e)node *p;p=(node *)malloc(sizeof(node);if(!p)exit(1);else*p=e;p->next=s.top;s.top=p;void DeleteStack(stack &s,node &e)node *p;if(s

27、.top=s.base)printf("棧為空！n");elsep=s.top;s.top=s.top->next;e=*p;free(p);-隊(duì)列-/-鏈隊(duì)列的描述及操作-/typedef struct Nodeint a;struct Node *next;Qnode,*QueuePtr;typedef struct QueuePtr front;QueuePtr rear;LinkQueue;void InitQueue(LinkQueue &Q)Q.front=(Qnode *)malloc(sizeof(Qnode);if(!Q.front)exit

28、(1);Q.rear=Q.front;Q.front->next=NULL;void InsertQueue(LinkQueue &Q,Qnode e)QueuePtr p;p=(Qnode *)malloc(sizeof(Qnode);if(!p)exit(1);*p=e;p->next=NULL;Q.rear->next=p;Q.rear=p;void DeleteQueue(LinkQueue &Q,Qnode &e)Qnode *p;if(Q.front=Q.rear)printf("隊(duì)列為空！n");elsep=Q.fro

29、nt->next;e=*p;Q.front->next=p->next;if(p=Q.rear)Q.rear=Q.front;free(p);/-循環(huán)隊(duì)列-/typedef struct nodeint data;struct node *next;node;typedef struct queuenode *base;int front;int rear;Queue;int tag;void InitQueue(Queue &Q)Q.base=(node *)malloc(MAX*sizeof(node);if(!Q.base)exit(1);Q.front=Q.r

30、ear=0;tag=0;void InsertQueue(Queue &Q,node e)if(tag=1&&Q.front=Q.rear)printf("循環(huán)隊(duì)列已滿！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("隊(duì)列為空！n");elsee=Q.baseQ.front;Q.

31、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;-串-/-串：堆分配存儲(chǔ)形式的一些操作-/typedef struct stringchar *ch;int length;sstring;void CreatString(sstring &T)T.ch=(char*)malloc(sizeof(char);T.length=0;void StringAssign(sstring

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

33、ring &T,sstring 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(1);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)/取子串操作

34、，取串s中位置從pos至len處的子串于sub中int i,j=0;if(sub.ch)free(sub.ch);sub.ch=(char *)malloc(len-pos+1+1)*sizeof(char);if(!sub.ch)printf("ERRORn");exit(1);for(i=pos-1;i<len;i+)sub.chj+=s.chi;sub.chj='0'sub.length=strlen(sub.ch);int CountString(sstring s1,sstring s2)/判斷子串s2在母串s1中出現(xiàn)的次數(shù)int i,j,k

35、,count=0;if(s1.length=0|s2.length=0|s2.length>s1.length)printf("ERRORn");return 0;elsefor(i=0;i<s1.length;i+)k=1;for(j=0;j<s2.length;j+)if(s2.chj!=s1.chi+j)k=0;break;if(k)count+;return count;void Deletestring(sstring &s,int pos,int len)/刪除s串中位置從pos到len處的元素int i,j,k;if(s.length

36、=0)printf("ERRORn");elsefor(i=pos-1,j=len;j<s.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;i<s1.length;i+)k=1;if(tag)i-;for(j=0;j<s2.length;j+)if(s2.chj!=s1.chi+j)k=0;break;if(k)Delet

37、estring(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&&j<=T.length)if(S.chi=T.chj)i+;j+;elsej=nextj+1;if(j>T.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.ch

38、i=T.chj)i+;j+;if(T.chi!=T.chj)nexti=j;elsenexti=nextj;elsej=nextj;-數(shù)組-矩陣轉(zhuǎn)置的經(jīng)典算法-for(i=0;i<row;i+)for(j=0;j<col;j+)bji=aij;時(shí)間復(fù)雜度為O（row*col),每個(gè)元素都要存儲(chǔ)，相對(duì)于稀疏矩陣來說比較浪費(fèi)存儲(chǔ)空間。-矩陣轉(zhuǎn)置-利用三元組實(shí)現(xiàn)-#define MAX 12500/假設(shè)一個(gè)稀疏矩陣最多有12500個(gè)非零元typedef structint i,j;/i,j用于存儲(chǔ)矩陣中元素的行、列下標(biāo)int num;/num為矩陣中非零元的值Triple;/定義一個(gè)三元

39、組typedef struct Triple dataMAX+1;int mu,nu,tu;/mu,nu非別表示一個(gè)稀疏矩陣的行數(shù)和列數(shù)/tu表示該稀疏矩陣的非零元個(gè)數(shù)TSMatrix;/矩陣轉(zhuǎn)置，核心算法如下：t.mu=m.nu;t.nu=m.mu;t.tu=m.tu;for(i=0;i<m.nu;i+)for(j=0;j<m.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+;該算法時(shí)間復(fù)雜度為O(nu*tu),即與該矩陣

40、的列數(shù)和非零元個(gè)數(shù)有關(guān)，當(dāng)tu=mu*nu時(shí)，時(shí)間復(fù)雜度為O(nu2*tu),此時(shí)的時(shí)間復(fù)雜度比一般算法的時(shí)間復(fù)雜度還要大，因此此算法適用于tu<<mu*nu的情況，此算法相比一般算法節(jié)省了存儲(chǔ)空間。-快速轉(zhuǎn)置算法<改進(jìn)了時(shí)間復(fù)雜度>-t.tu=m.tu;t.mu=m.nu;t.nu=m.mu;for(i=1;i<=m.nu;i+)numi=0;/先使每列上元素的個(gè)數(shù)為0for(i=0;i<m.tu;i+)numm.datai.j+;/遍歷三元組求得每列上元素的個(gè)數(shù)for(i=2;i<=m.nu;i+)cpoti=cpoti-1+numi-1;/求得每

41、列上第一個(gè)元素在轉(zhuǎn)置矩陣三元組中的存儲(chǔ)序號(hào)for(i=0;i<m.tu;i+)j=m.datai.j;q=cpotj;t.dataq.i=m.datai.j;t.dataq.j=m.datai.i;t.dataq.num=m.datai.num;cpotj+;/當(dāng)該列上一個(gè)元素存儲(chǔ)完時(shí)序號(hào)加1該算法時(shí)間復(fù)雜度O(nu+tu)，這種算法稱為快速轉(zhuǎn)置算法。-利用行邏輯連接順序表實(shí)現(xiàn)矩陣相乘-typedef struct int i,j;int num;Triple;typedef struct Triple dataMAXSIZE;int rposMAXRC;/存放每行中首個(gè)非零元的位置in

42、t mu,nu,tu;RLSMatrix;/行邏輯連接順序表的定義int MultMatrix(RLSMatrix m,RLSMatrix n,RLSMatrix &q)/矩陣相乘函數(shù)、核心算法int arow,ctempMAXRC,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;/每行處理開始，使得cte

43、mp置零q.rposarow=q.tu+1;/求矩陣q中rpos的值if(arow<m.mu)tp=m.rposarow+1;elsetp=m.tu+1;/求得arow下一行第一個(gè)非零所在的位置for(p=m.rposarow;p<tp;p+)/依次處理矩陣m中每行上所有的非零元brow=m.datap.j;if(brow<n.mu)t=n.rposbrow+1;elset=n.tu+1;for(ql=n.rposbrow;ql<t;ql+)ccol=n.dataql.j;ctempccol+=m.datap.num*n.dataql.num;for(ccol=1;cc

44、ol<=n.nu;ccol+)if(ctempccol)if(+q.tu>MAXSIZE) 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,numMAXRC,j;for(i=1;i<=m.mu;i+)numi=0;/先使每行上元素的個(gè)數(shù)為0for(i=1;i<=m.tu;i+)numm.datai.i+;/遍歷三元組求得每行上元素的個(gè)數(shù)for(j=1;j<=m.mu;j+)i

45、f(numj!=0)break;m.rposj=1;/j代表第一個(gè)非零元數(shù)不為零的行的下標(biāo)for(i=j+1;i<=m.mu;i+)m.rposi=m.rposi-1+numi-1; /求得每列上第一個(gè)元素在轉(zhuǎn)置矩陣三元組中的存儲(chǔ)序號(hào)-十字鏈表-/定義typedef struct OLNodeint i,j;/行列下標(biāo)int e;struct OLNode *right,*dowm;OLNode;typedef struct ListMatrixOLNode *rhead,*chead;int mu,nu,tu;/行數(shù)、列數(shù)、非零元個(gè)數(shù)ListMatrix;/將結(jié)點(diǎn)插入十字鏈表表示的矩陣

46、中void InsertMatrix(OLNode *t,ListMatrix &q)OLNode *rpre,*cpre,*p;int i,tag;p=(OLNode *)malloc(sizeof(OLNode);p->i=t->i;p->j=t->j;p->e=t->e;rpre=&q.rheadp->i;cpre=&q.cheadp->j;for(i=1;i<q.nu+1;i+)tag=1;if(rpre->right=NULL|rpre->right->j>p->j) brea

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

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