乐趣区

数据结构单链表的实现和基本操作

jiezi

单链表是不同于顺序表的另一种线性结构，每一个结点包含了数据域和指针域，可通过每一结点的指针域直接访问下一个结点，顾名思义，是一种链式结构。
本次实现的功能包括：

  1. 构建空表
  2. 插入元素
  3. 删除元素
  4. 查找元素
  5. 交换相邻元素 
#include<stdio.h>
#include<stdlib.h>
#include "malloc.h" 

#define TRUE         1
#define FALSE        0
#define OK           1
#define ERROR        0
#define INFEASIBLE   -1
#define OVERFLOW     -2

typedef int Status;
typedef struct LNode{
    int data;
    struct LNode *next;
}LNode,* Linklist; 

Status InitList(Linklist &L){
    // 构造空表
    L = (Linklist)malloc(sizeof(LNode));
    L->data = NULL;
    L->next = NULL;
}     
Status ListInsert_L(Linklist &L,int i){
    // 在带头结点的单链线性表 L 中第 i 个位置插入键盘输入的数
    int e,j = 0;
    scanf("%d",&e);
    Linklist p;
    p = L; 
    while(p && j < i-1){p = p->next; ++j;} // 找到链表中第 i - 1 个元素
    if(!p || j>i-1)return ERROR;
    Linklist s = (Linklist)malloc(sizeof(LNode));
    s->data = e;s->next = p->next;
    p->next = s;
    return OK; 
}
Status Elem_search(Linklist L){
    // 查找链表中指定元素
    printf("您要查找哪个位置的数 \n");
    int i,j = 0;
    Linklist p = L;
    scanf("%d",&i);
    while(p && j < i) {p = p->next;++j;} // 找到链表中第 i 个元素
    if(!p || j > i)return ERROR;
    printf("您查找的数是：%d\n",p->data);
    return OK;
}
Status List_print(Linklist L){
    // 打印链表
    Linklist p;
    p = L;
    printf("现有的单链表为:\n");
    p = p->next;
    while(p->next != NULL) {printf("%d",p->data);p = p->next;}
    printf("%d",p->data);
    printf("\n");
    return OK;
}
Status ListDelete_L(Linklist &L){
    // 删除指定元素，并输出
    printf("请输入要删除元素的位置：\n");
    int i;
    scanf("%d",&i);
    Linklist p = L;
    int j = 0;
    while(p->next && j<i-1){p = p->next;++j;} // 找到链表中第 i - 1 个元素
    if(!(p->next)||j>i-1)return ERROR; // 保证链表有第 i 个元素
    Linklist q = p->next;
    p->next = q->next;
    printf("%d 被删除了 \n",q->data);
    free(q); 
    return OK;
}
Status List_exchange(Linklist &L){
    // 交换指定元素与他后面一个元素的值
    printf("请输入要交换元素的位置：\n");
    int a,b,j = 0;
    scanf("%d",&a);
    Linklist p = L;
    while(p && j<a){p = p->next;++j;} // 找到链表第 a 个元素
    if(!(p->next)||j>a)return ERROR; // 保证链表有第 a + 1 个元素
    b = p->data;p->data = p->next->data;p->next->data = b;
    printf("位置 %d 和位置 %d 交换了 \n",a,a+1);
    return OK;
}
int main(){
    Linklist L;
    InitList(L);
    printf("请依次输入四个整数：\n");
    for(int r=1;r <= 4;r++)ListInsert_L(L,r);
    List_print(L);
    printf("请输入插入的位置和数 ( 用换行分开)：\n");
    int a;
    scanf("%d",&a);
    ListInsert_L(L,a);
    List_print(L);
    Elem_search(L);
    ListDelete_L(L);
    List_print(L);
    List_exchange(L);
    List_print(L);
}

单链表的基本操作和顺序表无异，但需要注意：访问顺序表中某一个元素时可直接访问，访问单链表中的某一元素则需要从头结点依次访问。

所用的编译器是 dev c++.

退出移动版