انواع داده به‌زبان آدمیزاد

در برنامه‌نویسی، به روش‌های مختلفی که به‌کمک آنها می‌توان داده‌ها را ذخیره یا بازیابی کرد، یکی از اساسی‌ترین شرط‌های برنامه‌نویسی بهینه، استفاده بهینه از ساختمان‌های داده و انتخاب ساختمان داده از میان انواع موجود است. به‌طور کلی، ساختمان‌های داده به دو دسته تقسیم می‌شوند:‌

کد خبر: ۲۶۷۴۹۵

1- ایستا: که خود به دو دسته کوچک‌تر تقسیم می‌شود:

الف) اولیه: داده‌های صحیح، اعشاری، کاراکتری و ...

ب) غیراولیه (تعریف شده توسط کاربر): آرایه رشته1، رکورد، کلاس و ...

2- نیمه ایستا: پشته2 و صف3

3- پویا: که به دو نوع خطی (لیست‌های پیوندی4) و غیرخطی (انواع درخت5 و گراف6) تقسیم می‌شود.

داده‌های ایستا7، جزو ثابت دروس برنامه‌نویسی‌اند، اما داده‌های پویا8 معمولا در دوره‌های برنامه‌نویسی تدریس نمی‌شوند و بهتر است آنها را دوباره بررسی کنیم. نخست بهتر است نگاهی به داده‌های پویای خطی بپردازیم.

لیست پیوندی، برای ذخیره سازی مجموعه‌ای از داده ساده‌ترین روش استفاده از آرایه است. ولی این روش با مزایا و معایبی همراه است، اولین عیب آن حافظه‌ای است که اشغال می‌کند، مثلا اگر آرایه‌ای به طول 10 تعریف کنیم و 2 عنصر را در آن قرار دهیم 8 خانه باقی بلا استفاده می‌ماند، و حافظه آنها همچنان رزرو شده است (حافظه هرز داریم).

یک راه‌حل برای حل این مشکل استفاده از لیست پیوندی است. لیست پیوندی، لیستی از داده‌ها است که به وسیله اشاره‌گر به‌هم متصل‌اند. مزیت این روش در حافظه نسبت به استفاده از آرایه این است که اگر 2 دو عنصر به آن افزوده شود، به اندازه همان دو عنصر فضا اشغال می‌کند.

مزیت دیگر این است که چون عناصر آرایه در حافظه پشت سرهم هستند در هنگام تعریف ممکن است آن مقدار خانه پشت سر هم موجود نباشد و خطای منطقی رخ دهد. اما در لیست پیوندی عناصر الزاما پشت سر هم نیستند. یکی از معایب لیست پیوندی نسبت به آرایه پیاده‌سازی پیچیده‌تر آن در مقابل آرایه‌ها است. لیست پیوندی چندین نوع دارد: یک طرفه، یک‌طرفه چرخشی، دو طرفه و دوطرفه چرخشی. در این مقاله فقط به یک نوع آن یعنی لیست پیوندی یک طرفه بدون حلقه می‌پردازیم. بقیه لیست‌های پیوندی با کمی تغییرات جزئی، مشابه همدیگرند. لیست پیوندی را با ساختاری به‌شکل زیر تعریف می‌کنند:

typedef struct Node{

int Data;

struct Node* Next;

}List;

در ساختار ساده بالا، لیستی پیوندی با یک عنصر داده و یک عنصر اشاره‌گر با نام Next وجود دارد. حال، می‌توان همانند عملیات پایه‌ که عناصر داده‌ای پایه با خود دارند، روی این ساختمان داده نیز عملیات ساده و پیچیده‌ای تعریف کرد. بنابراین از ساده‌ترین عملیات روی لیست آغاز می‌کنیم:

درج و حذف در لیست

برای عملیات درج به این صورت عمل می‌کنیم، اولین عنصر را گرفته سپس یک متغییر از نوع List می‌سازیم و مقدار Next آنرا برابر null قرار می‌دهیم (برای این‌که آخرین عنصر است)، سپس مقدار Next اولین عنصر لیست را برابر آدرس متغییر ساخته شده قرار می‌دهیم، به این صورت:

List *list_add(List **p, int i){

List *n = (List *) malloc(sizeof(List));

if (n == NULL)

return NULL;

n->Next = *p;

*p = n;

n->Data = i;

return *p;

}

حذف از لیست نیز درست شبیه به همین عملیات است. مثلا اگر بخواهیم عنصر دهم را حذف کنیم، باید آدرس اولین عنصر در لیست را (که معمولا نام لیست به آن اشاره می‌کند) پیدا کنیم و تا نهمین خانه به پیش برویم. در این‌جا باید اشاره‌گر جدیدی را به خانه بعدی عنصر محذوف ایجاد کنیم. سپس عنصر را حذف کنیم، و محل اشاره عنصر نهم را برابر اشاره‌گر جدید قرار دهیم. به‌این تکه کدها نگاهی بیاندازید:

List **list_search(List **n, int i){

while (*n != NULL){

if ((*n)->Data == i)

{

return n;

}

n = &(*n)->Next;

}

return NULL;

}

void list_remove(List **p){

if (*p != NULL)

{

List *n = *p;

*p = (*p)->Next;

free(n);

}

داده‌های نیمه ایستا

از انواع داده‌های نیمه‌ایستا، می‌توان به ساختمان داده‌ای به نام پشته اشاره کرد. این ساختمان داده از یک قانون خاص تبعیت می‌کند: آخرین عنصری که وارد شود، اولین عنصری خواهد بود که از پشته خارج خواهد شد. به این قانون LIFO1 می‌گویند. پشته‌ها، مثل ستونی از بشقاب‌ها هستند، همواره بشقاب بالایی برداشته می‌شود و اگر بخواهد چیزی اضافه شود، روی بشقاب بالایی قرار خواهد گرفت.

پیاده‌سازی پشته‌ها

پشته‌ها را با دو روش پیاده‌سازی می‌کنند، روش اول با استفاده از آرایه و روش دیگر با استفاده از لیست پیوندی (که در آخر این روش را بیان می‌کنیم) در روش اول یک ساختار داده که شامل یک آرایه به‌طول N که تعداد عناصر پشته را مشخص می کند، می‌سازیم و یک متغییر از نوع صحیح که اندیس عنصر بالای پشته (اندیس خانه بالای پشته) را در خود نگه می‌دارد، این ساختار به‌صورت زیر پیاده‌سازی می‌شود:

#define STACKSIZE 10

typedef struct{

int top;

int items[STACKSIZE];

}STACK;

عملیات روی پشته

با توجه به مطالب گفته شده، شرط خالی بودن پشته زمانی است که مقدار Top برابر 0 باشد، و شرط پر بودن پشته این است که مقدار Top از مقدار STACKSIZE یک واحد کمتر باشد. برای درج در پشته، نخست باید از وجود جای خالی در پشته مطمئن شد. اگر پشته خالی بود، در این صورت مقدار Top را یکی زیاد کرده و سپس عنصر را در آرایه قرار می‌دهیم. به تکه کد زیر توجه کنید:

void push(int x, STACK *ps)

{

if(ps->top == STACKSIZE-1){

printf("Stack is full");

exit(EXIT_FAILURE);

}

else

ps->items[++(ps->top)] = x;

}

در دستور بالا، اگر پشته پر بود، پیغام Stack is full صادر می‌شود، در غیراین‌صورت، عملیات درج انجام می‌پذیرد. با استفاده از شرایط گفته شده عمل حذف را نیز انجام می‌دهیم، اگه پشته خالی باشد عمل حذف انجام نمی‌گیرد (داده‌ای برای حذف وجود ندارد)، پس شرط انجام حذف از پشته زمانی است که پشته حداقل یک عنصر داخلش داشته باشد، برای عمل حذف بر خلاف عمل درج رفتار می‌کنیم. ابتدا عنصر بالایی را حذف کرده و سپس یک واحد از Top کم می‌کنیم، به این صورت:

int pop(STACK *ps){

if(empty(ps)){

printf("Stack is empty");

exit(EXIT_FAILURE);

}

else

return(ps->items[(ps->top)--]);

}

مرتبه زمانی دو عمل فوق برابر O(1) است.

پیاده‌سازی پشته با لیست پیوندی

در این روش به‌جای ساختار تعریف شده برای پشته که در بالا توضیح داده شد، از ساختار لیست پیوندی با یک تغییر کوچک استفاده می‌کنیم به این صورت:

struct Node{

int info;

struct Node *Next;

}*Top=NULL;

همانطوری که مشاهده می‌کنید در این ساختار یک متغییر به اسم Top با مقدار اولیه Null تعریف کرده‌ایم، این متغییر آدرس عنصر بالای پشته را در خود نگه می‌دارد. عملیات درج و حذف در این نوع پشته مانند لیست پیوندی است، و فقط باید هنگام درج و حذف مقدار متغییر Top را نیز تنظیم کرد، مرتبه اجرایی مانند لیست پیوندی از مرتبه O(1) است، این عمل بصورت زیر انجام می‌شود.

void push(int data){

Node *tmp;

tmp = (Node *)malloc(sizeof(Node));

tmp->Data=data;

tmp->Next=top;

Top=tmp;

}

برای حذف از پشته نیز باز مانند لیست پیوندی انجام می‌شود و در حذف نیز باید اشاره گر Top را نیز تنظیم نمود که این عمل نیز از مرتبه O(1) است، این عمل بصورت زیر است:

void pop(){

struct Node *tmp;

if(Top == NULL)

printf("Stack is empty\n");

else{

tmp=Top;

printf("Popped item is %d\n",tmp->Data);

Top=Top->Next;

free(tmp);

}

پی‌نوشت

1. Array