线性表，栈和队列

[thyecust]

线性表

线性表是一种线性结构，也就是说一个数据集合中，有第一元素和最后元素，其他元素都有唯一的前驱和唯一的后继。

线性表可以定义为一种 ADT

D = { ai | i = 0,1,2, ... }
R = { <ai-1,ai> | ai-1,ai in D }

方法包括

• keyOf(i)，根据索引返回值
• find(x)，找到第一个值为 x 的元素的索引
• insert(i, x)，在 i 索引前面插入一个新元素 x
• delete(i)，删除索引为 i 的元素
• size()，返回表的长度

顺序表

顺序表就是用顺序存储的方式实现线性表。

slist.h

#define MAXSIZE 1000

struct SeqList {
    int elements[MAXSIZE];
    int n;
};
typedef struct SeqList *PSeqList;

PSeqList createList_seq(void);
bool isEmpty_seq(PSeqList pslist);
bool insert_seq(PSeqList pslist, int i, int x);
bool delete_seq(PSeqList pslist, int i);
int find_seq(PSeqList pslist, int x);
int keyOf_seq(PSeqList pslist, int i);

#include <iostream>
#include "slist.h"
using namespace std;

PSeqList makeList_seq(void) {
    PSeqList pslist = (PSeqList)malloc(sizeof(struct SeqList));
    if (pslist != NULL) {
        pslist -> n = 0;
    } else {
        cout<<"存储分配失败\n";
    }
    return pslist;
}

bool isEmpty_seq(PSeqList pslist) {
    return pslist -> n == 0;
}

bool insert_seq(PSeqList pslist, int i, int x) {
    if (pslist -> n == MAXSIZE) {
        cout<<"SeqList 超出长度\n";
        return false;
    }
    if (i < 0 || i > pslist -> n) {
        cout << "插入位置不合法\n";
        return false;
    }

    int q;
    for (q = pslist -> n - 1; q >= i; q--) {
        pslist -> elements[q+1] = pslist -> elements[q];
    }
    pslist -> elements[i] = x;
    pslist -> n++;
    return true;
}

bool delete_seq(PSeqList pslist, int i) {
    if (i < 0 || i >= pslist -> n) {
        cout << "删除位置不合法\n";
        return false;
    }
    int q;
    for (q = i; q <= pslist -> n - 1; q++) {
        pslist -> elements[q] = pslist -> elements[q+1];
    }
    pslist -> n--;
    return true;
}

int find_seq(PSeqList pslist, int x){
    int q;
    for (q = 0; q <= pslist -> n - 1; q++) {
        if (pslist -> elements[q] == x){
            return q;
        }
    }
    return -1;
}

int keyOf_seq(PSeqList pslist, int i) {
    if (i < 0 || i >= pslist -> n) {
        cout << "位置不合法\n";
        return -1;
    }
    return pslist -> elements[i];
}

int main() {
    PSeqList list = makeList_seq();
    insert_seq(list,0,1);
    insert_seq(list,0,2);
    cout << list->elements[0] << list->elements[1];
    cout << keyOf_seq(list,1);
    cout << isEmpty_seq(list);
    return 0;
}

[thyecust]

链表

llist.h

struct Node;
typedef struct Node* PNode;
typedef struct Node* LinkList;

struct Node {
    int data;
    PNode next;
};

LinkList makeList_link(void);
bool isEmpty_link(LinkList pslist);
bool insert_link(LinkList pslist, int i, int x);
bool delete_link(LinkList pslist, int i);
int find_link(LinkList pslist, int x);
int keyOf_link(LinkList pslist, int i);

#include <iostream>
#include "llist.h"
using namespace std;

LinkList makeList_link(void) {
    LinkList llist = (LinkList)malloc(sizeof(struct Node));
    if (llist != NULL) {
        llist -> next = NULL;
    }
    return llist;
}

bool isEmpty_link(LinkList llist) {
    return llist == NULL || llist -> next == NULL;
}

bool insert_link(LinkList llist, int i, int x){
    PNode p = llist;
    int j;
    for (j = 0; p != NULL && j < i; j++){
        p = p -> next;
    }
    if (j != i){
        cout << "超出范围\n";
        return false;
    }
    PNode q = (PNode)malloc(sizeof(struct Node));
    if (q == NULL) {
        cout << "内存分配失败\n";
        return false;
    }
    q -> data = x;
    q -> next = p -> next;
    p -> next = q;
    return true;
}

bool delete_link(LinkList llist, int i) {
    PNode p = llist;
    int j;
    for (j = 0; p != NULL && j < i; j++){
        p = p -> next;
    }
    if (j != i){
        cout << "超出范围\n";
        return false;
    }
    PNode q = p -> next;
    p -> next = q -> next;
    free(q);
    return true;
}

void list_show(LinkList llist) {
    PNode p = llist;
    while (p != NULL) {
        cout << p->data << endl;
        p = p->next;
    }
}

int find_link(LinkList llist, int x) {
    PNode p = llist;
    int j;
    for (j = 0; p != NULL && p -> data != x; j++){
        p = p -> next;
    }
    if (p -> data = x) {
        return j-1;
    } else {
        return -1;
    }
}
    
int keyOf_link(LinkList llist, int i) {
    PNode p = llist;
    int j;
    for (j = 0; p != NULL && j < i; j++){
        p = p -> next;
    }
    if (j != i){
        cout << "超出范围\n";
        return false;
    }
    return p->next->data;
}

int main() {
    LinkList llist = makeList_link();
    insert_link(llist,0,1);
    insert_link(llist,0,2);
    insert_link(llist,1,3);
    list_show(llist);
    cout << find_link(llist,3);
    return 0;
}