### 数据结构算法举例知识点
#### 一、顺序表算法
**1. 使用结构描述顺序表**
在本例中，顺序表被定义为一种线性结构，通过数组来存储元素，并用一个整数变量记录表的实际长度。具体实现如下：
```c
#define ListSize 100 // 假定表容量为100
typedef int DataType; // DataType代表的类型为int型
typedef struct {
DataType data[ListSize]; // 数组data用于存放表结点
int length; // 当前表的长度（结点数）
} SeqList;
```
**2. 顺序表的初始化**
顺序表初始化的目的是将表的长度设置为0，表示此时表为空。
```c
void initList(SeqList *L) {
// 将当前表L的表长L->length置为0
L->length = 0;
}
```
**3. 求顺序表的长度**
该函数返回顺序表的实际长度，即存储的元素个数。
```c
int LengthList(SeqList *L) {
// 返回顺序表L的表长L->length
return L->length;
}
```
**4. 取表元**
该函数返回顺序表中指定位置上的元素值。
```c
DataType GetList(SeqList *L, int i) {
// 返回顺序表L的第i个结点的值L->data[i-1]
return L->data[i - 1];
}
```
**5. 顺序表插入操作**
该函数实现了将一个新元素插入到顺序表中的指定位置。需要注意的是，如果插入位置不合理或者表已满，则无法进行插入操作。
```c
void InsertList(SeqList *L, DataType t, int i) {
int j;
if (i < 1 || i > L->length + 1) {
puts("插入位置错");
exit(0);
}
if (L->length >= ListSize) {
puts("表满不能插入");
exit(0);
} else {
for (j = L->length - 1; j >= i - 1; j--) {
L->data[j + 1] = L->data[j]; // 结点依次后移
}
L->data[i - 1] = t; // 插入t
L->length++; // 表长加1
}
}
```
**6. 顺序表删除操作**
该函数实现了从顺序表中删除指定位置的元素。同样地，如果删除位置不合理或者表为空，则无法执行删除操作。
```c
void DeleteList(SeqList *L, int i) {
int j;
if (i < 1 || i > L->length) {
puts("删除位置错");
exit(0);
}
if (L->length == 0) {
puts("空表不能删除");
exit(0);
} else {
for (j = i; j <= L->length - 1; j++) {
L->data[j - 1] = L->data[j]; // 结点依次前移
}
L->length--; // 表长减1
}
}
```
**7. 顺序表按值查找**
该函数实现了在顺序表中查找特定值的元素。如果找到了该值，则返回其在表中的位置；如果没有找到，则返回-1。
```c
int SearchList(SeqList *L, DataType t) {
int i = 1;
while (i <= L->length && L->data[i - 1] != t) {
i++;
}
if (L->data[i - 1] == t) {
return i;
} else {
return -1;
}
}
```
#### 二、链表算法
**1. 链表结点的描述**
链表中的每个结点由两部分组成：数据域和指针域。数据域用于存储数据，而指针域则指向下一个结点。
```c
typedef char DataType; // 定义结点的数据域类型
typedef struct node {
// 结点类型定义
DataType data; // 结点数据域
struct node *next; // 结点指针域
} ListNode; // 结构体类型标识符
typedef ListNode *LinkList; // 定义指向链表的头指针
```
**2. 节点的申请和释放**
动态分配内存用于创建新的结点，并使用`free`函数释放结点所占用的内存。
```c
ListNode *p; // 定义一个指向结点的指针
p = (ListNode *)malloc(sizeof(ListNode)); // 申请节点
free(p); // 释放节点
```
**3. 头插法建单链表算法的实现**
该函数通过头插法构建单链表。每次读入一个字符就创建一个新的结点并将其插入到链表头部。
```c
LinkList CreatListF(void) {
DataType ch;
LinkList head; // 头指针
ListNode *s; // 工作指针
head = NULL; // 链表开始为空
printf("请输入链表各结点的数据:\n");
while ((ch = getchar()) != '\n') {
s = (ListNode *)malloc(sizeof(ListNode));
s->data = ch;
s->next = head;
head = s;
}
return head;
}
```
**4. 尾插法建单链表算法的实现**
该函数通过尾插法构建单链表。每次读入一个字符就创建一个新的结点并将其插入到链表尾部。
```c
LinkList CreatListR(void) {
DataType ch;
LinkList head; // 头指针
ListNode *s, *r; // 工作指针
head = NULL; // 链表开始为空
r = NULL; // 尾指针初值为空
while ((ch = getchar()) != '\n') {
s = (ListNode *)malloc(sizeof(ListNode));
s->data = ch;
if (head == NULL) {
head = s; // 新结点插入空表
} else {
r->next = s; // 将新结点插到链表尾
r = s; // 尾指针指向新表尾
}
}
if (r != NULL) {
r->next = NULL; // 设置最后一个结点的next为NULL
}
return head;
}
```
以上是文档中提到的主要数据结构算法示例。这些算法不仅限于顺序表和链表的操作，还涉及到基本的数据结构概念及其在C语言中的实现方式。对于理解和掌握基础的数据结构知识具有重要的参考价值。
