线性结构

:material-circle-edit-outline: 约 274 个字 :fontawesome-solid-code: 71 行代码 :material-clock-time-two-outline: 预计阅读时间 2 分钟

线性表 (Linear List)

线性表 (Linear List) 即由同类型的数据元素构成的 有序序列 的线性结构

• 长度：元素个数
• 空表：无元素
• 表头、表尾：起始位置与结束位置

操作集

List MakeEmpty() ：初始化空线性表 L

List MakeEmpty(){
    List PtrL;
    PtrL = (List)malloc(sizeof (struct LNode));
    PtrL->Last = -1;
    return PtrL;
}

ElementType FindKth (int K, List L) ：根据位序 K ，返回相应元素

int Find (ElementType X, List L) ：找到

...

实现

typedef struct LNode *List;
struct LNode{
    ElementType Data[MAXSIZE];
    int Last;   //pos of last element; length = Ptrl->Last+1
}
struct LNode L;
List PtrL;  //ptr --> pointer

堆栈（stack）

顺序存储实现

typedef srtuct SNode *Stack;
struct SNode{
    ElementType Data[MaxSize];
    int top;
};

Push

void Push(Stack PtrS, item){
    if(PtrS->top == MAXSIZE-1)
        return;
    else
        PtrS->Data[++(PtrS->top)] = item;    
}

Pop

#define ERROR 6666
ElementType Pop(Stack PtrS){
    if(PtrS->top == -1)
        return ERROR;
    else 
        return (PtrS->Data[(PtrS->top)--])
}

改进

对于一个堆栈，初始化时已经占用了MAXSIZE的空间，大部分空间可能都用不上，如此造成浪费。

如果这个数组让两个堆栈分别两头使用，就能提高空间利用率。

struct DStack{
    int Data[MAXSIZE];
    int top1;
    int top2;
} S;

//top1->-1;
//top2->MAXSIZE;
//传参多一个用tag标志用哪个堆栈即可

链表实现

S是空的，第一个是S->Next

typedef struct SNode *Stack;
struct SNode{
    int data;
    struct SNode *Next;
};

Create

Stack S;
S = (Stack)malloc(sizeof(struct SNode));
S->Next = NULL;
return S;

Empty

return (S->Next == NULL);

Push

struct SNode *Tmp;
Tmp = (struct SNode *)malloc(siezof(syruct SNode));
Tmp->data = item;
tmp->Next = S->Next;
S->Next = Tmp;

队列（queue）

一端输入，另一端输出/删除

分顺序队列和顺环队列

• 顺环队列即闭合的队列

注意：front是dequeue的地方，rear是enqueue的地方，与直觉相反！！！

而且front是空的，rear是有元素的

极其容易出错

顺序存储实现

stryct QNode{
    int data[MAXSIZE];
    int rear;
    int front;
};

链式存储实现

struct Node{
    int data;
    struct Node *Next;
};

struct QNode{
    struct Node *rear;
    struct Node *front;
};
typedef struct QNode *Queue;
Queue PrtQ;