在准备考研的时候就想发学习笔记，想来已经过了多时。现在在培训班又要展开学习，说明一件事：408是指导学习研究计算机的基础！对于编写程序而言，数据结构与算法，是关键！我想其他的组成原理，计算机网络，操作系统也很重要，这是一个system，有必要有需要学习认真的学习之。希望这个是好的开始！
————————————————————————————————————————————————————————————————
昨天晚上看浙大在网易云课上的视频，没有上过浙大的我还是非常激动，哈哈，三个短视频看完之后，有几点我需要记下来的是：
1.数据结构和算法相辅相成。
2.存储换速度。
3.递归不是很好用，会爆栈。（想到严老师那本书里面把递归算法改成非递归算法就头疼，也是有原因的啊）
今天上课的时候我老师也让我们要学会模块化编程，统一化接口，学着像一个要正式上班的程序猿一样~~
——————————————————————————————————————————
线性表
有顺序表和链表，在实际应用中，线性表都是以栈、队列、字符串、数组等特殊线性表的形式来使用的。
当然，这篇文章我只是记录学习顺序表。
特点：
1. 需要一块连续的空间
2. 每个元素都有一个直接前驱和直接后继，但是第一个元素没有前驱，最后一个元素没有后继。
3. 存储密度高，访问效率高
这个很像我们经常接触的数组。一片连续的内存中存放数据类型相同的元素。
/************************************************************************* > File Name: Struct.h > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 10:23:25 AM CST ************************************************************************/#ifndef _STRUCT_H_#define _STRUCT_H_#define SIZE 20enum RETURNVAL{ ERROR = -1, OK, FALSE = 0, TRUE,};typedef int Status;typedef int ElemType;typedef struct LNode{ int lenght; ElemType data[SIZE];}SqList, *pSqList;#endif 定义结构体，相关宏定义~
#ifndef _FUN_H_#define _FUN_H_void insertToList(SqList * Line,int Location,int num);void showItemFromList(SqList * Line);pSqList InitList();void menu();void destoryList(pSqList pList);void delete(pSqList plink,int location , ElemType * DEL_data);int searchFromList(pSqList plink, int num);void updateItemInList(pSqList plink,int location,int number);#endif
申明函数
/************************************************************************* > File Name: InitList.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 10:55:57 AM CST ************************************************************************/#include#include"Struct.h"#include #include pSqList InitList(){ pSqList pList = (pSqList)malloc(sizeof(SqList)); if (NULL != pList) memset(pList,0,sizeof(SqList)); return pList;}void destoryList(pSqList pList){ if (NULL == pList) printf("destoryList failed"); free(pList); pList = NULL;}
初始化函数---我没有设置成动态开辟malloc，设成了死的，以后补上动态开辟的，
当然，有malloc 就有 free ，我们时刻记住开辟的内存要还回去，这样不会造成内存泄漏~
/************************************************************************* > File Name: showItemFromList.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 10:24:39 AM CST ************************************************************************/#include#include"Struct.h"void showItemFromList(SqList * pList){ int i; if (NULL == pList) { printf("there is nothing\n"); return ; } printf("Liner List is \n"); for(i = 0;i < pList->lenght;i++) printf("%d\t",pList->data[i]); printf("\n");}
显示函数---线性表的好处，一通到底。。
/************************************************************************* > File Name: insert.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 10:22:28 AM CST ************************************************************************/#include#include"Struct.h"#define SIZE 20void insertToList(SqList * pLink,int Location,int num){ int i; if (Location > pLink->lenght + 1 ||(Location < 0) ||(pLink->lenght == SIZE) ) { printf("dont input number in a mistakeble way"); } else { for(i = pLink->lenght;i >= Location; i--) pLink->data[i] = pLink->data[i - 1]; pLink->data[Location - 1] = num; pLink->lenght++; }}
插入函数，那些报错的代码，应该那样明白的写出来。
这里就有顺序表的劣势了，和链表比起来，需要动的数据太多了。
/************************************************************************* > File Name: delete.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 03:58:51 PM CST ************************************************************************/#include#include"Struct.h"void delete(pSqList plink,int location , ElemType * DEL_data){ if (location > plink->lenght) { printf("there are not %d in the link\n",location); return; } if ( NULL == plink ||(location < 0) ) { printf("illegal input"); return; } *DEL_data = plink->data[location - 1]; int i; if (location == SIZE) { plink->lenght--; } else { for(i = location - 1;i < plink->lenght;i++ ) plink->data[i] = plink->data[i + 1]; plink->lenght--; }}
删除 和插入差不多
/************************************************************************* > File Name: menu.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 11:28:05 AM CST ************************************************************************/#include#include void menu(){ printf("1......insert\n"); printf("2......show\n"); printf("3......delete\n"); printf("4......destory\n"); printf("5......search\n"); printf("6......updata\n"); printf("please input you choise:\n");}
菜单~
/************************************************************************* > File Name: search.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 05:00:17 PM CST ************************************************************************/#include#include"Struct.h"int searchFromList(pSqList plink, int num){ if (NULL == plink) return ERROR; int i; for( i = 0; i < plink->lenght ; i++ ) if (num == plink->data[i]) return i; printf("there isn't the number %d in the link\n",num);}
顺序表能立马找到数据的位置也是优势
/************************************************************************* > File Name: updateItemInList.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 05:10:49 PM CST ************************************************************************/#include#include"Struct.h"void updateItemInList(pSqList plink,int location,int number){ if (NULL == plink) printf("error!"); plink->data[location - 1] = number;}
和查找差不多！
/************************************************************************* > File Name: Sort.c > Author: aaron > Mail: 60360329@163.com > Created Time: Tue 14 Mar 2017 22:59:06 PM CST ************************************************************************/#include"Struct.h"#includeint partition(pSqList plink, int low, int high){ int pivotkey = plink->data[low]; while (low < high) { while (low < high && plink->data[high] >= pivotkey ) --high; plink->data[low] = plink->data[high]; plink->data[high] = pivotkey; while (low < high && plink->data[low] <= pivotkey ) ++low; plink->data[high] = plink->data[low]; plink->data[low] = pivotkey; } return low;} void quickSort(pSqList plink, int low, int high){ int pivot; if(low < high) { pivot = partition(plink, low, high); quickSort(plink, low, pivot - 1); quickSort(plink, pivot + 1, high); } }
快速排序！看别人的哈哈 书上有算法~~
——————————————————————————————————————————————————————————————————后补上动态
2017-03-1613:51:51
typedef int Elemtypetypedef struct ListNode{ Elemtype * pData; int count; int totalSize;}ListNode,* pListNode;//createpListNode pList = malloc(sizeof(ListNode));memset(pList,0,sizeof(ListNode));pList->totalSize = SIZE;pList->pData = (Elemtype)malloc(pList->totalSize);//add_storepList->totalSize += SIZE;pList->pData = (Elemtype)realloc(pList->pData,pList->totalSize);