数据结构实验习题

codeblock F2是出控制台

1.1

/*
by 1705 WYY
*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define YES 1
#define NO 0
#define OK 1
#define ERROR 0
#define SUCCESS 1
#define UNSUCCESS 0
#define OVERFLOW -2
#define UNDERFLOW -3
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int Status;
typedef char ElemType;
typedef struct {
    ElemType *elem;
    int length;
    int listsize;
}SqList;

Status InitList(SqList *L){
    (*L).elem =(ElemType *)malloc(LIST_INIT_SIZE *sizeof(ElemType));
    if(!(*L).elem) exit(OVERFLOW);//分配失败
    (*L).length=0;
    (*L).listsize = LIST_INIT_SIZE;
    return OK;
}

Status ListInsert(SqList *L,int i,ElemType e)
{   ElemType *newbase;
    ElemType *p,*q;
    if(i<1||i>(*L).length+1)return ERROR;
    if((*L).length>=(*L).listsize){
        newbase = (ElemType *) realloc ((*L).elem,((*L).listsize+LISTINCREMENT)*sizeof(ElemType));
        if(!newbase) exit (OVERFLOW);
        (*L).elem =newbase;
        (*L).listsize +=LISTINCREMENT;

    }
    q=&((*L).elem[i-1]);
    for(p=&((*L).elem[(*L).length-1]);p>=q;--p)
        *(p+1) = *p;
    *q=e;
    ++(*L).length;
    return OK;

}

Status ListDelete(SqList *L,int i,ElemType *e)
{
    int j;
    ElemType *p,*q;
    if(i<1||i>(*L).length)return ERROR;
    p=&(*L).elem[i-1];
    *e=*p;
    q=(*L).elem+(*L).length-1;//指向最后的一个节点
    for(++p;p<=q;++p)
        *(p-1)=*p;
    (*L).length--;
    return OK;
}
Status GetElem(SqList L,int i ,ElemType *e )
{
    if(i<1||i>L.length)return ERROR;
    else *e=L.elem[i-1];
    return OK;
}

int main(){
SqList L;
int i;
ElemType e,z;
InitList (&L);
for(int i=1; i<=26;i++)
    ListInsert(&L,i,(char)i+64);

ListDelete(&L,4,&z);
GetElem(L,4,&z);
printf("%c\n",z);

ListInsert(&L,4,'D');
GetElem(L,4,&z);
printf("%c\n",z);
}

1.2
调试了半天总是有问题，最终发现是自己本来应该用线性链表，结果用成了线性表

/**
	Joseph问题
	Author：BaoMinyang
	Date：2018/09/20 
*/
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int ElemType;
typedef int DeleteType;
typedef int Status;

//定义链表结点 
typedef struct LNode{
	ElemType num;
	ElemType data;
	LNode *next;
}*LinkList;

//定义被删除的结点编号变量 
DeleteType del_num;

//链表初始化 
Status InitRList(LinkList &L){
	L = (LinkList) malloc (sizeof(LNode));
	if(!L) exit(OVERFLOW);
	L->next = NULL;
	return OK;
}

//创建链表 
Status CreateRList(LinkList &L,int a[],int n){
	LinkList r = L;
	for (int i = 0; i < n; ++i){
		LinkList q = (LinkList) malloc (sizeof(LNode));
		q->num = i+1;
		q->data = a[i];
		r->next = q;
		r = q;
		printf("num:%d,p:%d\n",q->num,q->data);
	}
	r->next = L->next; 
	return OK;
}

//删除链表结点 
LinkList DeleteRList(LinkList &m,int key){
	LinkList p,q;
	p = m;
	for (int j = 0; j < key-1; j++) p = p->next;
	q = p->next;
	p->next = q->next;
	printf("num:%d出列\n",q->num);
	del_num = q->data;
	free(q);
	return p;
}

//游戏开始 
Status Joseph(LinkList &L,int n,int key){
	LinkList q = L;
	bool isDone = 1;
	while (n-1){
		if (isDone){
			q = DeleteRList(q,key);
			isDone = 0;
		}
		else {
			q = DeleteRList(q,del_num);
		}
		n--;
	}
	return q->num;
}

int main(){	

	int a[35],n=0,init_m;
	LinkList L;
	
	printf("请输入m的初始值:");
	scanf("%d",&init_m);
	
	printf("请输入参加游戏的人数n:");
	scanf("%d",&n);
	
	printf("请输入每个人的密码:");
	for (int i = 0; i < n; ++i){
		scanf("%d",&a[i]);
	}
	
	InitRList(L);
	
	CreateRList(L,a,n);
	
	printf("游戏开始:\n"); 
	printf("最终剩下的是num:%d",Joseph(L,n,init_m));
	
	return 0;
}

C函数库中的malloc和free分别用于执行动态内存分配和释放。
这两个函数的原型如下所示，他们都在头文件stdlib.h中声明。
void *malloc ( size_t size );
void free ( void *pointer );
malloc的作用是在内存的动态存储区中分配一个长度为size的连续空间。其参数是一个无符号整形数，返回值是一个指向所分配的连续存储域的起始地址的指针。还有一点必须注意的是，当函数未能成功分配存储空间（如内存不足）就会返回一个NULL指针。所以在调用该函数时应该检测返回值是否为NULL，确保非空之后再使用非常重要。malloc所分配的内存是一块连续的空间。同时，malloc实际分配的内存空间可能会比你请求的多一点，但是这个行为只是由编译器定义的。malloc不知道用户所请求的内存需要存储的数据类型，所以malloc返回一个void *的指针，它可以转换为其它任何类型的指针。
void *realloc (void ptr, size_t new_size );
realloc函数用于修改一个原先已经分配的内存块的大小，可以使一块内存的扩大或缩小。当起始空间的地址为空，即ptr = NULL,则同malloc。
如果原先的内存尾部空间不足，或原先的内存块无法改变大小，realloc将重新分配另一块nuw_size大小的内存，并把原先那块内存的内容复制到新的内存块上。因此，使用realloc后就应该改用realloc返回的新指针。

2.1

/*
By WYY
*/
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
using namespace std;

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define TRUE 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW -1
#define MAXSIZE 100

typedef int Status;
typedef int SElemType;


typedef struct {
    SElemType *base;
    SElemType *top;
    int stacksize;}SqStack;

Status InitStack(SqStack &s){
s.base = (SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
if(!s.base)exit(OVERFLOW);
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return OK;
}

Status Push(SqStack &s,SElemType e)//插入新元素e
{
    if(s.top-s.base>=s.stacksize){//栈满 需要追加存储空间
        s.base=(SElemType *)realloc(s.base,(s.stacksize +STACKINCREMENT)* sizeof(SElemType));
        if(!s.base)exit(OVERFLOW);
        s.top =s.base +s.stacksize;
        s.stacksize +=STACKINCREMENT;
    }
    *s.top++ =e ;
    return OK;
}

Status Pop(SqStack &s ,SElemType &e){
//用e返回删除的这个值
if(s.top == s.base)return ERROR;
e = * --s.top;
return OK;
}

Status StackEmpty(SqStack &s){
if(s.top==s.base)return TRUE;
else return FALSE;
}

void conversion();

int main(){



    conversion();

}

void conversion (){
    int n,m;//数n,进制m
    cin>>n>>m;
    int e;
    SqStack s;
    InitStack(s);

    while(n){
        Push(s,n%m);
        n=n/m;
            }
    while(!StackEmpty(s))
    {
        Pop(s,e);
        printf("%d",e);
    }
}

函数fun 则输出fun *fun &fun值相同

表达式求值

operandtype操作数类型 operatortype 运算符类型

3.1 判断回文

while ((ch = getchar()) != '\n'){
		Push(S,ch);
		EnQueue(q,ch );
	}
	while (!StackEmpty(S)){
		Pop(S,e1);
		DeQueue(q,e2);
		if (e1 != e2) 
		{
			printf("No!!");
			return OK;
		}
	}

3.2 猴子吃桃
★实验任务
动物园里的n只猴子编号为 1，2，…，n，依次排成一队等待饲养员按规则分桃。动物
园的分桃规则是每只猴子可分得m个桃子，但必须排队领取。饲养员循环地每次取出1 个，
2 个，…，k个桃放入筐中，由排在队首的猴子领取。取到筐中的桃子数为k 后，又重新从
1开始。当筐中桃子数加上队首猴子已取得的桃子数不超过m 时，队首的猴子可以全部取出
筐中桃子。取得桃子总数不足m个的猴子，继续到队尾排队等候。当筐中桃子数加上队首猴
子已取得的桃子数超过m时，队首的猴子只能取满m个，然后离开队列，筐中剩余的桃子由
下一只猴子取用。上述分桃过程一直进行到每只猴子都分到m 个桃子。
对于给定的n，k和 m，模拟上述猴子分桃过程。
★数据输入
第 1 行中有 3 个正整数 n，k 和 m，分别表示有 n 只猴子，每次最多取k个桃到筐中，每只猴子最终都分到m个桃子。
★数据输出
将分桃过程中每只猴子离开队列的次序依次输出
输入示例
输出示例
5 3 40
1 3 5 2 4

参考了一下包包的代码，他用的线性链表。。。

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

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2

typedef int ElemType;
typedef int DeleteType;
typedef int Status;

//定义链表结点
typedef struct LNode{
	ElemType num;
	ElemType data;
	LNode *next;
}*LinkList;


//链表初始化
Status InitRList(LinkList &L){
	L = (LinkList) malloc (sizeof(LNode));
	if(!L) exit(OVERFLOW);
	L->next = NULL;
	return OK;
}

//创建链表
Status CreateRList(LinkList &L,int n){
	LinkList r = L;
	for (int i = 0; i < n; ++i){
		LinkList q = (LinkList) malloc (sizeof(LNode));
		q->num = i+1;//排编号
		q->data = 0;//桃子数为0
		r->next = q;//放进链表
		r = q;//尾指针更新

	}
	r->next = L->next;
	return OK;
}

int ListLength(LinkList L)
{
	if (L->next == NULL) return 0;
	int i = 0;
	LinkList p = L->next;
	if (p->next == L->next) return 1;
	else{
		p = p->next;
		while(p != L->next)
		{
			i++;
			p=p->next;
		}
	}
	return i+1;
}

//删除链表结点
LinkList DeleteRList(LinkList &L,int m){
	LinkList p,q;
	p = L;
	while (p->next->data != m)
		p = p->next;//p指向桃子数为m的前一个
	q = p->next;//q指向桃子数为m的那个
	p->next = q->next;//将桃子数为m的节点删除
	p = q->next;//p指向更新的节点
	printf("num:%d出列\n",q->num);
	free(q);
	return p;
}

Status print(LinkList p){
	LinkList q;
	while (q->next != p){
		q = q->next;
	}
	while (p->next != q){
		printf("%d",p->data);
		p = p->next;
	}
	printf("\n");
	return OK;
}

//开始分桃
Status Peaches(int n,int k,int m){//n猴子，最多一次放k，一猴子拿够m
	LinkList L,p;
	InitRList(L);
	CreateRList(L,n);
	p = L->next;
	int temp = 0,cnt = 0,t = 0;//cnt猴子取得的篮里的桃
	//t篮里桃

	while (ListLength(p) > 1){
		if (t) cnt = t;
		else {//重新分发桃
			cnt = temp % k + 1;
			temp++;
		}
		t = 0;//拿走桃子

		if (p->data + cnt < m){
			p->data += cnt;
			p = p->next;
		}
		else {
			t = p->data + cnt - m;
			p->data = m;
			LinkList q = p;
			p = DeleteRList(q,m);

		}
	}
	return p->num;
}

int main(){
	int n,k,m;
	cin>>n>>k>>m;
	printf("num:%d出列\n",Peaches(n,k,m));
	return 0;
}

4.1 串的置换算法

Status StrReplace(HString &S, HString T, HString V)//将v替换主串s中出现的所有与T相等的不重叠子串
{
	HString head, tail, temp, S0;
	int i, n;
	for (n = 0, i = 1; i <= (S.length - T.length + 1); i++)
	{
		SubString(temp, S, i, T.length);//用temp返回串s的第i个字符起长度为len的子串
		if (!StrCompare(temp, T))//返回0也就是相等时
		{
			SubString(head, S, 1, i - 1);
			int m = S.length - i - T.length + 1;
			SubString(tail, S, i + T.length, m);
			Concat(S0, head, V);//s0返回head+v
			Concat(S, S0, tail);
			i += V.length - 1;
			n++;
		}
	}
	printf("%s\n", S.ch);
	return n;
}