王道考研数据结构第三章知识点总结

**王道考研数据结构第三章知识点总结**

第三章是《王道考研数据结构》中的一个重要部分，涵盖了线性表的基本概念、线性表的存储方式以及线性表的运算。下面我们将对这些内容进行详细的总结和分析。

**3.1 线性表的基本概念**

线性表是指元素之间存在一一对应关系的数据结构，通常表现为一个序列或链条。线性表可以分为两类：顺序存储和链式存储。

* **顺序存储**：在内存中连续地存放线性表中的所有元素。
* **链式存储**：每个元素的地址不一定相邻，通过指针来连接各个元素。

**3.2 线性表的存储方式**

线性表有两种基本的存储方式：顺序存储和链式存储。

###3.2.1 顺序存储在内存中连续地存放线性表中的所有元素。这种存储方式通常使用数组来实现。

c// 顺序存储的线性表示例typedef struct {
 int data[10]; // 存储数据 int length; // 表长} SeqList;

int main() {
 SeqList list;
 list.length =5;
 for (int i =0; i < list.length; i++) {
 scanf("%d", &list.data[i]);
 }
 printf("线性表元素:");
 for (int i =0; i < list.length; i++) {
 printf("%d ", list.data[i]);
 }
 return0;
}

###3.2.2 链式存储每个元素的地址不一定相邻，通过指针来连接各个元素。这种存储方式通常使用链表来实现。

c// 链式存储的线性表示例typedef struct Node {
 int data; // 存储数据 struct Node* next; // 指向下一个结点的指针} Node;

typedef struct {
 Node* head; // 头结点 Node* tail; // 尾结点 int length; // 表长} LinkList;

int main() {
 LinkList list;
 list.length =5;
 for (int i =0; i < list.length; i++) {
 Node node;
 scanf("%d", &node.data);
 if (list.head == NULL) {
 list.head = &node;
 list.tail = &node;
 } else {
 list.tail->next = &node;
 list.tail = &node;
 }
 }
 printf("线性表元素:");
 Node* p = list.head;
 while (p != NULL) {
 printf("%d ", p->data);
 p = p->next;
 }
 return0;
}

**3.3 线性表的运算**

线性表支持以下基本运算：

* **插入**:在指定位置插入一个新元素。
* **删除**:从指定位置删除一个元素。
* **查找**:找到指定元素的位置。
* **排序**:对线性表进行排序。

这些运算可以分别使用顺序存储和链式存储来实现。下面我们将对这些内容进行详细的总结和分析。

###3.3.1 插入插入是指在指定位置插入一个新元素。这种操作需要考虑到线性表的存储方式。

#### 顺序存储在顺序存储中，插入可以使用数组的索引来实现。

c// 顺序存储中的插入示例void insert(SeqList* list, int index, int data) {
 if (index < 0 || index > list->length) {
 printf("错误：索引越界。
");
 return;
 }
 for (int i = list->length; i > index; i--) {
 list->data[i] = list->data[i -1];
 }
 list->data[index] = data;
 list->length++;
}

#### 链式存储在链式存储中，插入需要考虑到新元素的位置和指针的更新。

c// 链式存储中的插入示例void insert(LinkList* list, int index, int data) {
 Node node;
 node.data = data;
 if (index ==0) {
 node.next = list->head;
 list->head = &node;
 } else if (index == list->length) {
 list->tail->next = &node;
 list->tail = &node;
 } else {
 Node* p = list->head;
 for (int i =0; i < index -1; i++) {
 p = p->next;
 }
 node.next = p->next;
 p->next = &node;
 }
 list->length++;
}

###3.3.2 删除删除是指从指定位置删除一个元素。这种操作需要考虑到线性表的存储方式。

#### 顺序存储在顺序存储中，删除可以使用数组的索引来实现。

c// 顺序存储中的删除示例void delete(SeqList* list, int index) {
 if (index < 0 || index >= list->length) {
 printf("错误：索引越界。
");
 return;
 }
 for (int i = index; i < list->length -1; i++) {
 list->data[i] = list->data[i +1];
 }
 list->length--;
}

#### 链式存储在链式存储中，删除需要考虑到被删除元素的位置和指针的更新。

c// 链式存储中的删除示例void delete(LinkList* list, int index) {
 if (index ==0) {
 Node* p = list->head;
 list->head = p->next;
 free(p);
 } else if (index == list->length -1) {
 Node* p = list->tail;
 list->tail = p->prev;
 list->tail->next = NULL;
 free(p);
 } else {
 Node* p = list->head;
 for (int i =0; i < index -1; i++) {
 p = p->next;
 }
 Node* q = p->next;
 p->next = q->next;
 free(q);
 }
 list->length--;
}

###3.3.3 查找查找是指找到指定元素的位置。这种操作需要考虑到线性表的存储方式。

#### 顺序存储在顺序存储中，查找可以使用数组的索引来实现。

c// 顺序存储中的查找示例int find(SeqList* list, int data) {
 for (int i =0; i < list->length; i++) {
 if (list->data[i] == data) {
 return i;
 }
 }
 return -1;
}

#### 链式存储在链式存储中，查找需要考虑到元素的位置和指针的更新。

c// 链式存储中的查找示例int find(LinkList* list, int data) {
 Node* p = list->head;
 while (p != NULL) {
 if (p->data == data) {
 return0; // 找到元素，返回位置 }
 p = p->next;
 }
 return -1; // 未找到元素，返回-1}

###3.3.4 排序排序是指对线性表进行排序。这种操作需要考虑到线性表的存储方式。

#### 顺序存储在顺序存储中，排序可以使用数组的索引来实现。

c// 顺序存储中的排序示例void sort(SeqList* list) {
 for (int i =0; i < list->length -1; i++) {
 for (int j =0; j < list->length - i -1; j++) {
 if (list->data[j] > list->data[j +1]) {
 int temp = list->data[j];
 list->data[j] = list->data[j +1];
 list->data[j +1] = temp;
 }
 }
 }
}

#### 链式存储在链式存储中，排序需要考虑到元素的位置和指针的更新。

c// 链式存储中的排序示例void sort(LinkList* list) {
 Node* p = list->head;
 while (p