数据结构实验报告——链表

• 实验目的与要求
• 实验步骤与内容
• 问题与说明
• 备注
• 程序清单

实验目的与要求

1.掌握链表的各种实现形式（静态和动态）。

2.理解单链表，循环链表，双向链表的形式。

3.理解头插入法和尾插入法的异同。

4.会使用链表删除的几种变形。

5.会使用链表求解一些基本问题。

实验步骤与内容

1.单链表

单链表只有一个指针域，其头结点在第一个节点之前，不存内容。<br>

1.节点的描述

  typedef struct Lnde {
      ElemType data;
    struct Lnode *next;
  }Lnode,*LinkLIst;

2.节点的实现

节点是通过动态分配和释放来实现的，即按需分配，不需要时就实时释放掉。

| 函数名 | malloc() | realloc() | free() | sizeof() |
| —— |
| 作用 | 申请 | 增加 | 释放 | 大小 |
在c++里用new和delete实现。

动态分配

p=(Lnode *)malloc(sizeof(Lnode));
//malloc分配了一个类型为Lnode的节点变量的空间，并将地址放入p中

动态释放

free(q);
//系统回收由指针变量p所指向的内存区，p必须是最近一次使用调用malloc时的返回值

3.基本操作

(1)节点赋值:

Lnode *p;
p=(Lnode *)malloc(sizeof(Lnode));
p->data=data;
p->next=NULL;

(2)建立链表

A.头插入法建表

头插入法建表，是在头结点处进行链表的构建，即链表中的元素顺序与原来的顺序为逆序。

 Lnode *create_Linklist(void){
    int data;
    Lnode *head,*p;
    head=(Lnode *)malloc(sizeof(Lnode));
    head->next = NULL;
    while(1){
        scanf("%d",&data);
        p=(Lnode *)malloc(sizeof(Lnode));
        p->data=data;
        p->next=head->next;
        head->next=p;
        return head;
    }
}

B.尾插入法建表

尾插入法建表需要多一个last指针指向尾节点。

 Lnode *create_Linklist(void){
     int data;
     Lnode *p,*head,*last;
     head=(Lnode *)malloc(sizeof(Lnode));
     head->next=NULL;
     last=head;
     while(1){
         scanf("%d",&data);
         p=(Lnode *)malloc(sizeof(Lnode));
         p->data=data;
         p->next=last->next; /* equal to: p->next=NULL;*/
         last->next=p;
         last=p;
         return (head);
     }
 }

无论那种建表方式，如果节点为n个，时间为O(n);
只要建表时存在勾连过程。如果没有直接后继，必须遵循“先右后左”的原则。先右后左就是指在链表的逻辑结构上的节点勾连时先勾连右边的节点。

(3)单链表查找

A.按序号查找

取第i个元素，从链表的头节点出发，顺链表一直找到第i个为止。（顺序存储结构）。

ElemType Get_Elem(int i,LinkList *L){
    int j=1;
    Lnode *p=L->next;
    while(p!=NULL && j<i){
        p=p->next;
        j++;
    }
    if(j!=i) return (-32768);
    else return p->data; //此时返回为NULL表示p的data太大
}
//时间复杂度为O(n)

B.按值查找

遍历整个链表

Lnode *Locate_Elem(Lnode *L,ElemType key){
    Lnode *p=L->next;
    while(p!=NULL&&p->data!=key)
        p=p->next;
    if(p->data==key) return p;
    else return NULL;
}

(4)单链表的插入

插入ai-1与ai之间，先右后左。

• 在第1个节点前插入q

  q->next=head->next;
  head->next=q;

• 在链表中间p后插入q

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

• 在链表末尾插入q

  p->next=q , q->next=NULL , p=q;

  算法描述

  void Insert_Lnode(Lnode *L,int i,ElemType e){
    int j=0; Lnode *p,*q;
    p=L->next;
    while(P!=NULL && j<i-1){
           p=p->next;
        j++;
    }
    if(j!=i-1) printf("the i doesnt exist");
    else {
        q=(Lnode *)malloc(sizeof(Lnode));
        q->data=e;
        q->next = p->next;
        p->next=q;     
    }
  }

(5)单链表的删除

A.按序号删除 （双指针法）

void Delete_LinkList(Lnode *L,int i){
    int j=1;  Lnode *p,*q;
    p=L;  q=L->next;
    while(p->next != NULL && j<i){
        p=q;
        q=q->next;
        j++;
    }
    if(j!=i) printf("the i doesn't exist");
    else {
        p->next=q->next;
        free(q);
    }
}

B.按值删除（必须双指针）

void Delete_Linklist_value(ElemType key,Linklist *L){
    Lnode *p=L, *q=L->next;
    while(q!=NULL && q->data != key){
        p=q;
        q=q->next;
    }
    if(q->data==key) {
        p->next=q->next;
        free(q);
    }else  printf("not exeist");
}

4.循环链表

整个链表的指针域构成一个环，判断是否为空链表的条件是head->next==head，判断是否是表尾p->next==head。

循环链表是带尾指针的，在表头插入新节点时间复杂度为O(1)；在表头删除节点O(1)；在表尾插入新节点O(1)；在表尾删除需要寻找前驱节点O(n)。

5.双向链表

拥有两个指针，一个指向pre，一个指向next。
双向链表的节点及其基本定义:

typedef struct Dulnode {
    ElemType data;
    struct Dlnode *prior,*next;
}Dulnode;

双向链表的基本操作:

(1)双向链表的插入

将值为e的节点插入双向链表中，在插入时仅指出前驱节点，勾连时必须注意先后次序。

S=(Dulnode *)malloc(sizeof(Dulnode);
S->data=e;
S->next=p->next;
p->next->prior=S;
p->next=S;
S->prior=p;

(2)双向链表的节点删除

设要删除的节点为p。删除时可以不引入新的辅助变量，可以先断链。

p->prior->next=p->next;
p->next->prior=p->prior;
free(p);

6.静态链表

借助数组描述，静态链表有以下三个特性：连续空间段；通过修改指针域来实现插入删除；一次性分配储存空间。

typedef struct{
    ElemType data;
    int cur;
}component,SLinkList[MAXSIZE];
//cur为数组下表因此为整数

静态链表的查找

int locate_elem_SL(SLinklist S,ElemType e){
    i=S[0].cur;
    while(i && S[i].data!=e)
        i=S[i].cur;
    return i;
}

问题与说明

单链表删除的变形：

• A.删除值为key的所有节点

  void Delete_Linklist_node(Linklist *L,int key){
    Lnode *p=L,*q=L->next;
    while( q != NULL){
        if(q->data==key){
            p->next=q->next;
            free(q);
            q=p->next;
        }else {
            p=q;
            q=p->next;
        }
    }
  }

• B.删除所有值重复的节点

第一种是O(n^2)的方法

void Delete_Linklist_value(Lnode *L){
    Lnode *p=L,*q,*ptr;
    while(p!=NULL){
        q=p;
        ptr=q->next;
        while(ptr!=NULL){
            if(ptr->data==p->data){
                q->next=ptr->next;
                free(ptr);
                ptr=q->next;
            }else {
                q=ptr;
                ptr=ptr->next;
            }
        }
        p=p->next;
    }
}

第二种是利用map来存值，只需要O(n)

void Delete_Linklist_value(Linklist *L){
    Lnode *p,*q;
    p=L;q=L->next;
    int a[32767]=0;
    while(q!=NULL){
        if(a[q->data]){
            p->next=q->next;
            free(q);
            q=p->next;
        }else{
            a[q->data]++;
            p=q;
            q=p->next;
        }
    }
}

约瑟夫问题

问题描述：n个人围成一圈，第一个人从1开始报数，报到第m个数的人出去，从下一个人开始从1开始重新报数，直到只剩下一个人。

第一种方法利用count计数：

void play(List head,int m,int n){
    List p,q;int count,k;
    p=head ;
    count=1;
    k=n;
    while(k>1){
        if(count==m-1){
            q=p->next;
            p->next=q->next;
            printf("%d",p->data);
            free(q);
            count=0;
            --k;
        }else {
            count++;
            p=p->next;
        }
    }
    printf("Winner"+p->data);
}

第二种方法：

void Josephus(List h,int n,int m){
    Node *p=h,*pre =NULL;
    int i,j;
    for(i=0;i<n-1;++i){
        for(j=1;j<m;++j){
            pre = p;
            p=p->next;
        }
        pre->next=p->next;
        free(p);
        p=pre->next;
    }
    printf("Winner"+p->data);
}

备注

C语言实现 Clion集成开发环境

程序清单

C语言实现

#include <iostream>
#include <bits/stdc++.h>
#include "mylist.h"
#define MAXSIZE 1000 //the longest length of linklist

typedef struct  LNode{
    ElemType  data;
    struct LNode *next;
}LNode, * LinkList;
typedef int Status;
LNode *p;
int j=0;
Status GetElem_L(LinkList L,int i,ElemType &e) {
    // L is the header pointer of single link-list
    //when the ith element exist, the ith value arrange to e and return OK,otherwise return ERROR
    p = L->next;
    j = 1;  //initialize ,p point to the first node,j is counter
    while (p && j < i) {   //follow the pointer to search, until the p point to ith element or p is null
        p = p->next;
        ++j;
    }
    if (!p || j > i) return 0; //the ith element doesn't exist
    e = p->data;     // is ith element exist
    return 1;
}//GetElem_L
//Algorithm 2.8
Status ListInsert_L(LinkList &L,int i,ElemType e){
    //Insert the e above the ith element of the link-list
    p = L; j = 0;
    while(p && j<i-1){ p =p->next;++j;} // search the i-1th node
    if(!p||j>i-1) return 0;
    LNode *s;
    s = (LinkList)malloc(sizeof(LNode));
    s->next = p->next;
    s->data=e;
    p->next = s;
    return 1;
}
//Algorithm 2.9
Status ListDelete_l(LinkList &L, int i,ElemType &e){
    //Delete the ith element and use e to return the value of ith element
    LNode *q;
    p = L;
    j = 0;
    while (p->next && j<i-1){
        //search the ith element
        p=p->next;
        ++j;
    }
    if(!(p->next) || j>i-1) return 0; // the delete location is not value
    q = p->next;
    p->next=q->next;
    e = q->data;shixianshixian
    free(q);
    return 1;
}//ListDelete_L

//Algorithm 2.10
void CreatList_L(LinkList &L,int n){
    // inverse input the n element ,establish a linklist
    L = (LinkList)malloc(sizeof(LNode));
    L->next=NULL;
    for(int i =n;i>0;--i){
        p = (LinkList)malloc(sizeof(LNode));  //generate a new node
        scanf(&p->data);
        p->next = L->next;
        L->next = p;
    }
}//CreateList_L

//Algorithm 2.11
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
    // the La & Lb element's values increasing
    // the new Link-list Lc is also increasing
    LNode *pa = La->next;
    LNode *pb = Lb->next;
    LNode *pc = La;
    Lc = pc;            // using the header node of La as the header node of 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;  // Insert the extra list
    free(Lb);               // free the header node of Lb
}//MergeList_L

//Algorithm 2.12
typedef struct{
    ElemType data;
    int cur;
}component,SLinkList[MAXSIZE];
int LacateElem_SL(SLinkList S,ElemType e){
    //find the first element which value equal to e of L
    //if find the element return the locate of the element.otherwise return 0
    int i = S[0].cur;
    while (i&& S[i].data !=e) i = S[i].cur;
    return i;
}//LocateElem_SL

//Example 2-3
void InitSpace_SL(SLinkList &space){
    //link the array space ,the head pointer is space[0].cur
    //"0" represent null pointer
    for(int i=0;i<MAXSIZE-1;i++) space[i].cur=i+1;
    space[MAXSIZE-1].cur = 0;
}// InitSpace_SL

//Algorithm 2.14
int Malloc_SL(SLinkList &space){
    //if the another space is not empty,return the malloc node ,otherwise return 0
    int i = space[0].cur;
    if(space[0].cur) space[0].cur = space[i].cur;
    return i;
}//Malloc_SL

//Algorithm 2.15
void Free_Sl(SLinkList &space ,int k){
    //put node which the tag is k into the another list
    space[k].cur= space[0].cur;
    space[0].cur=k;
}//Free_SL

void differnece(SLinkList &space ,int &S){
    //input the A and B elements, establish a linklist represent the (A-B)U(B-A)
    //s is the head pointer
    InitSpace_SL(space);
    S = Malloc_SL(space);
    r =S;
    scanf(m,n);
    for(j=1;j<=m;++j){
        i = Malloc_SL(space);
        scanf(space[i].data);
        space[r].cur=i;
        r=i;      
    }
}