線性表的順序存儲：
優點：無須為表示表中元素的邏輯關系而額外的存儲空間，可以快速的取表中任意位置的元素。
缺點：插入和刪除操作需要轉移大量元素，線性表的長度較大時，難以確定存儲空間的容量， 造成存儲空間的“碎片”。
線性表的鏈式存儲：
為了表示每一個數據元素a1與其直接后級數據元素ai+1之間的邏輯關系，對數據元素a1來說，除了存儲其本身的信息之外，還需存儲一個指示其直接后繼的信號（即直接后繼的存儲位置）。存儲數據元素信息的域叫做數據域，把存儲直接后繼位置的域稱為指針域。指針域中存儲的信息稱為指針或鏈。這兩部分組成數據元素ai的存儲影像，稱為結點（Node）
其中頭指針和頭結點的區別：
1，頭指針是指向鏈表的個結點的指針，若鏈表有都結點，則指向頭結點的指針。頭指針具有標示作用，所以常用頭指針冠以鏈表的名字。無論鏈表是否為空，頭指針均不為空，頭指針是鏈表的必要條件。
2，頭結點是為了操作的統一和方便設置的，放在頭一個元素的結點之前，其數據域一般無意義。有了頭結點，對其在元素位置前插入刪除擦偶偶與其他結點的操作統一。頭結點不是鏈表的必須要素。
帶有頭結點的指針;
C語言中用結構指針表示結點：
typedef struct Node
{
int data;
struct Node *next;
}Node, *pNode,*LinkList;
其中單鏈表的抽象數據結構即操作有：
void InitList(LinkList *list);//初始化操作，建立空的單鏈表 void ClearList(LinkList *list);//清空單鏈表。 void ListInsert(LinkList *list,int i, int e);//單鏈表第i個位置后面插入變量e void DestoryList(LinkList *list);//銷毀鏈表 bool ListEmpty(LinkList list);//判斷單鏈表是否為空，為空返回真 void GetElem(LinkList, int &e, int i);//將單鏈表中第i個位置的值返回給變量e void ListDelete(LinkList *list, int i, int &e);//刪除單鏈表表第i個位置元素 void ListTraverse(LinkList list);//遍歷線性表 int ListLength(LinkList list);//返回線性表的長度 void Recursion(LinkList list);//遞歸逆序輸出單鏈表
各種函數的實現源代碼：
void InitList(LinkList *list)
{
*list = (LinkList)malloc(sizeof(Node));
(*list)->next = NULL;
(*list)->data = 0;
}
void ListInsert(LinkList *list, int i , int e)//第i個元素后面插入e
{
LinkList p = *list;
if( i == 0)
{
pNode q = (LinkList)malloc(sizeof(Node));
q->next = NULL;
q->data = e;
p->next = q;
}
else
{
pNode p = (*list)->next;
int j = 1;
while( p && i > j)
{
p = p->next;
++j;
}
pNode q = (LinkList)malloc(sizeof(Node));
q->next = p->next;
q->data = e;
p->next = q;
}
}
void ListTraverse(LinkList list)
{
pNode p = list;
if(p != NULL)
{
p = p->next;
}
else
{
return;
}
while(p)
{
printf("%dt", p->data);
p = p->next;
}
}
void Recursion(LinkList list)//遞歸的方法逆序輸出鏈表
{
if(NULL==list)
{
return;
}
if(list->next!=NULL)
{
Recursion(list->next);
}
printf("%dt",list->data);
}
bool ListEmpty(LinkList list)
{
pNode p = list;
if(NULL == list->next)
return true;
else
return false;
}
void GetElem(LinkList list, int &e, int i)
{
pNode p = list;
if( i < 0 || i > ListLength(list))
return ;
p = p->next;
int j = 1;
while( j < i)
{
p = p->next;
j++;
}
e = p->data;
}
void ListDelete(LinkList *list, int i, int &e)
{
pNode p = *list;
if( i < 0 || i > ListLength(*list))
return ;
pNode q = p;
p = q->next;
int j = 1;
while( j < i )
{ q = p;
p = p->next;
j++;
}
p->data = e;
q->next = p->next;
free(p);
}
int ListLength(LinkList list)
{
pNode p = list;
int i = 0;
p = p->next;
while(p)
{
p = p->next;
i++;
}
return i;
}
void ClearList (LinkList *list)
{
pNode p = *list;
if( p != NULL)
p = p->next;
pNode q;
while( p )
{
q = p;
p = p->next;
free(q);
}
}
void DestoryList(LinkList *list)
{
pNode p = *list;
if( p != NULL)
p = p->next;
pNode q;
while( p )
{
q = p;
p = p->next;
free(q);
}
free(*list);
}
測試函數源代碼：
int main()
{
LinkList list;
InitList(&list);
ListInsert(&list, 0, 1);
ListInsert(&list, 1, 2);
ListInsert(&list, 2, 3);
ListInsert(&list, 1, 4);
ListInsert(&list, 1, 5);
ListInsert(&list, 5, 6);
ListInsert(&list, 6, 7);
ListInsert(&list, 7, 8);
ListInsert(&list, 8, 9);
ListInsert(&list, 9, 10);
printf("n遞歸調用函數Reversion:n");
LinkList p = list->next;
Recursion(p);
printf("n遍歷鏈表ListTranverse:n");
ListTraverse(list);
int j = ListLength(list);
printf("n鏈表的長度ListLength：%dt",j);
int e;
GetElem(list, e, 3);
printf("取鏈表特定的元素GetElem : %dn",e);
ListDelete(&list, 1, e);
printf("n刪除鏈表中特定位置的元素:%dn", e);
ListTraverse(list);
ClearList (&list);
printf("n鏈表清空ClearList: n");
ListInsert(&list, 0, 1);
ListInsert(&list, 1, 2);
ListInsert(&list, 2, 3);
ListTraverse(list);
DestoryList(&list);
return 0;
}
想要了解更多的C++應用技術那就加入我們吧！