下面是我自己实现的代码，编译器通过了，结果也是对的，但是没准也会有错误存在。
单链表
*************************************************************************
> 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;
}版权属于：孟超
本文链接：https://mengchao.xyz/index.php/archives/215/
转载时须注明出处及本声明
One comment