線性表
線性表是最簡單最常見的資料結構,屬于邏輯結構;
線性表有兩種實作方式(存盤方式),分別是順序實作和鏈接實作;
定義:
線性表是由n(>=0)個資料元素組成的有限序列,資料元素的個數n定義為表的長度;
術語:
- 前驅, 后繼, 直接前驅, 直接后繼, 長度, 空表
案例:
線性表用L表示,一個非空線性表可記為L = (a1,a2,..an);
a1后面的稱為a1的后繼
an前面的稱為an的前驅
a1為起始節點,an為終端節點,任意相鄰的兩個元素,如a1和a2,a1是a2的直接前驅,a2是a1的直接后繼;
線性表中元素個數即表的長度,此處為n;
表中沒有任何元素時,稱為空表
除了首節點和尾節點之外,每個節點都有且只有一個直接前驅和直接后繼,首節點沒有前驅,尾節點沒有后繼;
節點之間的關系屬于一對一;
線性表的基本運算
- 初始化
? Initiate(L) 建立一個空表L(),L不包含資料元素
- 求表長度
? Length(L) 回傳線性表的長度
- 取表元素
? Get(L,i) 回傳線性表的第i個元素,i不滿足1<=i<=Length(L)時,回傳特殊值;
- 定位
? Locate(L,x)查找x在L中的節點序號,若有多個匹配的回傳第一個,若沒有匹配的回傳0;
- 插入
? Insert(L,x,i)將x插入到L的第i個元素的前面(其他元素往后挪),引數i取值范圍為1<=i<=Length(L)+1;運算結束后表長度+1;
- 洗掉
? Delete(L,i)洗掉表L中的第i個元素,i有效范圍1<=i<=Length(L);操作結束后表長度-1
強調:上述的第i個指的是元素的序號從1開始,而不是下標從0開始;
另外:插入操作要保證操作后資料還是一個接著一個的不能出現空缺;
線性表的順序存盤實作
線性表是一種邏輯結構,可以通過順序存盤結構來實作,即:
? 將表中的節點一次存放在計算機記憶體中一組連續的存盤單元中,資料元素在線性表中的鄰接關系決定了它們在存盤空間中的存盤位置;換句話說邏輯結構中相鄰的兩個節點的實際存盤位置也相鄰;
用順序存盤結構實作的線性表也稱之為為順序表,一般采用陣列來實作;
圖示:
大小與長度:
線性表的大小:指的是最大能存盤的元素個數
線性表的長度:指的是當前已存盤的個數
示例:
c語言實作:
#include <stdio.h>
//初始化操作:
const MAX_SIZE = 5;//最大長度
typedef struct list {
int data[MAX_SIZE];//陣列
int length;//當前資料長度
};
//獲取targert在表中的位置
int locate(struct list *l,int target){
for (int i = 0;i < l->length;i++){
if (target == l->data[i]){
return i + 1;
}
}
return 0;
}
//獲取第loc個元素
int get(struct list *l,int loc){
if (loc < 1 || loc > l->length){
printf("error:位置超出范圍\n");
return -1;
}else{
return l->data[loc-1];
}
}
//插入一個元素到第loc個位置上
void insert(struct list *l,int data,int location){
if (l->length == MAX_SIZE){
printf("errolr:表容量已滿\n");
return;
}
if (location < 1 || location > l->length+1){
printf("error:位置超出范圍\n");
return;
}
//目標位置后面的內容以此往后挪
for (int i = l->length; i >= location; i--) {
l->data[i] = l->data[i-1];
}
//在目標位置放入新的資料
l->data[location-1] = data;
l->length+=1;//長度加1
}
//洗掉第loc個元素,從目標位置往后的元素一次向前移動
void delete(struct list *l,int loc){
if (loc < 1|| loc > l->length){
printf("error:位置超出范圍\n");
return;
}
//目標位置及后面的所有元素全部向后移動
for (;loc < l->length; ++loc) {
l->data[loc-1] = l->data[loc];
}
l->length-=1;
}
//列印所有元素 測驗用
void show(struct list l){
for (int i = 0; i < l.length; ++i) {
printf("%d\n",l.data[i]);
}
}
//測驗
int main() {
struct list alist = {};
insert(&alist,100,alist.length+1);
insert(&alist,200,alist.length+1);
insert(&alist,300,alist.length+1);
insert(&alist,400,alist.length+1);
delete(&alist,1);
printf("%d\n",alist.length);
show(alist);
printf("%d\n",get(&alist,4));
printf("%d\n", locate(&alist,300));
printf("%d\n", get(&alist,1));
return 0;
}
插入演算法分析:
假設線性表中含有n個元素,
在插入元素時,有n+1個位置可以插入,因為要保證資料是連續的
每個位置插入資料的概率是: 1/(n+1)
在i的位置插入時,要移動的元素個數為:n - i + 1
演算法時間復雜度為:O(n)
洗掉演算法分析:
假設線性表中含有n個元素,
在洗掉元素時,有n個位置可以洗掉
每個位置插入資料的概率是: 1/n
在i的位置洗掉時,要移動的元素個數為:n - i
演算法時間復雜度為:O(n)
插入與洗掉的不足
順序表在進行插入和洗掉操作時,平均要移動大約一半的資料元素,當存盤的資料量非常大的時候,這一點需要特別注意;
簡單的說,順序表在插入和洗掉時的效率是不夠好的;特別在資料量大的情況下;
順序表總結:
1.順序表是一維陣列實作的線性表
2.邏輯上相鄰的元素,在存盤結構中也是相鄰的
3.順序表可實作隨機讀取
優缺點:
優點:
- 無需為了表示元素直接的邏輯關系而增加額外的存盤空間
- 可方便的隨機存取表中的任一節點
缺點:
- 插入和洗掉運算不方便,需要移動大量的節點
- 順序表要求占用連續的存盤空間,必須預先分配記憶體,因此當表中長度變化較大時,難以確定合適的存盤空間大小;
順序表節點存盤地址計算:
設第i個節點的存盤地址為x
設順序表起始地址為loc,每個資料元素占L個存盤單位
計算公式為:x = loc + L * (i-1)
如 loc = 100 i = 5 L = 4 則 x = 116
線性表的鏈接存盤實作
線性表也可通過鏈接存盤方式來實作,用鏈接存盤方式實作的線性表也稱為鏈表 Link List
鏈式存盤結構:
1.可用任意一組存盤單元來存盤資料
2.鏈表中節點的邏輯次序與物理次序不一定相同
3.每個節點必須存盤其后繼節點的地址資訊(指標)
圖示:
單鏈表
單鏈表指的是只能沿一個方向查找資料的鏈表,如上圖
每個節點由兩個部分(也稱為域)組成
- data域 存放節點值得資料域
- next域 存放節點的直接后繼的地址的指標域(也稱為鏈域)
節點結構:
每個節點只知道自己后面一個節點卻不知道自己前面的節點所以稱為單鏈表
圖示:
帶有head節點的單鏈表:
單鏈表的第一個節點通常不存盤資料,稱為頭指標,使用頭指標來存盤該節點的地址資訊,之所以這么設計是為了方便運算;
單鏈表特點:
- 其實節點也稱為首節點,沒有前驅,所以頭指標要指向該節點,以保證能夠訪問到起始節點;
- 頭指標可以唯一確定一個鏈表,單鏈表可以使用頭指標的名稱來命名;
- 終端節點也稱尾節點,沒有后繼節點,所以終端節點的next域為NULL;
- 除頭結點之外的幾點稱為表結點
- 為方便運算,頭結點中不存盤資料
單鏈表資料結構定義
//資料結構定義
typedef struct node {
struct node *next;
int data,length;
} Node, *LinkList;
/*
* typedef 是用來取別名的
* Node 是struct node 的別名
* *LinkList 是 struct node *的別名
* 后續使用就不用在寫struct關鍵字了
*/
運算:
初始化
一個空鏈表有一個頭指標和一個頭結點構成
假設已定義指標變數L,使L指向一個頭結點,并使頭結點的next為NULL
//時間復雜度 :O(1)
LinkList initialLinkList() {
// 定義鏈表的頭結點
LinkList head;
//申請空間
head = malloc(sizeof(struct node));
//使頭結點指向NULL
head->next = NULL;
return head;
}
求表長
從頭指標開始遍歷每個節點知道某個節點next為NULL為止,next不為空則個數len+1;
//求表長 時間復雜度 :O(n)
int length(LinkList list){
int len = 0;
Node *c = list->next;
while(c != NULL){
len+=1;
c = c->next;
}
return len;
}
讀表元素
給定一個位置n,獲取該位置的節點
? 遍歷鏈表,程序中若某節點next為NULL或已遍歷個數index=n則結束回圈
//從鏈表中獲取第position個位置的節點 時間復雜度 :O(n)
Node *get(LinkList list, int position) {
Node *current;
int index = 1;
current = list->next;
//如果下面還有值并且還沒有到達指定的位置就繼續遍歷 要和查找元素區別開 這就是一直往后遍歷直到位置匹配就行了
while (current != NULL && index < position) {
current = current->next;
index += 1;
}
if (index == position) {
return current;
}
return NULL;
}
定位
對給定表元素的值，找出這個元素的位置
? 遍歷鏈表,若某節點資料域與要查找的元素data相等則回傳當前遍歷的次數index
//求表head中第一個值等于x的結點的序號(從1開始)，若不存在這種結點，回傳結果為0 時間復雜度 :O(n)
int locate(LinkList list,int data){
int index = 1;
Node *c;
c = list->next;
while (c != NULL){
if (c->data =https://www.cnblogs.com/yangyuanhu/p/= data){
return index;
}
index+=1;
c = c->next;
}
return 0;
}
插入
在表的第i個資料元素結點之前插入一個以x為值的新結點new
? 獲取第i的節點的直接前驅節點pre(若存在),使new.next = pre.next;pre.next = new;
//在表head的第i個資料元素結點之前插入一個以x為值的新結點 時間復雜度 :O(n)
void insert(LinkList list, int position, int data) {
Node *pre, *new;
if (position == 1) {
//若插入位置為1 則表示要插入到表的最前面 即head的后面
pre = list;
} else {
//pre表示目標位置的前一個元素 所以-1
pre = get(list, position - 1);
if (pre == NULL) {
printf("error:插入的位置超出范圍");
exit(0);
}
}
new = malloc(sizeof(Node));
new->data = https://www.cnblogs.com/yangyuanhu/p/data;
new->next = pre->next;
pre->next = new;
list->length += 1;
}
洗掉
洗掉給定位置的節點
? 獲取目標節點target的直接前驅節點pre(若pre與目標都有效),pre.next = target.next; free(target);
//洗掉鏈表中第position個位置的節點 時間復雜度 :O(n)
void delete(LinkList list,int position){
//獲取要洗掉節點的直接前驅
Node *pre;
if (position == 1){ //如要洗掉的節點是第一個那直接前驅就是頭結點
pre = list;
}else{
pre = get(list,position-1);
}
////如果目標和前驅都存在則執行洗掉
if (pre != NULL && pre->next != NULL){
Node *target = pre->next; //要洗掉的目標節點
//直接前驅的next指向目標的直接后繼的next
pre->next = target->next;
free(target);
printf("info: %d被洗掉\n",target->data);
list->length -= 1;
}else{
printf("error:洗掉的位置不正確!");
exit(1);
}
}
創建具備指定資料節點的鏈表
//效率比較差演算法 時間復雜度 :O(n^2)
LinkList createLinkList1(){
LinkList list = initialLinkList();
int a;//輸入的資料
int index = 1; //記錄當前位置
scanf("%d",&a);
while (a != -1){ // O(n)
insert(list,index++,a); // O(n^2) 每次都要從頭遍歷鏈表
scanf("%d",&a);
}
return list;
}
//尾插演算法 記錄尾節點 從而避免遍歷 時間復雜度 :O(n)
LinkList createLinkList2(){
LinkList list = initialLinkList();
int a;//輸入的資料
Node *tail = list;//當前的尾部節點
scanf("%d",&a);
while (a != -1){ // O(n)
Node * newNode = malloc(sizeof(Node)); //新節點
newNode->next = NULL;
newNode->data = https://www.cnblogs.com/yangyuanhu/p/a;
tail->next = newNode;//尾部節點的next指向新節點
tail = newNode;//新節點作為尾部節點
scanf("%d",&a);
}
return list;
}
//頭插演算法 每次插到head的后面,不用遍歷但是順序與插入時相反 時間復雜度 :O(n)
LinkList createLinkList3(){
LinkList list = initialLinkList();
int a;//輸入的資料
Node * head = list;
scanf("%d",&a);
while (a != -1){ // O(n)
Node * newNode = malloc(sizeof(Node)); //新節點
newNode->next = NULL;
newNode->data = a;
newNode->next = head->next;//將原本head的next 交給新節點;
head->next = newNode;//在把新節點作為head的next;
scanf("%d",&a);
}
return list;
}
優缺點
優點:
- 在非終端節點插入洗掉時無需移動其他元素
- 無需預分配空間,大小沒有限制(記憶體夠的情況)
缺點:
- 無法隨機存取
- 讀取資料慢
鏈表與順序表的對比:
| 操作 | 順序表 | 鏈表 |
|---|---|---|
| 讀表元 | O(1) | O(n) |
| 定位 | O(n) | O(n) |
| 插入 | O(n) | O(n) |
| 洗掉 | O(n) | O(n) |
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85166.html
標籤：其他
下一篇：CDQ分治筆記+例題