數(shù)據(jù)結(jié)構(gòu) B數(shù)據(jù)結(jié)構(gòu)習(xí)題課：線性表學(xué)習(xí)課件

基本要求：線性表基本概念熟練掌握各種存儲(chǔ)結(jié)構(gòu)基本操作及其實(shí)現(xiàn)線性鏈表問答題1：設(shè)m×n階稀疏矩陣A有t個(gè)非零元素，其三元組表表示為LTMA[1:(t+1)，1:3]，試問：非零元素的個(gè)數(shù)t達(dá)到什么時(shí)候時(shí)用LTMA表示A才有意義？解答：A的最后一個(gè)元素是amn，其余元素的下標(biāo)積必小于mn即有：3(t+1)≤mn因而：當(dāng)t≤mn/3-1時(shí)，用LTMA表示A才有意義。問答題2：假設(shè)按低下標(biāo)優(yōu)先存儲(chǔ)整數(shù)數(shù)組A(-3:8,3:5,-4:0,0:7)時(shí)，第一個(gè)元素的字節(jié)存儲(chǔ)地址是100，每個(gè)整數(shù)占4個(gè)字節(jié)。問：A(0,4,-2,5)的存儲(chǔ)地址是什么？坐標(biāo)平移：A(-3:8,3:5,-4:0,0:7)對應(yīng)規(guī)范化的數(shù)組為：A(0:11,0:2,0:4,0:7)元素A(0,4,-2,5)相當(dāng)于A(3,1,2,5)所以有：L(3,1,2,5)=100+4(3x2x4x7+1x4x7+2x7+5)=1164……h(huán)ead^1、輸入系列整數(shù)，建立按升序排列的有序鏈表分析：head^head^2PqP……h(huán)ead^^……pq22125425023……h(huán)ead^^pq225425063P=head;while((p->next!=NULL)&&(p->next->data<=x))p=p->next;NODE*creat_link(){NODE*head,*p,*q;

intx;head=(NODE*)malloc(sizeof(NODE*));head->next=NULL;

scanf("%d",&x);while(x!=-999){q=(NODE*)malloc(sizeof(NODE*));q->data=x;q->next=NULL;p=head;while((p->next!=NULL)&&(p->next->data<=x))p=p->next;q->next=p->next;p->next=q;

scanf("%d",&x);}return(head);}算法2、刪除值為x的結(jié)點(diǎn)Voiddelete_x(NODE*head,intx){NODE*p,*q;p=head;while((p->next!=NULL)&&(p->next->data!=x))p=p->next;If(p->next){q=p->next;p->next=q->next;free(q);}}head^PqheadxPPxqPxqP^3、在值為x的結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)y,

若x不存在，則插入在表尾Voidinsert_after_x(NODE*head,int

x,inty){NODE*p,*q;q=(NODE*)malloc(sizeof(NODE*));q->data=y;q->next=NULL;if(head->next){head->next=q;return;}p=head->next;while((p->next!=NULL)&&(p->data!=x))p=p->next;q->next=p->next;p->next=q;}headxPP^head^yq^Pxyq^4、在值為x的結(jié)點(diǎn)前插入一個(gè)新的結(jié)點(diǎn)y,

若x不存在，則插入在表尾Voidinsert_after_x(NODE*head,int

x,inty){NODE*p,*q;q=(NODE*)malloc(sizeof(NODE*));q->data=y;q->next=NULL;p=head;while((p->next!=NULL)&&(p->next->data!=x))p=p->next;q->next=p->next;p->next=q;}headxPP^Pxyq^head^yq^p5、刪除鏈表heada自第i個(gè)元素起共len個(gè)元素，然后將

heada插入到鏈表headb中第j個(gè)元素位置NODE*delete_i_len(NODE*heada,int

i,int

len){NODE*p,*q;

intk;if(i==1)for(k=1;k<=len;k++){q=heada;

heada=heada->next;free(q);}else{p=heada;for(k=1;k<=i-2;k++)p=p->next;for(k=1;k<=len;k++){q=p->next;p->next=q->next;free(q)}}

return(heada);}NODE*insert_j(NODE*heada,NODE*headb,intj){NODE*p,*q;

intk;p=heada;while(p!=NULL)p=p->next;if(j==1){p->next=headb;

headb=heada;}else{q=headb;for(k=1;k<=j-2;k++)q=q->next;p->next=q->next;q->next=heada;}

return(headb);}調(diào)用：p=delete_i_len(head,i,len);q=insert_j(p,head,j);6、某百貨公司倉庫中有一批電視機(jī)，按其價(jià)格從低到高的次序構(gòu)成了一個(gè)單鏈表存在計(jì)算機(jī)中，鏈表的每個(gè)結(jié)點(diǎn)表示同樣價(jià)格的若干臺(tái)電視。現(xiàn)在有新到m臺(tái)價(jià)格為h的電視機(jī)入庫。試編寫出倉庫電視機(jī)鏈表增加電視機(jī)的算法。struct

CellType{ floatprice;

intnum;

struct

CellType*next;};typedef

struct

CellType*LIST;LISTcreate_link()//創(chuàng)建倉庫{LISTp,q,head;floatx;inty;head=newCellType;//建立表頭結(jié)點(diǎn)

head->next=NULL;

printf("輸入庫中現(xiàn)有電視機(jī)的價(jià)格和臺(tái)數(shù)，以逗號間隔，輸入0,0結(jié)束:\n");

scanf("%f,%d",&x,&y);

while(x!=0) {q=newCellType;q->price=x;q->num=y;q->next=NULL; p=head;

while((p->next!=NULL)&&(p->next->price<=x)) p=p->next; q->next=p->next; p->next=q;

scanf("%f,%d",&x,&y); }

return(head);}voidinsert(LISThead)//新的電視到貨{LISTp,q;p=head->next;floatx;inty;

printf("新到電視的價(jià)格，臺(tái)數(shù)？:");

scanf("%f,%d",&x,&y);

while((p->next!=NULL)&&(p->next->price<=x))p=p->next;

if(p->price==x) p->num=p->num+y;else{q=newCellType;q->price=x;q->num=y;q->next=p->next;p->next=q;}};7、假設(shè)有一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域：pre,data和link,其中data為數(shù)據(jù)域，link為指針域，他指向后繼結(jié)點(diǎn)，pre為指針域，他的值為空指針。試編寫算法，將此表改成雙向鏈表。struct

CellType{

intdata;

struct

CellType*pre,*link;};typedef

struct

CellType*LIST;LISTcreate_link()//創(chuàng)建單向循環(huán)鏈表{LISTp,q,head;

intx;

printf("輸入鏈表結(jié)點(diǎn)值，-999結(jié)束:\n");

cin>>x;

if(x==-999)return(NULL);head=newCellType;//建立表頭結(jié)點(diǎn)

head->data=x;head->link=NULL;head->pre=NULL;p=head;

scanf("%d",&x);

while(x!=-999) {q=newCellType;q->data=x;q->link=NULL;q->pre=NULL; q->link=p->link; p->link=q; p=q;

cin>>x; }p->link=head;

return(p);}voiddouble_link(LISThead)//單向鏈表變成雙向鏈表{LISTp,q;p=q=head->link;do{q->link->pre=q;q=q->link;}while(q!=p);}voidoutput_double(LISThead)//輸出雙向鏈表{LISTp;p=head;

printf("\n雙向循環(huán)鏈表如下：\n");do{

printf("%d,",p->data);p=p->pre;}while(p!=head);};8、設(shè)有一個(gè)雙向鏈表，每個(gè)結(jié)點(diǎn)中除有pre、data和next三個(gè)域外，還增設(shè)了一個(gè)訪問頻度域freq。在鏈表被啟用后，頻度域freq的值均初始化為零，而每當(dāng)對鏈表進(jìn)行一次LOCATE(L,x)的操作后，被訪問的節(jié)點(diǎn)（即元素值等于x的結(jié)點(diǎn)）中的頻度域freq的值便增1，同時(shí)，調(diào)整鏈表中結(jié)點(diǎn)之間的次序，使其按訪問頻度非遞增的次序順利排列，以便始終保持被頻繁訪問的節(jié)點(diǎn)總是靠近表頭結(jié)點(diǎn)。試編寫符合上述要求的LOCATE操作的算法。struct

CellType{

intdata;

intfreq;

struct

CellType*next,*pre;};typedef

struct

CellType*LIST;LISTcreate_link()//創(chuàng)建按freq有序的雙向鏈表{LISTp,q,head;

intx,f;head=newCellType;//建立表頭結(jié)點(diǎn)

head->next=NULL;head->pre=NULL;

cout<<"輸入鏈表各結(jié)點(diǎn)的值和訪問頻度，以逗號間隔，-999，0結(jié)束:"<<endl;

scanf("%d,%d",&x,&f);

while(x!=-999){q=newCellType;q->data=x;q->freq=f;q->next=NULL;q->pre=NULL;p=head;

while((p->next!=NULL)&&(p->next->freq>f)) p=p->next;q->next=p->next;q->pre=p;

if(p->next)p->next->pre=q;p->next=q;

scanf("%d,%d",&x,&f);}

return(head);}voidlocate(LIST

head,intx){LISTp,q;p=head->next;

while((p!=NULL)&&(p->data!=x))p=p->next;

if(p==NULL)printf("表中無%d結(jié)點(diǎn)!\n",x);else{p->freq=p->freq+1;

if(p->freq>p->pre->freq) {q=p;//刪除

p->pre->next=q->next; p->next->pre=p->pre; p=head;//重新插入，并保持有序

while((p->next!=NULL)&&(p->next->freq>q->freq)) p=p->next; q->next=p->next; q->pre=p;

if(p->next)p->next->pre=q; p->next=q; }}}9、設(shè)一單向鏈表的頭指針為Head，鏈表的紀(jì)錄中包含著整數(shù)類型關(guān)鍵字key域，試設(shè)計(jì)算法，將此鏈表的記錄按照key遞增的順序進(jìn)行就地排序。struct

CellType{

intdata;

struct

CellTy