概述
线性表
顺序表
#include<iostream>
#include<stdlib.h>
using namespace std;
const int defaultSize = 10;
class SeqList {
protected:
int *data;
int maxSize;
int last;
void reSize(int newSize);
public:
SeqList(int sz = defaultSize);
SeqList(SeqList &l);
~SeqList();
int Size() const;
int Length() const;
int Search(int &x) const;
bool getData(int i,int &x) const;
void setData(int i,int &x);
bool Insert(int i,int &x);
bool Remove(int i,int &x);
bool isEmpty();
bool isFull();
void output();
};
bool SeqList::isFull()//判断线性表是否满
{
if(last+1==maxSize)
return true;
else
return false;
}
bool SeqList::isEmpty()//判断线性表是否空
{
if(last == -1)
{
return true;
}else
{
return false;
}
}
void SeqList::reSize(int newSize)//重新开辟空间
{
data = new int[newSize];
}
SeqList::SeqList(int sz)//构造线性表
{
if (sz>0) {
maxSize = sz;
last = -1;
data = new int[maxSize];
if (data == NULL)
exit(1);
}
}
SeqList::~SeqList()//删除线性表
{
delete []data;
}
int SeqList::Length() const//获取线性表的长度
{
return last+1;
}
bool SeqList::getData(int i,int &x) const//获取线性表的第i个元素
{
if(i-1>-1&&i-1<=last)
{
x = data[i-1];
return true;
}else
{
return false;
}
}
void SeqList::setData(int i,int &x)//更改线性表的第i个元素为x
{
if(i-1>0&&i-1<=last)
{
data[i-1] = x;
}
}
bool SeqList::Insert(int i,int &x)//在线性表的第i个位置插入x
{
if (last == maxSize-1)
return false;
if (i<0||i>last+1)
return false;
int j;
for (j=last;j>=i;j--)
data[j+1] = data[j];
data[i] = x;
last++;
return true;
}
bool SeqList::Remove(int i,int &x)//删除线性表第i个元素
{
i = i-1;
if(i>-1&&i<=last)
{
x = data[i];
int j;
for (j=i;j<=last-1;j++)
data[j] = data[j+1];
last--;
return true;
}else return false;
}
void SeqList::output()//输出线性表
{
int i;
for (i=0;i<=last;i++)
cout << data[i] << " ";
cout << endl;
}
int SeqList::Size() const//获得线性表的最大容量
{
return maxSize;
}
int SeqList::Search(int &x) const//获取数据x的下标
{
for(int i=0;i<=last;i++)
{
if(data[i]==x)
{
return i+1;
}
}
return 0;
}
int main()
{
SeqList l(8);
int n,i,x;
cin >> n;
for (i=0;i<n;i++) {
cin >> x;
if (l.isFull())
break;
l.Insert(i,x);
}
cout << l.Size() << " " << l.Length() << endl;
l.output();
l.Remove(3,n);
l.setData(2,n);
l.getData(1,n);
cout << n << endl;
l.output();
return 0;
}
/*
6
3 2 8 9 5 1
*/
单链表
#include <iostream>
using namespace std;
typedef struct Node
{
int data;
struct Node *next;
}node,*pnode;
int emptylist(pnode H)
{
if(H->next == NULL)
return 1;
else
return 0;
}
int getLength(node *H)//获取链表长度并返回
{
pnode p;
int i = 0;
p = H->next;
if(p!=NULL)
{
while(p!=NULL)
{
i++;
p = p->next;
}
return i;
}else
return 0;
}
void getdata(node *H,int k,int &x)//获取链表第k个数据;并赋给x
{
pnode p;
int i;
p = H ->next;
if(p!=NULL)
{
for(i=0;i<k;i++)
{
x = p->data;
p = p->next;
}
}
}
int searchdata(node *H,int &k,int x)//获取与x相等的第一个元素的下标并赋给k
{
pnode p;
int i=0;
p = H ->next;
if(p!=NULL)
{
while(p)
{
i++;
if(p->data == x)
{
return i;
}
p = p->next;
}
}
return 0;
}
void deletedata(node *H,int k,int &x)//删除链表第k个数据,并赋给x(要注意存在无法删除的情况)
{
pnode p,q;
int i;
p = H;
i = 0;
while(p->next&&i<k-1)
{
p = p->next;
i++;
}
if(p->next&&i<=k-1)
{
q = p->next;
p->next = q->next;
x = q->data;
free(q);
}
}
void insertdata(node *H,int k,int x)//在链表的第k个位置上插入x
{
pnode p,q,l;
p = H->next;
q = H;
l = (node*)malloc(sizeof(node));
l->data = x;
for(int i=0;i<k-1;i++)
{
q = p;
p = p->next;
}
q->next = l;
l->next = p;
}
void output(pnode H)//输出链表
{
pnode p;
p = H->next;
while(p!=NULL)
{
printf("%d",p->data);
p = p->next;
}
cout<<endl;
}
void destroyList(pnode H)//销毁链表
{
pnode p,q;
p = H->next;
while(p)
{
q = p;
p = p->next;
free(q);
}
}
void deletall(pnode H)//清空链表(就加了个H->next = NULL)
{
pnode p,q;
p = H->next;
while(p)
{
q = p;
p = p->next;
free(q);
}
H->next = NULL;
}
pnode combine(pnode H1,pnode H2)//链表合并(有重复元素)
{
pnode p,q,l,H3;
l = H3 = H1;
p = H1->next;
q = H2->next;
while(p&&q)
{
if(p->data<=q->data)
{
l->next = p;
l = p;
p = p->next;
}else
{
l->next = q;
l = q;
q = q->next;
}
}
if(p==NULL&&q!=NULL)
{
l->next = q;
}else
{
l->next =p;
}
return H3;
}
pnode combine2(pnode H1,pnode H2)//链表合并(无重复元素)
{
pnode p,q,l,H3;
l = H3 = H1;
p = H1->next;
q = H2->next;
while(p&&q)
{
if(p->data<q->data)
{
l->next = p;
l = p;
p = p->next;
}else if(p->data>q->data)
{
l->next = q;
l = q;
q = q->next;
}else
{
q = q->next;
}
}
if(p==NULL&&q!=NULL)
{
l->next = q;
}else
{
l->next =p;
}
return H3;
}
int main()
{
pnode H1,H2;
H1 = (pnode)malloc(sizeof(node));
H1->next = NULL;
H2 = (pnode)malloc(sizeof(node));
H2->next = NULL;
int n,x;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>x;
insertdata(H1,i,x);
}
for(int i=1;i<=n;i++)
{
cin>>x;
insertdata(H2,i,2*x);
}
//output(H);
/*
insertdata(H,2,2);
output(H);
deletedata(H,4,x);
cout<<x<<endl;
output(H);
cout<<getLength(H)<<endl;
getdata(H,4,x);
cout<<x<<endl;
deletall(H);
printf("%dn",emptylist(H));
*/
//searchdata(H,n,5);
//cout<<n<<endl;
//deletedata(H,4,x);
//output(H);
output(H1);
output(H2);
//H1 = combine(H1,H2);
H1 = combine2(H1,H2);
output(H1);
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/
循环链表
Z哥的代码
双向链表
Z哥的代码
双向循环链表
在这里插入代码片
栈
顺序栈
#include <iostream>
using namespace std;
int MAXSIZE = 100;
typedef struct
{
int *base;
int *top;
int stacksize;
}Node;
void initstack(Node &S)//顺序栈的初始化
{
S.base = new int[MAXSIZE];
S.top = S.base;
S.stacksize = MAXSIZE;
}
bool stackempty(Node S)//判断栈空
{
if(S.top == S.base)
return true;
else
return false;
}
int stacklength(Node S)//求栈的长度
{
return S.top - S.base;
}
void clearstack(Node &S)//清空栈
{
if(S.base)
S.top = S.base;
}
void destroystack(Node &S)//销毁栈
{
if(S.base)
{
free(S.base);
S.stacksize = 0;
S.base = S.top = NULL;
}
}
void Push(Node &S,int x)//顺序入栈
{
if(S.top - S.base < S.stacksize)
*S.top++ = x;
}
void Pop(Node &S,int &x)//顺序出栈
{
if(S.top!=S.base)
{
x = *--S.top;
}
}
void GetTop(Node S,int &x)//取栈顶元素
{
if(S.base!=S.top)
{
x = *(S.top--);
}
}
int main()
{
Node S;
int x;
initstack(S);
for(int i=0;i<5;i++)
Push(S,i);
for(int i=0;i<5;i++)
{
Pop(S,x);
cout<<x<<' ';
}
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/
链栈
#include <iostream>
using namespace std;
typedef struct StackNode
{
int data;
struct StackNode *next;
}node,*lnode;
void initstack(lnode &S)//栈的初始化
{
S = NULL;
}
bool stackempty(lnode S)//判断栈空
{
if(S == NULL)
return true;
else
return false;
}
void Push(lnode &S,int x)//顺序入栈
{
lnode p;
p = (lnode)malloc(sizeof(node));
p->data = x;
p->next = S;
S = p;
}
void Pop(lnode &S,int &x)//顺序出栈
{
if(S!=NULL)
{
lnode p;
p = S;
x = S->data;
S = S->next;
free(p);
}
}
void GetTop(lnode S,int &x)//取栈顶元素
{
if(S!=NULL)
{
x = S->data;
}
}
int main()
{
lnode S;
int x;
initstack(S);
for(int i=0;i<5;i++)
Push(S,i);
for(int i=0;i<5;i++)
{
Pop(S,x);
cout<<x<<' ';
}
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/
双栈
在这里插入代码片
队列
顺序队列
在这里插入代码片
循环队列
用循环队列的目的是防止发生假溢出的情况,同时最大限度的利用储存空间,其队满和队空的情况要分两种判断情况:队空时front==rear,队满时由于rear指向的空间为空,实际队满其实只使用了MAX-1的空间,所以要用(rear+1)%MAX == front来判断。
#include <iostream>
using namespace std;
#define MAXQSIZE 10
typedef struct
{
int *base;
int front1;
int rear;
}queueq;
void initqueue(queueq &Q)//循环队列初始化
{
Q.base = new int[MAXQSIZE];
Q.front1 = Q.rear = 0;
}
int queuelength(queueq Q)//求循环队列长度
{
return (Q.rear - Q.front1 + MAXQSIZE)%MAXQSIZE;
}
void enqueue(queueq &Q,int x)//循环队列入队
{
if((Q.rear+1)%MAXQSIZE!=Q.front1)
{
Q.base[Q.rear]=x;
Q.rear = (Q.rear+1)%MAXQSIZE;
}
}
void dequeue(queueq &Q,int &x)//循环队列出队
{
if(Q.front1!=Q.rear)
{
x = Q.base[Q.front1];
Q.front1 = (Q.front1+1)%MAXQSIZE;
}
}
bool queueempty(queueq &Q)//判断队空
{
return (Q.front1 == Q.rear);
}
bool queuefull(queueq &Q)//判断队满
{
return ((Q.rear+1)%MAXQSIZE == Q.front1);
}
int main()
{
queueq Q;
initqueue(Q);
for(int i=0;i<9;i++)
{
enqueue(Q,i);
}
cout<<queuefull<<endl;
int x;
for(int i=0;i<9;i++)
{
dequeue(Q,x);
cout<<x<<' ';
}
cout<<endl;
cout<<queueempty(Q);
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/
链队列
有些拿不准(‧_‧?)
#include <iostream>
using namespace std;
typedef struct Qnode
{
int data;
struct Qnode *next;
}qnode;
typedef struct
{
qnode *front1;
qnode *rear;
}Lqueue;
void initqueue(Lqueue &Q)//链队列初始化
{
Q.front1 = Q.rear = (qnode *)malloc(sizeof(qnode));
Q.front1->next = NULL;
}
void destroyqueue(Lqueue &Q)//销毁链队列
{
while(Q.front1)
{
Q.rear = Q.front1->next;
free(Q.front1);
Q.front1 = Q.rear;
}
}
bool queueempty(Lqueue Q)//判断链队列是否为空
{
return (Q.front1 == Q.rear);
}
void getqueue(Lqueue Q,int &x)//取队头元素
{
if(Q.front1!=Q.rear)
x = Q.front1->next->data;
}
void enqueue(Lqueue &Q,int x)//链队入队
{
qnode *p;
p = (qnode *)malloc(sizeof(qnode));
p->data = x;
p->next = Q.rear->next;
Q.rear->next = p;
Q.rear = p;
}
void dequeue(Lqueue &Q,int &x)//链队出队
{
if(Q.front1!=Q.rear)
{
qnode *p;
p = Q.front1;
Q.front1 = Q.front1->next;
x = Q.front1->data;
free(p);
}
}
int main()
{
Lqueue Q;
initqueue(Q);
for(int i=0;i<5;i++)
{
enqueue(Q,i);
}
int x;
for(int i=0;i<5;i++)
{
dequeue(Q,x);
cout<<x<<' ';
}
return 0;
}
/*
5
1 2 3 4 5
1 2 3 4 5
*/
树
二叉树
#include <iostream>
#include <queue>
using namespace std;
typedef struct tree
{
char data;
struct tree *lchild,*rchild;
int LTag,RTag;
}trenode,*ptrenode;
ptrenode pre;
void createtree(ptrenode &T)//利用先序遍历建立二叉树
{
char ch;
cin>>ch;
if(ch=='#')
{
T = NULL;
}else
{
T = new tree;
T->data
= ch;
createtree(T->lchild);
createtree(T->rchild);
}
}
void inoutput(ptrenode T)//利用中序遍历输出二叉树
{
if(T!=NULL)
{
inoutput(T->lchild);
cout<<T->data;
inoutput(T->rchild);
}
}
void noutput(ptrenode T)//层序输出Big陈
{
ptrenode p;
queue<ptrenode> Q;
if(T)
{
Q.push(T);
while (!Q.empty())
{
p=Q.front();
cout<<p->data;
Q.pop();
if(p->lchild)
Q.push(p->lchild);
if(p->rchild)
Q.push(p->rchild);
}
}
}
void trecopy(ptrenode &T1,ptrenode &T2)//树的复制
{
if(T1 == NULL)
{
T2 = NULL;
return;
}else
{
T2 = new tree;
T2->data
= T1->data;
trecopy(T1->lchild,T2->lchild);
trecopy(T1->rchild,T2->rchild);
}
}
int Countnode(ptrenode T)//计算二叉树结点总数
{
if(T==NULL)
return 0;
else
return Countnode(T->lchild)+Countnode(T->rchild)+1;
}
int Countlead(ptrenode T)//计算二叉树叶子总数
{
if(T == NULL)
return 0;
if(T->lchild == NULL&&T->rchild == NULL)
return 1;
else
return Countlead(T->lchild)+Countlead(T->rchild);
}
int Countdepth(ptrenode T)//求二叉树的深度
{
if(T==NULL)
return 0;
else
return max(Countdepth(T->lchild)+1,Countdepth(T->rchild)+1);
}
int Num1(ptrenode &T){
//统计度为1的节点的个数
if(T == NULL)
return 0;
if(T->lchild == NULL&&T->rchild != NULL)
{
return Num1(T->rchild)+1;
}
else if(T->lchild != NULL&&T->rchild == NULL)
{
return Num1(T->lchild)+1;
}
else
{
return Num1(T->rchild)+Num1(T->lchild);
}
}
void inthreading(ptrenode &T)//线索二叉树的建立(有问题)
{
if(T)
{
inthreading(T->lchild);
if(!T->lchild)
{
T->LTag=1;
T->lchild = pre;
}else
T->LTag=0;
if(!pre->rchild)
{
pre->RTag=1;
pre->rchild = T;
}else
pre->RTag = 0;
pre=T;
inthreading(T->rchild);
}
}
int main()
{
//pre->RTag = 1;
//pre->rchild = NULL;
ptrenode T,Tnew;
createtree(T);
inoutput(T);
cout<<endl;
trecopy(T,Tnew);
inoutput(Tnew);
cout<<endl;
cout<<Countnode(T)<<endl;
cout<<Countlead(T)<<endl;
cout<<Countdepth(T)<<endl;
/*
createtree(T);
inthreading(T);
inoutput(T);
*/
return 0;
}
/*
ABC##DE#G##F###
*/
线索二叉树
来自Big陈的代码
#include <iostream>
#include<cstdio>
using namespace std;
typedef struct BThrNode{
char data;
struct BThrNode *lchild, *rchild;
int ltag, rtag;
}BThrNode, *BThrTree;
BThrTree T,p;
void createBTree(BThrTree &T)//前序遍历建立二叉树
{
char ch;
cin>>ch;
if(ch=='@') T=NULL;
else
{
T=new BThrNode;
T->data=ch;
createBTree(T->lchild);
createBTree(T->rchild);
}
}
BThrTree pre=NULL;//全局变量
void InThread(BThrTree p)//中序遍历线索化二叉树
{
if(p!=NULL)
{
InThread(p->lchild);
if(p->lchild==NULL)
{
p->ltag=1;
p->lchild=pre;
}else
p->ltag=0;
if(p->rchild==NULL)
{
p->rtag=1;
pre->rchild=p;
}
else
pre->rtag=0;
pre=p;
InThread(p->rchild);
}
}
void TraveBTree(BThrTree &T)
{
if(T)
{
TraveBTree(T->lchild);
cout<<T->data;
TraveBTree(T->rchild);
}
}
int main()
{
createBTree(T);
InThread(p);
TraveBTree(T);
return 0;
}
图
邻接矩阵(曾哥的代码)
#include <iostream>
using namespace std;
typedef struct linjiejuzhen{
char a[100];
int b[100][100];
int dian,bian;
}linjie;
int find1(linjie t,char x)
{
int i;
for(i=0;i<t.dian;i++)
{
if(t.a[i]==x)
return i;
}
return -1;
}
int createju(linjie &t)
{
scanf("%d %d",&t.dian,&t.bian);
int i,j,k;
char m,n;
for(i=0;i<t.dian;i++)
{
scanf(" %c",&t.a[i]);
}
for(i=0;i<t.dian;i++)
{
for(j=0;j<t.dian;j++)
t.b[i][j]=0;
}
for(i=0;i<t.bian;i++)
{
scanf(" %c %c",&m,&n);
j=find1(t,m);
k=find1(t,n);
t.b[k][j]=1;
t.b[j][k]=1;
}
for(i=0;i<t.dian;i++)
{
for(j=0;j<t.dian;j++)
printf("%d ",t.b[i][j]);
printf("n");
}
}
int main()
{
linjie t;
createju(t);
return 0;
}
邻接表
#include<iostream>
#include<cstdio>
#include<queue>
#define MAX_NUM 20
using namespace std;
int w;
int mark[100];
int vis[100];
typedef struct EdgeNode//边的结点
{
int edge;
int weight;
struct EdgeNode *nextedge;
}EdgeNode;
typedef struct Vnode//点的节点
{
int data;
EdgeNode *pp;
}Vnode;
typedef struct//图的定义
{
Vnode VList[MAX_NUM];
int n,e;//点数和边数
}Graph;
void createDirGraph(Graph &G)//有向图的构建
{
int x,y;
EdgeNode *q;
cin>>G.n>>G.e;
for(int i=1;i<=G.n;i++)//输入结点信息并初始化节点
{
cin>>G.VList[i].data;
G.VList[i].pp=NULL;
}
for(int i=1;i<=G.e;i++)//输入边的信息
{
cin>>x>>y;
q = new EdgeNode;
q->edge = y;
q->nextedge = G.VList[x].pp;
G.VList[x].pp = q;
}
}
void createUndirGraph(Graph &G)//无向图的构建
{
int x,y;
EdgeNode *q,*p;
cin>>G.n>>G.e;
for(int i=1;i<=G.n;i++)//输入结点信息并初始化节点
{
cin>>G.VList[i].data;
G.VList[i].pp=NULL;
}
for(int i=1;i<=G.e;i++)//输入边的信息
{
cin>>x>>y;
q = new EdgeNode;
p = new EdgeNode;
q->edge = y;
p->edge = x;
q->nextedge = G.VList[x].pp;
p->nextedge = G.VList[y].pp;
G.VList[x].pp = q;
G.VList[y].pp = p;
}
}
void showGraph(Graph G)
{
for(int i=1;i<=G.n;i++)
{
cout<<G.VList[i].data<<':';
EdgeNode *p = G.VList[i].pp;
while(p)
{
cout<<p->edge<<' ';
p = p->nextedge;
}
cout<<endl;
}
}
void DFS(Graph &G,int v)//深度优先遍历
{
cout<<v<<" ";
mark[v]=1;
EdgeNode *p=G.VList[v].pp;
while(p!=NULL)
{
w=p->edge;
if(!mark[w])
DFS(G, w);
p=p->nextedge;
}
}
void BFS(Graph &G,int v)//广度优先遍历
{
int x;
queue<int>Q;
Q.push(G.VList[v].data);
while(!Q.empty())
{
x = Q.front();
Q.pop();
if(!vis[x])
{
cout<<'v'<<x<<' ';
vis[x] = 1;
}
EdgeNode *p = G.VList[x].pp;
while(p)
{
if(!vis[p->edge])
{
Q.push(p->edge);
}
p=p->nextedge;
}
}
}
void getdu(Graph &G)//求入度,出度,度
{
int a[100][3],cnt;
for(int i=1;i<=G.n;i++)
a[i][1] = 0;
for(int i=1;i<=G.n;i++)
{
cnt = 0;
a[i][0] = G.VList[i].data;
EdgeNode *p = G.VList[i].pp;
while(p)
{
cnt++;
a[p->edge][1]++;
p = p->nextedge;
}
a[i][2] = cnt;
}
for(int i=1;i<=G.n;i++)
{
cout<<a[i][0]<<':'<<a[i][1]<<' '<<a[i][2]<<' '<<a[i][1]+a[i][2]<<endl;
}
}
int main()
{
Graph G;
createUndirGraph(G);
BFS(G,1);
return 0;
}
/*
12 16
1 2 3 4 5 6 7 8 9 10 11 12
1 4
1 2
1 3
1 12
4 5
2 3
3 5
3 7
5 7
3 8
9 12
9 10
10 12
9 11
11 6
6 8
*/
最后
以上就是愉快板凳为你收集整理的数据结构学习线性表栈队列树图的全部内容,希望文章能够帮你解决数据结构学习线性表栈队列树图所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复