[C++知识库]LinuxC应用开发学习笔记（四）--数据结构

数据结构

1、线性表

线性表的头文件

#ifndef SQLIST_H__
#define SQLIST_H__

#define DATASIZE  1024 
typedef int datatype;

typedef struct node_st
{
    datatype data[DATASIZE];
    int last;
    /* data */
}sqlist;
sqlist *sqlist_create();

void sqlist_creat1(sqlist **);

int sqlist_insert(sqlist *,int i,datatype *);

int sqlist_delete(sqlist *,int i);

int sqlist_find(sqlist *,datatype *);

int sqlist_isempty(sqlist *);

int sqlist_setempty(sqlist *);

int sqlist_getnum(sqlist *);

void sqlist_display(sqlist *);

int sqlist_destory(sqlist *);

int sqlist_union(sqlist *,sqlist *);

#endif // !SQLIST_H__

线性表的C文件

#include <stdio.h>
#include "sqlist.h"
#include <stdlib.h>

#define DATASIZE  1024 
typedef int datatype;


sqlist *sqlist_create()
{
    sqlist *me;
    me = malloc(sizeof(*me));
    if (me == NULL)
    {
        return NULL;
    }
    me->last = -1;
    return me;

}

void sqlist_creat1(sqlist **ptr)
{
    *ptr = malloc(sizeof(**ptr));
    if (*ptr == NULL)
    {
        return ;
    }
    (*ptr)->last =-1;
    return ;
    
}

int sqlist_insert(sqlist *me,int i,datatype *data){

    int j;
    if (me->last == DATASIZE-1)
    {
        return -1;
    }
    if (i<0 || i>me->last+1)
    {
        return -2;
    }

    for (j = me->last; i <= j; j--)
    {
        me->data[j+1] = me->data[j];
    }
    me->data[i] = *data;
    me->last++;
    return 0;
    
    
}

int sqlist_delete(sqlist *me,int i)
{
    int j;
    if (i< 0 || i> me->last)
        return -1;

    for ( j = i+1; j <= me->last;j++)
        me->data[j-1] = me->data[j];
    me->last--;
    return 0; 
}

int sqlist_find(sqlist *me,datatype *data)
{
    int i;
    
    if (sqlist_isempty(me) == 0)
      return -1;

    for (i = 0; i < me->last; i++)
        if (me->data[i] == *data)
            return i;
    return -2;

}

int sqlist_isempty(sqlist *me)
{
    if (me->last == -1)
    {
        return 0;
    }
    return -1;

    
    
}

int sqlist_setempty(sqlist *me)
{
    me->last = -1;
    return 0;
    
}

int sqlist_getnum(sqlist *me)
{
   return (me->last + 1);
}

void sqlist_display(sqlist *me)
{
    int i;
    if (me->last == -1)
    return;
    for ( i = 0; i <= me->last; i++)
    {
        printf("%d ",me->data[i]);
    }
    printf("\n");
    return;
}


int sqlist_destory(sqlist *me)
{
    free(me);
    return 0;  
}

int sqlist_union(sqlist *list1,sqlist *list2)
{
        // list 1-> 12 23 34 45 56
        // list 2-> 78 89 56 23 10
        int i;
        for(i=0;i <= list2->last;i++)
        {
            if (sqlist_find(list1,&list2->data[i])<0)
            {
                sqlist_insert(list1,0,&list2->data[i]);
            }
        }        
}

线性表的main.c文件

#include <stdio.h>
#include "sqlist.h"
#include <stdlib.h>

int main()
{
    sqlist *list = NULL;
    sqlist *list1 = NULL;
    datatype arr[] = {12,23,34,45,56};
    datatype arr1[] = {89,98,67,47,53};
    int i;
    int err;
    list = sqlist_create();
//    sqlist_creat1(&list);
    if(list == NULL)
    {
        fprintf(stderr,"sqlist_creat() failed!\n");
        exit(1);
    }

    list1 = sqlist_create();
    if (list1 == NULL)
    {
        fprintf(stderr,"sqlist1_creat() failed!\n");
        exit(1);
    }
    

 //   printf("%d %d\n",__LINE__,sizeof(arr)/sizeof(*arr));
    for ( i = 0; i < sizeof(arr)/sizeof(*arr); i++)
    {
         if((err = sqlist_insert(list,0,&arr[i]))!=0)
         {  
            if(err == -1)
                fprintf(stderr,"The arr is full.\n");
            else if (err == -2)
                fprintf(stderr,"The position you wan to insert is wrong.\n");
            
            else 
                fprintf(stderr,"error!");
            exit(1);
         }
    }
    
    sqlist_display(list);
    for (int  i = 0; i < sizeof(arr1)/sizeof(*arr1); i++)
    {
        sqlist_insert(list1,0,&arr1[i]);
    }
    sqlist_display(list);

    
    sqlist_delete(list,1);
//  printf("%d\n",ret);
    sqlist_display(list);
#if 0
    sqlist_union(list,list1);

    sqlist_display(list);

    sqlist_destory(list1);
#endif
    exit(0);
}

有头结点的单向链表

单向链表的.h文件

#ifndef LIST_H__
#define LIST_H__
typedef int datatype;
typedef struct node_st
{
    datatype data;
    struct node_st *next;
}list;

list* list_creat();

int list_insert_at(list *,int i,datatype *); 
int list_order_insert(list *,datatype *);
int list_delete_at(list*,int i,datatype *);
int list_delete(list *,datatype *);
int list_isempty(list *);
void list_display(list*);
void list_destory(list *);
#endif // !LIST_H__#define  "" 

单向链表的.c文件

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"

list* list_creat()
{
    //一个带头节点的单链表
    list *me;
    me =  malloc(sizeof(*me));
    if (me == NULL)
        return NULL;
    me->next = NULL;
    return me;
}

int list_insert_at(list *me,int i,datatype *data)
{
    int j = 0;
    list *node = me,*newnode;
    if (i<0)return -1;
    
    while (j<i&& node != NULL)
    {
        node = node->next;
        j++;
    }
    if (node)
    {
        newnode = malloc(sizeof(*newnode));
        if (newnode == NULL)
            return -2;
        newnode->data = *data;
        newnode->next == NULL;
        newnode->next = node->next;
        node->next = newnode;

        return 0;
        
    }
    else
        return -3;
    

} 
void list_display(list*me)
{
    list *node = me->next;
    if(list_isempty(me) == 0)
    {
        return;
    }
    while (node!=NULL)
    {
        printf("%d ",node->data);
        node = node->next;
    }
    printf("\n");
    return ;
}
int list_order_insert(list *me,datatype *data)
{
    list *p = me,*q;
    while (p->next && p->next->data<*data)
        p = p->next;
        q = malloc(sizeof(*q));
        if (q == NULL)
            return -1;
        q->data = *data;
        q->next = p->next;
        p->next = q;
        return 0;
}
int list_delete_at(list*me,int i,datatype *data)
{
   int j = 0;
   list *p = me,*q;

    *data = -1;

   if (i<0)
   {
       return -1;
   }
   
   while (j<i&&p)
   {
       p = p->next;
       j++;
   }
   if (p)
   {
       q = p->next;
       p->next = q->next;
       *data = q->data;
       free(q);
       q = NULL;
       return 0;
   }
   else
   {
       return -2;
   }
   
   
   
    
    

}
int list_delete(list *me,datatype *data)
{
    list *p = me,*q;
    while (p->next && p->next->data != *data)
    {
        p=p->next;
    }
    if (p->next == NULL )
        return -1;
    else
    {
        q = p->next;
        p->next = q->next;
        free(q);
        q = NULL;
    }

}
int list_isempty(list *me)
{
    if (me->next == NULL)    
        return 0;
    return 1;
    
}
void list_destory(list *me)
{
    list *node,*next;
    for(node = me->next;node!=NULL;node = next)
    {
        next = node->next;
        free(node);
    }
    free(me);
    return;
} 

单向链表表的main.c文件

#include <stdio.h>
#include <stdlib.h>
#include "linklist.h"
int main()
{
    list *l;
    int i,err;
    datatype arr[] = {12,9,23,2,34,6,45};
    l = list_creat();
    if (l == NULL)
    {
        exit(1);
    }

    for (i = 0; i < sizeof(arr)/sizeof(*arr); i++)
    {

       if(list_order_insert(l,&arr[i]))
       //if(list_insert_at(l,0,&arr[i]))
           exit(1);
    }

    list_display(l);
    datatype value;

    err = list_delete_at(l,2,&value);
    if (err)
    {
        exit(1);
    }
    list_display(l);
    printf("delete:%d\n",value);
    
#if 0
    int value = 12;
    list_delete(l,&value);
    list_display(l);
#endif
    list_destory(l);
    



    exit(0);

}

无头结点的单向链表

无头结点的单向链表.h文件

#ifndef NOHEAD_H__
#define NOHEAD_H__ 
#define NAMESIZE 32

struct score_st
{
    int id;
    char name[NAMESIZE];
    int math;
    int chinese;
};

struct  node_st
{
    struct score_st data;
    struct node_st *next;
};

int list_insert(struct node_st **,struct score_st *);

void list_show(struct node_st *);


int list_delete(struct node_st **);

struct score_st * list_find(struct node_st*,int id);

void list_destory(struct node_st* );

#endif // !1

无头结点的单向链表.c文件

#include <stdio.h>
#include <stdlib.h>
#include "noheadlink.h"

int list_insert(struct node_st **list,struct score_st *data)
{
    struct node_st *new;
    new = malloc(sizeof(*new));

    if (new == NULL)
    {
        return -1;
    }
    new->data = *data;
    new->next = *list;
    *list = new;
    
    return 0;
}

void list_show(struct node_st *list)
{
    struct node_st *cur;
    for (cur = list;cur != NULL;cur=cur->next)
    {
        printf("%d %s %d %d \n",cur->data.id,cur->data.name,cur->data.math,cur->data.chinese);
    }
    
}


int list_delete(struct node_st **list)
{
    struct  node_st *cur;
    if (*list == NULL)
    {
        return -1;
    }
    cur = *list;
    *list = (*list)->next;   
    free(cur);
    return 0;
}

struct score_st *list_find(struct node_st*list,int id)
{
    struct node_st *cur;
    for (cur  = list; cur != NULL;cur = cur->next)
    {
        if(cur->data.id == id)
            {
                return &cur->data;
            }
        

    }
    return NULL;
}

void list_destory(struct node_st* list)
{
    struct node_st *cur;
    if (list == NULL)
    {
       return;
    }
    for (cur = list;cur!= NULL;cur = list)
    {
        list = cur->next;
        free(cur);
    }
    

}

无头结点的main.c文件

#include <stdio.h>
#include <stdlib.h>
#include "noheadlink.h"

int main()
{
    struct node_st *list = NULL;
    struct score_st tmp;
    int i,ret;
    for ( i = 0; i < 7; i++)
    {
        tmp.id = i;
        snprintf(tmp.name,NAMESIZE,"std %d",i);
        tmp.math = rand()%100;
        tmp.chinese = rand()%100;
  
        ret = list_insert(&list,&tmp);  
        if (ret != 0)
        {
           exit(1);
        }
         
    }

    list_show(list);

    printf("\n\n");
//    list_delete(&list);
//    list_show(list);
    int id = 13;
    struct score_st *ptr;
    ptr = list_find(list,id); 
    if(ptr == NULL)
    {
        printf("can't find\n");
    }
    else
    {
       printf("%d %s %d %d \n",ptr->id,ptr->name,ptr->math,(*ptr).chinese);

    }

    list_destory(list);
    
    exit(0);
}

多项式合并的文件

#include <stdio.h>
#include <stdlib.h>

struct node_st
{
    int coef;//系数
    int exp;
    struct node_st *next;
};

struct node_st *ploy_create(int a[][2],int n)
{
    struct node_st *me;
    struct node_st *newnode,*cur;
    int i;
    me = malloc(sizeof(*me));
    if (me == NULL)
    {
        exit(1);
    }

    me->next = NULL;

    cur = me;

    for (i = 0;i<n;i++)
    {
       newnode = malloc(sizeof(*newnode));
        if(newnode == NULL)
        {
            return NULL;
        } 
           newnode->coef = a[i][0];
           newnode->exp  = a[i][1];
           newnode->next = NULL;

           cur->next = newnode;
           cur = newnode;
       
    }
    

    return me;
    

}


void poly_show(struct node_st *me)
{
    struct node_st *cur;
    for (cur = me->next;cur!=NULL;cur = cur->next)
    {
        printf("(%d %d) ",cur->coef,cur->exp);
    }
    printf("\n");

}

void poly_union(struct node_st *p1,struct node_st *p2)
{
    struct node_st *p,*q,*r;
    p = p1->next;
    q = p2->next;
    r = p1;

    while (p && q)
    {
        if (p->exp<q->exp)
        {
           r->next = p;
           r = p;
           p = p->next; 
        }
        else if (p->exp>q->exp)
        {
            r->next = q;
            r = q;
            q = q->next;
        }
        else
        {
              p->coef += q->coef;
              if (p->coef)
              {
                  r->next = p;
                  r = p;
              }
              p = p->next;
              q = q->next;     
        }  
    }
    if (p == NULL)
        r->next = q;
    else 
        r->next = p;

}
int main()
{
  int a[][2] = {{5,0},{2,1},{8,8},{3,16}};
  int b[][2] = {{6,1},{16,6},{-8,8}};
  
  struct node_st *p1,*p2;

    p1 = ploy_create(a,4);
        if (p1 == NULL)
        {
           exit(1);
        }
    p2 = ploy_create(b,3);
        if (p2 == NULL)
        {
            exit(1);
        }
  poly_show(p1);

  poly_show(p2);

  poly_union(p1,p2);

  poly_show(p1);
    

}

约瑟夫环问题

约瑟夫环的单向环链文件

//单项环链
#include <stdio.h>
#include <stdlib.h>
#define  JOSE_NR 8
struct node_st
{
    int data;
    struct node_st *next;
};

struct node_st *jose_create(int n)
{
    struct node_st *me;
    int i = 1;
    struct node_st *newnode,*cur;

    me = malloc(sizeof(*me));
    if (me == NULL)
        return NULL;
    me->data = i;
    me->next = me;
    i++;

    cur = me;
    for (;i<=n;i++)
    {
       newnode =  malloc(sizeof(*newnode));
       if(newnode == NULL)
            return NULL;
       newnode->data = i;
       newnode->next = me;

       cur->next = newnode;
       cur = newnode;
    } 
    return me;
}

void jose_show(struct node_st *me)
{
    struct node_st *list;
    for (list = me;list->next!=me;list = list->next)
    {
        printf("%d ",list->data);
    }
    printf("%d\n",list->data);
    
    
}

void jose_kill( struct node_st **me,int n)
{
    struct node_st *cur = *me,*node;
    int i = 1;
    while(cur != cur->next)
    {
        while (i<n)
        {
        node = cur;
        cur = cur->next;
        i++;
        }

        printf("%d ",cur->data);
        node->next = cur->next;
        free(cur);

        cur = node->next;
        i = 1;
    }

    *me = cur;
    printf("\n");
}


int main()
{
    struct node_st *list;
    int n = 3;
    list = jose_create(JOSE_NR);
    if (list == NULL)
    {
        exit(1);
    }
    
    jose_show(list);

    jose_kill(&list,3);

    jose_show(list);

    exit(0);
}