試描述頭指針頭結點開始結點的區別並說明頭指針和頭結點的作用
答
開始結點是指鏈表中的第一個結點也就是沒有直接前趨的那個結點
鏈表的頭指針是一指向鏈表開始結點的指針(沒有頭結點時)單鏈表由頭指針唯一確定因此單鏈表可以用頭指針的名字來命名
頭結點是在鏈表的開始結點之前附加的一個結點有了頭結點之後頭指針指向頭結點不論鏈表否為空頭指針總是非空而且頭指針的設置使得對鏈表的第一個位置上的操作與在表其他位置上的操作一致(都是在某一結點之後)
何時選用順序表何時選用鏈表作為線性表的存儲結構為宜?
答
在實際應用中應根據具體問題的要求和性質來選擇順序表或鏈表作為線性表的存儲結構通常有以下幾方面的考慮
基於空間的考慮當要求存儲的線性表長度變化不大易於事先確定其大小時為了節約存儲空間宜采用順序表反之當線性表長度變化大難以估計其存儲規模時采用動態鏈表作為存儲結構為好
基於時間的考慮若線性表的操作主要是進行查找很少做插入和刪除操作時采用順序表做存儲結構為宜反之 若需要對線性表進行頻繁地插入或刪除等的操作時宜采用鏈表做存儲結構並且若鏈表的插入和刪除主要發生在表的首尾兩端則采用尾指針表示的單循環鏈表為宜
在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決於哪兩個因素?
答
在等概率情況下順序表中插入一個結點需平均移動n/個結點刪除一個結點需平均移動(n)/個結點具體的移動次數取決於順序表的長度n以及需插入或刪除的位置ii越接近n則所需移動的結點數越少
為什麼在單循環鏈表中設置尾指針比設置頭指針更好?
答
尾指針是指向終端結點的指針用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便設一帶頭結點的單循環鏈表其尾指針為rear則開始結點和終端結點的位置分別是rear>next>next 和 rear 查找時間都是O()
若用頭指針來表示該鏈表則查找終端結點的時間為O(n)
在單鏈表雙鏈表和單循環鏈表中若僅知道指針p指向某結點不知道頭指針能否將結點*p從相應的鏈表中刪去?若可以其時間復雜度各為多少?
答
下面分別討論三種鏈表的情況
單鏈表若指針p指向某結點時能夠根據該指針找到其直接後繼能夠順後繼指針鏈找到*p結點後的結點但是由於不知道其頭指針所以無法訪問到p指針指向的結點的直接前趨因此無法刪去該結點
雙鏈表由於這樣的鏈表提供雙向指針根據*p結點的前趨指針和後繼指針可以查找到其直接前趨和直接後繼從而可以刪除該結點其時間復雜度為O()
單循環鏈表根據已知結點位置可以直接得到其後相鄰的結點位置(直接後繼)又因為是循環鏈表所以我們可以通過查找得到p結點的直接前趨因此可以刪去p所指結點其時間復雜度應為O(n)
下述算法的功能是什麼?
LinkList Demo(LinkList L){ // L 是無頭結點單鏈表
ListNode *Q*P;
if(L&&L>next){
Q=L;L=L>next;P=L;
while (P>next) P=P>next;
P>next=Q; Q>next=NULL;
}
return L;
}// Demo
答
該算法的功能是將開始結點摘下鏈接到終端結點之後成為新的終端結點而原來的第二個結點成為新的開始結點返回新鏈表的頭指針
設線性表的n個結點定義為(aaan)重寫順序表上實現的插入和刪除算法InsertList 和DeleteList
解算法如下:
#define ListSize // 假定表空間大小為
typedef int DataType;//假定DataType的類型為int型
typedef struct{
DataType data[ListSize];// 向量data用於存放表結點
int length; // 當前的表長度
} Seqlist;
//以上為定義表結構
void InsertList ( Seqlist *L Datatype x int i)
{
//將新結點x插入L所指的順序表的第i個結點ai的位置上即插入的合法位置為<=i<=L>length
int j;
if ( i < || i > L > length )
Error(position error);// 非法位置退出該函數定義見教材P
if ( L>length>=ListSize )
Error(overflow);
for ( j=L>length ; j >= i ; j )
L>data[ j+]=L>data [ j ];
L>data[ i ]=x ;
L>length++ ;
}
void DeleteList ( Seqlist *L int i )
{// 從L所指的順序表中刪除第i個結點ai合法的刪除位置為<=i<=L>length
int j;
if ( i< || i >= L> length)
Error( position error ) ;
for ( j = i ; j < L> length ; j++ )
L>data [ j ]=L>data [ j+]; //結點前移
L> length ; //表長減小
}
試分別用順序表和單鏈表作為存儲結構實現將線性表(aaan)就地逆置的操作所謂就地指輔助空間應為O()
答
順序表
要將該表逆置可以將表中的開始結點與終端結點互換第二個結點與倒數第二個結點互換如此反復就可將整個表逆置了算法如下
// 順序表結構定義同上題
void ReverseList( Seqlist *L)
{
DataType temp ; //設置臨時空間用於存放data
int i;
for (i=;i<=L>length/;i++)//L>length/為整除運算
{ temp = L>data[i]; //交換數據
L > data[ i ] = L > data[ L > lengthi];
L > data[ L > length i ] = temp;
}
}
鏈表
分析
可以用交換數據的方式來達到逆置的目的但是由於是單鏈表數據的存取不是隨機的因此算法效率太低可以利用指針改指來達到表逆置的目的具體情況入下
()當鏈表為空表或只有一個結點時該鏈表的逆置鏈表與原表相同
()當鏈表含個以上結點時可將該鏈表處理成只含第一結點的帶頭結點鏈表和一個無頭結點的包含該鏈表剩余結點的鏈表然後將該無頭結點鏈表中的所有結點順著鏈表指針由前往後將每個結點依次從無頭結點鏈表中摘下作為第一個結點插入到帶頭結點鏈表中這樣就可以得到逆置的鏈表算法是這樣的
結點結構定義如下
typedef char DataType; //假設結點的數據域類型的字符
typedef struct node{ //結點類型定義
DataType data; //結點的數據域
struct node *next;//結點的指針域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
LinkList ReverseList( LinkList head )
{// 將head 所指的單鏈表(帶頭結點)逆置
ListNode *p *q ;//設置兩個臨時指針變量
if( head>next && head>next>next)
{ //當鏈表不是空表或單結點時
p=head>next;
q=p>next;
p > next=NULL; //將開始結點變成終端結點
while (q)
{ //每次循環將後一個結點變成開始結點
p=q;
q=q>next ;
p>next = head> next ;
head>next = p;
}
return head;
}
return head; //如是空表或單結點表直接返回head
}
設順序表L是一個遞增有序表試寫一算法將x插入L中並使L仍是一個有序表
答
因已知順序表L是遞增有序表所以只要從順序表終端結點（設為i位置元素）開始向前尋找到第一個小於或等於x的元素位置i後插入該位置即可
在尋找過程中由於大於x的元素都應放在x之後所以可邊尋找邊後移元素當找到第一個小於或等於x的元素位置i時該位置也空出來了
算法如下
//順序表存儲結構如題
void InsertIncreaseList( Seqlist *L Datatype x )
{
int i;
if ( L>length>=ListSize)
Error(overflow);
for ( i=L > length ; i> && L>data[ i ] > x ; i)
L>data[ i ]=L>data[ i ] ; // 比較並移動元素
L>data[ i ] =x;
<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23992.html
