数据结构：线性表

线性表(单链表)C语言简单实现

#include 
#include 
#include 

#define _CRT_SECURE_NO_WARNINGS
#define ok 1
#define error -1

typedef int Elemtype;
typedef int Status;

//带头结点的
typedef struct LNode{
  Elemtype data;
  struct LNode *next;
}LNode, *LinkList; //*LinkList为LNode类型的指针

//头插法建立单链表（插入顺序和打印顺序相反）
LinkList HeadInsert(LNode *L,int n)
{
  LNode *s;
  int i;

  L = (LinkList)malloc(sizeof(LNode)); // 创建头结点的空间
  L->next = NULL;                      // 空链表
  
  for(i = 0; i < n; i++){
    s = (LNode *)malloc(sizeof(LNode));
    scanf("%d",&s->data);
    s->next = L->next;
    L->next = s;
  }
  printf("头插法建立单链表成功\n");
  return L;
}

//尾插法建立单链表（一样的顺序）
LinkList TailInsert(LinkList L,int n)
{
  int i;
  L = (LinkList)malloc(sizeof(LNode)); // 创建头结点的空间
  LNode *s, *r = L; //r为尾指针

  for(i = 0; i < n; i++){
    s = (LNode *)malloc(sizeof(LNode));
    scanf("%d",&s->data);
    r->next = s;
    r = s; // r 指向新的表尾结点
  }

  r->next = NULL; // 尾结点指针置为空
  printf("尾插法建立单链表成功\n");
  return L;
}

//按值查找表结点(返回指向e的指针)
LNode *LocateElem(LinkList L, Elemtype e)
{
  LNode *s = L->next; // 从第一个结点开始查找
  while(s&&s->data!=e){
    s = s->next;
  }
  return s;
}

//按序号查找表结点
LNode *GetElem(LinkList L, int pos)
{
  int j = 1; // 用于计数
  LNode *s = L->next; // 从第一个结点开始
  if(pos == 0)
    //返回值也为空
    return L;
  if(pos < 1)
    return NULL;
  while(s&&j<pos){ //从第一个结点开始，直到第pos个结点为止
    s = s->next;
    j++;
  }
  //找到了或者没找到为空
  return s;
}

//插入结点（i-1的位置后插法）
Status Insert(LinkList L, int pos)
{
  if(pos<0||pos>Length(L)+1)
    return error;
  
  LNode *s, *p;

  s = (LNode *)malloc(sizeof(LNode));
  printf("请输入要插入结点的值为:");
  scanf("%d", &s->data);

  p = GetElem(L,pos-1); // 插入位置的前驱结点
  s->next = p->next;
  p->next = s;

  return ok;
}

//插入结点扩展：（i位置后插入再交换data数据）
Status InsertExtension(LinkList L, int pos)
{
  if(pos<0||pos>Length(L)+1)
    return error;
  
  LNode *s, *p;
  int temp;

  s = (LNode *)malloc(sizeof(LNode));
  printf("请输入要插入结点的值为:");
  scanf("%d", &s->data);

  p = GetElem(L,pos);

  s->next = p->next;
  p->next = s;
  temp = p->data;
  p->data = s->data;
  s->data = temp;

  return ok;
}

//删除结点（找第i-1个结点删除其后继结点）
Status Delete(LinkList L, int pos)
{

  LNode *p, *q;

  if(pos<0||pos>=Length(L)+1)
    return error;

  p = GetElem(L,pos-1); // p 指向删除结点的前驱结点
  q = p->next; // q指向要删除的结点
  p->next = q->next;
  free(q);

  return ok;
}

//删除结点扩展：（找到后继结点将其值赋给要被删的结点，再将后继结点删除）
Status DeleteExtension(LinkList L, int pos)
{

  LNode *p, *q;

  if(pos<0||pos>=Length(L)+1)
    return error;

  p = GetElem(L,pos);
  q = p->next; // q为要被删除的结点的后继结点
  p->data = p->next->data; //将后继结点的值(q的值)赋值给p
  p->next = q->next;
  free(q);

  return ok;
}

//求表长
Status Length(LinkList L)
{
  LNode *s;
  s = L->next; 
  int i = 0;
  if(s == NULL){
    printf("空表\n");
    return error;
  }else{
    while(s != NULL){
      i++;
      s = s->next;
    }
    return i;
  }
  return error;
}

//打印链表
Status print(LinkList L)
{
  LNode *s = L->next;
  while(s){
    printf("%d ", s->data);
    s = s->next;
  }
  printf("\n");
  return ok;
}

int main()
{
  int t, n, m;
  int pos;
  Elemtype e;
  LinkList L;
  LNode *p; 
  while (1)
	{
		printf("================================\n");
		printf("         线性表(单链表)\n");
		printf("================================\n");
		printf("1:求表长        2:头插法           3:尾插法\n");
		printf("4:按值查找      5:按序号查找       6:插入结点\n");
    	printf("7:插入结点扩展  8:删除结点         9:删除结点扩展\n");
    	printf("10:打印链表     11:退出\n");
		printf("--------------------------------\n");
		printf("请选择:");
		scanf("%d", &t);
		switch (t) {
      case 1:
        n = Length(L);
        if(n != -1){
          printf("表长为:%d\n",n);
        }
        break;
      
      case 2:
        printf("请输入元素个数:");
        scanf("%d", &m);
        L = HeadInsert(L,m);
        break;
      case 3:
        printf("请输入元素个数:");
        scanf("%d", &m);
        L = TailInsert(L,m);
        break;

      case 4:
        printf("请输入要查找的元素:");
        scanf("%d", &e);
        p = LocateElem(L,e);
        if(p != NULL){
          printf("查找值:%d成功\n", p->data);
        }else{
          printf("没有此值\n");
        }
        break;
      case 5:
        printf("请输入要查找的序号:");
        scanf("%d", &pos);
        p = GetElem(L,pos);
        if(p){
          printf("找到序号为%d的元素值为:%d\n",pos,p->data);
        }else{
          printf("没找到\n");
        }
        break;

      case 6:
        printf("请输入要插入的位置:");
        scanf("%d", &pos);
        n = Insert(L,pos);
        if(n == -1){
          printf("插入的位置错误\n");
        }else{
          printf("插入成功\n");
          print(L);
        }
        break;
      case 7:
        printf("请输入要插入的位置:");
        scanf("%d", &pos);
        n = InsertExtension(L,pos);
        if(n == -1){
          printf("插入的位置错误\n");
        }else{
          printf("插入成功\n");
          print(L);
        }
        break;

      case 8:
        printf("请输入要删除的位置:");
        scanf("%d", &pos);
        n = Delete(L,pos);
        if(n == -1){
          printf("删除的位置错误\n");
        }else{
          printf("删除成功\n");
          print(L);
        }
        break;
      case 9:
        printf("请输入要删除的位置:");
        scanf("%d", &pos);
        n = DeleteExtension(L,pos);
        if(n == -1){
          printf("删除的位置错误\n");
        }else{
          printf("删除成功\n");
          print(L);
        }
        break;

      case 10:
        print(L);
        break;

      case 11:
        printf("单链表模拟结束Bye!\n");
				exit(0);
        break;
		}
	}
  return 0;
}