原创 线性链表的基本操作

一、上机实验的问题和要求：<?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />

单链表的查找、插入与删除。设计算法，实现线性结构上的单链表的产生以及元素的查找、插入与删除。具体实现要求：

1. 从键盘输入20个整数，产生不带表头的单链表，并输入结点值。

2. 从键盘输入1个整数，在单链表中查找该结点的位置。若找到，则显示“找到了”；否则，则显示“找不到”。

3. 从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出单链表所有结点值，观察输出结果。

4. 从键盘输入1个整数，表示欲删除结点的位置，输出单链表所有结点值，观察输出结果。

5. 将单链表中值重复的结点删除，使所得的结果表中个结点值均不相同，输出单链表所有结点值，观察输出结果。

6. 删除其中所有数据值为偶数的结点，输出单链表所有结点值，观察输出结果。

7. 把单链表变成带表头结点的循环链表，输出循环单链表所有结点值，观察输出结果。

8. （★）将单链表分解成两个单链表A和B，使A链表中含有原链表中序号为奇数的元素，而B链表中含有原链表中序号为偶数的元素，且保持原来的相对顺序，分别输出单链表A和单链表B的所有结点值，观察输出结果。

二、程序设计的基本思想，原理和算法描述：

（包括程序的结构，数据结构，输入/输出设计，符号名说明等）

    这是一个带头结点的线性链表，数据域存放整形数据，由用户输入。头结点数据域存链表长度，所以程序中有个求链表长度的函数

          int LengthList(LinkList L);            //求链表长度

L是指向头结点的指针，将长度值存入语句为

          L->data = LengthList(L);

    为了实时观察链表情况，程序中有个输出链表数据的函数

          void PrintList(LinkList L);            //输出链表

    程序可以实现8种不同的操作，这8种不同的操作由8个函数实现，分别是

void CreateList(LinkList &L);          //创建链表

void Locate(LinkList L);               //查询数值

void InsertList(LinkList &L);          //插入数值

void DeleteList(LinkList &L);          //选择删除

void Deleterepeat(LinkList &L);        //删除重复结点

void DeleteEven(LinkList &L);         //删除数值为偶数的结点

void Rotate(LinkList &L);              //变为循环链表

void Divide(LinkList &L);              //分解成两个链表

这些基本操作的实现算法都比较简单，有些跟书本上一样，有些需要自己稍作思考才能写出，具体程序见第三部分

   8种不同的操作可以由用户通过按A-H这八个字母键来选择，分别是   A:创建 B:查询 C:插入 D:选择删除 E:删除重复 F:删除偶数  G:变为循环链表 H:分解为两个链表，见第四部分输出截图，可以清晰的看到整个过程

主程序中用  开关语句实现:

char operate;

printf("\n\n输入字符选择链表操作类型\nA:创建 B:查询 C:插入 D:选择删除 E:删除重复 F:删除偶数 \nG:变为循环链表 H:分解为两个链表\n");

scanf("%c",&operate);

switch (operate)

{

      case 'a':

          case 'A': CreateList(L);break;

  case 'b':

  case 'B': Locate(L);break;

  case 'c':

  case 'C': InsertList(L); break;

  case 'd':

  case 'D': DeleteList(L);break;

  case 'e':

  case 'E': Deleterepeat(L);break;

  case 'f':

  case 'F': DeleteEven(L);break;

  case 'g':

  case 'G': Rotate(L);break;

  case 'h':

  case 'H': Divide(L);break;

  case '\n':goto label;

          default: printf("输入有误，请重新输入！");break;

}

三、源程序及注释：

#include<stdio.h>

#include<malloc.h>

typedef struct LNode         //链表结点

{

int data;

struct LNode *next;

}LNode,*LinkList;

int over_flag=0;                        //主函数结束标识符

void CreateList(LinkList &L);          //创建链表

void Locate(LinkList L);               //查询数值

void InsertList(LinkList &L);          //插入数值

void DeleteList(LinkList &L);          //选择删除

void Deleterepeat(LinkList &L);        //删除重复结点

void DeleteEven(LinkList &L);          //删除数值为偶数的结点

void Rotate(LinkList &L);              //变为循环链表

void Divide(LinkList &L);              //分解成两个链表

int LengthList(LinkList L);            //求链表长度

void PrintList(LinkList L);            //输出链表

/**********************************************************************

                            主函数

**********************************************************************/

void main(void)

{   

char operate;

LinkList L;

int n;

for( n=0;n<40;n++)

{

printf("\n\n输入字符选择链表操作类型\nA:创建 B:查询 C:插入 D:选择删除 E:删除重复 F:删除偶数 \nG:变为循环链表 H:分解为两个链表\n");

        label:scanf("%c",&operate);

switch (operate)

{

      case 'a':

          case 'A': CreateList(L);break;

  case 'b':

  case 'B': Locate(L);break;

  case 'c':

  case 'C': InsertList(L); break;

  case 'd':

  case 'D': DeleteList(L);break;

  case 'e':

  case 'E': Deleterepeat(L);break;

  case 'f':

  case 'F': DeleteEven(L);break;

  case 'g':

  case 'G': Rotate(L);break;

  case 'h':

  case 'H': Divide(L);break;

  case '\n':goto label;                    //排除换行键的影响

          default: printf("输入有误，请重新输入！");break;

}

        if(over_flag)return;

    }

}

/**********************************************************************

                            创建链表

**********************************************************************/

void CreateList(LinkList &L)

{  

   int temp;

   printf("创建链表：\n请输入创建链表所需的整数值(以-1结束):");

   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 = NULL;

       q->next = p;

       q = q->next;  

       scanf("%d",&temp);

}

    L->data = LengthList(L);

    PrintList(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个元素。\n",i);

         return ;

  }

  p=p->next;

  i++;

}

    printf("找不到。\n");

}

/**********************************************************************

                            插入数值

**********************************************************************/

void InsertList(LinkList &L)

{

  int x,i;

  printf("插入数值：\n输入要插入的数值和插入的位置：");

  scanf("%d",&x);

  scanf("%d",&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;

  L->data = LengthList(L);

  PrintList(L);

} 

/**********************************************************************

                            选择位置删除节点

**********************************************************************/

void DeleteList(LinkList &L)

{ 

  int i;

  LinkList p = L;

  printf("选择位置删除结点：\n输入要删除数值的位置：");

  scanf("%d",&i);

  int j = 0;

  while (p->next && j < i-1)

  {  

    p = p->next;

    ++j;

  }

  if (!(p->next) || j > i-1)

  {

  printf("输入位置错误!") ;

  return;

  }

  LinkList q = p->next;

  p->next = q->next;          

  free(q);

  L->data = LengthList(L);

  PrintList(L);

} 

/**********************************************************************

                            删除重复结点

**********************************************************************/

void Deleterepeat(LinkList &L)

{

    printf("删除重复结点后的链表为：\n");

int n=1;

int a[20];

LinkList q=L->next;

LinkList p=q->next;

    a[0]=q->data;

while(p)

{

for(int i=0;i<n;i++)

{

if(p->data==a)