作者在 2008-10-12 10:54:44 发布以下内容
顺序存储结构的弱点：在作插入或删除操作时，需移动大量元素。
链式存储结构没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。
1.单链表的存储实现
typedfed struct LNode
{elemtype data;
struct LNode *next;
}LNode,*linklist; //linklist为线性表的类型
2.单链表的新建、插入、删除
（1）单链表的建立（头插法）
// - - - - - - 头插法 - - - - - - -
linklsit Creat(linklist &L) // 逆位序输入n个元素的值,建立带表头结点的单链线性表L
{int node;linklist p;
L=(elemtype)malloc(sizeof(LNode));
L->next=NULL; //建立带头节点的空链表
while(node！=0)
{p=(elemtype)malloc(sizeof(LNode)); //生成新节点
scanf("%6d",&node)； //输入元素，以零结束
node=p->data;
p->next=L->next;
L-next=p;} //插入表头
}
// - - - - - - 尾插法 - - - - - - -
linklsit Creat(linklist &L)
{int node;linklist p,q;
q=L; //q始终指向尾结点
L=(elemtype)malloc(sizeof(LNode));
L->next=NULL; //建立带头节点的空链表
while(node！=0)
{p=(elemtype)malloc(sizeof(LNode)); //生成新节点
scanf("%6d",&node)； //输入元素，以零结束
node=p->data;
q->next=p; //插入q后面
q=p;
q->next=NULL;
}
（2）在第i个元素前插入元素e
linklist Insert(linklist &L,int i,elentype x)
{int j;linklist p,s;
p=L;j=0;
while(p!=NULL&&j<i)
{p=p->next;j++;} //寻找第i-1个节点
if(p==NULL||j>=i)
return ERROR;
else{s=(elemtype)malloc(sizeof(LNode);) //生成新结点
s->data=x;
s->next=p->next;
p->next=s;} //插入元素x
return L;
}
（3）单链表删除第i个元素
liklsit delete(linklist &L,int i, elemtype &x)
{int j;liklsit p,q;
j=0;p=L;
while(p->next!=NULL&&j<i);
{p=p->next;j++;} //找到第i-1个元素
if(p->next==NULL||j>=i)
return ERROR;
else{q=p->next; //删除第i个元素
p->next=q->next;
x=q->data;
free(q);}
return L;}
3.函数Getelem
Getelem(linklist L,int i,elemtype &e)
{int j;linklist p;
j=1;p=L->next;
while(p==NULL&&j<i)
{p=p->next;j++;} //顺指针找，直到p为空或第i个元素不存在
if(p!=NULL||j>i)rerurn ERROR; //第i个元素不存在
e=p->data;} //取第i个元素