实验二  单链表的基本操作（必做，设计性实验）

1. 实验目的

了解线性表的链式存储结构和顺序存取特性，熟练掌握线性表的链式存储结构的C语言描述方法，熟练掌握动态链表的基本操作查找、插入、定位等，能在实际应用中选择适当的链表结构。掌握用链表表示特定形式的数据的方法，并能编写出有关运算的算法。

1. 实验内容

1. 已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。
2. 完成单链表上的如下操作：

① 逆序建立单链表

② 遍历单链表(输出单链表每个元素的值)

③ 在单链表第5个元素前插入一个值为999的元素.

④ 删除单链表第5个元素.

1. 问题描述

    （说明你选做的题目及要求）

1、已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

2、完成单链表上的如下操作：

① 逆序建立单链表

② 遍历单链表(输出单链表每个元素的值)

③ 在单链表第5个元素前插入一个值为999的元素.

④ 删除单链表第5个元素.

1. 数据结构定义

    （说明你算法中用到的数据结构、数据类型的定义）

数据结构：线性表的链式存储

在单链表中，假定每个结点类型用Linklist表示，它包括存储元素的数据域，用data表示，其类型用通用类型标识符ElemType 表示，还包括存储后续元素位置的指针域 用next表示。

LinkList类型的定义如下:

Typedef struct LNode

{      ElemType data;

       Struct LNode *next;

}LinkList;

1. 算法思想及算法设计

    （先文字说明算法的思想，然后给出类C语言算法）

1、

尾插法建表：

从一个空表开始，读取字符数组a中的字符，生成新结点，将读取的数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到结束为止

void CreateList(LinkList &L, int n)

{

 L = new LNode; L->next = NULL;

 LNode *r;

 r = L;

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

 {

  printf("请输入链表第%d个元素的值:", i + 1);

  LNode *s;

  s = new LNode;

  scanf("%d", &s->data);

s->next = NULL;r->next = s;r = s;

 }

删除算法：

先将第一个结点的数据跟mink比较，如果小于mink，则指向下一个结点，如果大于mink，跳出，如果小于则将在有效范围内的数据删除并释放结点空间，将删除后的前后两段重新链接。

void DeleteSome(LinkList &L, ElemType mink, ElemType maxk)

{   LinkList p,q,w;

   p=L->next;

   w=NULL;

   while(p->data<=mink)

    {w=p;

    p=p->next;

    if(!p) break; }

   while(p->data>maxk

   {q=p;p=q->next;

    free(q);

    if(!p) break;

    }

    w->next=p; }

2、逆序创建单链表

int transCreat(LinkList head){

 LinkList pnew;

 pnew = (LinkList)malloc(LEN);

 printf("请依次输入数据(输入-1认为输入终止)\n");

 scanf("%d",&pnew->data);

 while(pnew->data!=-1){//先把后边的串上再串前边的

  head->data++;

  pnew->next = head->next;//核心语句

  head->next = pnew;      //核心语句

  pnew = (LinkList)malloc(LEN);

  scanf("%d",&pnew->data);

 }

1. 插入节点的运算

先在链表中确定头结点p，将要插入的值赋值给新结点的数据域，将插入位置之后的元素都向后移一位，将新结点插入。

int insertLNode(LinkList head,int num,int locate){

 LinkList pnew,p;

 int i=0;

 p = head;//p指向第0个结点 i也表示第0个结点

 pnew = (LinkList)malloc(LEN);

 pnew->data = num;

 while(p&&i<locate-1){//p的位置停在所要插入位置的前一位

  p = p->next;

  i++;//p往后移动 i作为一个位置游标就加1

 }

 pnew->next = p->next;

 p->next = pnew;

 head->data++;

 return OK;

}

1. 实验代码

    （即C语言程序）

实验一

#include<stdio.h>

#include<iostream>

using namespace std;

typedef struct LNode

{

 int data;

 struct LNode *next;

}LNode, *LinkList;


int InitList(LinkList &L)

{

 L = new LNode;

 L->next = NULL;

 return 1;

}


void TraveList(LinkList L)

{

 LNode *p;

 p = L->next;



 while (p)

 {

  printf("%d ", p->data);

  p = p->next;

 }

 printf("\n");

}


// 尾插法建立链表

void CreateList(LinkList &L, int n)

{

 L = new LNode;

 L->next = NULL;

 LNode *r;

 r = L;

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

 {

  printf("请输入链表第%d个元素的值:", i + 1);

  LNode *s;

  s = new LNode;

  scanf("%d", &s->data);

  s->next = NULL;

  r->next = s;

  r = s;

 }

}


void Delete(LinkList &L, int mink, int maxk)

{   LinkList p,q,w;

   p=L->next;

   w=NULL;

   while(p->data<=mink) //先将第一个结点的数据跟mink比较，

    {w=p;

    p=p->next;          //如果小于mink，则指向下一个结点

    if(!p) break;        //如果大于mink，跳出

    }

  
   while(p->data

   {q=p;                 //如果大于，则跳出

    p=q->next;           //如果小于则将在有效范围内的数据删除并释放结点空间

    free(q);

    if(!p) break;

    }

    w->next=p;          //将删除后的前后两段重新链接

}

int main()

{

 LinkList L1;

 if (InitList(L1))

 {

  printf("L1初始化成功!\n");

 }

 else

 {

  printf("L1初始化失败!\n");

 }

 printf("请输入L1的长度:");

 int n1;

 scanf("%d", &n1);

 CreateList(L1, n1);

 TraveList(L1);


 int a, b;

 printf("请输入min和max的值\n");

 scanf("%d %d",&a,&b);

 printf("删除链表中大于%d小于%d的节点:\n", a, b);

 Delete(L1, a, b);

 TraveList(L1);

 system("pause");

 return 0;

}

实验二

#include<stdio.h>

#include<stdlib.h>

#define OK 1

#define ERROR 0

#define LEN sizeof(struct LNode)

struct LNode{

 int data;

 struct LNode *next;

};

typedef struct LNode LNode,* LinkList;



//初始化

LinkList InitLNode(void){

 LinkList head = (LinkList)malloc(LEN);

 if(!head){

  printf("存储空间分配失败！\n");

  exit(ERROR);

 }

 head->data = 0;

 head->next = NULL;

 return head;

}

//逆序创建单链表

int transCreat(LinkList head){

 LinkList pnew;

 pnew = (LinkList)malloc(LEN);

 printf("请依次输入数据(输入-1认为输入终止)\n");

 scanf("%d",&pnew->data);

 while(pnew->data!=-1){//先把后边的串上再串前边的

  head->data++;

  pnew->next = head->next;//核心语句

  head->next = pnew;      //核心语句

  pnew = (LinkList)malloc(LEN);

  scanf("%d",&pnew->data);

 }

 free(pnew);//此时的pnew数据域里存放着-1 没有被链入到链表中 无用

 return OK;

}

//输出单链表

int printLNode(LinkList head){

 if(!head->next){

  printf("空链表！\n");

  return ERROR;

 }

 LinkList p;

 p = head->next;

 do{

  printf("%d ",p->data);

  p = p->next ;

 }while(p);

}

//插入

int insertLNode(LinkList head,int num,int locate){

 if(locate<1||locate>head->data+1){

  printf("插入位置有误！\n");

  exit(ERROR);

 }

 LinkList pnew,p;

 int i=0;

 p = head;//p指向第0个结点 i也表示第0个结点

 pnew = (LinkList)malloc(LEN);

 pnew->data = num;

 while(p&&i<locate-1){//p的位置停在所要插入位置的前一位

  p = p->next;

  i++;//p往后移动 i作为一个位置游标就加1

 }

 pnew->next = p->next;

 p->next = pnew;

 head->data++;

 return OK;

}

//删除

int delLinkList(LinkList head,int locate){

 if(!head->next){

  printf("空链表！\n");

  exit(ERROR);

 }

 if(locate<1||locate>head->data){

  printf("位置有误!\n");

  return ERROR;

 }

 LinkList pleft,pright;

 int i = 0;

 pleft = pright = head;

 while(pright&&i<locate){

  pleft = pright;

  pright = pright->next;

  i++;//pright和i指的是同一个结点

 }

 pleft->next = pright->next;

 head->data--;

 free(pright);

 return OK;

}



main(){

 LinkList head;

 head = InitLNode();

 transCreat(head);

 printLNode(head);

 printf("\n\n在单链表第5个元素前插入一个值为999的元素后结果是：\n");

 insertLNode(head,999,5);

 printLNode(head);

 printf("\n\n删除单链表第5个元素后结果是：\n");

 delLinkList(head,5);

 printLNode(head);

}

1. 算法测试结果

    （说明测试数据，粘贴实验结果图）

（1）链表元素{ 1 2 3 4 5 } mink和maxk分别是1，3

 

（2）链表元素{1 2 3 4 5 6 7 8 9 10}

 

1. 分析与总结

    （1）算法复杂度分析及优、缺点分析

        （说明你编写算法的复杂度，算法的优点和缺点有哪些）

尾插法建表void CreateList(LinkList &L, int n)的时间复杂度为O(n),删除插入while循环体中的语句频率和元素位置有关，因此算法时间复杂度为O(n).已知链表中元素插入删除位置的情况下，在单链表中插入或删除一个结点时，仅需要修改指针而不需要移动元素。

    （2）实验总结

        （说明你怎么解决实验中遇到的问题，有什么收获）

通过这次实验，更好的了解和学习到了单链表中链表建立，元素删除，插入等基本操作，熟悉了操作平台的使用，对单链表的操作有更好的认识。