线性表的顺序存储：
优点：无须为表示表中元素的逻辑关系而额外的存储空间，可以快速的取表中任意位置的元素。
缺点：插入和删除操作需要转移大量元素，线性表的长度较大时，难以确定存储空间的容量， 造成存储空间的“碎片”。
线性表的链式存储：
为了表示每一个数据元素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++应用技术那就加入我们吧！