线性表:
由一组具有相同数据类型的元素组成的有序序列。线性表中的元素之间存在一个前后关系，每个元素都有一个唯一的前驱元素（除了第一个元素）和一个唯一的后继元素（除了最后一个元素）。
常见操作包括插入元素、删除元素、查找元素、获取元素等。
实现方式：
顺序表（Sequential List）：
顺序表使用数组来实现，元素在内存中连续存储。通过数组的索引可以直接访问元素，因此随机访问的时间复杂度为O(1)。但是插入和删除操作需要移动元素，时间复杂度为O(n)，其中n是元素的数量。适合于频繁进行随机访问的场景。
链表（Linked List）：
链表使用节点（Node）来存储元素，每个节点包含一个数据项和一个指向下一个节点的指针。链表的元素在内存中可以是不连续的，通过指针可以实现元素之间的连接。链表的插入和删除操作比较灵活，时间复杂度为O(1)。但是随机访问的时间复杂度为O(n)，需要从头节点开始顺序查找。适合于频繁进行插入和删除操作的场景。
链表相关代码（C语言）：
以下是单链表在C语言中的基本操作示例：
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点结构
struct Node {
int data; // 数据域
struct Node* next; // 指针域，指向下一个节点
};
// 初始化链表
void initList(struct Node** head) {
*head = NULL; // 将头指针置为空，表示链表为空
}
// 在链表末尾添加节点
void appendNode(struct Node** head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
} else {
struct Node* temp = *head;
while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}
}
// 在链表指定位置插入节点
void insertNode(struct Node** head, int data, int position) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (position == 0) {
newNode->next = *head;
*head = newNode;
} else {
struct Node* temp = *head;
int count = 0;
while (temp != NULL && count < position - 1) {
temp = temp->next;
count++;
}
if (temp == NULL) {
printf("Invalid position\n");
return;
}
newNode->next = temp->next;
temp->next = newNode;
}
}
// 删除链表指定位置的节点
void deleteNode(struct Node** head, int position) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
struct Node* temp = *head;
if (position == 0) {
*head = temp->next;
free(temp);
} else {
int count = 0;
struct Node* prev = NULL;
while (temp != NULL && count < position) {
prev = temp;
temp = temp->next;
count++;
}
if (temp == NULL) {
printf("Invalid position\n");
return;
}
prev->next = temp->next;
free(temp);
}
}
// 查找链表中指定元素的位置
int searchNode(struct Node* head, int data) {
struct Node* temp = head;
int position = 0;
while (temp != NULL) {
if (temp->data == data) {
return position;
}
temp = temp->next;
position++;
}
return -1; // 表示未找到
}
// 修改链表指定位置的节点值
void modifyNode(struct Node* head, int position, int newData) {
struct Node* temp = head;
int count = 0;
while (temp != NULL && count < position) {
temp = temp->next;
count++;
}
if (temp == NULL) {
printf("Invalid position\n");
return;
}
temp->data = newData;
}
// 打印链表
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// 释放链表内存
void freeList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
struct Node* nextNode = temp->next;
free(temp);
temp = nextNode;
}
}
int main() {
struct Node* head;
initList(&head);
// 在链表末尾添加节点
appendNode(&head, 10);
appendNode(&head, 20);
appendNode(&head, 30);
appendNode(&head, 40);
// 打印链表
printf("List: ");
printList(head); // 输出: 10 20 30 40
// 在链表指定位置插入节点
insertNode(&head, 25, 2);
// 打印链表
printf("List after insertion: ");
printList(head); // 输出: 10 20 25 30 40
// 删除链表指定位置的节点
deleteNode(&head, 3);
// 打印链表
printf("List after deletion: ");
printList(head); // 输出: 10 20 25 40
// 查找链表中指定元素的位置
int position = searchNode(head, 25);
printf("Position of 25: %d\n", position); // 输出: 2
// 修改链表指定位置的节点值
modifyNode(head, 1, 15);
// 打印链表
printf("List after modification: ");
printList(head); // 输出: 10 15 25 40
// 释放链表内存
freeList(head);
return 0;
}
