數(shù)據(jù)結(jié)構(gòu)作業(yè)題

數(shù)據(jù)結(jié)構(gòu)作業(yè)題精品文檔，放心下載，放心閱讀1簡述下列術(shù)語：線性表，順序表，鏈表。答：線性表是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)，一個(gè)線性表是N個(gè)數(shù)據(jù)元素的有限序列。順序表是指用一組地址連續(xù)的儲(chǔ)存單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡稱順序表。鏈表是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素。用這種方法存儲(chǔ)的線性表簡稱線性鏈表。2何時(shí)選用順序表，何時(shí)選用鏈表作為線性表的存儲(chǔ)結(jié)構(gòu)合適?各自的主要優(yōu)缺點(diǎn)是什么?答：線性表的邏輯順序與物理順序一致;數(shù)據(jù)元素之間的關(guān)系是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來體現(xiàn)。而存儲(chǔ)鏈表中結(jié)點(diǎn)的一組任意的存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中結(jié)點(diǎn)的邏輯順序和物理順序不一定相同。3在順序表中插入和刪除一個(gè)結(jié)點(diǎn)平均需要移動(dòng)多少個(gè)結(jié)點(diǎn)?具體的移動(dòng)次數(shù)取決于哪兩個(gè)因素?答：在順序表中插入和刪除一個(gè)結(jié)點(diǎn)平均需要移動(dòng)1個(gè)結(jié)點(diǎn)，具體移動(dòng)次數(shù)取決于時(shí)間復(fù)雜和空間復(fù)雜程度。4鏈表所表示的元素是否有序?如有序，則有序性體現(xiàn)于何處?鏈表所表示的元素是否一定要在物理上是相鄰的?有序表的有序性又如何理解?答：鏈表元素的有序并不一定是值得有序，而是邏輯次序上的有序；鏈表中的元素并不需要物理位置上相鄰，因?yàn)槠溥壿嬄?lián)系已經(jīng)在結(jié)點(diǎn)中包括了。5設(shè)順序表L是遞增有序表，試寫一算法，將x插入到L中并使L仍是遞增有序表。答：usingSystem;usingSystem.Collections.Generic;usingSystem.Collections;數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第1頁。usingSystem.Text;數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第1頁。namespacetest{classarrlist_test{publicstaticArrayLista=newArrayList();publicstaticvoidmain(){do{currency.write("請寫入下一個(gè)值");a.Add(Console.ReadLine());a.Sort();}while(currency.choice());for(inti=0;i<a.Count;i++){Console.Write("\t"+a[i]);}}}}6寫一求單鏈表的結(jié)點(diǎn)數(shù)目ListLength(L)的算法。答：inti=0;LinkNode*pa;pa=L->next;while(pa!=null)pa=pa->next,i++;returni;7寫一算法將單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的結(jié)果鏈表中所有結(jié)點(diǎn)的值均不相同。答：voidDeleteList(LinkListL){ListNode*p,*q,*s;p=L-next;while(p->next&&p->next->next){q=p;while(q->next)if(p->data==q->next->data){s=q->next;q->next=s->next;free(s);}elseq=q->next;數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第2頁。數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第2頁。}}8寫一算法從一給定的向量A刪除值在x到y(tǒng)(x≤y)之間的所有元素(注意：x和y是給定的參數(shù)，可以和表中的元素相同，也可以不同)。數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第3頁。答：#include<stdio.h>

typedefintdatatype;

#definemaxsize100

/*定義順序表*/

typedefstruct

{

datatypedata[maxsize];

intlast;

}SeqList;

/*初始化*/

voidinit_SeqList(SeqList*L)

{

L->last=-1;

}

/*輸入順序表*/

voidinput_SeqList(SeqList*L,intn)

{

inti;

L->last=0;//初始化

for(i=0;i<n;i++)

scanf("%d",&(L->data[i]));

L->last=L->last+n;

}

/*判斷*/

intmeasure(SeqList*L,intx,inty,intn)

{

if((L->data[0]>=L->data[n-1]&&x>=L->data[n-1]&&y<=L->data[0])||//是n-1

(L->data[0]<=L->data[n-1]&&x>=L->data[0]&&y<=L->data[n-1]))

return1;

elsereturn0;

}

/*刪除值*/

intdelete_list(SeqList*L,intx,inty)

{

inti=0,j=0;

while(i<L->last)

{

/*if((L->data[i]>=x)&&(L->data[i]<=y))

distence++;

elseL->data[i-distence]=L->data[i];*/

if(L->data[i]<x||L->data[i]>y)

L->data[j++]=L->data[i];

i++;

}

//L->last-=distence;

L->last=j;

//printf("j=%d\n",j);

if(L->last==0)

{

printf("原表已為空表!");

return0;

}

return1;

}

/*輸出元素*/

intoutput_SeqList(SeqList*L)

{

inti;

for(i=0;i<L->last;i++)

printf("%d",L->data[i]);

puts("");

return(L->data[i]);

}

voidmain()

{

ints,x,y;

SeqListL;

init_SeqList(&L);

printf("請輸入順序表長度:");

scanf("%d",&s);

printf("請輸入順序表:");

input_SeqList(&L,s);

//output_SeqList(&L);

printf("輸入x和y的值：");

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

if(measure(&L,x,y,s))

{

delete_list(&L,x,y);

output_SeqList(&L);

數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第4頁。}

else

printf("不存在x~y之間的元素!");數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第3頁。數(shù)據(jù)結(jié)構(gòu)作業(yè)題全文共5頁，當(dāng)前為第4頁。9設(shè)A和B是兩個(gè)按元素值遞增有序的單鏈表，寫一算法將A和B歸并為按按元素值遞減有序的單鏈表C，試分析算法的時(shí)間復(fù)雜度。答：node*mergelink(node*p,node*q)

{

node*h,*r;

h=(node*)malloc(sizeof(node));

h->next=NULL;

r=h;

while(p!=NULL&&q!=NULL)

{

if(p->data<=q->data)

{

r->next=p;

r=p;

p=p->next;

}

else

{

r->next=q;

r=q;

q=q->next;

}