数据结构是计算机专业很重要的一门专业课，网上也有很多代码实现，博主在复习数据结构时重新实现了一边线性结构，线性表、栈、队列这些网上有大把大把的理论解释，就不再细说（主要还是因为懒得打字
），代码虽然网上也是一大堆，但就是想在自己博客中记录下自己的实现。
线性表
Java实现（链表）：
import java.util.Iterator;
public class LinkList<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
private int N = 0;
private Node head = null;
//是否为空表
public boolean isEmpty() {
return N == 0;
}
//获取表的大小
public int size() {
return N;
}
//添加元素
public void add(Item item) {
Node newNode = new Node();
newNode.data = item;
newNode.next = null;
if (head == null) {
head = newNode;
N++;
} else {
Node cur = head;
while (cur.next != null) {
cur = cur.next;
}
cur.next = newNode;
N++;
}
}
//取得第i个元素
public Item getItem(int i) {
if(i > 0 && !isEmpty()) {
Node cur = head;
for (int j = 1; j < i; j++) {
cur = cur.next;
}
return cur.data;
}
return null;
}
//在第i个元素后插入元素
public void insert(int i, Item item) {
if(i <= N) {
Node cur = head;
for (int j = 1; j < i; j++) {
cur = cur.next;
}
Node oldCur = cur;
Node next = cur.next;
cur = new Node();
cur.data = item;
cur.next = next;
oldCur.next = cur;
N++;
}
}
//取得元素是第几个
public int locate(Item item) {
Node cur = head;
int i = 1;
while(cur != null) {
if(cur.data.equals(item)) {
return i;
}
++i;
cur = cur.next;
}
//不存在返回-1
return -1;
}
//删除第i个元素
public void delete(int i) {
if(i <= N) {
Node cur = head;
for (int j = 1; j < N - i - 1; j++)
cur = cur.next;
Node del = cur.next;
cur.next = del.next;
del.data = null;
del.next = null;
N--;
}
}
/*
* 已下为迭代器的实现，便于直接使用foreach遍历链表
*/
@Override
public Iterator<Item> iterator() {
return new ListIterator();
}
private class ListIterator implements Iterator<Item> {
private Node cur = head;
@Override
public void remove() {
}
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public Item next() {
Item item = cur.data;
cur = cur.next;
return item;
}
}
}C/C++实现（顺序存储）：
#include <stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 //线性表的存储空间的初始分配量
#define LISTINCREMENT 10 //线性表的存储空间的的分配增量
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//初始化线性表，初始化结构体参数，主要是为线性表的存放申请空间
int initList(SqList &L){
//构造一个线性表L
L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
if (!L.elem) exit(OVERFLOW);
L.length = 0;
L.listsize = LIST_INIT_SIZE;
return OK;
}
// 创建线性表，初始化函数线性表所申请的内存，初始化数据
int createList(SqList &L, int n)
{
ElemType *newbase;
int i;
if (n<0)
{
return ERROR;
}
if (n>L.listsize)
{
newbase = (ElemType*)realloc(L.elem, (L.listsize + n)*sizeof(ElemType));
if (!newbase) exit(OVERFLOW);
L.elem = newbase;
L.listsize += n;
}
L.length = n;
printf("请输入数据，用空格分隔:\n");
for (i = 0; i<n; i++)
{
scanf("%d", &(L.elem[i]));
}
return OK;
}
//在线性表指定位置插入一个数据
int listInsert(SqList &L, int i, ElemType e)
{
ElemType* newbase, *q, *p;
if (i<1 || i>L.length) return ERROR;
if (L.length > L.listsize)
{
newbase = (ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
if (!newbase) exit(OVERFLOW);
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
q = &(L.elem[i - 1]);
for (p = &(L.elem[L.length - 1]); p >= q; --p)
{
*(p + 1) = *p;
}
*q = e;
++L.length;
return OK;
}
//删除线性表指定位置的数值，并且返回删除的数据，保存在 e.
int listDelete(SqList &L, int i, ElemType &e)
{
ElemType *p, *q;
if ((i<1) || (i>L.length)) return ERROR;
p = &(L.elem[i - 1]);
e = *p;
q = L.elem + L.length - 1;
for (++p; p <= q; ++p)
{
*(p - 1) = *p;
}
--L.length;
return OK;
}
//查找线性表中的是否包含某个值，返回满足条件的第一个位置
int compare(ElemType a, ElemType b)
{
if (a == b)
{
return TRUE;
}
return FALSE;
}
//取得元素是第几个
int locateElem(SqList L, ElemType e, int(*compare)(ElemType, ElemType))
{
int i;
ElemType *p;
i = 1;
p = L.elem;
while (i <= L.length && !(*compare)(*p++, e))
{
++i;
}
if (i <= L.length)
{
return i;
}
return 0;
}
//删除线性表，主要功能是将 malloc 或者 realloc 函数分配而来的内存释放掉
int destroyList(SqList &L)
{
if (L.elem)
{
free(L.elem);
}
return OK;
}
//打印线性表
int showList(SqList &L)
{
int i;
if (L.length <= 0)
{
return ERROR;
}
for (i = 0; i<L.length; i++)
{
printf("%d\t", L.elem[i]);
}
printf("\n");
return OK;
}C/C++实现（链式存储）：
#include<stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define LIST_INIT_SIZE 100 //线性表的存储空间的初始分配量
#define LISTINCREMENT 10 //线性表的存储空间的的分配增量
typedef int ElemType;
typedef struct Node
{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
// 当第i个元素存在时，其值赋给e,并返回OK , 否则返回ERROR
int getElem(LinkList L, int i, ElemType &e)
{
LinkList p;
int j;
p = L->next; //初始化，p 指向第一个节点
j = 1; //j为计数器
while (p && j<i)
{
p = p->next;
++j;
}
//判断该位置是否合法
if (!p || j>i)
{
return ERROR;
}
//取第i个元素
e = p->data;
return OK;
}
//在带头结点的单链线性表L中第 i 个位置之前插入元素 e
int listInsert(LinkList &L, int i, ElemType e)
{
LinkList p, s;
int j;
p = L;
j = 0;
//寻找第i-1个节点
while (p && j<i - 1)
{
p = p->next;
++j;
}
if (!p || j>i - 1)
{
return ERROR;
}
//生成新节点，插入到L中
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
//在带头节点的单链表L中，删除第i个元素，并由e 返回其值
int listDelete(LinkList &L, int i, ElemType &e)
{
LinkList p, q;
int j;
p = L;
j = 0;
//寻找第i个节点，并令p指向其前驱
while (p->next && j<i - 1)
{
p = p->next;
++j;
}
//位置不合理
if (!(p->next) && j>i - 1)
{
return ERROR;
}
//删除并释放节点
q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
//建立带表头的节点的单链线性表L
void createList(LinkList &L, int n)
{
int i;
LinkList p;
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
printf("请输入 %d 个数据:\n", n);
for (i = n; i>0; --i)
{
//生成新节点
p = (LinkList)malloc(sizeof(LNode));
//输入元素值
scanf("%d", &p->data);
p->next = L->next;
L->next = p;
}
}
//删除带有头结点的链表
void destroyList(LinkList &L)
{
LinkList p, q;
p = L->next;
while (p != NULL)
{
q = p->next;
free(p);
p = q;
}
}
//打印链表
void showList(LinkList &L)
{
LinkList p = L->next;
while (p != NULL)
{
printf("%d\t", p->data);
p = p->next;
}
printf("\n");
}栈
Java实现（顺序存储）：
import java.util.Iterator;
/*
* 顺序栈
* 效率低，效率与栈的大小成正比
*/
public class SequenceStack<Item> implements Iterable<Item>{
private Item[] data = (Item[]) new Object[1];
private int top = 0;
//取得栈的大小
public int size() {
return top;
}
//是否为空栈
public boolean isEmpty(){
return top == 0;
}
//调整栈的大小
public void resize(int size) {
Item[] now = (Item[]) new Object[size];
for (int i = 0; i < top; i++) {
now[i] = this.data[i];
this.data[i] = null;
}
this.data = now;
}
//入栈
public void push(Item item) {
if(top == data.length) resize(2 * data.length);
data[top++] = item;
}
//出栈
public Item pop() {
Item item = null;
if(top > 0) {
item = data[--top];
data[top] = null;
if (top < data.length / 4) resize(data.length / 2);
}
return item;
}
//取得栈顶元素
public Item getTop() {
return data[top - 1];
}
//清空栈
public void clear(){
this.top = 0;
}
/*
* 一下为迭代器实现，便于使用foreach遍历栈
*/
@Override
public Iterator<Item> iterator() {
return new StackIterator();
}
private class StackIterator implements Iterator<Item> {
private int i = top;
@Override
public void remove() {
}
@Override
public boolean hasNext() {
return i > 0;
}
@Override
public Item next() {
return data[--i];
}
}
}Java实现（链式存储）：
import java.util.Iterator;
public class Stack<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
private int N = 0;
private Node head = null;
public void push(Item item) {
Node oldHead = head;
head = new Node();
head.data = item;
head.next = oldHead;
N++;
}
public Item pop() {
if(!isEmpty()) {
Item item = head.data;
head.data = null;
head = head.next;
N--;
return item;
}
return null;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
public boolean clear() {
if(!isEmpty()) {
int n = N;
for(int i = 0; i < n; i++)
pop();
return true;
}
return false;
}
public Item getTop() {
if(!isEmpty())
return head.data;
return null;
}
@Override
public Iterator<Item> iterator() {
return new StackIterator();
}
private class StackIterator implements Iterator<Item> {
private Node cur = head;
@Override
public void remove() {
}
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public Item next() {
Item item = cur.data;
cur = cur.next;
return item;
}
}
}C/C++实现（顺序存储）：
#include <stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define STACK_INIT_SIZE 100 //存储空间分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef int SElemType;
typedef struct{
SElemType *base; //在构造之前和销毁之后，base的值为NULL
SElemType *top; //栈顶指针
int stacksize; //当前已分配的存储空间，以元素为单位
}SqStack;
//构造一个空栈
int initStack(SqStack &S)
{
S.base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if (!S.base) exit(OVERFLOW); //分配失败
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}
//销毁一个栈
int destroyStack(SqStack &S)
{
if (!S.base)
{
printf("不存在该栈\n");
return OK;
}
free(S.base);
return OK;
}
//得到栈顶的元素
int getTop(SqStack S, SElemType &e)
{
//若栈不空，则用e 返回S 的栈顶元素，并返回OK;否则返回ERROR
if (S.top == S.base) return ERROR;
e = *(S.top - 1);
return OK;
}
//入栈
int push(SqStack &S, SElemType e)
{
//插入元素e为新的栈顶元素
//栈满追加存储空间
if (S.top - S.base >= S.stacksize)
{
S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if (!S.base) exit(OVERFLOW);//分配存储失败
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}
//出栈
int pop(SqStack &S, SElemType &e)
{
//若栈不空，则删除S的栈顶元素，用e 返回其值，并返回OK;否则返回ERROR
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}
//打印栈中的数据
int displayStack(SqStack S)
{
if (S.top == S.base)
{
printf("该栈为空\n");
return OK;
}
printf("栈中的内容是：\n");
for (; S.top != S.base;)
{
printf("%d\t", *(--S.top));
}
printf("\n");
return OK;
}队列
Java实现（链式存储）：
import java.util.Iterator;
public class Queue<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
private Node head = null;
private Node tail = null;
private int N = 0;
public boolean isEmpty() {
return N == 0;
}
public void enQueue(Item item) {
Node oldTail = tail;
tail = new Node();
tail.data = item;
tail.next = null;
if(isEmpty())
head = tail;
else
oldTail.next = tail;
N++;
}
public Item deQueue() {
Item item = null;
if(!isEmpty()) {
item = head.data;
head.data = null;
head = head.next;
N--;
return item;
}
return null;
}
public Item getHead() {
if(!isEmpty()) {
return head.data;
}
return null;
}
public int size() {
return N;
}
@Override
public Iterator<Item> iterator() {
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item> {
private Node cur = head;
@Override
public void remove() {
}
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public Item next() {
Item item = cur.data;
cur = cur.next;
return item;
}
}
}C/C++实现（链式存储）：
#include <stdio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
//队列的链式存储结构
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
int initQueue(LinkQueue &Q)
{
//构造一个空队列 Q
Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));
if (!Q.front) exit(OVERFLOW); //存储分配失败
Q.front->next = NULL;
return OK;
}
int destroyQueue(LinkQueue &Q)
{
//销毁队列
while (Q.front)
{
Q.rear = Q.front->next;
free(Q.front);
Q.front = Q.rear;
}
return OK;
}
int enQueue(LinkQueue &Q, QElemType e)
{
//插入元素e 为Q 的新队列
QueuePtr p;
p = (QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW); //存储分配失败
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
int deQueue(LinkQueue &Q, QElemType &e)
{
//若队列不空，则删除Q的队头元素，用e 返回其值，并返回Ok;
//否则返回ERROR
QueuePtr p;
if (Q.front == Q.rear) return ERROR;
p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p) Q.rear = Q.front;
free(p);
return OK;
}
//打印队中的元素
int displayQueue(LinkQueue &Q)
{
QueuePtr front, rear;
front = Q.front->next;
rear = Q.rear;
if (front == rear)
{
printf("空队列\n");
return OK;
}
while (front != NULL)
{
printf("%d\t", front->data);
front = front->next;
}
printf("\n");
return OK;
}背包
Java实现：
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item> {
private class Node {
Item data;
Node next;
}
private int N = 0;
private Node head = null;
public void add(Item item) {
Node oldHead = head;
head = new Node();
head.data = item;
head.next = oldHead;
N++;
}
public int size() {
return N;
}
public boolean isEmpty() {
return N == 0;
}
@Override
public Iterator<Item> iterator() {
return new BagIterator();
}
private class BagIterator implements Iterator<Item> {
private Node cur = head;
@Override
public void remove() {
}
@Override
public boolean hasNext() {
return cur != null;
}
@Override
public Item next() {
Item item = cur.data;
cur = cur.next;
return item;
}
}
}
大佬，Java实现用Object类代替泛型也可以吧
@Agoni : 当然可以，但使用Object存在一些问题，比如栈，在pop()的时候需要转型，如果将错误的类型数据压入栈中，错误只能在执行pop()时才能发现（抛出异常），而使用泛型可以在编译时就发现问题（压入错误类型数据将无法通过编译）