數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)存儲(chǔ)、組織數(shù)據(jù)的方式今野。數(shù)據(jù)結(jié)構(gòu)是指相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合葡公。通常情況下，精心選擇的數(shù)據(jù)結(jié)構(gòu)可以帶來(lái)更高的運(yùn)行或者存儲(chǔ)效率条霜。數(shù)據(jù)結(jié)構(gòu)往往同高效的檢索算法和索引技術(shù)有關(guān)催什。
希望大家喜歡，點(diǎn)贊哦
鏈表的實(shí)現(xiàn)：
鏈表list.h 接口頭文件
/* list.h -- 簡(jiǎn)單列表類(lèi)型的頭文件 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* C99 特性 */
//需要保存的數(shù)據(jù)類(lèi)型
struct data_type
{
char c;
int i;
//寫(xiě)出想要表示的數(shù)據(jù)即可宰睡。蒲凶。。
}
//一般類(lèi)型定義
typedef struct data_type Item;
/*在鏈表的實(shí)現(xiàn)中拆内，每一個(gè)鏈接被稱(chēng)為一個(gè)節(jié)點(diǎn)（node）旋圆。每個(gè)節(jié)點(diǎn)包含形成列表內(nèi)容的信息和指向下一節(jié)點(diǎn)的指針*/
typedef struct node
{
Item item;
struct node * next;
} Node;
//為了管理列表，需要一個(gè)指向其開(kāi)始處的指針
typedef Node * List;
/* 函數(shù)原型 */
/* 操作：初始化一個(gè)列表： */
void InitializeList(List * plist);
/* 操作：確定列表是否為空列表 */
bool ListIsEmpty(const List *plist);
/* 操作：確定列表是否已滿(mǎn) */
bool ListIsFull(const List *plist);
/* 操作：確定列表中項(xiàng)目的個(gè)數(shù) */
unsigned int ListItemCount(const List *plist);
/* 操作：在列表尾部添加一個(gè)項(xiàng)目 */
bool AddItem(Item item, List * plist);
/* 操作：把一個(gè)函數(shù)作用于列表的每個(gè)項(xiàng)目 */
void Traverse (const List *plist, void (* pfun)(Item item) );
/* 操作：釋放已分配的內(nèi)存（如果有） */
void EmptyTheList(List * plist);
#endif
list.c 實(shí)現(xiàn)文件
/* list.c -- 支持列表操作的功能 */
#include <stdio.h>
#include <stdlib.h>
#include "list.h"
/* 局部函數(shù)原型 */
static void CopyToNode(Item item, Node * pnode);
/* 接口函數(shù) */
/* 初始化一個(gè)列表 */
void InitializeList(List * plist)
{
* plist = NULL;
}
/* 如果列表為空則返回真 */
bool ListIsEmpty(const List * plist)
{
if (*plist == NULL)
return true;
else
return false;
}
/* 如果列表已滿(mǎn)則返回真 */
bool ListIsFull(const List * plist)
{
Node * pt;
bool full;
pt = (Node *) malloc(sizeof(Node));
if (pt == NULL)
full = true;
else
full = false;
free(pt);
return full;
}
/* 返回節(jié)點(diǎn)數(shù) */
unsigned int ListItemCount(const List * plist)
{
unsigned int count = 0;
Node * pnode = *plist; /* set to start of list */
while (pnode != NULL)
{
++count;
pnode = pnode->next; /* set to next node */
}
return count;
}
/* 創(chuàng)建存放項(xiàng)目的節(jié)點(diǎn)麸恍，并把它添加到有plist指向的列表尾部 */
bool AddItem(Item item, List * plist)
{
Node * pnew;
Node * scan = *plist;
pnew = (Node *) malloc(sizeof(Node));
if (pnew == NULL)
return false; /* quit function on failure */
CopyToNode(item, pnew);
pnew->next = NULL;
if (scan == NULL) /* empty list, so place */
*plist = pnew; /* pnew at head of list */
else
{
while (scan->next != NULL)
scan = scan->next; /* find end of list */
scan->next = pnew; /* add pnew to end */
}
return true;
}
/* 訪問(wèn)每個(gè)節(jié)點(diǎn)并對(duì)他們分別執(zhí)行由pfun指向的函數(shù) */
void Traverse (const List * plist, void (* pfun)(Item item) )
{
Node * pnode = *plist; /* set to start of list */
while (pnode != NULL)
{
(*pfun)(pnode->item); /* apply function to item */
pnode = pnode->next; /* advance to next item */
}
}
/* 釋放由malloc（）分配的內(nèi)存灵巧，把列表指針設(shè)置為NULL */
void EmptyTheList(List * plist)
{
Node * psave;
while (*plist != NULL)
{
psave = (*plist)->next; /* save address of next node */
free(*plist); /* free current node */
*plist = psave; /* advance to next node */
}
}
/* 局部函數(shù)定義 */
/* 把一個(gè)項(xiàng)目復(fù)制到節(jié)點(diǎn)中 */
static void CopyToNode(Item item, Node * pnode)
{
pnode->item = item; /* structure copy */
}
棧的實(shí)現(xiàn)：
棧 stack.h 接口頭文件
#ifndef STACK_H_
#define STACK_H_
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode Stack;
int IsEmpty( Stack S );
Stack CreateStack( void );
void DisposeStack( Stack S );
void MakeEmpty( Stack S );
void Push( ElementType X, Stack S );
ElementType Top( Stack S );
void Pop( Stack S );
#endif
stack.c 實(shí)現(xiàn)文件
#include "stack.h"
#include "fatal.h"
struct Node
{
ElementType Element;
PtrToNode Next;
}
int IsEmpty( Stack S )
{
return S->Next ==NULL;
}
Stack CreateStack( void )
{
Stack S;
S=malloc (sizeof(struct Node));
if(S==NULL)
FatalError( "Out of space!!!" );
S->Next = NULL;
MakeEmpty(S);
return S;
}
void MakeEmpty( Stack S )
{
if (S==NULL)
Error( "Must use CreateStack first" );
else
while(!IsEmpty(S))
Pop(S);
}
void Stack (Stack S)
{
MakeEmpty(S);
free(S);
}
void Push( ElementType X, Stack S )
{
PtrToNode TmpCell;
TmpCell = malloc( sizeof( struct Node ) );
if( TmpCell == NULL )
FatalError( "Out of space!!!" );
else
{
TmpCell->Element = X;
TmpCell->Next = S->Next;
S->Next = TmpCell;
}
}
ElementType Top( Stack S )
{
if( !IsEmpty( S ) )
return S->Next->Element;
Error( "Empty stack" );
return 0; /* Return value used to avoid warning */
}
void Pop( Stack S )
{
PtrToNode FirstCell;
if( IsEmpty( S ) )
Error( "Empty stack" );
else
{
FirstCell = S->Next;
S->Next = S->Next->Next;
free( FirstCell );
}
}
隊(duì)列的實(shí)現(xiàn)：
隊(duì)列queue.h 接口頭文件
typedef int ElementType;
/* START: fig3_57.txt */
#ifndef _Queue_h
#define _Queue_h
struct QueueRecord;
typedef struct QueueRecord *Queue;
int IsEmpty( Queue Q );
int IsFull( Queue Q );
Queue CreateQueue( int MaxElements );
void DisposeQueue( Queue Q );
void MakeEmpty( Queue Q );
void Enqueue( ElementType X, Queue Q );
ElementType Front( Queue Q );
void Dequeue( Queue Q );
ElementType FrontAndDequeue( Queue Q );
#endif /* _Queue_h */
/* END */
queue.c 實(shí)現(xiàn)文件
#include "queue.h"
#include "fatal.h"
#include <stdlib.h>
#define MinQueueSize ( 5 )
struct QueueRecord
{
int Capacity;
int Front;
int Rear;
int Size;
ElementType *Array;
};
/* START: fig3_58.txt */
int
IsEmpty( Queue Q )
{
return Q->Size == 0;
}
/* END */
int
IsFull( Queue Q )
{
return Q->Size == Q->Capacity;
}
Queue
CreateQueue( int MaxElements )
{
Queue Q;
/* 1*/ if( MaxElements < MinQueueSize )
/* 2*/ Error( "Queue size is too small" );
/* 3*/ Q = malloc( sizeof( struct QueueRecord ) );
/* 4*/ if( Q == NULL )
/* 5*/ FatalError( "Out of space!!!" );
/* 6*/ Q->Array = malloc( sizeof( ElementType ) * MaxElements );
/* 7*/ if( Q->Array == NULL )
/* 8*/ FatalError( "Out of space!!!" );
/* 9*/ Q->Capacity = MaxElements;
/*10*/ MakeEmpty( Q );
/*11*/ return Q;
}
/* START: fig3_59.txt */
void
MakeEmpty( Queue Q )
{
Q->Size = 0;
Q->Front = 1;
Q->Rear = 0;
}
/* END */
void
DisposeQueue( Queue Q )
{
if( Q != NULL )
{
free( Q->Array );
free( Q );
}
}
/* START: fig3_60.txt */
static int
Succ( int Value, Queue Q )
{
if( ++Value == Q->Capacity )
Value = 0;
return Value;
}
void
Enqueue( ElementType X, Queue Q )
{
if( IsFull( Q ) )
Error( "Full queue" );
else
{
Q->Size++;
Q->Rear = Succ( Q->Rear, Q );
Q->Array[ Q->Rear ] = X;
}
}
/* END */
ElementType
Front( Queue Q )
{
if( !IsEmpty( Q ) )
return Q->Array[ Q->Front ];
Error( "Empty queue" );
return 0; /* Return value used to avoid warning */
}
void
Dequeue( Queue Q )
{
if( IsEmpty( Q ) )
Error( "Empty queue" );
else
{
Q->Size--;
Q->Front = Succ( Q->Front, Q );
}
}
ElementType
FrontAndDequeue( Queue Q )
{
ElementType X = 0;
if( IsEmpty( Q ) )
Error( "Empty queue" );
else
{
Q->Size--;
X = Q->Array[ Q->Front ];
Q->Front = Succ( Q->Front, Q );
}
return X;
}
希望大家喜歡，點(diǎn)贊哦
