常見的線性表的基本運(yùn)算

常見的線性表的基本運(yùn)算：InitList(&L)構(gòu)造一個空的線性表L,即表的初始化。DestroyList(&L)銷毀線性表。ClearList(&L)將L重置為空表。ListEmpty(L)若L為空表，則返回TRUE,否則返回FALSE。ListLength(L)求線性表L中的結(jié)點個數(shù)，即求表長。GetElem(L,i,&e)用e返回L中第i數(shù)據(jù)個元素的值。這里要求l<i<ListLength(L)LocateElem(L.pare())返回L中第1個與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。不存在，則返回值為0。ListInsert(&L,i>e)在L中第i個位置之前插入新的數(shù)據(jù)元素e,L的長度加1。ListDelete(&L,i,&e)刪除L的第i個數(shù)據(jù)元素，并用e返回其值，L的長度減1。組合基本運(yùn)算，實現(xiàn)復(fù)雜運(yùn)算：.假設(shè)利用兩個線性表LA和LB分別表示兩個集合A和B(即：線性表中的數(shù)據(jù)元素即為集合中的成員)，現(xiàn)要求一個新的集合A=AUB"［思想］:這就要求對線性表作如下操作：擴(kuò)大線性表LA,將存在于線性表LB中而不存在于線性表LA中的數(shù)據(jù)元素插入到線性表LA中去。只要從線性表LB中依次取得每個數(shù)據(jù)元素，并依值在線性表LA中進(jìn)行查訪，若不存在，則插入之。［算法描述如下］:voidunion(List&La,ListLb){〃將所有在線性表Lb中但不在La中的數(shù)據(jù)元素插入到La中；La_len=ListLength(La)：Lb_len=ListLength(Lb)；〃求線性表的長度for(i=1；i<=Lb_len；i++){GetElem(Lb,i,e)：〃取Lb中第i個數(shù)據(jù)元素賦給eif(!LocateElem(La.e，equal))Listinsert(La,++Lalen,e)；//La中不存在和e相同的數(shù)據(jù)元素，則插入)}//union算法2.1.已知線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為?個新的線性表LC,且LC中的數(shù)據(jù)元素仍按值非遞減有序排列。［思想］:從上述問題要求可知，LC中的數(shù)據(jù)元素或是LA中的數(shù)據(jù)元素，或是LB中的數(shù)據(jù)元素，則只

要先設(shè)LC為空表，然后將LA或LB中的元素逐個插入到LC中即可。為使LC中元素按值非遞減有序排列，可設(shè)兩個指針i和j分別指向LA和LB中某個元素，若設(shè)i當(dāng)前所指的元素為a,j當(dāng)前所指的元素為b,則當(dāng)前應(yīng)插入到LC中的元素min(a,b)；顯然，指針i和j的初值均為1,在所指元素插入LC之后，在LA或LB中順序后移。［歸并算法如算法2.2所示］:VoidMergeList(ListLa,ListLb,List&Lc){〃已知線性表La和Lb中數(shù)據(jù)元素按值非遞減排列。歸并La和Lb得到新的線性表Lc,Lc的數(shù)據(jù)元素也按值非遞減排列InitList(Lc)；i=j=1；k=0；Lalen=ListLength(La)；Lbjen=ListLehgth(Lb)；while((i<=La_len)&&(j<=Lb_len))//La和Lb均非空{(diào)GetElem(La,i,ai)；GetElem(Lb,j,bj)：if(ai<=bj){Listlnsert(Lc>++k?ai)；++i；}else{Listlnsert(Lc,-H-k?bj)；-Hj：}}while(i<=La_len){GetElem(La,i++,ai)；JIII+一^-?lli-Mli~1l-k~Listlnsert(Lc?++k,ai)：}while(j<=Lb_len){GetElem(Lb,j++,bj)；Listlnsert(Lc,-H-k,bj)；)}//算法JIII+一^-?lli-Mli~1l-k~voidMcrgcListL(LinkList&La?LinkList&Lb,LinkList&Lc){〃已知單鏈線性表La和Lb的元素按值非遞減排列。歸并La和Lb得到新的單鏈線性表Lc,Lc元素也按值非遞減排列。pa=La—>next；pb=Lb->next；Lc=pc=La；〃用La的頭結(jié)點作為Lc的頭結(jié)點while(pa&&pb){if(pa—>data<pb—>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的頭結(jié)點}//MerqeList_L算法2.122.在帶頭結(jié)點的雙鏈循環(huán)線性表中第i個位置之前插入元素e。StatusListlnsertDuL(DuLinkList&L,inti,ElemTypee){〃在帶頭結(jié)點的雙鏈循環(huán)線性表中第i個位置之前插入元素e,i的合法值為1<=i<=表長+1.if(!(p=GetElemP_DuL(L,i)))〃在L中確定第i個元素的位置指針preturnERROR;//p=NULL,即第i個元素不存在if(!(s=(DuLinkList)malloc(sizeof(DuLNode)))returnERROR;s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;}//ListInsert_DuL;算法2.186.刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i個元素。StatusListDclctc_DuL(DuLinkList&L,inti,ElemType&e)(〃刪除帶頭結(jié)點的雙鏈循環(huán)線性表L的第i個元素，i的合法值為氏/表長i?!(p=GetElcmP_DuL(L,i)))〃在L中確定第i個元素的位置指針preturnERROR：//p=NULL,即第i個元素不存在e=p->data；p—>prior—>next=p->next;p—>next—>prior=p—>prior;free(p)；returnOK}//ListDelctcDuL定點起始遠(yuǎn)動圓設(shè)計程序要求:設(shè)計一個運(yùn)動的圓.起點由用戶輸入！include"graphics.h"include"stdlib.h"include"stdio.h"include"dos.h"intmain。

inti,gd=DETECT,gr;registerbgidriver(EGAVGAdriver);initgraph(&gd,&gr,"c:\\turboc2");cleardevice();for(i=0;i<300;i+=10)(cleardevice();circle(50+i,50+i,20);delay(100);/*延遲100毫秒*/)getch();closegraph();hi貼吧新浪微博騰訊微博QQ空間人人網(wǎng)豆瓣MSN1回答時間：2008-1-2220:14我來評論實驗?zāi)康暮鸵螅壕帉懸粋€簡單的算法解決一個具體的問題并在C環(huán)境中上機(jī)實現(xiàn)。對己學(xué)的C語言設(shè)計知識作一回顧。實驗內(nèi)容：用C語言編程求解百雞問題。(兩種方法)編程求解100~1000之間的所有素數(shù)。用基本窮舉法用篩法實驗二幾種算法比較 用C語言編程求解百雞問題1￥#include<stdio.h>voidmain(){intcock,hen;for(cock=0;cock<=20;cock++)for(hen=0;hen<=100/3;hen++)if(cock*5+hen*3+(100-cock-hen)*1<=100)printf("cock:%d,hen:%d,chick:%d\n",cock,hen,100-cock-hen);

}#include<stdio.h>voidchicken_question(intchicken_num,int*k,intg[],intm[],intx[])inta,b,c,t;t=0;for(a=0;a<=chicken_num/5;a++)for(b=0;b<=chicken_num/3;b++)c=100-a-b;if((a+b+c)==chicken_num&&(5*a+3*b+c/3==chicken_num)&&(c%3==0))g[t]=a;m[t]=b;x[t]=c;t++；)}*k=t;}2￥main()intn;intgongji[50],muji[50],xiaoji[50],num=0;inti,*p_num=#printfF公雞5元每只，母雞3元每只，小雞3只1元)printf("n元買n只雞,請輸入n的值：")；scanf("%d",&n);chicken_question(n,p_num,gongji,muji,xiaoji);for(i=0;i<num;i++)-{printf("%d%d%d",gongji[i],muji[i],xiaoji[i]);})3￥voidmain(){intx,y,z,j=0;printf(MFolleingarepossibleplanstobuy100fowlswith100Yuan.Wn1');for(x=0;x<=20;x++)for(y=0;y<=33;y++) z=100-x-y;if(z%3==0&&5*x+3*y+z/3==100) printf(M%2d:cock=%2dhen=%2dchicken=%2d\\n”,++j,x,y,z);}*運(yùn)行結(jié)果

Follwingarepossibleplanstobuy100fowlswith100Yuan.1:cock=0hen=25chicken=752:cock=4hen=18chicken=783:cock=8hen=11chicken=814:cock=12hen=4chicken=84編程求解100~1000之間的所有素數(shù)。#include<iostream.h>#include<math.h>boolisPrime(intn)(ints,i;〃cout<<"請輸入一個大于二的正整數(shù)："；//cin?n;s=(int)sqrt(n);for(i=2;i<=s;i++)if(n%i==O)returnfalse;returntrue;〃cout<<"該數(shù)是素數(shù)!//else coutvv"概數(shù)不是素數(shù)！";}voidmain()(intm;for(m=100;m<=999;m++)if(isPrime(m))cout?m?"\t";)Q****實驗?zāi)康暮鸵螅?1)學(xué)習(xí)工程中常用的幾種算法設(shè)計方法(2)通過上機(jī)實踐來比較這幾種算法之間的區(qū)別和聯(lián)系實驗內(nèi)容：輸出自然數(shù)「n。分別用for循環(huán)和遞歸算法實現(xiàn)。求n!。分別用for循環(huán)和遞歸算法實現(xiàn)。用二分法求解方程的根，方程式為f(x)=x'-5x2+16x-80。使用減半遞推方法完成。

實驗三線性表的初始化、插入運(yùn)算實驗?zāi)康暮鸵螅?1)學(xué)習(xí)線性表的順序存儲結(jié)構(gòu)(2)學(xué)會建立線性表(3)學(xué)會線性表順序存儲結(jié)構(gòu)下的插入運(yùn)算實驗內(nèi)容：初始化一個空的線性表，并輸入指定元素，然后輸出。實驗用例：D={13,29,5,7,81,23,92,36,24,10)在第?題的基礎(chǔ)上自定義一個函數(shù)insert,該函數(shù)用來實現(xiàn)在指定的元素前插入給定的元素(例如：在81前插入101)o注意上溢的發(fā)生。試寫出在順序存儲結(jié)構(gòu)下逆轉(zhuǎn)線性表的算法。(可選)提示：新建一個線性表，從原表按相反順序復(fù)制。實驗四線性表的刪除運(yùn)算實驗?zāi)康暮鸵螅?1)掌握線性表中順序表的結(jié)構(gòu)(2)學(xué)會線性表順序存儲結(jié)構(gòu)下的刪除運(yùn)算實驗內(nèi)容：在實驗三的源程序中增加一個函數(shù)dellist(),用來實現(xiàn)順序存儲結(jié)構(gòu)下線性表的刪除算法(例如：刪除指定元素81)o實驗用例：D={13,29,5,7,81,23,92,36,24,10}用菜單實現(xiàn)在源程序中調(diào)用線性表刪除算法的功能。實驗五線性單鏈表的初始化、插入算法實驗?zāi)康暮鸵螅?1)學(xué)會建立單鏈表

(2)學(xué)會在單鏈表中實現(xiàn)數(shù)據(jù)的插入實驗內(nèi)容：用C語言編程，建立一個單鏈表。要求完成，初始化函數(shù)的編寫、輸入函數(shù)的編寫、輸出函數(shù)的編寫、插入指定元素函數(shù)的編寫。實驗六線性單鏈表的刪除運(yùn)算實驗?zāi)康暮鸵螅?1)掌握線性單鏈表的結(jié)構(gòu)(2)學(xué)會在單鏈表中實現(xiàn)數(shù)據(jù)的刪除實驗內(nèi)容：1.在實驗五的基礎(chǔ)上，增加一個自定義函數(shù)del(),該函數(shù)實現(xiàn)在一個單鏈表中刪除指定的元素。2.在主函數(shù)中編寫菜單，實現(xiàn)插入元素和刪除元素的調(diào)用。#include<iostream>usingnamespacestd;template<classT>classlist;template<classT>classnode(friendlist<T>;private:Tdata;node<T>*next;public:node<T>():data(0),next(NULL){);~node<T>(){}TgetData(){returndata;}node<T>*getNext(){returnnext;}}；

template<classT>classlist(private:node<T>*head;public:list(){head=newnode<T>;}intinsert(T&);intremove(T&);node<T>*find(T&);voidprint();voidsort();}；template<classT>intlist<T>::insert(T&x){node<T>*p=newnode<T>;p->data=x;if(!p)return0;p->next=head->next;head->next=p;return1;template<classT>intlist<T>::remove(T&x){node<T>*p=find(x);if(!p)return0;node<T>*q=p->next;p->next=q->next;deleteq;return1;}template<classT>node<T>*list<T>::find(T&x)node<T>*q=head;

while(q->next!=NULL)if(q->next->data==x)returnq;q=q->next;}returnNULL;)template<classT>voidlist<T>::sort()(node<T>*p=head->next,*q;for(;p!=NULL;p=p->next)for(q=p->next;q!=NULL;q=q->next)if(p->data>q->data)(Ttemp=q->data;q->data=p->data;p->data=temp;}}template<classT>voidlist<T>::print()(node<T>*q=head->next;while(q!=NULL)(cout?q->data;q=q->next;)cout?endl;)template<classT>list<T>::~list()(node<T>*p=head->next;while(p!=NULL)(head->next=p->next;deletep;p=head->next;

deletehead;)intmain()(list<int>I;intx;do(cin?x;//input0exitif(x==O)break;l.insert(x);}while(1);l.sort();l-printO;cin?x;node<int>*p=Lfind(x)->getNext();cout?p->getData()?endl;l.remove(x);l-printO;return0;實現(xiàn)雙鏈表各種基本運(yùn)算的算法include<stdio.h>/*定/*指向前/*定/*指向前elemtypedata;structdnode*prior;

驅(qū)結(jié)點*/structdnode*next;繼結(jié)點*/}dlinklist;voidinitlist(dlinklist*&L){L=(dlinklist)malloc(sizeof(dlinklist));點*/L->prior=L->next=NULL;)voiddestroylist(dlinklist*&L){dlinklist*p=L,*q=p-〉next;while(q!=NULL){free(p);/*指向后/*創(chuàng)建頭結(jié)P/*指向后/*創(chuàng)建頭結(jié)q=p->next;free(p);intlistempty(dlinklist*L){return(L->next==NULL);)intlistlength(dlinklist*L){dlinklist*p=L;inti=0;while(p->next!=NULL){i++;p=p->next;)return(i);)voiddisplist(dlinklist*L)(dlinklist*p=L-〉next;while(p!=NULL)printf(〃%c〃,p->data);p=p->next;)printf(〃\n〃);)intgetelem(dlinklist*L,inti,elemtype&e){intj=0;dlinklist*p=L;while(j<i&&p!=NULL){j++；p=p->next;)if(p==NULL)return0;else{e=p->data;return1;intlocateelem(dlinklist*L,elemtypee)dlinklist*p=L->next;intn=l;while(p!=NULL&&p->data!=e){p=p->next;n++;)if(p==NULL)return(0);elsereturn(n);)intlistinsert(dlinklist*&L,inti,elemtypee){intj=0;dlinklist*p=L,*s;while(j<i-l&&p!=NULL){j++；p=p->next;if(p==NULL) /*未找到第IT個結(jié)點*/return0;else /*找到第IT個結(jié)點*/{s=(dlinklist*)malloc(sizeof(dlinklist));/*創(chuàng)建新結(jié)點*s*/s->data=e;s->next=p->next; /*將*s插到*p之后*/if(p->next!=NULL)p->next->prior=s;s->prior=p;p->next=s;return1;))intlistdelete(dlinklist*&L,inti,elemtype&e){intj=0;dlinklist*p=L,*q;

while(j<i-l&&p!=NULL)j++；p=p->next;)if(p—NULL)到第iT個結(jié)點*/return0;else1-1個結(jié)點*/{q=p->next;要刪除的結(jié)點*/if(q==NULL)return0;T個結(jié)點*/p->next=q->next;表中刪除*q結(jié)點*/if(p->next!=NULL)p->next->prior=p;free(q);/*未找/*/*未找/*找到第/*q指向/*不存在第/*從單鏈/*釋放*q結(jié)點voidmain()dlinklist*h;elemtypee;printf(〃(1)初始化單鏈表