网站建设利润网址大全360
链表:
特点:
通过 next 指针 把内存上不连续 的几段数据 联系起来
set nu -- 打印行号
概念: 一种数据结构 -- 数据存放的思想
比如 -- 数组 -- 内存连续的一段空间，存放相同类型的一堆数据
缺点 -- 增删元素很 难 -- 不灵活 --> 引入链表
next指针的初步认识:
#include<stdio.h>struct chain
{
int num;
struct chain* next;
};
int main()
{
int arr[3]={1,2,3};
puts("use arr to output:");for(int i=0;i<3;++i)
{
printf("%d ",arr[i]);
}
puts("");
struct chain a={1,NULL};
struct chain b={2,NULL};
struct chain c={3,NULL};a.next=&b;
b.next=&c;
puts("use chain to output:");
printf("%d %d %d\n",a.num,a.next->num,b.next->num);return 0;
}
遍历:
遍历条件 -- 尾部元素的next 指针为NULL -- 结束条件
遍历 只需要 传入首元素的地址就-ok -> 后续元素直接 next去获取
#include<stdio.h>struct chain
{
int num;
struct chain* next;
};
void printChain(struct chain* head)
{
struct chain* p=head;
while(p!=NULL)
{
printf("%d ",p->num);
p=p->next;
}puts("");
}
int main()
{
int arr[3]={1,2,3};
puts("use arr to output:");for(int i=0;i<3;++i)
{
printf("%d ",arr[i]);
}
puts("");
struct chain a={1,NULL};
struct chain b={2,NULL};
struct chain c={3,NULL};a.next=&b;
b.next=&c;
puts("use chain to output:");
//printf("%d %d %d\n",a.num,a.next->num,b.next->num);printChain(&a);
return 0;
}//p-> next 下一个元素的地址
==========================================
列表的查找
int getTotal(struct chain* head) //获得链表长度
{
int cnt=0;
while(head!=NULL)
{
cnt++;
head=head->next;
}
return cnt;
}int check(struct chain* head,int n) //查看n是否在链表内
{
while(head!=NULL)
{
if(head->num==n) return 1;head=head->next;
return 0;
}
=================================
插入新节点
后面插入
int insert(struct chain* head,int data,struct chain*new)
{
struct chain* p=head;
while(p!=NULL)
{
if(p->num==data) //找到目标元素位置
{
new->next=p->next; //插入到目标元素后面
p->next=new; //目标元素的下一个数改为插入值
return 1;
}p=p->next;
}
return 0;}
==============================================
前面插入
struct chain* frontInsert(struct chain* head,int data,struct chain*new)
{
struct chain* p=head;
if(p->num==data) //在头部插入
{
new->next=head;//换头
puts("insert succeed");
return new;
}while(p->next!=NULL)
{
if(p->next->num==data) // 找到目标元素的上一个元素位置
{
new->next=p->next; //差到目标元素上一个元素的后面就是目标元素的前面
p->next=new; //目标元素的上一个元素指向我们的插入值
puts("insert succeed");
return head;
}
p=p->next;}
puts("insert failed!!");
return head;}
==================================
删除指定节点:
分情况:
1.改头 -- 记得把之前的头free掉(malloc 创建的才能free -- 一般也是malloc去创建)，避免浪费系统空间
2.跳过
struct chain* myRemove(struct chain* head,int data)
{
struct chain *p =head;if(p->num==data) //第一个就是目标
{
head=head->next;
return head;
}while(p->next!=NULL)
{
if(p->next->num==data)
{
p->next=p->next->next; //跳过中间值 == 删除//注-- if 是malloc 动态创建的内存空间这里要free释放掉--一般都是动态内存空间
return head;
}
p=p->next;
}
return head;
}
================================================
链表的动态创建:
头插法
struct chain* frontCreate(struct chain* head)
{
struct chain*new=NULL;
while(1)
{
new=(struct chain*)malloc(sizeof(struct chain)); //拿到一块新的内存空间
puts("清输入一个数字， 0--退出!");
scanf("%d",&new->num);if(new->num==0)
{
puts("0 -- quit");
return head;
}if(head==NULL)
{
head=new; //给链表头赋值
}
else
{
new->next=head; //头插，新元素插到头后面
head=new; //然后新的节点变成头 -- 类似栈 --先进后出
}
}return head;
}
========================================
优化-- 循环 和 头插 分开写
struct chain *frontCreate(struct chain *head, struct chain *new)
{
if (head == NULL)
{
head = new;
}
else
{
new->next = head;
head = new;
}
return head;
}
struct chain *myCreate(struct chain *head)
{
while (1)
{
struct chain *new = NULL;
new = (struct chain *)malloc(sizeof(struct chain));
puts("清输入一个数字， 0--退出!");
scanf("%d", &new->num);
if (new->num == 0)
{
puts("0 -- quit");
free(new);
return head;
}
head= frontCreate(head, new);
}
return head;
}
========================================
尾插法
struct chain *behindCreate(struct chain *head, struct chain *new)
{
struct chain *p = head;
if (head == NULL)
{
head = new;
return head;
}
while (p->next != NULL) //拿到尾部位置 p==NULL
{
p = p->next;
}
p->next = new; //直接在当前链表的尾部添加return head;
}
===================================
整个程序:
#include <stdio.h>struct chain
{
int num;
struct chain *next;
};void printChain(struct chain *head)
{
struct chain *p = head;
while (p != NULL)
{
printf("%d ", p->num);
p = p->next;
}puts("");
}int getTotal(struct chain *head)
{
int cnt = 0;
while (head != NULL)
{
cnt++;
head = head->next;
}
return cnt;
}int check(struct chain *head, int n)
{
while (head != NULL)
{
if (head->num == n)
return 1;head = head->next;
return 0;
}
}void modif(struct chain *head, int n, int new)
{
struct chain *p = head;
while (p != NULL)
{
if (p->num == n)
{
p->num = new;
puts("修改成功！");
}p = p->next;
}
}int insert(struct chain *head, int data, struct chain *new)
{
struct chain *p = head;
while (p != NULL)
{
if (p->num == data)
{
new->next = p->next;
p->next = new;
return 1;
}p = p->next;
}
return 0;
}struct chain *frontInsert(struct chain *head, int data, struct chain *new)
{
struct chain *p = head;
if (p->num == data) // 在头部插入
{
new->next = head; // 换头
puts("insert succeed");
return new;
}while (p->next != NULL)
{
if (p->next->num == data)
{new->next = p->next;
p->next = new;
puts("insert succeed");
return head;
}
p = p->next;
}
puts("insert failed!!");
return head;
}struct chain *myRemove(struct chain *head, int data)
{
struct chain *p = head;if (p->num == data) // 第一个就是目标
{
head = head->next;
return head;
}while (p->next != NULL)
{
if (p->next->num == data)
{
p->next = p->next->next;
return head;
}
p = p->next;
}
return head;
}struct chain *frontCreate(struct chain *head, struct chain *new)
{if (head == NULL)
{
head = new;
}
else
{
new->next = head;
head = new;
}return head;
}struct chain *behindCreate(struct chain *head, struct chain *new)
{
struct chain *p = head;
if (head == NULL)
{
head = new;
return head;
}
while (p->next != NULL)
{
p = p->next;
}
p->next = new;return head;
}struct chain *myCreate(struct chain *head,int func)
{
while (1)
{
struct chain *new = NULL;new = (struct chain *)malloc(sizeof(struct chain));
puts("清输入一个数字， 0--退出!");
scanf("%d", &new->num);if (new->num == 0)
{
puts("0 -- quit");
free(new);
return head;
}
if(func)
head = frontCreate(head, new);
else
head = behindCreate(head, new);
}
return head;
}int main()
{puts("use chain to output:");
// printf("%d %d %d\n",a.num,a.next->num,b.next->num);
struct chain *head = NULL;
int func;
puts("清选择插入方式:1--头插 0--尾插");
scanf("%d",&func);
head = myCreate(head,func);printChain(head);
// insert(&a,1,&new);
// head=frontInsert(head,4,&new);
// head=myRemove(head,4);
// modif(head,4,255);
// printChain(head);return 0;
}