数据结构——单向链表的获取、插入、删除、创建、合并、遍历

1、单向链表的头文件的声明：

#define OK 1
#define ERROR 0

typedef int ElemType;
typedef int Status;
typedef struct LNode
{
 ElemType data;  //数据域
 struct LNode* next; //指针域
}LNode,*LinkList;
//获取元素
Status GetElem_L(LinkList L, int i, ElemType& e);
//插入元素
Status ListInsert_L(LinkList& L, int i, ElemType e);
//删除元素
Status ListDelete_L(LinkList& L, int i, ElemType& e);
//创造链表
void CreateList_L(LinkList& L, int n);
//合并链表
void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc);
//遍历链表
Status ListTraver_L(LinkList L);

2、单向链表函数的定义：

2.1、获取元素：

Status GetElem_L(LinkList L, int i, ElemType& e)
{
 //L为带头结点的单链表指针，LinkList的类型为LNode *
 //当第i个元素存在时，其值赋给e并返回OK，否则返回ERROR
 LinkList p;
 int j;  
 p = L->next; j = 1;  //初始化，p指向第一个结点，j为计时器
 while (p && j < i)  //顺指针向后查找，知道p指向第i个元素或p为空
 {
  p = p->next;
   ++j;
 }
 if (!p || j > i)  //第i个元素不存在
  return ERROR;
 e = p->data;   //取第i个元素
 return OK;
}

2.2、插入元素：

Status ListInsert_L(LinkList& L, int i, ElemType e)
{
 //在带头结点的单链表L中第i个位置之前插入元素e
 LinkList p=L;
 int j=0;
 while (p && j < i - 1)  //寻找第i-1个结点
 {
  p = p->next;   //i为i-2时，p的next结点为i-1，所以找到第i-1个结点
  ++j;
 }
 if (!p || j > i - 1)  //i小于1或者大于表长加1
  return ERROR;
 LinkList s = (LinkList)malloc(sizeof(LNode));  //生成新的结点
 if (!s)
  return ERROR;
 s->data = e; s->next = p->next;      //插入L中
 p->next = s;
 return OK;
}

2.3、删除元素：

Status ListDelete_L(LinkList& L, int i, ElemType& e)
{
 //带头结点的单链线性表L中，删除第i个元素，并由e返回
 LinkList p=L,q;
 int j=0;
 if (p && p->next)
 {
 	while (p->next && j < i - 1)  //寻找第i-1个结点，并令p指向其前驱
 	 {
   		p = p->next;
 		++j;
	 }
	
  if (!(p->next) || j > i - 1)  //删除位置不合理
   return ERROR;
  q = p->next;//删除并释放结点，即释放指针
  p->next = q->next;
  e = q->data;
  free(q);
 } 
 return OK;
}

2.4、创建链表：

void CreateList_L(LinkList& L, int n)
{ 
 //逆序位输入n个元素的值，建立带头结点的单链表L
 int i;
 LinkList p;
 L = (LinkList)malloc(sizeof(LNode));
 if(L)
 {
  L->next = NULL;   //先建立一个带头结点的单链表
 }
 cout << "创造有"<<n<<"个元素的链表，输入元素的值：";
 for (i = n; i > 0; --i)
 {
 p = (LinkList)malloc(sizeof(LNode));  //生成新的结点
  if (p && L)
  {
   cin>>p->data;       //输入元素值
   p->next = L->next;      //插入表头
   L->next = p;
  }
 }
 }

2.5、合并链表：

void MergeList_L(LinkList& La, LinkList& Lb, LinkList& Lc)
{
 //已知单链表La和Lb的元素按值非递减排列
 //合并La与Lb得到Lc，Lc的元素也非递减排列
 LinkList pa, pb, pc;
 pa = La->next;
 pb = Lb->next;
 Lc = pc = La;   //用La的头结点作为Lc的头结点
 while (pa && pb)
 {
 if (pa->data <= pb->data)
  {
   pc->next = pa;
   pc = pa;
   pa = pa->next;
  }
  else
  {
   pc->next = pb;
   pc = pb;
   pb = pb->next;
  }
 }
 pc->next = pa ? pa : pb;  //插入剩余段
 free(Lb);      //释放Lb的头结点
}

2.6、遍历链表：

Status ListTraver_L(LinkList L)
{
 //遍历头结点L的单链表
 LinkList p;
 if (!L)   //空表返回错误
  return ERROR;
  p = L->next; //首元结点赋给p
 cout << "链表各元素为：";
 while (p)
 {
  cout << p->data << " ";
   p = p->next;
 }
 cout << endl;
 return OK;
}

3、测试代码：