1. 首页
  2. 文章中心
  3. 数据结构实验

数据结构实验一

50 阅读 0 评论
我是靠谱客的博主 调皮饼干，最近开发中收集的这篇文章主要介绍数据结构实验一，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

实验内容：

（一）单链表的定义及基本操作

  1. 用带表头的链表存放输入的数据，每读入一个数，按升序顺序插入到链表中，链表中允许两个结点有相同值。链表的头结点存放链表后面的结点个数，初始化时就生成头结点（初值为0）。
  2. 在上述带表头的链表中删除第i个结点或删除数值为item的结点。

（3）链表翻转是把数据逆序（变成降序），注意，头结点不动。翻转后要再翻转一次，恢复升序后才能插入新元素，否则会出错。

（4）设A与B分别为两个带有头结点的有序循环链表（所谓有序是指链接点按数据域值大小链接，本题不妨设按数据域值从小到大排列），list1和list2分别为指向两个链表的指针。请写出并在计算机上实现将这两个链表合并为一个带头结点的有序循环链表的算法。

（二）链式堆栈的定义及基本操作

（5）先定义堆栈的几个基本操作，再设计一主函数利用堆栈的操作完成以下功能：假设一个算术表达式中可以包含三种括号：()[]{}，且这三种括号可以按任意次序嵌套使用（如：...[...{...}...[...]...]...(...)）。编写判别给定表达式中所含括号是否正确配对出现的算法，已知表达式已存入数据元素为字符的单链表中。

（三）链式队列的定义及基本操作

（6）先定义队列的几个基本操作，再设计一主函数利用队列的操作完成以下功能：键盘输入的字符可以临时存入键盘的缓冲区中。为了充分利用缓冲区的空间，往往将缓冲区设计成链式循环队列的结构，并为循环队列结构的缓冲区设置一个队首指针和一个队尾指针。每输入一个字符到缓冲区中，就将尾指针后移，链入缓冲区的循环队列之中；每输出一个字符号，就将队头指针前移，将它从缓冲队列中删除。假设有两个进程同时存在于一个应用程序中，第一个进程连续在屏幕上显示字符“X”，第二个进程不断检查键盘上是否有输入，若有则读入用户键入的字符，将其保存到键盘缓冲区中。

#include <iostream>
#include <conio.h>
using namespace std;
#define MAXQSIZE 100
typedef struct QNode
{
    char data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=new QNode;
    Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,char e)
{
    QueuePtr p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
}
bool DeQueue(LinkQueue &Q,char &e)
{
    if(Q.front==Q.rear) return 0;
    QueuePtr p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    delete p;
    return 1;
}
int main()
{
    LinkQueue Q;
    InitQueue(Q);
    while(1)
    {
        cout<<'X';
        if(kbhit())
        {
            char ch=getch();
            if(ch=='#') break;
            EnQueue(Q,ch);
        }
    }
    char e;
    while(DeQueue(Q,e))
    {
        cout<<e;
    }
	return 0;
}

#include<iostream>
using namespace std;

struct node
{
	int val;
	node *nex;
	node *pre;
	node()
	{
		val=0;
		nex=NULL;
		pre=NULL;
	}
};

void addnode(node* &T,int val)
{
	node *tmp=new node;
	tmp->val=val;
	if(T->nex==NULL)
	{
		T->nex=tmp;
		return ;
	}
	node *p=T;
	node *s=T->nex;
	while(s!=NULL&&s->val<val)
	{
	    p=s;
		s=s->nex;
	}
	if(s==NULL)
	{
		p->nex=tmp;
	}
	else
	{
		p->nex=tmp;
		tmp->nex=s;
	}
	T->val++;
}

void del_id_node(node* &T,int id)
{
	if(!T->nex)
	{
		cout<<"Line is NULL"<<endl;
		return ;
	}
	if(T->val<id)
	{
		cout<<"no "<<id<<" numn";
		return ;
	}

	node *p=T;
	node *s=T->nex;
	int cnt=0;
	while(1)
	{
		cnt++;
		if(cnt==id)
		{
			cout<<"The "<<id<<" node is delete, its val is ";
			cout<<s->val<<endl;
			p->nex=s->nex;
			delete s;
			break;
		}
		p=s;
		s=s->nex;
	}
	cout<<"The new Link is ";
	node *ne=T->nex;
	while(ne!=NULL)
	{
		cout<<ne->val<<" ";
		ne=ne->nex;
	}
	cout<<endl;
}

void del_val_node(node* &T,int val)
{
    node *p=T;
	node *s=T->nex;

	while(s!=NULL)
    {
        if(s->val==val)
        {
            node *t=s;
            p->nex=s->nex;
            s=s->nex;
            delete t;
        }
        else
        {
            p=s;
            s=s->nex;
        }
    }
	cout<<"The "<<val<<" number is delete"<<endl;
    cout<<"The new Link is ";
	node *ne=T->nex;
	while(ne!=NULL)
	{
		cout<<ne->val<<" ";
		ne=ne->nex;
	}
	cout<<endl;
}

void Reverse(node * &T)
{
    if(!T->val)
    {
        return ;
    }
    node *p=T;
    node *s=T->nex;
    while(s->nex!=NULL)
    {
        s->pre=p;
        p=s;
        s=s->nex;
    }

    T->nex=s;
    while(p!=T)
    {
        //cout<<p->val<<" "<<s->val<<endl;
        s->nex=p;
        s=p;
        p=p->pre;
    }
    s->nex=NULL;
    p=NULL;
    //cout<<p->val<<endl;
    cout<<"The link was reverse , the new Link is ";
	node *ne=T->nex;
	while(ne!=NULL)
	{
		cout<<ne->val<<" ";
		ne=ne->nex;
	}
	cout<<endl;
}

void Join(node* &T3,node* &T2,node* &T1)
{
    node *p=T3;
    node *p1=T1->nex;
    node *p2=T2->nex;
    //cout<<p1->val<<" "<<p2->val<<endl;

    while(p1!=T1&&p2!=T2)
    {
        int val1=0;
        int val2=0;
        val1=p1->val;
        val2=p2->val;
        //cout<<val1<<" "<<val2<<endl;
        if(val1>val2)
        {
            node *t=new node;
            t->val=val2;
            p->nex=t;
            p=p->nex;
            p2=p2->nex;
        }
        else
        {
            node *t=new node;
            t->val=val1;
            p->nex=t;
            p=p->nex;
            p1=p1->nex;
        }
    }
    if(p1==T1)
    {
        while(p2!=T2)
        {
            node *t=new node;
            t->val=p2->val;
            p2=p2->nex;
            p->nex=t;
            p=p->nex;
        }
    }
    else
    {
        while(p1!=T1)
        {
            node *t=new node;
            t->val=p1->val;
            p1=p1->nex;
            p->nex=t;
            p=p->nex;
        }
    }

    cout<<"T1 ans T2 joined is ";
	node *ne=T3->nex;
	while(ne!=NULL)
    {
        cout<<ne->val<<" ";
        ne=ne->nex;
    }
    cout<<endl;
}

node* Show(node * &T,int id)
{
    node *p=T;
	node *ne=T->nex;
	cout<<"The Link"<<id<<" is ";
	while(ne!=NULL)
	{
		cout<<ne->val<<" ";
		p=ne;
		ne=ne->nex;
	}
	cout<<endl;
	return p;
}

int n;
int main()
{
    //(1)
    node *T=new node;
    cin>>n;
    while(n--)
    {
        int a;
        cin>>a;
        addnode(T,a);
    }
    Show(T,1);

    //(2)
    del_id_node(T,3);
    del_val_node(T,12);

    //(3)
    Reverse(T);

    //(4)循环链表合并
	node *T1=new node;
	cin>>n;
	while(n--)
	{
		int a;
		cin>>a;
		addnode(T1,a);
	}
	node *p=Show(T1,1);
	p->nex=T1;//指向头指针

	node *T2=new node;
	cin>>n;
        while(n--)
	{
		int a;
		cin>>a;
		addnode(T2,a);
	}
	p=Show(T2,2);
	p->nex=T2;

	node *T3=new node;

	Join(T3,T2,T1);

	return 0;
}

 

#include <iostream>
#include <cstring>
using namespace std;

#define MAXSIZE 100
#define OVERFLOW 0
#define OK 1
#define ERROR 0
#define NO 0


typedef struct StackNode
{
	char data;
	struct StackNode *next;
}StackNode,*LinkStack;

InitStack(LinkStack &S)
{
	S=NULL;
	return OK;
};

bool Push(LinkStack &S ,char e)
{
	LinkStack p=new StackNode;
	p->data=e;
	p->next=S;
	S=p;
	return OK;
}

bool Pop(LinkStack &S,char &e)
{
	if(S==NULL) return ERROR;
	e=S->data;
	LinkStack p=S;
	S=S->next;
	delete p;
	return OK;
}

char GetTop(LinkStack S)
{
	if(S!=NULL) 
		return S->data;
	else return ERROR;
}

bool Check(LinkStack S,string str)
{
	int len=str.length();
	//cout<<len<<endl;
	for(int i=0;i<len;i++)
	{
		if(str[i]!='('&&str[i]!=')'&&str[i]!='['&&str[i]!=']'&&str[i]!='{'&&str[i]!='}') continue;
		
		
		if(S==NULL)
			Push(S,str[i]);
		else 
		{
			//cout<<GetTop(S)<<" ";
			if(GetTop(S)=='('&&str[i]==')')
			{
				char e;
				Pop(S,e);
			}
			else if(GetTop(S)=='{'&&str[i]=='}')
			{
				char e;
				Pop(S,e);
			}	
			else if(GetTop(S)=='['&&str[i]==']')
			{
				char e;
				Pop(S,e);
			}
			else 
			{
				Push(S,str[i]);
			}
		}
	}
	if(!S)
		return OK;
	else return NO;
}

int main()
{
	string str;
	LinkStack S;
	//freopen("input.txt","r",stdin);
	while(cin>>str)
	{
		cout<<str<<endl;
		InitStack(S);
		bool f=Check(S,str);
		if(f) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	} 
	return 0;
}
typedef struct QNode
{
    char data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)
{
    Q.front=Q.rear=new QNode;
    Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,char e)
{
    QueuePtr p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
}
bool DeQueue(LinkQueue &Q,char &e)
{
    if(Q.front==Q.rear) return 0;
    QueuePtr p=Q.front->next;
    e=p->data;
    Q.front->next=p->next;
    if(Q.rear==p) Q.rear=Q.front;
    delete p;
    return 1;
}
int main()
{
    LinkQueue Q;
    InitQueue(Q);
    while(1)
    {
        cout<<'X';
        if(kbhit())
        {
            char ch=getch();
            if(ch=='#') break;
            EnQueue(Q,ch);
        }
    }
    char e;
    while(DeQueue(Q,e))
    {
        cout<<e;
    }
	return 0;
}

 

 

最后

以上就是调皮饼干为你收集整理的数据结构实验一的全部内容，希望文章能够帮你解决数据结构实验一所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(33)

相关文章

数据结构学习之二叉树（JAVA）树二叉树
数据结构学习之二叉树（JAVA）树二叉树
链表总结(力扣：合并两个有序链表)
链表总结(力扣：合并两个有序链表)
八数码问题实验报告c语言,八数码问题
八数码问题实验报告c语言,八数码问题
数据结构 ||大根堆的实现
数据结构 ||大根堆的实现
数据结构实验一
数据结构实验一
PTA：两个有序链表的合并解题报告
PTA：两个有序链表的合并解题报告
二叉排序树的插入，删除和遍历
二叉排序树的插入，删除和遍历
LeetCode--合并有序链表总结
LeetCode--合并有序链表总结

评论列表共有 0 条评论

立即
投稿
返回
顶部