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

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

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]);
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

数据结构与算法 - 线性表

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");

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163

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;          // 线性表的大小（链表结点数）。
};
1
2
3
4
5
6
7
8
9
10
11
12

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

• 创建空线性表：创建一个链接存储的线性表，初始为空表，返回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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 释放线性表结点：释放链表的结点，然后释放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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 置空线性表：释放链表的所有结点，将当前线性表变为一个空表。具体操作函数定义如下：
  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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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

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

1
2
3
4
5
6
7

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

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

• 设置线性表当前位置： 设置线性表的当前位置为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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

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

1
2
3
4
5
6
7

• 设置线性表当前位置的下一位置为当前位置： 设置成功，则返回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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 获取线性表当前位置的数据元素的值： 具体操作函数定义如下：
  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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

• 修改线性表当前位置数据元素的值： 将线性表的当前位置的数据元素的值修改为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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

• 在线性表当前位置之前插入数据元素： 在线性表的当前位置之前插入数据元素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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

• 在线性表当前位置之后插入数据元素： 在线性表的当前位置之后插入数据元素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 **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

• 删除线性表当前位置数据元素结点： 若删除失败（为空表），则返回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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

• 删除线性表当前位置后面的那个数据元素结点： 若删除失败（为空表，或当前位置是表尾），则返回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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

• 查找线性表中第一个值为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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 删除线性表中第一个值为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;
}
1
2
3
4
5
6
7
8
9
10

• 打印整个线性表： 具体操作函数定义如下：
  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");
}

1
2
3
4
5
6
7
8
9
10
11
12

"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_

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98

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

1
2
3
4
5

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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

总结：

• 注意题目是说：有序链表（测试的时候千万不要乱输入，否则输出结果就是将两个表拼接）
• 当*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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

实验三 栈之基础

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);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

//顺序存储的栈 实现文件
/
#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");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

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
//

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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

#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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121

实验三 栈之应用

第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 **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164

第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 **********/
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135

第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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

队列之基础

第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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#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");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

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

输入输出说明：

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

• 输出格式：
  输出队列长度，然后从队头到队尾依次输出队列的各元素。

typedef int T;

struct LNode {
    T data;
    LNode* next;
};
1
2
3
4
5
6

#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);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#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");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115