【1】线性表的顺序存储结构有存储密度高及能够随机存取等优点,但存在以下不足:
(1)要求系统提供一片较大的连续存储空间。
(2)插入、删除等运算耗时,且存在元素在存储器中成片移动的现象;
【2】线性表的链式存储(单链表)的实现
typedef int datatype_t;
struct node
{
datatype_t data;
struct node *next;
};
int linklist_empty(struct node *ll)
{
return (ll->next==NULL)?1:0;
}
struct node *linklist_create()
{
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->next=NULL;
tmp->data=-1;
return tmp;
}
void linklist_insert_head(struct node *ll,datatype_t value)
{
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=value;
tmp->next=ll->next;
ll->next=tmp;
}
int linklist_insert_by_pos(struct node *ll,int pos,datatype_t value)
{
int cnt=0;
while(ll->next!=NULL)
{
if(cnt==pos)
{
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=value;
tmp->next=ll->next;
ll->next=tmp;
return 0;
}
cnt++;
ll=ll->next;
}
return -1;
}
void linklist_insert_tail(struct node *ll,datatype_t value)
{
while(ll->next!=NULL)
ll=ll->next;
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=value;
tmp->next=ll->next;
ll->next=tmp;
}
void linklist_insert_bt_sort(struct node *ll,datatype_t value)
{
while(ll->next!=NULL && ll->next->data<value)
ll=ll->next;
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=value;
tmp->next=ll->next;
ll->next=tmp;
}
datatype_t linklist_delete_head(struct node *ll)
{
if(linklist_empty(ll)==1)
{
return -1;
}
struct node *p=ll->next;
ll->next=p->next;
free(p);
p=NULL;
}
void linklist_reverse(struct node *ll)
{
struct node *p,*q;
p=ll->next;
ll->next=NULL;
while(p!=NULL)
{
q=p;
p=p->next;
q->next=ll->next;
ll->next=q;
}
}
void linklist_modify_by_data(struct node *ll,datatype_t pre,datatype_t value)
{
while(ll->next!=NULL)
{
if(ll->next->data==pre)
ll->next->data=value;
ll=ll->next;
}
}
int linklist_search_by_data(struct node *ll,datatype_t value)
{
int pos=0;
while(ll->next!=NULL)
{
if(ll->next->data==value)
return pos;
ll=ll->next;
pos++;
}
return -1;
}
void linklist_free(struct node *ll)
{
struct node *p,*q;
p=ll->next;
ll->next=NULL;
while(p!=NULL)
{
q=p;
p=p->next;
free(q);
}
}
void linklist_show(struct node *ll)
{
while(ll->next!=NULL)
{
printf("%d ",ll->next->data);
ll=ll->next;
}
putchar('\n');
}
int main()
{
int i;
struct node *linklist;
linklist=linklist_create();
for(i=5;i>=0;i--)
{
linklist_insert_bt_sort(linklist,i);
}
linklist_show(linklist);
datatype_t d=linklist_delete_head(linklist);
linklist_show(linklist);
linklist_modify_by_data(linklist,4,3);
linklist_show(linklist);
linklist_insert_by_pos(linklist,1,20);
linklist_show(linklist);
linklist_reverse(linklist);
linklist_show(linklist);
linklist_free(linklist);
return 0;
}
【3】单向循环链表的实现
#include <stdio.h>
#include <stdlib.h>
typedef int datatype_t;
struct node
{
datatype_t data;
struct node *next;
};
struct node *looplist_create()
{
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->next=tmp;
return tmp;
}
void looplist_insert(struct node *ll,datatype_t value)
{
struct node *tmp=(struct node *)malloc(sizeof(struct node));
tmp->data=value;
if(ll->next==ll)
{
tmp->next=tmp;
ll->next=tmp;
}
else
{
struct node *p=ll->next;
while(p->next!=ll->next)
{
p=p->next;
}
tmp->next=ll->next;
ll->next=tmp;
p->next=tmp;
}
}
void looplist_show(struct node *ll)
{
struct node *p=ll->next;
if(ll->next==ll)
return;
else if(p->next==p)
{
printf("%d\n",p->data);
}
else
{
do
{
printf("%d ",p->data);
p=p->next;
}while(p!=ll->next);
}
putchar('\n');
}
int main()
{
int i;
struct node *looplist;
looplist=looplist_create();
for(i=5;i>0;i--)
{
looplist_insert(looplist,i);
}
looplist_show(looplist);
return 0;
}