首页 > 代码库 > 数据结构之第二章线性表之链式存储
数据结构之第二章线性表之链式存储
1~~特点：逻辑上相邻的元素，他的物理位置不一定相邻，其实几乎是不像邻的。表中的元素只能顺序访问，插入，删除等操作只需修改指针而不需要移动元素，存储空间利用率高，表的容量可以动态变化。适合个数变化大的情况。
2～～链式存储`的存储结构
typedef struct Node{ int data; struct Node *next;}NODE,*PNODE;
3~~线性表的基本操作
（1）线性表的的 插表头 建立算法
” 插表头“方式得到的线性链表，元素存储的顺序和输入顺序相反，这与栈的特点相吻合，因此链表的压栈实际上是插表头。
int creatlinklist(PNODE head,int n){ //逆序输入n个元素，建立带有头节点的线性链表 int value; head=(PNODE)malloc(sizeof(NODE)); head->next=NULL;//建立一个带有头节点的线性链表 for(i=n;i>0;--i){ newbase=(PNODE)malloc(sizeof(NODE)); PNODE phead=head; scanf("%d",&value);//输入元素的值并把她给你新定义的节点。 newbase.data=http://www.mamicode.com/value; newbase.next=phead.next; phead.next=newbase;//插入 }}
算法的时间复杂度为O（listlength（head））
（2） 线性链表的 插表尾 建立算法
“插表尾”方式得到的线性链表，元素存储的顺序和输入顺序相同，这一点和队列的入队操作相吻合，因此链式队列的入队实际上是插表尾。
int creatlinklist(PNODE head ,int n){ int value; head=(PNODE)malloc(sizeof(NODE)); phead=head;//建立一个带有头节点和尾指针的线性链表 for(int i=0;i<n;i++){ PNODE newbase=(PNODE)malloc(sizeof(NODE));//开辟新节点 scanf("%d",&value);//输入元素值 phead.next=newbase;//插入 phead=newbase; } phead->next=NULL;//修改尾指针}
算法的时间复杂度为O（linklength（head））
（3）线性链表的插入
int insertlink(PNODE head,int num,int pos){ //这里的num是你所要插入的数值，然后这个poe就是你所要插入的位置 int value; PNODE phead=head; for(int i=0;i<pos-1;i++){ phead=phead->next; } PNODE newbase=(PNODE)malloc(sizeof(NDOE)); newbase->next=phead->next; phead.next=newbase; return 1;}
算法的时间复杂度是O（linklength（head））
（4）线性链表的删除
int deletelink(PNODE head,int num,int pos){ //这里的num是你所要删除的数值，然后这个poe就是你所要删除的位置 int value; PNODE phead=head; for(int i=0;i<pos-1;i++){ phead=phead->next; } phead=phead.next.next; free(phead.next); return 1;}
算法的时间复杂度为O（linklength（head））
注意：一个节点之前插入一个结点和一个节点之后删除一个结点的差别，以及删除当前节点和删除一个节点的后继的差别。
（1）讲节点P插入到节点pa之后，关键是修改指针：
p->next=pa->next;pa->next=p;
(2)将节点P插入到节点Pa之前，可转换为将p插在pa之后
p->next=pa->next;pa->next=p;x=p->data;p->data=http://www.mamicode.com/pa->data;pa->data=http://www.mamicode.com/x;
(3)删除节点pa的后继（pa->next!=NULL):
p=pa->next;pa->next=pa->next->next;free(p);
(4)删除节点pa可以转换为删除pa的后继
现将pa的后继的数据域覆盖pa的数据域，然后删除pa的后继
pa->data=http://www.mamicode.com/pa->next.data;p=pa->next;pa->next=pa->next->next;free(p);
(5）线性链表的查找（取第i个元素）
int getnode(PNODE head,int i,int e){ //在带头节点的单链表中，取第i个元素,将这个位置的数值给e phead=head->next; int j=1;//j为计数器 while(phead&&j<i){ phead=phead->next; ++j; } if(!phead||j>i) return 0; else e=phead.data; return 1; }
(6)两个有序链表的合并
void hebing(PNODE head1,PNODE head2,PNODE head3){ phead1=head1->next; phead2=head2->next; phead3=head3->next; while(head1&&head2){ if(phead1->data<=phead2->data){ phead3->next=head1; phead3=phead1; phead1=phead1->next; } else { phead3->next=phead2; phead3=phead1; phead2=phead2->next; } phead3->next=phead1?phead1:phead2; free(phead2); }}
算法的时间复杂度为O(linklength(head1+head2))
数据结构之第二章线性表之链式存储