線性表的順序存儲結構

第一章 線性表的順序存儲結構

---

文章目錄

• 線性表的順序存儲結構
• 前言
• 一、順序存儲結構的建立
• • 1.條件
  • 2.代碼
• 二、順序存儲結構的獲得元素
• • 1.條件
  • 2.代碼
• 三、順序存儲結構的插入
• • 1.條件
  • 2.代碼
• 四、順序存儲結構的刪除
• • 1.條件
  • 2.代碼
• 五、總代碼
• 總結

---

前言

數據結構是大學里計算機專業類必掌握的一門課程，它很重要，尤其是對一些考研的計算機類學生來說，通常為專業課。數據結構并不是哪種編程語言所設定的，它可以用c語言來寫，也可以用c++、java、python等等，學會了一門編程語言，僅僅只是掌握一些，而學會了數據結構可以掌握很多技巧和算法并不斷提高編程能力，這對將來很重要。

---

提示：本系列文章均使用Visual Studio 2019編程，編程語言為c語言。

一、順序存儲結構的建立

1.條件

設順序線性表L，n為數據元素，則1 ≦ n ≦ ListLength（L），這里解釋一下這個閉區間，首先我們知道線性表是從1開始的，而不是像數組從0開始，這點要知道，所以n的值不能小于1，并且不能大于該線性表的長度。
我們設該線性表的存儲空間為20，即#define MAXSIZE 20，然后假設ElemType為int類型，使用一個結構體，定義一個data數組來存儲數據元素，length為當前長度。
即，我們可知道建立一個順序線性表有三個要點：
①首先要定義其最大存儲量
②存儲空間
③線性表的當前長度

2.代碼

#include <stdio.h> #define MAXSIZE 20 //設定存儲空間初始分配量 //順序存儲結構的建立 typedef int ElemType; typedef struct {ElemType data[MAXSIZE]; //數組存儲數據元素，最大值為MAXSIZEint length; //線性表當前長度 }SqList;

二、順序存儲結構的獲得元素

1.條件

首先這里返回值類型Status是一個int整型，返回OK代表1，返回ERROR代表0。我們要實行GetElem操作，即將順序線性表L的第i個元素值返回，因為數組是從0開始的，代碼中只要n的數值在所定義的數組下標的范圍內，把數組n-1下標的值返回。
即，我們可知道順序線性表獲得元素有兩個要點：
①判斷語句
②返回值

2.代碼

#include <stdio.h> #define MAXSIZE 20 //設定存儲空間初始分配量 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; //順序結構的獲得元素操作 Status GetElem(SqList L, int n, ElemType* e) //Status是函數類型，其值是函數結果狀態代碼，例OK等； { //SqList L為該線性表；int n為索引位置；ElemType*e為指針直接訪問地址if (L.length == 0 || n<1 || n>L.length) //線性表的長度不為0；線性表是從1訪問的，而不是0；索引位置不能大于線性表的長度return ERROR; //以上均返回錯誤*e = L.data[n-1]; //若滿足以上條件，則將線性表L中的第n個位置元素值返回，即只要n的數值在數組下標范圍內，就將數組第n-1下標的值返回return OK; }

三、順序存儲結構的插入

1.條件

設k為當前位置，首先判斷線性表是否已滿，再對插入位置進行判斷，然后判斷插入位置是否在表尾，從而執行不同操作，若不在表尾，通過for語句遍歷，將要插入的位置后的數據元素向后移動一位；若在表尾，則直接插入新元素，當前長度++。
即，順序線性表插入元素有五個要點：
①若插入位置不合理，拋出異常
②判斷語句
③從最后一個元素開始向前遍歷到第i個位置，分別將它們都向后移動一個位置
④將要插入元素插入位置i處
⑤表長加1

2.代碼

//順序結構的插入操作 typedef int Status; Status ListInsert(SqList* L, int n, ElemType e) {int k; //k為當前位置if (L->length == MAXSIZE) //當順序線性表存儲已滿返回錯誤 return ERROR; if (n<1 || n>L->length + 1) //插入位置小于1、大于當前長度加一則返回錯誤return ERROR;if (n <= L->length) //若插入位置不在線性表表尾，執行以下操作，將要插入的位置后數據元素向后移動一位{for (k = L->length - 1; k >= n - 1; k--) //遍歷從i索引位置到線性表長度的每個數據元素，將其全部向后移動一位L->data[k + 1] = L->data[k]; }//若插入位置在表尾，執行插入新元素操作L->data[n - 1] = e; //[i-1]是因為順序表位置-1=數組下標，數組從0開始，順序表從1開始L->length++;return OK; }

四、順序存儲結構的刪除

1.條件

設k為當前位置，首先判斷線性表是否為空表，再判斷刪除元素長度，用指針取出所要刪除的數據元素，然后再判斷刪除位置是否在表尾，若不在表尾，通過for語句遍歷，將要刪除的位置后數據元素向前移動一位；若在表尾，則刪除該元素，當前長度- -。
順序線性表刪除元素有四個要點：
①若刪除位置不合理，拋出異常
②取出刪除元素
③從刪除元素位置開始遍歷到最后一個元素位置，將它們向前移動一位
④表長減1

2.代碼

//順序結構的刪除操作 typedef int Status; Status ListDelete(SqList* L, int n, ElemType* e) {int k; //k為當前位置if (L->length == 0) //若線性表為空，即空表，則返回錯誤return ERROR;if (n<1 || n>L->length) //當刪除元素小于1，大于當前長度，刪除位置不正確返回錯誤return ERROR;*e = L->data[n - 1]; //e相當于回收站，將要刪除的元素位置放到e中；*e表示取指針e所指地址存儲的值；線性表中第n個值相當于數組data[n-1]if (n < L->length) //若刪除操作不是最后位置，執行以下操作，將要刪除的位置后數據元素向前移動一位{for (k = n; k < L->length; k++) //遍歷從n索引位置到線性表長度的每個數據元素，將其全部向后移動一位L->data[k - 1] = L->data[k];}L->length--; return OK; }

五、總代碼

//線性表順序存儲結構 #include <stdio.h> #define MAXSIZE 20 //設定存儲空間初始分配量 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0//順序存儲結構的建立 typedef int Status; typedef int ElemType; typedef struct {ElemType data[MAXSIZE]; //數組存儲數據元素，最大值為MAXSIZEint length; //線性表當前長度 }SqList;//順序結構的獲得元素操作 Status GetElem(SqList L, int n, ElemType* e) //Status是函數類型，其值是函數結果狀態代碼，例OK等； { //SqList L為該線性表；int n為索引位置；ElemType*e為指針直接訪問地址if (L.length == 0 || n<1 || n>L.length) //線性表的長度不為0；線性表是從1訪問的，而不是0；索引位置不能大于線性表的長度return ERROR; //以上均返回錯誤*e = L.data[n-1]; //若滿足以上條件，則將線性表L中的第n個位置元素值返回，即只要n的數值在數組下標范圍內，就將數組第n-1下標的值返回return OK; }//順序結構的插入操作 Status ListInsert(SqList* L, int n, ElemType e) {int k; //k為當前位置if (L->length == MAXSIZE) //當順序線性表存儲已滿返回錯誤 return ERROR; if (n<1 || n>L->length + 1) //插入位置小于1、大于當前長度加一則返回錯誤return ERROR;if (n <= L->length) //若插入位置不在線性表表尾，執行以下操作，將要插入的位置后數據元素向后移動一位{for (k = L->length - 1; k >= n - 1; k--) //遍歷從i索引位置到線性表長度的每個數據元素，將其全部向后移動一位L->data[k + 1] = L->data[k]; }//若插入位置在表尾，執行插入新元素操作L->data[n - 1] = e; //[i-1]是因為順序表位置-1=數組下標，數組從0開始，順序表從1開始L->length++;return OK; }//順序結構的刪除操作 Status ListDelete(SqList* L, int n, ElemType* e) {int k; //k為當前位置if (L->length == 0) //若線性表為空，即空表，則返回錯誤return ERROR;if (n<1 || n>L->length) //當刪除元素小于1，大于當前長度，刪除位置不正確返回錯誤return ERROR;*e = L->data[n - 1]; //e相當于回收站，將要刪除的元素位置放到e中；*e表示取指針e所指地址存儲的值；線性表中第n個值相當于數組data[n-1]if (n < L->length) //若刪除操作不是最后位置，執行以下操作，將要刪除的位置后數據元素向前移動一位{for (k = n; k < L->length; k++) //遍歷從n索引位置到線性表長度的每個數據元素，將其全部向后移動一位L->data[k - 1] = L->data[k];}L->length--; return OK; }

總結

以上就是本次的筆記內容，本文僅僅通過文字和代碼簡單介紹了順序存儲結構的各項操作，建議自己分析總結其各個操作并結合自己的編程能力選擇編程語言再寫一遍代碼從而加深印象。

---

附：在下一文章會介紹線性表鏈式存儲結構的各項操作，持續更新ing……

總結

以上是生活随笔為你收集整理的《数据结构》c语言版学习笔记——线性表的顺序存储结构的全部內容，希望文章能夠幫你解決所遇到的問題。

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