【数据结构】线性表
静态分配顺序表
// 静态分配顺序表
// 1. 顺序存储类型
#define MaxSize 50
typedef struct
{
// Elemtype data[MaxSize];
int data[MaxSize];
int length;
} SqList;
// 2. 初始化
void InitList(SqList &L)
{
L.length = 0;
}
// 3. 插入元素
// bool ListINert(SqList &L, int i, Elemtype e)
bool ListInsert(SqList &L, int i, int e)
{
if (i < 1 || i > L.length + 1)
return false;
if (L.length >= MaxSize)
return false;
for (int j = L.length; j >= i; j--)
{
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}
// 4. 删除
// bool ListDelete(SqList &L, int i ,Elemtype &e)
bool ListDelete(SqList &L, int i, int &e)
{
if (i < 1 || i > L.length)
return false;
e = L.data[i - 1];
for (int j = i; j <= L.length; j++)
{
L.data[j - 1] = L.data[j];
}
L.length--;
return true;
}
// 5. 按位查找
int GetElem(SqList L, int i)
{
return L.data[i - 1];
}
// 5. 按值查找
// int LocateElem(SqList &L, Elemtype &e)
int LocateElem(SqList &L, int &e)
{
for (int i = 0; i < L.length; i++)
{
if (L.data[i] == e)
return i + 1;
}
return 0;
}
动态分配顺序表
// 动态分配顺序表
// 1. 顺序存储类型
#define InitSize 50
typedef struct
{
// Elemtype *data;
int *data;
int MaxSize, length;
} SqList;
// 2. 初始化
void InitList(SqList &L)
{
// L.data = (Elemtype *)malloc(sizeof(Elemtype) * InitSize);
L.data = (int *)malloc(sizeof(int) * InitSize);
L.length = 0;
L.MaxSize = InitSize;
}
// 3. 插入元素
// bool ListINert(SqList &L, int i, Elemtype e)
bool ListInsert(SqList &L, int i, int e)
{
if (i < 1 || i > L.length + 1)
return false;
if (L.length >= MaxSize)
return false;
for (int j = L.length; j >= i; j--)
{
L.data[j] = L.data[j - 1];
}
L.data[i - 1] = e;
L.length++;
return true;
}
// 4. 删除
// bool ListDelete(SqList &L, int i ,Elemtype &e)
bool ListDelete(SqList &L, int i, int &e)
{
if (i < 1 || i > L.length)
return false;
e = L.data[i - 1];
for (int j = i; j <= L.length; j++)
{
L.data[j - 1] = L.data[j];
}
L.length--;
return true;
}
// 5. 按位查找
int GetElem(SqList L, int i)
{
return L.data[i - 1];
}
// 5. 按值查找
// int LocateElem(SqList &L, Elemtype &e)
int LocateElem(SqList &L, int &e)
{
for (int i = 0; i < L.length; i++)
{
if (L.data[i] == e)
return i + 1;
}
return 0;
}
带头结点的单链表
typedef struct LNode
{
// ElemType data;
int data;
struct LNode *next;
} LNode, *LinkList;
// 1.单链表的初始化
// (有头结点)
bool InitList(LinkList &L)
{
L = (LNode *)malloc(sizeof(LNode));
if (L == NULL)
return false;
L->next = NULL;
return true;
}
// 没有头结点
bool InitList(LinkList &L)
{
L = NULL;
return true;
}
// 2.尾插法建立单链表
LinkList List_TailInsert(LinkList &L)
{
int x;
// 创建头结点
L = (LinkList)malloc(sizeof(LNode));
// r为尾结点,s为每次创建的新结点
LNode *s, *r = L;
scanf("%d", &x);
while (x != 9999)
{
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
r->next = s;
r = s;
scanf("%d", &x);
}
// 尾结点置为空
r->next = NULL;
return L;
}
// 3.头插法创建单链表
LinkList List_HeadInsert(LinkList &L)
{
int x;
LNode *s;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
scanf("%d", &x);
while (x != 9999)
{
s = (LNode *)malloc(sizeof(LNode));
s->data = x;
s->next = L->next;
L->next = s;
scanf("%d", &x);
}
return L;
}
// 4.插入节点
// p = GetElem(L, i - 1);
// s->next = p->next;
// p->next = s;
// 5.在第i个位置后插入节点操作(带头结点)
// bool ListInsert(LinkList &L, int i, ElemType e)
bool ListInsert(LinkList &L, int i, int e)
{
if (i < 1)
return false;
// p指向当前扫描到的节点
LNode *p;
int j = 0;
p = L;
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
// 6.在第i个位置后插入节点操作(不带头结点)
bool ListInsert(LinkList &L, int i, int e)
{
if (i < 1)
return false;
if (i == 1)
{
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = L;
// 头指针指向新节点
L = s;
return true;
}
LNode *p;
p = L;
// 注意j的取值
int j = 1;
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
// 7.在第i个位置之前插入节点操作
bool InsertPriorNode(LNode *p, int e)
{
if (p == NULL)
return false;
LNode *s = (LNode *)malloc(sizeof(LNode));
if (s == NULL)
return false;
s->next = p->next;
p->next = s;
s->data = p->data;
p->data = e;
return true;
}
// 8.在第i个位置删除节点操作(带头结点)
bool ListDelete(LinkList &L, int i, int e)
{
if (i < 1)
return false;
LNode *p;
int j = 0;
p = L;
while (p != NULL && j < i - 1)
{
p = p->next;
j++;
}
if (p == NULL)
return false;
if (p->next == NULL)
return false;
LNode *q = p->next;
e = q->data;
p->next = p->next->next;
free(q);
return true;
}
// 9.删除指定节点
bool DeleteNode(LNode *p)
{
if (p == NULL)
return false;
LNode *q = p->next;
p->next = q->next;
free(q);
return true;
}
// 10.按序号查找节点值
LNode *GetElem(LinkList L, int i)
{
int j = 1;
LNode *p = L->next;
// 返回头结点
if (i == 0)
return L;
if (i < 1)
return NULL;
while (p != NULL && j < i)
{
p = p->next;
j++;
}
return p;
}
// 另外一个版本
// LNode *GetElem(LinkList L, int i)
// {
// if (i < 1)
// return NULL;
// int j = 0;
// LNode *p = L;
// while (p != NULL && j < i)
// {
// p = p->next;
// j++;
// }
// return p;
// }
// 11.按值查找表节点
LNode *LocateElem(LinkList L, int e)
{
LNode *p = L;
if (p == NULL)
return false;
while (p != NULL && p->date != e)
{
p = p->next;
}
return p;
}
// 12.求表长(不含头结点)
int Length(LinkList L)
{
int len = 0;
LNode *p = L;
while (p->next != NULL)
{
p = p->next;
len++;
}
return len;
}
双链表
// 有两个指针,一个prior,一个next
typedef struct DNode
{
int data;
struct DNode *prior, *next;
} DNode, *DLinkList;
// 1.初始化双链表
bool InitDLinkList(DLinkList &L)
{
L = (DNode *)malloc(sizeof(DNode));
if (L == NULL)
return false;
// 头结点的prior永远指向NULL,头结点之后暂时还没有节点
L->prior = NULL;
L->next = NULL;
return true;
}
// 2.双链表中插入操作
bool InsertNextDNode(DNode *p, DNode *s)
{
if (p == NULL || s == NULL)
return false;
s->next = p->next;
// 如果p节点有后继结点
// 如果是循环双链表,这个if判断可以省略
if (p->next != NULL)
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}
// 3.循环双链表中删除操作
bool DeleteNextNode(DNode *p, DNode *s)
{
if (p == NULL)
return false;
DNode *q = p->next;
if (q == NULL)
return false;
p->next = q->next;
if (q->next != NULL)
q->next->prior = p;
return true;
}
原文地址:https://blog.csdn.net/2201_76119663/article/details/142686907
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!