【 数据结构（C语言）】线性表——单链表和单循环链表
1.线性链表：用任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的也可以是不连续）
2.动态链表和静态链表的区别
- 静态链表是用数组实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配大小。
- 动态链表是用申请内存函数（C是malloc,C++是new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。
3.单链表基本功能实现
#include <bits/stdc++.h>
using namespace std;
#define ElemType int
#define Status int
#define ERROR -1
#define OK 1
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode ,*LinkList;
LinkList CreateListHead_L(int n)///* 头插入
{
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
while (n--)
{
LinkList newnode = (LinkList)malloc(sizeof(LNode));
scanf("%d",&newnode->data);
newnode->next = L->next;
L->next = newnode;
}
return L;
}
LinkList CreateListTail_L(int n)///尾插入
{
LinkList L = (LinkList)malloc(sizeof(LNode));
LinkList last = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
last = L;
while (n--)
{
ElemType e;
scanf("%d",&e);
LinkList newnode = (LinkList)malloc(sizeof(LNode));
newnode->data = e;
last->next = newnode;
newnode->next = NULL;
last = newnode;
}
return L;
}
Status GetElem_L(LinkList &L,int i,ElemType &e)
{
LinkList index = L->next;
int ct = 1;
while (index && ct < i)
{
index = index->next;
++ct;
}
if (!index || ct > i) return ERROR;
e = index->data;
return OK;
}
Status ListInsert_L(LinkList &L,int i,ElemType e)
{
LinkList index = L->next;
int ct = 1;
while (index && ct < (i-1))
{
index = index->next;
++ct;
}
if (!index || ct > i -1) return ERROR;
LinkList newnode = (LinkList)malloc(sizeof(LNode));
newnode->data = e;
newnode->next = index->next;
index->next = newnode;
return OK;
}
Status ListDeteleByPos_L(LinkList &L,int i,ElemType &e)
{
LinkList index = L->next;
int ct = 1;
while (index && ct < i-1)
{
index = index->next;
++ct;
}
if (!(index->next) || ct > i-1) return ERROR;
LinkList tmp = index->next;
index->next = tmp->next;
e = tmp->data;
free(tmp);
return OK;
}
Status ListDeteleByVal_L(LinkList &L,ElemType e)
{
LinkList index = L->next,pri = L;
while (index) /// 注意：判断的如果是 pri pri 是最后一个元素的时候 index 已经超出链表
{
if (index->data == e)
{
pri->next = index->next;
free(index);
index = pri->next;
}
else
{
pri = pri->next;
index = index->next;
}
}
return OK;
}
int GetLength(LinkList &L)
{
int len = 0;
LinkList index = L->next;
while (index)
{
index = index->next;
len++;
}
return len;
}
LinkList ListReverse(LinkList &L)
{
LinkList a = L->next;
LinkList b = a->next;
LinkList c = b->next;
a->next = NULL;
int len = GetLength(L);
while (len--)
{
b->next = a;
c = b;
b = a;
if(!a)
{
L->next=a;
}
else c=c->next;
}
return L;
}
void TrverseLinklist(LinkList &L)///* 注意：这里是带头指针的链表
{
LinkList index = L->next;
for (;index!= NULL; index = index->next)
{
cout<<index->data<<" ";
}
cout<<endl;
}
4.单循环链表
注意：只是将单链表中的最后一个结点的指针是指着头结点的，形成循环
#include <bits/stdc++.h>
using namespace std;
#define ElemType int
#define Status int
#define ERROR -1
#define OK 1
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LNode ,*LinkList;
LinkList CreateListHead_L(int n)///* 头插入
{
LinkList L = (LinkList)malloc(sizeof(LNode));
L->next = L;/// 改：
while (n--)
{
LinkList newnode = (LinkList)malloc(sizeof(LNode));
scanf("%d",&newnode->data);
newnode->next = L->next;
L->next = newnode;
}
return L;
}
LinkList CreateListTail_L(int n)///尾插入
{
LinkList L = (LinkList)malloc(sizeof(LNode));
LinkList last = (LinkList)malloc(sizeof(LNode));
L->next = L;
last = L;
while (n--)
{
ElemType e;
scanf("%d",&e);
LinkList newnode = (LinkList)malloc(sizeof(LNode));
newnode->data = e;
last->next = newnode;
newnode->next = L;/// 改：
last = newnode;
}
return L;
}
Status GetElem_L(LinkList &L,int i,ElemType &e)
{
LinkList index = L->next;
int ct = 1;
while (index && ct < i)
{
index = index->next;
++ct;
}
if (!index || ct > i) return ERROR;
e = index->data;
return OK;
}
Status ListInsert_L(LinkList &L,int i,ElemType e)
{
LinkList index = L->next;
int ct = 1;
while (index && ct < (i-1))
{
index = index->next;
++ct;
}
if (!index || ct > i -1) return ERROR;
LinkList newnode = (LinkList)malloc(sizeof(LNode));
newnode->data = e;
newnode->next = index->next;
index->next = newnode;
return OK;
}
Status ListDeteleByPos_L(LinkList &L,int i,ElemType &e)
{
LinkList index = L->next;
int ct = 1;
while (index && ct < i-1)
{
index = index->next;
++ct;
}
if (!(index->next) || ct > i-1) return ERROR;
LinkList tmp = index->next;
index->next = tmp->next;
e = tmp->data;
free(tmp);
return OK;
}
Status ListDeteleByVal_L(LinkList &L,ElemType e)
{
LinkList index = L->next,pri = L;
while (index != L) /// 改：将循环条件改了
{
if (index->data == e)
{
pri->next = index->next;
free(index);
index = pri->next;
}
else
{
pri = pri->next;
index = index->next;
}
}
return OK;
}
int GetLength(LinkList &L)
{
int len = 0;
LinkList index = L->next;
while (index != L)/// 改：将循环条件改了
{
index = index->next;
len++;
}
return len;
}
void TrverseLinklist(LinkList &L)///* 注意：这里是带头指针的链表
{
LinkList index = L->next;
for (;index!= L; index = index->next)/// 改：将循环条件改了
{
cout<<index->data<<" ";
}
cout<<endl;
}