【数据结构】基础结构实现集合

一些我早期学数据结构的时候用C++实现的代码。指针在实现上比较方便

(1)栈

#include<iostream>

using namespace std;

#define OK 1
#define ERROR 0

typedef int SElemType;
typedef struct StackNode{
    SElemType data;
    struct StackNode *next;
}StackNode,*LinkStack;

int InitStack(LinkStack &top){
    top = (StackNode*)malloc(sizeof(StackNode));
    if(top!=NULL){
        top = NULL;
    }
    return OK;
}

int Push(LinkStack &top,SElemType e){
    LinkStack p =(StackNode*)malloc(sizeof(StackNode));
    p->data=e;
    p->next=top;
    top=p;
    return OK;
}

int CreateStack(LinkStack &top){
    int n;
    cout << "输入入栈元素个数:";
    cin>>n;
    for(int i=0;i<n;i++){
        int m;
        cout<<"输入进栈元素:";
        cin>>m;
        Push(top,m);
    }
    return OK;
}

int Pop(LinkStack &top,SElemType &e){
    LinkStack p;
    if(top!=NULL){
        p=top;
        e = top->data;
        top = top->next;
        free(p);
    }
    else
        return ERROR;
    return OK;
}

int GetTop(LinkStack top,SElemType &e){
    if(top!=NULL)
        e = top->data;
    else
        return ERROR;
    return OK;
}

void outStack(LinkStack top){
    while(top!=NULL){
        cout<<top->data<<endl;
        top=top->next;
    }
}


int main(){
    LinkStack top;
    InitStack(top);
    CreateStack(top);
    outStack(top);
    int e;
    cout<<"出栈一次;";
    Pop(top,e);
    cout<<"出栈元素:"<<e<<endl;
    outStack(top);
    GetTop(top,e);
    cout<<"栈顶元素为:"<<e<<endl;

    return 0;
}

(2)静态链表

#include<iostream>

using namespace std;

#define MAXSIZE 1000
#define OK 1
#define ERROR 0
#define FALSE 0
#define TRUE 1

typedef int status;

typedef struct{
    status data;
    int cur;
}
component,    SLinkList[MAXSIZE];

//初始化
status InitList(SLinkList space){
    int i;
    for(i=0;i<MAXSIZE-1;i++)
        space[i].cur = i+1;
    space[MAXSIZE-1].cur=0;
    return OK;
}

//若备用空间链表非空，返回分配的结点下标
int Malloc_SLL(SLinkList space){
    int i = space[0].cur;

    if(space[0].cur)
        space[0].cur = space[i].cur;

    return i;
}

int ListLength(SLinkList sl){
    int j=0;
    int i=sl[MAXSIZE-1].cur;
    while(i){
        i=sl[i].cur;
        j++;
    }
    return j;
}


//插入
status ListInsert(SLinkList L,int i,status e){
    int j,k,l;
    k=MAXSIZE-1;
    if(i<1||i>ListLength(L)+1)
        return ERROR;
    j=Malloc_SLL(L);
    if(j){
        L[j].data=e;
        for(l=1;l<=i-1;l++)
            k=L[k].cur;
        L[j].cur=L[k].cur;
        L[k].cur=j;
        return OK;
    }
    return ERROR;
}

//回收空闲结点
void Free_SSL(SLinkList space,int k){
    space[k].cur=space[0].cur;
    space[0].cur=k;
}
//删除
status ListDelete(SLinkList L,int i){
    int j,k;
    if(i<1||i>ListLength(L))
        return ERROR;
    k = MAXSIZE-1;
    for(j=1;j<=i-1;j++)
        k=L[k].cur;
    j=L[k].cur;
    L[k].cur=L[j].cur;
    Free_SSL(L,j);
    return OK;
}


int main(){
    return 0;
}

(3)链式存储结构表及表间操作

#include<iostream>
#include<stdlib.h>
#include<time.h>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

typedef struct LNode{
    Status data;
    struct LNode *next;                
}LNode ,*LinkList;

Status InitList(LinkList &L){
    L = (LNode*)malloc(sizeof(LNode));

    if(L == NULL)
        return ERROR;
    L->next=NULL;
    return OK;
}

Status GetElem(LinkList L,int i,Status *e){
    int j;
    LinkList p;
    p = L->next;
    j = 1;
    while(p&&j<i){
        p = p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    *e = p->data;
    return OK;
}

Status ListInsert(LinkList &L,int i,Status e){
    int j;
    LinkList p,s;
    p = L;
    j=1;
    while( p && j<i ){
        p=p->next;
        ++j;
    }
    if(!p||j>i)
        return ERROR;
    s =(LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;

    p->next = s;  
    return OK;
}

Status ListDelete(LinkList &L,int i,Status *e){
    int j;
    LinkList p,q;

    p = L;
    j = 1;
    while(p->next&&j<i){
        p = p->next;
        ++j;
    }
    if(!(p->next)||j>i)
        return ERROR;
    q=p->next;
    p->next=q->next;
    *e = q->data;
    free(q);
    return OK;
}

void CreateList(LinkList &L,int n){
    LinkList p ;
    int i;
    srand(time(0));
    L->next=NULL;
    for(i=0;i<n;i++){
        p=(LinkList) malloc(sizeof(LNode));
        p->data=rand()%100+1;
        p->next=L->next;
        L->next = p;
    }
}

Status ClearList(LinkList &L){
    LinkList p,q;
    p=L->next;
    while(p){
        q=p->next;
        free(p);
        p=q;
    }
    L->next=NULL;
    return OK;
}

void unionList(LinkList &L,LinkList L1){
    LinkList p;
    p=L;
    L=p;
    while(p->next){
        p = p->next;
    }
    p->next=L1->next;
}

void outList(LinkList L){
    L=L->next;
    while(L!=NULL){
        cout<<L->data<<" ";
        L=L->next;
    }
    cout<<endl;
}

int main(){
    LinkList p;
    InitList(p);
    CreateList(p,4);
    outList(p);

    cout << "请输入插入元素位置：";
    int i;
    cin>>i;
    cout<<"请输入插入元素:";
    int e;
    cin>>e;
    ListInsert(p,i,e);
    outList(p);

    cout<<"请输入删除元素位置:";
    int j;
    int num;
    cin>>j;
    ListDelete(p,j,&num);
    outList(p);
    cout<<"删除元素为:"<<num<<endl;

    cout << "表2:";
    LinkList p1;
    InitList(p1);
    CreateList(p1,7);
    outList(p1);

    cout << "合并得:"<<endl;
    unionList(p,p1);
    outList(p);

    return 0;
}

(4)堆实现字符串

//字符串的堆分配表示与实现
#include<iostream>

using namespace std;

#define MAXISIZE 100
#define ERROR 0
#define OK 1

typedef struct string 
{
    char *str;
    int length;
}HeapString;

//初始化串
int initString(HeapString &pH)
{
    pH.str ='\0';
    pH.length = 0;
    return OK;
}

//给指定的字符串赋值
int strAssign(HeapString &pH,char cstr[])
{
    int i;
    int len;
    if(pH.str)
        free(pH.str);
    for( i = 0;cstr[i]!='\0';i++);
        len = i;
    if(!cstr)
    {
        pH.length = 0;
        pH.str = '\0';
    }
    else
    {
        pH.str = (char * )malloc(len*sizeof(char));
        if(!pH.str)
        {
            return ERROR;
        }
        for(i = 0;i<len;i++)
        {
            pH.str[i] = cstr[i];
        }
        pH.length = len;
    }
    return OK;
}

//字符串的插入
int strInsert(HeapString &pH,int pos,HeapString S)
{
    int i;
    if(pos<1||pos>pH.length+1)
        return ERROR;
    pH.str = (char *)realloc(pH.str,(pH.length+S.length)*sizeof(char));
    if(!pH.str)
        return ERROR;
    for(i = pH.length-1;i>=pos-1;i--)
    {
        pH.str[i+S.length] = pH.str[i];
    }

    for(i = 0;i<S.length;i++)
    {
        pH.str[i+pos-1]= S.str[i];
    }

    pH.length = pH.length+ S.length;
    return OK;

}

//字符串的复制
int strCopy(HeapString pH,HeapString &T)
{
    int i;
    int len = pH.length;
    T.str = (char * )malloc(len*sizeof(char));
    if(!T.str)
    {
        return ERROR;
    }
    for( i = 0;i<pH.length;i++)
    {
        T.str[i] = pH.str[i];
    }
    T.length = pH.length;
    return OK;
}

//字符串的输出
int outStr(HeapString pH)
{
    int i;
    for(i = 0;i<pH.length;i++)
    {
        cout<<pH.str[i];
    }
    cout<<endl;
    return OK;
}

int main()
{
    HeapString pH;
    char cstr[MAXISIZE];
    initString(pH);
    cout<<"请输入一个字符串:";
    gets(cstr);
    strAssign(pH,cstr);
    cout << "串1:";
    outStr(pH);

    HeapString pH1;
    initString(pH1);
    strCopy(pH,pH1);
    cout << "串2:";
    outStr(pH1);
    int pos;
    cout<<"请输入插入位置:";
    cin>>pos;
    strInsert(pH,pos,pH1);
    cout<<"插入操作后的串1:";
    outStr(pH);

    return 0;
}

(5)队列

#include<iostream>

using namespace std;

#define ERROR 0
#define OK 1

typedef int QElemType;
typedef struct QNode{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
    QueuePtr front,rear;
}LinkQueue;

int InitDL(LinkQueue &Q){
    Q.front = Q.rear=(QNode*)malloc(sizeof(QNode));
    if(!Q.front)
        return ERROR;
    Q.front->next=NULL;
    return OK;
} 

int InDL(LinkQueue &Q,QElemType e){
    QueuePtr p;
    p=(QueuePtr)malloc(sizeof(QNode));
    if(!p)
        return ERROR;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}

int OutDL(LinkQueue &Q,QElemType &e){
    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 getheadDL(LinkQueue Q,QElemType &e){
    e=Q.front->next->data;
    return OK;
}

int prinftDL(LinkQueue Q){
    QueuePtr p;
    p=Q.front->next;
    while(p){
        cout<<p->data<<"  ";
        p=p->next;
    }
    cout << endl;
    return OK;
}

int main(){
    LinkQueue Q;
    InitDL(Q);
    int m,n,e;
    cout<<"输入进队元素个数:";
    cin>>m;
    for(int i=0;i<m;i++){
        cout << "输入入队元素:";
        cin>>n;
        InDL(Q,n);
    }
    prinftDL(Q);
    getheadDL(Q,e);
    cout << "队头元素为:"<<e<<endl;
    OutDL(Q,e);    
    cout << "出队一次，出队元素为:"<<e<<endl;
    prinftDL(Q);
    return 0;
}

循环队列:

#include<iostream>

using namespace std;

#define MAXSIZE 5
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int QElemType;

typedef struct{
    QElemType data[MAXSIZE];
    int front;
    int rear;
}SqQueue;

//初始化
int InitQueue(SqQueue *Q){
    Q->front=0;
    Q->rear=0;
    return OK;
}

//返回长度
int QueueLength(SqQueue Q){
    return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

//插入元素e到队尾
int EnQueue(SqQueue *Q,QElemType e){
    if((Q->rear+1)%MAXSIZE==Q->front)
        return ERROR;
    Q->data[Q->rear]=e;
    Q->rear=(Q->rear+1)%MAXSIZE;

    return OK;
}

//若队列不空，则删除队头元素，用e返回其值
int DeQueue(SqQueue *Q,QElemType *e){
    if(Q->front==Q->rear)
        return ERROR;
    *e=Q->data[Q->front];
    Q->front=(Q->front+1)%MAXSIZE;

    return OK;
}

//输出队列
void outQueue(SqQueue Q){
    int j = (Q.rear-1+MAXSIZE)%MAXSIZE;
    for(int i=0;i<QueueLength(Q);i++){
        cout << (Q.data[j])<<" ";
        j=((--j) + MAXSIZE)%MAXSIZE;
    }
    cout << endl;
}

int main(){
    SqQueue sq;
    InitQueue(&sq);
    int a;
    int count;
    cout<<"输入插入元素个数:";
    cin>>count;
    for(int i=0;i<count;i++){
        cout << "输入插入元素:";
        cin>>a;
        EnQueue(&sq,a);        
    }

    outQueue(sq);

    int e;
    int num;
    cout << "删除元素个数:";
    cin >> num;
    for(int n=0;n<num;n++){
        DeQueue(&sq,&e);
        cout << "删除元素:"<< e << endl;        
    }
    outQueue(sq);

    cout<<"输入插入元素个数:";
    cin>>count;
    for(int m=0;m<count;m++){
        cout << "输入插入元素:";
        cin>>a;
        EnQueue(&sq,a);        
    }

    outQueue(sq);


    cout << "队列长度:" << QueueLength(sq) <<endl;


    return 0;
}

(6)二叉树

#include<iostream>
#include<stdlib.h>
using namespace std;

#define TRUE 1
#define FALSE 0
typedef struct BiTNode{
    int data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

int SearchBST(BiTree T,int key,BiTree f,BiTree &p){
    if(T==NULL){
        p = f;
        return FALSE;
    }
    else if(key == T->data){
        p=T;
        return TRUE;
    }
    else if(key<T->data)
        return SearchBST(T->lchild,key,T,p);
    else 
        return SearchBST(T->rchild,key,T,p);
}

int InsertBST(BiTree &T,int key){
    BiTree p,s;
    if(!SearchBST(T,key,NULL,p))
    {
        s = (BiTree)malloc(sizeof(BiTree));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!p)
            T=s;
        else if(key<p->data)
            p->lchild=s;
        else
            p->rchild=s;
        return TRUE;
    }
    else
        return FALSE;
}

int Delete(BiTree *p){
    BiTree q,s;
    if((*p)->lchild==NULL&&(*p)->rchild==NULL)
        *p=NULL;
    else if((*p)->rchild==NULL){
        q=(*p);
        (*p)=(*p)->lchild;
        free(q);
    }
    else if((*p)->lchild==NULL){
        q=(*p);
        (*p)=(*p)->rchild;
        free(q);
    }
    else{
        q=(*p);
        s=(*p)->lchild;
        while(s->rchild!=NULL){
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data;
        if(!s->lchild){
            if(q!=(*p))
                (q)->rchild=s->lchild;
            else
                (q)->lchild=s->lchild;
            }
        free(s);
    }
    return TRUE;
}

int DeleteBST(BiTree *T,int key){
    if(!*T)
        return FALSE;
    else{
        if(key==(*T)->data)
            return Delete(T);
        else if(key<(*T)->data)
            return DeleteBST(&(*T)->lchild,key);
        else
            return DeleteBST(&(*T)->rchild,key);
    }
}

int CreateBST(BiTree &T){

    int n;
    cout << "输入树的结点个数:";
    cin>>n;
    T=NULL;
    for(int i=0;i<n;i++){
        int m;
        cout << "输入元素:";
        cin>>m;
        InsertBST(T,m);
    }
    return TRUE;
}

int main(){
    BiTree T;
    CreateBST(T);
    BiTree f=NULL;
    BiTree    p;
    int key;
    cout << "请输入查找元素:";
    cin>>key;
    if(SearchBST(T,key,f,p)){
        cout<<"查找成功"<<endl;
    }
    else
        cout<<"未查到此数。"<<endl;

    int key1;
    cout<<"请输入删除元素:";
    cin>>key1;
    DeleteBST(&T,key1);
    int key2;
    cout << "请输入查找元素:";
    cin>>key2;
    if(SearchBST(T,key2,f,p)){
        cout<<"查找成功"<<endl;
    }
    else
        cout<<"未查到此数。"<<endl;
    return 0;
}

(7)图

#include<iostream>
#include "DL.h"

using namespace std;

#define ERROR 0
#define OK 1
#define MAXVEX 100
#define INFINITY 65535
typedef int Boolean;
Boolean visited[MAXVEX];
typedef char VertexType;
typedef int EdgeType;

//邻接矩阵
typedef struct{
    VertexType vexs[MAXVEX];
    EdgeType arc[MAXVEX][MAXVEX];
    int numVertexes,numEdges;
}MGraph;

void CreateMGraph(MGraph *G){
    int i,j,k,w;
    cout<<"输入顶点数和边数:\n";
    cin>>G->numVertexes;
    cin>>G->numEdges;
    for(i=0;i<G->numVertexes;i++){
        cout << "输入顶点:";
        cin>>G->vexs[i];
    }
    for(i=0;i<G->numVertexes;i++){
        for(j=0;j<G->numVertexes;j++){
            G->arc[i][j]=INFINITY;
        }
    }
    for(k=0;k<G->numEdges;k++){
        cout<<"输入边（vi,vj）上的下标i，下标j和权w:"<<endl;
        cin>>i;
        cin>>j;
        cin>>w;
        G->arc[i][j]=w;
        G->arc[j][i]=G->arc[i][j];
    }
}

//深度优先
void DFS(MGraph G,int i){
    int j;
    visited[i]=1;
    cout<<G.vexs[i];
    for(j=0;j<G.numVertexes;j++)
        if(G.arc[i][j]!=INFINITY&&!visited[j])
            DFS(G,j);
}
void DFSTraverse(MGraph G){
    int i;
    for(i=0;i<G.numVertexes;i++)
        visited[i]=0;
    for(i=0;i<G.numVertexes;i++)
        if(!visited[i])
            DFS(G,i);
}

//广度遍历
void BFSTraverse(MGraph G){
    int i,j;
    LinkQueue Q;
    for(i=0;i<G.numVertexes;i++)
        visited[i]=0;
    InitDL(Q);
    for(i=0;i<G.numVertexes;i++){
        if(!visited[i]){
            visited[i]=1;
            cout<<G.vexs[i];
            InDL(Q,i);
            while(!DLEmpty(Q)){
                OutDL(Q,i);
                for(j=0;j<G.numVertexes;j++){
                    if(G.arc[i][j]!=INFINITY&&!visited[j]){
                        visited[j]=1;
                        cout <<G.vexs[j];
                        OutDL(Q,j);
                    }
                }
            }
        }
    }
}

//普里姆算法
void MiniSpanTree_Prim(MGraph G){
    int min,i,j,k;
    int adjvex[MAXVEX];
    int lowcost[MAXVEX];
    lowcost[0]=0;
    adjvex[0]=0;
    for(i=1;i<G.numVertexes;i++){
        lowcost[i]=G.arc[0][i];
        adjvex[i]=0;
    }
    for(i=1;i<G.numVertexes;i++){
        min = INFINITY;

        j=1;
        k=0;
        while(j<G.numVertexes){
            if(lowcost[j]!=0&&lowcost[j]<min){
                min = lowcost[j];
                k=j;
            }
            j++;
        }
        cout<<"("<<adjvex[k]<<","<<k<<")";
        lowcost[k]=0;
        for(j=1;j<G.numVertexes;j++){
            if(lowcost[j]!=0&&G.arc[k][j]<lowcost[j]){
                lowcost[j]=G.arc[k][j];
                adjvex[j]=k;
            }
        }
    }
}

int main(){
    MGraph G;
    CreateMGraph(&G);
    cout << endl;
    cout << "深度遍历"<<endl;
    DFSTraverse(G);
    cout << endl;
    cout << "广度遍历"<<endl;
    BFSTraverse(G); 
    cout << endl;
    MiniSpanTree_Prim(G);
    return 0;
}

这些结构里也包含它们对应的遍历、插入、删除算法（有些还未经优化）….
当然这里还漏了很多基本结构类型，之后再补吧。
….