线性表,栈和队列
Opened this issue · 1 comments
thyecust commented
线性表
线性表是一种线性结构,也就是说一个数据集合中,有第一元素和最后元素,其他元素都有唯一的前驱和唯一的后继。
线性表可以定义为一种 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 索引前面插入一个新元素 xdelete(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 commented
链表
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;
}