目录
1.双向带头循环链表
结构:
2.自定义头文件:
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<stdlib.h>
#include<string>
using namespace std;
typedef int type;
struct List
{
type val;
struct List* pre;
struct List* next;
};
typedef struct List List;
void init(List** st);
List* newnode(type x);
void pushback(List* st, type x);
void print(List* st);
void pushfront(List* st, type x);
void popback(List* st);
void popfront(List* st);
void insert(List* pos, type x);
void erase(List* pos);
List* find(List* st, type x);
void destory(List* st);
void menu();
双向链表中的结点具有pre和next指针,分别连向上一个结点和下一个结点,val用来存储值。
3.List.cpp 文件
代码:
#include"Sqlist.h"
void menu()
{
printf("******************************\n");
printf("***1.init 2.pushback***\n");
printf("***3.pushfront 4.print***\n");
printf("***5.popback 6.popfront***\n");
printf("***7.insert 8.erase***\n");
printf("***9.destory 0.exit***\n");
printf("******************************\n");
}
void init(List** st)
{
*st = newnode(-1);
}
List* newnode(type x)
{
List* nnee = (List*)malloc(sizeof(List));
if (nnee == NULL)
{
perror("malloc");
exit(0);
}
nnee->val = x;
nnee->next = nnee->pre = nnee;
return nnee;
}
void pushback(List* st, type x)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
List* nnee = newnode(x);
nnee->next = st;
nnee->pre = st->pre;
st->pre->next = nnee;
st->pre = nnee;
}
void print(List* st)
{
List* cur = st->next;
while (cur != st)
{
cout << cur->val << ' ';
cur = cur->next;
}
cout << endl;
return;
}
void pushfront(List* st, type x)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
List* nnee = newnode(x);
nnee->next = st->next;
nnee->pre = st;
st->next->pre = nnee;
st->next = nnee;
}
void popback(List* st)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
if (st->next == st)
{
printf("st is empty\n");
return;
}
List* cur = st->pre;
cur->pre->next = st;
st->pre = cur->pre;
free(cur);
cur = NULL;
}
void popfront(List* st)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
if (st->next == st)
{
printf("st is empty\n");
return;
}
List* del = st->next;
st->next = del->next;
del->next->pre = st;
free(del);
del = NULL;
}
void insert(List* pos, type x)//之后
{
if (pos == NULL)
{
printf("NULL\n");
return;
}
List* nnee = newnode(x);
nnee->next = pos->next;
nnee->pre = pos;
pos->next->pre = nnee;
pos->next = nnee;
}
void erase(List* pos)
{
if (pos == NULL)
{
printf("pos is NULL\n");
return;
}
pos->pre->next = pos->next;
pos->next->pre = pos->pre;
free(pos);
pos = NULL;
}
List* find(List* st, type x)
{
List* cur = st->next;
while (cur != st)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
void destory(List* st)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
List* cur = st->next;
while (cur != st)
{
List* ne = cur->next;
free(cur);
cur = ne;
}
free(st);
st = NULL;
cur = NULL;
}
3.1 newnode()函数讲解
代码:
List* newnode(type x)
{
List* nnee = (List*)malloc(sizeof(List));
if (nnee == NULL)
{
perror("malloc");
exit(0);
}
nnee->val = x;
nnee->next = nnee->pre = nnee;
return nnee;
}
(1).使用malloc函数开辟一块空间,赋给nnee。
(2).再判断是否开辟成功。开辟成功后,将x赋值给nnee的val,并且把nnee的两个指针域都赋值为自己。最后返回该结点。
3.2 init() 函数 初始化
void init(List** st)
{
*st = newnode(-1);
}
(1).由于我们创建的是带头循环链表,所以初始化要将链表的最开始创建一个头结点。
3.3 pushback()函数 尾插
void pushback(List* st, type x)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
List* nnee = newnode(x);
nnee->next = st;
nnee->pre = st->pre;
st->pre->next = nnee;
st->pre = nnee;
}
(1).先判断链表的地址是否为空。
(2).创建一个新结点。
(3).将新结点的next指针指向头结点,再将新结点的pre指针指向st的pre。
再将头结点的pre的next(链表最后一个结点)指向新结点,再将头结点的pre指向新结点。
3.4 pushfront()函数 头插
void pushfront(List* st, type x)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
List* nnee = newnode(x);
nnee->next = st->next;
nnee->pre = st;
st->next->pre = nnee;
st->next = nnee;
}
(1).创建新结点。
(2).将新结点的next指向头结点的next,再将新结点的pre指向头结点。
(3).再将头结点的next的pre指向新结点。头结点的next指向新结点。
3.5 popback() 尾删
void popback(List* st)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
if (st->next == st)
{
printf("st is empty\n");
return;
}
List* cur = st->pre;
cur->pre->next = st;
st->pre = cur->pre;
free(cur);
cur = NULL;
}
(1).首先判断链表是否有头结点,还要判断链表是否已经为空,为空则 st->next == st,头结点自己指向自己时
(2).创建一个指针cur,令cur指向链表最后一个结点,再令最后一个节点的pre(倒数第二个结点)的next指向头结点,再令头节点的pre指向cur的pre(倒数第二个指针)。
3.6 popfront() 函数 头删
void popfront(List* st)
{
if (st == NULL)
{
printf("st is NULL\n");
return;
}
if (st->next == st)
{
printf("st is empty\n");
return;
}
List* del = st->next;
st->next = del->next;
del->next->pre = st;
free(del);
del = NULL;
}
(1).首先判断链表是否有头结点,还要判断链表是否已经为空,为空则 st->next == st,头结点自己指向自己时
(2).创建一个指针del,令del指向头结点的next(头结点的下一个结点),再将头结点的next指向del的next,再将del的next的pre指向头结点。
3.7 insert()函数 在pos之后插入
void insert(List* pos, type x)//之后
{
if (pos == NULL)
{
printf("NULL\n");
return;
}
List* nnee = newnode(x);
nnee->next = pos->next;
nnee->pre = pos;
pos->next->pre = nnee;
pos->next = nnee;
}
(1).创建一个新结点,令新结点的next指向pos的next。再将新结点的pre指向pos。
(2).再将pos的next的pre(pos下一个结点的pre指针)指向新结点;pos的next指向新结点。
3.8 popback()函数 删除
void erase(List* pos)
{
if (pos == NULL)
{
printf("pos is NULL\n");
return;
}
pos->pre->next = pos->next;
pos->next->pre = pos->pre;
free(pos);
pos = NULL;
}
(1).将pos的pre的next(pos的前一个节点的next指针)指向pos的next(pos的下一个节点)。
(2).再将pos的next的pre(pos的下一个节点的pre指针)指向pos的pre(pos的前一个指针)
3.9 find() 函数 查找
List* find(List* st, type x)
{
List* cur = st->next;
while (cur != st)
{
if (cur->val == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
(1).直接遍历链表即可,当遇到当前节点的val与x相同时,直接返回地址。
(2).若遍历完后还没有找到,则最后返回空。
3.10 print()函数 打印
void print(List* st)
{
List* cur = st->next;
while (cur != st)
{
cout << cur->val << ' ';
cur = cur->next;
}
cout << endl;
return;
}
(1).直接遍历链表即可,依次打印节点的每个值。
4.test.cpp 文件
代码:
#include"Sqlist.h"
int main()
{
List* head;
List* pos=NULL;
type x;
int op;
int n;
type y;
init(&head);
do
{
menu();
printf("input optio\n");
cin >> op;
switch (op)
{
case 1:
init(&head);
break;
case 2:
printf("input you want push number\n");
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
pushback(head, x);
}
break;
case 3:
printf("input you want push number\n");
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
pushfront(head, x);
}
break;
case 4:
print(head);
break;
case 5:
popback(head);
break;
case 6:
popfront(head);
break;
case 7:
printf("input you pos and val\n");
cin >> y >> x;
pos = find(head,y);
if (pos == NULL)
{
printf("pos is not save\n");
}
else
{
insert(pos, x);
}
break;
case 8:
printf("input you pos \n");
cin >> y;
pos = find(head, y);
if (pos == NULL)
{
printf("pos is not save\n");
}
else
{
erase(pos);
}
break;
case 9:
destory(head);
break;
case 0:
break;
default:
printf("piease input correct option\n");
break;
}
} while (op);
}
完.