數據結構 之 線性表（附代碼）

• 線性表思維導圖:
• 線性表定義（邏輯結構）：
• • 一、順序表
  • • 1、順序表思維導圖:
    • 2、順序表的邏輯結構：
    • 3、順序表基本操作的功能實現：
    • • 1.線性表的靜態定義：
      • 2.線性表的動態定義：
      • 3. 線性表的靜態初始化：
      • 4. 線性表的動態初始化：
      • 5. 線性表的插入：
      • 6. 線性表的刪除：
      • 7. 線性表的按位查找：
      • 8. 線性表的按值查找：
      • 9.動態增長內存：
  • 二、鏈表：
  • • 1. 鏈表的思維導圖：
    • 2.鏈表的邏輯結構：
    • 3. 單鏈表：
    • • 1.單鏈表的定義：
      • 2.不帶頭節點的單鏈表的初始化：
      • 3.帶頭結點的單鏈表的初始化：
      • 4.指定節點的后插操作：
      • 5.帶頭結點的按位序插入：
      • 6.不帶頭結點的按位序插入：
      • 7.指定節點的前插操作：
      • 8.帶頭節點的按位序刪除：
      • 9.指定節點的刪除：
      • 10.帶頭結點的按位查找：
      • 11.帶頭結點的按值查找：
      • 12.求表的長度：
      • 13.帶頭結點的判斷空表：
      • 14.尾插法建立單鏈表：
      • 15.頭插法建立單鏈表：
    • 4.雙鏈表：
    • • 1.雙鏈表的定義：
      • 2. 雙鏈表的初始化：
      • 3.雙鏈表的后插操作：
      • 4.雙鏈表的節點刪除：
      • 5.雙鏈表的銷毀：
      • 6.雙鏈表的前向遍歷：
      • 7.雙鏈表的后向遍歷：
    • 5.循環單鏈表：
    • 6.循環雙鏈表
    • • 1.循環雙鏈表的定義：
      • 2.循環雙鏈表的初始化：
      • 3.循環雙鏈表的判空：
      • 4.判斷節點P是否為循環雙鏈表的表尾節點：
      • 5.循環雙鏈表的插入：
      • 6.循環雙鏈表的刪除：
    • 7.靜態鏈表：
    • • 1.什么是靜態鏈表：
      • 2. 靜態單鏈表的定義：
      • 3.靜態鏈表的特點：
  • 三、順序表和鏈表的對比：
  • • 1.順序表：
    • • 1.優點：
      • 2.缺點：
    • 2.鏈表：
    • • 1.優點：
      • 2.缺點：

線性表思維導圖:

線性表定義（邏輯結構）：

線性表L是具有相同數據結構類型的n個數據元素的有限序列
L=(a₁,a₂,a₃,a₄,…,a_i,…,a_n)

注： 1. 元素個數有限
　　 2. 邏輯上有先后順序性，有先后次序
　　 3. 都是數據元素，數據類型相同，占空間相同
　　 4. 除a₁外，都有唯一前驅； 除a_n外，都有唯一后繼

注：&表示對修改的結果“帶回來”，即操作同一地址空間的數據，例：

#include<stdio.h>void test(int x){x = 1024;printf("test內部x=%d\n",x); }int main(){int x = 1;printf("執行test前x=%d\n",x);test(x);printf("執行test后x=%d\n",x); } 運行結果：1，1024，1 #include<stdio.h>void test(int &x){x = 1024;printf("test內部x=%d\n",x); }int main(){int x = 1;printf("執行test前x=%d\n",x);test(x);printf("執行test后x=%d\n",x); } 運行結果：1，1024，1024

一、順序表

1、順序表思維導圖:

2、順序表的邏輯結構：

邏輯相鄰物理也相鄰

3、順序表基本操作的功能實現：

1.線性表的靜態定義：

#define MaxSize 100; //定義順序表最大長度 typedef struct{ElemType data[MaxSize]; int length; //當前順序表的長度 }SqlList; //順序表的類型定義

2.線性表的動態定義：

typedef struct{int *data; //動態分配數組的指針 int MaxSize; //順序表的最大容量int length; //當前順序表的長度 }SqlList; //順序表的類型定義

3. 線性表的靜態初始化：

void InitList(SqlList &L){for(int i = 0;i < MaxSize; i++)L.data[i] = 0; //防止“臟數據”L.length = 0; }

4. 線性表的動態初始化：

#define InitSize 10 void InitList(SqlList &L){L.data = (int *)malloc(InitSize * sizeof(int))L.length = 0;L.MaxSize = InitSize; }

5. 線性表的插入：

bool ListInsert(SqlList &L,int i,ElemType e){if(i < 1 || i > L.length) //判斷i值是否合法return false;if(L.length > L.MaxSize) //判斷return false;for(int j = L.length;j >= i;j--)L.data[j] = L.data[j-1];L.data[i-1] = e;L.length++;return true; }

6. 線性表的刪除：

bool ListDelete(SqlList &L,int i,ElemType &e){if(i < 1 || i > L.length)return false;e = L.data[i-1];for(int j = i;j < L.length;j ++)L.data[j-1] = L.data[j];L.length--;return true; }

7. 線性表的按位查找：

ElemType GetElem(SqlList L,int i){return L.data[i-1]; }

8. 線性表的按值查找：

ElemType LocateElem(SqlList L,ElemType e){for(int i = 0;i < L.length;i ++)if(L.data[i] == e)return i+1;return 0; }

9.動態增長內存：

void IncreaseSize(SqlList &L,int len){int *p = L.data;L.data = (int *)malloc((L.MaxSize+len) * sizeof(int));for(int i = 0;i < L.length;i++)L.data[i] = p[i];L.MaxSize = L.MaxSize + len;free(p); }

二、鏈表：

1. 鏈表的思維導圖：

2.鏈表的邏輯結構：

邏輯上相鄰物理上不一定相鄰，由指針指向下一個數據元素

3. 單鏈表：

注： 未明確說明，一律按帶頭節點處理
注： LNode * = LinkList,但是LinkList強調的是一個鏈表，而LNode *強　　　　調的是一個節點。例如:
聲明一個單鏈表時：

LinkList L;

定義一個節點時：

LNode *p;

1.單鏈表的定義：

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

2.不帶頭節點的單鏈表的初始化：

bool InitList(LinkList &L){L = NULL; //空表 return true; }

3.帶頭結點的單鏈表的初始化：

bool InitList (LinkList &L){L = (LNode *)malloc(sizeof(LNode));if(L == false)return false; //內存不足，無法分配 L->next = NULL;return true; }

4.指定節點的后插操作：

bool InsertNextNode(LNode *p,int e){if(p == NULL)return false;LNode *s = (LNode *)malloc(sizeof(LNode));if(s == NULL)return false;s->data = e;s->next = p->next;return true; }

5.帶頭結點的按位序插入：

bool ListInsert(LinkList &L,int i,int e){if(i < 1)return false;LNode *p;int j = 0;p = L;while(p != NULL && j < i-1){ //找要插入位置節點的前驅節點 p = p->next;j++;} InsertNextNode(p,e); //后插操作 }

6.不帶頭結點的按位序插入：

bool ListInsert(LinkList &L,int i,int e){if(i < 1)return false;if(i == 1){LNode *s = (LNode *)malloc(sizeof(LNode));s->data = e;s->next = L;return true;}LNode *p;int j = 0;p = L;while(p != NULL && j < i-1){ //找要插入位置節點的前驅節點 p = p->next;j++;} InsertNextNode(p,e); //后插操作 }

7.指定節點的前插操作：

bool InsertPriorNode(LNode *p,LNode *s){//第一種方法：遍歷整個單鏈表，找到p節點的前驅節點，執行后插操作//第二種方法：在p節點后直接插入新節點q，然后交換 p節點和q節點的值//此處只演示第二種方法if(p == NULL || s == NULL)return false;s->next = p->next;p->next = s;int temp = p->data;p->data = s->data;s->data = temp;return true; }

8.帶頭節點的按位序刪除：

bool ListDelete(LinkList &L,int i,int &e){if(i < 1)return false;LNode *p;int j=0;p = L;while(p != NULL && j < i-1){p = p->next;j++;}if(p == NULL)return false;if(p->next == NULL)return false;LNode *q = p->next;e = q->data;p->next = q->next;free(q);return true; }

9.指定節點的刪除：

bool DeleteNode(LNode *p){if(p == NULL)return false;LNode *q = p->next;p->data = p->next->data;p->next - q->next;free(q);return true; }

10.帶頭結點的按位查找：

LNode* GetElem(LinkList L,int i){if(i < 0)return NULL;LNode *p;int j = 0;p = L;while(p != NULL && j < i){p = p->next;j++;} return p; }

11.帶頭結點的按值查找：

LNode* locateElem(LinkList L,int e){LNode *p = L->next;while(p != NULL && p->data != e)p = p->next;return p; }

12.求表的長度：

int length(LinkList L){int len = 0;LNode *p = L;while(p->next != NULL){p = p->next;len++;}return len; }

13.帶頭結點的判斷空表：

bool Empty(LinkList L){if(L->next == NULL)return true;elsereturn false; }

14.尾插法建立單鏈表：

LinkList List_TailInsert(LinkList &L){int x;L = (LinkList)malloc(sizeof(LNode));LNode *s,*r = L;scanf("%d",&x);while(x != 9999){s = (LNode *)malloc(sizeof(LNode));s->data = x;r->next = s;r = s;scanf("%d",&x);}r->next = NULL;return L; }

15.頭插法建立單鏈表：

LinkList List_HeadInsert(LinkList &L){int x;LNode *s;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;scanf("%d",&x);while(x != 9999){s = (LNode *)malloc(sizeof(LNode));s->data = x;s->next = L->next;L->next = s;scanf("%d",&x);}return L; }

4.雙鏈表：

1.雙鏈表的定義：

typedef struct DNode{int data;struct DNode *prior,*next; }DNode,*DLinkList;

2. 雙鏈表的初始化：

bool InitDLinkList(DLinkList &L){L = (DNode *)malloc(sizeof(DNode));if(L == NULL)return false;L->prior = NULL;L->next = NULL;return true; }

3.雙鏈表的后插操作：

bool InsertNextDNode(DNode *p,DNode *s){if(p==NULL || s == NULL)return false;s->next = p->next;if(p->next != NULL) //p節點有后記節點 p->next->prior = s;s->prior = p;p->next = s;return true; }

4.雙鏈表的節點刪除：

bool DeleteNextDNode(DNode *p){if(p == NULL)return false;DNode *q = p->next;if(q == NULL)return false;p->next = q->next;if(q->next != NULL)q->next->prior = p;free(q);return true; }

5.雙鏈表的銷毀：

void DestoryList(DLinkList &L){while(L->next != NULL)DeleteNextDNode(L);free(L);L = NULL;}

6.雙鏈表的前向遍歷：

void PriorTraverse(DNode *p){while(p != NULL){printf("%d\n",p->data);p = p->prior;} }

7.雙鏈表的后向遍歷：

void NextTraverse(DNode *p){while(p != NULL){printf("%d\n",p->data);p = p->next;} }

5.循環單鏈表：

把單鏈表的最后一個指針指向頭節點L即可。其他操作同單鏈表相似，小編就水了哈。
注： 當執行插入操作時，可將L指向最后一個節點。這樣就不用遍歷整 　　　個鏈表了，神奇不神奇。

6.循環雙鏈表

1.循環雙鏈表的定義：

typedef struct DNode{int data;struct DNode *prior,*next; }DNode,*DLinkList;

2.循環雙鏈表的初始化：

bool InitDLinkList(DLinkList &L){L = (DNode *)malloc(sizeof(DNode));if(L == NULL)return false;L->prior = L;L->next = L;return true; }

3.循環雙鏈表的判空：

bool Empty(DLinkList L){if(L->next == L)return true;elsereturn false; }

4.判斷節點P是否為循環雙鏈表的表尾節點：

bool isTail(DLinkList L,DNode *p){if(p->next == L)return true;elsereturn false; }

5.循環雙鏈表的插入：

bool InsertNextDNode(DNode *p,DNode *s){if(p==NULL || s == NULL)return false;s->next = p->next;p->next->prior = s;s->prior = p;p->next = s;return true; }

6.循環雙鏈表的刪除：

bool DeleteNextDNode(DNode *p){if(p == NULL)return false;DNode *q = p->next;if(q == NULL)return false;p->next = q->next;q->next->prior = p;free(q);return true; }

7.靜態鏈表：

1.什么是靜態鏈表：

特殊類型的單鏈表，分配一片連續的存儲空間，各個節點集中安置，單鏈表的指針映射成游標，即用數組的方式實現鏈表。如圖：

注：假設第一個數據元素的地址為addr，一個數據元素4B，一個游標4B，則第n個數據元素的地址：(addr + n * 8)B

2. 靜態單鏈表的定義：

typedef struct Node SLinkList[MaxSize]；typedef struct Node{int data; //存儲數據元素 int next; //存儲數據元素的數組下標 }SLinkList[MaxSize];void test(){SLinkList a; //初始化了一個MaxSize大小的數組 }

或者

struct Node{int data; //存儲數據元素 int next; //存儲數據元素的數組下標 };typedef struct Node SLinkList[MaxSize]；

二者等價

3.靜態鏈表的特點：

優點：增刪不需要移動大量的元素
缺點：不能隨機存取，查找不便；容量固定不可變

三、順序表和鏈表的對比：

1.順序表：

1.優點：

1.隨機存取，查找速度快。2.存儲密度高，每個數據元素只需要存儲數據本身即可

2.缺點：

1.空間分配不便，需要一塊連續的存儲空間2.改變容量不便

2.鏈表：

1.優點：

1.空間分配方便，只需分配離散的小空間即可2.容量改變方便

2.缺點：

1.存儲密度小，除了要存儲數據本身外，還要存儲指針2.不可隨機存取，查找不便

開放式答題框架技巧：
ps: 累死小編了，整整敲了一天代碼，有些地方直接省略掉了，大家腦補腦補哈。這是小編第一次寫博客，不足之處請多多諒解。有任何問題，隨時可以叨擾小編。若有錯誤的地方，請聯系小編指正。

總結

以上是生活随笔為你收集整理的数据结构之线性表（附代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。