线性表

/* 顺序存储 */
#include <stdlib.h>
#include <stdio.h>

#define MAXSIZE 10

typedef struct node {                    /* 顺序表的类型 */
  int data[MAXSIZE];
  int length;
} SeqList;

void SeqListInit (SeqList *p, int n)         /* 顺序表初始化函数，其中参数n为初始化数据元素的个数 */
{
  int i;
  if (n > MAXSIZE)                 /* 数据元素的个数不能大于MAXSIZE，否则输出错误信息并返回 */
  {
    printf("error!\n");
    return;
  }
  for(i=0; i<n; i++)                     /* 将数据元素初始化为1~n */
  {
    p->data[i] = i + 1;
  }
  p->length = n;                     /* 初始化顺序表的长度 */
}

int main()
{
  SeqList sl;                        /* 定义顺序表 */
  int i;
  int n = 7;
  SeqListInit(&sl, n);                 /* 初始化顺序表 */
  printf("element (1~%d):\n", sl.length);
  for(i=0; i< sl.length; i++)                /* 输出顺序表的各数据元素 */
  {
    printf("%d ", sl.data[i]);
  }
  printf("\n");
  return 0;
}




/*链式存储 单链表*/
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
struct node {
  char data;                            /* 数据元素为单个字符 */
  struct node *next;
};
typedef struct node LinkList;                 /* 定义节点类型 */

LinkList *LinkListCreat()                    /* 创建单链表 */
{
  char ch;
  LinkList *p, *p1, *p2;
  p = (LinkList *)malloc(sizeof(LinkList));        /* 创建表头节点 */
  p->data = '\0';
  p->next = NULL;
  p1 = p;
  while ((ch = getchar()) != '\n')                /* 从键盘重复读入字符 */
  {
    p2 = (LinkList *)malloc(sizeof(LinkList));    /* 创建新节点 */
    p2->data = ch;                        /* 数据域设为读入的字符 */
    p2->next = NULL;                    /* 指针域设为空 */
    p1->next = p2;                        /* 添加到链表的末尾 */
    p1 = p2;
  }
  return p;                             /* 返回链表头指针 */
}

int main()
{
  LinkList *p, *q;
  p = LinkListCreat();                    /* 创建单链表 */
  q = p->next;
  printf("element:\n");
  while(q)                                /* 输出链表的各数据元素 */
  {
    printf("%c ", q->data);
    q = q->next;
  }
  printf("\n");
  return 0;
}


/*单链表应用*/
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

struct node {
  char data;                            /* 数据元素为单个字符 */
  struct node *next;
};
typedef struct node LinkList;                 /* 定义节点类型 */


LinkList *LinkListCreat()                    /* 创建单链表 */
{
  char ch;
  LinkList *p, *p1, *p2;
  p = (LinkList *)malloc(sizeof(LinkList));        /* 创建表头节点 */
  p->data = '\0';
  p->next = NULL;
  p1 = p;
  while ((ch = getchar()) != '\n')                /* 从键盘重复读入字符 */
  {
    p2 = (LinkList *)malloc(sizeof(LinkList));    /* 创建新节点 */
    p2->data = ch;                        /* 数据域设为读入的字符 */
    p2->next = NULL;                    /* 指针域设为空 */
    p1->next = p2;                        /* 添加到链表的末尾 */
    p1 = p2;
  }
  return p;                             /* 返回链表头指针 */
}

/*按序号查找节点*/
LinkList *ElemLocatebyNum(LinkList *p, int n)
{
    int i =1;
    LinkList *q;
    q = p;
    while (q != NULL)
    {
        if(n==i)
        {
            return p;
        }
        i++;
        q = q->next;
    }
    return NULL;
}

/*插入节点*/
int LinkListInsert(LinkList *p, int n, char ch)
{
    LinkList *p1, *p2;
    p1 = ElemLocatebyNum(p, n-1);
    if(p1 == NULL)
    {
        printf("error!\n");
        return -1;
    }
    p2 = (LinkList *)malloc(sizeof(LinkList));
    p2->data = ch;
    p2->next = p1->next;
    p1->next = p2;
    return 0;
}

/*删除节点*/
int LinkListDelete(LinkList *p, int n)
{
    LinkList *p1, *p2;
    p1 = ElemLocatebyNum(p, n-1);
    if(p1 == NULL)
    {
        printf("error!\n");
        return -1;
    }
    p2 = p1->next;
    p1->next = p2->next;
    free(p2);
    return 0;
}

int main()
{
  char x, ch;
  int n;
  LinkList *p, *q, *t;
  p = LinkListCreat();                    /* 创建单链表 */
  q = p->next;
  printf("Usage:\n");                        /* 输出帮助信息 */
  printf("p\t print the link list\n");
  printf("l\t locate a node\n");
  printf("i\t insert a node\n");
  printf("d\t delete a node\n");
  printf("q\t quit\n");
  printf("> ");                            /* 输出提示符 */
  while(1)
  {
    x = getchar();                        /* 获取命令字符 */
    if(x == '\n')                         /* 过滤命令字符后的回车符 */
    {
      printf("> ");
      continue;
    }
    switch (x)                            /* 根据命令字符，执行相应操作 */
    {
      case 'p':                         /* 输出链表的各数据元素 */
        while(q)
        {
          printf("%c ", q->data);
          q = q->next;
        }
        printf("\n");
        q = p->next;                     /* 命令执行完成后将指针指回原位置 */
        break;
      case 'l':                             /* 根据序号查找节点 */
        printf("input the number:\n");
        scanf("%d", &n);                 /* 输入节点序号 */
        t = ElemLocatebyNum(q, n);
        printf("%c ", t->data);                 /* 输出对应的数据元素 */
        break;
      case 'i':                             /* 插入节点 */
        printf("input the number:\n");
        scanf("%d", &n);                 /* 输入插入位置 */
        printf("input the character:\n");
        getchar();                        /* 过滤回车符 */
        ch = getchar();                    /* 输入要插入的字符 */
        LinkListInsert (q, n, ch);
        break;
      case 'd':                         /* 删除节点 */
        printf("input the number:\n");
        scanf("%d", &n);                 /* 输入节点序号 */
        LinkListDelete (q, n);
        break;
      case 'q':                         /* 退出程序 */
        return 0;
        break;
      default:                             /* 命令字符无法识别 */
        printf("error option!\n");
    }
  }
  return 0;
}