数据结构基础(一).顺序表

#include <stdio.h>  
#define LEN 100 //定义此表的最大长度

typedef struct line 
{
  int date[LEN]; //用来存放数据
  int last; //用来存放最后下标
}LIST,*LP; //为顺序表结构体重命名为LIST，为指针重命名为LP

int ifEmptyList(const LP head)  //用来判断此表是否为空
{
  if(-1 == head->last) return 0; //如果下标为-1就代表为空返回0，否则返回-1
  else return -1;
}

int showList(const LP head) //将列表中的所有元素进行打印
{
  int i=0;
  for(i=0;i < head->last+1;i++)printf("[%d]",head->date[i]);  //这里边际条件如果不是 head->last+1 就会忽略掉最后一个元素
  printf("\n");
  return 0;
}

int instNode(const LP head,int pos,int value)  //在列表中指定的位置插入一个值
{
  int i=0;
  if(head->last >= LEN-1) //通过最大下标判断此列表有没有满，如果满了，就警告退出
  {
    printf("the list is full\n");
    return -1;
  }
  if(pos < 0) pos=0; //对插入位置进行校正，位置为负时，定位到0位置
  if(pos > head->last+1) pos= head->last+1; //对插入位置进行校正，位置超出最后一个元素时，定位到末尾位置
  for(i=head->last;i>=pos;i--) head->date[i+1]=head->date[i]; //对数据进行迁移，这也是顺序表插入元素过程中，最耗时的步骤
  head->date[pos]=value;  //将值进行插入
  head->last++; //及时跟进最大下标
  return 0;
}

int delNode(const LP head,int pos) //在列表中指定的位置删除一个值
{
  int i=0;
  if(0 == ifEmptyList(head))return -1; //删除前进行一下检查，判断此表是否为空
  if(0 > pos)pos=0; //对删除位置进行校正，位置为负时，定位到0位置
  if(pos > head->last) pos=head->last; //对删除位置进行校正，位置超出最后一个元素时，定位到最后一个元素的位置
  for(i=pos;i < head->last ;i++)head->date[i]=head->date[i+1]; //对数据进行迁移，这也是顺序表删除元素过程中，最耗时的步骤
  head->last--; //及时跟进最大下标
  return 0;
}

int sortListAsc(const LP head) //对顺序表进行升序排序
{
  int i=0,j=0,tmp=0; 
  if(0 == ifEmptyList(head))return -1; //排序前进行一下检查，判断此表是否为空
  for(i=0;i < head->last;i++) //冒泡排序的思想进行排序
  {
    for(j=i+1;j < head->last+1;j++)
    {
      if(head->date[i] > head->date[j]) 
      {
	    tmp=head->date[i];
	    head->date[i]=head->date[j];
	    head->date[j]=tmp;
      }
    }
  }
  return 0;
}

int sortListDesc(const LP head) //对顺序表进行降序排序
{
  int i=0,j=0,tmp=0;
  if(0 == ifEmptyList(head))return -1; //排序前进行一下检查，判断此表是否为空
  for(i=0;i < head->last;i++) //冒泡排序的思想进行排序
  {
    for(j=i+1;j < head->last+1;j++)
    {
      if(head->date[i] <  head->date[j])
      {
	    tmp=head->date[i];
	    head->date[i]=head->date[j];
	    head->date[j]=tmp;
      }
    }
  }
  return 0;
}

int modifyNode(const LP head,int pos,int value) //表中指定位置的元素修改为新值
{
  if(0 == ifEmptyList(head))return -1; //修改前进行一下检查，判断此表是否为空
  if(pos > head->last || pos < 0) //对指定位置进行有效性检查，如果超出范围，进行提醒
  {
    printf("the pos is out of range [0,%d],and pos is %d\n",head->last,pos);
    return -1;
  }
  head->date[pos]=value; //指定位置的元素修改为新值
  return 0;
}

int getNode(const LP head,int pos) //获取表中指定位置元素的值
{
  if(0 == ifEmptyList(head))return -1; //查询前进行一下检查，判断此表是否为空
  if(pos > head->last || pos < 0) //对指定位置进行有效性检查，如果超出范围，进行提醒
  {
    printf("the pos is out of range [0,%d],and pos is %d\n",head->last,pos);
    return -1;
  }
  printf("the value of Node on pos %d  is [%d]\n",pos,head->date[pos]); //输出指定位置元素的值
  return 0;
}

int clearList(const LP head) //清空表
{
  head->last=-1; //因为最大下标对表里的元素有合法性的约束力，所以直接置-1就轻易的进行了清表操作，其实数据并没删除，但是已经不被认为合法
  return 0;
}

int main()
{
  //creat a list
  LIST list; //创建一个表
  LP l=&list; 
  l->last = -1; //将表的最大下标置-1，代表此表为空
  //show list
  printf("show this list\n"); 
  showList(l); //打印测试
  //add nodes to list
  printf("add 9 nodes to list\n"); 
  instNode(l,-100,3);
  instNode(l,0,2);
  instNode(l,100,7);
  instNode(l,100,9);
  instNode(l,2,19);
  instNode(l,5,88);
  instNode(l,100,99);
  instNode(l,100,11);
  instNode(l,100,44); //添加元素测试
  showList(l);
  //del a node from list
  printf("delete 5 nodes(-7,0,4,5,19) from list\n");
  delNode(l,-7);
  delNode(l,0);
  delNode(l,4);
  delNode(l,5);
  delNode(l,19); //分别取五个有代表性的位置进行删除测试
  showList(l);
  //sort list order by desc
  printf("sort list order by desc \n"); 
  sortListDesc(l); //降序排序测试
  showList(l);
  printf("sort list order by asc\n");
  //sort list order by asc
  sortListAsc(l); //升序排序测试
  showList(l);
  //modify a node value
  printf("modify node on 3 postion(-9,3,40)\n");
  modifyNode(l,-9,99);
  modifyNode(l,3,99);
  modifyNode(l,40,99); //修改值测试
  showList(l);
  //get a node value
  printf("get node on 3 postion(-1,2,90)\n");
  getNode(l,-1);
  getNode(l,2);
  getNode(l,90); //查询测试
  showList(l);
  //clear list
  printf("clear list\n");
  clearList(l); //清表测试
  showList(l);
  return 0;
}

emacs@ubuntu:~/c$ alias gtc
alias gtc='gcc -Wall -g -o'
emacs@ubuntu:~/c$ gtc toblog.x toblog.c
emacs@ubuntu:~/c$ ./toblog.x 
show this list

add 9 nodes to list
[2][3][19][7][9][88][99][11][44]
delete 5 nodes(-7,0,4,5,19) from list
[19][7][9][88]
sort list order by desc 
[88][19][9][7]
sort list order by asc
[7][9][19][88]
modify node on 3 postion(-9,3,40)
the pos is out of range [0,3],and pos is -9
the pos is out of range [0,3],and pos is 40
[7][9][19][99]
get node on 3 postion(-1,2,90)
the pos is out of range [0,3],and pos is -1
the value of Node on pos 2  is [19]
the pos is out of range [0,3],and pos is 90
[7][9][19][99]
clear list

emacs@ubuntu:~/c$