目錄
一、線性表
1. 線性表的定義
2. 線性表的要素
二、線性表的基本操作
三、線性表的順序存儲結構
1. 定義
2. 順序表的操作? ? ??
a. 插入操作
b. 刪除操作
c. 查找操作
d. 修改操作
e. 代碼實例
一、線性表
1. 線性表的定義
????????一個線性表是由零個或多個具有相同類型的結點組成的有序集合。
????????這里用（a1，a2，…，an）來表示一個線性表，n為自然數(shù)：
①?當n=0時，線性表中無結點（或曰包含零個結點），這樣的線性表被稱為空表；
②?當n=1時，線性表中僅有一個結點，該結點既是表頭（head），又是表尾（tail）；
③?當n≥1時，稱a1為線性表的表頭，稱an為線性表的表尾；
④?當n≥2時，稱ai為ai+1的前驅結點，稱ai+1為ai的后繼結點，其中1≤ i < n；表頭結點無前驅結點，表尾結點無后繼結點。
????????線性表中的元素之間存在一對一的關系，也就是說每個元素都有一個直接前驅和一個直接后繼，除了第一個元素沒有前驅，最后一個元素沒有后繼。線性表可以用來表示各種具有線性關系的數(shù)據(jù)，例如數(shù)組、鏈表等。
2. 線性表的要素
- 元素類型：線性表中的元素具有相同的數(shù)據(jù)類型，可以是整數(shù)、字符、結構體等。
- 元素個數(shù)：線性表中的元素個數(shù)可以是任意的，可以是有限的或無限的。
- 元素順序：線性表中的元素按照一定的次序排列，每個元素都有一個唯一的位置。
- 關系定義：線性表中的元素之間存在順序關系，每個元素都與它的前驅和后繼相連。
- 表頭和表尾：線性表有一個表頭和一個表尾，表頭是線性表中第一個元素，表尾是線性表中最后一個元素。
二、線性表的基本操作
????????①創(chuàng)建一個線性表
????????②確定線性表的長度
????????③確定線性表是否為空
????????④存取表中指定位置結點的字段值
????????⑤查找指定字段值在表中的位置
????????⑥刪除表中指定位置的結點
????????⑦在表中指定位置插入一個新結點
三、線性表的順序存儲結構
1. 定義
????????按照線性表結點間的邏輯順序依次將它們存儲于一組地址連續(xù)的存儲單元中的存儲方式被稱為線性表的順序存儲方式。
????????按順序存儲方式存儲的線性表具有順序存儲結構，一般稱之為順序表。換言之，在程序中采用定長的一維數(shù)組，按照順序存儲方式存儲的線性表，被稱為順序表。若順序表中的元素按其值有序，則稱其為有序順序表。
????????在高級程序設計語言中，“數(shù)組”這種數(shù)據(jù)類型同樣具有隨機存儲的特性，因此用高級程序設計語言實現(xiàn)線性表的順序存儲結構時，通常選擇數(shù)組。因此，數(shù)組的長度就是順序表的最大長度（MaxSize），順序表的實際長度為length，其值必須小于等于MaxSize。
// 定義順序表結構體
typedef struct {
int data[MAX_SIZE]; // 用數(shù)組存儲元素
int length; // 順序表的長度
} SeqList;結構體基礎知識：
【重拾C語言】八、表單數(shù)據(jù)組織——結構體（類型、類型別名、直接/間接訪問；典例：復數(shù)、成績單）-CSDN博客https://blog.csdn.net/m0_63834988/article/details/133793105?spm=1001.2014.3001.5502
2. 順序表的操作? ? ??
// 初始化順序表
void initSeqList(SeqList *list) {
list->length = 0;
}
a. 插入操作
????????插入操作用于向順序表中插入一個新的元素：需要將插入位置之后的所有元素依次后移一位，為新元素騰出空間，并將新元素放入目標位置。
int insert(SeqList *list, int position, int element) {
if (position < 0 || position > list->length || list->length == MAX_SIZE) {
return 0; // 插入位置非法或順序表已滿，插入失敗
}
// 將插入位置之后的元素依次后移一位
for (int i = list->length - 1; i >= position; i--) {
list->data[i + 1] = list->data[i];
}
// 在插入位置放入新元素
list->data[position] = element;
list->length++;
return 1; // 插入成功
}b. 刪除操作
????????刪除操作用于從順序表中刪除指定位置的元素：需要將刪除位置之后的所有元素依次前移一位，覆蓋被刪除的元素，同時將順序表的長度減一。
int delete(SeqList *list, int position) {
if (position < 0 || position >= list->length) {
return 0; // 刪除位置非法，刪除失敗
}
// 將刪除位置之后的元素依次前移一位
for (int i = position + 1; i < list->length; i++) {
list->data[i - 1] = list->data[i];
}
list->length--;
return 1; // 刪除成功
}c. 查找操作
????????查找操作可以根據(jù)元素的值進行查找，也可以根據(jù)位置進行查找。
- 對于按值查找，需要遍歷順序表的所有元素，逐個比較元素的值；
- 對于按位置查找，直接通過索引訪問數(shù)組中的元素即可。
int search(SeqList *list, int element) {
for (int i = 0; i < list->length; i++) {
if (list->data[i] == element) {
return i; // 找到元素，返回索引
}
}
return -1; // 未找到元素
}d. 修改操作
????????修改操作用于修改順序表中指定位置的元素的值：可以通過索引直接訪問到目標位置的元素，并進行修改。
????????在順序存儲結構中，插入和刪除操作可能需要移動大量元素，導致時間復雜度較高。而查找和修改操作可以在常數(shù)時間內(nèi)完成，時間復雜度為O(1)。文章來源：http://www.zghlxwxcb.cn/news/detail-776276.html
int modify(SeqList *list, int position, int newElement) {
if (position < 0 || position >= list->length) {
return 0; // 修改位置非法，修改失敗
}
list->data[position] = newElement;
return 1; // 修改成功
}e. 代碼實例
#include <stdio.h>
#define MAX_SIZE 100
// 定義順序表結構體
typedef struct {
int data[MAX_SIZE]; // 用數(shù)組存儲元素
int length; // 順序表的長度
} SeqList;
// 初始化順序表
void initSeqList(SeqList *list) {
list->length = 0;
}
// 插入操作
int insert(SeqList *list, int position, int element) {
if (position < 0 || position > list->length || list->length == MAX_SIZE) {
return 0; // 插入位置非法或順序表已滿，插入失敗
}
// 將插入位置之后的元素依次后移一位
for (int i = list->length - 1; i >= position; i--) {
list->data[i + 1] = list->data[i];
}
// 在插入位置放入新元素
list->data[position] = element;
list->length++;
return 1; // 插入成功
}
// 刪除操作
int delete(SeqList *list, int position) {
if (position < 0 || position >= list->length) {
return 0; // 刪除位置非法，刪除失敗
}
// 將刪除位置之后的元素依次前移一位
for (int i = position + 1; i < list->length; i++) {
list->data[i - 1] = list->data[i];
}
list->length--;
return 1; // 刪除成功
}
// 查找操作（按值查找）
int search(SeqList *list, int element) {
for (int i = 0; i < list->length; i++) {
if (list->data[i] == element) {
return i; // 找到元素，返回索引
}
}
return -1; // 未找到元素
}
// 修改操作
int modify(SeqList *list, int position, int newElement) {
if (position < 0 || position >= list->length) {
return 0; // 修改位置非法，修改失敗
}
list->data[position] = newElement;
return 1; // 修改成功
}
int main() {
SeqList list;
initSeqList(&list);
// 在順序表中插入元素
insert(&list, 0, 10);
insert(&list, 1, 20);
insert(&list, 2, 30);
// 刪除順序表中的元素
delete(&list, 1);
// 查找順序表中的元素
int index = search(&list, 30);
if (index != -1) {
printf("元素30的索引為：%d\n", index);
} else {
printf("未找到元素30\n");
}
// 修改順序表中的元素
modify(&list, 0, 40);
return 0;
}
?文章來源地址http://www.zghlxwxcb.cn/news/detail-776276.html
到了這里，關于【數(shù)據(jù)結構】線性表（一）線性表的定義及其基本操作（順序表插入、刪除、查找、修改）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
