データ構造問題の練習

シーケンステーブルのその場で逆置き
関数を記述し,シーケンステーブルのその場逆置きを実現する,すなわち,元のテーブルの記憶空間を利用してシーケンステーブル(a 1,a 2...an),逆置き(an,an-1...a 1)を実現する.

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

    //    

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

    reverseSQ(&l);//    

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

    system("pause");
    return 0;
}

動的数列ソート
キーボードから任意の整数を入力し、0を終了フラグとして、この整数シーケンスを小さいものから大きいものに並べ替え、並べ替え後の構造を出力する機能を実現します.

#include 
#include 

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

元の表領域で集計を実現
要素値で増加する2つの順序付けされたチェーンテーブルlist 1とlist 2があり、2つのチェーンテーブルを要素値で増加する順序付けされたチェーンテーブルlist 3にマージする必要があります.元の表空間のノード空間を利用して新しい表を構築する必要がある.

#include 
#include 

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...nのn人は時計回りに座り、一人一人がパスワードを持っている.最初は正の整数を1つの报数の上限mとして选んで、最初の人から时计回りに1から顺番に报数を表して、报道mは停止して、mに报いた人は列を出して、彼の手の中のパスワードを新しい报数の上限mとして、时计回りの方向の次の人から再び1报数から、このように报数して、最后に残ったあの人の最初の番号を求めます.ジョセフループの問題を解決するには、データを格納するデータ構造を選択することが最も重要です.最も簡単な方法は,循環チェーンテーブルを記憶構造として用い,チェーンテーブルの削除操作により新聞数人の列出しを実現し,チェーンテーブルの循環遍歴により時計回りの新聞数を実現することである.

#include 
#include 
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("
The last person in the cicrle is %d
", 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;
}

バイナリ/8進変換器
端末から0/1で表されるバイナリ数の列を入力し、その8進数で表される形式を表すことが要求される.進数変換という演算の最も簡単な方法は、スタックのデータ構造を用いて、スタックAのトップから3ビットずつ取り出し、対応する8進数に変換して、新しいスタックBに格納することである.

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

エコー文字列
正読みと逆読みが同じ文字シーケンスがあり、この文字シーケンスは「回文」になります.キーボードから任意の長さの文字列を入力し、#を終了フラグとして、返信かどうかを判断します.考え方:文字シーケンスを入力するときに、入力した文字をスタックとキューに保存します.スタックデータとキューデータを繰り返し、比較してlen/2回繰り返します.

#pragma once
#include 
#include 
#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 
#include 
#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!
");
    }
    else
    {
        printf("It is a circle string!
");
    }
    system("pause");
    return 0;
}