数据结构线性存储
一级目录
链表：
#if 0
#include<iostream>
using namespace std;
typedef int Status;
//typedef struct {
// char num[8];
// char name[8];
// int score;
//}ElemType;
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
//Lnode L;
Status InitList_L(LinkList &L)
{
//L = (LinkList)malloc(sizeof(Lnode));
L = new Lnode;
L->next = NULL;
}
int ListEmpty(LinkList L)
{
if (L->next) {
return 0;
}
else {
return false;
}
}
Status DeStroyList(LinkList &L)
{
Lnode *p;
while (L)
{
p = L;
L = L->next;
delete p;
}
}
Status ClearList(LinkList &L)
{
Lnode *p,*q;
p = L->next;
while (p)
{
q = p->next;
delete p;
p = q;
}
L->next = NULL;
}
int ListLength_L(LinkList L)
{
Lnode *p;
int i = 0;
p = L->next;
if (L->next == NULL) return 0;
else
{
while (p)
{
i++;
p = p->next;
}
return i;
}
}
//单链表的基本操作
Status GetElem_L(LinkList L, int i, ElemType &e)
{
Lnode *p;
int j = 1;
p = L->next;
while (p&&j < i)
{
p = p->next;
j++;
}
if (!p || j > i) return false;
e = p->data;
}
Lnode *LocateElem_L(LinkList L, ElemType e)
{
Lnode *p = L->next;
while (p && p->data != e)
{
p = p->next;
return p;
}
}
int LocateElem(LinkList L, ElemType e)
{
Lnode *p = L->next;
int j = 1;
while (p && p->data != e)
{
p = p->next;
j++;
}
if (p) {
return j;
}
return false;
}
//插入第i个节点
Status ListInsert_L(LinkList &L, int i, ElemType e)
{
Lnode *p = L;
int j = 0;
while (p && j < i - 1)
{
p = p->next;
j++; //让p指向i-1位置
}
if (!p || j > i - 1)
{
return false;
}
Lnode * s = new Lnode;
s->data = e;
s->next = p->next;
p->next = s;
}
// 删除
Status ListDelete_L(LinkList &L, int i, ElemType &e)
{
Lnode *p = L;
int j = 0;
int i = 0;
Lnode *q = new Lnode;
while (p->next && j < i - 1)
{
p = p->next;
j++;
}
if (!(p->next) || j > i - 1) return false;
q = p->next;
p->next = q->next;
e = q->data;
delete q;
}
//头插法建立单链表
void CreatList_H(LinkList &L, int n)
{
Lnode *L = new Lnode;
L->next = NULL;
for (int i = n; i > 0; --i)
{
Lnode *p = (Lnode*)malloc(sizeof(Lnode));
p->next = L->next;
L->next = p;
}
}
//尾插法建立单链表
void CreatList_R(LinkList &L, int n)
{
Lnode *L = new Lnode;
L->next = NULL;
Lnode *r = new Lnode;
r = L;
for (int i = 0; i < n; i++)
{
Lnode *p = new Lnode;
p->next = NULL;
r->next = p;
r = p;
}
}
typedef int ElemType;
typedef struct Lnode
{
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
int main()
{
return 0;
}
#endif // 0
二级目录
链栈：
#if 0
#include<iostream>
using namespace std;
//链栈是运算受限的单链表，只能在链表头部进行操作
/*
链表的头指针就是栈顶
不需要头节点
基本不存在栈满的情况
空栈相当于头指针指向空
插入和删除仅在栈顶处执行
*/
typedef int SElemType;
typedef int Status;
typedef struct StackNode
{
SElemType data;
struct SatckNode *next;
}StackNode,*Linkstack;
//链栈的初始化
Status InitStack(Linkstack &S)
{
//构造一个空栈，栈顶指针置空
Linkstack S = (Linkstack)malloc(sizeof(StackNode));
if (!S)
{
return false;
}
else
{
S = NULL;
return true;
}
}
Status StackEmpty(Linkstack S)
{
if (S == NULL)
{
return true;
}
else
{
return false;
}
}
Status Push(Linkstack &S, SElemType e)
{
StackNode *p = new StackNode;
p->data = e;
p->next = S;
S = p;
return true;
}
Status Pop(Linkstack &S, SElemType &e)
{
StackNode *p = new StackNode;
if (S == NULL) return false;
e = S->data;
p = S;
S = S->next;
delete p;
return true;
}
int main()
{
return 0;
}
#endif // 0
三级目录
队列：
#if 0
#include<iostream>
using namespace std;
//链式队列
#define MAXQSIZE 100
typedef int Status;
typedef int QEleType;
typedef struct Qnode
{
QEleType data;
struct Qnode *next;
}Qnode,*QueuePtr;
typedef struct
{
QueuePtr front;
QueuePtr rear;
}LinkQueue;
Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (QueuePtr)malloc(sizeof(Qnode));
if (!Q.front) exit(OVERFLOW);
else
{
Q.front->next = NULL;
return true;
}
}
//从队头结点开始，以此释放所有结点
Status DestroyQueue(LinkQueue &Q)
{
Qnode *p = new Qnode;
while (Q.front)
{
p = Q.front->next;
free(Q.front);
Q.front = p;
return true;
}
delete p;
p = nullptr;
}
//入队
Status EnQueue(LinkQueue &Q, QEleType e)
{
Qnode *p = (QueuePtr)malloc(sizeof(Qnode));
if (!p) exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return true;
}
Status DeQueue(LinkQueue &Q, QEleType e)
{
Qnode *p = (QueuePtr)malloc(sizeof(Qnode));
if (Q.front == Q.rear) exit(OVERFLOW);
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
delete p;
return true;
}
Status GetHead(LinkQueue Q, QEleType &e)
{
if (Q.front == Q.rear) return false;
return e = Q.front->next->data;
}
//循环队列
#define MAXQSIZE 100
typedef int QElemType;
typedef int Status;
typedef struct
{
QElemType *base;
int front;
int rear;
}SqQueue;
Status IninQueue(SqQueue &Q)
{
Q.base = new QElemType(MAXQSIZE);
//Q.base = (QElemType*)malloc(sizeof(QElemType)*MAXQSIZE);
if (!Q.base) exit(OVERFLOW);
Q.front = Q.rear = 0;
}
int QueueLength(SqQueue Q)
{
return ((Q.rear - Q.front + MAXQSIZE) % MAXQSIZE);
}
//入队
Status EnQueue(SqQueue &Q, QElemType &e)
{
if ((Q.rear + 1) % MAXQSIZE == Q.front) exit(OVERFLOW);//队满
else
{
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
return true;
}
}
//出队
Status DeQueue(SqQueue &Q, QElemType e)
{
if (Q.front == Q.rear) exit(OVERFLOW);
else
{
e = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
return true;
}
}
//取队头元素
/*Status GetHead(SqQueue Q)
{
if (Q.base != Q.front);
return Q.base[Q.front];
}*/
int main()
{
return 0;
}
#endif // 0