单链表的头插、尾插、删除、合并等操作-创新互联
单链表的头插、尾插、删除、合并等操作实现代码如下：
#include
using namespace std;
//单链表的存储结构
typedef struct Node
{
int data;
struct Node* next;
}Node,*LinkList;//LinkList为结构指针类型
//初始化单链表
void InitList(LinkList *L)
{
*L = (LinkList)malloc(sizeof(Node));//建立头结点
(*L)->next = NULL;//建立空的单链表L
}
//L是带头结点的空链表头指针，通过键盘输入表中元素值，利用头插法建单链表L
void CreateFromHead(LinkList L)
{
Node *s;
char c;
int flag = 1;
while (flag)//flag初值为1，当输入'$'时，置flag为0，建表结束
{
c = getchar();
if (c != '$')
{
s = (Node*)malloc(sizeof(Node));//建立新结点s
s->data = c;
s->next = L->next;//将s结点插入表头
L->next = s;
}
else
{
flag = 0;
}
}
}
//L是带头结点的空链表头指针，通过键盘输入表中元素值，利用尾插法建单链表L
void CreateFromFail(LinkList L)
{
Node *r,*s;
r=L;//r指针动态指向链表的当前表尾，以便做尾插入，其初值指向头结点
int flag = 1;
char c;
while (flag)//flag初值为1，当输入'$'时，置flag为0，建表结束
{
c = getchar();
if (c != '$')
{
s = (Node*)malloc(sizeof(Node));//建立新结点s
s->data = c;
r->next = s;
r = s;
}
else
{
flag = 0;
r->next = NULL;//将最后一个结点的next链域置为空，表示链表结束
}
}
}
//在带头结点的单链表L中查找第i个结点，若找到(1<=i<=n),则返回该结点的存储位置，否则返回NULL
Node *Get(LinkList L, int i)
{
int j = 0;
Node *p;
if (i <= 0)
{
return NULL;
}
p = L;
while ((p->next != NULL) && (j < i))
{
p = p->next;//扫描下一结点
j++;//已扫描结点计数器
}
if (i == j)
{
return p;//找到了第i个结点
}
else
{
return NULL;
}
}
//在带头结点的单链表L中查找其结点值等于key的第1个结点，若找到则返回该结点的存储位置p，否则返回NULL
Node *Locate(LinkList L, int key)
{
Node *p;
p = L->next;//从表中第一个结点开始
while (p!= NULL) //当前表未查完
{
if (p->data!=key)
{
p = p->next;
}
else
{
break;//找到结点值等于key时退出循环
}
}
return p;
}
//求带头结点的单链表L的长度
int ListLength(LinkList L)
{
Node *p;
p = L->next;
int j = 0;//用来存放单链表的长度
while (p != NULL)
{
p = p->next;
j++;
}
return j;//j为求得的单链表的长度
}
//在带头结点的单链表L中第i个位置插入值为e的新结点，n个元素有n+1个插入位置
#define OK 1
#define ERROR 0
void InsList(LinkList L, int i, int e)
{
Node *pre, *s;
int k = 0;
if (i<=0) //判断插入位置是否合法
{
cout << "插入位置i值不合法！" << endl;
return (ERROR);
}
pre = L;
while (pre != NULL&&k < (i - 1))//表未查完且未查到第i-1个元素时重复，若找到pre指向第i-1个
{
pre = pre->next;
k = k + 1;
}
if (!pre)//若当前位置pre为空表，已找完还未找到第i个，说明插入位置不合理
{
cout << "插入位置不合理！" << endl;
return (ERROR);
}
s = (Node*)malloc(sizeof(Node));//申请一个新结点s
s->data = e;//值e置入s的数据域
s->next = pre->next;//修改指针，完成插入操作
pre->next = s;
return (OK);
}
//在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中
void DelList(LinkList L, int i, int *e)
{
Node *pre, *r;
int k = 0;
pre = L;
while (pre->next != NULL&&k < (i - 1))//寻找被删除结点i的前驱结点i-1，使p指向它
{
pre = pre->next;
k = k + 1;
}
//while循环是因为pre->next=NULL或i<1而跳出来的，因为pre->next=NULL，没有找到合法的前驱位置，说明删除位置i不合法
if (!(pre->next))
{
cout << "删除结点的位置i不合理！" << endl;
return (ERROR);
}
r= pre->next;
pre->next=r->next;//修改指针，删除结点r
*e=r->data ;
free(r);//释放被删除结点所占的内存空间
return (OK);
}
//将递增有序的单链表LA和LB，合并成一个递增有序的单链表LC
LinkList MergeLinkList(LinkList LA, LinkList LB)
{
Node *pa, *pb,*r;
LinkList LC;//将Lc初始置为空表，pa和pb分别指向单链表LA和LB中的第一个结点，r初值为LC且r始终指向LC的表尾
pa = LA->next;
pb = LB->next;
LC = LA;
LC->next = NULL;
r = LC;
//当两个表中均未处理完时，比较选择将较小值结点插入到新表LC中
while ((pa != NULL) && (pb != NULL))
{
if (pa->data <= pb->data)
{
r->next= pa;
r = pa;//pa变成新的r结点
pa=pa->next;
}
else
{
r->next = pb;
r = pb;
pb = pb->next;
}
}
if (pa)//当表LA有剩余元素时，则将表LA的剩余元素链到新表LC表尾
{
r->next = pa;
}
else//否则将表LB的剩余元素链到新表LC表尾
{
r->next = pb;
}
free(LB);
return (LC);
}
创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。
本文名称：单链表的头插、尾插、删除、合并等操作-创新互联
标题URL：http://mswzjz.cn/article/dedped.html