数据结构--单向链表

1．按位置查找返回元素的值

// 按位置查找元素
int query_num(node_p P, int pos) {if (P == NULL) {return 0;}if (pos <= 0 || pos > P->len) {printf("所选插入位置不准确\n");return 0;}int i;node_p H = P;for (i = 0; i < pos; i++, H = H->next);return H->data;}

2.按值修改(多个一样的值改第一个)

// 按值修改
void update_value(node_p P, int target, int value) {if (P == NULL) {return;}node_p H = P->next;int i;for (i = 0; i < P->len; i++, H = H->next) {if (target == H->data) {H->data = value;break;}}if (i == P->len) {printf("没有要修改的值\n");}
}

3.单向链表的逆置

//13、逆置
void reverse_link(node_p H)
{if(H==NULL){return;}if(empty_link(H)){return;}if(H->next->next==NULL){return;}//提前将第二个结点开始链表保存下来node_p p = H->next->next;node_p q;//让原来的第一个结点变成现在的最后一个结点H->next->next = NULL;//循环头插//只要p的指向的结点不为空说明要头插while(p!=NULL){//先保留下一个要头插结点的首地址q = p->next;//头插p->next = H->next;H->next = p;p = q;  //让p指向下一个要头插的结点}
}

4.尝试实现单向循环链表
        a.特点：尾结点指向头结点
        b.创建
        c.头插、尾插、任意位置插入
        d.头删、尾删、任意位置删除

头文件

#ifndef __LOOP_H__
#define __LOOP_H__
#include <stdio.h>
#include <stdlib.h>
typedef struct node
{union{int len;int data;};struct node *next;
}node,*node_p;
//1、申请单向循环链表
node_p create_loop();
//2、申请结点
node_p create_node(int value);
//3、判空
int empty_loop(node_p H);
//4、头插
void insert_head(node_p H,int value);
//5、尾插
void insert_tail(node_p H,int value);
//6、头删
void dele_head(node_p H);
//7、尾删
void dele_tail(node_p H);
//8、输出
void show_loop(node_p H);
node_p delete(node_p H);
//10、删除头结点后的单向循环链表的输出
void show_no_head(node_p H);#endif

功能文件

#include "loop.h"
//1、申请单向循环链表
node_p create_loop()
{node_p H = (node_p)malloc(sizeof(node));if(H==NULL){printf("申请空间失败\n");return NULL;}H->len=0;H->next = H;return H;
}
//2、申请结点
node_p create_node(int value)
{node_p new = (node_p)malloc(sizeof(node));new->next = NULL;new->data = value;return new;
}
//3、判空
int empty_loop(node_p H)
{if(H==NULL){return -1;}return H->next==H?1:0;
}
//4、头插
void insert_head(node_p H,int value)
{if(H==NULL){return;}node_p new = create_node(value);//新结点的后继指向头结点的后继new->next = H->next;H->next = new;H->len++;
}
//5、尾插
void insert_tail(node_p H,int value)
{if(H==NULL){return;}node_p p=H; //p用于遍历链表，找到最后一个结点while(p->next!=H){p=p->next;}node_p new = create_node(value);//退出循环后p指向最后一个结点p->next = new;new->next=H;//new->next = p->next;//p->next = new;H->len++;
}
//6、头删
void dele_head(node_p H)
{if(H==NULL){return;}if(empty_loop(H)){return;}//保存要删除结点的首地址node_p p=H->next;//让头结点指向原来的第二个结点H->next=p->next;free(p);H->len--;return;
}
//7、尾删
void dele_tail(node_p H)
{if(H==NULL){return;}if(empty_loop(H)) {return;}node_p p=H;//尾删要找倒数第二个结点while(p->next->next!=H){p=p->next;}//循环退出时p指向倒数第二个节点node_p q=p->next;p->next=H;free(q);//free(p->next);  //先释放最后一个结点//p->next = H;H->len--;
}
//8、输出
void show_loop(node_p H)
{if(H==NULL){return;}if(empty_loop(H)){return;}node_p p = H->next;while(p!=H){printf("%d->",p->data);p = p->next;}printf("H\n");
}
//9、删除单向循环链表的头结点
//删除头结点后需要返回给主调函数处新的链表的头
node_p delete(node_p H)
{if(H==NULL){return NULL;}if(empty_loop(H)){return NULL;}//保存第一个结点的首地址node_p p = H->next;//找到最后一个结点node_p tail = H->next;while(tail->next!=H){tail=tail->next;}//让最后一个结点的后继节点变成原来的第一个结点tail->next = p;//释放头结点free(H);return p;
}
//10、删除头结点后的单向循环链表的输出
void show_no_head(node_p H)
{if(H==NULL){return;}//不需要再判空//因为没有头结点了传过来的结点只要不是空说明链表中就有元素node_p p = H;do{printf("%d->",p->data);p = p->next;}while(p!=H);printf("H\n");//需要第一次循环时不判断条件//只能使用do··while
}

主函数文件

#include "loop.h"
int main()
{node_p H = create_loop();insert_head(H,67);insert_head(H,90);insert_head(H,34);insert_head(H,8);show_loop(H);printf("H->next=%p\n",H->next);H = delete(H);  //删除头结点后链表已经没有头结点了//H需要重新被赋值show_no_head(H);return 0;
}