數據結構之線性表

一、概述

線性表的順序表示，特點是邏輯關系上相鄰的兩個元素物理位置上也相鄰，這種數據結構的優點是可以隨機讀取表中的任意元素；缺點是做插入或者刪除時，需要移動大量的元素。

與之相對的鏈式表示，不要求邏輯上相連的元素物理位置也相鄰，每個元素除了存儲其本身的數據之外，還存儲了一個指示其后繼元素位置的信息。因此在插入和刪除時，不需要移動大量的元素，但是也不支持隨機讀取表中的任意元素。

二、線性鏈表的實現

#include?<stdio.h>

typedef?struct?Node?{
????int?data;
????struct?Node?*?next;
}?Node;

int?initLinkList(Node?*node)?{
????node->data?=?0;
????node->next?=?NULL;
????return?0;
}
int?getLinkListLen(Node?*node)
{
????int?i?=?0;
????for?(i=0;?node->next?!=?NULL;?i++)?{
????????node?=?node?->?next;
????}
????return?i;
}
int?getLinkListElm(Node?*node,?int?num,?int?*?data)
{
????int?i?=?0;
????int?len;
????len?=?getLinkListLen(node);
????if?(num?>?len)?{
????????printf("the?number?exceed?link?list?lenth\n");
????????return?-1;
????}
????for?(i=0;?i<num;?i++)?{
????????node?=?node?->?next;
????}
????*data?=?node->data;
????return?0;
}
int?insertLinkList(Node?*node,?int?num,?int?*data)
{
????int?i?=?0;
????int?len;
????Node?*?newNode?=?(Node?*)malloc(sizeof(Node));
????newNode->data?=?*data;
????newNode->next?=?NULL;
????
????len?=?getLinkListLen(node);
????
????if?(num?>?len)?{
????????printf("the?number?exceed?link?list?lenth\n");
????????return?-1;
????}
????for?(i=0;?i<num;?i++)?{
????????node?=?node?->?next;
????}
????newNode->next?=?node->next;
????node->next?=?newNode;
????return?0;
}
int?delLinkList(Node?*node,?int?num)
{
????int?i?=?0;
????int?len?=?0;
????Node?*delNode?=?(Node?*)malloc(sizeof(Node));
????len?=?getLinkListLen(node);
????if?(num?>?len)?{
????????printf("the?number?exceed?link?list?lenth\n");
????????return?-1;
????}
????for?(i=0;?i<num-1;?i++)?{
????????node?=?node?->?next;
????}
????delNode?=?node->next;
????node?->?next?=?delNode?->?next;
????free(delNode);
????return?0;
}
void?printLinkList(Node?*node)
{
????int?i?=?0;
????for?(i=0;?node->next?!=?NULL;?i++)?{
????????printf("%d?",?node->next->data);
????????node?=?node->next;
????}
????printf("\n");
}

int?main(int?argc,?char?argv[])
{
????testInsertLinkList();
????testDelLinkList();
????testGetLinkListElm();
????return?0;
}

void?testInsertLinkList()
{
????Node?*node?=?(Node?*)malloc(sizeof(Node));
????initLinkList(node);
????int?num?=?8;
????insertLinkList(node,?0,?&num);
????printf("the?link?list?should?be:?8,?and?it?is:?");
????printLinkList(node);
????num?=?9;
????insertLinkList(node,?0,?&num);
????printf("the?link?list?should?be:?9?8,?and?it?is:?");
????printLinkList(node);
????num?=?1;
????insertLinkList(node,?2,?&num);
????printf("the?link?list?should?be:?9?8?1,?and?it?is:?");
????printLinkList(node);
}
void?testDelLinkList()
{
????Node?*node?=?(Node?*)malloc(sizeof(Node));
????initLinkList(node);
????int?num?=?8;
????insertLinkList(node,?0,?&num);
????num??=?9;
????insertLinkList(node,?0,?&num);
????num?=?122;
????insertLinkList(node,?1,?&num);
????printf("the?link?list?should?be:?9?122?8,?and?it?is:?");
????printLinkList(node);
????delLinkList(node,?1);
????printf("the?link?list?should?be:?122?8,?and?it?is:?");
????printLinkList(node);
????
}
void?testGetLinkListElm()
{
????int?data?=?0;
????Node?*node?=?(Node?*)malloc(sizeof(Node));
????initLinkList(node);
????int?num?=?8;
????insertLinkList(node,?0,?&num);
????getLinkListElm(node,?1,?&data);
????printf("data?should?be?8,?and?it?is:?%d\n",?data);
????num?=?9;
????insertLinkList(node,?1,?&num);
????num?=?10;
????insertLinkList(node,?2,?&num);
????getLinkListElm(node,?3,?&data);
????printf("data?should?be?10,?and?it?is:?%d\n",?data);
}