线性表的顺序存储结构的优缺点
优点;随机存取,存储空间利用率高
缺点:插入,删除效率低;必须按事先估计的最大元素个数分配连续的存储空间,难以临时扩大
链表的定义
采用链式存储结构的线性表称为链表
链表
单链表、循环链表、双向链表
结点
每个数据元素——数据域
直接后继的存储地址——指针域
单链表的定义
每个结点只包含一个指针域的链表
单链表结构
最后一个结点的指针域为null
First是头指针,指向链表中的第一个结点
链表中的第一个结点称为头结点
单链表类型定义
typedef struct node
{ElemType element;Struct node *link;
}node;
tepedef struct singleList
{struct node first;int n;
}singleList
单链表的插入
功能:
在给定元素ai之后插入值为X的元素
插入算法步骤为:
1、生成数据域为x的新结点,指针q指向新结点
2、从头结点开始,找到元素ai所在结点,指针p指向该结点
3、将新结点插入在ai所在结点之后
4、表长加1
Status Insert(SingleList *L,int i,ElemType x)
{Node *p,*q;int j;if(i<-1||i>L-n-1)return ERROR;p=L->first;for(j=0;j<i;j++)p=p->link;//从头结点开始查找ai q=malloc(sizeof(Node));//生成新结点q q->element=x;if(i>-1){q->link=p->link;p->link=q;}//新结点插在单链表中间位置的情况 else{q->link=L->first;L->first=q;}//新结点插在a0之前,成为新的头结点 L->n++;//表长增加1 return OK;
}
单链表的删除运算
Status Delete(SingleList *L,int i)
{int j;Node *p,*q;if(!L->n)return ERROR;if(i<0||i>L->n-1)return ERROR;q=L->first;p=L->first;for(j=0;j<i-1;j++)q=q->link;//q指向ai-1 if(i==0)L->first=L->first->link//删除的是头结点else{p=q->link;//p指向ai q->link=p->link;//从单链表中删除p所指向的结点 }free(p);//释放P所指结点的存储空间 L->n--;return OK;
}