數據結構實驗習題

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：BaoMinyangDate：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 -2typedef 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 100typedef 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,進制mcin>>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 -2typedef 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;//桃子數為0r->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，一猴子拿夠mLinkList 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+vConcat(S, S0, tail);i += V.length - 1;n++;}}printf("%s\n", S.ch);return n;
}