郝斌老师__数据结构_笔记.doc

《郝斌老师__数据结构_笔记.doc》由会员分享，可在线阅读，更多相关《郝斌老师__数据结构_笔记.doc（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构15笔记Array_point 1# include int main(void)int a5 = 1,2,3,4,5;/a3 = *(3+a);printf(%pn, a+1);printf(%pn, a+2);printf(%dn, *a+3); /*a+3等价于 a0+3return 0;Array_point 2# include void Show_Array(int * p, int len)int i = 0;for (i=0; ilen; +i)printf(%dn, pi);/p2 = -1; /p0 = *p p2 = *(p+2) = *(a+2) = a2/pi

2、就是主函数的aiint main(void)int a5 = 1,2,3,4,5;Show_Array(a, 5); /a等价于&a0, &a0本身就是int *类型/printf(%dn, a2);return 0;Point_1# include int main(void)int * p; /p是个变量名字, int * 表示该p变量只能存储int类型变量的地址int i = 10;int j;/p = &i;j = *p; / 等价于 j = i;printf(i = %d, j = %d, *p = %dn, i, j, *p);/p = 10; /errorreturn 0;Poi

3、nt 2# include int main(void)int * p; /p是个变量名字, int * 表示该p变量只能存储int类型变量的地址int i = 10;int j;p = &i;*p = i; / 等价于 i = i;/j = *p; / 等价于 j = i;printf(i = %d, j = %d, *p = %dn, i, j, *p);return 0;Point3# include void f(int * p) /不是定义了一个名字叫做*p的形参, 而是定义了一个形参，该形参名字叫做p,它的类型是int *p = 100; /int main(void)int i

4、= 9;f(&i);printf(i = %dn, i);return 0;数据结构610笔记# include int main(void)double * p;double x = 66.6;p = &x; /x占8个子节 1个字节是8位, 1个子节一个地址double arr3 = 1.1, 2.2, 3.3;double * q;q = &arr0;printf(%pn, q); /%p实际就是以十六进制输出q = &arr1;printf(%pn, q); return 0;# include void f(int * p);int main(void)int i = 10;f(&i

5、);printf(i = %dn, i);return 0;void f(int * p)*p = 99;# include void f(int * q);int main(void)int i = 9;int * p = &i;/ int *p; p = &i;printf(%pn, p);f(&p);printf(%pn, p);return 0;void f(int * q)*q = (int *)0xFFFFFFFF;Malloc1# include # include int main(void)int a5 = 4, 10, 2, 8, 6;int len;printf(请输入你

6、需要分配的数组的长度: len = );scanf(%d, &len);int * pArr = (int *)malloc(sizeof(int) * len);/*pArr = 4; /类似于 a0 = 4;/pArr1 = 10; /类似于a1 = 10;/printf(%d %dn, *pArr, pArr1);/我们可以把pArr当做一个普通数组来使用for (int i=0; ilen; +i)scanf(%d, &pArri);for (i=0; ilen; +i)printf(%dn, *(pArr+i);free(pArr); /把pArr所代表的动态分配的20个字节的内存释

7、放return 0;Memory1# include int f();int main(void)int i = 10;i = f();printf(i = %dn, i);for (i=0; i2000; +i)f();return 0;int f()int j = 20;return j;Memory2# include # include struct Studentint sid;int age;struct Student * CreateStudent(void);void ShowStudent(struct Student *);int main(void)struct Stu

8、dent * ps;ps = CreateStudent();ShowStudent(ps);return 0;void ShowStudent(struct Student * pst)printf(%d %dn, pst-sid, pst-age);struct Student * CreateStudent(void)struct Student * p = (struct Student *)malloc(sizeof(struct Student);p-sid = 99;p-age = 88;return p;Struct1# include # include struct Stu

9、dentint sid;char name200;int age; /分号不能省int main(void)struct Student st = 1000, zhangsan, 20;printf(%d %s %dn, st.sid, st.name, st.age);st.sid = 99;/st.name = lisi; /errorstrcpy(st.name, lisi);st.age = 22;printf(%d %s %dn, st.sid, st.name, st.age);/printf(%d %s %dn, st); /errorreturn 0;Struct22009年8

10、月26日14:18:02如何使用结构体两种方式:struct Student st = 1000, zhangsan, 20;struct Student * pst = &st;1.st.sid2. pst-sidpst所指向的结构体变量中的sid这个成员# include # include struct Studentint sid;char name200;int age; /分号不能省int main(void)struct Student st = 1000, zhangsan, 20;/st.sid = 99; /第一种方式struct Student * pst;pst = &

11、st;pst-sid = 99; /第二种方式 pst-sid 等价于 (*pst).sid 而(*pst).sid等价于 st.sid, 所以pst-sid 等价于 st.sidreturn 0;Struct3# include # include struct Studentint sid;char name200;int age; /分号不能省void f(struct Student * pst);void g(struct Student st);void g2(struct Student *pst);int main(void)struct Student st; /已经为st分

12、配好了内存f(&st);g2(&st);/printf(%d %s %dn, st.sid, st.name, st.age);return 0;/这种方式耗内存 耗时间 不推荐void g(struct Student st)printf(%d %s %dn, st.sid, st.name, st.age);void g2(struct Student *pst)printf(%d %s %dn, pst-sid, pst-name, pst-age);void f(struct Student * pst)(*pst).sid = 99;strcpy(pst-name, zhangsan

13、);pst-age = 22;数据结构1013笔记# include # include /包含了malloc函数# include /包含了exit函数/定义了一个数据类型，该数据类型的名字叫做struct Arr, 该数据类型含有三个成员，分别是pBase, len, cntstruct Arrint * pBase; /存储的是数组第一个元素的地址int len; /数组所能容纳的最大元素的个数int cnt; /当前数组有效元素的个数void init_arr(struct Arr * pArr, int length); /分号不能省bool append_arr(struct Ar

14、r * pArr, int val); /追加bool insert_arr(struct Arr * pArr, int pos, int val); / pos的值从1开始bool delete_arr(struct Arr * pArr, int pos, int * pVal);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 * pArr); void inversion

15、_arr(struct Arr * pArr);int main(void)struct Arr arr;int val;init_arr(&arr, 6);show_arr(&arr);append_arr(&arr, 1);append_arr(&arr, 10);append_arr(&arr, -3);append_arr(&arr, 6);append_arr(&arr, 88);append_arr(&arr, 11);if ( delete_arr(&arr, 4, &val) )printf(删除成功!n);printf(您删除的元素是: %dn, val);elseprint

16、f(删除失败!n);/*append_arr(&arr, 2);append_arr(&arr, 3);append_arr(&arr, 4);append_arr(&arr, 5);insert_arr(&arr, -1, 99);append_arr(&arr, 6);append_arr(&arr, 7);if ( append_arr(&arr, 8) )printf(追加成功n);elseprintf(追加失败!n);show_arr(&arr);inversion_arr(&arr);printf(倒置之后的数组内容是:n);show_arr(&arr);sort_arr(&arr

17、);show_arr(&arr);/printf(%dn, arr.len);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); /终止整个程序elsepArr-len = length;pArr-cnt = 0;return;bool is_empty(struct Arr * pArr)if (0 = pArr-cnt)return tru

18、e;elsereturn false;bool is_full(struct Arr * pArr)if (pArr-cnt = pArr-len)return true;elsereturn false;void show_arr(struct Arr * pArr)if ( is_empty(pArr) ) printf(数组为空!n);elsefor (int i=0; icnt; +i)printf(%d , pArr-pBasei); /int *printf(n);bool append_arr(struct Arr * pArr, int val)/满是返回falseif ( i

19、s_full(pArr) )return false;/不满时追加pArr-pBasepArr-cnt = val; (pArr-cnt)+;return true;bool insert_arr(struct Arr * pArr, int pos, int val)int i;if (is_full(pArr)return false;if (pospArr-cnt+1) /return false;for (i=pArr-cnt-1; i=pos-1; -i)pArr-pBasei+1 = pArr-pBasei;pArr-pBasepos-1 = val;(pArr-cnt)+;ret

20、urn true;bool delete_arr(struct Arr * pArr, int pos, int * pVal)int i;if ( is_empty(pArr) )return false;if (pospArr-cnt)return false;*pVal = pArr-pBasepos-1;for (i=pos; icnt; +i)pArr-pBasei-1 = pArr-pBasei;pArr-cnt-;return true;void inversion_arr(struct Arr * pArr)int i = 0;int j = pArr-cnt-1;int t;

21、while (i pBasei;pArr-pBasei = pArr-pBasej;pArr-pBasej = t;+i;-j;return;void sort_arr(struct Arr * pArr)int i, j, t;for (i=0; icnt; +i)for (j=i+1; jcnt; +j)if (pArr-pBasei pArr-pBasej)t = pArr-pBasei;pArr-pBasei = pArr-pBasej;pArr-pBasej = t;数据结构1422笔记插入节点r = p-pNext; p-pNext = q; q-pNext = r;q-pNext

22、 = p-pNext; p-pNext = q;删除一个节点r = p-pNext;p-pNext = p-pNext-pNext;free(r);数据结构2328笔记List上课敲的程序# include # include # include typedef struct Nodeint data; /数据域struct Node * pNext; /指针域NODE, *PNODE; /NODE等价于struct Node PNODE等价于struct Node */函数声明PNODE create_list(void);void traverse_list(PNODE pHead);bo

23、ol is_empty(PNODE pHead);int length_list(PNODE);bool insert_list(PNODE, int, int); /在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始bool delete_list(PNODE, int, int *);void sort_list(PNODE);int main(void)PNODE pHead = NULL; /等价于 struct Node * pHead = NULL;int val;pHead = create_list(); /create

24、_list()功能：创建一个非循环单链表，并将该链表的头结点的地址付给pHeadtraverse_list(pHead);/insert_list(pHead, -4, 33);if ( delete_list(pHead, 4, &val) )printf(删除成功，您删除的元素是: %dn, val);elseprintf(删除失败!您删除的元素不存在!n);traverse_list(pHead);/int len = length_list(pHead);/printf(链表的长度是%dn, len);/sort_list(pHead);/traverse_list(pHead);/*

25、if ( is_empty(pHead) )printf(链表为空!n);elseprintf(链表不空!n);return 0;PNODE create_list(void)int len; /用来存放有效节点的个数int i;int val; /用来临时存放用户输入的结点的值/分配了一个不存放有效数据的头结点PNODE pHead = (PNODE)malloc(sizeof(NODE);if (NULL = pHead)printf(分配失败, 程序终止!n);exit(-1);PNODE pTail = pHead;pTail-pNext = NULL;printf(请输入您需要生成的

26、链表节点的个数: len = );scanf(%d, &len);for (i=0; idata = val;pTail-pNext = pNew;pNew-pNext = NULL;pTail = pNew;return pHead;void traverse_list(PNODE pHead)PNODE p = pHead-pNext;while (NULL != p)printf(%d , p-data);p = p-pNext;printf(n);return;bool is_empty(PNODE pHead)if (NULL = pHead-pNext)return true;el

27、sereturn false;int length_list(PNODE pHead)PNODE p = pHead-pNext;int len = 0;while (NULL != p)+len;p = p-pNext;return len;void sort_list(PNODE pHead)int i, j, t;int len = length_list(pHead);PNODE p, q;for (i=0,p=pHead-pNext; ipNext)for (j=i+1,q=p-pNext; jpNext)if (p-data q-data) /类似于数组中的: ai ajt = p

28、-data;/类似于数组中的: t = ai;p-data = q-data; /类似于数组中的: ai = aj;q-data = t; /类似于数组中的: aj = t;return;/在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始bool insert_list(PNODE pHead, int pos, int val)int i = 0;PNODE p = pHead;while (NULL!=p & ipNext;+i;if (ipos-1 | NULL=p)return false;PNODE pNew = (PNOD

29、E)malloc(sizeof(NODE);if (NULL = pNew)printf(动态分配内存失败!n);exit(-1);pNew-data = val;PNODE q = p-pNext;p-pNext = pNew;pNew-pNext = q;return true;bool delete_list(PNODE pHead, int pos, int * pVal)int i = 0;PNODE p = pHead;while (NULL!=p-pNext & ipNext;+i;if (ipos-1 | NULL=p-pNext)return false;PNODE q =

30、p-pNext;*pVal = q-data;/删除p节点后面的结点p-pNext = p-pNext-pNext;free(q);q = NULL;return true;课下教师又加了注释的程序# include # include # include typedef struct Nodeint data; /数据域struct Node * pNext; /指针域NODE, *PNODE; /NODE等价于struct Node PNODE等价于struct Node */函数声明PNODE create_list(void); /创建链表void traverse_list(PNOD

31、E pHead); /遍历链表bool is_empty(PNODE pHead); /判断链表是否为空int length_list(PNODE); /求链表长度bool insert_list(PNODE pHead, int pos, int val); /在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始bool delete_list(PNODE pHead, int pos, int * pVal); /删除链表第pos个节点，并将删除的结点的值存入pVal所指向的变量中, 并且pos的值是从1开始void sort_lis

32、t(PNODE); /对链表进行排序int main(void)PNODE pHead = NULL; /等价于 struct Node * pHead = NULL;int val;pHead = create_list(); /create_list()功能：创建一个非循环单链表，并将该链表的头结点的地址付给pHeadtraverse_list(pHead);/insert_list(pHead, -4, 33);if ( delete_list(pHead, 4, &val) )printf(删除成功，您删除的元素是: %dn, val);elseprintf(删除失败!您删除的元素不存

33、在!n);traverse_list(pHead);/int len = length_list(pHead);/printf(链表的长度是%dn, len);/sort_list(pHead);/traverse_list(pHead);/*if ( is_empty(pHead) )printf(链表为空!n);elseprintf(链表不空!n);return 0;PNODE create_list(void)int len; /用来存放有效节点的个数int i;int val; /用来临时存放用户输入的结点的值/分配了一个不存放有效数据的头结点PNODE pHead = (PNODE)

34、malloc(sizeof(NODE);if (NULL = pHead)printf(分配失败, 程序终止!n);exit(-1);PNODE pTail = pHead;pTail-pNext = NULL;printf(请输入您需要生成的链表节点的个数: len = );scanf(%d, &len);for (i=0; idata = val;pTail-pNext = pNew;pNew-pNext = NULL;pTail = pNew;return pHead;void traverse_list(PNODE pHead)PNODE p = pHead-pNext;while (

35、NULL != p)printf(%d , p-data);p = p-pNext;printf(n);return;bool is_empty(PNODE pHead)if (NULL = pHead-pNext)return true;elsereturn false;int length_list(PNODE pHead)PNODE p = pHead-pNext;int len = 0;while (NULL != p)+len;p = p-pNext;return len;void sort_list(PNODE pHead)int i, j, t;int len = length_

36、list(pHead);PNODE p, q;for (i=0,p=pHead-pNext; ipNext)for (j=i+1,q=p-pNext; jpNext)if (p-data q-data) /类似于数组中的: ai ajt = p-data;/类似于数组中的: t = ai;p-data = q-data; /类似于数组中的: ai = aj;q-data = t; /类似于数组中的: aj = t;return;/在pHead所指向链表的第pos个节点的前面插入一个新的结点，该节点的值是val， 并且pos的值是从1开始bool insert_list(PNODE pHead,

37、 int pos, int val)int i = 0;PNODE p = pHead;while (NULL!=p & ipNext;+i;if (ipos-1 | NULL=p)return false;/如果程序能执行到这一行说明p已经指向了第pos-1个结点,但第pos-1个节点是否存在无所谓/分配新的结点PNODE pNew = (PNODE)malloc(sizeof(NODE);if (NULL = pNew)printf(动态分配内存失败!n);exit(-1);pNew-data = val;/将新的结点存入p节点的后面PNODE q = p-pNext;p-pNext =

38、pNew;pNew-pNext = q;return true;bool delete_list(PNODE pHead, int pos, int * pVal)int i = 0;PNODE p = pHead;while (NULL!=p-pNext & ipNext;+i;if (ipos-1 | NULL=p-pNext)return false;/如果程序能执行到这一行说明p已经指向了第pos-1个结点，并且第pos个节点是存在的PNODE q = p-pNext; /q指向待删除的结点*pVal = q-data; /删除p节点后面的结点p-pNext = p-pNext-pNext;/释放q所指向的节点所占的内存free(q);q = NULL;return true;数据结构2934笔记# include # include void f(int k)int m;double * q = (double *)malloc(200);int main(void)int i = 10;int * p = (int *)malloc(100);return 0;Stack# include # include # include typedef struct Nodeint data;