二、線性表 | 數據結構

一、線性表的基本概念與實現

1、什麼是線性表？

線性表示具有相同特性的一個有限序列。其所包含的元素的個數叫做線性表的長度。長度為零則為空表。

線性表可以是有序的也可以是無序的。

2、線性表有什麼邏輯特性？

1）存在唯一的第一個元素和唯一的最後一個元素。

2）除了第一個元素外都有前驅，除了最後一個元素外都有後驅。

3、線性表的存儲結構

有兩種：順序表和鏈表。

1）順序表大家都很熟悉了，比如：

int a[100];

線性表中的所有元素按照其邏輯順序依次存儲到指定的存儲位置開始的一塊連續的存儲空間中。

2）鏈表呢？如下：

Typedef struct Node{ int data; struct Node*next;}Node;

每個結點不僅包含了所存元素的信息，還保存了元素之間的邏輯關係信息。

3）兩種存儲方式的比較

a、順序表

具有隨機訪問特性：即可以通過[]操作訪問順序表中的元素。

要求佔用連續的存儲空間：內存要一次性分配好，比如int arr[100]; 超過100就沒法存了，得新開一個大一點的數組，把原來的數據全轉存到新數組中。

b、鏈表

不支持隨機訪問：不能通過[]尋秩的方式來訪問元素，只能一個接著一個地去訪問。

支持存儲空間的動態分配：想要加入更多的元素？簡單，new 一個，連接上原鏈表的尾端就可以了。

鏈表有以下a、b、c、d、e五種形式：

a、單鏈表

細分為帶頭的單鏈表和不帶頭的單鏈表。

單鏈表，即單向鏈表。

Typedef struct LNode{ int data; struct LNode*next;}LNode;

I、帶頭的單鏈表：即在開始結點有一個頭結點（哨兵結點）的單鏈表，head->next==NULL時鏈表為空。

Node*head=new Node;

II、不帶頭的單鏈表，head==NULL時表為空的鏈表

b、雙鏈表

即雙向鏈表：

Typedef struct DLNode{ int data; struct DLNode*prior; struct DLNode*next;}DLNode;

同樣的，雙鏈表也細分為帶頭的和不帶頭的，同上。

c、循環單鏈表

在單鏈表的基礎上，將最後一個結點的next指向第一個結點（如果帶頭結點，則指向頭結點，否則指向開始節點）。

同樣的，循環單鏈表也分為帶頭的和不帶頭的，同上。

d、循環單鏈表

在雙鏈表的基礎上，終結點的next指向第一個結點，第一個結點的prior指向最後一個結點。

同樣的，循環單鏈表也分為帶頭的和不帶頭的，帶頭的head->next==NULL||head->prior==NULL必然都等於head。

e、靜態鏈表

靜態鏈表藉助一維數組來表示，之所以稱之為靜態，你可以理解為：它和數組一樣，只能以靜態的方式分配內存。

如圖：

靜態鏈表和一般鏈表最大的區別在於，一般鏈表的結點空間來自於整個內存，而靜態鏈表則來自於一個結構體數組。

4、順序表和鏈表的對比

1）空間

a、分配方式：順序表的存儲空間為一次性分配，鏈表則為多次分配。

b、存儲密度（=結點值域所佔的存儲量/結點結構所佔的存儲總量）：順序表存儲密度=1，鏈表的存儲密度<1（因為包含指針域）。

2）空間

a、存取方式：順序表可以隨機存取，也可以順序存取，鏈表則只能一個接一個地順序存取。

b、插入、刪除移動元素的個數：順序表，移動元素個數的期望值為：0+1+2...+n-1=(n-1)n/2/n=(n-1)/2，即插入和刪除的演算法複雜度為O(n)，鏈表則為O(1)。

二、線性表的結構體定義和基本操作

1、線性表表的結構體定義

1）順序表結構體定義：

#define maxSize 100typedef struct { int data[maxSize]; int length;}Sqlist;

當然，這樣也ok

#define maxSize 100int arr[maxSize];int len;

2）單鏈表結點定義

typedef struct LNode{ int data; struct LNode*next;}LNode;

3）雙鏈表結點定義

typedef struct DLNode{ int data; struct DLNode*prior; struct DLNode*next;}DLNode;

2、順序表的操作

1）按元素值的查找法

int findElem(Sqlist L,int e){ int i; for(i=0;i<L.length;i++){ if(e==L.data[i]){ return i; } } return -1;}

2）插入數據的演算法

#define maxSize 100int insertElem(Sqlist &L,int p,int e){ if(p<0||p>=L.length||L.length==maxSize) return 0; int i=L.length; for(;i>p;i--){ L.data[i]=L.data[i-1]; } L.data[p]=e; ++(L.length); return 1;}

3）簡單的初始化順序表演算法

void initList(Sqlist& L){ L.length=0;}

4）求指定位置元素的演算法

int getElem(Sqlist L,int p,int &e){ if(p<0||p>=L.length)return 0; e=L.data[p]; return 1;}

3、單鏈表的操作（都是帶頭結點的鏈表）

1）歸併兩個單鏈表

void merge(LNode *A,LNode *B,LNode* &C){ LNode *p=A->next; LNode *q=B->next; LNode *head=A; C=head; head->next=NULL; free(B);//釋放B鏈表的頭結點內存 while(p&&q){ if(p->data>q->data){ head->next=q; q=q->next; head=head->next; }else{ head->next=p; p=p->next; head=head->next; } } head->next=NULL; if(p)head->next=p; if(q)head->next=q;}

2）尾插法構造單鏈表

void createListR(LNode* &C,int arr[],int len){ LNode* p=(LNode*)malloc(sizeof(LNode)); C=p; int i; for(i=0;i<len;i++){ p->next=(LNode*)malloc(sizeof(LNode)); p=p->next; p->data=arr[i]; } p->next=NULL;}//尾插法

3）頭插法構造單鏈表

void createListF(LNode* &C,int arr[],int len){ LNode* p=(LNode*)malloc(sizeof(LNode)); p->next=NULL; C=p; int i; for(i=0;i<len;i++){ LNode* temp=(LNode*)malloc(sizeof(LNode)); temp->data=arr[i]; temp->next=p->next; p->next=temp; }}//頭插法，鏈表中的元素和原數組的元素次序剛好相反。

4）單鏈表的查找與刪除操作

int findAndDelete(LNode* C,int x){ LNode* p=C; while(p->next){ if(x==p->next->data){ LNode* temp=p->next; p->next=p->next->next; free(temp); return 1; } p=p->next; } return 0;}

4、雙鏈表的操作

1）背插法構造雙鏈表

void createDlistR(DLNode *&L, int arr[],int len){ DLNode*p=(DLNode*)malloc(sizeof(DLNode)); p->prior=NULL;p->next=NULL; L=p; int i; for(i=0;i<len;i++){ p->next=(DLNode*)malloc(sizeof(DLNode)); p->next->prior=p; p=p->next; p->data=arr[i]; } p->next=NULL;}

2）查找結點

DLNode* findNode(DLNode*L,int x){ DLNode*p=L->next; while(p){ if(p->data==x)break; p=p->next; } return p;}

3）插入結點

void insertAfter(DLNode*p,DLNode*s){ s->next=p->next; p->next=s; s->prior=p; s->next->prior=s;}

4）刪除後繼結點

void deleteNext(DLNode*p){ DLNode* next=p->next; p->next=p->next->next; next->next->prior=p; free(next);}

PS：

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

推薦閱讀：