数据结构代码实现——线性结构

当前位置: Home » 技术 » 数据结构代码实现——线性结构

数据结构是计算机专业很重要的一门专业课，网上也有很多代码实现，博主在复习数据结构时重新实现了一边线性结构，线性表、栈、队列这些网上有大把大把的理论解释，就不再细说（主要还是因为懒得打字），代码虽然网上也是一大堆，但就是想在自己博客中记录下自己的实现。

线性表

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;
        }
    }
}

声明：迟於|版权所有，违者必究|如未注明，均为原创|本网站采用BY-NC-SA协议进行授权

转载：转载请注明原文链接 - 数据结构代码实现——线性结构

栖迟於一丘