第二章線性表是n個型別相同的資料元素的有限序列,對n>0,除第乙個元素無直接前驅,最後乙個元素無直接後繼外,其餘的每個資料元素只有乙個直接前驅和乙個直接後繼。
1)同一性:線性表有同類元素資料組成,每乙個必須屬於同一資料型別。
2)有窮性:線性表由有限個資料元素組成,表長就是表中資料元素的個數。
3)有序性:線性表中相鄰資料元素之間存在著序偶關係。
抽象資料型別定義:見課本。
線性表的順序儲存結構是指用一組位址連續的儲存單元依次儲存線性表中的各個元素,使得線性表中在邏輯上相鄰的資料元素儲存在相鄰的物理儲存單元中,即通過資料元素物理儲存的相鄰關係來反映資料元素之間邏輯上的相鄰關係。採用順序儲存結構的線性表通常稱為順序表。
將線性表歸納為:關係線性化,節點順序存。
假定順序表中有個元素,每個元素占個單元,第乙個元素的位址為,則可通過如下公式計算出第個元素的位址:
其中,稱為基位址。
#define maxsize 100
typedef struct
seqlist;
上述為定義乙個結構體,結構名為seqlist。
知識延伸(typedef)(c課本用typedef宣告新型別名)
1、查詢操作
2、插入操作
3、刪除操作
4、順序表合併演算法
線性表順序儲存結構的優缺點分析
鍊錶定義:採用鏈式儲存結構的線性表稱為鍊錶。
鍊錶的分類:
1)按實現角度看:鍊錶可分為動態鍊錶和靜態鍊錶。
2)按鏈結方式的角度看:鍊錶可分為單鏈表、迴圈鍊錶和雙鏈表。
1、初始化單鏈表
initlist(linklist *l)
node,*linklist; /*linklist為結構指標型別*/
linklist與node *同為結構指標型別,這兩種型別是等價的。通常習慣上用linklist說明指標變數,強調他是某個單鏈表的頭指標變數。例如,使用定義linklist l,則l為單鏈表的頭指標,從而提高程式的可讀性。
用node *來定義指向單鏈表中節點的指標,例如,node *p,則p為指向單鏈表中節點的指標變數。
演算法:typedef struct node
node,*linklist;
void creatfromhead(linklist l)
else flag=0;
}}2)尾插法建表
演算法描述:頭插法建立鍊錶雖然簡單,但生成的鍊錶中結點的次序和輸入的順序相反。若希望二者相同,可採用尾插法建表。
該方法是將新節點插到當前單鏈表的尾上。為此需增加乙個尾指標r,使之指向當前單鏈表的結尾。
演算法:typedef struct node
node,*linklist;
void creatfromhead(linklist l)
else
}}3、單鏈表查詢
1)按序號查詢
演算法描述:設帶頭結點的單鏈表的長度為n,要查詢表中第i個結點,則需要從單鏈表的頭指標l出發,從頭結點(l->next)開始順著鏈域掃瞄,用指標p指向當前掃瞄到的結點,初值指向頭結點,用j做計數器,累計當前掃瞄過的結點數(初值為0),當j=i時,指標p所指的結點就是要找的第i個結點。
演算法:typedef struct node
node,*linklist;
node * get(linklist l,int i)
if(p->next==null) return null; /*找不到i*/
else
return i; /*找到了i*/
}2)按值查詢
演算法描述:按值查詢是指在單鏈表中查詢是否有節點值等於e的結點,若有的話,則返回首次找到的其值等於e的結點的儲存位置,否則返回null。查詢過程從單鏈表的頭指標指向的頭結點出發,順著鏈逐個將結點的值和給定值e作比較。
演算法:typedef struct node
node,*linklist;
node *locate(linklist l,elemtype key)
return null; /*沒有找到了key*/
4、單鏈表插入操作
問題要求:**性表的第個位置之前插入乙個新元素e。
演算法思想:
查詢:在單鏈表中找到第i-1個結點並有指標pre指示。
申請:申請新節點s,將其資料域的值置為e;
插入掛鏈:通過修改指標域將新節點s掛入單鏈表l。
演算法:typedef struct node
node,*linklist;
void inslist(elemtype e,int i,linklist l)
if(k==i)
else
}5、單鏈表刪除
問題要求:將線性表的第個元素e刪除
演算法思想:
查詢:通過計數方式找到第i-1個結點並由指標pre指示;
刪除第i個結點並釋放結點空間。
結果:將長度為n的線性表變成長度為n-1
的線性表
演算法:typedef struct node
node,*linklist;
void dellist(linklist l,int i,elemtype *e)
if(pre->next==null)
s=pre->next; /*使得刪除得第i個位置的指標為s*/
pre->next=s->next;
*e=s->data;
free(s); /*釋放被刪除的結點所佔的記憶體空間*/
return ok;
}1、求單鏈表的長度
演算法描述:
可以採用「數」結點的方法來求出單鏈表的長度,用指標p依次指向各個結點,從第乙個元素開始「數」,一直「數」到最後乙個結點(p->next=null).
資料結構知識點總結
第一章緒論 1.資料結構 data structure 是指相互之間具有 存在 一定聯絡 關係 的資料元素的集合。元素之間的相互聯絡 關係 稱為邏輯結構。資料元素之間的邏輯結構有四種基本型別 集合 結構中的資料元素除了 同屬於乙個集合 外,沒有其它關係。線性結構 結構中的資料元素之間存在一對一的關係...
資料結構C語言版知識點複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合,r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...
資料結構三章知識點及相應題目
第一章知識點 p3 資料結構從邏輯上劃分為 1 線性結構 2 非線性結構 樹型結構和圖型結構 p4 從儲存結構 物理結構 上劃分 1 順序結構 所有元素存放在一片連續的儲存單元中,邏輯上相鄰的元素存放到計算機記憶體中仍然相鄰 2 鏈式結構 所有元素存放在可以不連續的儲存單元中,但元素之間的關係可以通...