网站首页 C及单片机 菜鸟学数据结构
菜鸟学数据结构
编辑时间:2017-03-26 作者:金满斗 浏览量:514 来源:原创

当时是照着传智还是什么的写的,时间长了也记不清楚了。既然重新温习C语言。干脆把这段代码放上来,有时候也可以看看。

菜鸟学数据结构之(1)创建简单的结构体及使用

#include <stdio.h>
/*定义简单的结构体*/
struct Student{
 int sid;
 char name[2000];
 int age;
};
/*结构体显示的几种种方式*/
void xians(struct Student sta ){
 printf("sid=%d name =%s age=%d\n",sta.sid,sta.name,sta.age);
}
void xians2(struct Student sta ){
 struct Student *p = &sta ;   /*先定义一个结构体指针*/
 printf("sid=%d name =%s age=%d\n",p->sid,p->name,p->age);  /*这里的p->sid 就等于(*p).sid */
}
/*上面的都不推荐,因为耗费内存*/
void xians3(struct Student *p){  /*这样传指针只需要传4个字节,好*/
 printf("sid=%d name =%s age=%d\n",p->sid,p->name,p->age);  /*这里的p->sid 就等于(*p).sid */
}
 
int main(void){
 struct Student st = {1,"wode",20};
 xians(st);
 xians2(st);
 xians3(&st);
  
}


菜鸟学数据结构之(2)动态分配内存

#include <stdio.h>
#include <malloc.h>
int main(void)
{ int a[5] ={4,10,2,8,6};
int len;
printf("请输入你要使用数组的长度len=");
scanf("%d",&len);
int *parr = (int *)malloc(sizeof(int)*len); /*动态分配内存*/
*parr =4;
parr[1] = 5; /*可以这样直接赋值*/
for(int i=0;i<len;i++){
scanf("%d",&parr[i]);
}
 
 
for(int i=0;i<len;i++){
printf("%d\n",*(parr+i));
}
free(parr); /*释放指针*/
return 0;
}

菜鸟学数据结构之(3)跨函数使用内存

/*跨函数使用内存例子*/
 
#include <stdio.h>
#include <malloc.h>
 
/*定义一个结构体*/
struct Student  {
 int sid;
 int age;
};
 
struct Student * CreateStudent(void);   //创建结构体函数 ,返回值为结构体指针
void showStudent(struct Student *);   //定义显示结构体函数 ,无返回值,参数为结构体指针
 
int main(void)
{
 struct Student * st;
 st =  CreateStudent();
 st->sid = 50;
 st->age = 80;
 showStudent(st);
 free(st);         //释放 指针
 return 0;
}
 
struct Student * CreateStudent(void){
 struct Student * p = (struct Student * )malloc(sizeof(struct Student));
 return p;
}
 
void showStudent(struct Student *p){
 printf("sid=%d,age=%d\n",p->sid,p->age);
}

菜鸟学数据结构之(4) 模拟数组操作

/*模拟数组的一些常用操作*/
#include <stdio.h>
#include <malloc.h>   /*内存操作*/
#include <stdlib.h>   /*包含了exit函数*/
 
/*定义一个数据类型,名称叫struct Arr*/
struct Arr{
        int *pBase; /*存储数组第一元素地址*/
        int len;  /*数组容纳最大元素的个数*/
    int cnt;   /*当前数组的个数*/
};
void init_arr(struct Arr *pArr,int length);  /*初始化,参数为指针,数组预置长度*/
bool append_arr(struct Arr *pArr,int val); /*追加末尾,参数为指针,追加内容*/
bool insert_arr(struct Arr *pArr,int pos,int val);  /*某位插入,参数为指针,插入位置,插入内容**/
bool delete_arr(struct Arr *pArr,int pos,int *val);  /*删除,参数为指针,删除位置,返回删除元素的指针*/
int get();             /*获取*/
bool is_empty(struct Arr *pArr);  /*判断是否为空*/
bool is_full(struct Arr *pArr);     /*判断是否满*/
void sort_arr(struct Arr *pArr);   /*排序*/
void show_arr(struct Arr *);    /*显示输出*/
void inversion_arr(struct Arr *);        /*倒置*/
void quicksort_arr(struct Arr *,int,int);   /*快速排序*/
 
int main(void)
{
        struct Arr arr;     /*创建一个数组变量*/
        struct Arr *parr = &arr; 
        init_arr(parr,8);    /*初始化数组*/
        show_arr(parr); 
        printf("尾部添加\n"); 
        append_arr(parr,2);
        append_arr(parr,33);
        append_arr(parr,41);
        append_arr(parr,5);
        append_arr(parr,62);
        append_arr(parr,7);
        show_arr(parr); 
        printf("动态插入\n"); 
        insert_arr(parr,7,0);
        show_arr(parr); 
        printf("删除\n"); 
        int val;    /*为删除元素准备个变量*/
        if(delete_arr(parr,2,&val)) {
                printf("删除成功,删除元素为%d\n",val); 
        }else{
                printf("删除失败\n"); 
        } 
         
        show_arr(parr); 
        printf("倒序--------\n"); 
        inversion_arr(parr); 
        show_arr(parr); 
        printf("排序--------\n");
        sort_arr(parr); 
        show_arr(parr);
        append_arr(parr,42);
        append_arr(parr,8);
        append_arr(parr,14);
        printf("快速排序--------\n"); 
        quicksort_arr(parr,0,8);
        show_arr(parr);
         
         
        return 0;
}
 
/*初始化数组*/
void init_arr(struct Arr *pArr,int length){
        pArr->pBase = (int *)malloc(sizeof(int)* length);  /*给数组分配内存*/
        if(NULL==pArr->pBase){
                printf("动态内存分配失败\n"); 
                exit(-1);/*终止整个程序*/
        }else{
                pArr ->len = length;
                pArr -> cnt = 0; 
        } 
        return;
}
/*显示数组*/
void show_arr(struct Arr *pArr){
        if(is_empty(pArr)){
                printf("数组为空\n"); 
        }else{
                for(int i=0;i<pArr->cnt;i++){
                        printf("%d\n",pArr->pBase[i]);
                }
        }
}
/*判断数组是否为空*/
bool is_empty(struct Arr *pArr){
        if(0==pArr ->cnt)return true;
        return false;
}
 
bool append_arr(struct Arr *pArr,int val){
        if(is_full(pArr)){
                printf("数组已经满了\n");
                return false; 
        } 
        (pArr->cnt)++;
        pArr->pBase[pArr->cnt -1] = val;
        return true;
} 
 
 
/*判断数组是否已满*/
bool is_full(struct Arr *pArr){
  if(pArr->cnt == pArr->len)return true;  /*如果数组长度等于分配长度,则返回真*/
  return false; 
}
 
/*插入数组元素*/
bool insert_arr(struct Arr *pArr,int pos,int val){
        if(is_full(pArr)){
                printf("数组已经满了\n");
                return false; 
        } 
        int i = pArr->cnt;
        if(pos<1 || pos > i+1)return false;
 
        for(i;i > pos-1;i--){
                pArr->pBase[i] = pArr->pBase[i-1];        
        }
        pArr->pBase[pos-1] = val;
        (pArr->cnt)++;
        return true;
} 
/*删除数组元素*/
bool delete_arr(struct Arr *pArr,int pos,int *val){
        if(is_empty(pArr)) return false;
        int i = pArr ->cnt;
        if(pos<1 || pos>i) return false;
        *val = pArr->pBase[pos-1];
        for(pos;pos<i;pos++){
                pArr->pBase[pos-1] = pArr->pBase[pos];
        }
        (pArr->cnt)--;
        return true;        
} 
/*倒置*/
void inversion_arr(struct Arr *pArr){
        int i = 0;
        int j = pArr->cnt -1;
        int t;
        while(i<j){
                t =  pArr->pBase[i]; 
                pArr->pBase[i] = pArr->pBase[j];
                pArr->pBase[j] = t;
                i++;
                j--;
        }        
}
 
/*排序*/
void sort_arr(struct Arr *pArr){
        int i,j,t;
        for(i=0;i< pArr->cnt;i++){
                for(j=i+1;j<pArr->cnt;j++){
                        if(pArr->pBase[i]>pArr->pBase[j]){
                                t =  pArr->pBase[i]; 
                                pArr->pBase[i] = pArr->pBase[j];
                                pArr->pBase[j] = t;
                        }
                }
        } 
}
/*快速排序*/
void quicksort_arr(struct Arr *pArr,int left,int right){
        if(left > right) return;
        int i,j,t;
        i = left;
        j = right;
        t = pArr ->pBase[i];
        while(i != j){
           while(pArr->pBase[j] >= t && i<j){
                    j--;
                   }
                   if(i<j) pArr->pBase[i] = pArr->pBase[j];  /*先右边往左边移,这里填坑到左边基准*/
                   while(pArr->pBase[i]  < t && i<j){
                           i++;
                }
                if(i<j)pArr->pBase[j] = pArr->pBase[i];  /*左边和右边比较,填坑到右边*/
        }
        pArr->pBase[i] = t;  /*一段左右下来,把最初始的安排个位置放*/
        quicksort_arr(pArr,left,i-1);
        quicksort_arr(pArr,i+1,right); 
}

菜鸟学数据结构之(5)链表的一些算法

#include <stdio.h>
#include <malloc.h>   /*内存操作*/
#include <stdlib.h>   /*包含了exit函数*/
 
 
/*定义线线性表单链表存储结构*/
typedef struct Node{
    int data;            /*数据域*/
    struct Node *pNext;   /*指针域*/
} Node,*linkList;        /*Node 等价于typedef struct Node , *linkList 等价于typedef struct Node*   */
 
 
 
/*创建单链表*/
 
linkList crrate_list(void);
void traverse_list(linkList );  /*遍历链表*/
bool is_empty(linkList ); /*判断是否为空*/
int length(linkList);  /*判断链表长度*/
void sort_list(linkList); /*排序*/
bool insert_list(linkList,int pos,int val);  /* 向链表的pos的前面插入一个新节点,节点内容是val,并且pos是1开始*/
bool delete_list(linkList,int pos,int*);  /*通过第3个参数指针可以得到删除的数据*/
 
int main(void)
{
    linkList pHead = NULL;
    pHead = crrate_list();
    if(is_empty(pHead)){
        printf("链表为空\n");
    }
    printf("链表长度为%d\n",length(pHead));
    if(insert_list(pHead,4,99)){
        printf("99插入成功\n");
    };
    sort_list(pHead);
    int m; 
    if(delete_list(pHead,4,&m)) {
        printf("删除成功,删除数字为%d\n",m);
    }else{
            printf("删除失败");
    }
     
     
    traverse_list(pHead);
    return 0;
}
 
linkList crrate_list(void){
    int len;  /*设置链表的长度*/
    int i;
    int val;    /* 用来临时存放用户节点值 */
    printf("请输入链表的长度len=");
    scanf("%d",&len);
    /*先分配个头节点*/
    linkList pHead = (linkList)malloc(sizeof(Node));
    if(NULL == pHead){
            printf("分配内存失败,程序终止!\n");
            exit(-1); 
        }
    linkList pwei = pHead;    /*定义一个尾节点,指向头节点*/
    pwei ->pNext = NULL;
    for(i=0;i<len;i++){
        printf("请输入第%d节点的值:",i+1);
        scanf("%d",&val);
        linkList pNew = (linkList)malloc(sizeof(Node));
        if(NULL == pNew){
            printf("分配内存失败,程序终止!\n");
            exit(-1); 
        }
        pNew ->data = val;
        pwei ->pNext = pNew;
        pNew ->pNext = NULL;
        pwei = pNew;
         
         
    } 
    return pHead;
}
/*遍历链表*/
void traverse_list(linkList pHead){
    linkList p = pHead ->pNext;
    while(NULL != p){
        printf("%d ",p ->data);
        p = p ->pNext;
    }
    printf("\n");
    return;
}
/*判断链表是否为空*/
bool is_empty(linkList pHead){
    linkList p = pHead ->pNext;
    if(NULL == p) return true;
    return false;
     
} 
/*判断链表长度*/
int length(linkList pHead){
    linkList p = pHead ->pNext;
    int i = 0;
    while(NULL != p){
        p = p ->pNext;
        i++;
    }
    return i;
}  
 
/*排序*/
void sort_list(linkList pHead){
    int t,j,i;
    int len = length(pHead);
    linkList p,q;
    for(i=0,p = pHead ->pNext;i<len-1;i++,p = p ->pNext){
        for(j=1+i,q = p->pNext;j<len;j++,q = q-> pNext){
            if(p->data > q ->data){
                t = p ->data;
                p ->data = q ->data;
                q ->data = t;
            }
        }
    }
    return;
 
}
bool insert_list(linkList pHead,int pos,int val){
    int i =0;
    linkList p = pHead ->pNext;
    while(p != NULL && i < pos-1){
        p = p ->pNext;
        i++;
    }
    if(p == NULL || i > pos-1) return false;
    linkList pNew = (linkList)malloc(sizeof(Node));
        if(NULL == pNew){
            printf("分配内存失败,程序终止!\n");
            exit(-1); 
        }
    pNew ->data = val;
    linkList q = p ->pNext;
    p ->pNext = pNew;
    pNew ->pNext = q;
    return true;    
} 
 
bool delete_list(linkList pHead,int pos,int* pval){
    int i =0;
    linkList p = pHead ->pNext;
        while(p != NULL && i < pos-1){
        p = p ->pNext;
        i++;
    }
    if(p == NULL || i > pos-1) return false;
    linkList q = p ->pNext;
    *pval = q ->data;
    p ->pNext = p ->pNext ->pNext;
    free(q);
    q = NULL;
    return true;
}


来说两句吧