1. 鏈表
? ? ? 記錄一下《數據結構與算法分析 - C語言描述》的第3章，表、棧和隊列，在這記錄一下哈^_^
? ? ??當釋放鏈表的的空間時，可以用free函數通知系統回收它，free(P)的結果是，P正在指向的地址沒變，但在該地址處的數據此時已無定義了。
//關于鏈表的定義
~~~
#ifndef LIST_H_INCLUDED
#define LIST_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
#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 <stdio.h>
#include <stdlib.h>
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 <stdio.h>
#include <stdlib.h>
#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 <stdio.h>
#include <stdlib.h>
#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;
}
~~~
