考点猜测
编程题最大可能来源。
链接方式存储的线性表简称为链表。
- 用一组任意的存储单元存储表
- 每个数据元素(ai)不但包含元素值(data)，还必须存储相邻数据元素(ai-1)或(ai+1)的地址。
¶ 单链表
每个节点包含两个域，data存储该节点的元素，next存储下一节点的地址
分为有表头和无表头
¶ 操作
¶ 插入
s->next = p->next; // 1.s的 后 继 指 向p的 后 继
p->next = s; // 2.p的 后 继 指 向s
时间复杂度：
¶ 删除
q = p->next; // 1.q指 向 待 删 除 节 点
p->next = q->next; // 2.p的 后 继 指 向q的 后 继
free(q); // 3.释 放q节 点
不要忘记释放q节点。
时间复杂度：
¶ 无表头单链表
数据结构定义：
typedef struct node{
char Element;
struct node* Link;
}Node; //节点类型定义
typedef Node* List //头指针定义
List head;
空表的时候：list==null
¶ 头插法
【链表的头插法，数据结构与算法完整代码动画，考研408 期末考试数据结构】
struct Node *head = NULL;
void insertHead(int e){
Node *newNode = (Node *)malloc(sizeof(Node));
newNode -> data = e;
newNode -> next = head;
head = newNode;
}
时间复杂度：
¶ 尾插法
struct Node* head;
void insertLast(int e){
Node *newNode = (Node *)malloc(sizeof(Node));
newNode -> data = e;
newNode -> next = NULL;
if(head == NULL){
head = newNode;
}
else{
Node* lastNode = head;
while(lastNode->next != NULL){
lastNode = lastNode -> next;
} //寻找尾节点
lastNode -> next = newNode;
}
}
时间复杂度：
¶ 有表头单链表
数据结构定义：
typedef struct node{
char Element;
struct node* Link;
}Node; //节点类型定义
typedef Node* List //头指针定义
List head = (Node*) malloc(sizeof(Node)); //头节点定义
head -> next = NULL;
同无表头
表头结点位于表的最前端，本身不带数据
表头节点（头节点）后的第一个节点（整个链表的第一个数据节点）称为首元节点。
有表头单链表简化在哪里？
无表头单链表需要区分空表时头指针为NULL的情况，而有表头单链表即使是空表，仍然存在头节点，头指针不为空。所以在寻找有表头单链表的最后一个元素时，直接按照判定一个普通节点是否有后继（node->next != NULL）即可。
¶ 头插法
List head = (List)malloc(sizeof(List))
List_Insert(int e){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = e;
newNode->next = head->next;
head->next = newNode;
}
时间复杂度：
¶ 尾插法
这里令头节点中存储链表的长度。
List head = (List)malloc(sizeof(List));
head->next = NULL;
head->data = 0;
void insertLast(int e){
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = e;
newNode->next = NULL;
Node *lastNode = head;
while(lastNode->next != NULL){
lastNode = lastNode->next;
}
lastNode->next = newNode;
head->data++;
}
时间复杂度：
¶ 遍历求表长
int GetListLength(List p)
{
int length = 0;
while(p->next != NULL){
p = p->next;
length++;
}
return length;
}
时间复杂度：
¶ 返回位i的数据
char GetListNode(List p,int i){
int j=0;
while(p!=NULL && j<i){
p = p-next;
j++;
}
if(p==NULL || j>i)
return -1;
return p->data;
}
¶ 循环链表
最后一个结点的next指针不为0(NULL)，而是指向了表的前端。从任意结点出发均能找到其他结点。
- 判断空表的条件：
head == head->next
- 判断表尾节点的条件
head == p->next
¶ 双链表
双链表一般被设计为带表头结点的循环双链表，便于操作
单个节点的结构：
循环双链表结构：
- 判断空表的条件：
head == head->pri == head->next
数据结构定义：
typedef struct node{
struct node* prior;
char data;
struct node* next;
}Node;
¶ 操作
¶ 插入
将px节点插到p节点前：
px->next=p; //1.令px后继指针指向p
px->prior=p->prior; //2.令px的前驱指针指向p的前驱
p->prior=px; //3.令p的前驱指针指向px
px->prior->next=px; //4.令px前驱指针指向px
插入前：
插入后：
¶ 删除
将节点p删除：
p->next->prior=p->prior; //1.让p的后继指向p的前驱
p->prior->next=p->next; //2.让p的前驱指向p的后继
free(p); //3.释放节点p的空间
¶ 约瑟夫斯问题
问题描述：N 个人围成一圈，从某人开始报数，数到 k 的人出圈，然后从下一个
人继续报数，求出圈顺序
使用顺序表实现：
void Josephus(List *input_queue, int removeIndex, List *output_queue){
int out_pos = 0;
int i = 0;
while(input_queue->Length)
{
for(i = 0; i<removeIndex-1; i++)
out_pos = (out_pos+1) %input_queue->Length;
T_chd output_data;
Remove(input_queue, out_pos, &output_data);
Append(output_queue, output_data);
}
}
¶ 作业
题目：
令X=（x1, x2,…,xn）和Y=（y1, y2,…,ym）是两个带表头的单链表，编写程序合并X和Y并存储在新的带表头节点的双链表M中，
运行过程中，X和Y通过键盘输入字符构建单链表，合并后打印双链表M的数据。
链表的定义：
主函数：
节点插入函数：
请写出combin_list函数。
DList combin_list(List x, List y){
List px = x->next;
List py = y->next;
DList list_m = InitDList();
while(px ||py){
if(px){
InsertDNode(list_m, px->data, 0);
px = px->next;
}
if(py){
InsertDNode(list_m, py->data, 0);
py = py->next;
}
}
return list_m;
}