数据结构和算法学习记录（持续更新）

数据结构和算法学习记录

前言

程序是数据结构和算法的结合，数据结构是相互之间存在的一种或多种特定关系的数据元素的集合。包括4类基本的结构:集合、线形结构、树形结构、图状或网状结构。通俗点就是数据的逻辑结构，比方说这些数据在内存中以什么样的结构存放。
算法实际是编程过程中完成一件事采用的方法。好的算法可以在同样的运行过程中降低程序的运行消耗。

一、线性表

线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的。线性表的逻辑结构简单，便于实现和操作。因此，线性表这种数据结构在实际应用中是广泛采用的一种数据结构。
线性表可以顺序表示和链式表示，这里介绍顺序表和链表。

1.顺序表

先定义好线性表，然后就可以对它进行操作了，常见的线性表的基本操作有：创建线性表、查找元素、插入元素、删除元素、改变元素、清空、等。
定义结构体：

#define MAXDATA 100
typedef int data_t;
typedef struct{
   data_t data[MAXDATA];
   int last;
}seqlist_t;

创建：

seqlist_t *creat_seqlist(void)
 {
   seqlist_t *L=NULL;
   L=malloc(sizeof(seqlist_t));
   if(L==NULL)
   {
      puts("no memory");
      return NULL;
   }
	L->last=-1;                                                      
	return L;
 }

置空：

void clear_seqlist(seqlist_t *L)
{
   if(L==NULL)
   {
       puts("seqlist is null");
      return;
   }
  	free(L);
	return;
}

求长：

int get_len_empty(seqlist_t *L)
{
   if(L==NULL)
   {
      puts("seqlist is null");
      return -1;
   }
   return L->last;
}

判断表是否为空：

int is_empty_seqlist(seqlist_t *L)
{
    if(L==NULL)
    {
        puts("seqlist is null");
        return -1;
    }
    return(L->last==-1);
}

判断表是否为满：

int is_full_seqlist(seqlist_t *L)
{
   if(L==NULL)
   {
       puts("seqlist is null");
       return -1;
	}                                                                
   return(L->last==MAXDATA-1);
}

显示：

 void show_seqlist(seqlist_t *L)
{
   int i;                                                           
   for(i=0;i<=L->last;i++)
   {
       printf("%d\n",L->data[i]);
   }
   return;
}   

插入元素：

int insert_seqlist(seqlist_t *L,data_t x,int pos)
{
   int i;
   if((is_full_seqlist(L)||(pos<0)||(pos>L->last+1)))
   {
       puts("please input right information");
       return -1;
   }
   for(i=L->last;i>=pos;i--)
   {
 	   L->data[i+1]=L->data[i];
   }
   L->data[pos]=x;
   L->last++;
   return 0;
}

删除元素：

int delete_seqlist(seqlist_t *L,int pos)
{
   int i;
   if(L==NULL)
   {
       puts("seqlist is null");
      return -1;
   }
   for(i=pos;i<=L->last;i++)
   {
       L->data[i]=L->data[i+1];
   }
   L->last--;
   return 0;
}

改变元素：

int change_seqlist(seqlist_t *L,data_t x,int pos)
{
   if((pos<0)||(pos>L->last))
   {
      puts("error");
      return -1;                                                   
   }
   L->data[pos]=x;
   return 0;
}

查找元素：

int search_seqlist(seqlist_t *L,data_t x)
{
   int i;
   for(i=0;i<=L->last;i++)
   {
      if(L->data[i]==x)
   	  {                                                            
      printf("pos is %d\n",i);
      }
   }
    return 0;
}

2.链表

链表中一个数据元素占有一个节点，节点由两个部分组成，一是数据域，用来存放有效数据元素；二是指针域，用来指向下一个节点，链表的创建应当先创建节点，再把节点链接。

单链表

单链表

循环链表

循环链表

二、栈

三、列表

四、树和二叉树