链表表示和实现
单链表的按值查找
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
typedef struct node NODE;
NODE* create() {
int t;
NODE *head, *p, *q;
head = (NODE*)malloc(sizeof(NODE));
p = head;
while (1) {
printf("输入链表需要存放的数(输入负数结束)");
scanf("%d", &t);
if (t < 0) {
break;
}
q = (NODE*)malloc(sizeof(NODE));
q->data = t;
p->next = q;
p = q;
}
p->next = NULL;
return head;
}
void print(NODE* head) {
int t;
NODE* p;
p = head->next;
while (p != NULL) {
t = p->data;
printf("%d ", t);
p = p->next;
}
printf("\n");
}
/*
这是一个在链表按值查找目标元素的的函数
该函数需要链表的头指针,和需要查找的元素
该函数将返回目标节点的地址
*/
NODE* search(NODE*head, int e) {
NODE* p;//定义一个指针来指向需要查找的节点
p = head->next;//让指针指向首元节点
while (p != NULL) {//如果p不为空就进行循环
if (p->data == e) {
break;//找到了直接跳出循环
}
p = p->next;//没找到向后移动指针
}
return p;//返回指针的值,如果没找到的话指针的值将为null
}
int main() {
NODE* head;
int e;
head = create();
print(head);
scanf("%d", &e);
printf("%p", search(head, e));//打印出目标元素的地址
return 0;
}
单链表的按值查找
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *next;
};
typedef struct node NODE;
NODE* create() {
int t;
NODE *head, *p, *q;
head = (NODE*)malloc(sizeof(NODE));
p = head;
while (1) {
printf("输入链表需要存放的数(输入负数结束)");
scanf("%d", &t);
if (t < 0) {
break;
}
q = (NODE*)malloc(sizeof(NODE));
q->data = t;
p->next = q;
p = q;
}
p->next = NULL;
return head;
}
void print(NODE* head) {
int t;
NODE* p;
p = head->next;
while (p != NULL) {
t = p->data;
printf("%d ", t);
p = p->next;
}
printf("\n");
}
/*
这是一个在链表按值查找目标元素的的函数
该函数需要链表的头指针,和需要查找的元素
该函数将返回目标节点序号
*/
int search(NODE*head, int e) {
NODE* p;
p = head->next;
int i = 1;//定义一个记录序号的变量,让其初始化为1
while (p != NULL) {
if (p->data == e) {
break;//如果找到了直接跳出循环
}
//没找到将指针向后移动,同时i++;
p = p->next;
i++;
}
if (p == NULL) {//如果p==null说明没找到返回-1
return -1;
} else {
return i;//如果找到了返回i的值
}
}
int main() {
NODE* head;
int e;
head = create();
print(head);
scanf("%d", &e);
printf("%d", search(head, e));
return 0;
}
建立两个循环链表,并且将两个链表合并
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
NODE* create() {
int t;
NODE *head, *q, *p, *T;
//定义头指针,目标节点的指针,尾指针
//还有需要做为返回值的尾指针T
head = (NODE*)malloc(sizeof(NODE));
p = head;
while (1) {
scanf("%d", &t);
if (t == 0) {
break;
}
q = (NODE*)malloc(sizeof(NODE));
q->data = t;
p->next = q;
p = q;
}
p->next = head; //和建立单链表不同的是
//p->next不再指向null，而是直接指向头指针head
T = p; //将尾指针的值赋值给T，
return T;//返回循环链表的尾指针
}
/*
该函数用来遍历一个循环链表
需要一个参数就是链表的尾指针
该函数没有返回结果
*/
void print(NODE* T) {
NODE* head, *p;
//我们还是从head指针开始
head = T->next;
//头指针存放在尾指针T的next域里面
p = head->next; //让p指向首元结点
int t;
while (p != head) {
t = p->data;
printf("%d ", t);
p = p->next;
}
//因为我们从首元结点开始遍历，但是最后的尾指针指向的不只是null,而是指向
//了头节点的地址所以循环条件要改成p！=head，其他都相同
}
/*
该函数用来合并两个循环链表，变成一个循环链表
需要合并的两个循环链表的尾指针
该函数将返回合并好的循环链表的尾指针
*/
NODE* combination(NODE* Ta, NODE* Tb) {
NODE* p_temp;
p_temp = Ta->next;//定义一个临时变量来储存a链表头节点的地址
Ta->next = Tb->next->next;//让a链表的尾指针指向b链表的首元节点
free(Tb->next);//释放b链表的头结点
Tb->next = p_temp;//让b链表的尾指针所指向的next域指向a链表的头节点
//这样两个循环链表合并成了一个循环链表
return Tb;//返回新链表的尾指针
}
int main() {
NODE *Ta, *Tb, *Tc;
printf("请创建a链表以0结束\n");
Ta = create();
print(Ta);
printf("\n请创建b链表以0结束\n");
Tb = create();
print(Tb);
Tc = combination(Ta, Tb);
printf("\n合并完成之后的链表为\n");
print(Tc);
return 0;
}
链表的操作
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
//链表的创建
NODE* create() {
int t;//定义临时数据变量
NODE *head, *p, *q;//定义头指针head,末尾指针p，以及临时指针q.
head = (NODE*)malloc(sizeof(NODE));
//分配一个头结点，并且让头指针指向头结点
p = head;//让末尾指针也指向头结点
while (1) {
printf("请输入链表元素(输入负数结束)：\n");
scanf("%d", &t);
if (t < 0) {//如果搜集到负数；
p->next = NULL; //末尾指针所指向的指针域的值为null；
break;
}
q = (NODE*)malloc(sizeof(NODE));//每次循环分配一个结点，并且让临时指针q指向该结点
q->data = t;//用这种方式给刚分配的结点赋值，因为q指向该结点
p->next = q;//让末尾指针的指针域指向刚分配的结点，这样新结点就挂在了链表的后面
p = q;//移动末尾指针p让它始终指向末尾
}
return head;//最后返回该链表的头指针
}
//链表的遍历
void print(NODE *head) {
//遍历一个链表需要这个链表的头指针
NODE *p;//定义一个指针变量p，用来作为寻找指针
p = head->next; //这里是让p指向首结点
while (p != NULL) { //只要p不为空
printf("%d ", p->data); //打印出当前的数据域
p = p->next; //同时指针向后移动。
}
printf("\n");
}
//链表的删除函数
//需要头指针的值和需要删除元素的值
//该函数没有返回结果nt
void dele(NODE *head, int a) {
NODE *q, *p; //定义两个指针一个为前驱结点的指针一个为目标结点的指针
q = head; //让前驱结点指向头结点
p = q->next; //让q结点指向首结点
while (p != NULL) {
if (p->data == a) { //如果找到了目标结点
q->next = p->next; //直接让前驱结点指向目标结点的后续结点
free(p);//然后释放目标结点
break;//跳出循环
} else {
q = p; //如果目标指针p,的指针域不是目标值
//q向后移动一个
p = p->next;
//p指向p->next,也是向后移动一个
}
}
if (p == NULL) { //也就是说找到最后都，没找到目标结点
printf("没有符合条件的结点\n");
}
}
/*
在链表中插入结点
在链表中插入结点，是一种非常常见的，相对复杂的链表操作
要想在链表中插入一个新结点，首先必须确定插入的位置
一般来说通过查找第一个符合条件的结点，来确定插入的位置
带头结点的单向链表的插入步骤
1.首先，为新结点分配内存空间，并且存入数据
2.在链表中查找与插入位置相对应的目标结点
3.将新结点插入到目标结点之前（或之后）.
在目标结点之后插入新结点，相对容易实现，同时也很少使用
所以我们现在只讨论在目标结点之前插入新结点的情况
例如在一个带头结点的单向动态链表，所有结点按照数据域的值升序排列
要求传入一个结点使所有的结点仍然按照数据域的值升序排列
1.确定新结点的插入位置
新结点应该插入到所有结点值小于它的结点之后，第一个结点值不小于它的结点之前
由于链表的前端开始查找，按照结点值由大到小的顺序进行比较
因此应该将第一个结点值不小于新结点的结点，作为查找的目标结点
然后在其前面插入新结点。
2.如何在目标结点之前插入新结点？
要让目标结点的前驱结点的指针域指向新结点，另一方面还要让新结点的指针域指向目标结点
由于在单项链表的结点中只有指向后续结点的指针，而没有指向前驱结点的指针
因此，无法通过目标结点获得其前驱结点的地址
所以，需要定义三个指针变量r,p,q，分别指向新结点，目标结点以及前驱结点
*/
void insert(NODE *head,int t)
{
//插入链表结点函数，head为头指针，t为待插入结点值
NODE *p,*q,*r;
r=(NODE*)malloc(sizeof(NODE));//给新结点分配内存
//3.动态创建一个新结点，并且使得指针r指向它
//4.将形参传入的正整数存入新结点的数据域中
//5.使得指针q，p分别指向头结点以及后续结点;
r->data=t;//存入数据
q=head;
p=head->next;
while(p!=NULL){
if(p->data<t){//查找目标结点
q=p;
p=p->next;
}
else
{
break;
}
}
q->next=r;
r->next=p;
//6.若p==null，说明新结点的值很大，转向第九步。
//7.若p所指向的结点的值小于新结点的值，则使得所指向的p所指向的结点
//使得p指向下一个结点，
//8.否则，在q所指向的结点之间插入新结点：然后返回主调函数
//q->next=r;
//r->next=p;
//9.在末结点（即q所指向的结点）之后连接新结点.然后返回主调函数
//q->next=r;
//r->next=p;
return ;
}
int main() {
NODE *head;
head = create();
print(head);
int data;
while(1){
printf("请输入插入的正整数(以负数结束)：");
scanf("%d",&data);
if(data<0){
break;
}
insert(head,data);//插入新结点
print(head);
}
// int data;
// while (1) {
// printf("输入您想要删除的数据(输入负数结束):\n");
// scanf("%d", &data);
// if (data < 0) {
// break;
// }
// dele(head, data);
// print(head);
// }
return 0;
}
链表的创建和遍历
链表的创建和遍历
#include <stdio.h>
#include <stdlib.h>
struct node { //链表节点结构体类型
int data;//数据域
struct node *next;//指针域
};
typedef struct node NODE;//定义类型别名
/*
//创建动态链表函数
该函数不需要参数
返回的是一个node类型的指针，也就是头指针
*/
node *create() {
NODE *head, *p, *q;
int t;//用于暂存输入的成绩
head = (NODE*)malloc(sizeof(NODE));//创建头节点
//让头指针head来指向头节点
//3.让末节点指针p指向头节点（相当于空链表的末节点）
p = head;
while (1) {
printf("请输入一个整数成绩(以负数结束)：");
scanf("%d", &t);
//4.输入一个成绩并且暂存
if (t < 0) {
break;
}
//5.动态创建一个新的节点，并且q指向它
q = (NODE*)malloc(sizeof(NODE));
q->data = t;
//6.将已知的成绩存入新节点的数据域中
//7.将新节点连接到链表中，使得当前末节点的指针域指向新节点
p->next = q;
//8.调整末节点指针的值，使其指向已连接到链表的新节点
p = q;
//9.转向第5步，进行循环
//10.将末节点的指针域赋值为空指针null，作为链表的结束标志
}
p->next = NULL; //设置链表的结束标志
return head;//返回头指针
}
void print(NODE *head) {
/*
带头节点的单向链表的遍历步骤
1.通过头指针找到头节点
2.若头节点的指针域为空指针结束空链表
3.否则，跟随链表节点的指针域，找到下一个节点，并输出其数据域的值
4.遇到链表的结束标志为止
*/
//2.定义一个指向链表节点的指针变量p
NODE *p;
//3.使指针p指向头结点的后续节点
p = head->next;
if (p == NULL) {
printf("该链表为空！\n");
} else {
//输出当前节点的数据
printf("链表中的数据为:\n");
while (p != NULL) {
printf("->%d", p->data);
//使得p指向下一个节点
p = p->next;
}
}
//4.如果p==null，则输出“链表为空”的信息，然后返回主调函数
//5.输出p所指节点的数据域的值
//6.使得p指向下一个节点。p=p->next;
//7.若p！=NULL，则转向第5步
//8.否则返回主调函数
return;
}
int main() {
/*
这里我们需要定义3个指针变量
头指针head
末节点指针p
新节点指针q
然后动态创建一个新节点，作为头节点，
并使用头指针指向头节点
*/
NODE *h;
h = create(); //创建链表获得头指针
printf("%p", h);
print(h);//遍历链表，输出数据
return 0;
}
链表的清除
今天在b站听的数据结构网课讲的链表的清除现在我自己来实现一下
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
typedef struct node NODE;
NODE *create(int n)
{
NODE *head,*p,*q;
int t;
head = (NODE*)malloc(sizeof(NODE));
p=head;
for(int i=0;i<n;i++){
q=(NODE*)malloc(sizeof(NODE));
scanf("%d",&t);
q->data=t;
p->next=q;
p=q;
}
p->next=NULL;
return head;
}
void print(NODE*head)
{
int t;
NODE *p;
p=head->next;
// if(p==NULL){
// printf("该链表为空链表\n");
// }
while(p!=NULL){
t=p->data;
printf("%d ",t);
p=p->next;
}
printf("\n");
}
/*
这是一个清除链表的函数
清除就是将链表保留头节点和头指针，同时让头节点的指针域指向null
该函数需要链表的头指针
该函数没有返回结果
*/
void clear(NODE *L)
{
//其实清空链表和销毁链表的操作差不多只有一点点不同
NODE *p,*q;
//在销毁链表的函数中我们让L始终指向p所指向的后续节点
//现在我们需要重新定义一个指针q来始终指向p的后续节点
//因为我们的指针L需要一直保留
q=L->next;//让q一开始就指首元节点
while(q!=NULL){
p=q;//让p和q指向同一个节点
q=q->next;//让q向后移动
free(p);//释放p节点
}
L->next=NULL;//不要忘记将头节点的指针域变为空
printf("链表已经全部清除\n");
printf("L=%p\n",L);
printf("头节点的指针域的地址为%p",L->next);
}
int main()
{
int n;
NODE *head;
scanf("%d",&n);
head=create(n);
print(head);
clear(head);
print(head);
return 0;
}
链表的删除
链表的删除分享一下
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
//链表的创建
NODE* create() {
int t;//定义临时数据变量
NODE *head, *p, *q;//定义头指针head,末尾指针p，以及临时指针q.
head = (NODE*)malloc(sizeof(NODE));
//分配一个头结点，并且让头指针指向头结点
p = head;//让末尾指针也指向头结点
while (1) {
printf("请输入链表元素(输入负数结束)：\n");
scanf("%d", &t);
if (t < 0) {//如果搜集到负数；
p->next = NULL; //末尾指针所指向的指针域的值为null；
break;
}
q = (NODE*)malloc(sizeof(NODE));//每次循环分配一个结点，并且让临时指针q指向该结点
q->data = t;//用这种方式给刚分配的结点赋值，因为q指向该结点
p->next = q;//让末尾指针的指针域指向刚分配的结点，这样新结点就挂在了链表的后面
p = q;//移动末尾指针p让它始终指向末尾
}
return head;//最后返回该链表的头指针
}
//链表的遍历
void print(NODE *head) {
//遍历一个链表需要这个链表的头指针
NODE *p;//定义一个指针变量p，用来作为寻找指针
p = head->next; //这里是让p指向首结点
while (p != NULL) { //只要p不为空
printf("%d ", p->data); //打印出当前的数据域
p = p->next; //同时指针向后移动。
}
printf("\n");
}
//链表的删除函数
//需要头指针的值和需要删除元素的值
//该函数没有返回结果nt
void dele(NODE *head, int a) {
NODE *q, *p; //定义两个指针一个为前驱结点的指针一个为目标结点的指针
q = head; //让前驱结点指向头结点
p = q->next; //让q结点指向首结点
while (p != NULL) {
if (p->data == a) { //如果找到了目标结点
q->next = p->next; //直接让前驱结点指向目标结点的后续结点
free(p);//然后释放目标结点
break;//跳出循环
} else {
q = p; //如果目标指针p,的指针域不是目标值
//q向后移动一个
p = p->next;
//p指向p->next,也是向后移动一个
}
}
if (p == NULL) { //也就是说找到最后都，没找到目标结点
printf("没有符合条件的结点\n");
}
}
int main() {
NODE *head;
head = create();
print(head);
int data;
while (1) {
printf("输入您想要删除的数据(输入负数结束):\n");
scanf("%d", &data);
if (data < 0) {
break;
}
dele(head, data);
print(head);
}
return 0;
}
链表的删除2
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
//链表的创建
NODE* create() {
int t;//定义临时数据变量
NODE *head, *p, *q;//定义头指针head,末尾指针p，以及临时指针q.
head = (NODE*)malloc(sizeof(NODE));
//分配一个头结点，并且让头指针指向头结点
p = head;//让末尾指针也指向头结点
while (1) {
printf("请输入链表元素(输入负数结束)：\n");
scanf("%d", &t);
if (t < 0) {//如果搜集到负数；
p->next = NULL; //末尾指针所指向的指针域的值为null；
break;
}
q = (NODE*)malloc(sizeof(NODE));//每次循环分配一个结点，并且让临时指针q指向该结点
q->data = t;//用这种方式给刚分配的结点赋值，因为q指向该结点
p->next = q;//让末尾指针的指针域指向刚分配的结点，这样新结点就挂在了链表的后面
p = q;//移动末尾指针p让它始终指向末尾
}
return head;//最后返回该链表的头指针
}
//链表的遍历
void print(NODE *head) {
//遍历一个链表需要这个链表的头指针
NODE *p;//定义一个指针变量p，用来作为寻找指针
p = head->next; //这里是让p指向首结点
while (p != NULL) { //只要p不为空
printf("%d ", p->data); //打印出当前的数据域
p = p->next; //同时指针向后移动。
}
printf("\n");
}
//链表的删除函数
//需要头指针的值和需要删除元素的值
//该函数没有返回结果nt
void dele(NODE *head, int a) {
NODE *q, *p; //定义两个指针一个为前驱结点的指针一个为目标结点的指针
q = head; //让前驱结点指向头结点
p = q->next; //让q结点指向首结点
while (p != NULL) {
if (p->data == a) { //如果找到了目标结点
q->next = p->next; //直接让前驱结点指向目标结点的后续结点
free(p);//然后释放目标结点
break;//跳出循环
} else {
q = p; //如果目标指针p,的指针域不是目标值
//q向后移动一个
p = p->next;
//p指向p->next,也是向后移动一个
}
}
if (p == NULL) { //也就是说找到最后都，没找到目标结点
printf("没有符合条件的结点\n");
}
}
/*
在链表中插入结点
在链表中插入结点，是一种非常常见的，相对复杂的链表操作
要想在链表中插入一个新结点，首先必须确定插入的位置
一般来说通过查找第一个符合条件的结点，来确定插入的位置
带头结点的单向链表的插入步骤
1.首先，为新结点分配内存空间，并且存入数据
2.在链表中查找与插入位置相对应的目标结点
3.将新结点插入到目标结点之前（或之后）.
在目标结点之后插入新结点，相对容易实现，同时也很少使用
所以我们现在只讨论在目标结点之前插入新结点的情况
例如在一个带头结点的单向动态链表，所有结点按照数据域的值升序排列
要求传入一个结点使所有的结点仍然按照数据域的值升序排列
1.确定新结点的插入位置
新结点应该插入到所有结点值小于它的结点之后，第一个结点值不小于它的结点之前
由于链表的前端开始查找，按照结点值由大到小的顺序进行比较
因此应该将第一个结点值不小于新结点的结点，作为查找的目标结点
然后在其前面插入新结点。
2.如何在目标结点之前插入新结点？
要让目标结点的前驱结点的指针域指向新结点，另一方面还要让新结点的指针域指向目标结点
由于在单项链表的结点中只有指向后续结点的指针，而没有指向前驱结点的指针
因此，无法通过目标结点获得其前驱结点的地址
所以，需要定义三个指针变量r,p,q，分别指向新结点，目标结点以及前驱结点
*/
void insert(NODE *head,int t)
{
//插入链表结点函数，head为头指针，t为待插入结点值
NODE *p,*q,*r;
r=(NODE*)malloc(sizeof(NODE));//给新结点分配内存
//3.动态创建一个新结点，并且使得指针r指向它
//4.将形参传入的正整数存入新结点的数据域中
//5.使得指针q，p分别指向头结点以及后续结点;
r->data=t;//存入数据
q=head;
p=head->next;
while(p!=NULL){
if(p->data<t){//查找目标结点
q=p;
p=p->next;
}
else
{
break;
}
}
q->next=r;
r->next=p;
//6.若p==null，说明新结点的值很大，转向第九步。
//7.若p所指向的结点的值小于新结点的值，则使得所指向的p所指向的结点
//使得p指向下一个结点，
//8.否则，在q所指向的结点之间插入新结点：然后返回主调函数
//q->next=r;
//r->next=p;
//9.在末结点（即q所指向的结点）之后连接新结点.然后返回主调函数
//q->next=r;
//r->next=p;
return ;
}
int main() {
NODE *head;
head = create();
print(head);
int data;
while(1){
printf("请输入插入的正整数(以负数结束)：");
scanf("%d",&data);
if(data<0){
break;
}
insert(head,data);//插入新结点
print(head);
}
// int data;
// while (1) {
// printf("输入您想要删除的数据(输入负数结束):\n");
// scanf("%d", &data);
// if (data < 0) {
// break;
// }
// dele(head, data);
// print(head);
// }
return 0;
}
链表的销毁
今天在b站听的数据结构网课讲的链表的销毁现在我自己来实现一下
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
typedef struct node NODE;
NODE *create(int n)
{
NODE *head,*p,*q;
int t;
head = (NODE*)malloc(sizeof(NODE));
p=head;
for(int i=0;i<n;i++){
q=(NODE*)malloc(sizeof(NODE));
scanf("%d",&t);
q->data=t;
p->next=q;
p=q;
}
p->next=NULL;
return head;
}
void print(NODE*head)
{
int t;
NODE *p;
p=head->next;
while(p!=NULL){
t=p->data;
printf("%d ",t);
p=p->next;
}
printf("\n");
}
/*
这是一个销毁链表的函数
销毁也就是将链表全部的节点都清空包括头节点
该函数需要链表的头指针
该函数没有返回结果
*/
void destroy(NODE* L)
{
//在这一个函数中我们让L始终指向p的后续节点
NODE* p;//定义一个目标指针
while(L!=NULL){//只要L所指向的地方不为null，继续循环
p=L;//让目标节点p指向L所指向的节点
L=L->next;//让L指向p的后续节点，防止链表丢失
free(p);//释放目标节点
}
printf("链表已经销毁成功\n");
printf("L=%p\n",L);
printf("p=%p",p);
}
int main()
{
int n;
NODE *head;
scanf("%d",&n);
head=create(n);
print(head);
destroy(head);
return 0;
}
删除链表中的第i个元素
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
typedef struct node NODE;
NODE* create()
{
NODE *head,*q,*p;
int t;
head = (NODE*)malloc(sizeof(NODE));
p=head;
while(1){
printf("请输入结点元素(输入负数结束)\n");
scanf("%d",&t);
if(t==0){
break;
}
else
{
q=(NODE*)malloc(sizeof(NODE));
q->data=t;
p->next=q;
p=q;
}
}
p->next=NULL;
return head;
}
void print(NODE*head)
{
NODE *p;
int t;
p=head->next;
while(p!=NULL){
t=p->data;
printf("%d ",t);
p=p->next;
}
printf("\n");
}
//NODE* dele(NODE* head,int e)
//{
// int t;
// NODE* p,*q;
// q=head;
// p=q->next;
// while(p!=NULL){
// t=p->data;
// if(t==e){
// q->next=p->next;
// break;
// }
//q=p;
//p=q->next;
// }
//
// return head;
//
//
//
//}
NODE* dele(NODE* head,int i)
{
NODE *p;//用来指向目标节点的前驱结点
int j=0;//用来找到i-1位置在哪里
NODE *q;//用来指向目标结点并且释放它
p=head;
j=0;
while(p->next!=NULL && j<i-1){//当循环结束的时候,要么p->next==null,要么j==i-1
p=p->next;//p指针继续向后移动
j++;//同时j的值加1
}
if(p->next==NULL || j>i-1){//如果p->next==null这时候就说明目标序号超过了链表的长度
//如果j>i-1说明目标序号小于链表的长度
//我们直接退出就好
printf("输入的目标序号有误\n");
}
else
{
//如果找到了正确的目标值
q=p->next;//让指针q指向后续结点，方便一会释放
p->next=q->next;
//将目标结点的后续结点挂在目标结点的前驱结点的前面
free(q);//释放目标结点
}
return head;
}
int main()
{
NODE* head;
head=create();
print(head);
int e;
scanf("%d",&e);
head=dele(head,e);
print(head);
return 0;
}
头插法建立逆序链表
今天在学校oj上面做的一个题简单的分享一下
使用头插法建立逆序链表
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
/*
该函数的目的用来创建链表
该函数有一个参数就是需要创建的链表的长度
该函数的返回值为头指针的值
*/
NODE* create(int n) {
NODE *head, *p; //定义头指针head和目标指针p;
int t;
head = (NODE*)malloc(sizeof(NODE)); //分配一个头节点并且让头指针指向头节点
head->next = NULL; //将头节点的指针域赋值为空指针
for (int i = 0; i < n; i++) {
scanf("%d", &t);
p = (NODE*)malloc(sizeof(NODE)); //分配一个目标节点，并且让p指向它
p->data = t; //将数据存入目标节点的数据域中
//下面就是要将目标节点挂到头节点上
p->next = head->next; //这样把头节点指针域的值赋值给了目标目标节点的指针域
head->next = p; //然后将头节点指针域的指针指向目标节点，就将元素挂在了上面
//然后我在纸上演示了挂上第二个节点的过程和第一个没有任何区别，这就是引入头节点的好处吧
}
return head;//将头节点返回
}
/*
该函数的目的用来遍历链表
该函数有一个参数就是头指针的值
该函数没有返回值
*/
void print(NODE *head) {//对链表进行遍历
int count = 0; //这个是用来控制输出格式的我们不用管他
NODE *p;//定义一个目标指针
int t;//定义一个临时变量存储数据域的值
p = head->next;//让目标指针指向首节点
while (p != NULL) {//只要目标节点不为null，就执行循环
if (count != 0) {
printf(" ");
}
count++;
t = p->data;//将目标节点的值赋值给t
printf("%d", t);//将t的值打印出来
p = p->next; //让目标指针p向后移动直到null;
}
}
int main() {
int n;
NODE *head;//定义一个指针变量，来接收头指针的值
scanf("%d", &n);
head = create(n); //创建链表
print(head);//遍历链表
return 0;
}
头插法建立链表
#include <stdio.h>
#include <stdlib.h>
/*
先建立一个顺序的链表然后用头插法把这个链表逆序
*/
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
/*
创建一个链表以负数结束
*/
NODE* creat() {
int t;
NODE* head, *q, *p;//三个指针变量，分别是头指针head,临时指针q,尾指针p
head = (NODE*)malloc(sizeof(NODE));
p = head;// 让尾指针也指向头节点
while (1) {
scanf("%d", &t);
if (t == -1) {
break;
}
q = (NODE*)malloc(sizeof(NODE));
q->data = t;//给目标节点的数据域赋值
p->next = q;// 将目标节点挂在其前驱节点之后
p = q;//更新尾指针
}
q->next=NULL;//给最后一个节点的指针域赋值为null
return head;// 返回头节点
}
//用该函数对链表进行遍历
void print(NODE *head)
{
int count=0;
int t;
NODE *p;
p=head->next;
while(p!=NULL){
if(count!=0){
printf(" ");
}
count++;
t=p->data;
printf("%d",t);
p=p->next;
}
}
/*
该函数为链表逆置的函数
该函数需要的
*/
void reverse(NODE *head)
{
NODE *p,*q;//用p来指向目标节点，让q来保存目标节点的后续节点
// 防止后续节点的丢失
//1.将头节点切断，并且让q指向首节点
p=head->next;//让q指向首节点
head->next=NULL;//将头结点的指针域赋值为null
while(p!=NULL){
q=p->next;//用一个指针q来保存目标节点的后续节点
p->next=head->next;//让头节点指针域的指针值赋值给目标节点的指针域
head->next=p;//让头节点指向目标节点
p=q;//将目标节点向前移动
//通过循环这些代码，可以将链表元素全部逆置
}
}
int main() {
NODE *head;//定义一个指针变量用来储存头节点
head=creat();//将创建好的链表的头节点赋值给head
//print(head);
//printf("\n");
reverse(head);//调用链表逆转函数
print(head);//遍历链表
return 0;
}
顺序建立链表
这是我在学习的oj上面做的第一个链表的题目简单分享一下
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
NODE* create(int n) {
int t;//定义临时储存数据的变量t；
NODE *head, *p, *q;//定义头指针，尾指针，和储存临时变量的指针
head = (NODE*)malloc(sizeof(NODE));//动态分配一块内存，并且让头指针指向它。这就是头结点的地址；
p = head;//让末尾指针也指向头结点。当然我们一会会移动末尾指针
for(int i=0;i<n;i++){
scanf("%d",&t);
q=(NODE*)malloc(sizeof(NODE));//动态分配一块内存并且让q指向它
q->data=t;//将搜集到的t赋值给q指针所指向的数据域；
p->next=q;//如果是第一次会将首结点挂在头结点上面
p=q; //这里将q的值赋值给p，就是让p指向最后一个结点
}
p->next=NULL;//循环结束将最后一个结点的指针域赋值为null
return head;//将头指针返回
}
void print(NODE *head)//链表的遍历
{
int a=0;
NODE *p=head->next;//定义p，让p指向head->next;也就是p存放了首结点的地址
while(p!=NULL){//只要p的值不为null，进行循环
if(a!=0){
printf(" ");
}
a++;
printf("%d",p->data);//打印出p所指向的那个data
p=p->next;//然后将p指针后移
}
printf("\n");
}
int main() {
int n;
scanf("%d",&n);
NODE *p=create(n);
print(p);
return 0;
}
数据结构实验之链表五：单链表的拆分
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node
{
int data;
struct node* next;
};
typedef node NODE;
NODE* create(int n)
{
int t;
NODE* head,*q,*p;
head=(NODE*)malloc(sizeof(NODE));
p=head;
for(int i=0;i<n;i++){
scanf("%d",&t);
q=(NODE*)malloc(sizeof(NODE));
q->data=t;
p->next=q;
p=q;
}
p->next=NULL;
return head;
}//创建一个单链表
/*
改函数是将节点中的值为偶数的节点拿出来并且建立一个新链表
改函数需要原链表的头指针
改链表将返回新链表的头指针
*/
NODE* chaifen1(NODE* head,int* a)
{
NODE* T1;//新链表的头指针
NODE* Tp;//一直指向新链表的尾节点
NODE* Tq;//指向新分配的节点
T1=(NODE*)malloc(sizeof(NODE));//为新节点分配一个头节点
Tp=T1;//尾指针指向尾节点
int count=0;
NODE *p;//用指向传入链表的指针
p=head->next;
while(p!=NULL){//如果原链表不为空就执行循环
if(p->data%2==0){//如果该节点的数据域为偶数
Tq=(NODE*)malloc(sizeof(NODE));//动态分配一个新节点
Tq->data=p->data;//给新节点的数据域赋值
count++;//计数器加1
Tp->next=Tq;//将新节点挂在新链表上面
Tp=Tq;//移动新链表的尾指针
}
p=p->next;//移动用来遍历原链表的指针
}
Tp->next=NULL;//给新链表的尾节点的指针域赋值为null
*a=count;//将原链表有多少个偶数传回
return T1;//返回新链表的头指针
}
//这个和上面的函数相同只不过是用来计算奇数的
NODE* chaifen2(NODE* head,int* b)
{
NODE* T2;
NODE* Tp;
NODE* Tq;
T2=(NODE*)malloc(sizeof(NODE));
Tp=T2;
int count=0;
NODE *p;
p=head->next;
while(p!=NULL){
if((p->data)%2!=0){
Tq=(NODE*)malloc(sizeof(NODE));
Tq->data=p->data;
count++;
Tp->next=Tq;
Tp=Tq;
}
p=p->next;
}
Tp->next=NULL;
*b=count;
return T2;
}
/*
这是一个用来遍历链表的函数
*/
void print(NODE* head)
{
int t;
NODE* p;
p=head->next;
while(p!=NULL){
t=p->data;
printf("%d ",t);
p=p->next;
}
printf("\n");
}
int main()
{
NODE* head;
int a,b;
NODE* T1,*T2;
int n;
scanf("%d",&n);
head=create(n);
T1=chaifen1(head,&a);
T2=chaifen2(head,&b);
printf("%d %d\n",a,b);
print(T1);
print(T2);
return 0;
}
有序链表的归并
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
NODE *create(int n) {
int t;
NODE *head, *p, *q;
head = (NODE*)malloc(sizeof(NODE));
p = head;
for (int i = 0; i < n; i++) {
q = (NODE*)malloc(sizeof(NODE));
scanf("%d", &t);
q->data = t;
p->next = q;
p = q;
}
q->next = NULL;
return head;
}
void print(NODE*head) {
int count = 0;
int t;
NODE *p;
p = head->next;
while (p != NULL) {
if (count != 0) {
printf(" ");
}
count++;
t = p->data;
printf("%d", t);
p = p->next;
}
// printf("\n");
}
/*
该函数为归并有序链表的函数
该函数需要两个参数分别是两个链表的头指针
该函数将返回一个归并好了的有效链表的头指针
*/
NODE *merger(NODE* head1, NODE* head2) {
NODE *head3, *p1, *p2, *p3;
/*
这里定义了4个指针变量
指针head3为归并完成后链表的头指针
指针p1用来遍历第一个链表
指针p2用来遍历第二个链表
指针p3一直用来指向新生产链表的尾节点;
*/
head3 = (NODE*)malloc(sizeof(NODE));
/*
为新链表分配一个头节点,并且让头指针head3指向该节点
*/
p3 = head3;//让尾指针p3也指向头节点
p1 = head1->next;//让指针p1指向链表1的首节点
p2 = head2->next;//让指针p2指向链表2的首节点
while (p1 != NULL && p2 != NULL) {
//只要两链表都不为空就执行循环
if ((p1->data) < (p2->data)) {
p3->next = p1;//将p1所指向的节点挂在p3指向的节点的后面
p1 = p1->next;//p1指针向前移动
p3 = p3->next;//尾指针p3向前移动
} else {
p3->next = p2;//将p2所指向的节点挂在p3所指向的节点的后面
p2 = p2->next;//p2指针向前移动
p3 = p3->next;//尾指针p3向前移动
}
}
if (p1 == NULL) {
p3->next = p2;
/*
如果最后链表1先空
将链表2剩下的节点全部挂到新链表上面
*/
} else {
/*
如果最后链表2先空
将链表2剩下的节点全部挂到新链表上面
*/
p3->next = p1;
}
return head3;//返回新生成的链表的头指针
}
int main() {
NODE *head1, *head2, *head3;
int m, n;
scanf("%d %d", &m, &n);
head1 = create(m);
head2 = create(n);
// print(head1);
// print(head2);
head3 = merger(head1, head2);
print(head3);
return 0;
}
现在是2022.12.05今天又再pta上面做了一个类似的题目
再将代码简单的保存一下
下面是这个归并链表的函数代码
List Merge( List L1, List L2 ) {
List L3, p3, p1, p2;
L3 = (struct Node*)malloc(sizeof(struct Node));
p3 = L3; //p3始终指向新链表的末尾
p1 = L1->Next; //用p1指向L1链表
p2 = L2->Next; //用p2指向L2链表
while (p1 != NULL && p2 != NULL) { //当两个链表都不为空时开始循环
if (p1->Data < p2->Data) { //如果p1->data比较小
p3->Next = p1; //让p3指向p1
p3 = p1; //将p3移动到尾节点位置
p1 = p1->Next; //让p1指向下一个结点位置
} else { //当p2->data比较小的时候和上面相同只不过是操作的p2
p3->Next = p2;
p3 = p2;
p2 = p2->Next;
}
}
if (p1 == NULL) {
p3->Next = p2; //当p1为空的时候,将p2全部挂到p3上面
} else {
p3->Next = p1; //当p2为空的时候,将p1全部挂在p3上面
}
L1->Next = NULL; //将l1链表清空
L2->Next = NULL; //将l2链表清空
return L3;//返回新链表的头指针
}
约瑟夫问题
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
/*
该函数的目的是建立一个数据域的值为从1—n链表
该函数需要输入一个n
该函数的返回值是一个头指针
*/
NODE* create(int n) {
NODE* head, *q, *p;
head = (NODE*)malloc(sizeof(NODE));
head->data = 0;
p = head;
for (int i = 1; i <= n; i++) {
q = (NODE*)malloc(sizeof(NODE));
q->data = i;
p->next = q;
p = q;
}
p->next = head->next;//这里有点普通的循环链表有点不一样
//这里的尾指针指向首元节点,普通的循环链表都是头结点
return head;//返回头指针
}
void print(NODE* head) {
NODE* p;
p = head->next;
do {
printf("%d ", p->data);
p = p->next;
} while (p->data != 1);
}
/*
这是一个计算循环链表长度的函数
需要该链表中的任意一个结点的地址
该函数的返回值是该链表的长度
*/
int length(NODE* p) {
NODE* temp;
temp = p;//将p储存的地址赋值给temp;因为我们后面要用到
//这个最初传入的地址
int len = 0;
//这里使用do while循环因为循环至少要进行一次
do {
p = p->next;
len++;
} while (p != temp);
return len;//返回该链表的长度
}
NODE* dele(NODE* p, int m) {
NODE* q;//定义一个q变量,目的是让他指向p的后续结点
int j = 1;
while (j != m - 1) {
p = p->next;
j++;
}//这个循环是移动p让p指向目标结点的前驱结点
q = p->next;//让q指向目标结点
p->next = q->next;//把目标结点的next域的值赋值给p指向next的值
free(q);//释放目标结点的值
return p->next;//这里要返回p->next的值,因为下一次计数要从
//目标结点的后续结点开始
}
int main() {
int n;
int m;
scanf("%d", &n);
scanf("%d",&m);
NODE* head;
head = create(n);//创建一个带头结点的链表
// print(head);
NODE* p;//定义一个p指针
p=head->next;//让p指针指向首元结点
while(length(p)!=1){//当链表的长度为1的时候退出循环
p=dele(p,m);//每次删除第m给结点
}
//这时最后链表只剩下一个结点
printf("%d",p->data);//打印出最后剩下的一个结点的值
return 0;
}
在第i个元素之前插入结点
#include <stdio.h>
#include <stdlib.h>
struct node
{
int data;
struct node* next;
};
typedef struct node NODE;
NODE* create()
{
NODE* head,*q,*p;
int t;
head = (NODE*)malloc(sizeof(NODE));
p=head;
while(1){
scanf("%d",&t);
if(t==0){
break;
}
else
{
q=(NODE*)malloc(sizeof(NODE));
q->data=t;
p->next=q;
p=q;
}
}
p->next=NULL;
return head;
}
void print(NODE* head)
{
NODE *p;
int t;
p=head->next;
while(p!=NULL){
t=p->data;
printf("%d ",t);
p=p->next;
}
}
/*
该函数是链表的插入算法
该函数有3个参数头指针head,插入位置i,插入数值e
该函数的返回值为一个头指针
*/
NODE* insert(NODE* head,int i,int e)
{
NODE* p,*s;//定义两个指针变量p,s;
p=head;//让p也指向头节点
int j=0;//让j初始化为0
while(p!=NULL && j<i-1){
p=p->next;
j++;
}//寻找目标结点的前驱结点
if(p==NULL || j>i-1){//如果p满足这两个条件的其中之一
//说明给出的i值的信息有误
printf("给出的i值有误\n");
}
else
{
//动态分配一个新结点并且让s指针指向这个结点
s=(NODE*)malloc(sizeof(NODE));
s->data=e;//给目标结点的数据域赋值
s->next=p->next;//让新生成的结点的指针域指向下一个结点
p->next=s;//让目标结点指向新生成的结点
}
return head;
}
int main()
{
NODE*head;
int i;
int e;
head=create();
print(head);
printf("\n请输入要插入的位置\n");
scanf("%d",&i);
printf("请输入要插入的值\n");
scanf("%d",&e);
head=insert(head,i,e);
print(head);
return 0;
}
递增的整数序列链表的插入
递增的整数序列链表的插入
数据结构(浙大版)的一个课后习题,分享一下
List Insert( List L, int X ) {
PtrToNode p, q, s;
/*
p用来指向目标结点的前驱
q用来指向目标结点
s用来指向新生成的结点
这里的目标结点就是第一个比X大的数
*/
p = L;//让p指向头结点
q = L->Next; //让q指向首元结点
while (q != NULL) {//对链表进行遍历操作
if (q->Data < X) {//如果当前的元素比目标元素小
p = q;//让p向后移动一位
q = q->Next;//让q也向后移动一位
//但是要保证p始终指向q的前驱
} else {
//如果当前的元素比目标元素大
//直接跳出循环
break;
}
}
//我又画图讨论了一下,最后添加新结点不需要分类讨论
//如果循环是直接跳出的那么p,q已经指向了我们需要操作的结点
s = (struct Node*)malloc(sizeof(struct Node));//动态分配一个新的结点,并且让s指向这个结点
s->Data = X;//给数据域赋值
s->Next = q;//将后半段的链表直接挂在s上面
p->Next = s;//将带着s的后半段链表直接挂在p的后面
return L;//返回头指针
}
单链表中重复元素的删除
单链表中重复元素的删除
这个问题考察的知识还是很全面的,做这个问题,需要用到知道
- 如何用头插法建立单链表.
2.如果遍历整个链表的元素
3.如何计算整个链表中的长度
4.如何在单链表中删除指定元素
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node* next;
};
typedef struct node NODE;
/*
该函数为单链表创建函数
该函数需要一个参数n，表示有几个节点
该函数将返回一个头指针
根据题目要求这里是用头插法建立的链表
*/
NODE* create(int n) {
int e;
NODE *head, *q;
head = (NODE*)malloc(sizeof(NODE));
head->next = NULL;
for (int i = 0; i < n; i++) {
scanf("%d", &e);
q = (NODE*)malloc(sizeof(NODE));
q->data = e;
q->next = head->next;
head->next = q;
}
return head;
}
/*
该函数为遍历字符串的函数
*/
void print(NODE* head) {
int t;
NODE* p;
p = head->next;
while (p != NULL) {
t = p->data;
printf("%d ", t);
p = p->next;
}
printf("\n");
}
/*
该函数为删除链表中从复元素的函数
该函数需要头指针head
该函数没有返回值
*/
void deletesame(NODE* head) {
int e;
NODE *p, *q, *s;
/*
这里我们用双重循环来查找重复的元素
用p作为外层循环的指针
s用来始终指向目标节点的前驱节点
q用来指向目标节点
*/
p = head->next;//让p指向头节点
while (p != NULL) {//注意这里的外层循环不能用长度n来控制因为循环
//里面会删除指定元素的,导致链表的长度变化
e = p->data;//将p所指向的数据域保存下来
s = p;//让s和q相等
q = s->next;//q指向s的后续节点，因为我们要找到目标节点的前驱节点
while (q != NULL) {//用循环的形式遍历整个链表
if (e == q->data) {//如果找到目标结点
s->next = q->next;//让目标结点前驱结点指向目标结点的后续结点
free(q);//释放目标结点
q = s->next;//移动指针让其指向下一个结点
} else {
s = q;
q = q->next;
//如果没找到就继续后移动
//但还是要让s始终指向p的前驱
}
}
p = p->next;//不要忘了外层循环每次向后移动
}
}
/*
该函数为计算链表长度的函数
*/
int length(NODE* head) {
int len = 0;
NODE* p;
p = head->next;
while (p != NULL) {
len++;
p = p->next;
}
return len;
}
int main() {
int n;
scanf("%d", &n);
NODE* head;
head = create(n);
printf("%d\n", length(head));
print(head);
deletesame(head);
printf("%d\n", length(head));
print(head);
return 0;
}