线性表

最简单的一种数据结构

1. 线性表

• 数据对象：n个元素构成的有序序列

• 操作集

  • list init_list()
  • element_type find_kth(list L, int k)
  • int find(element_type x, list L)
  • void insert(element_type x, int i, list L)
  • void delete(int i, list L)
  • int length(list L)

• 存储方式

  • 数组
  • 链表

2. 实现方式

2.1 顺序存储

• 定义

  struct LNode{
      element_type data[MAX];
  	int last;
  }list, *Plist;

• 创建

  plist
      init_list()
  {
      plist p_list;
      p_list = (plist)malloc(sizeof(struct LNode));
      p_list->last = -1;
      return p-list;
  }

• 查找

  int find(element_type x, plist p_list)
  {
      int i = 0;
      while(i <= p_list->last && p_list->data[i]!=x)
          i++;
     if(i > p_list->last)
         return -1;
      else
          return i;
  }

• 插入

  void insert(element_type x, plist p_list, int i)
  {
      int j;
      if(p_list->last == MAX - 1)
          return;
      
      if(i<1 || i>p_list->last+1)//落在1和n+1之间，last是表长度-1
          return -1;
      for(j = p_list->last;j>=i-1;j--)//将从下标为1的开始全部后移一位
          p_list->data[j+1] = p_list->data[j];
      p_list->data[i-1] = x;
      p_list->last++;
      return;
  }

• 删除

  void delete(int i, plist p_list)
  {
  	int j;
      if(i<1||i>p_list->last+1)
          return -1;
      for(j=i; j<=p_list->last; j++)
          p_list->data[j-1] = p_list->data[j];
      p_list->last--;
      return;
  }

2.2 链式存储

• 定义

  typedef struct LNode
  {
  	element_type data;
  	LNode* next;
  }*plist;

• 求表长

  int length(plist p_list)
  {
      plist p = p_list;
      int j = 0;
      while(p)
      {
         p = p->next;
         j++;
      }
      return j;
  }

• 查找

  list find_kth(plist p_list)
  {
      plist p;
      p = p_list;
      int i = 1;
      while(p != NULL && i < k)
      {   p = p->next;
      	i++;
      }
      if(i == k) return p;
      else return NULL;
  }

  list find(element_type x, plist p_list)
  {
      plist p;
      p = p_list;
      while(p!=NUll&&p->data != x)
          p = p->next;
      return p;
  }

• 插入

  plist insert(element_type x,int i, plist p_list)
  {
     	plist p, s;
      if(i == 1)
      {
          s = (plist) malloc (sizeof(struct LNode));
          s->data = x;
          s->next = p_list;
          return s;
      }
      p = find_kth(i-1, p_list);
      if(p==NULL)
          return NULL;
      else
      {
          s = (plist)malloc(sizeof(struct LNode));
          s->data = x;
          s->next = p->next;
          p->next = s;
          return p_list;
      }
  }

• 删除

  plist delete(int i; plist p_list)
  {
      plist p ,s;
      if(i==1)
      {
          s = p_list;
          if(!p_list)
              p_lsit = p_list->next;
          else return NULL;
          free(s);
          return p_list;
      }
      p = find_kth(i-1, p_list);
      if(p == NULL)
          return NULL;
      else if(p->next == NULL)
          return NULL;
      else
      {
          s = p->next;
          p->next = s->next;
          free(s);
          return p_list;
  }