数据结构 链表

单链表：单链表用来写邻接表，邻接表用来存储图和树

双链表：用来优化某些问题

单链表

链式存储

#include

#include

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

#include

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

#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

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

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

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;

}