单链表:单链表用来写邻接表,邻接表用来存储图和树
双链表:用来优化某些问题
单链表
链式存储
#include<stdio.h>
#include<stdlib.h>
int cont = 0;
//结构体
typedef struct List {
int data; //数据域
struct List* next; //指针域,指向当前结点的下一个结点,next指针的作用:1.直接访问下一个结点2.进行链表的遍历
}List,*Listptr; //类型名
//创建链表
_Bool CreateList(Listptr *head) { //若改变一级指针的值【一级指针所存储的地址】,只能找到二级指针进行修改,Listptr本身就是一级指针,Listptr*是二级指针【传参过程,如果想要改变参数本身,只能使用指针/引用进行】
*head = (Listptr)malloc(sizeof(List));//为第一个结点【头节点,什么都不放】申请空间 “=”改变指针的指向 malloc()请的空间是void*类型
//C语言指针赋值的规则:基类型相容,修饰符种类与个数:左边>右边
if(*head){
(*head)->data = 0;
(*head)->next = NULL;//指向为空,避免野指针的出现
return 1;
}
else
return 0;
}
//头插法
void Insert(Listptr head) {
Listptr temp;//要插入的结点
CreateList(&temp);//对新的结点进行申请空间和初始化结点
scanf("%d", &temp->data);
temp->next = head->next;//改变next指针的指向,先进行这一步,防止数据丢失
head->next = temp;
}
//尾插法,引入一个Listptr end(尾结点),指向最后一个结点
//尾插法 未引入尾结点
void Bottom_Insert(Listptr head) {
Listptr temp;
CreateList(&temp);
scanf("%d", &temp->data);
while (head->next) {
head = head->next;
}
head->next = temp;
}
//特定位置插
void Particular_Insert(Listptr head, int index) {
Listptr temp;
CreateList(&temp);
scanf("%d", &temp->data);
int i = 0; //此时位置从0开始算起
//int i = 1; 此时位置从1开始算起
while (i < index && head) {
i++;
head = head->next;
}
if (i == index && head) { //找到特定位置,并且该位置不是尾结点
temp->next = head->next;
head->next = temp;
}
else if (i == index && !head) { //找到特定位置,但是该位置是尾结点
head->next = temp;
}
else { //未找到特定位置
printf("插入失败\n");
}
}
//查——遍历查找
Listptr Search(Listptr head,int check) {
Listptr i = head;//i指针指向头结点,头结点不存放数据,故不用判断
while (i->next) {//i->next!=NULL;的时候进行循环
i = i->next;
cont++;
if (i->data == check) {
return i;
}
}
return NULL;
}
//按个数查找,只查找一个
Listptr SearchIndex(Listptr head, int index) {
int i = 0;
while (i < index && head != NULL) { //当查到找到或者查到末尾时停止
i++;
head = head->next;
}
if (head && i==index) //找到
return head;
else
return NULL;
}
//输出——遍历输出
void Print(Listptr head) {
Listptr i = head;//i本身就是一个指针
while (i->next) {//i->next!=NULL;的时候进行循环
i = i->next;
printf("%d ", i->data);
}
printf("\n");
}
//删1——删除特定的结点——按结点个数来查找
//需要遍历查到特定结点
_Bool DeleteNode(Listptr head,int index,int *e){
int i = 0;
Listptr front = head;
i = 1;
head = head->next;
while (i < index && head!= NULL) {
front = head;
head = head->next;
i++;
}
if (i == index && head != NULL) {//head就是查找的结点,front就是查找的前一个值
Listptr t = head;
front->next = head->next;
*e = t->data;
free(t);
return 1;
}
return 0;
}
//删2——删除特定结点——按结点个数查找
//使用查找函数查找
_Bool DeleteNode_SearchIndex(Listptr head, int index, int* e) {
Listptr front = SearchIndex(head, index - 1);
head = SearchIndex(head, index);
if (head && front) {
Listptr t = head;
front->next = head->next;
*e = t->data;
free(t);
return 1;
}
return 0;
}
//改
_Bool Alert(Listptr head, int index, int data) {
head = SearchIndex(head, index);
if (head) {
head->data = data;
return 1;
}
else
return 0;
}
int main() {
Listptr head; //第一个结点的指针
CreateList(&head);//对链表进行初始化
for (int i = 0;i < 10;i++) {
Insert(head);//插入
}
Print(head);//输出
for (int i = 0;i < 5;i++) {
int index = 0;
scanf("%d", &index);
printf("%d\n", SearchIndex(head, index)->data);
scanf("%d", &index);
int data;//删除
if (DeleteNode(head, index, &data)) {
printf("删除成功,删除值为%d\n", data);
}
else
printf("删除失败\n");
Print(head);
scanf("%d%d", &index, &data);
if (Alert(head, index, data)) {//更改
printf("更改成功\n");
}
else
printf("更改失败\n");
Print(head);
}
for (int i = 0;i < 10;i++) {
int check = 0;
scanf("%d", &check);
if (!Search(head, check)) {//查找
printf("没查到\n");
}
else
printf("第%d个结点\n",cont);
}
return 0;
}
自己码代码
#include<stdio.h>
#include<stdlib.h>
typedef struct List {
int data;
struct List* next;
}List,*Listptr;
int cont=0;
//初始化
_Bool CreateList(Listptr* head) {
*head = (Listptr)malloc(sizeof(List));
if (*head) {
(*head)->data = 0;
(*head)->next = NULL;
return 1;
}
else
return 0;
}
//头插法
void Insert(Listptr head) {
Listptr temp;
CreateList(&temp);
scanf("%d", &temp->data);
temp->next = head->next;
head->next = temp;
}
//尾插法
void Bottom_Insert(Listptr head) {
Listptr temp;
CreateList(&temp);
scanf("%d", &temp->data);
while (head->next) {
head = head->next;
}
head->next = temp;
}
//特定位置插
void Particular_Insert(Listptr head, int index) {
Listptr temp;
CreateList(&temp);
scanf("%d", &temp->data);
int i = 0;
while (i < index && head) {
i++;
head = head->next;
}
if (i == index && head) {
temp->next = head->next;
head->next = temp;
}
else if (i == index && !head) {
head->next = temp;
}
else {
printf("插入失败\n");
}
}
//查1——按值查找
Listptr Search(Listptr head, int check) {
Listptr i;
i = head;
while (i->next) {
i = i->next;
cont++;
if (i->data == check) {
return i;
}
}
return NULL;
}
//查2——按结点位置查找
Listptr SearchIndex(Listptr head, int index) {
int i = 0;
while (i < index && head) {
i++;
head = head->next;
}
if (head && i == index) {
return head;
}
else
return NULL;
}
//输出
void Print(Listptr head) {
Listptr i = head;
while (i->next) {
i = i->next;
printf("%d ", i->data);
}
printf("\n");
}
//删——删除特定节点
_Bool DeleteNode(Listptr head, int index, int* e) {
Listptr front = SearchIndex(head, index - 1);
head = SearchIndex(head, index);
if (head && front) {
Listptr t = head;
front->next = head->next;
*e = t->data;
free(t);
return 1;
}
return 0;
}
//改
_Bool Alert(Listptr head, int index, int data) {
head = SearchIndex(head, index);
if (head) {
head->data = data;
return 1;
}
else
return 0;
}
int main() {
Listptr head;
CreateList(&head);
for (int i = 0;i < 5;i++) {
Insert(head);//头插法
}
Print(head);
Bottom_Insert(head);//尾插法
Print(head);
int index1;
scanf("%d", &index1);
Particular_Insert(head, index1);//特定位置插入
Print(head);
int check;
scanf("%d", &check);
Search(head, check);//按值查找
printf("值为%d的是第%d个结点\n", check, cont);
int index2;
scanf("%d", &index2);
printf("第%d个结点的值为%d\n", index2, SearchIndex(head, index2)->data);//按位置查找
int index3;
scanf("%d", &index3);
int data1;
if (DeleteNode(head, index3, &data1)) {//删
printf("删除成功,删除值为%d\n", data1);
}
else
printf("删除失败\n");
Print(head);
int index4, data2;
scanf("%d%d", &index4, &data2);
if (Alert(head, index4, data2)) {//改
printf("更改成功\n");
}
else
printf("更改失败\n");
Print(head);
return 0;
}
顺序存储
用数组模拟链表,静态链表,比动态链表快(因为 new 生成新结点慢)
//链表的顺序存储,用数组来模拟链表
#include<stdio.h>
#define N 100
typedef struct List {//typedef作用:将后面的定义变量的语句变成给类型重命名的语句
int data;
int next;//索引,下标可以替代next指针,以此来访问下一个结点
}List, * Listptr;
List heap[100] = { 0 };//数组代表堆这个空间
//确定数组未使用空间为空 1.逐个遍历——麻烦 2.将空余空间构成链表【整体过程存在两个链表,一个是有数据即将使用的链表,一个是空余未使用空间串联构成的备用链表(当需要空间的时候,自取)】
//初始化
int head, leisure;//分别代表两个链表的头指针,head是using链表的头指针,用来指向第一个结点,leisure是空余链表的头指针
void InitHeap() {
int i;
head = 0;
//heap[0].next = 1;//用来存储空余链表的第一个结点的下标
heap[N - 1].next = 0;//0代表为空,意思是什么都不指向,指向为NULL,next只要为0,就相当于什么都不指向,指向为空
for (i = 0;i < N - 1;i++) {
heap[i].next = i + 1;
}
}
//模仿malloc
int Malloc() {//空间申请,申请一个结点的空间,一个结点==数组中的一个元素
int temp;
if (heap[0].next) {//heap[0].next==0 整个堆中没有空余空间,反之有空余空间
temp = heap[0].next;//临时变量存储要删除的结点
heap[0].next = heap[heap[0].next].next;//利用第一个结点指向第三个结点,第一个结点存储的第二个结点的下标,第二个结点存储的第三个结点的下标
return temp;//返回刚申请空间的索引
}
else {
return 0;//无法申请空间
}
}
//模仿free
void Free(int index) {//动态链表中释放空间,静态链表中将正在使用链表中的结点放在空余链表中
//因为这个空间本来就有,所以就不用再申请了
heap[index].next = heap[0].next;
heap[0].next = index;
}
//增——头插法
_Bool InsertHead() {
int temp = Malloc();
if (temp) {
heap[temp].next = head;
head = temp;
return 1;
}
else
return 0;
}
//按data值查找
int Search(int check) {
int temp = head;//将第一个结点的索引赋给temp,所以heap[temp]指的是第一个结点
while (temp) {
if (heap[temp].data == check) {
return temp;
}
else {
temp = heap[temp].next;
}
}
}
//按索引查找
int SearchByIndex(int Index) {
int i = head, cont = 0;
while (i < Index && i != 0) {
cont++;
if (cont == Index) {
return i;
}
else {
i = heap[i].next;
}
}
return 0;
}
//改
_Bool Alert(int index, int data) {
int temp = Search(index);
if (temp) {
heap[temp].data = data;
return 1;
}
else
return 0;
}
//删
_Bool Delete(int index) {
int front = SearchByIndex(index - 1), aim = SearchByIndex(index);
if (aim && front) {//从第二个结点开始删除
int temp = aim;//存储要删除的结点
heap[front].next = heap[aim].next;//将目标前一个结点指向目标后一个结点
Free(temp);
}
else if (aim) {//从第一个结点开始删除
int temp = aim;
front = heap[aim].next;//如果使用 heap[front].next = heap[aim].next;将会丢失空余链表剩下的部分,因为你直接将空余链表的头结点指向第二个结点,使得空余链表的后面的空结点丢失
Free(temp);
}
}
int main() {
return 0;
}
Acwing 课程
代码
//使用两个数组模拟链表
#include<iostream>
using namespace std;
const int N = 100010;
//head表示头结点的下标,头结点最开始指向一个空结点(用-1表示),每次插入一个新的元素
//e[i]表示结点i的值,ne[i]表示结点i的next指针是多少
//idx存储当前已经用到哪个点
int head, e[N], ne[N], idx;
//初始化
void init() {
head = -1;//表示空集
idx = 0;
}
//头插法 分两步进行
void add_to_head(int x) {
e[idx] = x;//存储数值
ne[idx] = head;//第一步
head = idx;//第二步
idx++;
}
//指定位置插
//将x插到下标是k这个点后面
//分两步进行
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//删除特定位置的点
//删去下标为k的后面的一个点
void remove(int k) {
ne[k] = ne[ne[k]];
}
int main() {
return 0;
}
题目
实现一个单链表,链表初始为空,支持三种操作:
(1) 向链表头插入一个数;
(2) 删除第k个插入的数后面的数;
(3) 在第k个插入的数后插入一个数
现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数,则按照插入的时间顺序,这n个数依次为:第1个插入的数,第2个插入的数,…第n个插入的数。
输入格式
第一行包含整数M,表示操作次数。
接下来M行,每行包含一个操作命令,操作命令可能为以下几种:
(1) “H x”,表示向链表头插入一个数x。//头插法
(2) “D k”,表示删除第k个输入的数后面的数(当k为0时,表示删除头结点)。//第k个输入,下标为k-1,即删除下标为k-1后面的数
(3) “I k x”,表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。//即在下标为k-1后插入一个数
输出格式
共一行,将整个链表从头到尾输出。
数据范围
1 ≤ M ≤ 100000 1≤M≤1000001≤M≤100000
所有操作保证合法。
输入样例
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
输出样例
6 4 6 5
注意点
1.插入、删除操作都是对第k个数后面的数进行操作的,因为指针域存储的是下一个节点。
2.删除时,首先要考虑是否删除的是头节点。
3.输出时从头结点开始,末尾是空,指向−1。
4.scanf在读入字符时不会跳过空格,还是用cin。
//使用两个数组模拟链表
#include<iostream>
using namespace std;
const int N = 100010;
//head表示头结点的下标
//e[i]表示结点i的值,ne[i]表示结点i的next指针是多少
//idx存储当前已经用到哪个点
int head, e[N], ne[N], idx;
//初始化
void init() {
head = -1;//表示空集
idx = 0;
}
//头插法 分两步进行
void add_to_head(int x) {
e[idx] = x;//存储数值
ne[idx] = head;//第一步
head = idx;//第二步
idx++;
}
//指定位置插
//将x插到下标是k这个点后面
//分两步进行
void add(int k, int x) {
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//删除特定位置的点
//删去下标为k的后面的一个点
void remove(int k) {
ne[k] = ne[ne[k]];
}
int main() {
int M;
cin >> M;
init();
while (M--) {
int k, x;
char op;
cin >> op;
if (op == 'H') {
cin >> x;
add_to_head(x);
}
else if (op == 'D') {
cin >> k;
if (!k)
head = ne[head];//删除头结点,使head指向它现在指向的点的下一个点,head指向的点就是head本身
remove(k - 1);//因为第一个插入的点下标是0,以此类推
}
else {
cin >> k >> x;
add(k - 1, x);
}
}
for (int i = head;i != -1;i = ne[i])
cout << e[i] << ' ';
return 0;
}
邻接表
实际上就是开了 n 个单链表。
双链表
一个结点有两个指针,分别指向它的左边和右边,l[N],r[N],不专门定义头结点head和尾结点tail,下标为0的点是最左边的点,下标为1的点是最右边的点。
代码
#include<iostream>
using namespace std;
const int N = 100010;
int e[N], l[N], r[N], idx;
//初始化
void init() {
//0表示左端点,1表示右端点,最开始的时候,0号点的右边是1号点,1号点的左边是0号点
r[0] = 1, l[1] = 0;
idx = 2;
}
//增——两种选择,插入到某点的右边或插入到某点的左边
//在下标为k的点的右边插入一个数
void add(int k, int x) {
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++;
}
//在下标为k的点的左边插入一个数
//可以重新写,也可以直接调用,即在l[k]的右边插入一个数 add(l[k],x)
//删
//删除下标为k的点
void remove(int k) {
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main() {
return 0;
}