24考研数据结构-线性表4

**线性表**

线性表是一种基本的数据结构，它是由一组元素按照一定的顺序排列而成的。线性表中的每个元素都有一个唯一的索引或下标，通过这个下标可以访问到相应的元素。

###1. 线性表的定义线性表可以用以下几种方式来定义：

* **顺序存储法**：将线性表中的所有元素连续地存放在一块内存中。
* **链式存储法**：每个元素都有一个指针域，指向下一个元素。

###2. 线性表的基本操作线性表支持以下几种基本操作：

* **插入**：将一个新元素插入到线性表中。
* **删除**：从线性表中删除一个元素。
* **查找**：在线性表中找到一个指定的元素。
* **排序**：对线性表中的所有元素进行排序。

###3. 线性表的应用线性表有很多应用，例如：

* **栈**：一种后进先出的数据结构，可以用来实现括号匹配、表达式求值等功能。
* **队列**：一种先进先出的数据结构，可以用来实现进程调度、消息传递等功能。

###4. 线性表的实现线性表可以使用以下几种方式来实现：

* **顺序存储法**：将线性表中的所有元素连续地存放在一块内存中。
* **链式存储法**：每个元素都有一个指针域，指向下一个元素。

###5. 线性表的时间复杂度线性表的基本操作的时间复杂度如下：

* **插入**：O(n)
* **删除**：O(n)
* **查找**：O(n)
* **排序**：O(n log n)

###6. 线性表的空间复杂度线性表的基本操作的空间复杂度如下：

* **插入**：O(1)
* **删除**：O(1)
* **查找**：O(1)
* **排序**：O(n)

###7. 线性表的代码示例以下是线性表的一些代码示例：

c// 顺序存储法实现线性表typedef struct {
 int data[10];
 int length;
} SeqList;

void init(SeqList *list) {
 list->length =0;
}

int insert(SeqList *list, int pos, int value) {
 if (pos < 1 || pos > list->length +1) return -1;
 for (int i = list->length; i >= pos; --i) {
 list->data[i] = list->data[i-1];
 }
 list->data[pos-1] = value;
 ++list->length;
 return0;
}

int delete(SeqList *list, int pos) {
 if (pos < 1 || pos > list->length) return -1;
 for (int i = pos; i < list->length; ++i) {
 list->data[i-1] = list->data[i];
 }
 --list->length;
 return0;
}

int search(SeqList *list, int value) {
 for (int i =0; i < list->length; ++i) {
 if (list->data[i] == value) return i +1;
 }
 return -1;
}

c// 链式存储法实现线性表typedef struct Node {
 int data;
 struct Node *next;
} Node;

typedef struct {
 Node *head;
 Node *tail;
 int length;
} LinkList;

void init(LinkList *list) {
 list->head = NULL;
 list->tail = NULL;
 list->length =0;
}

int insert(LinkList *list, int pos, int value) {
 if (pos < 1 || pos > list->length +1) return -1;
 Node *node = malloc(sizeof(Node));
 node->data = value;
 node->next = NULL;
 if (list->head == NULL) {
 list->head = node;
 list->tail = node;
 } else {
 for (Node *p = list->head; p != NULL && p->next != NULL; p = p->next) {
 if (pos-1 == p->length +1) break;
 }
 if (pos-1 == p->length +1) {
 node->next = p->next;
 p->next = node;
 } else {
 Node *q = list->head;
 for (; q != NULL && q->next != NULL; q = q->next) {
 if (q->length == pos-2) break;
 }
 node->next = q->next;
 q->next = node;
 }
 }
 ++list->length;
 return0;
}

int delete(LinkList *list, int pos) {
 if (pos < 1 || pos > list->length) return -1;
 Node *node = NULL;
 if (pos ==1) {
 node = list->head;
 list->head = list->head->next;
 if (list->head == NULL) list->tail = NULL;
 } else {
 for (Node *p = list->head; p != NULL && p->next != NULL; p = p->next) {
 if (pos-1 == p->length +1) break;
 }
 node = p->next;
 p->next = p->next->next;
 }
 free(node);
 --list->length;
 return0;
}

int search(LinkList *list, int value) {
 Node *node = list->head;
 while (node != NULL && node->data != value) {
 node = node->next;
 }
 if (node == NULL || node->data != value) return -1;
 return0;
}