/** 链表是由N个结点链接起来的
* 单链表 ： 每个结点只有一个指针域,（单方向）
*
* 结点由两部分组成：数据域和指针域
* 数据域 -> 存储数据元素
* 指针域 -> 存储结点之间的位置关系。 如单链表 只存储后继位置的指针
*
*/
/** 头结点和头指针的异同
*
* 头指针 是指向链表第一个结点的指针；若链表有头结点，则是指向头结点的指针
* 头指针具有标识的作用，常用来指代链表的名字
* 无论链表是否为空，头指针均不为空。<头指针必须存在>
*
* 头结点 是为了操作的统一和方便而设立的，放在第一元素的结点之前 方便在第一元素前插入结点和删除第一结点
* <头结点不是必须存在的要素>
*/
1.插入结点
插入结点
1.s->next = p->next 先让p的后续结点改为s的后续结点
2.p->next = s 再把s变为p的后续结点
2.头插法
头插法
3.结点删除
删除结点
#include <stdio.h>
#include <stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef int ElemType;
typedef struct node {
ElemType data;
struct node *next;
} Node,*LinkList;
/** 此处的小写 node代表结构体的标签名，Node和*LinkList代表新类型 */
/** 用指针引用结构体变量的方式是 ==> (*指针变量).成员名 or 指针变量名->成员名 or 结构体变量.成员名
* 注意：*p两边的括号不可省略， 因为成员运算符 '.' 的优先级高于指针运算符'*'
* 指针变量 p 指向的是结构体变量Node第一个成员的地址，
* ->是指向结构体成员运算符，它的优先级 同结构体成员运算符'.' 一样高
*
*/
/** 头插法初始化 头插法是创建了一个节点 一直放在头部*/
void createList_Head (LinkList *list, int n) {
*list = (LinkList)malloc(sizeof(Node));
(*list)->next = NULL;
for (int i =0; i < n; i++) {
LinkList p = (LinkList)malloc(sizeof(Node));
p->data = I;
p->next = (*list)->next;
(*list)->next = p;
printf("create address %d %p\n",i,p);
}
}
/** 尾插法初始化*/
void createList_tail(LinkList *list, int n) {
*list = (LinkList)malloc(sizeof(Node));
(*list)->next = NULL;
LinkList p = (*list);
for (int i = 0; i < n; i++) {
LinkList node = (LinkList)malloc(sizeof(Node));
node->data = I;
p->next = node;
p = node;
}
p->next = NULL;
}
/** 遍历数据*/
void iteraotrList (LinkList *list) {
LinkList p = *list;
p=p->next;
while (p) {
printf("++current is data is %d,address is %p\n",p->data,p);
p=p->next;
}
}
/** 查找第i个位置的元素*/
Status GetElem(LinkList list, int i, ElemType *e) {
int j;
LinkList p;
p = list->next;
j = 1;
while (p && j<i) {
p = p->next;
++j;
}
if (!p || j>i) {
return ERROR;
}
*e = p->data;
return OK;
}
/** 插入*/
Status insertElem(LinkList *list,int i,ElemType e) {
int j = 1;
LinkList p,insertNode;
p = *list;
while (p && j < i) {
p= p->next;
++j;
}
if (!p || j > i) {
return ERROR;
}
insertNode =(LinkList)malloc(sizeof(Node));
insertNode->data = e;
insertNode->next = p->next;
p->next = insertNode;
return OK;
}
/** 删除第i个位置的节点，并返回删除的元素*/
Status list_delete(LinkList *list,int i, ElemType *e) {
LinkList p,q;
p = *list;
int j = 1;
while (p->next && j < i) {
p = p->next;
++j;
}
if (j > i || !(p->next)) {
return ERROR;
}
q = p->next;
*e = q->data;
p->next = q->next;
free(q);
return OK;
}
/** 清链表的时候 用了两个指针，一个指向将要删除的节点，另一个指向下一个节点*/
Status clearList(LinkList *list) {
LinkList p,q;
p = (*list)->next;
while (p) {
q = p->next;
free(p);
p=q;
}
(*list)->next = NULL;
return OK;
}
#pragma mark - 敲黑板 这是重点
/** 翻转链表
* 需要借助两个指针
* 一个指针负责指向next去递归剩下的数据;
* 一个指针负责指向当前的结点,将当前结点的指针反指 相当于重新生成一个链表 然后执行头插法
*/
LinkList k_reverseList(LinkList header) {
LinkList currentNodel = header;
header = NULL;
while (currentNodel) {
//取出当前结点，next反指与原来链表断开联系,并移动头结点
LinkList m = currentNodel;
m->next = header;
header = m;
//移动到下一个结点
currentNodel = currentNodel->next;
}
return header;
}
#pragma mark -使用
void k_node_test() {
LinkList list;
//头插法生成链表，并遍历
createList_Head(&list, 10);
iteraotrList(&list);
// //翻转链表
printf("\n\n");
list = k_reverseList(list);
iteraotrList(&list);
// //尾插法生成链表，并遍历
// printf("\n\n");
// createList_tail(&list, 10);
// iteraotrList(&list);
//
// //在某个位置插入数据
// printf("\n\n");
// insertElem(&list, 2, 20);
// iteraotrList(&list);
//
// //删除某个位置的数据，并返回元素
// printf("\n\n");
// ElemType deleteEle;
// list_delete(&list, 5, &deleteEle);
// iteraotrList(&list);
// printf("清空链表\n");
// clearList(&list);
}
