关于链表
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。
单链表
第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表还用来构建许多其它数据结构，如堆栈，队列等等。
文章图片
#include
using namespace std;
typedef struct Node {//定义结构体Node
int data;
struct Node* next;
}* LinkedList,LNode;
//别名void CreateLinkedList(LinkedList &L, int &length) {/*创建链表 注意此处LinkedList &L为引用，
引用在C++里面是确保传入的参数可以被修改。形参是无关的单引用可以使其修改*/
L = (LinkedList)malloc(sizeof(LNode));
//初始化，头节点创建
L->data = https://www.it610.com/article/0;
L->next = NULL;
LinkedList tail = L;
//尾节点 cout << "The length of the LinkedList is" <> temp->data;
tail->next= temp;
tail = temp;
temp = NULL;
L->data++;
}
tail->next = NULL;
}
bool getElem(int &e, int i, LinkedList L){//判断元素是否在相应围殴之
while (L !=NULL && i>0){
i--;
L = L->next;
}
if (i == 0 && L !=NULL){
e = L->data;
return true;
}
else
return false;
}
bool insertElem(int e, int i, LinkedList L) {//插入数据
if (i > L->data || i <= 0)
return false;
else {
L->data++;
while (i > 1) {
i--;
L = L->next;
}
LinkedList temp = (LinkedList)malloc(sizeof(LNode));
temp->data = https://www.it610.com/article/e;
temp->next = L->next;
L->next = temp;
return true;
}
}bool DeleteElem(int i, LinkedList L) {//删除
if (i > L->data || i < 1)
return false;
else {
L->data--;
while (i > 1) {
i--;
L = L->next;
}
LinkedList temp = (LinkedList)malloc(sizeof(LNode));
temp = L ->next;
L->next = temp->next;
free(temp);
return true;
}
}
bool destoryLinkedList(LinkedList &L) {//销毁链表
if (L->next != NULL)
destoryLinkedList(L->next);
free(L);
return true;
}
bool clearLinkedList(LinkedList &L) {//清空链表
destoryLinkedList(L->next);
L->data = https://www.it610.com/article/0;
L->next = NULL;
return true;
}
void printLinkedList(LinkedList L) {//打印输出
LinkedList head = L->next;
cout << "\n\t";
while (head != NULL) {
cout << "[" << head->data << "]";
if(head->next)cout<< "-->";
head = head->next;
}
cout << "\n"<> ListSize;
CreateLinkedList(L, ListSize);
next:
cout << "(1)打印链表(2)插入元素\n"
<< "(3)删除元素(4)清空链表\n"
<< "(5)销毁链表(6)存在元素\n";
cin >> choice;
switch (choice) {//switch选择判断 ，goto循环指向
case 1:
cout << "these are elements you input \n";
printLinkedList(L);
goto next;
case 2:
cout << "input num and location\n";
cin >> i;
cin >> Elem;
insertElem(Elem, i, L);
goto next;
case 3:
cout << "input location\n";
cin >> i;
DeleteElem(i, L);
goto next;
case 4:
clearLinkedList(L);
goto next;
case 5:
destoryLinkedList(L);
cout << "you destory the list!create it(1) OR withdraw it " << endl;
cin >> choice;
cin >> Elem;
if (choice == 1) {
(*p)(L, Elem);
//函数指针的使用
goto next;
}
else return 0;
case 6:
cin >> Elem;
cin >> i;
cout< 循环链表
循环链表，注意将最后的尾指针指向头节点即可。
#include
using namespace std;
typedef struct node {//定义单链表的节点
int data;
struct node *next;
}*NodePointer, CirNode;
NodePointer head, rear;
//声明一个表头和尾指针
class CircularList {
public :
NodePointer createList()//初始化一个循环链表
{
head = new CirNode;
rear = head;
rear->next = head;
return head;
}
NodePointer createList(int n)//创建一个循环链表
{
NodePointer p;
head = new CirNode;
rear = head;
for (int i = 1;
i <= n;
i++)
{
p = new CirNode;
p->next = rear->next;
rear->next = p;
rear = p;
cin >> p->data;
}
rear->next = head;
return head;
}
int insertList(NodePointer head, int i, int x)
{
NodePointer p, q;
int j = 0;
p = head->next;
while (p != head)
{
j++;
p = p->next;
}
p = head;
for (int j = 1;
j < i;
j++)
p = p->next;
if (i > j + 1 || i < 1)
{
printf("插入位置出错\n");
return -1;
}
q = new CirNode;
q->data = https://www.it610.com/article/x;
q->next = p->next;
p->next = q;
return 0;
}
int deleteList(NodePointer head, int i)//删除位置i处的节点
{
NodePointer p, q;
p = head->next;
int j = 0;
while (p != head)
{
j++;
p = p->next;
}
if (i<1 || i>j)
{
printf("删除位置出错\n");
return -1;
}
p = head;
for (j = 1;
j < i;
j++)
p = p->next;
q = p->next;
p->next = p->next->next;
free(q);
return 0;
}
void printList(NodePointer head)//输出循环链表的所有元素
{
int cal = 0;
NodePointer p;
p = head->next;
while (cal < 5)
{
printf(" %d ", p->data);
p = p->next;
if (p->next == head)
p->next = head->next;
cal++;
}
}
};
int main()
{
CircularList* c = new CircularList;
c->createList(2);
c->printList(head);
system("pause");
return 0;
} 【C++|链表以及链表的各种操作（增删改查）+循环链表】
推荐阅读
- 个人日记|K8s中Pod生命周期和重启策略
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧（用class类实现链表）
- C++|从零开始学C++之基本知识
- 步履拾级杂记|VS2019的各种使用问题及解决方法
- leetcode题解|leetcode#106. 从中序与后序遍历序列构造二叉树
- 动态规划|暴力递归经典问题
- 麦克算法|4指针与队列
- 遇见蓝桥遇见你|小唐开始刷蓝桥（一）2020年第十一届C/C++ B组第二场蓝桥杯省赛真题