数据结构【完整代码】之（C语言实现【顺序存储表、单链表】创建、插入、删除、查找、输出、求长度、合并的实现与测试）

本文包含两个文件的代码和一张测试效果图：

List.h文件：用于存储信息：存放函数、结构体、链表、变量名等
achieve.cpp文件：用于测试
效果图：（位于最下方）

List.h文件：

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 
typedef int ElemType;
typedef int Status;

//线性表-------------------------------------------------------------顺序表的基本操作实现（开始） 


typedef struct{
  ElemType data[MAXSIZE]; /*数组存储数据元素，最大个数为MAXSIZE*/ 
  int length;       /*当前线性表的长度*/ 
}SqList;

Status LineListInit(SqList *L){ /*【创建/初始化】*/ 
  int i;
  for(i = 0; i < MAXSIZE; i++){
    L->data[i] = 0;
  }
  L->length = 0;
  return OK;
}

Status LineListGetElem(SqList L, int i, ElemType *e){ /*根据元素序号【查找】元素*/ 
  if(L.length == 0 || i < 1 || i > L.length)
    return ERROR;
  *e = L.data[i-1];
  return OK;
}

Status LineListExistElem(SqList L, ElemType e){ /*根据已知值【查找】元素是否存在*/ 
  int k;
  if(L.length == 0)
    return ERROR;
  for(k = 0; k < L.length; k++){
    if(L.data[k] == e){
      return TRUE;
    }
  }
  return FALSE;
} 

Status LineListPrint(SqList L){  /*【输出】*/ 
  int k;
  for(k = 0; k < L.length; k++){
    printf("第%d个元素值为%d\n", k+1, L.data[k]);
  }
}

int LineListLength(SqList L){   /*【求长度】*/
  return L.length;
}

Status LineListInsert(SqList *L, int i, ElemType e){  //【插入】 
  int k;
  if(L->length == MAXSIZE || i < 1 || i > L->length + 1) /*顺序线性表已满或当i不在范围内时*/
    return ERROR;
  if(i <= L->length){ /*若插入数据位置不在表尾*/ 
    for(k = L->length - 1; k >= i - 1; k--) /*将要插入位置后数据元素向后移动一位*/ 
      L->data[k+1] = L->data[k];
  }
  L->data[i-1] = e; /*将新元素插入*/
  L->length++;
  return OK; 
} 

Status LineListDelete(SqList *L, int i, ElemType *e){ //【删除】 
  int k;
  if(L->length == 0 || i < 1 || i > L->length) /*线性表为空或删除位置不正确*/
    return ERROR;
  *e = L->data[i-1];
  if(i < L->length){ /*如果删除位置不是最后位置*/
     for(k = i; k < L->length; k++) /*将删除位置后继元素前移*/ 
      L->data[k-1] = L->data[k];
  }
  L->length--;
  return OK;
}

Status LineListUnion(SqList La, SqList Lb, SqList *Lc){
  Lc->length = La.length + Lb.length;
  int a, b, c; //用于标记La， Lb, Lc的下标
  a = 0;
  b = 0; 
  c = 0;
  while(a < La.length || b < Lb.length){
    if(a < La.length && b < Lb.length){
      if(La.data[a] < Lb.data[b]){
      Lc->data[c] = La.data[a];
      a ++;
      }
      else{
        Lc->data[c] = Lb.data[b];
        b ++;
      }
    }
    else if(a < La.length){
      Lc->data[c] = La.data[a];
      a ++;
    }
    else if(b < Lb.length){
      Lc->data[c] = Lb.data[b];
      b ++;
    }
    c ++;
  }
  return OK;
}

//线性表--------------------------------------------------------------------顺序表的基本操作实现（结束） 

//线性表--------------------------------------------------------------------单链表的基本操作实现（开始） 


typedef struct Node{
  ElemType data;
  struct Node *next;
}Node;
typedef struct Node *LinkList; /*定义LinkList*/

Status LinkListGetElem(LinkList L, int i, ElemType *e){ /*根据元素序号【查找】元素*/ 
  int j;
  LinkList p;
  p = L->next; /*让p指向链表L的第一个结点*/
  j = 1;    /*j为计数器*/ 
  while(p && j < i){ /*寻找第i个结点（因为之前p = L->next）*/
    p = p->next;
    ++j;
  }
  if(!p || j>i)
    return ERROR; /*第i个结点不存在*/ 
  *e = p->data;
  return OK; 
}

Status LinkListExistElem(LinkList L, ElemType e){  /*根据已知值【查找】元素是否存在*/ 
  LinkList p;
  p = L->next; /*让p指向链表L的第一个结点*/
  while(p){
    if(p->data == e){
      return TRUE;
    }
    p = p->next;
  }
  if(!p)
    return ERROR;
}

Status LinkListInsert(LinkList *L, int i, ElemType e){ //【向后插入】
  int j;
  LinkList p, s;
  p = *L;
  p = p->next;
  j = 1;
  while(p && j < i){ //寻找第i个结点
    p = p->next;
    ++j;
  }
  if(!p || j > i)
    return ERROR; //第i个结点不存在
  s = (LinkList)malloc(sizeof(Node));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return OK;
}

Status LinkListDelete(LinkList *L, int i, ElemType *e){  //【删除】 
  int j;
  LinkList p, q;
  p = *L;
  j = 1;
  while(p->next && j < i){ /*寻找第i-1个结点*/ 
    p = p->next;
    ++j;
  }
  if(!(p->next) || j > i)
    return ERROR;
  q = p->next;
  p->next = q->next;
  *e = q->data;
  free(q);
  return OK;
}

int LinkListLength(LinkList L){ //【求长度】 
  int length;
  LinkList p;
  length = 0;
  p = L->next;   /*p指向第一个结点*/
  while(p){
    length++;
    p = p->next;
  } 
  return length;
}
/*
Status LinkListInsert(LinkList *L, int i, ElemType e){  //【插入】 
  int j;
  int length;
  LinkList p, s;
  p = *L;
  j = 0;
  length = LinkListLength(p);
  if(length == MAXSIZE || i < 1 || i > length + 1) //单链表已满或当i不在范围内时
    return ERROR;
  while(p && j < i-1){ //寻找第i-1个结点 
    p = p->next;
    j++;
  }
  if(!p)
    return ERROR;
  s = (LinkList)malloc(sizeof(Node));
  s->data = e;
  s->next = p->next;
  p->next = s;
  return OK;
}*/


Status LinkListInitHead(LinkList *L, int n){ //单链表的【创建（头插法）】 
  LinkList p;
  int i;
  *L = (LinkList)malloc(sizeof(Node));
  (*L)->next = NULL;
  for(i = 0; i < n; i++){
    p = (LinkList)malloc(sizeof(Node));
    p->data = 0;
    p->next = (*L)->next;
    (*L)->next = p;
  }
  return OK;
}

Status LinkListInitTail(LinkList *L, int n){ //单链表的【创建（尾插法）】 
  LinkList p, r;
  int i;
  *L = (LinkList)malloc(sizeof(Node));
  r = *L;
  for(i = 0; i < n; i++){
    p = (Node *)malloc(sizeof(Node));
    p->data = 0;
    r->next = p;
    r = p;
  }
  r->next = NULL;
  return OK;
} 

Status LinkListClear(LinkList *L){  //【清空】
  LinkList p, q;
  p = (*L)->next;    /*p指向第一个结点*/
  while(p){
    q = p->next;
    free(p);
    p = q;
  } 
  (*L)->next = NULL;
  return OK;
} 

Status LinkListPrint(LinkList L){ //【输出】
  int k; //记录元素序号 
  LinkList p;
  p = L->next;   /*p指向第一个结点*/
  k = 1;
  while(p){
    printf("第%d个元素值为%d\n", k, p->data);
    p = p->next;
    k++;
  } 
} 

Status LinkListUnion(LinkList La, LinkList Lb, LinkList *Lc){
  LinkList p;
  p = *Lc;
  La = La->next;
  Lb = Lb->next;
  while(La && Lb){
    if(La->data < Lb->data){
      p->next = La;
      p = La;
      La = La->next;
    }
    else{
      p->next = Lb;
      p = Lb;
      Lb = Lb->next;
    }
  }
  p->next = La ? La : Lb;
  return OK;
}

//线性表--------------------------------------------------------------------单链表的基本操作实现（结束）

achieve.cpp文件：

#include "List.h"

int main(){
  printf("//---------顺序表测试----------// \n");
  SqList Line;
  LineListInit(&Line); //【创建】 

  for(int i = 1; i <= 5; i++){
    LineListInsert(&Line, i, i+10); //【插入】 
  }

  LineListPrint(Line); //【输出】
  printf("\n"); 

  printf("线性表的长度为：%d\n", LineListLength(Line)); //【长度】
  printf("\n"); 

  int e;
  LineListDelete(&Line, 2, &e); //【删除】
  printf("被删除的元素值为：%d\n", e);
  LineListPrint(Line); //【输出】
  printf("\n"); 

  LineListGetElem(Line, 1, &e); //根据元素序号【查找】元素
  printf("第%d个元素值为：%d\n", 1, e);
  printf("\n"); 

  if(LineListExistElem(Line, 15)){ //根据元素值【查找】元素
    printf("存在%d\n", 15);
  }
  else{
    printf("不存在%d\n", 15);
  }
  printf("\n"); 


  SqList Linea, Lineb, Linec;
  LineListInit(&Linea);
  LineListInit(&Lineb);
  LineListInit(&Linec);
  for(int i = 1; i <= 5; i++){
    LineListInsert(&Linea, i, i+10); //【插入】（向前插入） 
  } 
  for(int i = 1; i <= 5; i++){
    LineListInsert(&Lineb, i, i+20); //【插入】（向前插入） 
  }
  LineListUnion(Linea, Lineb, &Linec); //【合并】 
  LineListPrint(Linec); 
  printf("\n"); 

  printf("//---------单链表测试----------// \n\n");
  LinkList Link;
  LinkListInitTail(&Link, 1); //【创建】(尾插法） 
  LinkListPrint(Link); //【输出】
  printf("\n"); 


  for(int i = 1; i <= 5; i++){
    LinkListInsert(&Link, i, i+10); //【插入】（向后插入） 
  }
  LinkListPrint(Link); //【输出】
  printf("\n"); 

  printf("线性表的长度为：%d\n", LinkListLength(Link)); //【长度】
  printf("\n"); 

  LinkListDelete(&Link, 2, &e); //【删除】
  printf("被删除的元素值为：%d\n\n", e); 
  LinkListPrint(Link); //【输出】
  printf("\n"); 

  LinkListGetElem(Link, 1, &e); //根据元素序号【查找】元素
  printf("第%d个元素值为：%d\n", 1, e);
  printf("\n"); 

  if(LinkListExistElem(Link, 15)){ //根据元素值【查找】元素
    printf("存在%d\n", 15);
  }
  else{
    printf("不存在%d\n", 15);
  }
  printf("\n"); 

  LinkList Linka, Linkb, Linkc;
  LinkListInitTail(&Linka, 1);
  LinkListInitTail(&Linkb, 1);
  LinkListInitTail(&Linkc, 1);
  for(int i = 1; i <= 5; i++){
    LinkListInsert(&Linka, i, i+10); //【插入】（向后插入） 
  } 
  for(int i = 1; i <= 5; i++){
    LinkListInsert(&Linkb, i, i+20); //【插入】（向后插入） 
  }
  LinkListUnion(Linka, Linkb, &Linkc); //【合并】 
  LinkListPrint(Linkc); 

}

效果图：