1 单向链表
1.1 线性表-单链表节点长相如下图：
单链表节点
1.2 线性表-单链表逻辑结构如下图：
单链表逻辑状态
1.3 线性表-单链表增加头结点逻辑结构如下图：
头节点的数据域可以自定义用来记录相关数据，也可以置空不用，看个人习惯。
单链表增加头节点的好处：
• 便于⾸元结点处理；
• 便于空表和⾮空表的统一处理。
空表逻辑结构与增加头节点的单向链表逻辑结构
1.4 线性表-链表结构与顺序存储结构优缺点对⽐
存储分配方式：
• 顺序存储结构⽤⼀段连续的存储单元依次存储线性表的数据元素。
• 单链表采⽤链式存储结构，⽤⼀组任意的存储单元存放线性表的元素。
时间性能:
①查找
• 顺序存储 O(1)。
• 单链表O(n)。
②插⼊和删除
• 存储结构需要平均移动⼀个表⻓⼀半的元素，时间O(n)。
• 单链表查找某位置后的指针后，插⼊和删除为 O(1)。
空间性能:
• 顺序存储结构需要预先分配存储空间，分太⼤浪费空间，分⼩了发⽣上溢出。
• 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。
2 单向循环链表
单向循环链表实际上就是单向链表的尾节点指向头结点，最终形成一个环。
单向循环链表逻辑结构
2.1 单向循环链表的创建用代码设计实现一下
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;/* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int ElemType;/* ElemType类型根据实际情况而定，这里假设为int */
//定义结点
typedef struct Node{
ElemType data;
struct Node *next;
}Node;
typedef struct Node * LinkList;
/*
循环链表创建!
2种情况:① 第一次开始创建; ②已经创建,往里面新增数据。
1. 判断是否第一次创建链表
YES->创建一个新结点,并使得新结点的next 指向自身; (*L)->next = (*L);
NO-> 找链表尾结点,将尾结点的next = 新结点. 新结点的next = (*L);
*/
Status CreateList(LinkList *L){
int item;
LinkList temp = NULL;
LinkList target = NULL;
printf("输入节点的值，输入0结束\n");
while(1){
scanf("%d",&item);
if(item==0) break;
//如果输入的链表是空。则创建一个新的节点，使其next指针指向自己 (*head)->next=*head;
if(*L==NULL) {
*L = (LinkList)malloc(sizeof(Node));
if(!L)exit(0);
(*L)->data=item;
(*L)->next=*L;
}else {
//输入的链表不是空的，寻找链表的尾节点，使尾节点的next=新节点。新节点的next指向头节点
for (target = *L; target->next != *L; target = target->next);
temp=(LinkList)malloc(sizeof(Node));
if(!temp) return ERROR;
temp->data=item;
temp->next=*L; //新节点指向头节点
target->next=temp;//尾节点指向新节点
}
}
return OK;
}
2.2 打印所有的节点
//2 遍历循环链表，循环链表的遍历最好用do while语句，因为头节点就有值
void show(LinkList p){
//如果链表是空
if(p == NULL){
printf("打印的链表为空!\n");
return;
}else{
LinkList temp;
temp = p;
do{
printf("%5d",temp->data);
temp = temp->next;
}while (temp != p);
printf("\n");
}
}
2.3 单向循环链表插入数据
Status ListInsert(LinkList *L, int place, int num){
LinkList temp ,target;
int i;
if (place == 1) {
//如果插入的位置为1,则属于插入首元结点,所以需要特殊处理
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2. 找到链表最后的结点_尾结点,
//3. 让新结点的next 执行头结点.
//4. 尾结点的next 指向新的头结点;
//5. 让头指针指向temp(临时的新结点)
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for (target = *L; target->next != *L; target = target->next);
temp->next = *L;
target->next = temp;
*L = temp;
}else {
//如果插入的位置在其他位置;
//1. 创建新结点temp,并判断是否创建成功,成功则赋值,否则返回ERROR;
//2. 先找到插入的位置,如果超过链表长度,则自动插入队尾;
//3. 通过target找到要插入位置的前一个结点, 让target->next = temp;
//4. 插入结点的前驱指向新结点,新结点的next 指向target原来的next位置 ;
temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = num;
for ( i = 1,target = *L; target->next != *L && i != place - 1; target = target->next,i++) ;
temp->next = target->next;
target->next = temp;
}
return OK;
}
2.4 单向循环链表删除元素
Status LinkListDelete(LinkList *L,int place){
LinkList temp,target;
int i;
//temp 指向链表首元结点
temp = *L;
if(temp == NULL) return ERROR;
if (place == 1) {
//①.如果删除到只剩下首元结点了,则直接将*L置空;
if((*L)->next == (*L)){
(*L) = NULL;
return OK;
}
//②.链表还有很多数据,但是删除的是首结点;
//1. 找到尾结点, 使得尾结点next 指向头结点的下一个结点 target->next = (*L)->next;
//2. 新结点做为头结点,则释放原来的头结点
for (target = *L; target->next != *L; target = target->next);
temp = *L;
*L = (*L)->next;
target->next = *L;
free(temp);
}else {
//如果删除其他结点--其他结点
//1. 找到删除结点前一个结点target
//2. 使得target->next 指向下一个结点
//3. 释放需要删除的结点temp
for(i=1,target = *L;target->next != *L && i != place -1;target = target->next,i++) ;
temp = target->next;
target->next = temp->next;
free(temp);
}
return OK;
}
2.5 单向循环链表查询值
int findValue(LinkList L,int value){
int i = 1;
LinkList p;
p = L;
//寻找链表中的结点 data == value
while (p->data != value && p->next != L) {
i++;
p = p->next;
}
//当尾结点指向头结点就会直接跳出循环,所以要额外增加一次判断尾结点的data == value;
if (p->next == L && p->data != value) {
return -1;
}
return i;
}
2.6 单向循环链表的逆序
因为是单向链表：
• 断开节点前需要引用下一个节点，要不然就找不到了。
• 单向链表没法直接找到前一个节点，所以需要一个额外的引用。
Status ListReverse(LinkList *L) {
if (L == NULL) return ERROR;
LinkList prev, current, next;
prev = *L;
current = prev->next;
next = current->next;
while (current != *L) { // 当current为头结点时结束，再移动就找不到尾节点了
current->next = prev; // 指针反向
// 依次移动节点
prev = current;
current = next;
next = next->next;
}
current->next = prev; // current为头结点，但还没有反向，所以先反向
*L = prev; // 头结点逆序后应为原来的尾节点
return OK;
}
2.7 单向循环链表倒数第n个数
核心思想是两个指针，保证2个指针间隔为 n，后面的指针到头的时候，另一个指针指向倒数第 n 个数。
Status ListLocateKBackwards(LinkList L, int n, ElemType *elem) {
if (L == NULL) return ERROR;
LinkList target, tmp;
target = L;
tmp = L->next;
// 移动tmp使得两个指针间隔k
for (int i = 1; i < n && tmp != L; tmp = tmp->next, i++);
if (tmp == L && i < n) return ERROR;
// tmp走到头的时候，倒数第k个节点被target指针指向
do {
target = target->next;
tmp = tmp->next;
} while (tmp != L);
*elem = target->data;
return OK;
}
