单链表

作者在 2010-06-19 10:21:31 发布以下内容
//007.h
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
int over_flag=0;
typedef int ElemType;
typedef struct LNode
{
 ElemType data;
 struct LNode *next;
}LNode,*LinkList;

void Traverse(LinkList L);
void CreateList(LinkList &L);
void exchange(LinkList &L);
void delete_even(LinkList &L);
void Insert_Sort(LinkList &L,ElemType e);
void Create_Sort(LinkList &L);
void MergeIncrease(LinkList La,LinkList Lb,LinkList &Lc);
void Divide(LinkList &L);
void InsertList(LinkList &L);
void Locate(LinkList L);
void DeleteList(LinkList &L);
//尾插法建立单链表
void CreateList(LinkList &L)
{  
 int temp;
 L=(LinkList)malloc(sizeof(LNode));
 L->next=NULL;
 LinkList q=L;
 scanf("%d",&temp);
 while(temp!=-1)
 {
  LinkList p;
  p=(LinkList)malloc(sizeof(LNode));
  p->data=temp;
  p->next=q->next;
  q->next=p;
  q=q->next;
  scanf("%d",&temp);
 }
    Traverse(L);
}
//遍历单链表
void Traverse(LinkList L)
{  
 LinkList t=L->next;
 printf("结点数值:");
 while(t)
 {
  printf("%d",t->data);
  t=t->next;
 }
 printf("\n");
}

//链表中元素逆置
void exchange(LinkList &L)
{
 LinkList p,s;
    p=L->next;
 L->next=NULL;
 while(p)
 {
  s=p;
  p=p->next;
  s->next=L->next;
  L->next=s;
 }
}

//在单向链表中删除所有偶数元素结点
void delete_even(LinkList &L)
{
 printf("删除偶数结点后的链表为:\n");
 LinkList q=L;
 LinkList p=L->next;
 while(p)
 {
  if(p->data%2==0)
  {
   LinkList r=p;
   q->next=p->next;
   p=p->next;
   free(r);
  }
            else
   {
        p=p->next;
        q=q->next;
   }
 }
  Traverse(L);
}

//非递减有序单向链表中插入元素e,序列仍有序
void Insert_Sort(LinkList &L,ElemType e)
{
 LinkList p,s;
 s=(LinkList)malloc(sizeof(LNode));
 s->data=e;
 p=L;
 while(p->next&&p->next->data<e)
 {
  p=p->next;
  s->next=p->next;
  p->next=s;
 }
}

//建立递增有序单项链表
void Create_Sort(LinkList &L)
{
 int e;
 L=(LinkList)malloc(sizeof(LNode));
 L->next=NULL;
 printf("建立递增有序表,输入任意个整型数据以0结束\n");
 scanf("%d",&e);
 while(e)
 {
  Insert_Sort(L,e);
  scanf("%d",&e);
 }
}
 
//建立两个非递减有序单向链表,然后合并成一个仍非递减链表
void MergeIncrease(LinkList La,LinkList Lb,LinkList Lc)
{
 LinkList p,q,s,rear;
 p=La->next;
 q=Lb->next;
 Lc=rear=La;
 free(Lb);
 while(p&&q)
 {
  if(p->data<q->data)
  {
   s=p;
   p=p->next;
  }
  else
  {
   s=q;
   q=q->next;
  }
  rear->next=s;
  rear=rear->next;
 }
 if(p)
  rear->next=p;
 else
  rear->next=q;
}

//将链表分解,一个全为奇数,一个全为偶数
void Divide(LinkList &L)
{
 printf("分解成两个链表:\n");
 LinkList A=L;
 LinkList B=(LinkList)malloc(sizeof(LNode));
 B->next=NULL;
 LinkList Lb=B;
 int i=1;
 LinkList La=L;
 LinkList p=L->next;
 while(p)
 {
  if(i++%2==0)
  {
   La->next=p->next;
   p->next=NULL;
   Lb->next=p;
   Lb=Lb->next;
   p=La->next;
  }
  else
  {
   p=p->next;
   La=La->next;
  }
 }
 printf("链表A:");
 Traverse(A);
 printf("链表B:");
 Traverse(B);
 printf("已经分解成两个链表!\n");
 over_flag=1;
}

//求单链表的长度
int ListLength(LinkList &L)
{
 int i=0;
 LinkList p=L->next;
 while(p)
 {
  p=p->next;
  i++;
 }
 return i;
}

//插入元素
void InsertList(LinkList &L)
{
 int x,i;
 printf("请输入您要插入的数值和元素的位置:");
 scanf("%d%d",&x,&i);
 LinkList p=L;
 int j=0;
 while(p&&j<i-1)
 {
  p=p->next;
  ++j;
 }
 if(!p||j>i-1)
 {
  printf("输入位置有误!");
  return;
 }
 LinkList s=(LinkList)malloc(sizeof(LNode));
 s->data=x;
 s->next=p->next;
 p->next=s;
 Traverse(L);
}

//查找元素
void Locate(LinkList L)
{
 if(!L)
  printf("错误:链表未创建!");
 int element;
 printf("查询数值:\n输入要查询的数值:");
 scanf("%d",&element);
 LinkList p=L->next;
 int i=1;
 while(p)
 {
  if(p->data=element)
  {
   printf("找到了,它是链表第%d个元素",i);
   return;
  }
  p=p->next;
  i++;
 }
 printf("找不到.\n");
}

void GetElem(LinkList L)
{  
 int x,e;
 printf("请输入您要查找的元素的位置:");
 scanf("%d",&x);
 LinkList p=L->next;
 j=1;
 while(p&&j<i)
 {
  p=p->next;
  ++j;
 }
 if(!p||j>i)
  return 0;
    e=p->data;
 printf("第%d个结点位置的元素值为:%d",x,e);
}
 
void DeleteList(LinkList &L)
{
 int i;
 LinkList p=L->next;
 printf("选择位置删除结点:\n输入要删除数值的位置:");
 scanf("%d",&i);
 int j=1;
 while(p&&j<i-1)
 {
  p=p->next;
  ++j;
 }
 if(!p||j>i-1)
 {
  printf("输入位置错误!");
  return ;
 }
 LinkList q=p->next;
 p->next=q->next;
 free(q);
 Traverse(L);
}
 
主函数
 
#include <stdio.h>
#include <stdlib.h>
#include "007.h"
void main()
{
 LinkList La,Lb,Lc;
    char operate;
 
 do
 {
        printf("A\t\t\t建立无序单向链表, 并进行下一步操作(插入、删除、查找)\n");
  printf("B\t\t\t建立递增有序链表,再逆置\t\t\t\n");
  printf("C\t\t\t建立两个递增有序表,将它们合并为一个仍递增表\n");
  printf("D\t\t\t建立两个递增有序表,将它们合并为一个非递增链表\n");
  printf("E\t\t\t将无序链表分解为两个链表\n");
  printf("F\t\t\t删除所有偶数元素的结点\n");
  printf("Q\t\t\t退出\n");
  scanf("%c",&operate);
  switch(operate)
  {
  case a:
  case A:
            {
    CreateList(La);
    int select;
    do{
     printf("
   }
   break;
  case b:
  case B:
   break;
  case c:
  case C:
   break;
  case d:
  case D:
   break;
  case e:
  case E:
   break;
  case f:
  case F:
   break;
  case q:
  case Q:
   break;
  }while(operate)
 }
}
 
文章评论,共0条
游客请输入验证码
文章归档
最新评论