一、初始化
初始化是使用单链表前必须要进行的操作。因为一个新的单链表并没有指向任何节点，所以必须将其初始化为空，即头指针指向NULL。
typedef struct Node{
int data;
struct Node *next;
}Node, *LinkList;
//初始化链表
LinkList initList(){
Node *head = (Node*)malloc(sizeof(Node));
head->next = NULL;
return head;
}以上代码中，我们定义了一个结构体Node，包括数据域data和指针域next。而LinkList类型是struct Node*的别名，可以直接使用LinkList作为函数返回值。
二、插入元素
单链表的插入操作分为头插法和尾插法。其中头插法将新节点插入到链表头部，尾插法则将新节点插入链表尾部。
1.头插法
头插法是将每个新节点插入到链表头部。主要步骤有：
1.创建新节点p，设置其数据域为x，并将其next指针指向头节点的下一个节点。
2.将头节点的next指针指向新节点p。
//头插法插入节点
void insertHead(LinkList L, int x){
Node *p = (Node*)malloc(sizeof(Node));
p->data = x;
p->next = L->next;
L->next = p;
}2.尾插法
尾插法是将每个新节点插入到链表尾部。主要步骤也很简单：
1.创建新节点p，设置其数据域为x，并将其next指针指向NULL。
2.找到链表最后一个节点，并将其next指针指向新节点p。
//尾插法插入节点
void insertTail(LinkList L, int x){
Node *p = (Node*)malloc(sizeof(Node));
p->data = x;
p->next = NULL;
Node *cur = L;
while(cur->next) cur = cur->next;
cur->next = p;
}三、删除元素
删除元素就是将链表中指定的节点删除。其步骤包括：
1.查找需要删除的节点。
2.将待删除节点的前一个节点的next指针指向待删除节点的下一个节点。
3.释放待删除节点的内存。
//删除链表中第i(i>=1)个节点
void deleteNode(LinkList L, int i){
Node *cur = L;
for(int j = 1; j next;
if(!cur || !cur->next) return; //链表长度不够i个
Node *del = cur->next;
cur->next = del->next;
free(del);
}四、遍历链表
遍历链表就是按照链表的顺序将节点的值输出。遍历操作很简单，只需要从头节点的下一个节点开始依次遍历到链表结尾即可。
//遍历链表并输出每个节点的值
void traverse(LinkList L){
Node *cur = L->next;
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
}五、查找元素
查找元素需要遍历链表，查找目标节点的值与链表中每个节点的值逐一比较。如果查找到目标节点，则返回该节点在链表中的位置，否则返回0。
//查找值为x的节点并返回其位置
int search(LinkList L, int x){
int i = 1;
Node *cur = L->next;
while(cur){
if(cur->data == x) return i;
cur = cur->next;
i++;
}
return 0;
}六、完整代码示例
typedef struct Node{
int data;
struct Node *next;
}Node, *LinkList;
//初始化链表
LinkList initList(){
Node *head = (Node*)malloc(sizeof(Node));
head->next = NULL;
return head;
}
//头插法插入节点
void insertHead(LinkList L, int x){
Node *p = (Node*)malloc(sizeof(Node));
p->data = x;
p->next = L->next;
L->next = p;
}
//尾插法插入节点
void insertTail(LinkList L, int x){
Node *p = (Node*)malloc(sizeof(Node));
p->data = x;
p->next = NULL;
Node *cur = L;
while(cur->next) cur = cur->next;
cur->next = p;
}
//删除链表中第i(i>=1)个节点
void deleteNode(LinkList L, int i){
Node *cur = L;
for(int j = 1; j next;
if(!cur || !cur->next) return; //链表长度不够i个
Node *del = cur->next;
cur->next = del->next;
free(del);
}
//遍历链表并输出每个节点的值
void traverse(LinkList L){
Node *cur = L->next;
while(cur){
printf("%d ", cur->data);
cur = cur->next;
}
}
//查找值为x的节点并返回其位置
int search(LinkList L, int x){
int i = 1;
Node *cur = L->next;
while(cur){
if(cur->data == x) return i;
cur = cur->next;
i++;
}
return 0;
}
//测试代码
int main(){
LinkList L = initList();
insertHead(L, 1);
insertTail(L, 2);
insertTail(L, 3);
deleteNode(L, 2);
traverse(L);
printf("\n%d\n", search(L, 2));
return 0;
}原创文章，作者：QMLY，如若转载，请注明出处：https://www.506064.com/n/131908.html
微信扫一扫 
支付宝扫一扫 