首页 > 代码库 > 顺序表--单链表
顺序表--单链表
单链表：
typedef struct Lnode{ ElemType data; /*数据域，保存结点的值 */ struct Lnode *next; /*指针域*/}LNode, *LinkList; /*结点的类型 */
建表：
1）头插入建表：每次插入的结点都作为链表的第一个结点。 只要在新创建单线性链表时，如果要插入的结点是n个，算法的时间复杂度均为O(n)。
void create_LinkList(LinkList &L,int n)/*给一组数据逆着插入才是顺序*/ { LNode *p, *q; L= (LinkList) malloc(sizeof(LNode)); L->next=NULL; /* 创建一个带头结点的单链表L */ for (i=n;i>0;i--) { p=(LinkList) malloc(sizeof(LNode)); scanf(&p->data) ; /* 数据域赋值 */ p–>next=L->next; L->next=p; /*插到表头*/ }}
2）尾插入建表：新结点插入到当前链表的表尾，使其成为当前链表的尾结点。
void *create_LinkList(LinkList &L, int n)/* 尾插入法创建单链表*/ { LNode *p, *q; L=p=(LinkList)malloc(sizeof(LNode)); p->next=NULL; /* 创建单链表的表头结点L */ for (i=1;i<=n;i++) { q=(LinkList) malloc(sizeof(LNode)); scanf(&q->data) ; /* 数据域赋值 */ q–>next=p->next; p->next=q; p=q; /*插到表尾*/ }}
查找:
1)按序号查找 取单链表中的第i个元素
Status Get_Elem(LNode *L, int i, ElemType &e){ int j ; LNode *p; p=L->next; j=1; /* 使p指向第一个结点 */ while (p && j<i) { p=p–>next; j++; } /* 移动指针p , j计数 */ if (!p || j>i) return ERROR ; e=p->data ; return OK;}移动指针p的频度：i<1时：0次; i∈[1,n]：i-1次；i>n：n次。∴时间复杂度: O(n)。
2)按值查找:算法的执行与形参key有关，平均时间复杂度为O(n)
ElemType *Locate_Node(LNode *L，ElemType key)/* 在以L为头结点的单链表中查找值为key的第一个结点 */ { LNode *p=L–>next; while( p!=NULL&& p–>data!=key) p=p–>next; if(p–>data=http://www.mamicode.com/=key) return p; else { printf(“所要查找的结点不存在!!\n”); retutn(NULL); }}
插入:（算法的时间主要耗费移动指针p上，故时间复杂度亦为O(n)）。
Status Insert_LNode(LinkList &L，int i，ElemType e)/* 在以L为头结点的单链表的第i个位置插入值为e的结点 */ { int j=0; LNode *p，*q; p=L–>next ; while( p&& j<i-1) { p=p–>next; j++; } if(!p || j>i-1) { printf(“i太大或i为0!!\n ”); return ERROR; } q=(LinkList)malloc(sizeof(LNode)); q–>data=http://www.mamicode.com/e; q–>next=p–>next; p–>next=q; return OK;}
删除：
1） 按序号删除 算法的时间复杂度是O(n)。
Status Delete_LinkList(LNode *L， int i，ElemType &e) /* 删除以L为头结点的单链表中的第i个结点，由e返回删除值 */ { int j=1; LNode *p，*q; p=L; q=L->next; while( p->next && j<i) /*找到第i-1个结点*/ { p=p–>next; j++; } if(!(p->next) || j>i) { printf(“i太大或i为0!!\n ”); return Error; } q=p–>next; p->next=q->next; e=q->data; free(q); return OK;}
2）按值删除 算法的执行与形参key有关，平均时间复杂度为O(n)
void Delete_LinkList(LNode *L，int key)/* 删除以L为头结点的单链表中值为key的第一个结点 */ { LNode *p=L, *q=L–>next; while( q && q–>data!=key) { p=q; q=q–>next; } if(q–>data=http://www.mamicode.com/=key) { p->next=q->next; free(q); } else printf(“所要删除的结点不存在!!\n”);}
3） 删除单链表中值为key的所有结点。
void Delete_LinkList_Node(LNode *L，int key)/* 删除以L为头结点的单链表中值为key的第一个结点 */ { LNode *p=L, *q=L–>next; while( q!=NULL) { if (q–>data=http://www.mamicode.com/=key) { p->next=q->next; free(q); q=p->next; } else { p=q; q=q–>next; } }}
4）删除单链表中所有值重复的结点，使得所有结点的值都不相同
void Delete_Node_value(LNode *L)/* 删除以L为头结点的单链表中所有值相同的结点 */ { LNode *p=L->next, *q, *ptr; while(p) /* 检查链表中所有结点 */ { *q=p, *ptr=p–>next;/* 检查结点p的所有后继结点ptr */ while (ptr) { if (ptr–>data=http://www.mamicode.com/=p->data) { q->next=ptr->next; free(ptr); ptr=q->next; } else { q=ptr; ptr=ptr–>next; } } p=p->next ; }}
单链表的合并：若La ，Lb两个链表的长度分别是m，n，则链表合并的时间复杂度为O(m+n)
void Merge_LinkList(LinkList &La，LinkList &Lb, LinkList &Lc) /* 合并以非递减有序单链表La, Lb到有序单链表Lc */{ LNode *pa,*pb,*pc,*ptr ; pa=La->next ; pb=Lb->next ; Lc= pc=La; while (pa && pb) { if(pa->data<=pb->data) { pc->next=pa ; pc=pa ; pa=pa->next ; } /* 将pa所指的结点合并，pa指向下一个结点 */ else { pc->next=pb ; pc=pb ; pb=pb->next ; }/* 将pb所指的结点合并，pb指向下一个结点 */ } pc-next=pa?pa:pb; free(Lb) ;}
顺序表--单链表
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。