数据结构头歌实验梳理

实验一 算法表示与实现基础

1 数据交换

#include <stdio.h>
void swap(int *a,int *b){
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
int main(){
    int a,b;
    scanf("%d,%d",&a,&b);
    swap(&a,&b);
    printf("%d,%d",a,b);
    return 0;
}

2 最大最小值问题

#include<stdio.h>
typedef int ElemType;
void Compute(ElemType a[ ],int n,ElemType &max, ElemType &min);
void reverse(ElemType a[] ,int n);
int main(){
    int n;
    int a[1000];
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    int maxm=a[0];
    int minm=a[0];
    Compute(a,n,maxm,minm);
    reverse(a,n);
    
    return 0;
}
void Compute(ElemType a[ ],int n,ElemType &max, ElemType &min){
    
    
    
    for(int i=0;i<n;i++){
        if(max<a[i]){
            max=a[i];
        }
        if(min>a[i]){
            min=a[i];
        }
    }
    printf("最大值：%d\n最小值：%d\n",max,min);
}
void reverse(ElemType a[] ,int n){
    ElemType temp;
    int j=n-1;
    for(int i=0;i<n/2;i++){
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
        j--;
    }
    printf("逆置为：");
    for(int i=0;i<n-1;i++){
        printf("%d ",a[i]);
    }
    printf("%d ",a[n-1]);
    
}

3 ADT-Complex

#include<stdio.h>
typedef struct{
    int real;
    int unreal;
}Complex;

Complex create(int x,int y){
    Complex z;
    z.real=x;
    z.unreal=y;
    return z;
}
Complex add(Complex a1,Complex a2){
    Complex sum;
    sum.real=a1.real+a2.real;
    return sum;
}
int main()
{
    Complex a1,a2,a3;
    int a,b;
    scanf("%d, %d\n",&a,&b);
    a1=create(a,b);
    int c,d;
    scanf("%d, %d\n",&c,&d);
    a2=create(c,d);
    a3=add(a1,a2);
    printf("`第1个复数的实部值为：%d`\n",a1.real);
    printf("`第1个复数的虚部值为：%d`\n",a1.unreal);
    printf("`第2个复数的实部值为：%d`\n",a2.real);
    printf("`第2个复数的虚部值为：%d`\n",a2.unreal);
    printf("`2个复数的实部和为：%d`",a3.real);
    return 0;
}

数据结构与算法 - 线性表

1 实现一个顺序存储的线性表

#include <stdio.h>
#include <stdlib.h>
#include "Seqlist.h"

int SL_Create(SeqList &slist,int maxlen)
// 创建一个顺序表。
// 与SqLst_Free()配对。
{
	slist.data = (T*)malloc(sizeof(T)*maxlen);
	slist.max=maxlen;
	slist.len=0;
	return 1;
}

void SL_Free(SeqList &slist)
// 释放/删除 顺序表。
// 与SqLst_Create()配对。
{
	free(slist.data);
}

void SL_MakeEmpty(SeqList &slist)
// 置为空表。
{
	slist.len=0;
}

int SL_Length(SeqList slist)
// 获取长度。
{
	return slist.len;
}

bool SL_IsEmpty(SeqList slist)
// 判断顺序表是否空。
{
	return 0==slist.len;
}

bool SL_IsFull(SeqList slist)
// 判断顺序表是否满。
{
	return slist.len==slist.max;
}

T SL_GetAt(SeqList slist, int i)
// 获取顺序表slist的第i号结点数据。
// 返回第i号结点的值。
{
	if(i<0||i>=slist.len) {
		printf("SL_GetAt(): location error when reading elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		return slist.data[i];
}

void SL_SetAt(SeqList &slist, int i, T x)
// 设置第i号结点的值（对第i号结点的数据进行写）。
{
	if(i<0||i>=slist.len-1) {
		printf("SL_SetAt(): location error when setting elements of the slist!\n");		
		SL_Free(slist);
		exit(0);
	}
	else 
		slist.data[i]=x;
}

bool SL_InsAt(SeqList &slist, int i, T x)
// 在顺序表的位置i插入结点x, 插入d[i]之前。
// i 的有效范围[0,plist.len]。
{
    // 请在下面的Begin-End之间补充代码，插入结点。
    /********** Begin *********/
    if(i<1||i>slist.len+1) //判断i的范围是否有效 
	{
		return false;
	}
	if(slist.len>=slist.max) //当前存储空间已满，不能插入 
	{
		return false;
	}
	for(int j=slist.len;j>=i;j--) //将第i个元素及之后的元素后移 
	{
		slist.data[j]=slist.data[j-1];
	 } 
	slist.data[i-1]=x; //在第i个位置放入e 
	slist.len++; //长度加1 
	return true;

    /********** End **********/
}

T SL_DelAt(SeqList &slist, int i)
// 删除顺序表plist的第i号结点。
// i的有效范围应在[0,plist.len)内，否则会产生异常或错误。
// 返回被删除的数据元素的值。
{
    // 在下面的Begin-End之间补充代码，删除第i号结点。
    /********** Begin *********/
    if(i<1||i>slist.len)
    {
    	return false;
	}
	for(int j=i;j<slist.len;j++)
	{
		slist.data[j-1]=slist.data[j];
	}
	slist.len--;
	return true;

    /********** End **********/
}

int SL_FindValue(SeqList  slist, T x)
// 在顺序表表中查找第一个值为x的结点，返回结点的编号。
// 返回值大于等于0时表示找到值为x的结点的编号，-1表示没有找到。
{
	int i=0;
	while(i<slist.len && slist.data[i]!=x) i++;
	if (i<slist.len) return i;
	else return -1;
}

int SL_DelValue(SeqList &slist, T x)
// 删除第一个值为x的结点。
// 存在值为x的结点则返回结点编号, 未找到返回－1。
{
    // 在下面的Begin-End之间补充代码，删除第一个值为 x 的结点。
    /********** Begin *********/
    int i=0;
    while(slist.data[i]==x)
    {
    	for(int j=i;j<slist.len;j++)
    	{
    		slist.data[j-1]=slist.data[j];
		}
		slist.len--;
	}
	while(i<slist.len && slist.data[i]!=x) i++;
	if (i<slist.len) return i;
	else return -1;
    /********** End **********/
}

void SL_Print(SeqList slist)
// 打印整个顺序表。
{
	if (slist.len==0) {
		printf("The slist is empty.\n");		
		return;
	}

	//printf("The slist contains: ");
	for (int i=0; i<slist.len; i++) {
		printf("%d  ", slist.data[i]);
	}

	printf("\n");	
	
}

2 实现一个链接存储的线性表

PS：该代码块表明了链接存储线性表所有常见相关用法及性质。对于初学者需要分成一小块一小块食用

特别说明：

• “当前位置”：当前位置由curr指针给出，当前位置的前一个位置由pre指针给出，当前位置的编号由position给出。后面将定义的若干操作与当前位置有关，例如：在当前位置结点之前插入结点，在当前位置结点之后插入结点，等等。当为空链表时，curr和pre都为空指针，position为0。当前位置在非空链表的最左端时，pre为空指针，curr指向头结点，position=0。当前位置在非空链表的最右端时，pre指向尾结点，curr为空指针，position等于len。
• 要好好理解一下下面几个指针

struct LinkNode {
    T data;
    LinkNode* next;
};
struct LinkList {
    LinkNode* front;  // 指向头结点。
    LinkNode* rear;   // 指向尾结点。
    LinkNode* pre;    // 指向当前位置结点的前一个结点。
    LinkNode* curr;   // 指向当前位置结点。
    int position;     // 当前位子结点的编号。
    int len;          // 线性表的大小（链表结点数）。
};

针对链表数据，我们定义如下操作：

• 创建空线性表：创建一个链接存储的线性表，初始为空表，返回llist指针。具体操作函数定义如下：
  LinkList* LL_Create()

// 1）
LinkList* LL_Create()
// 创建一个链接存储的线性表，初始为空表，返回llist指针。
{
    LinkList* llist=(LinkList*)malloc(sizeof(LinkList));
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
    return llist;
}

• 释放线性表结点：释放链表的结点，然后释放llist所指向的结构。具体操作函数定义如下：
  void LL_Free(LinkList* llist)

// 2）	
void LL_Free(LinkList* llist)
// 释放链表的结点，然后释放llist所指向的结构。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    free(llist);
}

• 置空线性表：释放链表的所有结点，将当前线性表变为一个空表。具体操作函数定义如下：
  void LL_MakeEmpty(LinkList* llist)

// 3）	
void LL_MakeEmpty(LinkList* llist)
// 将当前线性表变为一个空表，因此需要释放所有结点。
{
    LinkNode* node=llist->front;
    LinkNode* nextnode;
    while(node){
        nextnode=node->next;
        free(node);
        node=nextnode;
    }
    llist->front=NULL;
    llist->rear=NULL;
    llist->pre=NULL;
    llist->curr=NULL;
    llist->position=0;
    llist->len=0;
}

• 获取线性表当前长度： 返回线性表的当前长度。具体操作函数定义如下：
  int LL_Length(LinkList* llist)

// 4）	
int LL_Length(LinkList* llist)
// 返回线性表的当前长度。
{
    return llist->len;
}

• 判断线性表是否为空： 若当前线性表是空表，则返回true，否则返回false。具体操作函数定义如下：
  bool LL_IsEmpty(LinkList* llist)

// 5）	
bool LL_IsEmpty(LinkList* llist)
// 若当前线性表是空表，则返回true，否则返回TRUE。
{
    return llist->len==0;
}

• 设置线性表当前位置： 设置线性表的当前位置为i号位置。设置成功，则返回true，否则返回false（线性表为空，或i不在有效范围）。假设线性表当前长度为len，那么i的有效范围为[0,len]。具体操作函数定义如下：
  bool LL_SetPosition(LinkList* llist, int i)

// 6）  
bool LL_SetPosition(LinkList* llist, int i)
// 设置线性表的当前位置为i号位置。
// 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
// 假设线性表当前长度为len，那么i的有效范围为[0,len]。
{	
    int k;
    /* 若链表为空，则返回*/
    if (llist->len==0) return false;

    /*若位置越界*/
    if( i < 0 || i > llist->len)
    {	printf("LL_SetPosition(): position error");
        return false;
    }

    /* 寻找对应结点*/
    llist->curr = llist->front;
    llist->pre = NULL;
    llist->position = 0;
    for ( k = 0; k < i; k++)	{
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = (llist->curr)->next;
    }
    
    /* 返回当前结点位置*/
    return true;
}

• 获取线性表当前位置结点编号： 获取线性表的当前位置结点的编号。具体操作函数定义如下：
  int LL_GetPosition(LinkList* llist)

// 7)	
int LL_GetPosition(LinkList* llist)
// 获取线性表的当前位置结点的编号。
{
    return llist->position;
}

• 设置线性表当前位置的下一位置为当前位置： 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。具体操作函数定义如下：
  bool LL_NextPosition(LinkList* llist)

// 8）	
bool LL_NextPosition(LinkList* llist)
// 设置线性表的当前位置的下一个位置为当前位置。
// 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。
{
    if (llist->position >= 0 && llist->position < llist->len)
    /* 若当前结点存在，则将其后继结点设置为当前结点*/
    {
        llist->position++;
        llist->pre = llist->curr;
        llist->curr = llist->curr->next;
        return true;
    }
    else 
        return false;
}

• 获取线性表当前位置的数据元素的值： 具体操作函数定义如下：
  T LL_GetAt(LinkList* llist)

// 9）	
T LL_GetAt(LinkList* llist)
// 返回线性表的当前位置的数据元素的值。
{
    if(llist->curr==NULL)
    {
        printf("LL_GetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
	}
    return llist->curr->data;
}

• 修改线性表当前位置数据元素的值： 将线性表的当前位置的数据元素的值修改为x。具体操作函数定义如下：
  void LL_SetAt(LinkList* llist, T x)

// 10）	
void LL_SetAt(LinkList* llist, T x)
// 将线性表的当前位置的数据元素的值修改为x。
{
    if(llist->curr==NULL)
    {
        printf("LL_SetAt(): Empty list, or End of the List.\n");
        LL_Free(llist);
        exit(1);
    }
    llist->curr->data=x;
}

• 在线性表当前位置之前插入数据元素： 在线性表的当前位置之前插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true。具体操作函数定义如下：
  bool LL_InsAt(LinkList* llist, T x)

// 11）	
bool LL_InsAt(LinkList* llist, T x)
// 在线性表的当前位置之前插入数据元素x。当前位置指针指向新数据元素结点。
// 若插入失败，返回false，否则返回true。
{	
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;

    newNode->data=x;

    if (llist->len==0){
        /* 在空表中插入*/
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
	}
    //当前位置为表头。
    else if (llist->pre==NULL)
    {
        /* 在表头结点处插入*/
        newNode->next = llist->front;
        llist->front = newNode;
    }
    else {  
        /* 在链表的中间位置或表尾后的位置插入*/
        newNode->next = llist->curr;
        llist->pre->next=newNode;
    }
    //插入在表尾后。
    if (llist->pre==llist->rear)
        llist->rear=newNode;
    /* 增加链表的大小*/
    llist->len++;
    /* 新插入的结点为当前结点*/
    llist->curr = newNode;
    return true;
}

• 在线性表当前位置之后插入数据元素： 在线性表的当前位置之后插入数据元素x。空表允许插入，当前位置指针将指向新结点。若插入失败，返回false，否则返回true。具体操作函数定义如下：
  bool LL_InsAfter(LinkList* llist, T x)

// 12）	
bool LL_InsAfter(LinkList* llist, T x)

// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。
{
    // 请在Begin-End之间补充代码，实现结点插入。
    /********** Begin *********/
    LinkNode *newNode=(LinkNode*)malloc(sizeof(LinkNode));
    if (newNode==NULL) return false;

    newNode->data=x;

    if (llist->len==0){
        newNode->next=NULL;
        llist->front = llist->rear = newNode;
        llist->curr = newNode;
	}
    else if (llist->curr==llist->rear)
    {
        newNode->next=NULL;
        llist->rear->next=newNode;
        llist->pre=llist->rear;
        llist->rear=newNode;
        llist->curr = newNode;
        llist->position=llist->len;
    }
    else{
        newNode->next=llist->curr->next;
        llist->curr->next=newNode;
        llist->pre=llist->curr;
        llist->curr=newNode;
        llist->position++;
    }

    llist->len++;
    return true;
    
    /********** End **********/
}

• 删除线性表当前位置数据元素结点： 若删除失败（为空表），则返回false，否则返回true。具体操作函数定义如下：
  bool LL_DelAt(LinkList* llist)

// 13）	
bool LL_DelAt(LinkList* llist)
// 删除线性表的当前位置的数据元素结点。
// 若删除失败（为空表，或当前位置为尾结点之后），则返回false，否则返回true。
{	
    LinkNode *oldNode;
    /* 若表为空或已到表尾之后，则给出错误提示并返回*/
    if (llist->curr==NULL)
    {	
        printf("LL_DelAt(): delete a node that does not exist.\n");
        return false;
    }
    oldNode=llist->curr;
    /* 删除的是表头结点*/
    if (llist->pre==NULL)
    {	
        llist->front = oldNode->next;
    }
    /* 删除的是表中或表尾结点*/
    else if(llist->curr!=NULL){
        llist->pre->next = oldNode->next;
    }
    if (oldNode == llist->rear)	{
        /* 删除的是表尾结点，则修改表尾指针和当前结点位置值*/
        llist->rear = llist->pre;
    }

    /* 后继结点作为新的当前结点*/
    llist->curr = oldNode->next;

    /* 释放原当前结点*/
    free(oldNode);

    /* 链表大小减*/
    llist->len --;
    return true;
}

• 删除线性表当前位置后面的那个数据元素结点： 若删除失败（为空表，或当前位置是表尾），则返回false，否则返回true。具体操作函数定义如下：
  bool LL_DelAfter(LinkList* llist)

// 14）	
bool LL_DelAfter(LinkList* llist)
// 删除线性表的当前位置的后面那个数据元素。
// 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。
{
    LinkNode *oldNode;
    /* 若表为空或已到表尾，则给出错误提示并返回*/
    if (llist->curr==NULL || llist->curr== llist->rear)
    {
        printf("LL_DelAfter():  delete a node that does not exist.\n");
        return false;
    }
    /* 保存被删除结点的指针并从链表中删除该结点*/
    oldNode = llist->curr->next;
    llist->curr->next=oldNode->next;
    
    if (oldNode == llist->rear)
        /* 删除的是表尾结点*/
        llist->rear = llist->curr;
    /* 释放被删除结点*/
    free(oldNode);
    /* 链表大小减*/
    llist->len --;
    return true;
}

• 查找线性表中第一个值为x的数据元素的编号： 返回值-1表示没有找到，返回值>=0表示编号。具体操作函数定义如下：
  int LL_FindValue(LinkList* llist, T x)

// 15）	
int LL_FindValue(LinkList* llist, T x)
// 找到线性表中第一个值为x的数据元素的编号。
// 返回值-1表示没有找到，返回值>=0表示编号。
{
    LinkNode* p=llist->front;
    int idx=0;
    while(p!=NULL && p->data!=x) {
        idx++;
        p = p->next;
    }
    if (idx>=llist->len) return -1;
    else return idx;
}

• 删除线性表中第一个值为x的数据元素： 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。具体操作函数定义如下：
  int LL_DelValue(LinkList* llist, T x)

// 16）	
int LL_DelValue(LinkList* llist, T x)
// 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。
{
    int idx=LL_FindValue(llist, x);
    if (idx<0) return -1;
    LL_SetPosition(llist, idx);
    LL_DelAt(llist);
    return idx;
}

• 打印整个线性表： 具体操作函数定义如下：
  void LL_Print(LinkList* llist)

// 17）	
void LL_Print(LinkList* llist)
// 打印整个线性表。
{
    LinkNode* node=llist->front;
    while (node) {
        printf("%d ", node->data);
        node=node->next;
    }
    printf("\n");
}

"LinkList.h"头文件是自己创建的
这个文件里包含：

• 创建头结点LNode
• 创建链表LinkList
• 函数声明

// 单链表 头文件
///
#if !defined(LINKED_LIST_H_LIELJE7398CNHD_INCLUDE_)
#define LINKED_LIST_H_LIELJE7398CNHD_INCLUDE_

 
typedef int T;
struct LinkNode {
    T data;
    LinkNode* next;
};
struct LinkList {
    LinkNode* front;  // 指向头结点。
    LinkNode* rear;   // 指向尾结点。
    LinkNode* pre;    // 指向当前位置结点的前一个结点。
    LinkNode* curr;   // 指向当前位置结点。
    int position;     // 当前位子结点的编号。
    int len;          // 线性表的大小（链表结点数）。
};

// 1）	
LinkList* LL_Create();
// 创建一个链接存储的线性表，初始为空表，返回llist指针。

// 2）	
void LL_Free(LinkList* llist);
// 释放链表的结点，然后释放llist所指向的结构。

// 3）	
void LL_MakeEmpty(LinkList* llist);
// 将当前线性表变为一个空表，因此需要释放所有结点。

// 4）	
int LL_Length(LinkList* llist);
// 返回线性表的当前长度。

// 5）	
bool LL_IsEmpty(LinkList* llist);
// 若当前线性表是空表，则返回true，否则返回TRUE。

// 6）  
bool LL_SetPosition(LinkList* llist, int i);
// 设置线性表的当前位置为i号位置。
// 设置成功，则返回true，否则返回false（线性表为空，或i不在有效的返回）。
// 假设线性表当前长度为len，那么i的有效范围为[0,len]。

// 7)		
int LL_GetPosition(LinkList* llist);
// 获取线性表的当前位置结点的编号。

// 8）	
bool LL_NextPosition(LinkList* llist);
// 设置线性表的当前位置的下一个位置为当前位置。
// 设置成功，则返回true，否则返回false（线性表为空，或当前位置为表尾）。

// 9）	
T LL_GetAt(LinkList* llist);
// 返回线性表的当前位置的数据元素的值。

// 10）	
void LL_SetAt(LinkList* llist, T x);
// 将线性表的当前位置的数据元素的值修改为x。

// 11）	
bool LL_InsAt(LinkList* llist, T x);
// 在线性表的当前位置之前插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。

// 12）	
bool LL_InsAfter(LinkList* llist, T x);
// 在线性表的当前位置之后插入数据元素x。空表允许插入。当前位置指针将指向新结点。
// 若插入失败，返回false，否则返回true。

// 13）	
bool LL_DelAt(LinkList* llist);
// 删除线性表的当前位置的数据元素结点。
// 若删除失败（为空表），则返回false，否则返回true。

// 14）	
bool LL_DelAfter(LinkList* llist);
// 删除线性表的当前位置的后面那个数据元素。
// 若删除失败（为空表，或当前位置时表尾），则返回false，否则返回true。

// 15）	
int LL_FindValue(LinkList* llist, T x);
// 找到线性表中第一个值为x的数据元素的编号。
// 返回值-1表示没有找到，返回值>=0表示编号。

// 16）	
int LL_DelValue(LinkList* llist, T x);
// 删除第一个值为x的数据元素，返回该数据元素的编号。如果不存在值为x的数据元素，则返回-1。

// 17）	
void LL_Print(LinkList* llist);
// 打印整个线性表。

#endif // LINKED_LIST_H_LIELJE7398CNHD_INCLUDE_

// 单链表实现文件
#include <stdio.h>
#include <stdlib.h>
#include "LinkList.h"

3 就地归并两个有序表

编程要求
首先建立两个有序单链表，就地归并后输出。

测试说明
平台会对你编写的代码进行测试：
7 //输入第一个表的长度n1
2 4 7 8 10 13 18 //依次输入n1个有序的元素
5 /输入第一个表的长度n2
3 4 5 6 9 //依次输入n2个有序的元素
预期输出：
归并表为：2 3 4 5 6 7 8 9 10 13 18

//有序表就地归并
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#define ElemType int
#define MAXSIZE 100

typedef struct{
	ElemType *elem;
	int length;
}SqList;

int InitList_Sq(SqList &L){
	L.elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));
	if(!L.elem) return 0;
	L.length=0;
	return 1;
}

void CreateList(SqList &L,int n){
	for(int i=0;i<n;i++){
		scanf("%d",&L.elem[i]);
		L.length++;
	}
}

void Print(SqList L){
	for(int i=0;i<L.length;i++){
		
		printf("%d ",L.elem[i]);
	}
}

void MergeList_Sq(SqList LA,SqList LB,SqList &LC){
    int *pa,*pb,*pc,*pa_last,*pb_last;
	pa=LA.elem; 
	pb=LB.elem;
	LC.length=LA.length+LB.length;
	LC.elem=new ElemType[LC.length];
	pc=LC.elem;
	pa_last=LA.elem+LA.length-1;
	pb_last=LB.elem+LB.length-1;
	while(pa<=pa_last && pb<=pb_last){
		if(*pa<*pb){
			*pc++=*pa++;
		}	
		else if(*pa==*pb){
			*pc++=*pa++;
			pb++;
			LC.length--;
		} 
		else *pc++=*pb++;
	}
	while(pb<=pb_last) *pc++=*pb++;
	while(pa<=pa_last) *pc++=*pa++;
	
}

int main(){
	SqList L1,L2,L3;
	if(!InitList_Sq(L1))  return false;
	if(!InitList_Sq(L2))  return false;
	int n1;
	scanf("%d",&n1);
	CreateList(L1,n1);
	int n2;
	scanf("%d",&n2);
	CreateList(L2,n2);
	MergeList_Sq(L1,L2,L3);
	Print(L3);
	return 0;
}

总结：

• 注意题目是说：有序链表（测试的时候千万不要乱输入，否则输出结果就是将两个表拼接）
• 当*pa==*pb时要单独考虑
• pa本身是一个数据指针，有对应的地址，不加*使用就是指针，加上使用就代表对应地址的值
• &L.elem[i]对他取地址，是对应元素又有一个地址，而本身L.elem是一个指针。相当于它又构成了一个指针域。
• while(pb<=pb_last) *pc++=*pb++;
  while(pa<=pa_last) *pc++=*pa++;
  这里千万不要写反了

4 两个一元多项式异地相加

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#define ElemType int
#define MAXSIZE 100
typedef struct LNode{
	float c;
	int e;
	struct LNode *next;
}LNode;
typedef LNode* LinkList;

void CreatList(LinkList *L,int n);
void AddList(LinkList La,LinkList Lb,LinkList &Lc);
void PrintList(LinkList L);

//创建一元多项式，n为项数
void CreatList(LinkList *L,int n){
	LNode *newNode, *r;
	float x;
	int y,i;
	
	*L = (LNode *)malloc(sizeof(LNode));
	if(!(*L)){
		printf("分配内存失败!\n");
		exit(OVERFLOW);
	} 
	(*L)->next = NULL;//初始化，建立一个头结点
	r = *L;//尾指针，时钟指向当前链表的尾结点
	for(i=0;i<n;i++){
		scanf("%g%d",&x,&y);
		newNode = (LNode *)malloc(sizeof(LNode));
		if(!newNode) exit(OVERFLOW);
		newNode->c = x;
		newNode->e = y;
		r->next = newNode;
		r = newNode;
	} 
	r->next = NULL;
}

//多项式相加，Lc=La+Lb
void AddList(LinkList La,LinkList Lb,LinkList &Lc){
	LNode *pa,*pb,*pc,*s;
	pc = Lc =(LNode *)malloc(sizeof(LNode));
	pc->next = NULL;
	pa = La->next;
	pb = Lb->next;
	while(pa!=NULL&&pb!=NULL){
		if(pa->e < pb->e){
			s = (LNode *)malloc(sizeof(LNode));
			s->c = pa->c;
			s->e = pa->e;
			s->next = NULL;
			pc->next = s;
			pc = s;
			pa = pa->next;
		}else if(pa->e > pb->e){
			s = (LNode *)malloc(sizeof(LNode));
			s->c = pb->c;
			s->e = pb->e;
			s->next = NULL;
			pc->next = s;
			pc = s;
			pb = pb->next;
		}else{
			float x=pa->c+pb->c;
			if(abs(x)<=1.0e-6){
				pa=pa->next;
				pb=pb->next;
			}else{
				s = (LNode *)malloc(sizeof(LNode));
				s->c=x;
				s->e=pb->e;
				s->next=NULL;
				pc->next=s;
				pa = pa->next;
				pb = pb->next;
			}
		}
	}
	while(pa!=NULL){    //pb==NULL时，将a的剩余部分连到c后面 
		s=(LNode *)malloc(sizeof(LNode));
		s->c = pa->c;
		s->e = pa->e;
		s->next = NULL;
		pc->next = s;
		pc = s;
		pa = pa->next;
	}
	while(pb!=NULL){
		s=(LNode *)malloc(sizeof(LNode));
		s->c = pb->c;
		s->e = pb->e;
		s->next = NULL;
		pc->next = s;
		pc = s;
		pb = pb->next;
	}
} 
//输出多项式系数和指数
void PrintList(LinkList L){
	if(L->next==NULL){
		printf("0");
		return;
	}
	LNode *p = L->next;
	while(p!=NULL){	
		printf("%g %d ",p->c,p->e);
		p=p->next;	
	}
}
int main(){
	LinkList La,Lb,Lc;
	int n1,n2;
	scanf("%d",&n1);
	CreatList(&La,n1);

	scanf("%d",&n2);
	CreatList(&Lb,n2);
	AddList(La,Lb,Lc);

	PrintList(Lc);
	return 0;
}

5 约瑟夫环问题

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100
#define ElemType int
typedef struct node{
	ElemType data;
	ElemType passw;
	struct node *next;
}ElemSN; 
ElemSN *Create();
int n,m;
void Josephus(ElemSN *tail);
int main(){
	ElemSN *tail;
	tail = Create();
	Josephus(tail);
}
ElemSN *Create(){
	ElemSN *tail=NULL,*p;
	scanf("%d%d",&m,&n);
	for(int i=0;i<n;i++){
		p=(ElemSN *)malloc(sizeof(ElemSN));
		//tail为空，建立尾结点： 
		if(!tail){
			tail=p->next=p;
			//位置序号为1
			p->data=i+1;
			//输入第一个人的密码 

			scanf("%d",&p->passw); 
		}else{
			p->data=i+1;
			scanf("%d",&p->passw);
			//使尾结点后移 
			p->next=tail->next;
			//构成循环 
			tail=tail->next=p;
		} 
	}
	return tail;
}
void Josephus(ElemSN *tail){
	int i=0;
	ElemSN *p=NULL;
	while(n){
		i=(i+1)%m;
		if(i)
			tail=tail->next;
		else{
			p=tail->next;
			tail->next=p->next;
			printf("%d ",p->data);
			m=p->passw;
			free(p);
			n--;
			i=0;
		}
	}
}

实验三 栈之基础

1 顺序存储的栈

输入格式：
首先输入一个正整数max，创建一个最多可存储max个元素的栈。然后输入多个操作：如果输入”push”，则后面跟一个数x，表示x进栈；如果输入”pop”，表示出栈操作；如果输入”end”，表示输入结束。

输出格式：
输出栈的长度，然后从栈底到栈顶依次输出各元素。

样例输入:
6
push 56
push 15
push 12
push 13
pop
end
样例输出
Stack length: 3
stack data (from bottom to top): 56 15 12
SeqStack.h

typedef int T;
struct SeqStack{
    T* data; // 数据元素指针
    int top; // 栈顶元素编号
    int max; // 最大节点数
};

SeqStack* SS_Create(int maxlen);
void SS_Free(SeqStack* ss);
void SS_MakeEmpty(SeqStack* ss);
bool SS_IsFull(SeqStack* ss);
bool SS_IsEmpty(SeqStack* ss);
int SS_Length(SeqStack* ss);
bool SS_Push(SeqStack* ss, T x);
bool SS_Pop(SeqStack* ss, T& item);
bool SS_Top(SeqStack* ss, T& item);
void SS_Print(SeqStack* ss);

//顺序存储的栈 实现文件
/
#include <stdio.h>
#include <stdlib.h>
#include "SeqStack.h"

/*创建一个栈*/
SeqStack* SS_Create(int maxlen)
{
	SeqStack* ss=(SeqStack*)malloc(sizeof(SeqStack));
	ss->data=(T*)malloc(maxlen*sizeof(T));
	ss->top=-1;
	ss->max=maxlen;
	return ss;
}

/*释放一个栈*/
void SS_Free(SeqStack* ss)
{
	free(ss->data);
	free(ss);
}

/*清空一个栈*/
void SS_MakeEmpty(SeqStack* ss)
{
	ss->top=-1;
}

/*判断栈是否为满*/
bool SS_IsFull(SeqStack* ss)
{
	/*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
	return ss->top+1>=ss->max;
    /******END******/
}

/*判断栈是否为空*/
bool SS_IsEmpty(SeqStack* ss)
{
	/*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
	return ss->top<=-1;

    /******END******/
}

/*获取栈元素个数*/
int SS_Length(SeqStack* ss)
{
	/*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
	return ss->top+1;
    /******END******/
}

/*将x进栈,满栈则无法进栈(返回false)*/
bool SS_Push(SeqStack* ss, T x)
{
	/*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
	if(SS_IsFull(ss))  return false;
	else{
		ss->top++;
		ss->data[ss->top]=x;
		return true;
	}

    /******END******/
}

/*出栈，出栈的元素放入item,空栈则返回false*/
bool SS_Pop(SeqStack* ss, T &item)
{
	/*请在BEGIN和END之间实现你的代码*/
    /*****BEGIN*****/
	if(SS_IsEmpty(ss))  return false;
	else{
		item=ss->data[ss->top];
		ss->top--;
	}
    /******END******/
}

/*获取栈顶元素放入item中,空栈则返回false*/
bool SS_Top(SeqStack* ss, T & item)
{
	if (SS_IsEmpty(ss)) {
		return false;
	}
	item = ss->data[ss->top];
	return true;
}

/*从栈底到栈顶打印出所有元素*/
void SS_Print(SeqStack* ss)
{
	if (SS_IsEmpty(ss)) {
		printf("stack data: Empty!\n");
		return;
	}
	printf("stack data (from bottom to top):");
	int curr=0;
	while(curr<=ss->top) {
		printf(" %d", ss->data[curr]);
		curr++;
	}
	//printf("\n");
}

2 实现一个链接存储的栈

这种实现方案中与栈相关的两个属性元素top和len介绍如下：

• top: 指向栈顶结点的指针
• len: 栈中结点的个数
  特别说明：链接存储方式下，链表头结点作为栈顶结点，用指针top指向栈顶结点，栈结点个数由len给出。
  

编程要求
本关任务是实现step2/LnkStack.cpp中的LS_IsEmpty、LS_Length、LS_Push、LS_Pop和LS_Top五个操作函数，以实现判断栈是否为空、求栈的长度、进栈、出栈以及获取栈顶元素等功能。具体要求如下：

输入输出格式请参见后续说明及测试样例。
本关任务是实现step2/LnkStack.cpp中的LS_IsEmpty、LS_Length、LS_Push、LS_Pop和LS_Top五个操作函数，以实现判断栈是否为空、求栈的长度、进栈、出栈以及获取栈顶元素等功能。具体要求如下：

• LS_IsEmpty：判断栈是否为空，若栈为空，则返回true，否则返回false。

• LS_Length：获取链式栈的长度。

• LS_Push：将元素x进栈，若满栈则无法进栈，返回false，否则返回true。

• LS_Pop：若出栈成功(栈不为空)，则返回true；否则(空栈)，返回false。

• LS_Top：获取栈顶元素。

// 栈的链接存储 头文件

#if !defined(LINKED_STACK_H_985552)
#define LINKED_STACK_H_985552
typedef int T; //数据元素类型
struct LNode {
    T data;
    LNode* next;
};

struct LinkStack {
    LNode* top; // 栈顶指针
    int len; // 栈的长度
};


LinkStack* LS_Create();
void LS_Free(LinkStack* ls);
void LS_MakeEmpty(LinkStack* ls);
bool LS_IsEmpty(LinkStack* ls);
int LS_Length(LinkStack* ls);
void LS_Push(LinkStack* ls, T x);
bool LS_Pop(LinkStack* ls, T& item);
bool LS_Top(LinkStack* ls, T& item);
void LS_Print(LinkStack* ls);
#endif
//

// 链接存储的栈实现文件

#include <stdio.h>
#include <stdlib.h>
#include "LnkStack.h"

/*创建栈*/
LinkStack* LS_Create()
{
    LinkStack* ls=(LinkStack*)malloc(sizeof(LinkStack));
    ls->top = NULL;
    ls->len = 0;
    return ls;
}

/*释放栈*/
void LS_Free(LinkStack* ls)
{
    LNode* curr = ls->top;
    while(curr) {
        LNode* next = curr->next;
        free(curr);
        curr=next;
    }
    free(ls);
}

/*将栈变为空栈*/
void LS_MakeEmpty(LinkStack* ls)
{
    LNode* curr = ls->top;
    while(curr) {
        LNode* next = curr->next;
        free(curr);
        curr=next;
    }
    ls->top = NULL;
    ls->len = 0;
}

/*判断栈是否为空*/
bool LS_IsEmpty(LinkStack* ls)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    return ls->top==NULL;

    /********** End **********/
}

/*获取栈的长度*/
int LS_Length(LinkStack* ls)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    return ls->len;


    /********** End **********/
}

/*将x进栈*/
void LS_Push(LinkStack* ls, T x)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    LNode* node=(LNode*)malloc(sizeof(LNode));
    node->data=x;
    node->next=ls->top;
    ls->top=node;
    ls->len++;

    /********** End **********/
}

/*出栈。出栈元素放入item；如果空栈，将返回false*/
bool LS_Pop(LinkStack* ls, T& item)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    LNode*node=ls->top;
    if(node==NULL)  return false;
    item=node->data;
    ls->top=node->next;
    ls->len--;

    /********** End **********/
}

/*读栈顶元素放入item。如果空栈，将返回false*/
bool LS_Top(LinkStack* ls, T& item)
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    LNode* node=ls->top;
    if (node==NULL) 
    {
        return false;
    }
    item = node->data;
    return true;

    /********** End **********/
}

/*从栈顶到栈底打印各结点数据*/
void LS_Print(LinkStack* ls)
{
    if (ls->len==0){ 
        printf("The stack: Empty!");
        return;
    }
    printf("The stack (from top to bottom):");
    LNode* curr=ls->top;
    while(curr) {
        printf(" %d", curr->data);
         
        curr=curr->next;
    }
   // printf("\n");
}

实验三 栈之应用

第1关：利用栈实现整数的十进制转八进制

样例一：
测试输入：71
预期输出：107

样例二：
测试输入：8
预期输出：10

#ifndef stack__h
#define stack__h
#endif /* stack__h */
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

typedef int T; // 数据元素的数据类型

struct Stack{
    T* data;   // 数据元素存储空间的开始地址
    int top;   // 栈顶的位置
    int max;   // 栈的最大长度
};


Stack* Stack_Create(int maxlen);
// 创建栈

void Stack_Free(Stack* stk);
// 释放栈

void Stack_MakeEmpty(Stack* stk);
// 置为空栈

bool Stack_IsEmpty(Stack* stk);
// 判断栈是否空

bool Stack_IsFull(Stack* stk);
// 判断栈是否满

T Stack_Top(Stack* stk);
// 返回栈顶元素

T Stack_Push(Stack* stk, T e);
// 将元素e压入栈顶
// 返回栈顶点元素

T Stack_Pop(Stack* stk);
// 将栈顶元素出栈
// 返回栈顶元素

void Stack_Print(Stack* stk);
// 打印栈顶到栈低的元素

void Decimal_Conversion_Octal(T e);
//  利用stack栈实现整数的十进制转八进制
//  输入参数：十进制整数 e
//  打印结果，末尾换行

int main(int argc, const char * argv[]) {
    T e;
    scanf("%d", &e);
    Decimal_Conversion_Octal(e);
    return 0;
}

Stack* Stack_Create(int maxlen)
// 创建栈
{
    Stack* stk = (Stack*)malloc(sizeof(Stack));
    stk->data = (T*)malloc(sizeof(T)*maxlen);
    stk->max = maxlen;
    stk->top = -1;
    return stk;
}

void Stack_Free(Stack* stk)
// 释放栈
{
    free(stk->data);
    free(stk);
}

void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
    stk->top = -1;
}

bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
    return -1 == stk->top;
}

bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
    return stk->top == stk->max-1;
}

T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
    return stk->data[stk->top];
}

T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
    if(Stack_IsFull(stk)) {
        printf("Stack_IsFull(): stack full error when push element to the stack!\n");
        Stack_Free(stk);
        exit(0);
    }
    else{
        stk->top += 1;
        stk->data[stk->top] = e;
        return Stack_Top(stk);
    }
}

T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
    if(Stack_IsEmpty(stk)) {
        printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
        Stack_Free(stk);
        exit(0);
    }
    else{
        T topE = Stack_Top(stk);
        stk->top -= 1;
        return topE;
    }
}

void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
    if (Stack_IsEmpty(stk)) {
        printf("The stack is empty.\n");
        return;
    }
    
    //printf("The stack contains: ");
    for (int i=stk->top; i>=0; i--) {
        printf("%d", stk->data[i]);
    }
    printf("\n");
    
}

void Decimal_Conversion_Octal(T e)
//  利用stack栈实现整数的十进制转八进制
//  输入参数：十进制整数 e
//  打印e的八进制结果，末尾换行
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    Stack *stk = Stack_Create(32);
    while(e){
        Stack_Push(stk, e%8);//入栈 取余数
        e=e/8;
    }
    while(!Stack_IsEmpty(stk)){
        e = Stack_Pop(stk);//出栈
        printf("%d",e);
    }     
    /********** End **********/
}

第2关：利用栈判断字符串括号是否匹配

编程要求：基于栈stack数据结构判断字符串中的括号是否匹配，字符串中仅包含如下字符：( ) [ ] { }。

样例一：
测试输入：
6
{[()]}
预期输出：
YES

样例二：
测试输入：
4
[(])
预期输出：
NO

Stack* Stack_Create(int maxlen)
// 创建栈
{
    Stack* stk = (Stack*)malloc(sizeof(Stack));
    stk->data = (T*)malloc(sizeof(T)*maxlen);
    stk->max = maxlen;
    stk->top = -1;
    return stk;
}

void Stack_Free(Stack* stk)
// 释放栈
{
    free(stk->data);
    free(stk);
}

void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
    stk->top = -1;
}

bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
    return -1 == stk->top;
}

bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
    return stk->top == stk->max-1;
}

T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
    return stk->data[stk->top];
}

T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
    if(Stack_IsFull(stk)) {
        printf("Stack_IsFull(): stack full error when push element to the stack!\n");
        Stack_Free(stk);
        exit(0);
    }
    else{
        stk->top += 1;
        stk->data[stk->top] = e;
        return Stack_Top(stk);
    }
}

T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
    if(Stack_IsEmpty(stk)) {
        printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
        Stack_Free(stk);
        exit(0);
    }
    else{
        T topE = Stack_Top(stk);
        stk->top -= 1;
        return topE;
    }
}

void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
    if (Stack_IsEmpty(stk)) {
        printf("The stack is empty.\n");
        return;
    }
    
    //printf("The stack contains: ");
    for (int i=stk->top; i>=0; i--) {
        printf("%d", stk->data[i]);
    }
    printf("\n");
    
}

void Bracket_Match(T* str, int len)
//  利用stack栈判断括号是否匹配
//  输入参数：字符串序列，字符串长度
//  若匹配输出YES，否则输出NO，末尾换行
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    Stack *stk=Stack_Create(len);
    int i;
    char ch;
    bool flag=1;
    //判断栈是否满
    Stack_IsFull(stk);
    for(i=0;i<len;++i)
    {
    switch(str[i])
    {
        case'(':
        case'[':
        case'{':Stack_Push(stk,str[i]); break;//入栈
 
        case')':
        case']':
        case'}':Stack_Top(stk);// 获取当前栈顶元素
                ch=stk->data[stk->top];//赋值给ch
 
        if((ch=='('&&str[i]==')')||(ch=='['&&str[i]==']')||(ch=='{'&&str[i]=='}')){
                Stack_Pop(stk);// 将栈顶元素出栈
            }
            else {
                flag=0;
            }
    }
}
    //判断栈顶指针是否为空，不为空则说明还没判断完成
    if (stk->top!=-1)
        flag = 0;
    
    if (flag==1)
        printf("YES\n");
 
    else
        printf("NO\n");
 
    /********** End **********/
}

第3关：利用栈判断字符串是否为回文串

样例一：
测试输入：
4
1221
预期输出：
YES

样例二：
测试输入：
7
abababa
预期输出：
YES

Stack* Stack_Create(int maxlen)
// 创建栈
{
    Stack* stk = (Stack*)malloc(sizeof(Stack));
    stk->data = (T*)malloc(sizeof(T)*maxlen);
    stk->max = maxlen;
    stk->top = -1;
    return stk;
}

void Stack_Free(Stack* stk)
// 释放栈
{
    free(stk->data);
    free(stk);
}

void Stack_MakeEmpty(Stack* stk)
// 置为空栈
{
    stk->top = -1;
}

bool Stack_IsEmpty(Stack* stk)
// 判断栈是否空
{
    return -1 == stk->top;
}

bool Stack_IsFull(Stack* stk)
// 判断栈是否满
{
    return stk->top == stk->max-1;
}

T Stack_Top(Stack* stk)
// 获取当前栈顶元素
{
    return stk->data[stk->top];
}

T Stack_Push(Stack* stk, T e)
// 将元素e压入栈顶
// 返回栈顶点元素
{
    if(Stack_IsFull(stk)) {
        printf("Stack_IsFull(): stack full error when push element to the stack!\n");
        Stack_Free(stk);
        exit(0);
    }
    else{
        stk->top += 1;
        stk->data[stk->top] = e;
        return Stack_Top(stk);
    }
}

T Stack_Pop(Stack* stk)
// 将栈顶元素出栈
// 返回栈顶元素
{
    if(Stack_IsEmpty(stk)) {
        printf("Stack_IsEmpty(): stack empty error when pop element of the stack top!\n");
        Stack_Free(stk);
        exit(0);
    }
    else{
        T topE = Stack_Top(stk);
        stk->top -= 1;
        return topE;
    }
}

void Stack_Print(Stack* stk)
// 打印栈顶到栈低的元素
{
    if (Stack_IsEmpty(stk)) {
        printf("The stack is empty.\n");
        return;
    }
    
    //printf("The stack contains: ");
    for (int i=stk->top; i>=0; i--) {
        printf("%d", stk->data[i]);
    }
    printf("\n");
    
}

void Palindrome(T* str, int len)
//  利用stack栈判断字符串是否为回文串
//  输入参数：字符串序列，字符串长度
//  若是回文串输出YES，否则输出NO，末尾换行
{
    // 请在这里补充代码，完成本关任务
    /********** Begin *********/
    if(len==1){
        printf("YES\n");
    }else{
        //创建一个栈
        Stack *s=Stack_Create(100);
        //判断长度为奇偶
        if(len%2!=0){
       
            for(int i=len/2;i<len;i++){
				str[i]=str[i+1];
			}
            for(int i=0;i<len-1;i++){
                //将当前栈顶元素赋给st
		    	char st=Stack_Top(s);
                
		    	if(st==str[i]){
		    	//匹配后将栈顶元素出栈，返回栈顶元素
		    		Stack_Pop(s);
				}else{
				//将元素str[i]压入新栈s
					Stack_Push(s,str[i]);
				}
			}
            if(Stack_IsEmpty(s)){
				printf("YES\n");
			}else{
				printf("NO\n");
			}        
        }else{
            for(int i=0;i<len;i++){
		    	char st=Stack_Top(s);
		    	if(st==str[i]){
		    		Stack_Pop(s);
				}else{
					Stack_Push(s,str[i]);
				}
			}
			if(Stack_IsEmpty(s)){
				printf("YES\n");
			}else{
				printf("NO\n");
			}
        }
    }
   /********** End **********/
}

队列之基础

第1关：实现一个顺序存储的队列

#if !defined(SEQUENCE_QUEUE_H_LIELJE7398CNHD_INCLUDE_)
#define SEQUENCE_QUEUE_H_LIELJE7398CNHD_INCLUDE_
/
typedef int T;
struct SeqQueue { 
    T* data; // 指向数据元素数组的指针。
    int front; // 下一个出队元素的数组下标。
    int rear; // 下一个入队元素应该存放的单元的数组下标。
    int max;  // 队列中最多可放max-1个数据元素，留一个空数据单元以区分空和满。
};

SeqQueue* SQ_Create(int maxlen);
void SQ_Free(SeqQueue* sq);
void SQ_MakeEmpty(SeqQueue* sq);
bool SQ_IsEmpty(SeqQueue* sq);
bool SQ_IsFull(SeqQueue* sq);
int SQ_Length(SeqQueue* sq);

bool SQ_In(SeqQueue* sq, T x);
bool SQ_Out(SeqQueue* sq, T& item);
bool SQ_Head(SeqQueue* sq, T& head);

void SQ_Print(SeqQueue* sq);

#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"
#include <string.h>
#pragma warning(disable:4996)

int main()
{
    int maxlen;
    scanf("%d", &maxlen);
    SeqQueue* sq=SQ_Create(maxlen);
    char dowhat[100];
    while(true) {
        scanf("%s", dowhat);
        if (!strcmp(dowhat,"in")) {
            T x;
            scanf("%d", &x);
            SQ_In(sq,x);
        }else if (!strcmp(dowhat,"out")) {
            T item;
            SQ_Out(sq, item);
        }
        else {
            break;
        }
    }
    int length=SQ_Length(sq);
    printf("Queue length: %d\n", length);
    printf("Queue data: ");
    SQ_Print(sq);
    SQ_Free(sq);
}

#include <stdio.h>
#include <stdlib.h>
#include "SeqQueue.h"

SeqQueue* SQ_Create(int maxlen)
// 创建顺序队列, 队列最多存储maxlen个队列元素。
{
    SeqQueue* sq=(SeqQueue*)malloc(sizeof(SeqQueue));
    sq->data=(T*)malloc(sizeof(T)*(maxlen+1));
    sq->front=sq->rear=0;
    sq->max=maxlen+1;
    return sq;
}

void SQ_Free(SeqQueue* sq)
// 释放队列空间，以删除队列。
{
    free(sq->data);
    free(sq);
}

void SQ_MakeEmpty(SeqQueue* sq)
// 将队列置空。
{
    sq->front=0;
    sq->rear=0;
}

bool SQ_IsEmpty(SeqQueue* sq)
// 判断队列是否为空，为空返回true，否则返回false。
{
    // 请在Begin-End之间补充代码，完成队列是否为空的判断。
    /********** Begin *********/

    return sq->front==sq->rear;


    /********** End **********/
}

bool SQ_IsFull(SeqQueue* sq)
// 判断队列是否为满。为满返回true,否则返回false。
{
    // 请在Begin-End之间补充代码，完成队列是否为满的判断。
    /********** Begin *********/
    if((sq->rear+1)%sq->max==sq->front)
    return true;


    /********** End **********/
}

int SQ_Length(SeqQueue* sq)
// 队列长度。
{
    // 请在Begin-End之间补充代码，获取队列长度。
    /********** Begin *********/

    return(sq->rear-sq->front+sq->max)%sq->max;


    /********** End **********/
}

bool SQ_In(SeqQueue* sq, T x)
// 将x入队。若入队失败(队列满)，则返回false，否则返回true。
{
    // 请在Begin-End之间补充代码，将 x 入队。
    /********** Begin *********/

    if((sq->rear+1)%sq->max==sq->front)
    return false;
    T*head=sq->data;
    head[sq->rear]=x;//新元素插入队尾
    sq->rear=(sq->rear+1)%sq->max;//队尾指针加1
 
    /********** End **********/
}

bool SQ_Out(SeqQueue* sq, T& item)
// 从队列sq出队一个元素，返回时item为出队的元素的值。若出队成功(队列不为空)，则返回true，否则(队列空)，返回false，此时item不会返回有效值。
{
    // 请在Begin-End之间补充代码，完成元素出队操作。
    /********** Begin *********/
   if(sq->front==sq->rear)  return false;
    T*head=sq->data;//做的时候出错的地方
    item=head[sq->front];//保留队头的元素
    sq->front=(sq->front+1)%sq->max;//很容易遗漏的一点，队头指针需要加1
    return true;


    /********** End **********/
}

bool SQ_Head(SeqQueue* sq, T& head)
// 获取队列头结点元素，返回时head保存头结点元素。
// 若获取失败(队列空)，则返回值为false，否则返回值为true。
{
    if ( SQ_IsEmpty(sq) ){
        return false;
    }
    else {
        head = sq->data[sq->front];
        return true;
    }
}

void SQ_Print(SeqQueue* sq)
// 依次打印出队列中的每个元素。
{
    int i=sq->front;
    if (SQ_IsEmpty(sq)) {
        printf("queue is emtpy");
        return;
    }
    for (i=sq->front; i!=sq->rear; i=(i+1)%sq->max) {
        printf("%d  ", sq->data[i]);
    }
    printf("\n");
}

第2关：实现一个链接存储的队列

输入输出说明：

• 输入格式：
  输入多个操作：如果输入 “in” ，则后面跟一个数 x ，表示 x 入队列；如果输入 “out” ，表示出队列操作；如果输入 “end” ，表示输入结束。

• 输出格式：
  输出队列长度，然后从队头到队尾依次输出队列的各元素。文章来源地址https://www.toymoban.com/news/detail-411086.html

typedef int T;

struct LNode {
    T data;
    LNode* next;
};

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CLnkQueue.h"
#pragma warning(disable:4996)
int main()
{
    LNode* rear=CLQ_Create();
    char dowhat[100];
    while(true) {
        scanf("%s", dowhat);
        if (!strcmp(dowhat,"in")) {
            T x;
            scanf("%d", &x);
            CLQ_In(rear,x);
        }else if (!strcmp(dowhat,"out")) {
            T item;
            CLQ_Out(rear, item);
        }
        else {
            break;
        }
    }
    int length=CLQ_Length(rear);
    printf("Queue length: %d\n", length);
    printf("Queue data: ");
    CLQ_Print(rear);
    CLQ_Free(rear);
}

#include <stdio.h>
#include <stdlib.h>
#include "CLnkQueue.h"

LNode* CLQ_Create()
// 创建一个队列。
{
    LNode* rear=(LNode*)malloc(sizeof(LNode));
    rear->data = 0;
    rear->next = rear;
    return rear;
}
void CLQ_Free(LNode* rear)
// rear指向尾结点。
{
    CLQ_MakeEmpty(rear);
    free(rear);
}

void CLQ_MakeEmpty(LNode* & rear)
// rear指向尾结点。
// 将队列变为空队列。
{
    T item;
    while(!CLQ_IsEmpty(rear))
        CLQ_Out(rear,item);
}

bool CLQ_IsEmpty(LNode* rear)
// 判断队列是否为空。
{
    // 请在Begin-End之间补充代码，完成队列是否为空的判断。
    /********** Begin *********/

    return rear==rear->next;
 


    /********** End **********/
}

int CLQ_Length(LNode* rear)
// 返回队列长度，rear指向尾结点。
{
    // 请在Begin-End之间补充代码，获取队列长度。
    /********** Begin *********/

    return rear->next->data;
 
    /********** End **********/
}

void CLQ_In(LNode* & rear, T x)
// 入队列, 新结点加入链表尾部。rear指向尾结点。
{
    // 请在Begin-End之间补充代码，完成新结点入队操作。
    /********** Begin *********/
    LNode*newNode=new LNode;
    newNode->data=x;
    newNode->next=rear->next;
    rear->next=newNode;
    rear=newNode;
    rear->next->data++;//为输出做准备
 
    /********** End **********/
}

bool CLQ_Out(LNode* & rear, T& item)
// 出队列。空队列时，返回值为false。rear指向尾结点。
{
    // 请在Begin-End之间补充代码，完成结点出队操作。
    /********** Begin *********/
 if(CLQ_IsEmpty(rear))  return false;
    else if(rear->next->data==1) 
    {
        rear=rear->next;
        rear->next=rear;
        rear->data--;
    }
    else
 {
        LNode* addNode=rear->next;
        addNode->next=addNode->next->next;
        addNode->data--;
        return true;
    } 

    /********** End **********/
}

bool CLQ_Head(LNode* rear, T& item)
// rear指向尾结点。
// 获取队列头。空队列时返回值为false。
{
    if (CLQ_IsEmpty(rear)) 
        return false;

    item = rear->next->next->data;
    return true;
}
void CLQ_Print(LNode* rear)
// 打印队列。
{
    if (CLQ_IsEmpty(rear))  {
        printf("The queue is: empty. \n");
        return;
    }
    LNode* node=rear->next->next;
    do {
        printf("%d  ", node->data);
        node = node->next;
    }   while (node != rear->next); 
    //printf("\n");
}

到了这里，关于数据结构头歌实验梳理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！