双向链表动态数组+链表排序

2019-07-21 02:08发布

算是一个个人学习记录吧,
传感器数据采集的时候总是会因为不能确定数组长度而造成了一系列问题。
然后就想起来了以前学的链表,就是着做了个类似于ArrayList的东西(差得远)。也算是没白学2333。

主函数
[mw_shl_code=applescript,true]#include "stdio.h"
#include "DynamicArray.h"
float test[] = {1.33,3.22,4.0,5.012,3.4456,23.44,11.56};
float test1[] = {3.33,5.22,6.0,7.012,8.4456,88.44,99.56,434,123.3};
int main(void)
{
        int i = 0;

        struct node * Frame_Head =         CreatLink();
        struct node * Frame_Head1 = CreatLink();
        AddNewArray(Frame_Head,test,sizeof(test)/sizeof(test[0]));
        AddNewArray(Frame_Head1,test1,sizeof(test1)/sizeof(test1[0]));
        InsertNew(Frame_Head,3,33.3);
        InsertNew(Frame_Head1,4,33.3);
        DeleteNew(Frame_Head,4);
        DeleteNew(Frame_Head1,3);
        Output_Link(Frame_Head,1);
        Output_Link(Frame_Head,0);
        Output_Link(Frame_Head1,1);
        Output_Link(Frame_Head1,0);
        printf(" Link_Sort ");
        Link_Sort(Frame_Head,0);
        Link_Sort(Frame_Head1,0);
        Output_Link(Frame_Head,0);
        Output_Link(Frame_Head1,0);
        getchar();
}[/mw_shl_code]

DynamicArray.h
[mw_shl_code=applescript,true]#ifndef __DynamicArray_H
#define __DynamicArray_H

#include "stdlib.h"
#include "string.h"
struct Cnode
{
        struct Cnode * head;
        struct Cnode * next;
        float data;
};
struct node
{
        struct Cnode * Common_node;
        int count;
};

/* Globe variate instrument*/
/* If necessary, this variate is able to point header(bottom) of links */
/* As usual,these variates are not recommanded,nonetheless,if only one link is set and these variates is available*/
struct Cnode * bottom;
struct Cnode * Header;

struct node * CreatLink(void);
struct Cnode * Get_Header(struct node * Frame);
struct Cnode * Get_Bottom(struct node * Frame);
void AddNew(struct node * Frame,float Data);
void Pop(struct node * Frame);
void AddNewArray(struct node * Frame,float Data[],int length);
int InsertNew(struct node * Frame,int order,float data);
int DeleteNew(struct node * Frame,int order);
void Link_Sort(struct node * Frame,int order);
void Qsort(float *a, int left, int right);
void Output_Link(struct node * Frame,int mode);
#endif
[/mw_shl_code]

DynamicArray.c
[mw_shl_code=applescript,true]#include "DynamicArray.h"
#include "stdio.h"

/* Function Name: CreatLink                           */
/* Function Effect: To creat a double linked list     */
/* Function Parameter: List header(struct node *)     */
/* Function Return : Link Header                      */
struct node * CreatLink(void)
{
        struct node * Frame = (struct node *)malloc(sizeof(struct node));
        struct Cnode * head = (struct Cnode *)malloc(sizeof(struct Cnode));
        head->next = NULL;
        head->head = NULL;
        Frame->Common_node = head;
        Frame->count = 0;
        return Frame;
}
/* Function Name: Get_Header                           */
/* Function Effect: To find header of List             */
/* Function Parameter: A Link(struct node *)           */
/* Function Return : List header                       */
struct Cnode * Get_Header(struct node * Frame)
{
        struct Cnode * Temp_Header = Frame->Common_node;
        while(Temp_Header->head!=NULL)
        {
                Temp_Header = Temp_Header->head;
        }
        return Temp_Header;
}
/* Function Name: Get_Bottom                           */
/* Function Effect: To find bottom of List             */
/* Function Parameter: A Link(struct node *)           */
/* Function Return : List bottom                       */
struct Cnode * Get_Bottom(struct node * Frame)
{
        struct Cnode * Temp_Bottom = Frame->Common_node;
        while(Temp_Bottom->next!=NULL)
        {
                Temp_Bottom = Temp_Bottom->next;
        }
        return Temp_Bottom;
}
/* Function Name: AddNew                                        */
/* Function Effect: add a new element to the bottom of the list */
/* Function Parameter: A Link(struct node *),element(float)     */
/* Function Return : none                                       */
void AddNew(struct node * Frame,float Data)
{
        struct Cnode * Temp_node =(struct Cnode *)malloc(sizeof(struct Cnode));
        struct Cnode * Node_Cpy = Frame->Common_node;
        unsigned int counter = Frame->count;
        while(counter--)
        {
                Node_Cpy = Node_Cpy->next;
        }
        Temp_node->data = Data;
        Temp_node->next = NULL;
        Temp_node->head = Node_Cpy;
        Node_Cpy->next = Temp_node;
        Frame->count = Frame->count + 1;
}
/* Function Name: AddNewArray                                        */
/* Function Effect: add a new array(float) to the bottom of the list */
/* Function Parameter: A Link(struct node *),array(float)            */
/* Function Return : none                                            */
void AddNewArray(struct node * Frame,float Data[],int length)
{
        unsigned int i = 0;
        for(;i<length;i++)
        {
                AddNew(Frame,Data);
        }
}
/* Function Name: Pop                                    */
/* Function Effect: delete element last one in list      */
/* Function Parameter: A Link(struct node *),order(int)  */
/* Function Return : none                                */
void Pop(struct node * Frame)
{
        struct Cnode * Temp_node =Get_Bottom(Frame);
        Temp_node = Temp_node->head;
        Temp_node->next->head = NULL;
        Temp_node->next=NULL;
        Frame->count = Frame->count - 1;
}
/* Function Name: InsertNew                                         */
/* Function Effect: To insert element in list with certain order    */
/* Function Parameter: A Link(struct node *),order(int),data(float) */
/* Function Return : result(1:success,0:fail)                       */
int InsertNew(struct node * Frame,int order,float data)
{
        int i = 0;
        struct Cnode * Temp_node =Get_Header(Frame);
        struct Cnode * Temp = (struct Cnode*)malloc(sizeof(struct Cnode));
        struct Cnode * Record;
        if(Temp_node->next!=NULL&&Frame->count>order&&order>0)
        {
                for(;i<order-1;i++)
                {
                        Temp_node = Temp_node->next;
                }
                Record = Temp_node->next;
                Temp->data = data;
                Temp->head = Record->head;
                Temp->next = Temp_node->next;
                Temp_node->next = Temp;
                Record->head = Temp;
                Frame->count = Frame->count + 1;
                return 1;
        }
        if(Frame->count==order)
        {
                AddNew(Frame,data);
        }
        return 0;
}
/* Function Name: DeleteNew                                         */
/* Function Effect: To delete element in list with certain order    */
/* Function Parameter: A Link(struct node *),order(int)             */
/* Function Return : result(1:success,0:fail)                       */
int DeleteNew(struct node * Frame,int order)
{
        int i = 0;
        struct Cnode * Temp_node =Get_Header(Frame);
        struct Cnode * Record;
        if(Temp_node->next!=NULL&&Frame->count>order&&order>0)
        {
                for(;i<order-1;i++)
                {
                        Temp_node = Temp_node->next;
                }
                if(Temp_node->next->next!=NULL)
                {
                        Record = Temp_node->next;
                        Temp_node->next = Record->next;
                        Record->next->head = Temp_node;
                        Frame->count = Frame->count - 1;
                }
                return 1;
        }
        if(Frame->count == order)
        {
                Pop(Frame);
                return 1;
        }
        return 0;
}
/* Function Name: Link_Sort                              */
/* Function Effect: To sort list with certain order      */
/* Function Parameter: A Link(struct node *),order(int)  */
/* Function Return : none                                */
void Link_Sort(struct node * Frame,int order)          //Bubble Sort  mode1 = ascend  mode0 = descend
{
        int i,j,q;
        float temp_float;
        int length = Frame->count;
        struct Cnode * record = Get_Header(Frame);
        struct Cnode * temp = record;
        for(i =1;i<length;i++)
        {
                for(j =1;j<=length-1;j++)
                {
                        temp = record;
                        for(q = 0;q<j;q++)
                        {
                                temp = temp->next;
                        }
                        if(order)
                        {
                                if(temp->data > temp->next->data)
                                {
                                        temp_float =temp->data;
                                        temp->data = temp->next->data;
                                        temp->next->data = temp_float;
                                }
                        }
                        else
                        {
                                if(temp->data < temp->next->data)
                                {
                                        temp_float =temp->data;
                                        temp->data = temp->next->data;
                                        temp->next->data = temp_float;
                                }
                        }
                }
        }
}
void Qsort(float *a, int left, int right)
{
    int i = left;
    int j = right;
    float key = a[left];
        if(left >= right)
    {
        return ;
    }
     
    while(i < j)
    {
        while(i < j && key <= a[j])
        {
            j--;
        }
         
        a = a[j];
        while(i < j && key >= a)
        {
            i++;
        }
         
        a[j] = a;
    }
     
    a = key;
    Qsort(a, left, i - 1);
    Qsort(a, i + 1, right);
}
void Output_Link(struct node * Frame,int mode) //mode1 start from header
                                                                                           //mode0 start form bottom
{
        if(mode)
        {
                Frame->Common_node = Get_Header(Frame);
                printf("%d ",Frame->count);
                while(Frame->Common_node->next!=NULL)
                {
                        Frame->Common_node =Frame->Common_node->next;
                        printf("%.3f  ",Frame->Common_node->data);       
                }
                printf(" ");
        }
        else
        {
                Frame->Common_node = Get_Bottom(Frame);
                printf("%d ",Frame->count);
                while(Frame->Common_node->head!=NULL)
                {
                        printf("%.3f  ",Frame->Common_node->data);       
                        Frame->Common_node =Frame->Common_node->head;
                }
                printf(" ");
        }
}[/mw_shl_code]


友情提示: 此问题已得到解决,问题已经关闭,关闭后问题禁止继续编辑,回答。