数据结构算法实现(线性结构)

下面是我自己实现的代码,编译器通过了,结果也是对的,但是没准也会有错误存在。

单链表

*************************************************************************
    > File Name: list.c
    > Author: 孟超
    > Mail: 2205101365@qq.com 
    > Created Time: 2019年09月03日 星期二 23时39分13秒
 ************************************************************************/

#include<stdio.h>
#include<malloc.h>

typedef struct _Node
{
    int data;
    struct _Node * next;
}Node;

//创建空链表,带有头结点,head是头指针,生成的是头结点
Node *createList()
{
    Node *head = (Node *)malloc(sizeof(Node));
    head->next = NULL;
    return head;
    
}

//插入操作
void insertList(Node* head , int data)
{
    Node *cur = (Node*)malloc(sizeof(Node));
    cur->data = data;
    cur->next = head->next;
    head->next = cur;
}

//遍历
void travereList(Node *head)
{
    head = head ->next;
    while(head)    
    {
        printf("%d\n",head->data);
        head = head ->next;
    }
}    

int lenList(Node* head)
{
    int count = 0;        
    head = head ->next;
    while(head)    
    {
        count++;
        head = head ->next;
    }
    return count;
}

Node *searchList(Node*head,int find)
{
    head = head -> next;
    while(head)
    {
        if(head->data == find)
        {
                break;
        }
        head = head -> next;
    }
    return head;
}

//删除节点
void deleteList(Node *head , Node *pfind)
{
    while(head -> next != pfind)    
    {
        head = head -> next;    
    }
    head -> next = pfind -> next;
    free(pfind);
}

//排序
void popSortList(Node *head)
{
    Node *p,*q;
    int len = lenList(head);
    for(int i = 0;i< len-1;i++)
    {
        p = head -> next;
        q = p -> next; 
        for(int j = 0;j<len-1-i;j++)
        {
            if(p->data > q->data)
            {
                p->data ^= q->data;        
                q->data ^= p->data;        
                p->data ^= q->data;        
            }
            p = p->next;
            q = p->next;
        }
    }

}

//逆转链表,思想就是将链表拆分
void reverseList(Node *head)
{
    Node *h = head -> next;
    head->next = NULL;
    Node *t;
    while(h)    
    {
            t = h->next;
            h->next = head ->next;
            head->next = h;
            h = t;
    }
}

//销毁链表
void destoryList(Node *head)
{
    Node *t;
    while(head)
    {
        t = head->next;
        free(head);
        head = t;
    }

}

int main()
{
    Node *head = createList();    
    insertList(head,4);
    insertList(head,1);
    insertList(head,9);
    insertList(head,7);
    insertList(head,11);
    popSortList(head);
    reverseList(head);
    travereList(head);
    int count = lenList(head); 
    printf("%d\n",count);
    destoryList(head);
    return 0;
}

线性栈

栈可以用于深度优先搜索

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

typedef struct  stack
{
    int len;
    int top;
    char *_space;
}stack;

void initStack(stack *s , int size)
{
    s->len = size;
    s->top = 0;
    s->_space = (char *)malloc(s->len);
}

int isEmpty(stack *s)
{
    return s->top == 0;
}

int isFull(stack *s)
{
    return s->top == s->len;
}

void push(stack *s,char ch)
{
    s->_space[s->top++] = ch;
}

char pop(stack *s)
{
    return s->_space[--s->top];
}

void resetStack(stack *s)
{
    s->top = 0;
}

void clearStack(stack *s)
{
    free(s->_space);
}


int main()
{
    stack s;
    initStack(&s,27);
    for(char i = 'A'; i != 'Z'+1; ++i)
    {
        push(&s,i);
    }
    while(!isEmpty(&s))
    {
            char c = pop(&s);
            printf("%c\n",c);
    }
    return 0;
}

链栈

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

typedef struct Node
{
    char data;
    struct Node *next;
}Node;

typedef struct stack
{
    Node *top;
}stack;

void initStack(stack *s)
{
    s->top = (Node*)malloc(sizeof (Node));
    s->top->next = NULL;
}

int isEmpty(stack *s)
{
    return s->top->next == NULL;
}

void push(stack *s,char ch)
{
    Node *cur = (Node*)malloc(sizeof (Node));
    cur->data = ch;

    cur->next = s->top->next;
    s->top->next = cur;
}

char pop(stack*s)
{
    Node *t = s->top->next;
    char ch = t->data;
    s->top->next = t->next;
    free(t);
    return ch;
}

int main()
{
    stack s;
    initStack(&s);
    for(char i = 'A'; i != 'Z'+1; ++i)
    {
        push(&s,i);
    }
    while(!isEmpty(&s))
    {
            char c = pop(&s);
            printf("%c\n",c);
    }
    return 0;
}

环形对列

队列可以用于广度优先搜索

#include <stdio.h>
#include<stdlib.h>
//front最开始指向空白待插入位置,rear指向有内容的待出队的位置
typedef struct _Queue
{
    char *_space;
    int _len;
    int _rear;
    int _front;
}Queue;

void initQueue(Queue *q,int size)
{
    q->_len = size;
    q->_space = (char *)malloc(sizeof(q->_len));
    q->_rear = q->_front = 0;
}

int isEmpty(Queue *q)
{
    return q->_front ==  q->_rear;
}

int isFull(Queue *q)
{
    return (q->_rear +1)%q->_len == q->_front;
}

void enQueue(Queue *q,char ch)
{
    q->_space[q->_rear] =ch;
    q->_rear = ++q->_rear %q->_len;
}

char deQueue(Queue *q)
{
    char ch = q->_space[q->_front];
    q->_front = ++q->_front %q->_len;
    return ch;
}

int main()
{
    Queue q;
    initQueue(&q,27);
    for(char i = 'A'; i < 'Z'+1; ++i)
    {
        enQueue(&q,i);
    }
    while(!isEmpty(&q))
    {
            char c = deQueue(&q);
            printf("%c\n",c);
    }
    return 0;
}

链队列

#include <stdio.h>
#include <stdlib.h>
struct QNode
{
    int data;
    struct QNode * next;
};
//链式存储中, 只放两个头尾指针
struct Queue
{
    struct QNode *front;
    struct QNode *rear;
};

void initQueue(struct Queue * q)
{
    q->rear = q->front =
            (struct QNode*)malloc(sizeof(struct QNode));
    q->rear->next = NULL;
}
int isQueueEmpty(struct Queue * q)
{
          return q->rear == q->front;
}
void enQueue(struct Queue * q,int dat)
{
    struct QNode * cur =
            (struct QNode *)malloc(sizeof(struct QNode));
            cur->data = dat;
            cur->next = q->rear->next;
            q->rear->next = cur;
            q->rear = cur;
}
int deQueue(struct Queue * q)
{
    if(q->front->next == q->rear)
    {
        //只有一个元素
        int t = q->front->next->data;
        q->front->next = q->front->next->next;
        free(q->rear);
        q->rear = q->front;
        return t;
    }
    else
    {
        //有多个元素
        int t = q->front->next->data;
        struct QNode* pdel = q->front->next;
        q->front->next = q->front->next->next;
        free(pdel);
        return t;
    }
}
void clearQueue(struct Queue *q)
{
    struct QNode * t = q->front;
    struct QNode * cur;
    while(t)
    {
        cur = t->next;
        free(t);
        t = cur;
    }
    q->front = q->rear = NULL;
}
int main()
{
    struct Queue q;
    initQueue(&q);
    for(int i=0; i<10; i++)
    {
        enQueue(&q,i);
    }
    while(!isQueueEmpty(&q))
    {
        printf("%d\n",deQueue(&q));
    }
    clearQueue(&q);
    return 0;
}
Last modification:October 6th, 2019 at 01:56 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment

One comment

  1. 232432214@qq.com Google Chrome 75.0.3770.100 Windows 10 中国 陕西 西安