数据结构题目练习_利用原表的存储空间和利用原有结点是一回事儿吗

顺序表的就地逆置

编写一个函数，实现顺序表的就地逆置，也就是说利用原表的存储空间将顺序表（a1,a2…an）,逆置为（an,an-1…a1)

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 10//静态顺序表的最大空间

typedef struct
{
    int *base;
    int length;
}Sqlist;//顺序表


void reverseSQ(Sqlist *l)   
{   //实现顺序表l的就地逆置
    int low = 0, high = l->length - 1;
    int buf, i;


    for (int  i = 0; i < l->length / 2; i++)
    {   //循环l->length/2次
        buf = l->base[low];
        l->base[low] = l->base[high];
        l->base[high] = buf;
        low++;
        high--;
    }
}
int main(int argc, char const *argv[])
{
    Sqlist l;
    int i, data;

    l.base = (int*)malloc(sizeof(int) * MAXSIZE);
    l.length = 0;//创建顺序表
    if (!l.base)
    {   //分配内存失败
        printf("error!\n");
    }

    //输入数据

    for (i = 0; i < MAXSIZE; i++)
    {
        scanf("%d", &l.base[i]);
        l.length++;
    }

    //输出数据

    for (i = 0; i < l.length; i++)
    {
        printf("%d ", l.base[i]);
    }
    printf("\n");

    reverseSQ(&l);//就地逆置

    for (i = 0; i < l.length; i++)
    {
        printf("%d ", l.base[i]);
    }

    system("pause");
    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

动态数列排序

实现这样的功能：从键盘上输入任意个整数，以0作为结束标志，对这个整数序列从小到大排序，并输出排序后的结构

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

//定义链表的结点类型
typedef struct node
{
    int data;
    struct node *next;
}LNode, *LinkList;

//创建一个长度为n的链表
LinkList creatList(int n)
{
    LinkList p, q, list = NULL;
    int elem, i;

    for (i = 0; i < n; i++)
    {
        scanf("%d", &elem);
        p = (LinkList)malloc(sizeof(LNode));
        if (!p)
        {
            return NULL;
        }
        p->data = elem;
        p->next = NULL;
        if (list == NULL)
        {
            list = p;//第一个结点
        }
        else
        {
            q->next = p;
        }
        q = p;
    }
    return list;
}

//向链表中插入结点，并向该结点的数据域中存放数据
void insertList(LinkList *list, LinkList q, int elem)
{
    LinkList p;
    p = (LinkList)malloc(sizeof(LNode));
    if (!p)
    {
        return ;
    }
    p->data = elem;
    if (!*list)
    {   //如果首结点为空
       *list = p;
       p->next == NULL; 
    }
    else
    {   //向后插入
        p->next = q->next;
        q->next = p;
    }
}

//基于链表冒泡排序
void bubbleSort(LinkList list)
{
    LinkList p = list;
    int temp, i, j, k = 0;

    while (p)
    {
        k++;
        p = p->next;
    }//k为链表元素个数

    p = list;
    for (i = 0; i < k - 1; i++)
    {
        for (j = 0; j < k - 1 - i; j++)
        {
            if (p->data > p->next->data)
            {   //与下一个位置进行比较
                temp = p->data;
                p->data = p->next->data;
                p->next->data = temp;
            }
            p = p->next;
        }
        p = list;//指针重新指向开头
    }
}

//打印出排序后的新链表
void print(LinkList list)
{
    while (list)
    {
        printf("%d ", list->data);
        list = list->next;
    }
}

int main(int argc, char const *argv[])
{
    LinkList q, r;
    int elem;

    q = r = creatList(1);//创建一个链表结点，q和r都指向这个结点

    scanf("%d", &elem);
    while (elem)
    {   //循环输入数据同时插入结点
        insertList(&q, r, elem);
        r = r->next;
        scanf("%d", &elem);
    }

    bubbleSort(q);
    print(q);

    system("pause");
    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

在原表空间上实现归并

有两个按元素值递增的有序排列的链表list1和list2，现需要将两个链表合并一个按元素值递增的有序链表list3。要求利用原表空间的结点空间构造新表。

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

typedef struct node
{
    int data;
    struct node *next;
}LNode, *LinkList;

//创建一个长度为n的链表
LinkList creatLinkList(int n)
{
    LinkList p, r, list = NULL;
    int elem, i;

    for (i = 0; i < n; i++)
    {
        scanf("%d", &elem);
        p = (LinkList)malloc(sizeof(LNode));
        if (!p)
        {
            return NULL;
        }
        p->data = elem;
        p->next = NULL;
        if (!list)
        {
            list = p;
        }
        else
        {
            r->next = p;
        }
    }
    return list;
}

//向链表中插入结点，并向该结点的数据域中存放数据
void insertList(LinkList *list, LinkList q, int elem)
{
    LinkList p;
    p = (LinkList)malloc(sizeof(LNode));
    p->data = elem;
    if (!p)
    {
        return ;
    }
    if (!*list)
    {
        *list = p;
        p = p->next;
    }
    else
    {
        p->next = q->next;
        q->next = p;
    }
}

//将p指向的结点插入到q1,q2所指向的结点当中
void insertNode(LinkList *q1, LinkList *q2, LinkList *p, LinkList *l2)
{
    if (*q1 == *q2)
    {   //l1链表第一个结点内容小于来l2链表第一个结点内容，特判
        (*p)->next = *q2;
        *l2 = *q2 = *q1 = *p;
    }
    else
    {
        (*q2)->next = *p;
        (*p)->next = *q1;
        (*q2) = (*q2)->next;
    }
}

//将l1,l2原空间有序归并，用l3返回
void mergeLink(LinkList l1, LinkList l2, LinkList *l3)
{
    LinkList p, q1, q2;
    q1 = q2 = l2;//q1, q2指向l2链表
    p = l1;//p指向l1链表
    while (p && q1)
    {
        if (p->data >= q1->data)
        { 
            q2 = q1;
            q1 = q1->next;
        }
        else
        {
            l1 = l1->next;
            insertNode(&q1, &q2, &p, &l2);
            p = l1;
        }
        /*
            p指向l1链表，q1,q2指向l2链表，q2始终在q1后一个位置
            比较p->data 和 q1->data ,
            1.如果p->data >= q1->data, q1,q2指向其下一个位置
            2.如果p->data < q1->data, 将p插入q1,q2之间
            直到某一链表为空结束
        */
    }
    if (!q1)
    {
        q2->next = p;
    }
    /*
        如果l1链表为空，那么l1已经完全插入合并到l2中
        如果l2链表为空，则讲l2尾指针指向l1连接
    */
    *l3 = l2;//l2首结点赋给l3
}

//打印链表
void print(LinkList list)
{
    while (list)
    {
        printf("%d ", list->data);
        list = list->next;
    }
}

int main(void)
{
    LinkList l1, l2, l3, q;
    int elem;

    //创建链表l1
    q = l1 = creatLinkList(1);
    scanf("%d", &elem);
    while(elem)
    {
        insertList(&l1, q, elem);
        q = q->next;
        scanf("%d", &elem);
    }

    //创建链表l2
    q = l2 = creatLinkList(1);
    scanf("%d", &elem);
    while(elem)
    {
        insertList(&l2, q, elem);
        q = q->next;
        scanf("%d", &elem);
    }

    //归并链表
    mergeLink(l1, l2, &l3);
    //打印合并链表
    print(l3);

    system("pause");
    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
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

约瑟夫环

编号1， 2， 3…n的n个人按顺时针方向坐一圈，每个人手中持有一个密码。开始时任选一个正整数作为报数的上限m，从第一个人开始按顺时针方向自1开始顺序表报数，报道m停止，报到m的人出列，将他手中的密码作为新的报数上限m，从顺时针方向上的下一个开始重新从1报数，如此报数下去，求最后剩下的那个人的最初编号是多少。
解决约瑟夫环问题，最关键的是要选取好存放数据的数据结构。最简单的方法是使用循环链表作为存储结构，通过链表的删除操作实现报数人的出列，通过对链表的循环遍历，实现顺时针报数。

#include <stdio.h>
#include <stdlib.h>
typedef struct node
{
    int number;//编号
    int psw;//个人密码
    struct node *next;
}LNode, *LinkLisk;

//向链表list中q指向结点后面插入一个新结点
void insertList(LinkLisk *list, LinkLisk q, int data1, int data2)
{
    LinkLisk p;
    p = (LinkLisk)malloc(sizeof(LNode));
    p->number = data1;
    p->psw = data2;
    if(!*list)
    {
        *list = p;
    }
    else
    {
        p->next = q->next;
        q->next = p;
    }   
}

//创建一个约瑟夫环
void creatJoseph(LinkLisk *jsp, int n)
{   
    LinkLisk q = NULL, list = NULL;
    int i, elem;
    
    for (i = 0; i < n; i++)
    {
        scanf("%d", &elem);
        insertList(&list, q, i + 1, elem);//向q指向的结点后插入新的结点
        if (i == 0)
        {
            q = list;
        }
        else
        {
            q = q->next;
        }
    }
    q->next = list;//形成循环链表
    *jsp = list;
}

//
void exJosph(LinkLisk *jsp, int m)
{
    LinkLisk p, q;
    int i;

    p = q = *jsp;
    while (q->next != p)
    {
        q = q->next;//q指向p的前一个结点
    }
    while (p->next != p)
    {
        for (i = 0; i < m - 1; i++)
        {   //p指向要删除的结点，q指向删除结点的前一个结点
            q = p;
            p = p->next;
        }
        q->next = p->next;//删除p指向的结点
        printf("%d ", p->number);//输出出列的数
        m = p->psw;//重置报数上限
        free(p);//释放p指向的结点
        p = q->next;//p指向q的后一个结点
    }
    printf("\nThe last person in the cicrle is %d\n", p->number);
}

int main(void)
{
    LinkLisk jsp;
    int n, m;


    scanf("%d", &n);//输入约瑟夫环人数
    creatJoseph(&jsp, n);


    scanf("%d", &m);//输入约瑟夫环报数上限
    exJosph(&jsp, m);

    system("pause");
    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

二进制/八进制转化器

要求从终端输入一串0/1表示的二进制数，用来表示它的八进制表示形式。
进制转化这类运算最简单的办法是使用栈的数据结构，从栈A顶取数每取出3位，转换成一个对应的八进制数，存到新栈B。

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef struct 
{
    char *base;
    char *top;
    int stacksize;
    /* data */
}Stack;

//初始化栈
void initStack(Stack *s)
{
    //内存中开辟一段连续空间作为栈空间
    s->base = (char*)malloc(STACK_INIT_SIZE * sizeof(char));
    if (!s->base)
    {
        exit(0);
    }
    s->top = s->base;
    s->stacksize = STACK_INIT_SIZE;
}

//入栈操作
void push(Stack *s, char elem)
{
    if (s->top - s->base >= STACK_INIT_SIZE)
    {   //栈满追加空间
        s->base = (char*)realloc(s->base, sizeof(char) * (STACK_INIT_SIZE + STACKINCREMENT));
        if (!s->base)
        {
            exit(0);
        }
        s->top = s->base + s->stacksize;
        s->stacksize += STACKINCREMENT;
    }
    *(s->top++) = elem;
}

//出栈操作
void pop(Stack *s, char *elem)
{
    if (s->top == s->base)
    {
        return;
    }
    *elem = *--(s->top);
}

//返回栈s的当前长度
int stackLen(Stack s)
{
    return (s.top - s.base);
}

//销毁栈
void destoryStack(Stack *s)
{
	free(s->base);
	free(s->top);
	s->base = NULL;
	s->top = NULL;
}
int main(void)
{
    Stack a, b;
    char ch;
    int len = stackLen(a);
    int i, j, sum = 0;
    char elem;


    initStack(&a);//创建一个栈用来存2进制字符串
    scanf("%c", &ch);
    while (ch != '#')
    {
        if (ch == '0' || ch == '1')
        {
            push(&a, ch);
        }
        scanf("%c", &ch);
    }

    initStack(&b);//创建一个栈用来存放8进制字符串
    for (i = 0; i < len; i += 3)
    {
        for (j = 0; j < 3; j++)
        {
            pop(&a, &elem);
            sum += (elem - 48) * pow(2, j);
            if (a.base == a.top)
            {
                break;
            }
        }
        push(&b, sum + 48);
        sum = 0;
    }

    while (b.base != b.top)
    {
        pop(&b, &ch);
        printf("%c", ch);
    }

    system("pause");
    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

回文字符串

有一种字符序列正读和反读都相同，这种字符序列成为“回文”。从键盘输入一个任意长度的字符串，以#作为结束标志，判断是否是回文。
思路：在输入字符序列时，把输入的字符存到栈和队列中。
重复取栈数据和队列数据，进行比较重复len/2次。

#pragma once
#include <stdlib.h>
#include <stdio.h>
#define STACK_INIT_SIZE 20
#define STACKINCREMENT 10
typedef struct 
{
    char *base;
    char *top;
    int stackSize;
}Stack;
void initStack(Stack *s)
{
    s->base = (char*)malloc(sizeof(char) * STACK_INIT_SIZE);
    if (!s->base)
    {
        return;
    }
    s->top = s->base;
    s->stackSize = STACK_INIT_SIZE;
}
void push(Stack *s, char elem)
{
    if (s->top - s->base >= s->stackSize)
    {
        s->base = (char*)realloc(s->base, sizeof(char) * (STACK_INIT_SIZE + STACKINCREMENT));
        if (!s->base)
        {
            return;
        }
        s->top = s->base + STACK_INIT_SIZE;
        s->stackSize += STACKINCREMENT;
    }
    *(s->top++) = elem;
}
void pop(Stack *s, char *elem)
{
    if (s->top == s->base)
    {
        return;
    }
    *elem = *(--s->top);
}
void destoryStack(Stack *s)
{
	free(s->base);
	free(s->top);
	s->base = NULL;
	s->top = NULL;
}

int stackLen(Stack s)
{
    return s.top - s.base;
}




#pragma once
#include <stdlib.h>
#include <stdio.h>
#define QUEUE_INIT_SIZE 20
#define QUEUEINCREMENT 10
typedef struct queue
{
    char *buffer;
    int top;
    int count;
    int queueSize;
}Queue, *QueuePtr;

void initQueue(QueuePtr p)
{
    p->buffer = (char*)malloc(sizeof(char) * QUEUE_INIT_SIZE);
    if (!p->buffer)
    {
        exit(0);
    }
    p->top = 0;
    p->count = 0;
    p->queueSize = QUEUE_INIT_SIZE;
}

void enQueue(QueuePtr p, char elem)
{
    if (p->count == p->queueSize)
    {
        p->buffer = (char*)realloc(p->buffer, sizeof(char) * (QUEUE_INIT_SIZE + QUEUEINCREMENT));
        p->queueSize += QUEUEINCREMENT;
    }
    p->buffer[p->count++] = elem;
}

void deQueue(QueuePtr p, char *elem)
{
    if (p->count == 0)
    {
        return ;
    }
    *elem = p->buffer[p->top++];
}




#include "Stack.h"
#include "Queue.h"

int main(void)
{
    Queue q;
    Stack s;
    initQueue(&q);
    initStack(&s);
    char ch;
    scanf("%c", &ch);
    while(ch != '#')
    {
        push(&s, ch);
        enQueue(&q, ch);
        scanf("%c", &ch);
    }

    int len = stackLen(s);

    int i;
    char a, b;
    int flag = 0;
    for (i = 0; i < len / 2; i++)
    {
        pop(&s, &a);
        deQueue(&q, &b);
        if (a != b)
        {
            flag = 1;
            break;
        }
    }
    if (flag)
    {
        printf("It is not a circle string!\n");
    }
    else
    {
        printf("It is a circle string!\n");
    }
    system("pause");
    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
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