线性表链式存储的实现

C语言实现代码

预定义字符

//函数结果状态代码 
#define TRUE     1     //代码中出现TRUE相当于出现了1 
#define FALSE    0     //出现FALSE相当于出现了0 
#define OK       1     //出现OK相当于出现了1 
#define ERROR    0     //出现ERROR相当于出现了0 
#define INFEASIBLE    -1
#define OVERFLOW      -2 

typedef int Status;    //定义函数的返回状态 
typedef int ElemType; 

在这里使用了typedef定义了Status和ElemType为int类型，也就是说之后的代码当中如果出现了Status和ElemType，它们与int作用相同

1、单链表的构造

typedef struct LNode {
  ElemType data;                    // 结点数据域
  struct LNode *next;            // 结点指针域
}LNode, *LinkList;

2、初始化单链表（带头结点）

• 生成新结点作为头结点，用头指针L指向头结点
• 头结点的指针域为空

Status InitList(LinkList &L)
{// 构造一个空的单链表
  L = (LinkList) malloc (sizeof(LNode));
  if(!L) return ERROR;
  L -> next = NULL;
  printf("空的头结点创建成功\n");
  return OK;
}

在该函数传参时一定要在L之前加"&“符号，表示引用传递，保证形参和实参同时改变。
"->"是一个指针类型的运算符，它是用于指向结构体子数据的指针

3、线性表的赋值

Status SetList(LinkList &L, ElemType e)
{
  LinkList p;
  p = L;
  while (p -> next)
  {
    p = p -> next;
  }
  s = (LinkList)malloc(sizeof(LNode));
  s -> data = e;
  s -> next = p -> next;
  p -> next = s;
  return OK;
}

4、判断线性表是否为空

Status ListEmpty(LinkList L)
{
    if(L){
        if(L->next == NULL)        
        printf("线性表是空表\n");
        else
        printf("线性表不是空表\n");
    }
    else{
    printf("线性表不存在，无法判断\n");    
    }
    return OK;
}

在判断线性表是否为空时，首先判断头结点是否存在，当头结点存在时看头结点的指针域是否为空，当指针域为空时说明首元结点不存在，单链表是空表；当指针域不为空时说明存在首元结点，单链表不是空表。

5、线性表的销毁

Status DestroyList(LinkList &L)
{
  if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在\n");
        return ERROR;
    }
    LinkList p = L->next;    //使p指向单链表的首元结点  
    while(p != NULL){     //当p结点不为空时一直进入循环 
        free(L);          //释放L结点 
        L = p;            //将p结点赋值给L结点 
        p = L->next;      //将p结点赋值给L结点以后使p结点指向L的下一个结点 
    } 
    free(L);    //此时p的值为NULL，L指向尾结点，将其释放
    L = NULL;   
    printf("线性表已销毁\n"); 
}

6、线性表的清空

Status ClearList(LinkList &L)
{
  if (!L->next) 
  {
    printf("线性表为空表\n");
    return ERROR;
  }
  LinkList p, q;
  p = L->next;
  while (p)
  {
    q = p -> next;
    free(p);
    p = q;
  }
  L -> next = NULL;
  printf("线性表已清空");
  return OK;
}

7、线性表的表长

Status ListLength(LinkList &L)
{
  LinkList p;
  int i = 0;
  while (p)
  {
    i++;
    p = p -> next;
  }
  return i;
}

8、线性表的取值

Status GetElem(LinkList L,int i)
{// 在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
     p = L -> next;                                                 // 初始化，p指向首元结点，计数器j初值赋为1
  int j = 1;
  while (p && j < 1) {                                    // 顺链域向后扫描，直到p为空或p指向第i个元素
    p = p -> next;                                            // p指向下一个结点
    ++j;                                                                // 计数器j相应加1    
  }
  if (!p || j > i)
  {
    printf("当前位置没有元素\n");
    return ERROR;                // i值不合法i > n或i <= 0
  }
  printf("第%d个元素的值是：%d\n", i, p -> data);
  return OK;
}

9、单链表的插入

Status ListInsert(LinkList &L, int i, ElemType e)
{// 在带头结点的单链表L中第i个位置插入值为e的新结点
  p = L; j = 0;
  while (p && (j < i - 1)) {
    p = p -> next;                                                    // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!p || j > i - 1) 
  {
    printf("当前结点无法插入元素\n");
    return ERROR;                // i > n+1 或者 i < 1
  }
  s = new LNode;                                                        // 生成新结点*s
  s -> data = e;                                                        // 将结点*s的数据域置为e
  s -> next = p -> next;                                        // 将结点*s的指针域指向结点ai
  p -> next = s;                                                        // 将结点*p的指针域指向结点*s
  printf("插入元素成功\n");
  return OK;
}

10、单链表的删除

Status ListDelete(LinkList &L, int i)
{// 在带头结点的单链表L中，删除第i个元素
  LinkList p,q;
  p = L; 
  int j = 0;
  while ((p -> next) && (j < i - 1)) {
    p = p > next;                                                // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!(p -> next) || (j > i - 1)) 
  {
    printf("该位置无法删除元素\n");
    return ERROR;        // 当i > n 或 i < 1时删除位置不合理
  }
  q = p -> next;                                                                        // 临时保存被删除结点的地址以备释放
  p -> next = p -> next -> next;                                        // 改变删除结点前驱结点的指针域
  free(p);                                                                                  // 释放删除结点空间
  printf("当前位置元素已删除\n");
  return OK;
}

11、打印线性表

Status PrintList(LinkList L)
{
    if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在，无法打印\n");
        return ERROR;
    }
    LinkList p;
    p = L->next;    //将L的首元结点赋值给p ,为了不将头结点打印出来 
    while(p){
        printf(" %d",p->data);   //将p结点的数据域输出 
        p = p->next;    //结点不断的向后移动 
    }
    printf("\n");
    return OK;
}

代码：

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<windows.h> 

//函数结果状态代码 
#define TRUE     1     //代码中出现TRUE相当于出现了1 
#define FALSE    0     //出现FALSE相当于出现了0 
#define OK       1     //出现OK相当于出现了1 
#define ERROR    0     //出现ERROR相当于出现了0 
#define INFEASIBLE    -1
#define OVERFLOW      -2 

typedef int Status;    //定义函数的返回状态 
typedef int ElemType; 

typedef struct LNode {
  ElemType data;                    // 结点数据域
  struct LNode *next;            // 结点指针域
}LNode, *LinkList;

//构造一个空的头结点 
Status InitList(LinkList &L)
{// 构造一个空的单链表
  L = (LinkList) malloc (sizeof(LNode));
  if(!L) return ERROR;
  L -> next = NULL;
  printf("空的头结点创建成功\n");
  return OK;
} 

//对线性表进行赋值 
Status SetList(LinkList &L, ElemType e)
{
  LinkList p;
  p = L;
  while (p -> next)
  {
    p = p -> next;
  }
  s = (LinkList)malloc(sizeof(LNode));
  s -> data = e;
  s -> next = p -> next;
  p -> next = s;
  return OK;
}

//对线性表进行销毁
Status DestroyList(LinkList &L)
{
  if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在\n");
        return ERROR;
    }
    LinkList p = L->next;    //使p指向单链表的首元结点  
    while(p != NULL){     //当p结点不为空时一直进入循环 
        free(L);          //释放L结点 
        L = p;            //将p结点赋值给L结点 
        p = L->next;      //将p结点赋值给L结点以后使p结点指向L的下一个结点 
    } 
    free(L);    //此时p的值为NULL，L指向尾结点，将其释放
    L = NULL;   
    printf("线性表已销毁\n"); 
}

//对线性表进行重置
Status ClearList(LinkList &L)
{
  if (!L->next) 
  {
    printf("线性表为空表\n");
    return ERROR;
  }
  LinkList p, q;
  p = L->next;
  while (p)
  {
    q = p -> next;
    free(p);
    p = q;
  }
  L -> next = NULL;
  printf("线性表已清空");
  return OK;
}
 
//判断线性表是否为空
Status ListEmpty_L(LinkList L)
{
    if(L){
        if(L->next == NULL)        
        printf("线性表是空表\n");
        else
        printf("线性表不是空表\n");
    }
    else{
    printf("线性表不存在，无法判断\n");    
    }
    return OK;
}

//获取线性表的长度
Status ListLength(LinkList &L)
{
  LinkList p;
  int i = 0;
  while (p)
  {
    i++;
    p = p -> next;
  }
  return i;
}

//获取线性表某一位置对应的元素
Status GetElem(LinkList L,int i)
{// 在带头结点的单链表L中根据序号i获取元素的值，用e返回L中第i个数据元素的值
     p = L -> next;                                                 // 初始化，p指向首元结点，计数器j初值赋为1
  int j = 1;
  while (p && j < 1) {                                    // 顺链域向后扫描，直到p为空或p指向第i个元素
    p = p -> next;                                            // p指向下一个结点
    ++j;                                                                // 计数器j相应加1    
  }
  if (!p || j > i)
  {
    printf("当前位置没有元素\n");
    return ERROR;                // i值不合法i > n或i <= 0
  }
  printf("第%d个元素的值是：%d\n", i, p -> data);
  return OK;
}

//在线性表某一位置插入元素
Status ListInsert(LinkList &L, int i, ElemType e)
{// 在带头结点的单链表L中第i个位置插入值为e的新结点
  p = L; j = 0;
  while (p && (j < i - 1)) {
    p = p -> next;                                                    // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!p || j > i - 1) 
  {
    printf("当前结点无法插入元素\n");
    return ERROR;                // i > n+1 或者 i < 1
  }
  s = new LNode;                                                        // 生成新结点*s
  s -> data = e;                                                        // 将结点*s的数据域置为e
  s -> next = p -> next;                                        // 将结点*s的指针域指向结点ai
  p -> next = s;                                                        // 将结点*p的指针域指向结点*s
  printf("插入元素成功\n");
  return OK;
}

//删除线性表某一位置的元素
Status ListDelete(LinkList &L, int i)
{// 在带头结点的单链表L中，删除第i个元素
  LinkList p,q;
  p = L; 
  int j = 0;
  while ((p -> next) && (j < i - 1)) {
    p = p > next;                                                // 查找第i - 1个结点，p指向该结点
    ++j;
  }
  if (!(p -> next) || (j > i - 1)) 
  {
    printf("该位置无法删除元素\n");
    return ERROR;        // 当i > n 或 i < 1时删除位置不合理
  }
  q = p -> next;                                                                        // 临时保存被删除结点的地址以备释放
  p -> next = p -> next -> next;                                        // 改变删除结点前驱结点的指针域
  free(p);                                                                                  // 释放删除结点空间
  printf("当前位置元素已删除\n");
  return OK;
}

//打印线性表
Status PrintList(LinkList L)
{
    if(!L){            //如果线性表不存在，返回ERROR 
        printf("线性表不存在，无法打印\n");
        return ERROR;
    }
    LinkList p;
    p = L->next;    //将L的首元结点赋值给p ,为了不将头结点打印出来 
    while(p){
        printf(" %d",p->data);   //将p结点的数据域输出 
        p = p->next;    //结点不断的向后移动 
    }
    printf("\n");
    return OK;
}

int main(){
    SetConsoleTitle("java小豪");              //控制windows终端控制台的名称 
    LinkList L = NULL;                                   //声明线性表的头结点，但是并未进行初始化 
    int choose,i,e,n,v,k;
    while(1){
        printf("*****************************************\n");
        printf("*                                       *\n");
        printf("*  线性表的链式表示和实现：             *\n");
        printf("*                                       *\n");
        printf("*    1.  构造一个空的头结点             *\n");
        printf("*    2.  对线性表进行赋值               *\n");
        printf("*    3.  对线性表进行销毁               *\n");
        printf("*    4.  对线性表进行重置               *\n"); 
        printf("*    5.  判断线性表是否为空             *\n");
        printf("*    6.  获取线性表的长度               *\n");
        printf("*    7.  获取线性表某一位置对应的元素   *\n");
        printf("*    8.  在线性表某一位置插入元素       *\n");
        printf("*    9.  删除线性表某一位置的元素       *\n");
        printf("*    12. 打印线性表                     *\n");
        printf("*    13. 退出                           *\n");
        printf("*                                       *\n");
        printf("*****************************************\n");
        printf("请做出您的选择：");
        scanf("%d",&choose);
        switch(choose){
            case 1:InitList(L);break;
            case 2:{
                if(L){      //对线性表赋值的前提是线性表的头结点存在 
                    printf("请输入线性表元素的个数：");
                    scanf("%d",&n);
                    if(n > 0){
                        for(int i = 1;i <= n;i++){
                        printf("请输入第%d个元素的值：",i);
                        scanf("%d",&v);
                        SetList(L,v);
                        }
                    printf("线性表赋值成功\n");
                    }
                    else
                    printf("请输入一个有效数字\n");
                }
                else
                printf("线性表不存在，无法赋值\n"); 
                }
            break;
            case 3:DistoryList(L);break;
            case 4:ClearList(L);break;
            case 5:ListEmpty(L);break;
            case 6:{
                int ans = ListLength(L,1);
                printf("线性表的长度为：%d\n",ans-1);
            };break;
            case 7:{ 
                printf("请输入要获取元素的位置：");
                scanf("%d",&i);
                GetElem(L,i); 
            }
            break;
            case 8:{
                printf("请输入插入元素的位置：");
                scanf("%d",&i);
                printf("请输入插入元素的值：");
                scanf("%d",&e);
                ListInsert(L,i,e);
            }
            break;
            case 9:{
                printf("请输入要删除元素的位置：");
                scanf("%d",&i);
                DeleteList(L,i);
            }
            break;
            
            case 12:PrintList(L);break;
            case 13:exit(0);
        }
    }
    return 0;
}