数据结构

2024-03-22 21:44:40

补充第三章

循环链表

数据结构
数据结构
合并两个链表，就是把它们的尾指针改动一下即可
我们可以在创立链表的时候返回一个尾指针

LinkList CreateListTail( LinkList *L, int n )
{
	*L = (LinkList)malloc(sizeof(Node));
   
	LinkList rear = *L,s;
	
	srand(time(0));
 
	for(int i=0;i<n;i++)
	{
	    s = (LinkList)malloc(sizeof(Node));
		s->data = rand()%100+1;
		rear->next = s;
		rear = s;//更新rear的位置到尾结点
	}
	rear->next = *L;
 
	return rear;
}

然后修改一下输出：

void OutList_Tail(LinkList rear){
	LinkList p= rear->next->next;
	while(p != rear->next){
		printf("%d ",p->data);
		p = p->next;
	}
	printf("\n");
	return ;
}

再就是合并两个链表了！

int hebing(LinkList rearA,LinkList rearB){
	if(!ListEmpty(rearA->next)&&!ListEmpty(rearB->next)){
		LinkList p;
		p=rearA->next;
		rearA->next=rearB->next;
		rearB->next=p->next;
		free(p);
		printf("\n合并成功！");
	}else{
		printf("\n合并失败!");
	}
}

这里我在创建两个链表的时候用的随机数，但是用随机数创建的两个链表是一样的，于是我在网上搜到一个小技巧可以不判断之前的数字就生成一个完全和之前不重复的链表

	for(int i=0;i<200000000;i++)
	{
	
	}

就是加个这个！然后就结束了
运行结果：
数据结构

双向链表

数据结构

typedef struct DulNode
{
		ElemType data;
		struct DuLNode *prior;    	/*直接前驱指针*/
		struct DuLNode *next;		/*直接后继指针*/
} DulNode, *DuLinkList;

p->next->prior = p = p->prior->next

插入操作：
数据结构

s - >prior = p;   			/*把p赋值给s的前驱，如图中①*/
s -> next = p -> next;		/*把p->next赋值给s的后继，如图中②*/
p -> next -> prior = s;		/*把s赋值给p->next的前驱，如图中③*/
p -> next = s;				/*把s赋值给p的后继，如图中④*/

删除p:
数据结构

p->prior->next=p->next;   	/*把p->next赋值给p->prior的后继，如图中①*/
p->next->prior=p->prior;	/*把p->prior赋值给p->next的前驱，如图中②*/
free（p）;					/*释放结点*/

栈与队列

数据结构

栈（stack）

限定为只能表尾端进行插入和删除操作的线性表
数据结构
这里的表尾是指栈顶，即为top
数据结构
数据结构
数据结构
数据结构
弹夹的子弹压入和弹出，我们一般叫做进栈和出栈。
我们之前在对c++的表层学习时，学过一点点对栈的使用

#include<iostream>
#include<stack>
using namespace std;
stack<int>s;
int main(){
	int n;
	cin>>n;
	while(n--){
		int op,num;
		cin>>op;
		if(op==1){
			cin>>num;
			s.push(num);//入栈
		}
		if(op==2)cout<<"top: "<<s.top()<<endl;//栈顶
		if(op==3)s.pop();//删除栈顶
		if(op==4)cout<<"size: "<<s.size()<<endl;
		if(op==5)cout<<"empty:"<<(s.empty()?"true":"false")<<endl;
	}
	return 0;
}

栈的顺序结构

数据结构
我们默认空栈时top=-1
进栈：

int Push(SqStack *S,SElemType e){
	if(S->top==MAXSIZE-1){//若栈满，则返回 
		return 0;
	}
	S->top++;//栈顶指针增加 
	S->data[S->top]=e;//把数据存入栈顶空间 
	//S->data[++S->top]=e;(把上面两句合并)
	return 1;
}

出栈：

int Pop(SqStack *S,SElemType *e){
	if(S->top==-1){
		return 0;
	}
	*e=S->data[S->top];//把要删除的元素赋值给e 
	S->top--;//栈顶指针减一 
	return 1;
}

获取栈顶：

int GetTop(SqStack S,SElemType *e){
	if(S.top==-1){
		return 0;
	}else{
		*e=S.data[S.top];
		
	}return 1;
}

两栈共享空间

关键：从数组两端向中间靠拢
只是针对两个具有相同数据类型的栈的一个设计上的技巧
当top1=-1时，栈1为空，当top2=n时，栈2为空。
若top1=n-1,栈1满了；
若top2=0时，栈2满了；
栈满的条件：top1+1==top2;
进栈：

int Push(SqDoubleStack *S,SElemType e,int stackNumber){
	if(S->top1+1==S->top2){//栈已经满了，不能再加元素了 
		return 0;
	}
	if(stackNumber==1){
		S->data[++S->top1]=e;//若是栈1则先top1+1后给数组元素赋值
	}else if(stackNumber==2){
		S->data[++S->top2]=e;//若是栈2则先top2-1后给数组元素赋值
	}
	return 0;
}

出栈：

int Pop(SqDoubleStack *S,SElemType *e,int stackNumber){ 
        if (stackNumber==1) {
                if (S->top1==-1) 
                        return 0; /* 说明栈1已经是空栈，溢出 */
                *e=S->data[S->top1--]; /* 将栈1的栈顶元素出栈 */
        }
        else if (stackNumber==2){ 
                if (S->top2==MAXSIZE) 
                        return 0; /* 说明栈2已经是空栈，溢出 */
                *e=S->data[S->top2++]; /* 将栈2的栈顶元素出栈 */
        }
        return 1;
}

栈的链式结构

简称“链栈”
通常来说，链栈是不需要头结点的
数据结构

链栈结构：

typedef struct StackNode
{
        SElemType data;
        struct StackNode *next;
}StackNode,*LinkStackPtr;


typedef struct
{
        LinkStackPtr top;
        int count;
}LinkStack;

进栈：

Status Push(LinkStack *S,SElemType e)
{
        LinkStackPtr s=(LinkStackPtr)malloc(sizeof(StackNode)); 
        s->data=e; 
        s->next=S->top;	/* 把当前的栈顶元素赋值给新结点的直接后继，见图中① */
        S->top=s;         /* 将新的结点s赋值给栈顶指针，见图中② */
        S->count++;
        return OK;
}

数据结构
出栈：

Status Pop(LinkStack *S,SElemType *e)
{ 
        LinkStackPtr p;
        if(StackEmpty(*S))
                return ERROR;
        *e=S->top->data;
        p=S->top;					/* 将栈顶结点赋值给p，见图中③ */
        S->top=S->top->next;    /* 使得栈顶指针下移一位，指向后一结点，见图中④ */
        free(p);                    /* 释放结点p */        
        S->count--;
        return OK;
}

数据结构

栈的应用——四则运算求值

数据结构
后缀表达法

数据结构
数据结构

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int number[101];//储存运算数
char symbol[101];//储存运算符
char s[101];//储存字符串 
int i=0;//用来遍历字符串 
int p=1;//表达栈顶下标,初始化1是为了防止下标越界
void push()//入栈 
{
	symbol[++p]=s[i];
	//先增加p值然后将运算符置于栈顶.

}
void pop()//出栈,并顺带完成相应的运算 
{//将number[p](栈顶)与number[p-1]进行运算,并将结果储存在number[p-1]; 
	p--;//出栈后,栈顶下标-1;
	//number[p]是新的栈顶元素
	if(symbol[p+1]=='+')//已经弹出的运算符
	{
		number[p]+=number[p+1];//运算结果
	}else if(symbol[p+1]=='-')
	{
		number[p]-=number[p+1];
	}else if(symbol[p+1]=='*')
	{
		number[p]*=number[p+1];
	}else if(symbol[p+1]=='/')
	{
		number[p]/=number[p+1];
	}
}
int cmp(char a)//返回运算符优先级
{
	if(a=='*'||a=='/')
	{
		return 2;
	}else if(a=='+'||a=='-')
	{
		return 1;
	}else if(a=='(')
	{
		return 0;
	}
	return 0;
} 
int can()
{
	if(cmp(s[i])<=cmp(symbol[p]))//当栈顶运算符优先级大于等于比较运算符时进行出栈 
	{
		return 1; 
	}
	return 0;
}
int main()
{
	gets(s);
	s[strlen(s)]=')';
	symbol[p]='(';//symbol[1]是括号,防止对空栈操作,同时对应第一个数
	while(i<strlen(s)){
		while(s[i]=='(')//优先录入左括号 
		{
			push();
			i++;
		}
		int sum=0;
		while(s[i]>='0'&&s[i]<='9')//转化数字 
		{
			sum=sum*10+s[i++]-'0';
		}
		number[p]=sum;//设为栈顶运算数(因为下一个一定是运算符),初始化为0. 
 		do{//一定进行一轮 
				if(s[i]==')')//遇到右括号,不入栈 
				{
					while(symbol[p]!='(')//不是左括号则出栈 
					pop();
					//栈顶为左括号时 
					number[--p]=number[p+1];//处理括号对应的0;
					//此时symbol[p]为'(',因为'('对于的值是没有赋值的0,所以用栈顶的值代替括号对应的值. 
			 }
			 else
			 {
			 	if(s[i]=='-'&&s[i-1]=='*'||s[i-1]=='/')//处理负数 (单目运算符) 
			 	{number[p-1]*=-1;//改成负数
			 	 i++; 
			 	 continue;
				}
			 	while(can())//一直出栈直到可以入栈 
			 	pop();
			 	push();
			 }
			 i++;
		}while(i<strlen(s)&&s[i-1]==')');//判断是否有多重括号
	}
	cout<<number[0]<<endl; 
	return 0;
}

队列

数据结构
队列：队列是一种特殊的线性结构，只允许在首部进行删除，即为“出队”；在队尾进行插入，即为“入队”。遵循先进先出原则
数据结构
用STL实现：

#include<iostream>
#include<queue>
using namespace std;
queue<int>q;
int main(){
	int n;
	cin>>n;
	while(n--){
		int op,num;
		cin>>op;
		if(op==1){
			cin>>num;
			q.push(num);//入队
		}
		if(op==2)cout<<"back: "<<q.back()<<endl;//队尾
		if(op==3)cout<<"front: "<<q.front()<<endl;//队首
		if(op==4)q.pop();//出队
		if(op==5)cout<<"size: "<<q.size()<<endl;//大小
		if(op==6)cout<<"empty: "<<(q.empty()?"true":"false")<<endl;//是否为空
	}
	return 0;
}

循环队列

实现队列长度的式子：

int QueueLength(SqQueue Q)
{
	return  (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}

数据结构
队列满的情况：
数据结构
入队：

Status EnQueue(SqQueue *Q,QElemType e)
{
	if ((Q->rear+1)%MAXSIZE == Q->front)	/* 队列满的判断 */
		return ERROR;
	Q->data[Q->rear]=e;			/* 将元素e赋值给队尾 */
	Q->rear=(Q->rear+1)%MAXSIZE;/* rear指针向后移一位置， */
								/* 若到最后则转到数组头部 */
	return  OK;
}

出队：

Status DeQueue(SqQueue *Q,QElemType *e)
{
	if (Q->front == Q->rear)			/* 队列空的判断 */
		return ERROR;
	*e=Q->data[Q->front];				/* 将队头元素赋值给e */
	Q->front=(Q->front+1)%MAXSIZE;	/* front指针向后移一位置， */
									/* 若到最后则转到数组头部 */
	return  OK;
}

链式队列

typedef struct QNode	/* 结点结构 */
{
   QElemType data;
   struct QNode *next;
}QNode,*QueuePtr;

typedef struct			/* 队列的链表结构 */
{
   QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

构造一个空队列：

Status InitQueue(LinkQueue *Q)
{ 
	Q->front=Q->rear=(QueuePtr)malloc(sizeof(QNode));
	if(!Q->front)
		exit(OVERFLOW);
	Q->front->next=NULL;
	return OK;
}

入队：

数据结构

Status EnQueue(LinkQueue *Q,QElemType e)
{ 
	QueuePtr s=(QueuePtr)malloc(sizeof(QNode));
	if(!s) /* 存储分配失败 */
		exit(OVERFLOW);
	s->data=e;
	s->next=NULL;
	Q->rear->next=s;	/* 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中① */
	Q->rear=s;		/* 把当前的s设置为队尾结点，rear指向s，见图中② */
	return OK;
}

出队：
数据结构

Status DeQueue(LinkQueue *Q,QElemType *e)
{
	QueuePtr p;
	if(Q->front==Q->rear)
		return ERROR;
	p=Q->front->next;		/* 将欲删除的队头结点暂存给p，见图中① */
	*e=p->data;				/* 将欲删除的队头结点的值赋值给e */
	Q->front->next=p->next;/* 将原队头结点的后继p->next赋值给头结点后继，见图中② */
	if(Q->rear==p)		/* 若队头就是队尾，则删除后将rear指向头结点，见图中③ */
		Q->rear=Q->front;
	free(p);
	return OK;
}
上一篇：数据结构-栈，队列


下一篇：链式队列