表、栈、队列 – 数据结构
最后更新于：2022-04-01 20:06:04
1. 链表
记录一下《数据结构与算法分析 - C语言描述》的第3章，表、栈和队列，在这记录一下哈^_^
当释放链表的的空间时，可以用free函数通知系统回收它，free(P)的结果是，P正在指向的地址没变，但在该地址处的数据此时已无定义了。
//关于链表的定义
~~~
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include
#include
typedef struct NODE Node;
typedef struct NODE *List;
typedef struct NODE *Position;
List Creat(void);
Position Find(int x, List L);
Position FindPre(int x, List L);
void Insert(int x, List L, Position p);
void Delete(int x, List L);
void DeleteList(List L);
void Show(List L);
struct NODE
{
int data;
struct NODE *next;
};
#endif
~~~
//关于链表功能函数的定义
~~~
#include "list.h"
List Creat(void)
{
List L;
L = (List)malloc(sizeof(Node));
if(L == NULL)
exit(-1);
L->next = NULL;
return L;
}
Position Find(int x, List L)
{
List p = L->next;
while(p->data != x && p != NULL)
p = p->next;
return p;
}
Position FindPre(int x, List L)
{
List p = L->next;
while(p->next->data != x && p->next != NULL)
p = p->next;
return p;
}
void Insert(int x, List L, Position p)
{
Position tmpp;
L = L;
tmpp = (Position)malloc(sizeof(Node));
if(tmpp == NULL)
exit(-1);
tmpp->data = x;
tmpp->next = p->next;
p->next = tmpp;
}
int IsLast(Position p, List L)
{
L = L;
return p->next == NULL;
}
void Delete(int x, List L)
{
Position p, tmpL;
p = FindPre(x, L);
if(!IsLast(p, L))
{
tmpL = p->next;
p->next = tmpL->next;
free(tmpL);
}
}
void DeleteList(List L)
{
Position p;
p = L;
while(p != NULL)
{
L = p->next;
free(p);
p = L;
}
}
void Show(List L)
{
Position p;
p = L->next;
while(p != NULL)
{
printf("%d ", p->data);
p = p->next;
}
putchar('\n');
}
~~~
//链表的测试主函数
~~~
#include
#include
#include "list.h"
//非递归的形式把一个链表翻转过来
List reverse(List L)
{
Position preNode = NULL;
Position nextNode = NULL;
L = L->next;
while(L != NULL)
{
nextNode = L->next;
L->next = preNode;
preNode = L;
L = nextNode;
}
return preNode;
}
//递归的形式把一个链表翻转过来
List reverse1(List L)
{
Position nextNode, reverseNode;
if(L == NULL || L->next == NULL)
return L;
nextNode = L->next;
L->next = NULL;
reverseNode = reverse1(nextNode);
nextNode->next = L;
return reverseNode;
}
int main(void)
{
List list;
list = Creat();
Insert(1, list, list);
Insert(2, list, Find(1, list));
Insert(3, list, Find(2, list));
Insert(4, list, Find(3, list));
Show(list);
//list->next = reverse1(list->next);
// Show(list);
DeleteList(list);
return 0;
}
~~~
2. 栈
栈的数组实现
//关于栈的定义
~~~
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include
#include
typedef struct stack
{
int Capacity;
int TopOfStack;
int *Array;
}Stack;
#define EmptyTOS (-1)
#define MinStackSize 5
Stack *StackCreat(int maxNum);
int IsEmpty(Stack *S);
int IsFull(Stack *S);
int Push(Stack *S, int x);
int Pop(Stack *S, int *x);
int ShowStack(Stack *S);
int FreeStack(Stack *S);
#endif // LIST_H_INCLUDED
~~~
//关于栈的功能函数的定义
~~~
#include "list.h"
Stack *StackCreat(int maxNum)
{
Stack *S;
if(maxNum < MinStackSize)
{
printf("the maxNum is low the MinStackSize\n");
return NULL;
}
S = (Stack *)malloc(sizeof(Stack));
if(S == NULL)
exit(-1);
S->Array = (int *)malloc(sizeof(int) * maxNum);
if(S->Array == NULL)
exit(-1);
S->Capacity = maxNum;
S->TopOfStack = EmptyTOS;
return S;
}
int IsEmpty(Stack *S)
{
return S->TopOfStack == EmptyTOS;
}
int IsFull(Stack *S)
{
return S->TopOfStack == (S->Capacity-1);
}
int Push(Stack *S, int x)
{
if(IsFull(S))
{
printf("the stack is full\n");
return 0;
}
else
S->Array[++S->TopOfStack] = x;
return 1;
}
int Pop(Stack *S, int *x)
{
if(IsEmpty(S))
{
return 0;
}
else
{
*x = S->Array[S->TopOfStack--];
return 1;
}
}
int ShowStack(Stack *S)
{
int x;
while(Pop(S, &x) != 0)
printf("%d ", x);
return 1;
}
int FreeStack(Stack *S)
{
free(S->Array);
free(S);
return 1;
}
~~~
//栈的测试主函数
~~~
#include "list.h"
int main()
{
Stack *S;
S = StackCreat(6);
Push(S, 6);
Push(S, 5);
Push(S, 4);
Push(S, 3);
Push(S, 2);
Push(S, 1);
Push(S, 10);
ShowStack(S);
printf("\n%d\n", S->TopOfStack);
if(FreeStack(S))
printf("Free Stack is ok\n");
return 0;
}
~~~
3. 队列
队列从尾部插入，从头部弹出数据。
//关于队列的定义
~~~
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include
#include
#define QUEUESIZE 10
typedef struct QueueRecord *Queue;
typedef int ElementType;
int IsEmpty(Queue Q);
void MakeEmpty(Queue Q);
Queue CreatQueue(void);
void Enqueue(int x, Queue Q);
int Outqueue(Queue Q);
int Delete(Queue Q);
struct QueueRecord
{
int Capacity;
int Front;
int Rear;
int Size;
ElementType *Array;
};
#endif // LIST_H_INCLUDED
~~~
//关于队列的功能函数定义
~~~
#include "list.h"
void Error(char *str)
{
fprintf(stderr, "%s\n", str);
exit(-1);
}
int IsEmpty(Queue Q)
{
return Q->Size == 0;
}
void MakeEmpty(Queue Q)
{
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;
}
Queue CreatQueue(void)
{
Queue Q;
Q = (Queue)malloc(sizeof(struct QueueRecord));
if(Q == NULL)
Error("No space");
Q->Array = (int *)malloc(QUEUESIZE * sizeof(int));
if(Q->Array == NULL)
Error("No space");
Q->Capacity = QUEUESIZE;
Q->Front = 0;
Q->Rear = 0;
Q->Size = 0;
return Q;
}
static int Succ(int Value, Queue Q)
{
if(++Value == Q->Capacity)
Value = 0;
return Value;
}
int IsFull(Queue Q)
{
return Q->Size == Q->Capacity;
}
void Enqueue(int x, Queue Q)
{
if(IsFull(Q))
{
Delete(Q);
Error("Full Queue");
}
else
{
Q->Size++;
Q->Array[Q->Rear] = x;
Q->Rear = Succ(Q->Rear, Q);
}
}
int Outqueue(Queue Q)
{
int x;
if(IsEmpty((Q)))
{
Delete(Q);
Error("Empty Queue");
}
else
{
Q->Size--;
x = Q->Array[Q->Front];
Q->Front = Succ(Q->Front, Q);
}
return x;
}
int Delete(Queue Q)
{
int *p;
p = Q->Array;
free(p);
free(Q);
printf("Free the queue is ok\n");
return 1;
}
~~~
//队列的测试主函数
~~~
#include
#include
#include "list.h"
int main(void)
{
Queue Q;
Q = CreatQueue();
Enqueue(1, Q);
Enqueue(2, Q);
Enqueue(3, Q);
Enqueue(4, Q);
Enqueue(5, Q);
Enqueue(6, Q);
Enqueue(7, Q);
Enqueue(8, Q);
Enqueue(9, Q);
Enqueue(10, Q);
printf("The queue has %d elements\n", Q->Size);
printf("%d\n", Outqueue(Q));
printf("%d\n", Outqueue(Q));
printf("%d\n", Outqueue(Q));
printf("%d\n", Outqueue(Q));
printf("%d\n", Outqueue(Q));
Delete(Q);
return 0;
}
~~~
';