一，線性表的概念以及數學定義
1.線性表的概念
零個或多個數據元素的有限序列。首先說明這是一個序列，也就是說數據元素之間是有順序的，若元素存在多個，則第一個元素無前驅，最後一個元素無後繼，其他每個元素都有且僅有一個前驅和後繼。
2.數學定義
若將線性表記為(a1...ai-1,ai,ai+1....an)，則線性表中，ai-1領先於ai，ai領先於ai+1，則稱ai-1是ai的直接前驅元素，ai+1是ai的直接後繼元素，當i=1,2....n-1的時候，ai有且僅有一個直接後繼元素，當i=2,3...n的時候，ai有且僅有一個直接前驅元素。
二，線性表的順序存儲結構
1.順序存儲結構的概念
線性表的順序存儲結構，指的是利用一段地址連續的存儲單元依次存儲線性表的數據元素。
2.順序存儲方式的實現
我們利用數組這個數據類型，來表示一段地址連續的存儲單元。
三，線性表之順序存儲結構的的實現
1.線性表基本功能：
1.創建線性表 ==> List * createList(int capacity);
2.銷毀線性表 ==> void destoryList(List * list);
3.清空線性表 ==> void clearList(List * list);
4.獲取線性表長度 ==> int length(List * list);
5.獲取線性表容量 ==> int capacity(List * list);
6.線性表的插入 ==> void insert(List * list,int pos,Node * node);
7.線性表的刪除 ==> Node * delete(List * list,int pos);
8.線性表的修改 ==> Node * update(List * list,int pos,Node * node);
9.線性表的獲取 ==> Node * get(List * list,int pos);
2.線性表基本功能的代碼實現：
# include<stdio.h>
# include<stdlib.h>
# include<string.h>
typedef void Node;
typedef struct SeqList
{
int capacity;
int length;
int * array;
}List;
/* 創建指定容量大小的線性表 */
List * createList(int capacity)
{
// 在堆上分配線性表對象
List * list = (List *)malloc(sizeof(List));
// 初始化線性表對象的容量
list->capacity = capacity;
// 初始化線性表當前長度
list->length = 0;
// 初始化線性表的數組
list->array = malloc(capacity*sizeof(void *));
// 返回線性表
return list;
}
/* 銷毀線性表 */
void destoryList(List * list)
{
if (list != NULL)
{
if (list->array != NULL)
{
// 釋放線性表中的數組
free(list->array);
list->array = NULL;
}
// 釋放線性表對象
free(list);
list = NULL;
}
}
/* 清空線性表 */
void clearList(List * list)
{
if (list != NULL)
{
// 線性表的數組清空
memset(list->array, 0, sizeof(list->array)/list->capacity);
// 線性表的長度清空
list->length = 0;
}
}
/* 線性表的長度 */
int length(List * list)
{
return list->length;
}
/* 線性表的容量 */
int capacity(List * list)
{
return list->capacity;
}
/* 線性表的插入 */
void insert(List * list, int pos, Node * node)
{
if (list == NULL)
{
printf("線性表為NULL\n");
return;
}
if (pos > list->capacity)
{
printf("插入位置超過線性表的容量\n");
return;
}
if (list->length > list->capacity)
{
printf("線性表容量已滿,無法插入\n");
return;
}
// 容錯機制 6個長度，容量20，插入10，則自動插入到7這個位置
if (pos>list->length)
{
list->array[list->length] = node;
// 線性表長度加一
list->length++;
return;
}
// 移動pos之後的數據
for (int i = list->length; i > pos-1; i--)
{
list->array[i] = list->array[i-1];
}
// 插入數據
list->array[pos - 1] = node;
// 線性表長度加一
list->length++;
}
/* 線性表的刪除 */
Node * delete(List * list, int pos)
{
if (list == NULL)
{
printf("線性表為NULL\n");
return NULL;
}
if (pos > list->length)
{
printf("刪除位置不存在\n");
return NULL;
}
// 返回的元素
Node * node = list->array[pos - 1];;
// 刪除元素後線性表長度減一
list->length--;
// 刪除最後一個
if (pos == list->length)
{
list->array[pos - 1] = NULL;
return node;
}
// 刪除
for (int i = pos - 1; i < list->length; i++)
{
list->array[i] = list->array[i + 1];
}
return node;
}
/* 線性表的修改 */
Node * update(List * list, int pos, Node * node)
{
if (list == NULL)
{
printf("線性表為NULL\n");
return NULL;
}
// 返回修改前的對象
Node * result = list->array[pos - 1];
// 修改
list->array[pos - 1] = node;
return result;
}
/* 線性表的獲取 */
Node * get(List * list, int pos)
{
if (list == NULL)
{
printf("線性表為NULL\n");
return NULL;
}
return list->array[pos - 1];
}
3.測試程序實現
/* 測試程序 */
typedef struct Student
{
char name[64];
int age;
}Student;
int main()
{
// 創建線性表
List * list = createList(20);
// 創建學生對象並初始化
Student s1 = { "劉備",42 };
Student s2 = { "關羽",38 };
Student s3 = { "張飛",32 };
Student s4 = { "趙雲",36 };
Student s5 = { "馬超",26 };
Student s6 = { "黃忠",59 };
// 頭插法插入
insert(list, 1, &s1);
insert(list, 2, &s2);
insert(list, 3, &s3);
insert(list, 4, &s4);
insert(list, 5, &s5);
insert(list, 19, &s6);
// 獲取長度
printf("############線性表長度############\n");
printf("length = %d\n", length(list));
// 獲取容量
printf("############線性表容量############\n");
printf("capacity = %d\n", capacity(list));
// 遍歷
printf("############線性表遍歷############\n");
for (int i = 1; i <= length(list); i++)
{
Student * s = get(list, i);
printf("name = %s,age = %d\n", s->name, s->age);
}
// 刪除第一個元素
delete(list, 3);
printf("############刪除第三個元素############\n");
// 遍歷
for (int i = 1; i <= length(list); i++)
{
Student * s = get(list, i);
printf("name = %s,age = %d\n", s->name, s->age);
}
// 修改第一個元素
printf("############修改第一個元素############\n");
Student sss = { "劉備-漢中王",50 };
update(list, 1, &sss);
// 遍歷
for (int i = 1; i <= length(list); i++)
{
Student * s = get(list, i);
printf("name = %s,age = %d\n", s->name, s->age);
}
// 清空線性表
printf("############清空線性表############\n");
clearList(list);
// 遍歷
for (int i = 1; i <= length(list); i++)
{
Student * s = get(list, i);
printf("name = %s,age = %d\n", s->name, s->age);
}
// 銷毀線性表
printf("############銷毀線性表############\n");
destoryList(list);
return 0;
}
四，線性表順序存儲結構的總結
1.順序存儲結構的優點
1.無需為線性表中的邏輯關系增加額外的空間。
2.可以快速獲取線性表中合法位置的數據元素。
2.順序存儲結構的缺點
1.插入和刪除操作需要移動大量元素。
2.當線性表長度變化較大時難以確定存儲空間的容量。
3.總結
線性表順序存儲結構適用於查詢多，增刪少，數據長度變化小的場景。
更多詳情見請繼續閱讀下一頁的精彩內容： http://www.linuxidc.com/Linux/2017-01/139260p2.htm